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

杨崇俊; 任应超; 李津平

美国《工程索引》（EI）核心期刊
美国《剑桥科学文摘》（CSA）收录期刊
荷兰斯高帕斯数据库（Scopus）收录期刊
英国INSPEC数据库（SA）收录期刊

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

杨崇俊, 任应超, 李津平

文章导航 > 武汉大学学报 ● 信息科学版 > 2006 > 31(9): 835-838

杨崇俊, 任应超, 李津平. 基于单调链的Red/Blue扫描线求交算法[J]. 武汉大学学报 ● 信息科学版, 2006, 31(9): 835-838.

引用本文:

杨崇俊, 任应超, 李津平. 基于单调链的Red/Blue扫描线求交算法[J]. 武汉大学学报 ● 信息科学版, 2006, 31(9): 835-838.

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.

Citation:

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.

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

¹ 中国科学院遥感应用研究所遥感科学国家重点实验室,北京市大屯路甲3号,100101

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

详细信息

作者简介:
杨崇俊,研究员,博士生导师。主要研究方向为网络地理信息系统。

中图分类号: P208

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

¹ State Key Laboratory of Remote Sensing Sciences,IRSA,CAS,A3 Datun Road,Beijing 100101,China

Funds: 国家973计划资助项目(G2000077906)

摘要: 提出了一种基于单调链的Red/Blue平面扫描线算法。该算法针对GIS中线段之间具有连接关系的特性,将平面连接线段集分解为一组单调链,通过对单调链的粗扫描过滤和对线段的精扫描求交,减少了扫描过程中的冗余计算,提高了线段集求交点的效率。实验证明,该算法对于处理具有连接关系的线段集的求交点问题具有很高的效率。
- 单调链 /
- Red/Blue扫描线法 /
- 交点 /
- 两次扫描
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.
- monotone chains /
- Red/Blue sweep line algorithm /
- intersection /
- twice sweep

[1]	鲍金, 王解先, 黄帆, 吴廷, 李维涛, 丁阳. 单圆盾构隧道移动激光扫描收敛值计算 . 武汉大学学报 ● 信息科学版, 2021, 46(3): 353-359. doi: 10.13203/j.whugis20190119
[2]	张毅, 闫利, 杨红, 陈向阳. 地面激光扫描球形标靶的球心误差研究 . 武汉大学学报 ● 信息科学版, 2012, 37(5): 598-601.
[3]	王结臣, 沈定涛, 李利番. 利用于扫描线与梯形分割的面目标空间拓扑计算 . 武汉大学学报 ● 信息科学版, 2010, 35(7): 773-777.
[4]	朱洪欣, 彭碧波, 巨涛. 利用数值法获取两行根数 . 武汉大学学报 ● 信息科学版, 2009, 34(9): 1113-1115.
[5]	王琤, 李霖, 朱海红. 小比例尺地图面状水系名称注记自动配置研究 . 武汉大学学报 ● 信息科学版, 2007, 32(6): 544-547.
[6]	刘经南, 张小红. 利用激光强度信息分类激光扫描测高数据 . 武汉大学学报 ● 信息科学版, 2005, 30(3): 189-193.
[7]	朱元泓, 孔令罔, K. Muenger, 张旭亮. 扫描输入数据的颜色校正 . 武汉大学学报 ● 信息科学版, 2004, 29(9): 836-939.
[8]	赵丽华, 杨元喜, 张勤. 扫描数字化图质量的应变张量评估法 . 武汉大学学报 ● 信息科学版, 2004, 29(8): 725-727.
[9]	党莹, 李友一, 翟林培, 李兴华. 提高TDI摆扫航空相机镜筒扫描控制系统响应速度的方法 . 武汉大学学报 ● 信息科学版, 2003, 28(2): 224-226,232.
[10]	李必军, 方志祥, 任娟. 从激光扫描数据中进行建筑物特征提取研究 . 武汉大学学报 ● 信息科学版, 2003, 28(1): 65-70.
[11]	刘经南, 张小红. 激光扫描测高技术的发展与现状 . 武汉大学学报 ● 信息科学版, 2003, 28(2): 132-137.
[12]	任来平, 赵俊生, 翟国君, 黄谟涛. 机载激光测深海面扫描轨迹计算与分析 . 武汉大学学报 ● 信息科学版, 2002, 27(2): 138-142.
[13]	叶泽田, 何建邦. 航空扫描图像视角辐射误差的统计改正方法 . 武汉大学学报 ● 信息科学版, 2001, 26(1): 12-17.
[14]	刘少创, 尤红建, 刘彤, 李树楷. 机载激光测距-扫描成像制图系统的定位原理与误差分析 . 武汉大学学报 ● 信息科学版, 1999, 24(2): 124-128.
[15]	李树楷, 薛永祺. 机载扫描式激光测距-多光谱成像制图系统 . 武汉大学学报 ● 信息科学版, 1998, 23(4): 340-344.
[16]	马飞. 灰度级形态学及在扫描影像处理中的应用 . 武汉大学学报 ● 信息科学版, 1995, 20(4): 310-316.
[17]	马飞. 基于Windows的扫描等高线地图识别系统 . 武汉大学学报 ● 信息科学版, 1995, 20(3): 228-233.
[18]	张学廉. 大地线临界点和赤交点位置的确定 . 武汉大学学报 ● 信息科学版, 1985, 10(2): 48-56.
[19]	费立凡. 利用栅格扫描数据进行等高线的自动成组综合(化简) . 武汉大学学报 ● 信息科学版, 1983, 8(1): 87-101.
[20]	杨凯, 文沃根. 遥感多光谱扫描(MSS)数字影象的几何纠正 . 武汉大学学报 ● 信息科学版, 1982, 7(1): 77-90.

点击查看大图

计量

文章访问数: 669
HTML全文浏览量: 29
PDF下载量: 471
被引次数: 0

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

¹ 中国科学院遥感应用研究所遥感科学国家重点实验室,北京市大屯路甲3号,100101

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

作者简介:
杨崇俊,研究员,博士生导师。主要研究方向为网络地理信息系统。

收稿日期: 2006-06-27
修回日期: 2006-06-27
刊出日期: 2006-09-05

中图分类号: P208

关键词:

单调链 /

Red/Blue扫描线法 /

交点 /

两次扫描

摘要: 提出了一种基于单调链的Red/Blue平面扫描线算法。该算法针对GIS中线段之间具有连接关系的特性,将平面连接线段集分解为一组单调链,通过对单调链的粗扫描过滤和对线段的精扫描求交,减少了扫描过程中的冗余计算,提高了线段集求交点的效率。实验证明,该算法对于处理具有连接关系的线段集的求交点问题具有很高的效率。