多边形的交点
给出了两个多边形。 如何确定一个多边形是在另一个多边形的内部，外部还是相交？ 多边形可以是凹面或凸面。
您想对凸多边形使用分离轴定理。 基本上，对于每个多边形的每个面，您将每个多边形投影到该面的法线上，并查看这些投影是否相交。
您可以执行各种技巧来减少必须执行的这些计算的数量 – 例如，您可以在对象周围绘制一个矩形，并假设如果两个对象的矩形不相交，则它们本身不相交。 （这更容易，因为检查这些盒子的交叉点的计算成本较低，而且通常非常直观。）
凹面多边形更难。 我认为你可以将多边形分解为一组凸多边形并试图检查每个交叉的组合，但我不认为自己在这方面有足够的技巧来尝试它。
通常，这样的问题可以通过扫描线算法轻松解决。 然而，使用扫描线方法的主要目的和好处是，当输入由两组相对较大的多边形组成时，它可以有效地解决问题。 一旦实施了扫描线解决方案，如果需要，它还可以有效地应用于一对多边形。 也许你应该考虑朝着这个方向前进，以防你将来需要解决一个大问题。
但是，如果您确定需要两个且只有两个多边形的解决方案，则可以通过顺序点对多边形和段对多边形测试来解决。
有一种简单的方法可以检查点是否位于多边形中。 根据这篇维基百科文章，它被称为光线投射算法。
该算法的基本思想是，您从测试点向任意方向投射光线，并计算与其相交的多边形边数。 如果此数字是偶数，那么该点位于多边形外部，否则如果它是奇数，则该点位于多边形内部。
这个算法有很多问题我不会深入研究（它们在我之前链接的维基百科文章中讨论过），但它们是我称之为算法的原因。 但是为了给你一个想法，你必须处理涉及光线相交顶点的角落情况，光线平行并与边缘交叉，数值稳定性问题与靠近边缘的点。
然后，您可以按照托马斯在其答案中描述的方式使用此方法来测试两个多边形是否相交。 这应该给你一个O(NM)算法，其中两个多边形分别有N和M个顶点。
这是一个简单的算法，用于了解给定点是在给定多边形的内部还是外部：
bool isInside(point a, polygon B) { double angle = 0; for(int i = 0; i < B.nbVertices(); i++) { angle += angle(B[i],a,B[i+1]); } return (abs(angle) > pi); }
- 如果A的线段与B的线段相交，则两个多边形相互交叉。
- 否则，如果多边形A的所有点都在多边形B内，那么A在B内。
- 否则，如果多边形B的所有点都在多边形A内，则B在A内。
- 否则，如果多边形A的所有点都在多边形B之外，那么A在B之外。
- 否则这两个多边形相互交叉。