Filtering Relocations on a Delaunay Triangulation

Pedro Machado Manhães de Castro 1 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 : Updating a Delaunay triangulation when its vertices move is a bottleneck in several domains of application. Rebuilding the whole triangulation from scratch is surprisingly a very viable option compared to relocating the vertices. This can be explained by several recent advances in efficient construction of Delaunay triangulations. However, when all points move with a small magnitude, or when only a fraction of the vertices move, rebuilding is no longer the best option. This paper considers the problem of efficiently updating a Delaunay triangulation when its vertices are moving under small perturbations. The main contribution is a set of filters based upon the concept of vertex tolerances. Experiments show that filtering relocations is faster than rebuilding the whole triangulation from scratch under certain conditions.
Type de document :
Article dans une revue
Computer Graphics Forum, Wiley, 2009, 〈10.1111/j.1467-8659.2009.01523.x〉
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00413344
Contributeur : Pedro Machado Manhaes de Castro <>
Soumis le : jeudi 3 septembre 2009 - 17:56:14
Dernière modification le : samedi 27 janvier 2018 - 01:31:40
Document(s) archivé(s) le : mardi 16 octobre 2012 - 10:16:28

Fichier

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

Identifiants

Collections

Citation

Pedro Machado Manhães de Castro, Jane Tournois, Pierre Alliez, Olivier Devillers. Filtering Relocations on a Delaunay Triangulation. Computer Graphics Forum, Wiley, 2009, 〈10.1111/j.1467-8659.2009.01523.x〉. 〈inria-00413344〉

Partager

Métriques

Consultations de la notice

331

Téléchargements de fichiers

258