6533b86ffe1ef96bd12ce7c9
RESEARCH PRODUCT
Exact, efficient, and complete arrangement computation for cubic curves
Nicola WolpertArno EigenwilligElmar SchömerLutz Kettnersubject
Discrete mathematicsArrangementsControl and OptimizationComputationAlgebraic curvesMathematical analysisBézier curveSweep line algorithmComputer Science ApplicationsModuli of algebraic curvesComputational MathematicsGeometric designComputational Theory and MathematicsFamily of curvesSweep-line algorithmExact geometric computationGeometric primitiveAlgebraic curveGeometry and TopologyRobustnessComputingMethodologies_COMPUTERGRAPHICSMathematicsdescription
AbstractThe Bentley–Ottmann sweep-line method can compute the arrangement of planar curves, provided a number of geometric primitives operating on the curves are available. We discuss the reduction of the primitives to the analysis of curves and curve pairs, and describe efficient realizations of these analyses for planar algebraic curves of degree three or less. We obtain a complete, exact, and efficient algorithm for computing arrangements of cubic curves. Special cases of cubic curves are conics as well as implicitized cubic splines and Bézier curves.The algorithm is complete in that it handles all possible degeneracies such as tangential intersections and 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. The algorithm has been implemented in C++ as an Exacus library called CubiX.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2006-08-01 | Computational Geometry |