An Algorithm for Determining the Intersection, Union, and Difference of Any Two Polygons

A new idea about dividing edges of a polygon into odd edges and even edges is presented Based on the topology relationship between each edge of one polygon and another polygon, edges of both input polygons are divided into three types: interior edges, exterior edges, and overlap edges, and then an algorithm for determining intersection, union, and difference of the two polygons is put forward The algorithm runs in time O（（n+m+k） log （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 intersection points Supported by mathematical theorems, the algorithm well resolves the problems in special cases, such as overlapped edges, edges intersection at the vertex of edges, etc The algorithm is easy to implement