Sorting Points Along an Algebraic Curve
John K. Johnstone, Chanderjit L. Bajaj · SIAM Journal on Computing · 1990
An operation that is frequently needed during the creation and manipulation of geometric models is the sorting of points along an algebraic curve. Given a segment $\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{AB}$ of an algebraic curve, a set of points on the curve is sorted from A to B along $\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{AB}$ by putting them into the order that they would be encountered in traveling continuously from A to B along $\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{AB}$. A new method for sorting points along a plane or space algebraic curve is presented. Key steps in this method are the decomposition of a plane algebraic curve into convex segments and point location in this decomposition. This new method can sort points on an arbitrary algebraic curve (including points spread over several connected components) and it is particularly efficient because of its preprocessing, both of which make it superior to conventional methods. The complexity of the new method is analyzed, and execution times of various sorting methods on a number of algebraic curves are presented. The theory developed for sorting can also be used to locate points on an arbitrary segment of an algebraic curve and to decide whether two points lie on the same connected component.