A sweep line algorithm for polygonal chain intersection and its applications
Sang C. Park, Hayong Shin, Byoung K. Choi · 2001
Presented in this paper is a sweep-line algorithm for finding all intersections among polygonal chains with an O(( n + k ).log m ) worst-case time complexity, where n is the number of line segments in the polygonal chains, k is the number of intersections, and m is the number of monotone chains . The proposed algorithm is based on the Bentley-Ottmann’s sweep line algorithm, which finds all intersections among a collection of line segments with an O(( n + k )•log n ) time complexity. Unlike the previous polygonal-chain intersection algorithms that are designed to handle special only cases, such as convex polygons or C-oriented polygons, the proposed algorithm can handle arbitrarily shaped polygonal chains having self-intersections. The algorithm has been implemented and applied to 1) testing simplicity of a polygon, 2) finding intersections among polygons and 3) offsetting planar point-sequence curves.