We present the representations and algorithms that are needed for implementing arrangements of Bézier curves using exact arithmetic in the CGAL arrangement package. The implementation is efficient and complete, handling all degenerate cases. We make extensive use of the geometric properties of Bézier curves for filtering to avoid the prohibitive running times incurred by an indiscriminate usage of exact arithmetic. As a result, most operations are carried out using fast approximate methods, and only in degenerate (or near-degenerate) cases we resort to the exact, and more computationally-demanding, procedures. This is the first complete implementation that can construct arrangements of Bezier curves of any degree, and handle all degenerate cases in a robust manner, to the best of our knowledge. Integrated with the Boolean set-operation package in CGAL, our implementation can also compute Boolean operations on generalized polygons bounded by closed chains of Bézier curves.
Illustrations
