logo标签列表

将一个二维网格图数据结构转换为树形结构

algorithmdata-structuresgraphtree
9
我有一个网格： Grid 该网格由单元格组成，递归地分割为更小的单元格。 网格中的每个子单元格都受其父单元格的限制。
网格中的单元格存储在类似于图形的结构中。 每个单元格都有四个连接，分别位于每个角落。 每个角落连接到另一个单元格，使得平行于连接并且最接近它的单元格边缘相切。 该网格可以用以下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的答案后，我想强调网格结构的重要性。以下是两个外观相同但具有不同结构且因此具有非常不同的树表示的框的示例：
2个回答
3
我认为第四个选项是可行的。我认为实现并不是太复杂：我会维护一个森林的根节点集合，初始化为网格中的所有框（作为大小为1的树）。然后只需不断迭代该集合，检查您正在检查的框是否连接到具有两个边缘的任何框。如果是，则用一个更大的框替换两个框，并使该更大的框成为它们在森林中的父节点。
有一个微妙之处，我不确定在您的应用程序中它有多重要。对于上面的主要示例，您将不会在根处获得三进制节点：
     Root
/-----+-----\
|     |     |
A     B     C

你会得到类似下面的内容。
       Root
    /---^---\
   D        C
/--^--\
A     B

然而，我认为你可以在后处理步骤中检测到这种情况并进行纠正：遍历树，并且对于每个节点，检查它是否表示水平或垂直连接，如果一个节点X与其父节点Y具有相同的方向，则删除X并使其子节点成为Y的附加子节点。

那种微妙的细节很重要，但你说得对，它可以解决。我更喜欢其他方法，因为如果网格发生变化，更新结构非常容易（我知道我没有将其作为要求提到）。我会尝试一下看看是否可行。 - LandonSchropp
1
你可以从网格中制作一个图表，其中每个“盒子”都与其相邻的盒子之间有一条边。
然后为边确定一个权重（我会使用min(v1,v2)），以便决定某种排序方式。
然后只需使用最小生成树算法创建树即可。
这是一个有趣的方法。不幸的是，我认为我无法将整个网格空间表示为图中的一个顶点。我已经更新了我的问题，并举例说明为什么图结构如此重要。 - LandonSchropp
你可以将交叉点本身作为节点添加，然后仅将实际的方框连接到这些节点，并根据它们之间最初具有的边数给它们赋予权重。这将为您提供容器单元。 - Yochai Timmer
我不确定我是否完全理解您所说的交叉点被添加为节点。您能否再详细说明一下？ - LandonSchropp
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接