Delaunay Triangulation insertion

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Delaunay Triangulation insertion

gupta61
I have a question regarding the insert method of Delaunay_Triangulation_3.

If I have an existing Delaunay Triangulation from a bunch of points (call it T1), is there a way to insert a set of new points, either as a vector or one by one, without disturbing the connectivities of the finite cells of the existing Triangulation T1.

I can guarantee that the new set of points are outside the volume occupied by T1.

Thanks.
Piyush Gupta
UIUC
Reply | Threaded
Open this post in threaded view
|

Re: Delaunay Triangulation insertion

pbarletta
     mmm..., this is more of a theoretical question and I think the answer is 'probably not'.
   
     Delaunay triangulations have the 'empty sphere property', so there are lots of imaginary spheres inside the volume occupied by T1 and some of them burst out and occupy a large volume of the surrounding space. Especially with some arrangements of the d+1 points ('d' being the dimension) that imply huge spheres.

     If you add a point, even if its outside the volume occupied by T1, chances are the point will be inside in, at least, 1 of the spheres and so CGAL will rerun the triangulation and change some cells. You can see how big these spheres can get when yo use the draw_dual() function.

DISCLAIMER: I studied biology, not computational geometry, nor computer science; so this answer may be complete nonsense.


Reply | Threaded
Open this post in threaded view
|

Re: Delaunay Triangulation insertion

Pranav
In reply to this post by gupta61
gupta61 wrote
If I have an existing Delaunay Triangulation from a bunch of points (call it T1), is there a way to insert a set of new points, either as a vector or one by one, without disturbing the connectivities of the finite cells of the existing Triangulation T1.
You may specify T1 as the constraints to be preserved and try constructing a Constrained Delaunay triangulation like here(see section 1.2.4). However, it will not preserve Delaunay property(but constrained Delaunay) and it may result in addition of new points called the steiner points.
Reply | Threaded
Open this post in threaded view
|

Re: Delaunay Triangulation insertion

gupta61
Thanks for the answers.

So as a follow up, is it possible to create two separate Triangulations, T1 from the old points and T2 from the new points plus some shared points from T1 boundary and then add the cells created by T2 to the T1 Triangulation Data Structure (T1.tds()) using one of the methods listed here http://doc.cgal.org/latest/TDS_3/classTriangulationDataStructure__3.html#a1432860206073c24ca43dbbdfb13b26e

Now as you can imagine because these two triangulations are created separately, it is more than likely that this is an invalid triangulation i.e. faces of the cells created by T2 which are then added to T1 do not match at the boundary. Can Triangulation Data Structure 3 accept this inconsistency?

Piyush Gupta
UIUC
Reply | Threaded
Open this post in threaded view
|

Re: Delaunay Triangulation insertion

Pol Monsó Purtí

I'm quite new with cgal but for experience: Yes, but it will answer false to cdt.is_valid

You'll end up with a constrained delaunay triangulation where all the constraints are on T1, but a triangulation nonetheless (which doesnt satisfy the delaunay property).

If some of the points fell inside the T1 region you might get new triangles there, with the T1 edges untouched, but apparently that's not the case for you.

Note that T2 will connect with closest vertices of T1.


El dia 21/07/2016 08:53, "gupta61" <[hidden email]> va escriure:
Thanks for the answers.

So as a follow up, is it possible to create two separate Triangulations, T1
from the old points and T2 from the new points plus some shared points from
T1 boundary and then add the cells created by T2 to the T1 Triangulation
Data Structure (T1.tds()) using one of the methods listed here
http://doc.cgal.org/latest/TDS_3/classTriangulationDataStructure__3.html#a1432860206073c24ca43dbbdfb13b26e

Now as you can imagine because these two triangulations are created
separately, it is more than likely that this is an invalid triangulation
i.e. faces of the cells created by T2 which are then added to T1 do not
match at the boundary. Can Triangulation Data Structure 3 accept this
inconsistency?





-----
Piyush Gupta
UIUC
--
View this message in context: http://cgal-discuss.949826.n4.nabble.com/Delaunay-Triangulation-insertion-tp4662083p4662086.html
Sent from the cgal-discuss mailing list archive at Nabble.com.

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


Reply | Threaded
Open this post in threaded view
|

Re: Delaunay Triangulation insertion

Pranav
Pol Monsó Purtí wrote
I'm quite new with cgal but for experience: Yes, but it will answer false
to cdt.is_valid
cdt's are implemented only for 2D in CGAL. His domain is 3D.