查找相邻多边形的轮廓线

Question

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

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

我想计算出这两个多边形的轮廓线，而且不带任何“孔”。

这些 pictures 显示了预期结果。

我知道有很多用于剪切多边形的库，但是它们大多数性能不太好，因为它们适用于任何类型的多边形（带孔、重叠的多边形等）。在我的应用场景中，算法必须实时处理大量的多边形（>20,000）。如何最有效地计算轮廓？

- heinzwilli

---

尝试这个...https://dev59.com/5nVD5IYBdhLWcg3wHnsX - Angus Johnson

将会有用处：1）避免重复顶点；2）建立反向关系“这个顶点属于这个/这些轮廓”。从那里，您可以找到共享顶点并且可以合并的轮廓，并且处理将减少到逻辑上组合两个顶点列表。 - user1196549

给Yves Daoust：根据您的建议，我可以确定哪些顶点属于两个多边形。但是接下来该怎么做呢？图片中的第一种情况很容易解决。我只需要按照正确的顺序将多边形2的顶点插入到属于两个多边形的多边形1的两个顶点之间即可。图片中的第二种情况更加困难。如果我删除多边形之间的轮廓线，就会留下一个“洞”。我该如何确定哪些轮廓线属于这个“洞”呢？ - heinzwilli

你有看到任何一种可以选择保证是轮廓的一部分的顶点的方法吗？就像之前提到的图片的情况2会导致两种可能的轮廓。孔的轮廓和我正在寻找的轮廓。如果我能够识别轮廓上的一个点，我就知道应该选择哪个轮廓了。 - heinzwilli

问题文本说“多边形之间没有间隙”。在第二个例子中，由红色顶点3、4、5、6和蓝色顶点4、5、6、7形成的两个多边形之间的那个岛屿会被认为是一个间隙吗？ - Reto Koradi

第二个示例应该展示一个（或多个）多边形被即将合并的多边形所包围的可能性。 - heinzwilli

Answer 1

假设没有重叠的多边形，多边形之间没有间隙，也没有带有“孔”的多边形，那么以下算法应该可以解决问题。

1. 丢弃重复的线段。

2. 计算剩下部分的自然组合嵌入，作为双连通边列表。每个线段产生两个节点（半边，相互反转，其中线段的一个端点是头（或尾），另一个端点是尾（或头）），每个半边按逆时针顺序链接到具有相同头的下一个半边。

3. 提取面。在组合嵌入中，面是一组最小的非空半边集合，使得对于每个半边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}。

4. 通过求和有符号逆时针角度并测试符号，仅保留无限面。像{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.
   

- David Eisenstat