2D Centroidal Voronoi Tessellations with Constraints - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Numerical Mathematics: Theory, Methods and Applications Année : 2010

2D Centroidal Voronoi Tessellations with Constraints

Jane Tournois
  • Fonction : Auteur
  • PersonId : 857875
Pierre Alliez
Olivier Devillers

Résumé

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.
Fichier principal
Vignette du fichier
centroidal-vd.pdf (17.95 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00523812 , version 1 (06-10-2010)
inria-00523812 , version 2 (29-12-2010)

Identifiants

Citer

Jane Tournois, Pierre Alliez, Olivier Devillers. 2D Centroidal Voronoi Tessellations with Constraints. Numerical Mathematics: Theory, Methods and Applications, 2010, 3 (2), pp.212--222. ⟨10.4208/nmtma.2010.32s.6⟩. ⟨inria-00523812v2⟩
1060 Consultations
1626 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More