Abstract : The purpose of this paper is to present a new method to de- sign exact geometric predicates in algorithms dealing with curved objects such as circular arcs. We focus on the com- parison of the abscissae of two intersection points of circle arcs, which is known to be a difficult predicate involved in the computation of arrangements of circle arcs. We present an algorithm for deciding the x-order of intersections from the signs of the coefficients of a polynomial, obtained by a general approach based on resultants. This method allows the use of efficient arithmetic and filtering techniques lead- ing to fast implementation as shown by the experimental results.
https://hal.inria.fr/hal-01179417
Contributeur : Olivier Devillers
<>
Soumis le : mercredi 22 juillet 2015 - 14:30:36
Dernière modification le : samedi 27 janvier 2018 - 01:30:59
Olivier Devillers, Alexandra Fronville, Bernard Mourrain, Monique Teillaud. Algebraic methods and arithmetic filtering for exact predicates on circle arcs. Annual Symposium on Computational Geometry, 2000, Hong Kong, China. pp.139-147, 〈http://www.cse.ust.hk/tcsc/scg00.html〉. 〈10.1145/336154.336194〉. 〈hal-01179417〉
