inf*_*y_x 19 algorithm line asymptotic-complexity convex-polygon computational-geometry
检测线是否与凸多边形相交的O(n)算法包括检查多边形的任何边是否与线相交,并查看交点的数量是奇数还是偶数.
是否存在渐近更快的算法,例如O(log n)算法？
Chr*_*man 17
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)的运行时.