I have a grid:
The grid is composed of cells, recursively split into smaller cells. Each child cell in the grid is constrained by its parent.
The cells in the grid are stored in a graph-like structure. Each cell has four connections, one in each corner. Each corner connects to another cell such that the edges of the cells parallel to the connection and closest to it are flush. This grid could be represented by the following JSON:
{
"grid1":
{
"topLeft": null,
"topRight": "grid2",
"bottomLeft": "grid3",
"bottomRight": "grid2",
"topLeftDirection": null,
"topRightDirection": "horizontal",
"bottomLeftDirection": "vertical",
"bottomRightDirection": "horizontal"
},
"grid2":
{
"topLeft": "grid1",
"topRight": "grid4",
"bottomLeft": "grid1",
"bottomRight": "grid5",
"topLeftDirection": "horizontal",
"topRightDirection": "horizontal",
"bottomLeftDirection": "horizontal",
"bottomRightDirection": "vertical"
},
"grid3":
{
"topLeft": "grid1",
"topRight": "grid2",
"bottomLeft": null,
"bottomRight": "grid10",
"topLeftDirection": "vertical",
"topRightDirection": "vertical",
"bottomLeftDirection": null,
"bottomRightDirection": "horizontal"
},
"grid4":
{
"topLeft": "grid2",
"topRight": "grid7",
"bottomLeft": "grid5",
"bottomRight": "grid5",
"topLeftDirection": "horizontal",
"topRightDirection": "horizontal",
"bottomLeftDirection": "vertical",
"bottomRightDirection": "vertical"
},
"grid5":
{
"topLeft": "grid4",
"topRight": "grid4",
"bottomLeft": "grid6",
"bottomRight": "grid6",
"topLeftDirection": "vertical",
"topRightDirection": "vertical",
"bottomLeftDirection": "vertical",
"bottomRightDirection": "vertical"
},
"grid6":
{
"topLeft": "grid5",
"topRight": "grid5",
"bottomLeft": "grid9",
"bottomRight": "grid8",
"topLeftDirection": "vertical",
"topRightDirection": "vertical",
"bottomLeftDirection": "vertical",
"bottomRightDirection": "horizontal"
},
"grid7":
{
"topLeft": "grid4",
"topRight": "grid11",
"bottomLeft": "grid8",
"bottomRight": "grid8",
"topLeftDirection": "horizontal",
"topRightDirection": "horizontal",
"bottomLeftDirection": "vertical",
"bottomRightDirection": "vertical"
},
"grid8":
{
"topLeft": "grid7",
"topRight": "grid7",
"bottomLeft": "grid6",
"bottomRight": "grid9",
"topLeftDirection": "vertical",
"topRightDirection": "vertical",
"bottomLeftDirection": "horizontal",
"bottomRightDirection": "vertical"
},
"grid9":
{
"topLeft": "grid6",
"topRight": "grid8",
"bottomLeft": "grid10",
"bottomRight": "grid10",
"topLeftDirection": "vertical",
"topRightDirection": "vertical",
"bottomLeftDirection": "vertical",
"bottomRightDirection": "vertical"
},
"grid10":
{
"topLeft": "grid9",
"topRight": "grid9",
"bottomLeft": "grid3",
"bottomRight": "grid12",
"topLeftDirection": "vertical",
"topRightDirection": "vertical",
"bottomLeftDirection": "horizontal",
"bottomRightDirection": "horizontal"
},
"grid11":
{
"topLeft": "grid7",
"topRight": null,
"bottomLeft": "grid12",
"bottomRight": "grid12",
"topLeftDirection": "horizontal",
"topRightDirection": null,
"bottomLeftDirection": "vertical",
"bottomRightDirection": "vertical"
},
"grid12":
{
"topLeft": "grid11",
"topRight": "grid11",
"bottomLeft": "grid10",
"bottomRight": null,
"topLeftDirection": "vertical",
"topRightDirection": "vertical",
"bottomLeftDirection": "horizontal",
"bottomRightDirection": null
}
}
Here's a depiction of the structure:
By looking at the graph a person can see larger groups of cells which contain smaller groups of cells. I'm trying to develop an algorithm which can take the grid data structure and convert it into a tree. Each element in the tree is either a leaf (which represents a cell in the grid) or a container containing smaller containers or cells in the grid. Here's what the grid looks like as a tree:
So far I haven't had much luck. Here's what I've tried so far:
I'm really stuck on this and I would appreciate any comments, suggestions or ideas.
Update
After looking at Yochai Timmer's answer, I want to stress how important the grid structure is. Here's an example of two boxes which look the same, but have different structures and as a result have very different tree representations:
I think your fourth option is the way to go. I think implementation is not all that complicated: I would maintain a set of root nodes of a forest, initialized to all the boxes in your grid (as trees of size 1). Then just keep iterating through that set, checking whether the box that you're examining is connected to any box with two edges. If it is, then replace both with a bigger box, and make that bigger box their parent node in the forest.
There is one subtlety, which I'm not sure of how important it is in your application. For the main example above, you would not get a ternary node at the root: instead of
Root
/-----+-----\
| | |
A B C
you would get something like
Root
/---^---\
D C
/--^--\
A B
However, I think you would be able to detect such situations in a post-processing step and correct them afterwards: walk the tree, and for each node check to see if it represents a horizontal or a vertical join, and if a node X has the same orientation as its parent Y, then remove X and make its children additional children of Y.
You could make a graph from the grid, where you have an edge between every "box" to is neighbors.
Then decide on a weight for the edges (i would use min(v1,v2)) to decide some kind of ordering.
Then just use a Minimum spanning tree algorithm to create the tree.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With