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

Question

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

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

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

如果是，请给我算法的名称，如果不是 - 一些证明它不可能的资源。

Answer 1

摘自 paper on the Greiner-Hormann (PDF)多边形裁剪算法:

... if we have a polygon with n edges and another with m edges, the number of intersections can be nm in the worst case. So the average number of intersections grows on the order of O(nm).

There is a well-known result in computational geometry based on the plane sweep algorithm, which says that if there are N line segments generating k intersections, then these intersections can be reported in time O((N+k) log(N)) [7]. Note that this relation yields an even worse complexity in the worst case.

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

对“知名”结果的引用是:

[7] F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Texts and Monographs in Computer Science. Springer, New York, 1985.

这是一个 paper on the line sweep algorithm .