| N条线段求交的扫描线算法 | 您所在的位置：网站首页 › 对角线是哪里的线段啊 › N条线段求交的扫描线算法 |
N条线段求交的扫描线算法
|
转载自：http://johnhany.net/2013/11/sweep-algorithm-for-segments-intersection/ N条线段求交的扫描线算法在对图进行计算时，很常用的一个操作就是求若干条线段的交点，比如对图的叠加、截窗，需要频繁地计算线段交点，如果求交算法效率很低，上层的算法再优秀也表现不出好的性能。 先考虑一个很简单的情形：只有两条线段，求它们是否相交，如果相交，交点在哪？ 如左图，如果线段[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 |
【本文地址】