점열곡선의 꼬임을 효율적으로 찾는 알고리즘

Abstract

Presented in this paper is an 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 sweep line algorithm. 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 selfinter sections and singularities (tangential contact, multiple 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.