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

Question

我得到了二维空间中的一组有序点作为先前过程的输出。坐标点将以 ((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 为界)

在三个区域中，我只想要区域 1) 和区域 3)。我不采用区域 2) 的原因是因为对于我的 2D 平面上的所有有界区域，最外层的多边形始终代表相关区域的边界，并且生成代表我的闭环多边形的坐标集的输入永远不会有如果在末端区域 1) 和区域 2) 中要合并，请给我多边形 2 的点。相反，它只会给我多边形 1 和多边形 3，类似于我上面描述的情况。

总而言之， - 我获得了足够的信息来了解二维平面上一组闭环多边形的所有坐标点，并且它们彼此可以区分。 - 我需要开发一种算法，该算法将接受整组闭环多边形并返回足够的信息来描述有界区域。在考虑这个问题时，我认为我想要的输出是知道对于闭环多边形的每条线段，该线段的哪一侧在多边形的内部和外部。 - 它应该能够解决我在多边形内部有多边形的情况。 - 闭环多边形永远不会共享任何点。每组坐标点对于多边形都是唯一的。

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

Answer 1

从您的输入描述来看，将您的输入流拆分成单独的多边形是一项微不足道的任务。

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

1. 将所有多边形分为两类:主多边形和孔多边形。
2. 主要多边形 是......好吧，有界区域的外部 边界。它将界域内部与“外部世界”隔开。
3. Hole polygon 是描述某个主要多边形中的孔的多边形。
4. 每个孔洞多边形恰好与一个主多边形相关联
5. 每个主多边形与零个或多个孔多边形相关联
6. 可选地，您可以逆时针排列主多边形中的顶点，顺时针排列孔多边形中的顶点。但这对于满足“描述有界区域”的形式要求并不是严格必要的

最终的结构是两层的:你以一个主要多边形的列表结束，每个主要多边形可能包含一个它的洞的列表。

在您的示例中，您有 4 个主要多边形。其中一个包含两个孔多边形。

因此，您需要做的就是识别孔多边形并将它们与它们的主要多边形正确关联。

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

一个临时算法可能如下所示

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

就是这样。