High-Level Filtering for Arrangements of Conic Arcs

摘要

Many computational geometry algorithms involve the construction and maintenance of planar arrangements of conic arcs. Implementing a general, robust arrangement package for conic arcs handles most practical cases of planar arrangements covered in literature. A possible approach for implementing robust geometric algorithms is to use exact algebraic number types ― yet this may lead to a very slow, inefficient program. In this paper we suggest a simple technique for filtering the computations involved in the arrangement construction: when constructing an arrangement vertex, we keep track of the steps that lead to its construction and the equations we need to solve to obtain its coordinates. This construction history can be used for answering predicates very efficiently, compared to a naive implementation with an exact number type. Furthermore, using this representation most arrangement vertices may be computed approximately at first and can be refined later on in cases of ambiguity. Since such cases are relatively rare, the resulting implementation is both efficient and robust.