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

摘要：

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

关键词：多边形、双向链表、求交运算、求并运算

所属期刊栏目：41

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目50975211,61175013;湖北省教育厅科学技术研究项目Q20121507

在线出版日期：2013-07-04（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：463-465