标题：An algorithm for computing the union, intersection and difference of two polygons
作者：Shan-Xin, Zhang ;Rui-Lian, Qiang
作者机构：[Shan-Xin, Zhang ;Rui-Lian, Qiang ] Post-graduate Education College, Shandong University of Science and Technology, Qingdao, China
会议名称：2nd International Conference on Computer Research and Development, ICCRD 2010
会议日期：May 7, 2010 - May 10, 2010
来源：2nd International Conference on Computer Research and Development, ICCRD 2010
摘要：An new idea for setting operations on pairs of polygons algorithm is presented. The algorithm uses a boundary representation for the input and output polygons. Its domain includes polygons as well as polygons with holes within the area of the polygon. The algorithm runs in time 0((n+m+k) ) in a worst presented case, where n and m are the vertex number of the two polygons respectively, and k is the number of point of intersection. The algorithm well resolves the issues in special cases, such as overlapped edges, edges intersection at the vertex of edges, etc. It is facilitated by the use of double circular linked list. The algorithm is easy to implement. © 2010 IEEE.