Delaunay Tessellations and Voronoi Diagrams in CGAL

Pierre Alliez 1 Christophe Delage 2 Menelaos Karavelas 3 Sylvain Pion 2 Monique Teillaud 2 Mariette Yvinec 2
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : 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.
Type de document :
Rapport
[Research Report] INRIA Sophia Antipolis - Méditerranée; University of Crete. 2010
Liste complète des métadonnées


https://hal.inria.fr/hal-01421021
Contributeur : Monique Teillaud <>
Soumis le : mercredi 21 décembre 2016 - 14:08:05
Dernière modification le : samedi 27 janvier 2018 - 01:31:48
Document(s) archivé(s) le : mardi 21 mars 2017 - 13:05:42

Fichiers

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

Identifiants

  • HAL Id : hal-01421021, version 1

Collections

Citation

Pierre Alliez, Christophe Delage, Menelaos 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〉

Partager

Métriques

Consultations de la notice

392

Téléchargements de fichiers

383