N条线段求交的扫描线算法

        在对图进行计算时,很常用的一个操作就是求若干条线段的交点,比如对图的叠加、截窗,需要频繁地计算线段交点,如果求交算法效率很低,上层的算法再优秀也表现不出好的性能。


        先考虑一个很简单的情形:只有两条线段,求它们是否相交,如果相交,交点在哪?

two-lines

    如左图,如果线段[a0,a1]与[b0,b1]相交,则端点a0、a1必定落在[b0,b1]两侧,同时端点b0、b1必定落在[a0,a1]两侧。只要这两个条件同时满足,即认为两线段相交。(一条线段的端点落在另一条线段上也认为是两线段相交)

    一种比较快速的方法是使用向量外积。

    三角形面积公式的向量形式为:

          triangle_area

        面积恰是两边a,b外积大小的一半。而外积是有方向的。判断两点是否同侧,只需要判断外积是否同号。比如对上面的图进行如下计算:

        s1=(xb0-xa0)*(yb1-ya0)-(xb1-xa0)*(yb0-ya0)

        s2=(xb0-xa1)*(yb1-ya1)-(xb1-xa1)*(yb0-ya1)

        其中s1方向垂直屏幕向内,s2方向垂直屏幕向外,两者异号,所以点a0、a1位于线段[b0,b1]两侧。

        同理,计算s3=(xa1-xb0)*(ya0-yb0)-(xa0-xb0)*(ya1-yb0)和s4=s2-s1+s3异号,可以确定b0、b1落在[a0,a1]两侧。(由面积恒等关系s4-s3=s2-s1可以直接计算s4)

        确定两条线段相交,接着就要计算交点。这一步没有必要用向量计算,只要求解直角坐标下的方程组就好。不过需要注意端点重合的情况。


        现在考虑有很多条线段的情形。如果把这N条线段两两检查交点,时间复杂度是O(n^2),在线段数目很多时,计算速度会非常慢。这时,就需要扫描线算法了。

        观察一下那些相交的线段有什么特点。把每条线段向y轴投影:

projection

        可以看出相交的线段的投影会彼此叠加,而且投影不重合的线段也不可能相交。

        利用这个特性,用一条平行的直线从上到下平移,平移的过程中会与某些线段相交,在任何时刻只考虑这些与扫描线相交的线段之间是否相交。现考虑某时刻这条扫描线上的M条线段(M<=N):

sweep-line-1        在这条扫描线上,相交的线段一定是相邻的,比如b和c。虽然存在b和d不相邻也相交的情况,但由于算法的特点,处理到那个交点时,b和d一定是相邻的。比如:

sweep-line-2        扫描线在点T上方时,c与d相邻,但b与d不相邻。找到交点T。但扫描线经过T到达S上方时,c与d的位置交换了,此时b与d相邻而且相交。所以,只有相邻的线段才有可能相交。

        我们把相邻的线段称为互为邻居,比如a是b的左邻居,c是b的右邻居。

        在扫描线行进的过程中,需要动态维护两个数据结构:

                一条链表,负责记录所以线段的端点和已经找到的交点,每个点按y递减顺序存储(y相同的,按x递增排序);

                一棵二叉树,负责记录与扫描线相交的线段(确切地说,保存的是每条线段的上端点),每条线段按照上端点的x坐标递增顺序存储。

        所谓“扫描”,即程序从头到尾依次处理链表上的每个点,在每处理一个新的点时,会相应地更新链表和二叉树。新的点共有三种,相应的处理方法如下所述:

        1.新点是某线段的上端点p0:

                把这个端点存入二叉树,然后在树中找到p0的左邻居pa和右邻居pb,检查p0与pa是否相交,p0与pb是否相交。如果有交点,把交点存入链表。

sweep-line-3                比如b的上端点接触到扫描线,只需要检查a与b是否相交,b与c是否相交。

                新交点一定会在扫描线的下方,它在链表中的位置也一定在p0的后面,会在未来某个时刻得到处理。因为如果这个交点的位置在p0之前,说明扫描线在之前已经经过了这个交点,程序也已经处理过它了。

        2.新点是某线段的下端点p1:

                在二叉树内找到p1相应的上端点,然后找到上端点的左邻居pa和右邻居pb。把p0从二叉树删除,检查pa与pb是否相交。如果有交点,把交点存入链表。

sweep-line-5                比如b的下端点离开扫描线,删除b后检查a与c是否相交。

        3.新点是交点pt:

                输出这个交点的坐标。然后在二叉树中找到这个交点所在的两条线段pl和pr(假设pl在pr的左边),再找到pl的左邻居pa,和pr的右邻居pb,检查pr与pa是否相交,pl与pb是否相交。如果有交点,把交点存入链表。

sweep-line-4                比如b与c的交点接触到扫描线,检查a与c是否相交,b与d是否相交。

        以上就是扫描线算法的全部细节。采用这种算法,可以把时间复杂度降到O(nlogn+klogn),其中n是线段数目,k是交点数目。如果想了解这个时间是怎样计算出来的,可以参考《Computational Geometry Algorithms and Applications》(作者:M. de Berg, M. van Kreveld, M. Overmars and O. Schwarzkopf)


        我用C实现了这个算法,并且用OpenGL绘制出所有线段及交点。代码可以在这里下载:

                https://github.com/johnhany/SegmentsIntersection

        这是程序运行的结果:

segment-intersection-result

        这里还有一个扫描线求交算法的在线Java演示:Sweep Line Algorithm for Segment Intersection

  Subscribe  
订阅评论