查找相邻多边形的轮廓

我正在寻找一种方法来查找两个相邻多边形的轮廓。查找相邻多边形的轮廓

多边形由按多边形中出现次序排列的点列表定义。在我的用例中，没有重叠的多边形，多边形之间没有间隙，也没有带有“孔”的多边形。

我想计算没有任何“洞”的两个多边形的轮廓。这些pictures显示预期结果。

enter image description here

我知道有很多关于裁剪多边形库，但对于大多数人，因为他们对于任何一种多边形的工作（有孔，重叠的多边形等）的表现不是很好。在我的用例中，该算法必须实时处理大量多边形（> 20.000）。我怎样才能最有效地计算轮廓？

2014-09-29 heinzwilli

尝试...... http://stackoverflow.com/questions/83593/is-there -an-efficient-algorithm-to-generate-a-2d-concave-hull – 2014-09-29 16:05:51

将有助于1）避免重复顶点; 2）建立“这个顶点属于这个/这些轮廓”的逆关系。从那里，你可以找到共享一个顶点并且可以被合并的轮廓线，并且处理将减少到在逻辑上组合两个顶点列表。 – 2014-09-29 17:27:35

对Yves Daoust：遵循您的建议，我可以确定哪些顶点属于这两个多边形。但如何继续？案例一在图片中很容易。我只需要按照正确的顺序在属于两个多边形的多边形1的两个顶点之间插入多边形2的顶点。情况2从图片是我的事情更困难。如果我删除多边形之间的轮廓，则会留下“孔”。我怎样才能确定哪些轮廓属于“洞”？ – heinzwilli 2014-09-30 07:13:22

鉴于

没有重叠的多边形，还有多边形之间没有空隙，也没有与多边形的“洞”

以下算法应该做的伎俩。

丢弃重复的线段。
计算剩余为doubly connected edge list的自然组合嵌入。每个段产生两个节点（半边，彼此相反，段的一个端点是头部（分别是尾部），另一个端点是尾部（分别是头部）），并且每个半边链接到逆时针顺序的相同头部的下一半边缘。
提取面部。在组合嵌入中的一个面是最小的非空半边集合，使得对于每个半边e，来自e的下一个半边的反向在该集合中。这组面是半边的一个分区。请参阅下面的ASCII艺术图。
```
U----V----W 
| | | 
| | | 
Z----Y----X 
```
无限的脸是{U->Z, Z->Y, Y->X, X->W, W->V, V->U}。 W->V的下一个半边是U->V。从W->V开始的下一个半边的倒数是V->U。其他面孔是{U->V, V->Y, Y->Z, Z->U}和{V->W, W->X, X->Y, Y->V}。

通过将带符号的逆时针角度相加并测试符号来仅保留无限面。一个有限的脸像{U->V, V->Y, Y->Z, Z->U}具有负和

/_UVY - 180 + /_VYZ - 180 + /_YZU - 180 + /_ZUV - 180 
    = 4 * (90 - 180) = -360.

无限面具有正和

/_UZY - 180 + /_ZYX - 180 + /_YXW - 180 + /_XWV - 180 + /_WVU - 180 + /_VUZ - 180 
    = 4 * (270 - 180) + 2 * (180 - 180) = 360.

来源

2014-10-04 04:34:36

查找相邻多边形的轮廓

回答

相关问题