Two efficient algorithms for determining intersection points between simple polygons
The paper describes two new algorithms for calculating the intersection points between two Simple (non-self-intersected) polygons. Both algorithms use a sweep-line approach and differ only in how they store the so-called sweep-line status. The first algorithm (set-based intersection algorithm) needs two one-way dynamic lists of currently pierced line segments, whereas the second algorithm (a binary-search-tree-based intersection algorithm) uses a binary search tree for this purpose. In the situation of the first algorithm, the theoretical time complexity is still O(k(2)) (k=n+m, where n and m are the number of the input polygons' vertices) whereas the second algorithm gives O((k+I) x log(2)(k+I)), where I is the number of intersection points between the polygon edges. However, as shown in the paper, the expected time complexity of the first algorithm is closer to the second algorithm than to the brute-force implementation. The importance of the presented algorithms in GIS applications is considered. Boolean operations, polygon interference determination, splitting a polygon by a polyline, merging the set of polygons and constructing the geometric buffers are briefly described. (C) 2000 Elsevier Science Ltd. All rights reserved.
intersection points simple polygon gis applications sweep-line algorithm computational geometry