将2D网格图数据结构转换为树

Question

我有一个网格:

网格由单元组成,递归地分成较小的单元.网格中的每个子单元格都受其父级约束.

网格中的单元格以图形结构存储.每个单元有四个连接,每个角落一个.每个角连接到另一个单元,使得单元的边缘平行于连接并且最靠近它是齐平的.此网格可以由以下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
    }
}

这是对结构的描述:

通过查看图表,人们可以看到包含较小细胞群的较大细胞群. 我正在尝试开发一种算法,该算法可以采用网格数据结构并将其转换为树.树中的每个元素都是一个叶子(表示网格中的一个单元格)或一个包含较小容器或网格中单元格的容器.这是网格看起来像树的样子:

到目前为止,我没有太多运气.这是我到目前为止所尝试的:

• 我尝试在外面工作,确定网格的较大部分,然后将它们分开以找到较小的部分.问题是很难确定容器的构成,以及如何在网格本身之外选择网格中最大的容器.
• 我尝试将单个细胞和一条链子连接到它们最大的亲本,然后将这些链组合成一个网格.这种方法的问题是父容器并不总是很明显.
• 我尝试了一个网格,将它分成更小的网格,并沿着它最大的边缘将它分开.然而,当遇到边缘的末端时,很难判断结尾是否实际上是网格的边缘,或者它是否是局部边缘.
• 我试图确定网格中哪些单元格有直接兄弟(通过注意哪些连接位于连接到同一单元格的单元格的同一侧.然后我将它们放在容器中,用容器替换结构中的单元格并重复这个过程.我相信这种方法可能确实有效,但看起来非常麻烦且效率低下.
• 最后,我查看了几个不同的数据结构,包括树形图.我相信树形图是一个非常好的数据结构,在这个实例中使用,但我的网格已经内置了一个结构.我找到的所有构建kd树的算法都没有在网格中假设任何预先存在的结构.

我真的坚持这一点,我将不胜感激任何意见,建议或想法.

更新

在看了Yochai Timmer的回答之后,我想强调网格结构的重要性.这是两个看起来相同但具有不同结构的框的示例,因此具有非常不同的树表示:

Answer 1

我认为你的第四个选择是正确的选择。我认为实现并不那么复杂：我将维护一组森林的根节点，初始化为网格中的所有框（作为大小为 1 的树）。然后继续迭代该集合，检查您正在检查的框是否连接到任何具有两条边的框。如果是，则将两者替换为更大的盒子，并使该更大的盒子成为森林中的父节点。

有一个微妙之处，我不确定它在您的应用程序中有多重要。对于上面的主要示例，您不会在根处获得三元节点：而不是

     Root
/-----+-----\
|     |     |
A     B     C  

你会得到类似的东西

       Root
    /---^---\
   D        C
/--^--\
A     B

但是，我认为您可以在后处理步骤中检测到这种情况并在之后纠正它们：遍历树，并针对每个节点检查它是否代表水平或垂直连接，以及节点 X 是否具有与其父级 Y 方向相同，然后删除 X 并使其子级成为 Y 的子级。