Topology and arrangement computation of semi-algebraic planar curves

Lionel Alberti 1, 2 Bernard Mourrain 1 Julien Wintz 1
1 GALAAD - Geometry, algebra, algorithms
CRISAM - Inria Sophia Antipolis - Méditerranée , UNS - Université Nice Sophia Antipolis, CNRS - Centre National de la Recherche Scientifique : UMR6621
Abstract : We describe a new subdivision method to efficiently compute the topology and the arrangement of implicit planar curves. We emphasize that the output topology and arrangement are guaranteed to be correct. Although we focus on the implicit case, the algorithm can also treat parametric or piecewise linear curves without much additional work and no theoretical difficulties. The method isolates singular points from regular parts and deals with them independently. The topology near singular points is guaranteed through topological degree computation. In either case the topology inside regions is recovered from information on the boundary of a cell of the subdivision. Obtained regions are segmented to provide an efficient insertion operation while dynamically maintaining an arrangement structure. We use enveloping techniques of the polynomial represented in the Bernstein basis to achieve both efficiency and certification. It is finally shown on examples that this algorithm is able to handle curves defined by high degree polynomials with large coefficients, to identify regions of interest and use the resulting structure for either efficient rendering of implicit curves, point localization or boolean operation computation.
Type de document :
Article dans une revue
Computer Aided Geometric Design, Elsevier, 2008, Computer Graphics and Applications, 25 (8), pp.631-651. 〈10.1016/j.cagd.2008.06.009〉
Liste complète des métadonnées

Littérature citée [54 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00343110
Contributeur : Bernard Mourrain <>
Soumis le : samedi 29 novembre 2008 - 17:25:12
Dernière modification le : vendredi 12 janvier 2018 - 01:48:36
Document(s) archivé(s) le : lundi 7 juin 2010 - 23:34:55

Fichier

hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Lionel Alberti, Bernard Mourrain, Julien Wintz. Topology and arrangement computation of semi-algebraic planar curves. Computer Aided Geometric Design, Elsevier, 2008, Computer Graphics and Applications, 25 (8), pp.631-651. 〈10.1016/j.cagd.2008.06.009〉. 〈inria-00343110〉

Partager

Métriques

Consultations de la notice

514

Téléchargements de fichiers

414