如何检测闭环多边形的有界区域？

Question

在2D空间中，给出了一个有序的点集，作为前一个过程的输出。坐标点将以形式(( x0，y0)，(x1，y1)，…，( xn，yn))表示，其中最后一个坐标对将是第一对坐标的重复(即x0=xn和y0 = yn)。这样，我知道当我再次遇到相同的坐标时，我做了一个闭环。我想通过多边形来探测封闭的区域。如果给定一个闭环，输出应该是该闭环的封闭区域。现在假设我有一组独立的点，类似于第一组。如果给出一组多个闭环多边形，则如果每个多边形在空间上相互分离，则输出应该是每个封闭区域。然而，如果一些多边形相互包围，它应该是两个多边形之间的边界区域。例如，如果我在另一个闭环多边形中有一个，输出区域应该在它们之间(或者换句话说，由较大的一个包围的区域减去由较小的一个包围的区域)。如果在单个较大的多边形中有多个闭环多边形，它应该是由较大的多边形所包围的区域减去由较小的多边形所包围的所有区域)。

对于一个区域A被区域B包围，其中B被区域C所包围的情况，有三个不同的区域。

1. 区域C减去区域B(外部以多边形1为界)
2. 区域B减去区域A(外部以多边形2为界)
3. 区域A(外部以多边形3为界)

在这三个地区中，我只想要第一区和第三区)。我之所以不取区域2)是因为对于我的2D平面上的所有有界区域，最外层的多边形总是表示相关区域的边界，而生成代表我的闭环多边形的坐标集的输入将永远不会给出多边形2的点，如果在最后的区域1)和区域2)的话。相反，它只会给我多边形1和多边形3，类似于我上面描述的情况。

​

​

总之，给了我足够的信息来知道2D平面上的一组闭环多边形的所有坐标点，它们是相互区别的。-我需要开发一个算法，它将接受整个封闭环多边形，并返回足够的信息来描述一个有界区域。在考虑这个问题的时候，我想我想要知道的是，对于一个闭环多边形的每一个线段，该线段的哪一边在多边形的内部和外部。-它应该能够解决我在多边形内部有多边形的情况。-闭环多边形永远不会共享任何点。每一组坐标点都是一个多边形所特有的。

我最初的想法是计算多边形的质心，然后将所有的线段与质心进行比较，但我认为这并不适用于所有情况。

Answer 1

从输入的描述来判断，将输入流分割成不同的多边形是一项很小的任务。

之后，为了“返回足够多的信息来描述有界区域”，您可以从多边形中构建以下数据结构：

1. 将所有多边形分为两类:主多边形和洞多边形。
2. 主多边形是。有界区域的外部边界。它将有界区域的内部与“外部世界”分开。
3. 孔多边形是描述某一主要多边形中的一个孔的多边形。
4. 每个孔多边形都与一个主多边形相关联。
5. 每个主多边形都与零或多个空穴多边形相关联。
6. 或者，你可以按逆时针方向排列主多边形中的顶点，也可以顺时针排列洞多边形中的顶点。但这对于满足“描述有界区域”的形式要求来说并不是绝对必要的。

结果的结构是两层的:你用一个主多边形的列表结束你，每个主多边形可能包含它的孔列表。

在你的例子中，你有4个主要的多边形。其中一个包含两个洞多边形。

所以，你所需要做的就是识别洞多边形，并正确地将它们与它们的主多边形相关联。

解决这一任务的工业强度方法是将扫描线算法应用于输入多边形。它可以很容易地对主多边形和孔多边形进行分类，并在它们之间建立适当的关联。

ad算法可能如下所示

1. 按面积增加的顺序排列所有多边形。
2. 对于排序顺序中的每个多边形p，
   1. 取任意顶点v of p
   2. 对所有面积大于p的多边形执行“内部”v测试(例如，使用一个简单的奇偶交叉测试：How can I determine whether a 2D Point is within a Polygon?)。
   3. 如果包含v的多边形数为奇数，则p为空穴多边形。否则，p是一个主要多边形。
   4. 如果p是一个空穴多边形，那么包含v的最小面积多边形就是它的相关主多边形。

​

就这样。

Answer 2

我想，我想要知道的输出是，对于一个闭环多边形的每一个线段，该线段的哪一边在多边形的内部和外部。

1. 计算直线段(垂直线)的法线。
2. 计算线段的中点(任何点都可以)。
3. 每隔一条直线段与一条射线相交，从中点向正常方向投射。

直观地说，每个交点都意味着进入或退出另一个多边形。由于射线最终将在所有多边形外，我们可以推断，如果射线与其他线段的偶数相交，则由法线表示的线段的边在多边形的外部。如果奇怪的话，它就在里面。

有几个棘手的情况:一是光线正好与两个连通线段的端点相交。小心，只把它算成一个交叉口。另一种情况是光线与另一条线段平行并完全重叠。这应该算作两个交叉口。

有更有效的算法(例如，涉及三角剖分)，但这个是最简单的。