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

我有一个网格：

网格由单元组成，递归地分割成更小的单元。 网格中的每个子单元都受其父级约束。

网格中的单元格存储在类似图形的结构中。 每个单元有四个连接，每个角落都有一个连接。 每个角落都连接到另一个单元，以使与连接平行且距离其最近的单元边缘齐平。 这个网格可以用下面的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的回答后，我想强调电网结构的重要性。 以下是两个框的示例，它们看起来相同，但具有不同的结构，因此具有非常不同的树表示形式：

---

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

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

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

你会得到类似的东西

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

然而，我认为你可以在后期处理步骤中检测到这种情况，并在之后对其进行修正：遍历树，并检查每个节点是否代表水平或垂直连接，并且如果节点X具有与其父母Y相同的方向，然后移除X并使其子女成为Y的额外孩子。

---

你可以从网格中创建一个图表，在每个“框”之间有一条边是邻居。

然后决定边的权重（我会用min（v1，v2））来决定某种排序。

然后使用最小生成树算法创建树。

链接地址: http://www.djcxy.com/p/10943.html

上一篇: Converting a 2D grid graph data structure to a tree

下一篇: Show marker inside a resource drawable which obtained from url