基于扫描线的线段求交算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于扫描线的线段求交算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：本文以基于扫描线算法求线段的交点，首先设有一条扫描线l，从高于所有线段的位置起，自上而下地扫描整个平面，与当前扫描线相交的线段构成一个扫描线状态结构，在扫描线从上个事件点移到下个事件点时，要根据事件点的不同来更新扫描线的状态结构。该算法能避免盲目求交时大量无效求交测试。

关键词：线段；扫描线；求交

中图分类号：TP391.41

在地理信息系统中，线段求交是地图叠合处理必须要面对的问题，传统的做法是对所求区域内的所有线段对依次进行求交测试。当待求线段数比较少时，采用该方法能够很方便的得到结果，且容易实现；但线段数目比较庞大是，传统的方法就显得“力不从心”了，本文采用扫描线的方法求线段的交点，适用于解决大规模线段求交的问题。

1 扫描线填充算法

线段求交最简单的做法是依次判断每一对线段，测试它们是否相交，如果相交，则记录交点，但这种算法的时间复杂度是O（n2），如果所面对的是如图1所示的问题，即线段集间两两相交，此算法的效率也是最优解，因为无论采用何种算法，都需要计算每对线段间的交点，但实际情况是只有少数线段对间存在交点，即交点的个数远远小于线段条数n的平方级。此时，我们称线段的交点为“敏感点”，适用于处理此种情况的算法称为“交点敏感”的算法。

图1 所有线段两两相交

定义1 事件点：线段端点、线段的交点称为事件点

定义2 扫描线状态表：与当前扫描线相交的所有线段构成的集合称为“扫描线的状态表”。扫描线状态表按照与当前扫描线相交的线段自左向右排序。

设有一条扫描线l，从高于所有线段的位置起，自上而下地扫描整个平面，当扫描线到达某个事件点时才需要更新扫描线的状态表，此时需要进行一些相交测试，根据所触及事件点的不同，扫描线状态结构表要做不同的处理，事件点分为线段上端点、线段下端点、线段交点，因此，在更新扫描线状态表时要分为三种情况进行讨论。

1.1 事件点为线段的上端点

上端点所对应的线段开始与扫描线相交，此时需要测试该线段和那些与当前扫面线相交的线段是否相交。以图2为例，在扫描线未到达S3的上端点前一瞬间扫描线的状态表顺序为S2、S1、S4。当扫描线到达S3的上端点，S3开始与当前扫描线相交，此时扫描线的状态表更新为S2、S1、S3、S4。也即S3在扫描线的状态表中位于S1与S4之间，因此需要对S3 分别与S1和S4做求交测试。

图2 事件点为上端点

1.2 事件点为线段的下端点

下端点所对应的线段将不再与扫面线相交，因此需要将该线段从状态表中删去，以图3为例，扫描线到达S3下端点的前一瞬间，扫描线状态表的状态为S2、S1、S3、S4，当扫描线到达S3下端点时S3从状态表中删除，此时扫描线状态表的状态变为S2、S1、S4，也即S1与S4变为相邻的线段，需要对他们进行求交测试。

图3 事件点为下端点

1.3 事件点为线段的交点

以图4为例，在扫描线进入事件点前一瞬间，S4与S1相邻，S3与S5相邻，当扫描线到达下一个事件点前，扫描线状态表的顺序变为S2、S1、S3、S4、S5，也即变为S3与S1相邻，S4与S5相邻，此时需要对它们进行求交测试。

图4 事件点为线段的交点

上述在求交测试的过程中，如果所测试的两条线段相交，此交点可能在以前求交的测试中已经求出，此时不需重复记录，如果以前没有求出，则需要记录此交点，为此，需要建立一个交点表，用于存储线段的交点。

2 数据结构

实现本文算法用到以下数据结构：

（1）事件点

class point

{

double x，y

} ；

（2）线段

class Line

{

point p1，p2；

} ；

对于每条线段p1存储上端点，p2存储下端点，如果线段为水平线段时，p1存储左端点，p2存储右端点。

3 算法步骤

实现本文算法步骤如下：

Step1初始化一个事件队列EvenList，事件队列的初值为线段端点序列，在该序列中，端点从上到下，处于同一水平线的上端点从上到下排序。初始化一个初值为空的交点链表IntersectList；初始化一个初值为空的扫描线状态表StatusList；

Step2如果EvenList不为空，转到Setp3 ，否则转到Step4；

Step3则从EvenList中删除一个事件点， 根据事件点的不同更新扫描线状态结构表。如果求出新的交点，则把新交点添加到IntersectList，并按顺序插入到EvenList中；

Step4 算法结束。

4 实验结果

根据本文基于扫描线的线段求交算法，笔者在VC++6.0环境下实现了对应的算法，图5（b）用本文算法对图5（a）中一组线段集所得到的线段求交算法的结果。

（a） 线段集 （b） 线段集交点

图5 线段求交

参考文献：

[1]吴立新，史文中.地理信息系统原理与算法[M].科学出版社，2005.

[2]周陪德.计算几何――算法设计与分析（第4版）[M].清华大学出版社，2011.

[3]Joseph O’putation Geometry in C[M].机械工业出版社，2005.

[4]Mark de Berg等著，邓俊辉译.计算几何：算法与应用（第3版）[M].清华大学出版社，2009.

作者简介：李源（1981-），男，硕士，助教，主要研究方向：计算机图形学、地理信息系统；李永钢（1985-），男，硕士，助教，主要研究方向：面向服务体系结构，数据仓库与数据分析。