Polygonal chain intersection

Abstract

In order to find all intersections among polygonal chains. this paper presents a procedure consisting of two phases: (1) splitting polygonal chains into a minimal number of monotone chains and (2) finding intersections among the monotone chains. For the first phase, we suggest an optimal algorithm splitting polygonal chains into a minimal number of monotone chains, with an O(n + r log r) time complexity. where n is the number of line-segments in the polygonal chains and r is the number of C-subchains. For the second phase. we extend Bentley-Ottmann's sweep-line algorithm and the time complexity is O((n + k)log m), where k is the number of intersections. and to is the minimal number of monotone chains. (C) 2002 Elsevier Science Ltd. All rights reserved.