A Generic Implementation of dD Combinatorial Maps in CGAL - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2013

A Generic Implementation of dD Combinatorial Maps in CGAL

(1) , (2)
1
2
Monique Teillaud

Abstract

We present a generic implementation of dD combinatorial maps and linear cell complexes in CGAL, the Computational Geometry Algorithms Library. A combinatorial map describes an object subdivided into cells; a linear cell complex describes the linear geometry embedding of such a subdivision. In this paper, we show how generic programming and new techniques recently introduced in the C++11 standard allow a fully generic and customizable implementation of these two data structures, while maintaining optimal memory footprint and direct access to all information. We compare our implementation with existing 2D and 3D software, and illustrate its usage by two applications. To the best of our knowledge, the CGAL software packages presented here offer the only available generic implementation of combinatorial maps in any dimension.
Nous présentons une implantation générique des cartes combinatoires et des complexes cellulaires linéaires d-dimensionnels dans la bibliothèque CGAL, Computational Geometry Algorithms Library. Une carte combinatoire décrit un objet subdivisé en cellules~; un complexe cellulaire linéaire décrit le plongement géométrique linéaire d'une telle subdivision. Dans cet article, nous montrons comment la programmation générique et les nouvelles techniques récemment introduites dans le standard C++11 permettent une implantation complètement générique et flexible de ces deux structures de données, tout en maintenant une empreinte en mémoire optimale et un accès direct à toutes les informations. Nous comparons notre implantation avec des logiciels 2D et 3D, et illustrons son utilisation par deux applications. À notre connaissance, les modules CGAL présentés ici offrent la seule implantation générique des cartes combinatoires en dimension quelconque.
Vignette du fichier
intuitif-example-map.png (129.28 Ko) Télécharger le fichier Fichier principal
Vignette du fichier
RR-8427.pdf (717.57 Ko) Télécharger le fichier
Format : Figure, Image
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00919177 , version 1 (16-12-2013)

Identifiers

  • HAL Id : hal-00919177 , version 1

Cite

Guillaume Damiand, Monique Teillaud. A Generic Implementation of dD Combinatorial Maps in CGAL. [Research Report] RR-8427, INRIA. 2013. ⟨hal-00919177⟩
288 View
492 Download

Share

Gmail Facebook Twitter LinkedIn More