在对图进行计算时,很常用的一个操作就是求若干条线段的交点,比如对图的叠加、截窗,需要频繁地计算线段交点,如果求交算法效率很低,上层的算法再优秀也表现不出好的性能。
两条线段交点的计算
先考虑一个很简单的情形:只有两条线段,求它们是否相交,如果相交,交点在哪?
如上图,如果线段[a0,a1]与[b0,b1]相交,则端点a0、a1必定落在[b0,b1]两侧,同时端点b0、b1必定落在[a0,a1]两侧。只要这两个条件同时满足,即认为两线段相交。(一条线段的端点落在另一条线段上也认为是两线段相交)
一种比较快速的方法是使用向量外积。三角形面积公式的向量形式为:
面积恰是两边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)
确定两条线段相交,接着就要计算交点。这一步没有必要用向量计算,只要求解直角坐标下的方程组就好。不过需要注意端点重合的情况。
//inte[i][0]为交点x坐标 //inte[i][1]为交点y坐标 //_inteCount为之前找到的交点总数 if(xa0==xa1 || xb0==xb1) { if(xa0==xa1) { b=(yb0-yb1)/(xb0-xb1); inte[_inteCount][0]=xa0; inte[_inteCount][1]=b*(inte[_inteCount][0]-xb1)+yb1; }else{ a=(ya0-ya1)/(xa0-xa1); inte[_inteCount][0]=xb0; inte[_inteCount][1]=a*(inte[_inteCount][0]-xa1)+ya1; } }else{ a=(ya0-ya1)/(xa0-xa1); b=(yb0-yb1)/(xb0-xb1); inte[_inteCount][0]=(a*xa1-b*xb1-ya1+yb1)/(a-b); inte[_inteCount][1]=a*(inte[_inteCount][0]-xa1)+ya1; }多条线段交点的计算
现在考虑有很多条线段的情形。如果把这N条线段两两检查交点,时间复杂度是O(n^2),在线段数目很多时,计算速度会非常慢。这时,就需要扫描线算法了。
观察一下那些相交的线段有什么特点。把每条线段向y轴投影:
可以看出相交的线段的投影会彼此叠加,而且投影不重合的线段也不可能相交。
利用这个特性,用一条平行的直线从上到下平移,平移的过程中会与某些线段相交,在任何时刻只考虑这些与扫描线相交的线段之间是否相交。现考虑某时刻这条扫描线上的M条线段(M<=N):
在这条扫描线上,相交的线段一定是相邻的,比如b和c。虽然存在b和d不相邻也相交的情况,但由于算法的特点,处理到那个交点时,b和d一定是相邻的。比如:
扫描线在点T上方时,c与d相邻,但b与d不相邻。找到交点T。但扫描线经过T到达S上方时,c与d的位置交换了,此时b与d相邻而且相交。所以,只有相邻的线段才有可能相交。
我们把相邻的线段称为互为邻居,比如a是b的左邻居,c是b的右邻居。
在扫描线行进的过程中,需要动态维护两个数据结构:
- 一条链表,负责记录所以线段的端点和已经找到的交点,每个点按y递减顺序存储(y相同的,按x递增排序);
- 一棵二叉树,负责记录与扫描线相交的线段(确切地说,保存的是每条线段的上端点),每条线段按照上端点的x坐标递增顺序存储。
所谓“扫描”,即程序从头到尾依次处理链表上的每个点,在每处理一个新的点时,会相应地更新链表和二叉树。
新的点共有三种,相应的处理方法如下所述:
新点是某线段的上端点:
把这个端点存入二叉树,然后在树中找到p0的左邻居pa和右邻居pb,检查p0与pa是否相交,p0与pb是否相交。如果有交点,把交点存入链表。
比如b的上端点接触到扫描线,只需要检查a与b是否相交,b与c是否相交。
新交点一定会在扫描线的下方,它在链表中的位置也一定在p0的后面,会在未来某个时刻得到处理。因为如果这个交点的位置在p0之前,说明扫描线在之前已经经过了这个交点,程序也已经处理过它了。
新点是某线段的下端点
在二叉树内找到p1相应的上端点,然后找到上端点的左邻居pa和右邻居pb。把p0从二叉树删除,检查pa与pb是否相交。如果有交点,把交点存入链表。
比如b的下端点离开扫描线,删除b后检查a与c是否相交。
新点是交点
输出这个交点的坐标。然后在二叉树中找到这个交点所在的两条线段pl和pr(假设pl在pr的左边),再找到pl的左邻居pa,和pr的右邻居pb,检查pr与pa是否相交,pl与pb是否相交。如果有交点,把交点存入链表。
比如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绘制出所有线段及交点。代码可以在这里下载:
这是程序运行的结果: