新浪博客

求N条线段的所有交点——Bentley-Ottmann算法

2010-12-16 22:20阅读：

http://blog.sina.cn/dpool/blog/u/1773098877

单调链的说明: 对于折线L = {p1，p2，p3，…，pn}，xi是pi的横坐标，若xi<=xi+1，或xi>=xi+1，则称折线为关于x轴的单调增(或减)链。同样，对于y轴也适用。
求N条线段的所有交点——Bentley-Ottmann算法

平面上多条线段求交问题。
对于平面上的N条线段，若使用最直接的方法，即两两求其交点，则(N-1) + (N-2)+…1 = N(N-1)/2次运算，时间复杂度是O(n2)。这种方法对交点个数接近N(N-1)/2的情况可行，但大多数情况下，N条线段形成的交点个数是较少的，此时算法可调整成与输入线段个数和输出的交点个数相关的效
率更高的方法，如Bentley-Ottmann 算法。
求N条线段的所有交点——Bentley-Ottmann算法
算法的思路是，以X轴升序构造顶点队列和初始化扫描线链表后,对顶点队列中所有元素开始循环:
当取出的元素为线段的左端点时，首先将此条线段插入到扫描线段链表中，同时以Y轴的升序重排链表中所有元素，然后分别计算此条线段与扫描线段链表中上下相邻线段的相交情况，若有交点，则将交点插入到顶点队列中。
当取出的元素为线段的右端点时，首先将此条线段从扫描线段链表中删除，然后计算此时与此条线段上下相邻的那两条线段之间的相交情况，如果有交点，但在顶点队列中还不存在，则将其插入顶点队列。
当取出的元素为交点时，首先将这个交点增加到最后要输出的结果集合中。然后得到这个交点从属的两条线段，交换它们在扫描线链表中的位置后，分别与新邻接的线段求交点，如果有交点，但在顶点队列中还不存在，则将其插入顶点队列。
以上3种情况分别处理后，从顶点队列中移走这个取出的元素。
当循环处理完毕，结果集合中的元素即为所有的交点。
这种方法最后以一次循环取代了最直接的两两线段求交点的两次循环。不过，需要注意的是，当交点个数接近n2级别时，Bentley-Ottmann算法的效率比直接两两求其交点的方法低下。


Bentley-Ottmann代价：O((n+k)*lg(n))，其中n为segments个数，k为intersects个数。

参考代码：
int intersect_Polygon( Polygon Pn )
{
EventQueue Eq(Pn); //顶点队列
SweepLine SL(Pn); //扫描线链表
Point e; // 当前的顶点
SLseg* s; // 当前的线段
Point singlepoint; //准备求得的交点
PointList PL; //所有求得的交点保存在其中
while (Eq != EMPTY) //循环开始，直到队列为空
{
e = Eq->next(); //得到开头顶点元素
if (e->type == LEFT) { // 当为线段的开始顶点
s = SL.add(e); // 增加此顶点所属的线段到扫描线链表中
if (SL.intersect( s, s->above, singlepoint)) //判断此顶点所属线段与处于其上的线段是否相交
{
Eq->insert(singlepoint); // 插入交点到顶点队列中
SL.record(s, s->above, singlepoint);//在扫描线链表中记录此交点的上下线段
}
if (SL.intersect( s, s->below, singlepoint))
Eq->insert(singlepoint); // 插入交点到顶点队列中
}
else if(e->type == RIGHT) //当为线段的结束顶点
{
s = SL.find(e); // 从扫描线链表中找到此顶点所属的线段
if (SL.intersect( s->above, s->below,singlepoint)) //判断此线段的上下两相邻线段是否相交
if(Eq->find(singlepoint) == false) //如果求得的交点还不存在于顶点队列中
Eq->insert(singlepoint) //插入这个新求的交点到顶点队列中
SL.remove(s); // 从扫描线链表中移走此顶点所属的线段
}
else //当为交点
{
PL.add(e); //保存结果到最后的输出集合中
SLseg* sE1 = SL.findrecord(e,ABOVE);//得到此交点在扫描线链表中的第一条线段
SLseg* sE2 = SL.findrecord(e,BELOW);//得到此交点在扫描线链表中的第二条线段
SL.swap(sE1,sE2); //交换两条线段位置，从几何上可看作：通过顶点后，两条线段的上下位置关系交换
if (SL.intersect( sE2, sE2->above,singlepoint)) //判断新的上下两相邻线段是否相交
if(Eq->find(singlepoint) == false) //如果求得的交点还不存在于顶点队列中
Eq->insert(singlepoint) //插入这个新求的交点到顶点队列中
if (SL.intersect( sE1, sE1->below,singlepoint //判断新的上下两相邻线段是否相交
if(Eq->find(singlepoint) == false) //如果求得的交点还不存在于顶点队列中
Eq->insert(singlepoint) //插入这个新求的交点到顶点队列中
}
Eq->remove(e); //此元素处理完毕，将其弹出
}
return 1;
}

我的更多文章

下载客户端阅读体验更佳

APP专享