确定一个多边形是否包含另一个多边形。

Question

对于我的目的，“多边形”不包括自相交的多边形或带孔的多边形 - 只有简单（凸多边形或凹多边形）的多边形。

我已经找到了各种解决此问题的建议，主要基于以下内容：

如果Polygon1的边缘与Polygon2的边缘之间没有交点，并且Polygon2的至少一个顶点“在内部”Polygon1中，则Polygon1包含Polygon2。

（例如，请参见已接受的答案here）

然而，细节是魔鬼：

• “内部”多边形1是否包括“在边缘上”的多边形1？显然必须这样，否则在图F（参见下面链接的图像）中，多边形2（红色）将没有一个顶点“在内部”多边形1（蓝色）中，因此无法通过上述测试，但实际上它应该通过。

• 两条边的“交集”是否包括一条边端点上的点（即顶点）？如果是，“A”和“E”图中有交点，因此在应该通过测试时未能通过测试。但是，如果是“否”，则B、C和D图没有交点，因此当它们应该失败时通过了测试。

（注意：A、B和C图的Polygon2顶点位于Polygon1的边缘，而D和E图相反。）

我无法找出可以正确区分这些情况的测试条件。感谢任何指导意见！

- Andy31

---

你可以将凹多边形分解成一组三角形（或者可能是任何其他凸多边形，但三角形最容易处理）。然后，测试三角形的相交和包含关系就变得非常简单。 - 3Dave

@3Dave：非常糟糕的建议。1）三角测量多边形并不容易。2）这将在所有情况下将复杂度增加到O（N.M）。3）它会导致一个不可分割的混乱：在找到三角形与形成另一个多边形的三角形的所有交点之后，您需要检查三角形是否完全被覆盖。 - user1196549

@YvesDaoust 1) 三角剖分并不难，是一个经过深入研究和记录的任务。2) 如果OP目前没有可行的解决方案，那么它从什么地方增加呢？3) “完全覆盖”是什么意思我不清楚。 - 3Dave

@3Dave：1）三角测量很困难。2）从可能的O（N Log N）解决方案中增加。3）你好像没有认真考虑这个问题。 - user1196549

@YvesDaoust 叹气。我曾经解决过这个问题，并花了相当长的时间。如果你认为三角剖分很困难，也许你还没有仔细考虑过那个问题。 - 3Dave

@3Dave：噢，我明白了，你可能实现了Chazelle的解决方案。但要继续考虑第2点和第3点。 - user1196549

Answer 1

如果我们想要检查多边形B是否在多边形A内：

像你链接的答案中提到的那样，首先对每一对边进行线段相交测试。如果任何边相交（不包括位于边缘上和公共顶点），则B不在A内。

如果一个多边形的一个顶点V位于另一个多边形的一条边上，则将该边视为2条边，并将顶点V作为该多边形的新顶点。

现在我们只需要考虑公共顶点。

对于每个公共顶点V：

• 我们可以说V有边EA1和EA2（从A开始）以及EB1和EB2（从B开始）。
• 获取所有4条边的梯度。

• 使用这个来确定哪些边是相邻的。

  

• 如果EB1和EB2不相邻，则B不在A中。

• 如果EB2位于A上（即EB2位于EA2上，即它们具有相等的梯度），我们还不知道B是否在A中。

  

  在这种情况下，我们需要跟踪EB1在哪一侧并移动到相邻的顶点VB（EB2的另一个顶点），并检查EB3是否与EB1在同一侧。如果它们在不同的侧面，则B不在A内。

  如果EB3也在A上，我们需要检查EB4等等，直到找到一个不在A上的边。

  如果EB1在EA1上，而EB2在EA2上，我们需要向两个方向移动以确定我们需要在哪一侧。如果B的所有边都在A上，则A等于B。

  （注意：例如，如果EB2位于EA1而不是EA2上，则可以将它们重命名以满足上述条件）

假设我们不允许多边形与自身相交 - 允许这种情况可能会破坏它。

这里可能有一些非平凡的细节，但这应该是一个不错的起点。

- Bernhard Barker

Answer 2

甜线算法（几乎总是）给我们提供了最强大和高效的解决方案。

在其最简单的形式下，甜线算法可以找到所有线段交点。将其扩展为检查多边形包含性非常简单。只需跟踪每个多边形属于哪条线或点。在算法的任何步骤中，扫描线与每个多边形内部的交点是一组有限的垂直线段。你会遇到以下情况：

1. 如果在任何步骤中存在适当的（即不在端点处的）边缘相交，则游戏结束。
2. 否则，如果在每个步骤中红色和蓝色线段都不相交，则多边形完全在彼此之外。
3. 否则，如果在每个步骤中红色线段与蓝色线段相同（即红色集合和蓝色集合相同），则两个多边形相同。
4. 否则，如果在每个步骤中每个红色线段完全位于某些蓝色线段内，则红色多边形在蓝色多边形内。
5. 否则，如果在每个步骤中每个蓝色线段完全位于某些红色线段内，则蓝色多边形在红色多边形内。
6. 否则，多边形边界相交。

这样处理可以解决所有边缘情况。如果你想将你的情况A、E和F归类为“内部”，则只需测试线段内部的相交（即线段（0,1）和（1,2）不相交，而（0,1）在（0,2）内部）。否则，将上述情况视为适当的相交。

如果在某个步骤中有两条与扫描线平行且共线的边相交，可能有点难以决定。但是，通过在顶点之间计算扫描线多边形相交（例如在当前顶点和下一个顶点之间的中点处），可以解决所有边缘情况。这样一来，只有多边形内部（而非边界）被考虑。

实际上，该算法将我们的多边形分成了一堆小梯形，夹在每个顶点通过的平行线（例如垂直线）之间。很容易检查这些梯形是否相交、不相交或完全包含彼此。可以在这里找到说明。

编辑：澄清了一些措辞。 编辑2：发现了一个边缘情况;)

- n. m.

---

似乎具有处理多个对象的附加优点。 - גלעד ברקן

@גלעדברקן 是的，这是一个非常强大的算法。 - n. m.

Answer 3

非常感谢回复，特别是@Dukeling和@n.m。

我已经实现了（用Python）@n.m提出的扫描线解决方案，并在此发布，以防其他人发现它有用。（我发现这个比Dukeling的解决方案更容易编码。）在我的用例中，我知道哪个将是包含多边形（如果有的话），所以我不需要测试两种方式。

我已经使用超过20个测试用例进行了测试，包括上图中的所有测试用例及其在y = x中的反射。但是，如果有人发现任何实现无法工作的边缘情况，或者对代码效率的任何改进，欢迎评论。

编辑：
我已删除代码，因为我发现它不能处理一些情况。最终，我选择了一个更全面的解决方案，给定两个多边形A和B，确定A是否包含B，A在B内部，A和B重叠，或A和B不相交。

为了加快速度，它首先查看边界框，消除了一些可能性，然后如果边界框相等，则查看区域，然后才转到扫描线算法。

代码相当长，所以我在这里不包含它，但如果有人感兴趣，可以在https://github.com/andy31lewis/brySVG的PolygonObject的positionRelativeTo方法中查看。这已经通过了几百个测试用例的测试，似乎非常可靠。

- Andy31

Answer 4

我们可以在 O(|EA| + |EB|) 的时间内遍历边缘并进行“接住”的操作：当一个多边形的当前边沿着至少一个维度超出另一个多边形的边缘时，移动到另一个多边形的下一条/多条边缘，然后再切换回来。通过监测相交和边缘内部是哪一侧来确认包含性。

- גלעד ברקן