基于单调链的Red/Blue扫描线求交算法  

Red-Blue Sweep Line Algorithm Based on Monotone Chains for Connected Line Segment Intersection Problems

作　　者：杨崇俊[1] 任应超[1] 李津平[1] 

机构地区：[1]中国科学院遥感应用研究所遥感科学国家重点实验室,北京市大屯路甲3号100101

出　　处：《武汉大学学报（信息科学版）》2006年第9期835-838,共4页Geomatics and Information Science of Wuhan University

基　　金：国家973计划资助项目(G2000077906)

摘　　要：提出了一种基于单调链的Red/Blue平面扫描线算法。该算法针对GIS中线段之间具有连接关系的特性,将平面连接线段集分解为一组单调链,通过对单调链的粗扫描过滤和对线段的精扫描求交,减少了扫描过程中的冗余计算,提高了线段集求交点的效率。实验证明,该算法对于处理具有连接关系的线段集的求交点问题具有很高的效率。An improved Red/Blue sweep line algorithm is preserted for connected line segment intersection in GIS. First the algorithm breaks down the connected segments into monotone chains. By filtration for monotone chains, those monotone chains which can not generate intersection points are removed. Then algorithm computes intersection points among rest monotone chains by traditional Red/Blue sweep line algorithm, which is based on isolated line s more egmen efficie Key words ts. Both theoretic analysis and experiments show that our algorithm performs ntly than the traditional Red/Blue sweep line algorithm does.

关 键 词：单调链 Red/Blue扫描线法 交点 两次扫描 

分 类 号：P208[天文地球—地图制图学与地理信息工程]