TY - GEN
T1 - A sweep line algorithm for polygonal chain intersection and its applications
AU - Park, Sang C.
AU - Shin, Hayong
AU - Choi, Byoung K.
N1 - Copyright:
Copyright 2019 Elsevier B.V., All rights reserved.
PY - 2001
Y1 - 2001
N2 - Presented in this paper is a sweep-line algorithm for finding all intersections among polygonal chains with an O((n + k)-Iog 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.
AB - Presented in this paper is a sweep-line algorithm for finding all intersections among polygonal chains with an O((n + k)-Iog 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.
KW - Intersection
KW - Polygonal chain
KW - Sweep line algorithm
UR - http://www.scopus.com/inward/record.url?scp=84904258866&partnerID=8YFLogxK
U2 - 10.1007/978-0-387-35490-3
DO - 10.1007/978-0-387-35490-3
M3 - Conference contribution
AN - SCOPUS:84904258866
SN - 9781475753226
T3 - IFIP Advances in Information and Communication Technology
SP - 309
EP - 324
BT - Geometric Modelling
PB - Springer New York LLC
T2 - IFIP TC5/WG5.2 6th International Workshop on Geometric Modelling
Y2 - 7 December 1998 through 9 December 1998
ER -