Filtering Relocations on a Delaunay Triangulation |
| |
Authors: | Pedro Machado Manhães de Castro Jane Tournois Pierre Alliez Olivier Devillers |
| |
Affiliation: | INRIA Sophia Antipolis - Méditerranée, 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. |
| |
Keywords: | I 3 5 [Computer Graphics]: Computational Geometry and Object Modeling Geometric algorithms languages and systems |
|