摘要
对两个多边形的各边依次求交,根据交点所在边起始点与另一多边形的包含关系确定交点的入出状态,并按交点所在边的序号及距边起始点的距离排序,再插入到双向链表中,利用链表中各交点的入出状态搜索其交集、并集。论文算法中对点重合、边重合等特殊情况,仅需对在求取交点时做简单的特殊处理,其后续操作均使用统一处理方式,相比其它传统的算法,论文提出的算法简单高效。
Intersect each side of two polygon successively,then find the starting point of the side on which the intersection is,according to the inclusion relationship of this starting point and the other polygon,the start of the intersection such as Enter or Exit is determined.Sort all the intersections by order number of the side and distance between intersection and the starting point of the side,and insert them into the doubly-linked list.Finally,search the intersection/union by the state of each intersection in the list.Regarding concidence of point or side,simple special treatment is needed when determing the state of intersections,then unified opteration can be used in the following process.This algo is simpler and more efficient than similar algo in other literature.
出处
《计算机与数字工程》
2013年第3期463-465,共3页
Computer & Digital Engineering
基金
国家自然科学基金资助项目(编号:50975211
61175013)
湖北省教育厅科学技术研究项目(编号:Q20121507)资助
