An Efficient Algorithm for Intersection, Union and Difference between Two Polygons
Zhiyuan Jerry Lin, Yan Li · 2009
It is one of important algorithms to calculate intersection, union and difference between two polygons in computer graphics and also the kernel approach of spatial overlay analysis in geographic information system (GIS). The operating efficiency and ubiquity are directly influenced by the optimizing algorithm. Firstly, an efficient algorithm for intersection, union and difference between two convex polygons with scan-line algorithm is put forward in this paper, in which it runs a time complexity of O((n + m + k)log(n + m + k)) in a worst presented case. And then, the algorithm is extended to solve all the simple polygons without changing the data Structure, including concave polygons and polygons with holes inside. On one hand, the algorithm can get the intersection, union and difference between polygons through one procedure; on the other hand, it has a higher efficient calculation than the other algorithms. Finally, the new algorithm is compared with the existed algorithms. And the experiment result is showed that the more intersection points the more superior to calculating efficiency through one procedure.