我有一组简单的（没有孔，没有自相交）多边形，我需要检查它们是否相互交叉（一个可以完全包含在另一个中；没关系）。我可以通过简单地检查一个多边形与其他多边形的每个顶点内部来检查这一点。
我还需要确定包含树，它是一组关系，表明哪个多边形包含任何给定的多边形。由于没有多边形可以与任何其他多边形相交，因此任何包含的多边形都有一个唯一的容器；“下一个更大”的。换句话说，如果 A 包含 B 包含 C，则 A 是 B 的父级，B 是 C 的父级，我们不认为 A 是 C 的父级。
问题：如何有效地确定包含关系并检查不相交标准？我将此作为一个问题提出，因为也许组合算法比单独解决每个问题更有效。该算法应该将多边形列表作为输入，由它们的顶点列表给出。它应该生成一个布尔值 B，指示是否没有多边形与任何其他多边形相交，并且如果 B = true，则生成对 (P, C) 对的列表，其中多边形 P 是子 C 的父级。
这不是家庭作业。这是我正在从事的一个爱好项目。
首先，您的测试遏制算法没有正确测试相交。想象两个这样的矩形：
+--+
+--+--+--+
| | | |
+--+--+--+
+--+
顶点将位于 (1, 2) (1,3) (4,2) (4,3) 和 (2,1) (3,1) (2,4) (3,4) - 没有顶点位于在任何多边形内，但多边形确实相交。
为了测试这种相交，有必要确定任何多边形的边是否相交。出于您的目的，如果边相交但一个多边形不包含在另一个多边形中，那么您知道它们以不允许的方式重叠。
至于确定包含树，一种方法是按面积从最小到最大对多边形进行排序。如果多边形不重叠而不包含，那么树中任何多边形的父级都将是列表中紧随其后的第一个包含多边形。
编辑：哦，另外，我建议编写一个快速边界框或边界圆重叠例程，并使用它来避免必须进行所有线交点和顶点包含测试。如果这还不够快，您可能想要构建四叉树或 BSP 树；这会使事情变得相当复杂，但也会完全消除很多交叉检查。
可以O(n*log(n))通过应用Shamos-Hoey 算法来确定是否没有多边形相交。根据 Shamos-Hoey 算法返回的内容，如果来自 P j的任何顶点在P i内部，则多边形 P i包含多边形 P j，这对两个多边形完成。O(n)
要测试交叉点，您可以使用我的免费软件裁剪器库：http: //sourceforge.net/projects/polyclipping/。
要测试包容性，首先排除上述交叉点。然后再次使用 Clipper 添加所有多边形 - Clipper.AddPolygon()。然后对多边形执行联合（布尔或）操作 - Clipper.Execute(ctUnion, solution)。如果 Clipper.ForceAlternateOrientation 属性为 true，Clipper 将在解中以顺时针方向返回外部多边形，并以逆时针方向返回包含的多边形（孔）。然后，测试多边形方向并从逆时针多边形中的一个顶点对其他顺时针多边形应用 PointInPolygon 应该是一件简单的事情。
有关代码，请参阅gpc。