对描述多边形的线段数组进行排序和分组

我解析了一些数据，这些数据是作为描述几个封闭的任意形状/多边形的线段数组给出的。这些形状可以是凹形的。这里是什么，我在看一个简单的例子：对描述多边形的线段数组进行排序和分组

不过，我提供的数据具有以任意顺序段。根据这个例子，我的数据就像{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} ]

同样是一个有效的结果。

我对遍历几何没有经验，而且我的基本尝试和粗略的在线搜索都没有产生任何快速解决方案。我看着凹壳，但这似乎是过度的，因为数据已经知道点之间的联系。

来源

2016-12-26 interloper

看看我的答案（编辑部分）在这里：http://stackoverflow.com/questions/41245408/ – MBo

头扯皮的一天后，在这里实验的建议，并编写一些辅助类，我想出了一些非常普通的。在粗糙的伪代码，我的解决办法是：

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-27 13:38:13 interloper

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

创建节点列表：每个节点由它连接的两个段定义。例如节点1是连接段A和节点E的节点，节点2是连接A和B的节点等。
将节点分组为多边形，即将所有节点放在一起共享公共段。
大功告成

来源

2016-12-26 12:40:17 user7291698

对描述多边形的线段数组进行排序和分组

回答

相关问题