algorithm - 计算直线是否与凸多边形相交的渐近最优算法

Question

检测一条线是否与凸多边形相交的 O(n) 算法包括检查多边形的任何边是否与该线相交，并查看交叉点的数量是奇数还是偶数。

是否有渐进更快的算法，例如一个 O(log n) 的？

Answer 1

lhf 的回答接近正确。这是一个应该可以解决他的问题的版本。

让多边形有顶点 v0, v1, ..., vn 逆时针顺序。令 x0 和 x1 在直线上。

注意两件事:首先，找到两条线的交点(并确定它的存在)可以在常数时间内完成。其次，确定一个点是在一条线的左边还是右边可以在常数时间内完成。

我们将遵循 lhf 的相同基本思想来获得 O(log n) 算法。基本情况是多边形有 2 个或 3 个顶点。这些都可以在恒定时间内处理。

判断直线(v0,v(n/2))是否与直线(x0,x1)相交

情况 1:它们不相交。

在这种情况下，我们感兴趣的线位于多边形分割线的左侧或右侧，因此我们可以递归到多边形的那一半。具体来说，如果 x0 在 (v0,v(n/2)) 的左边，那么右边“一半”中的所有顶点，{v0, v1, ... v(n/2)} 都在同一侧(x0,x1) 的，所以我们知道多边形的“一半”没有交集。

情况 2:它们确实相交。

这种情况有点棘手，但我们仍然可以在常数时间内将交集缩小到多边形的“二分之一”。有 3 个子案例:

案例 2.1:交点在点 v0 和 v(n/2) 之间

我们完成了。该线与多边形相交。

情况2.2:交点离v0较近(即在v0一侧的多边形外)

判断直线(x0,x1)是否与直线(v0,v1)相交。

如果没有，那么我们就完成了，线不与多边形相交。

如果是，找到交点 p。如果 p 位于直线 (v0, v(n/2)) 的右侧，则递归到多边形的右“一半”{v0, v1, ..., v(n/2)}，否则递归向左“一半”{v0, v(n/2), ... vn}。

这种情况下的基本思想是多边形中的所有点都在线 (v0, v1) 的一侧。如果 (x0, x1) 在其与 (v0, v(n/2)) 交点的一侧偏离 (v0, v1)。我们知道在那一边不能与多边形相交。

情况2.3:交点更接近v(n/2)

这种情况的处理方式与情况 2.2 类似，但使用了 v(n/2) 的适当邻居。

我们完成了。对于每个级别，这需要两条线相交、左右检查并确定点在一条线上的位置。每个递归将顶点数除以 2(技术上至少除以 4/3)。因此我们得到了 O(log n) 的运行时间。