5

我正在解析一些数据，作为描述几个封闭的任意形状/多边形的线段数组给出。这些形状可以是凹形的。这是我正在查看的简化示例：

在此处输入图像描述

但是，我提供的数据具有任意顺序的段。根据示例，我的数据将类似于{V,E,D,X,U,A,Z,C,B,W,Y}. 因此，绘制线段会显示正确的形状，但对形状进行任何操作都不会变得更容易。

我正在尝试对上面的数组进行排序，以便每个闭合形状的段按照连接顺序排列，并且每个形状的段都组合在一起。

所以

{V,E,D,X,U,A,Z,C,B,W,Y}

会成为

[ {A,B,C,D,E} , {X,Y,Z} , {U,V,W} ]

每组线段的顺序对我来说并不重要，只是各个线段是按顺序排列的。我也不关心每个组的特定起始部分。

以便

[ {Y,Z,X} , {C,D,E,A,B} , {W,U,V} ]

是同样有效的结果。

我没有遍历几何的经验，我的初步尝试和粗略的在线搜索并没有产生任何快速的解决方案。我研究了凹形外壳，但鉴于数据已经知道点之间的连接，这似乎有点过头了。

4

2 回答 2

2

经过一天的头疼，在这里尝试建议并编写一些帮助类之后，我想出了一些非常传统的东西。在粗略的伪代码中，我的解决方案是：

create group list;

while (line segments exist in pool)
{
    create new group;
    remove one segment from pool and place into group;

    while (endpoint of last line in group != startpoint of first line in group)
    {
        get the endpoint of the last line in group;
        search pool for line segment whose startpoint = that endpoint;
        remove that segment from the pool and place into group;
    }

    store group in group list;
}

代码依赖于假设我的数据只包含封闭的形状（即每个形状的数据整齐地终止于相同的精确坐标），并且所有数据都创建形状，而不仅仅是孤线。我不确定它的效率如何，但考虑到它被用作预处理步骤一次，这就足够了。

于 2016-12-27T13:38:13.760 回答
1

如果我可以假设您知道每个线段的起点和终点（我们称它们为节点），并且多边形永远不会与另一个多边形有公共节点，那么您可以执行以下操作：

  • 制作节点列表：每个节点由它连接的两个段定义。例如，节点 1 是连接段 A 和 E 的节点，节点 2 是连接 A 和 B 的节点，以此类推。

  • 将节点分组为多边形，即将所有节点放在一起，共享一个公共段。

  • 你完成了

于 2016-12-26T12:40:17.687 回答