Abstract An Exact, Complete and Efficient Computation of Arrangements of Bézier Curves

Arrangements of planar curves are fundamental structures in computational geometry. The arrangement package of CGAL can construct and maintain arrangements of various families of curves, when provided with the representation of the curves and some basic geometric functionality on them. It employs the exact computation paradigm in order to handle all degenerate cases in a robust manner. We present the representations and algorithms that are needed for implementing arrangements of Bézier curves using exact arithmetic. The implementation is efficient and complete, handling all degenerate cases. In order to avoid the prohibitive running times incurred by an indiscriminate usage of exact arithmetic, we make extensive use of the geometric properties of Bézier curves for filtering. As a result, most operations are carried out using fast approximate methods, and only in degenerate (or near-degenerate) cases do we resort to the exact, and more computationally demanding, procedures. To the best of our knowledge this is the first complete implementation that can construct arrangements of Bézier curves of any degree, and handle all degenerate cases in a robust manner