I think I’ll frame today’s progress report as a coding problem. (I don’t know about you, maybe I’m weird, but this tickles my fancy!) Feel free to challenge yourself by not reading the solution until you have one of your own in mind, or to simply enjoy reading about it if you prefer that.
In preparation for implementing the Delete operation in a GridTree, I have to be able to clean up the space afterwards. Deleting involves three primary steps:
Remove Ownership: Set the parent’s Grid entries owned by that child to None (claimed at higher levels, but not currently claimed by a particular child), and remove the child from the child list.
Clear the Space: Clear out relevant empty (None) spaces, still keeping the parent’s Grid orthoconvex. This freeing of space recurses upwards.
Orthoconvex is like convex, but only checked along orthogonal lines. In standard convexity, shapes like bars and rectangles are allowed. Orthoconvexity further allows shapes like L, +, zigzags, etc., while neither form allows shapes like C or U (they don’t pass the line test).
We need orthoconvexity for shapes not to lock up when they need to move apart in the Grid.
Collapse: Pull siblings around into the freed space so we aren’t left with big awkward gaps all over the tree bloating the layout.
We’re on step 2.
Write a function, ‘convex_trim_rect’, which takes in a map or dictionary; this is our grid. It’s keys are coordinate pairs (integer tuples), and its values are either None (null), something, or not in the dictionary. It also takes an outer bounding box, and a rectangle to check within. These are each 4-tuples in the form of (x1, x2, y1, y2). My example code will be in Python. Here’s some scaffolding to start you off with:
Your goal is to scan for and remove any None entries in the grid which are safe to remove (keeping the rest orthoconvex). Return the coordinate pairs removed.
Expectations:
The grid should not be split by the cleanup; we need connected orthoconvexity for a Grid’s smooth push-apart guarantee to work.
Your solution should be complexity-bounded by O(n), where n is the number of entries in the grid. While actual steps can be greater than n, it should be as optimized as possible; memory reads from these dictionary-based grids are not as fast as from an array, and so we want to minimize the number of reads.
Assumptions:
The given grid will always have at least one child entry.
Grids could be on the order of hundreds of nodes wide or tall, or as small as a single cell.
Coordinates may be negative.
You may assume that the existing grid’s entries already form an orthoconvex shape.
Bounds are inclusive. (Handle up to and including each side given.)
You are allowed to check cells outside the bounds in a grid. You may assume that these are all empty (but for an extra challenge you may handle the case where the given bounds represent only a sub-rectangle of an existing orthoconvex shape, so some entries outside the bounds will be filled or None).
You can use these example grids to test your solution:
To be clear, this coding challenge represents only a simplified version of the problem; the full solution required for GridTrees requires handling additional details I haven’t included in the problem above:
Recursing these changes up the tree
Optimize for only a sub-rectangle within the bounds having changed, but some checks still need done outside of it for adjacent occupied spaces that may need trimmed because of trims inside it
Adjusting the bounds after clearing space, if needed
Handling history functions in the GridTree
Maybe some more stuff I forgot…
I’ll give my actual solution below, and I will try to explain my algorithm briefly, and the iterative process of thinking through and trying multiple solutions. They all use about the same approach, which is very different from the line-trimming method I use when a cascading push moves nodes around, which I touched on in the last post (to be explained some other time). Your solution might use an entirely different approach than mine; if so, post it in the comments, as I’d be curious to know about it!
*** SOLUTION SPOILERS BELOW ***
Let’s begin by talking about a few cases, considering how many neighbors a given None entry has:
No neighbors: The cell can be cleared.
One neighbor (only counting the four cardinal directions): The cell can be cleared.
Two neighbors, not opposite each other: The cell can be cleared.
Two neighbors, opposite each other: The cell is NOT to be cleared. (It would split the shape.)
Three neighbors: The cell is NOT to be cleared. (It would make the shape concave.)
Four neighbors: The cell is NOT to be cleared. (It would make a hole.)
So, a naive solution would simply check each cell for these conditions. This would be O(n) complexity (considered lightweight here, since a grid is considered small compared to the rest of the tree).
However, it’s not as simple as that; this solution won’t work because of the following additional cases:
N can be cleared if a neighbor (X) can be cleared.
The cell would be clearable, except that this would split the convex shape, making it disconnected, so it is NOT to be cleared.
The first thing to note, is that order matters. N can and must be cleared, but only if X is—so, we clear X first, then check N again. We could just iteratively check all cells over and over until no changes remain, using an eight-neighbor set of rules instead of four, but that would be O(n2) complexity, which is unacceptable. (With a leading coefficient of 9, too!) No, another solution must be found.
The nice thing is, we never have the problem that X can also only be cleared if N is—that would require a rather high complexity algorithm to solve if several cells depended entirely on each other. Instead, in our case we can always follow the trail back to a starting point, some cell that can be cleared for sure.
Another point to note is that the “starting point” will always be within the area that just changed in the grid. While this doesn’t matter for your solution, it does allow me, in the real GridTree, to define a smaller rectangle in which to check for None entries which are immediately removable, and then expand outward from there, re-checking the neighbors of any item which gets deleted. (I first made the mistake of thinking only nodes within that rectangle might need removed, but then realized removing these could cause others to be removable as well.
(Usable, but not super fast or reliable)
My first idea was a flood-fill technique starting from the corners of the rectangle, and flooding over empty spaces to find “corners” and “ends” of regions of Nones, because these will be removable—if the shape has been kept orthoconvex thus far, then any None at a corner can be cleared, as well as any sticking out with three empty sides. The flood is discontinued at full cells, but those with Nones get checked, and their None neighbors are added onto the queue for checking (even if they have been checked before). This way there would always be forward progression through the swaths of trimmable Nones, and any cell could be added at most four times (one for each neighbor).
At first, I thought I had to start from the four corners and work my way in to identify these “starting points”. Because of the way orthoconvexity works, this would work, but would easily break if for some reason the shape wasn’t already orthoconvex.
(Ding ding ding!)
Now, after some thought I realized that I don’t have to flood from the empty spaces at all, it’s a waste of lookups. Instead, I could simply scan through only the entries which were full (since it’s a map/dict, not an array), and add all Nones onto the queue to begin with. A cell will still have to re-add its neighbors if it itself is cleared, because clearing it might make a neighbor that was previously locked in removable. This way the trimming travels along regions of Nones happily. There’s still the potential of up to perhaps four visits per None entry, but that’s the price we pay for a simple workaround for the order-dependency problem.
This proved to be an excellent solution, and I implemented the pure algorithm in a test file, with the test cases I gave you (modified for my different direction convention). As I began to integrate it into the GridTree to work with my existing code, however, I realized something big.
But first, here’s the code, for those of you who are curious.
(The solution that eats my other solutions for breakfast)
Now, the next development of the algorithm is terribly minor - just feed it a list of cells to check instead of scanning the whole rectangle. No big deal. This was simply an optimization when attaching it to my other code, so that… hang on, this could replace the line-trimming method, too!
As it turns out, my very complicated solution which checks rows or columns that changed, and scans them in a fairly efficient way that is directionally dependent (so it doesn’t have to check as many neighbors) can easily be replaced by this simple solution—and it is just as fast, because while a flood method revisits a few cells, the line trimming method scans whole lines of cells in a rectangle to check for convexity rules.
Occam’s Razor—the simplest solution is usually the best. This is so much less complicated, easier to explain, and unifies all of my convex trimming in the whole tree under one simple algorithm. Woohoo! It’s a bit of a shame to discard my brilliant line-trimming method, but this solution feels good. And, as a nice bonus, it will be easier to explain in a research paper, soon.
The most beautiful part? Seeing it work :)
Yaaaaaayyyy!!
(You know, minus the collapsing part, which is the next step.)
Comments
Nothing yet. Say the first thing.
Sign in to join the conversation.