Delaunay Tessellations and Voronoi Diagrams in CGAL - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2010

Delaunay Tessellations and Voronoi Diagrams in CGAL

Pierre Alliez
Sylvain Pion
Monique Teillaud
Mariette Yvinec

Résumé

The Cgal library provides a rich variety of Voronoi diagrams and Delaunay triangulations. This variety covers several aspects: generators, dimensions and metrics, which we describe in Section 2. One aim of this paper is to present the main paradigms used in CGAL: Generic programming, separation between predicates/constructions and combinatorics, and exact geometric computation (not to be confused with exact arithmetic!). The first two paradigms translate into software design choices, described in Section 4, while the last covers both robustness and efficiency issues, respectively described in Sec- tion 6 and 7. Other important aspects of the Cgal library are the interface issues, be they for traversing a tessellation, or for interoperability with other libraries or languages, see Section 5. We present in Section 8 some tessellations at work in the context of surface reconstruction and mesh generation. Section 9 is devoted to some on-going and future work on periodic triangulations (triangulations in periodic spaces), and on high-quality mesh generation with optimized tessellations. Section 10 provides typical numbers in terms of efficiency and scalability for constructing tessellations, and lists the remaining weaknesses. We conclude by listing some of our directions for the future.
Fichier principal
Vignette du fichier
jigsaw.pdf (18.67 Mo) Télécharger le fichier
Vignette du fichier
vignette.png (12.56 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Figure, Image
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01421021 , version 1 (21-12-2016)

Identifiants

  • HAL Id : hal-01421021 , version 1

Citer

Pierre Alliez, Christophe Delage, Menelaos I Karavelas, Sylvain Pion, Monique Teillaud, et al.. Delaunay Tessellations and Voronoi Diagrams in CGAL. [Research Report] INRIA Sophia Antipolis - Méditerranée; University of Crete. 2010. ⟨hal-01421021⟩

Collections

INRIA INRIA2 LARA
393 Consultations
1048 Téléchargements

Partager

Gmail Facebook X LinkedIn More