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

EN

甜线算法(几乎总是)为我们提供了最健壮和最有效的解决方案。

在它最简单的形式，甜线找到所有的线段交叉口。将其扩展到检查多边形包含是很简单的。您只需跟踪哪些线或点属于每个多边形。在算法的任何一步，扫描线与每个多边形内部的交集是一个有限的垂直段集。你有这样的案例：

1. 如果在任何步骤上都有适当的(即不在端点处)边缘交点，游戏结束。
2. 否则，如果在每一步红和蓝段是不相交的，那么多边形完全是在彼此之外。
3. 否则，如果在每一步中，红段和蓝段是相同的(即红色集和蓝色集是相同的)，那么两个多边形是相同的。
4. 否则，如果在每一步中，每个红色段完全在某个蓝色段内，那么红色多边形就在蓝色段中。
5. 否则，如果在每一步中，每个蓝色段完全在某个红色段内，那么蓝色多边形就在红色多边形中。
6. 否则多边形边界相交。

这可以处理所有边缘案件。如果您想将您的案例A、E和F分类为“内部”，则只测试段内部的交点(即段(0,1)和(1,2)不相交，(0,1)在(0，2)的内部)。否则，只需将上述病例视为适当的交叉口。

如果在某一步，有两个边是共线和平行的扫描线，他们相交，这可能是有点难以确定。然而，所有的边缘情况都可以通过计算甜味线-多边形交点来解决，而不是在顶点(就像对甜味线算法来说是正常的)，而是在顶点之间(例如在当前顶点和下一个顶点之间的中点处)。这种方法只考虑多边形内部(而不是边界)。

实际上，该算法将我们的多边形分解成一串小梯形，夹在通过每个顶点绘制的平行(比如垂直)直线之间。很容易检查这些梯形是相交的，还是不相交的，或者是完全相互包容的。可以找到一个例子，这里。

编辑:澄清了一些措辞。编辑2:找到一个边缘案例;)

如果我们试图检查多边形B是否在多边形A中：

就像在你链接的答案中提到的，开始对每对边做一个直线相交试验，每个多边形一个。如果任何边相交(不包括位于边和公共顶点上的顶点)，则B不在A内。

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

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

对于每个公共顶点V：

• 我们可以说V有边EA1和EA2 (从A)和EB1和EB2 (来自B)。
• 得到所有四个边的梯度。
• 使用它来确定哪些边是相邻的。

​

• 如果EB1和EB2不相邻，则B不在A内。
• 如果EB2位于A上(也就是说，EB2在EA2上，即它们有一个相等的梯度)，我们还不知道B是否在A中。

在这种情况下，我们需要跟踪EB1在哪一边，然后转移到相邻的顶点VB ( EB2的另一个顶点)，并检查EB2之后的边缘EB3是否与EB1位于同一条边。如果它们在不同的一边，B就不在A里面。

如果EB3也在A上，我们需要检查EB4，以此类推，直到我们找到一个不是的。

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

(注意:例如，如果EB2位于EA1而不是EA2上，您可以简单地重命名它们以满足上述条件)

所有这一切都是假设我们不允许与自己相交的多边形-允许这可能会破坏这一点。

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

我们可以遍历O(|EA| + |EB|)中的边缘并播放"catch:“，当一个多边形的当前边缘在至少一个维度中超出另一个多边形的边缘时，沿着另一个多边形的下一个边缘/s移动，然后再次切换。断言包含，我们可以通过监视交叉口和边缘的哪一侧在其多边形内来判断。