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

Question

(就我的目的而言,"多边形"不包括自相交多边形或带孔的多边形 - 只是简单(凹或凸)多边形.)

我找到了针对这个问题的各种建议,主要基于以下几点:

如果Polygon1的边缘与Polygon2的边缘之间没有交叉点,并且Polygon2的至少一个顶点是"内部"Polygon1,则Polygon1包含Polygon2.

(例如,请参阅此处接受的答案)

然而,魔鬼在细节:

• "内部"Polygon1是否包含"Polygon1"的边缘？显然它必须,否则在图F中(参见下面链接的图像)Polygon2(红色)在Polygon1(蓝色)内部没有顶点,因此在应该通过时不能通过上述测试.

• 两条边的"交点"是否包含一条边(即顶点)末端的点？如果"是",则下面的图A和E具有交叉点,因此当它们通过时测试失败.但如果"不",则图B,C和D没有交叉点,因此当它们失败时通过测试.

(NB图A,B和C在Polygon1的边缘上具有Polygon2的顶点,图D和E反之亦然.)

我无法确定一个条件来测试这些不同情况之间的区别.我会感激任何指针？

Answer 1

扫描线算法（几乎总是如此）为我们提供了最稳健和最有效的解决方案。

以最简单的形式，扫描线查找所有线段交点。扩展它来检查多边形包含是很简单的。您只需跟踪属于每个多边形的线或点即可。在算法的任何步骤中，扫描线与每个多边形内部的交点都是一组有限的垂直线段。你有这些情况：

1. 如果在任何一步都有正确的（即不在端点处）边缘相交，则游戏结束。
2. 否则，如果在每一步红色和蓝色线段都不相交，则多边形完全彼此外部。
3. 否则，如果在每一步红色线段都与蓝色线段相同（即红色组和蓝色组相同），则这两个多边形是相同的。
4. 否则，如果在每一步，每个红色线段完全位于某个蓝色线段内，则红色多边形位于蓝色多边形内部。
5. 否则，如果在每一步，每个蓝色线段完全位于某个红色线段内，则蓝色多边形位于红色多边形内部。
6. 否则多边形边界相交。

这可以处理所有边缘情况。如果您想将情况 A、E 和 F 分类为“内部”，则仅测试线段内部的交集（即线段 (0,1) 和 (1,2) 不相交，并且 (0,1) 在(0,2))。否则，只需将上述情况视为适当的交集即可。

如果在某个步骤中有两条边与扫描线共线且平行并且它们相交，则可能有点难以决定。然而，所有边缘情况都可以通过计算扫掠线-多边形交集来解决，交集不是在顶点（与扫掠线算法一样）而是在顶点之间（例如在当前顶点和下一个顶点之间的中点）。这样，仅考虑多边形内部（而不是边界）。

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

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