Converting a 2D grid graph data structure to a tree

Question

I have a grid:

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:

Grid graph 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:

Grid tree structure

So far I haven't had much luck. Here's what I've tried so far:

I tried working outside in, determining the larger portions of the grid and then splitting them apart to find the smaller portions. The problem is it's difficult to determine what constitutes a container, and how to pick the largest one in the grid besides the grid itself.
I tried taking individual cells and following a chain to their largest parent, and then combining the chains to form a grid. The problem with this approach is the parent container isn't always obvious.
I tried taking a grid, splitting it into smaller grids and splitting it apart along its largest edge. However, when meeting the end of an edge, it's tough to tell if the end is actually the edge of the grid or if it's a local edge.
I tried to determine which cells in the grid have direct siblings (by noting which connections are on the same side of a cell connecting to the same cell. I then place these in a container, replace the cells in the structure with the container and repeat the process. I believe this approach might actually work, but it seems very cumbersome and inefficient.
Finally, I looked at several different data structures, include tree maps. I believe the tree map is a very good data structure to use in this instance, but my grid already has a structure built into it. All of the algorithms I could find which built kd trees didn't assume any preexisting structure in the grid.

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:

Grids with different structures

Erik P. Erik P. · Accepted Answer · 2012-07-12T16:24:24

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.

Converting a 2D grid graph data structure to a tree

2 Answers