Subject: CGAL users discussion list
List archive
Re: [cgal-discuss] which operation is more efficient when proccsing with large size Delaunay_triangulation_3
Chronological Thread
- From: Pedro Machado Manhães de Castro <>
- To:
- Subject: Re: [cgal-discuss] which operation is more efficient when proccsing with large size Delaunay_triangulation_3
- Date: Fri, 11 Dec 2009 15:10:51 +0100
- Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; b=t3VZFhlL4kmK26mkS0aj5yNb2L86Dz83cW+oV8l1tY7RIZgqaJyZM9lIJZwM4usMK9 dXcEmnBFrmXZeaCiQl/gh6mqpzNzRXFNT//c7n1NtgnF/dVnBp4w8z0TaGYNKFkpNlXF fFXBvafTFpWOv+2DsOp65UfubZYpz6t9Bt/VI=
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
- [cgal-discuss] which operation is more efficient when proccsing with large size Delaunay_triangulation_3, Shuchu Han, 12/11/2009
- Re: [cgal-discuss] which operation is more efficient when proccsing with large size Delaunay_triangulation_3, Pedro Machado Manhães de Castro, 12/11/2009
- Re: [cgal-discuss] which operation is more efficient when proccsing with large size Delaunay_triangulation_3, Daniel Duque, 12/11/2009
- Re: [cgal-discuss] which operation is more efficient when proccsing with large size Delaunay_triangulation_3, Pedro Machado Manhães de Castro, 12/11/2009
- Re: [cgal-discuss] which operation is more efficient when proccsing with large size Delaunay_triangulation_3, Shuchu Han, 12/17/2009
- Re: [cgal-discuss] which operation is more efficient when proccsing with large size Delaunay_triangulation_3, Daniel Duque, 12/11/2009
- Re: [cgal-discuss] which operation is more efficient when proccsing with large size Delaunay_triangulation_3, Pedro Machado Manhães de Castro, 12/11/2009
Archive powered by MHonArc 2.6.16.