algorithm - 是否有一种有效的算法来找到所有相交的多边形？

Question

我有两组多边形。笛卡尔空间中的红色多边形和蓝色多边形。我需要找到与任何蓝色多边形相交的所有红色多边形。我目前正在使用一种简单的双循环方法来解决这个问题。这是伪代码:

var candidates = HashMap<Int, Polygon>();
for (var red : redPolygons) {
    for (var blue : bluePolygons) {
        if (polygonsIntersect(red, blue)) {
           candidates[red.id] = red.polygon;
           break;
        }
    }
}

我正在寻找更高效的算法。理想情况下比 O(N^2) 更好。

更多细节。蓝色多边形的数量通常很少(少于 100 个)，而且是动态的。红色多边形的数量较多，且不经常变化，因此对红色多边形进行预处理是一个可行的选择。

Answer 1

Ideally something better than O(N^2)

(请注意，可能有 O(N²) 个交叉点:下面的许多高级算法使用了很多时间的最坏情况。)
如果所有边都平行于其中一个轴(等向)，计算几何中的许多问题会更简单；如果“所有”多边形都是凸的，许多多边形问题会更简单。

〇如果您正在寻找具有相交边的多边形，只需要寻找
Balaban, I. J.(1995 年):“寻找路段交叉点的最佳算法”。
对于两组边/多边形之间相交的特殊情况，有
Chan, T.M.(1994 年):“用于报告红/蓝线段交叉点的简单梯形扫描算法”，
曼特勒，A.； Snoeyink, J.(2001 年):“以最佳时间和精度相交的红色和蓝色线段”，
Basch, J.; Guibas, L. J.； Ramkumar, G. D.(2003 年)“报告两组连接线段之间的红蓝相交”，……

如果您也需要包含(多边形重叠)，从每个多边形中选取一个点并检查“另一组”中任何多边形中的包含就足够了；应该可以在单个 line sweep 中进行交叉和包含检查.

preprocessing the red polygons is a viable option.

传统的预处理包括按坐标对顶点进行排序。