TY - JOUR
T1 - Simplified linear-time jordan sorting and polygon clipping
AU - Fung, Khun Yee
AU - Nicholl, Tina M.
AU - Tarjan, Robert E.
AU - Van Wyk, Christopher J.
N1 - Funding Information:
* Research partially supported by NSERC Canada. ** Research partially supported by the National Science Foundation, Grant DCR-8605962, and the Office of Naval Research, Contract NOOO14-87-K-0467.
PY - 1990/6/29
Y1 - 1990/6/29
N2 - Given the intersection points of a Jordan curve with the x-axis in the order in which they occur along the curve, the Jordan sorting problem is to sort them into the order in which they occur along the x-axis. This problem arises in clipping a simple polygon against a rectangle (a "window") and in efficient algorithms for triangulating a simple polygon. Hoffman, Mehlhorn, Rosenstiehl, and Tarjan proposed an algorithm that solves the Jordan sorting problem in time that is linear in the number of intersection points, but their algorithm requires the use of a sophisticated data structure, the level-linked search tree. We propose a variant of the algorithm of Hoffman et al. that retains the linear-time bound but simplifies both the primary data structure and the operations it must perform.
AB - Given the intersection points of a Jordan curve with the x-axis in the order in which they occur along the curve, the Jordan sorting problem is to sort them into the order in which they occur along the x-axis. This problem arises in clipping a simple polygon against a rectangle (a "window") and in efficient algorithms for triangulating a simple polygon. Hoffman, Mehlhorn, Rosenstiehl, and Tarjan proposed an algorithm that solves the Jordan sorting problem in time that is linear in the number of intersection points, but their algorithm requires the use of a sophisticated data structure, the level-linked search tree. We propose a variant of the algorithm of Hoffman et al. that retains the linear-time bound but simplifies both the primary data structure and the operations it must perform.
KW - Analysis of algorithms
KW - computational geometry
KW - data structures
UR - http://www.scopus.com/inward/record.url?scp=0025439853&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0025439853&partnerID=8YFLogxK
U2 - 10.1016/0020-0190(90)90111-A
DO - 10.1016/0020-0190(90)90111-A
M3 - Article
AN - SCOPUS:0025439853
VL - 35
SP - 85
EP - 92
JO - Information Processing Letters
JF - Information Processing Letters
SN - 0020-0190
IS - 2
ER -