2D Centroidal Voronoi Tessellations with Constraints

Jane Tournois 1 Pierre Alliez 1 Olivier Devillers 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : We tackle the problem of constructing 2D centroidal Voronoi tessellations with constraints through an efficient and robust construction of bounded Voronoi diagrams, the pseudo-dual of the constrained Delaunay triangulation. We exploit the fact that the cells of the bounded Voronoi diagram can be obtained by clipping the ordinary ones against the constrained Delaunay edges. The clipping itself is efficiently computed by identifying for each constrained edge the (connected) set of triangles whose dual Voronoi vertex is hidden by the constraint. The resulting construction is amenable to Lloyd relaxation so as to obtain a centroidal tessellation with constraints.
Type de document :
Article dans une revue
Numerical Mathematics: Theory, Methods and Applications, Global Science Press, 2010, 3 (2), pp.212--222. 〈http://www.global-sci.org/nmtma/volumes/v3n2/pdf/32-212.pdf〉. 〈10.4208/nmtma.2010.32s.6〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00523812
Contributeur : Olivier Devillers <>
Soumis le : mercredi 29 décembre 2010 - 11:47:09
Dernière modification le : mardi 3 juillet 2018 - 13:12:19
Document(s) archivé(s) le : vendredi 2 décembre 2016 - 19:35:00

Fichier

centroidal-vd.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jane Tournois, Pierre Alliez, Olivier Devillers. 2D Centroidal Voronoi Tessellations with Constraints. Numerical Mathematics: Theory, Methods and Applications, Global Science Press, 2010, 3 (2), pp.212--222. 〈http://www.global-sci.org/nmtma/volumes/v3n2/pdf/32-212.pdf〉. 〈10.4208/nmtma.2010.32s.6〉. 〈inria-00523812v2〉

Partager

Métriques

Consultations de la notice

551

Téléchargements de fichiers

935