CGAL users discussion list

[Timo Strunk <>]

Hi everybody,

Many thanks for the extensive answers! I already read through the thesis 
(that's why I actually thought it might be possible with CGAL) and I 
will now check the new remaining papers.

Thanks again,
Timo

Pedro Machado Manhães de Castro wrote:
>     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
>     <http://salilab.org/%7Edrussel/daniel_russel_thesis.pdf>>. Pedro
>     has some more recent tech reports on the subject <[inria-00344053,
>     v1] Delaunay Triangulations for Moving Points
>     <http://hal.archives-ouvertes.fr/docs/00/34/40/53/PDF/RR-6750.pdf>>
>     and <[inria-00325816, v1] State of the Art: Updating Delaunay ...
>     <http://hal.archives-ouvertes.fr/docs/00/32/58/16/PDF/RR-6665.pdf>>
>     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


--
Timo Strunk

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

Tel: +49 7247 828954