基于双向链表操作的多边形求交与并的算法改进

被引：5

作者：

朱磊 ^{[1
]}

章秀华 ^{[1
]}

夏震 ^{[2
]}

机构：

[1] 武汉工程大学图像处理与智能控制实验室

[2] 武汉时代地智科技发展有限公司

来源：

计算机与数字工程 | 2013年 / 41卷 / 03期

关键词：

多边形; 双向链表; 求交运算; 求并运算;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

对两个多边形的各边依次求交,根据交点所在边起始点与另一多边形的包含关系确定交点的入出状态,并按交点所在边的序号及距边起始点的距离排序,再插入到双向链表中,利用链表中各交点的入出状态搜索其交集、并集。论文算法中对点重合、边重合等特殊情况,仅需对在求取交点时做简单的特殊处理,其后续操作均使用统一处理方式,相比其它传统的算法,论文提出的算法简单高效。

引用

页码：463 / 465

页数：3

共 10 条

[1]

地理信息系统[M]. 高等教育出版社 , 张超等主编, 1995

[2]

地理信息系统原理与算法[M]. 科学出版社 , 吴立新,史文中编著, 2003

[3]

计算几何[M]. 清华大学出版社 , 周培德著, 2005

[4]

地理信息系统算法基础[M]. 科学出版社 , 张宏,温永宁,刘爱利等编著, 2006