polygon - 多边形重叠，具体情况

Question

我已经实现了一个函数来检查两个多边形 p1 和 p2 的重叠，以验证 p1 是否与 p2 重叠，该函数获取 p1 的每个边缘并测试它的一个点是否在 p2 内部而不是 p2 的边缘（它们可以共享一条边）。

该函数工作得很好，问题是它被调用了一千次，它使我的程序非常慢，因为它必须逐点迭代每个边缘，我只检查 4 个多边形重叠的情况，它们是：

如果一个三角形与一个三角形重叠。

如果三角形与矩形重叠。

如果三角形与平行四边形重叠。

如果一个矩形与一个平行四边形重叠。

有没有更简单快捷的方法来检查这些重叠情况是否发生？

Answer 1

我在想你真正要找的只是线段相交的地方。这可以在 O((N+k) log N) 中完成，其中 N 是线段的数量（大致是顶点的数量），k 是交点的数量。使用 Bentley-Ottmann 算法。这可能最好使用所有多边形来完成，而不是一次只考虑两个。

麻烦在于跟踪哪些线段属于哪个多边形。还有一个问题是，考虑所有线段可能比只考虑两个多边形更糟糕，在这种情况下，一旦你得到一个有效的交叉点，你就会停下来（有些交叉点可能不符合你的要求，不能算作重叠）。这种方法可能更快，尽管它可能需要您尝试不同的多边形组合。在这种情况下，最好简单地考虑所有线段。

Answer 2

您可以通过首先检查边是否与多边形的边界框相交来加快相交测试。查看 Line2D.interSects(Rectangle2D rect)。

如果您有一万个多边形，那么您可以通过将多边形存储在空间索引（区域四叉树）中来进一步加快速度。然后，这会将搜索限制为视图多边形，而不是蛮力搜索所有。但这可能只有在您经常需要搜索时才有意义，而不仅仅是在程序启动时搜索一次。