# Delaunay Triangulation insertion

6 messages
Open this post in threaded view
|

## Delaunay Triangulation insertion

 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
Open this post in threaded view
|

## Re: Delaunay Triangulation insertion

 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.
Open this post in threaded view
|

## Re: Delaunay Triangulation insertion

 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.
Open this post in threaded view
|

## Re: Delaunay Triangulation insertion

 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#a1432860206073c24ca43dbbdfb13b26eNow 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