CGAL users discussion list

[Pedro Machado Manhães de Castro <>]

Hi Timo--

The positions of objects need to be continuous for kinetic data structures to work, so what you proposed will not work. Various of us have worked on algorithms for updating delaunay and regular triangulations when the points move discontinuously but by small amounts, but so far nothing has made it into CGAL. You can find some discussion of the problem in my thesis <http://salilab.org/~drussel/daniel_russel_thesis.pdf>. Pedro has some more recent tech reports on the subject <[inria-00344053, v1] Delaunay Triangulations for Moving Points> and <[inria-00325816, v1] State of the Art: Updating Delaunay ...> which I haven't read yet.

               --Daniel

Hello,

A more recent work can be found here:

Pedro Machado Manhães de Castro, Jane Tournois, Pierre Alliez, and Olivier Devillers. Filtering relocations on a Delaunay triangulation. Computer Graphics Forum, 2009. Note: Special issue for EUROGRAPHICS Symposium on Geometry Processing.

As you will see, moving points on a Delaunay triangulation is not a fast operation, and is not easy to make it 'fast'.
What you can easily do is to insert and remove vertices (the same as "moving"; prefer inserting before removing). Both the 'standard' Regular and Delaunay triangulations in CGAL support that (they are dynamic). If points move not to far, you may compute tolerances which was the main contribution of the articles cited by Daniel.
 
Cheers,
Pedro

On Jul 9, 2009, at 5:02 AM, Timo Strunk wrote:

Hi everybody,

Currently I am trying to use the Regular Triangulation 3 class from the Kinetic Data Structures package.
The examples show a usage for points with a continuous trajectory, which are read in using a stream directly from a file.

The main difference to my problem is that I have no continuous movement, but rather static snapshots, which however resemble themselves to a high degree: I don't have a continuous time. My biggest hope was therefore to use the Kinetic RT class in a way, where I can prepare the coordinates by hand each step and just tell it to afterwards recalculate.

I didn't find this in the manual - is it possible? Here is how I would try to do it:

First of all, I will set is_editing to true

Into the active objects table, I would insert:
Traits::Static_kernel::Weighted_point_3 Weighted_point
instead of
Traits::Kinetic_kernel::Weighted_point_3 Weighted_point
via mot.insert (my_static_weighted_point), where mot is an Active Objects Table
(documented here - the documentation is a bit off, because it is insert instead of insert_object, right?):
http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/Kinetic_framework_ref/Concept_Kinetic--ActiveObjectsTable.html#Cross_link_anchor_1576

Then I will set is_editing to false, so the triangulation gets created.

Now whenever points moved, I would set is_editing again, afterwards use mot.set(point_key, data) to the new location of the point and turn off is_editing. The main reason why I write now is that I think there is some flaw in my logic, because of the description of the set function )also from the url above):

"This method changes the motion of one moving object. The position at the current time should not be different from the previous current position. However, at the moment I do not check this as there is no reference to time in the /Kinetic::ActiveObjectsTable <http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/Kinetic_framework_ref/Concept_Kinetic--ActiveObjectsTable.html#Cross_link_anchor_1576>/. If /is_editing()/ is not true, then it is as if the calls /set_is_editing(true)/, /set(key, value)/ and finally /set_is_editing(false)/ were made. If it is true, then no notifications are created. "

Would this work? In the end I am completely missing the time as it was never set, therefore the positions at the same time would also move.

Sorry for the long mail; I'd just like to know, if this is even possible with the current (as it seems continuous) Kinetic RT3 package or not.

Thanks for reading,
Timo

--
Timo Strunk

Forschungszentrum Karlsruhe
Institut für Nanotechnologie
Gebäude 640
Hermann-von-Helmholtz-Platz 1
D-76344 Eggenstein-Leopoldshafen

Tel: +49 7247 828954

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss