CGAL users discussion list

[Pedro Machado Manhães de Castro <>]

Hello,

> Then, in general, your approach (2) is better (rebuilding).

But, sometimes the new points will be fairly close to the old ones. AFAIK,
this would mean that perhaps moving each of the points to its new (close-by)
location could be more efficient. There are two ways to do this: erase the old
point, insert the new one; or, insert then erase. I am currently using the
(undocumented?) T.move( ) function (in Delaunay 2D triangulations), which does
one of the two (I think the later, but I may be wrong).

If you use the T.insert() -> T.remove() AND all the points move, in 
most of the cases I tried (with CGAL 3.4), there is a factor of 
approximately 2 in 2D in favor of rebuilding (using the better static 
rebuilding of CGAL with spatial sort). This can be reduced to 
approximately 4/3, if points do not move "far away" from its original 
position by checking orientation and using flippings (if I remember 
well, this is done in CGAL, but it is not documented.. the T.move() 
method).

In 3D, it becomes even worse for T.move(), the removal operation is 
far too expensive (the factor becomes > 7).
Although if you don't move all the points, you can gain something.

The 2 works I cited before manage to overcome this situation, but the 
two approaches are sensitive to the application.

(static setting) Heuristics + Flipping:
Leonidas Guibas and Daniel Russel
An empirical comparison of techniques for updating Delaunay triangulations.
SCG '04: Proceedings of the twentieth annual symposium on Computational geometry, pages 170-179.

(dynamic setting) Filtering Relocations:
Pedro Machado Manhães de Castro, Jane Tournois, Pierre Alliez, and Olivier Devillers.
Filtering relocations on a Delaunay triangulation. Computer Graphics Forum, 28:1465-1474, 2009. Note: Special issue for EUROGRAPHICS Symposium on Geometry Processing.

Obs:

--1-- If you plan to implement a relocation algorithm such as 
T.move(), you should insert first and then remove.

--2-- In 3D you can optimize (if a point "slightly" change its 
position) by checking first whether a topological change is necessary 
or not. If not, just move the vertex to its new location.
         To do this, take the moving vertex and iterate on its adjacent cells so 
as to check their orientation, then iterate on its adjacent bi-cells 
checking for their Delaunay validity. (and do this for all the moving vertex)
         If the setting is static you can do the optimization above by 
checking cells and bi-cells of the triangulation instead. The 
improvement can be huge in this case.
         For example, in the static setting, if no topological changes 
are needed, the work is analogous to update the embedding of the 
vertices and run the is_valid function of Delaunay_triangulation_3 
(which is more than three times faster than rebuilding for instance). 
The first paper I have cited present some heuristics for this case.
         However, in a dynamic setting, for several triangulations I 
have tried, even checking for validity when every cells and bi-cells 
remain valid after the motion, is slower than simply rebuilding the 
whole triangulation. To overcome this problem you need to think of a 
way to filter relocations. One way to do this is presented in the 
later paper I have cited.

Best regards,
Pedro Machado Manhaes de Castro