如何查看两个多边形是否重叠？

Question

我需要检查两个 java.awt.Polygon 是否重叠，但我不知道如何。

Answer 1

从几何角度来看，重叠多边形满足了一些条件。

1) 如果 A 中的线段与 B 中的线段相交，则多边形重叠。

2) 如果 B 中的所有顶点都在 A 中，反之亦然，则多边形重叠。

3) 如果A中的所有顶点也是B中的顶点，则多边形重叠。

(1) 的测试相当简单。你只需做一点代数和蛮力。如果线是平行的，它们就不会交叉。如果这些线不平行，则它们相交。如果交点在任一线段内，则它们相交。最大迭代次数是 A 的长度 * B 的长度。

(2) 的测试稍微复杂一些。判断一个点是否在多边形内部的一种方法是：选择一个您知道在多边形外部的点，通常 x,y 的负值适用于此。然后，从参考点到测试点画一条线。如果它穿过奇数个线段，它就在里面。如果它穿过偶数或零线段，则它在外面。

Answer 2

Area area = new Area(poly1);
area.intersect(new Area(poly2));
return area.isEmpty();