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.
Document type :
Reports
Complete list of metadatas


https://hal.inria.fr/hal-01421021
Contributor : Monique Teillaud <>
Submitted on : Wednesday, December 21, 2016 - 2:08:05 PM
Last modification on : Wednesday, October 30, 2019 - 7:36:17 PM
Long-term archiving on : Tuesday, March 21, 2017 - 1:05:42 PM

Files

jigsaw.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

536

Files downloads

972