Item

Abstract

The Bentley-Ottmann sweep-line method can be used to compute the arrangement of planar curves provided a number of geometric primitives operating on the curves are available. We discuss the mathematics of the primitives for planar algebraic curves of degree three or less and derive efficient realizations. As a result, we obtain a complete, exact, and efficient algorithm for computing arrangements of cubic curves. Conics and cubic splines are special cases of cubic curves. The algorithm is complete in that it handles all possible degeneracies including singularities. It is exact in that it provides the mathematically correct result. It is efficient in that it can handle hundreds of curves with a quarter million of segments in the final arrangement.