是否存在有效的算法来确定两个可能非凸多边形的边之间的交点？

Question

这是我试图解决的任务：
给定一个具有 N 个顶点的多边形 A 和一个具有 M 个顶点的多边形 B，找到 A 中的线段与 B 中的线段之间的所有交集。
A 和 B 都可以是非凸的。

到目前为止，我已经实现了明显的解决方案（检查 A 中的每条边与 B 中的每条边，O(M*N)）。
现在，对于某些多边形，实际上可能有（几乎）M*N 个交叉点，因此任何此类算法的最坏情况都是 O(M*N)。

我的问题是：
是否存在一种算法来确定两个非凸多边形之间的交点，平均情况下复杂度低于 O(N*M)

如果是，请告诉我该算法的名称算法，如果没有 - 一些证明它是不可能的资源。

Answer 1

摘自有关 Greiner-Hormann 的论文 (PDF) 多边形裁剪算法：

...如果我们有一个
具有 n 条边的多边形，另一个具有
m条边，交点的数量
在最坏的情况下可以是nm。所以
平均交叉路口数量增加
大约为 O(nm)。

有一个
众所周知的计算结果
基于平面扫描的几何
算法，它表示如果有
是生成 k 的 N 条线段
交叉点，那么这些
路口可以及时报告
O((N+k) log(N)) [7]。请注意，这
关系会产生更糟糕的结果
最坏情况下的复杂性。

我相信第二段中的 N 是第一段中的 m + n。平均时间取决于 k 的平均值，即交叉点的数量。如果只有少数交叉点，则时间为 O(N log N)。

对“众所周知”结果的引用是：

[7] FP Preparata 和 MI Shamos。
计算几何：
介绍。文本和专着
计算机科学。纽约州施普林格,
1985 年。

这是一篇关于线扫描算法的论文。