| 基于单调链的Red/Blue扫描线求交算法 |
| |
| 引用本文： | 杨崇俊,任应超,李津平.基于单调链的Red/Blue扫描线求交算法[J].武汉大学学报(信息科学版),2006,31(9):835-838. |
| |
| 作者姓名： | 杨崇俊 任应超 李津平 |
| |
| 作者单位： | 中国科学院遥感应用研究所遥感科学国家重点实验室,100101 |
| |
| 基金项目： | 国家重点基础研究发展计划(973计划) |
| |
| 摘 要： | 提出了一种基于单调链的Red／Blue平面扫描线算法。该算法针对GIS中线段之间具有连接关系的特性，将平面连接线段集分解为一组单调链，通过对单调链的粗扫描过滤和对线段的精扫描求交，减少了扫描过程中的冗余计算，提高了线段集求交点的效率。实验证明，该算法对于处理具有连接关系的线段集的求交点问题具有很高的效率。
|
| 关 键 词： | 单调链 Red/Blue扫描线法 交点 两次扫描 |
| 文章编号： | 1671-8860(2006)09-0835-04 |
| 修稿时间： | 2006年6月27日 |
Red-Blue Sweep Line Algorithm Based on Monotone Chains for Connected Line Segment Intersection Problems |
| |
| YANG Chongjun,REN Yingchao,LI Jinping.Red-Blue Sweep Line Algorithm Based on Monotone Chains for Connected Line Segment Intersection Problems[J].Geomatics and Information Science of Wuhan University,2006,31(9):835-838. |
| |
| Authors: | YANG Chongjun REN Yingchao LI Jinping |
| |
| Abstract: | 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 segments.Both theoretic analysis and experiments show that our algorithm performs more efficiently than the traditional Red/Blue sweep line algorithm does. |
| |
| Keywords: | monotone chains Red/Blue sweep line algorithm intersection twice sweep |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
