这是一篇线段相关毕业论文的格式范文,与基于扫描线的线段求交算法相关毕业论文模板。是硕士论文专业与线段及地理信息系统及数据结构方面相关的免费优秀学术论文范文资料，可作为线段方面的大学硕士与本科毕业论文开题报告范文和职称论文论文写作参考文献下载。
摘 要：本文以基于扫描线算法求线段的交点,首先设有一条扫描线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 事件点
13888888888
点击咨询 