CGAL users discussion list

[Priyank Jain <>]

Hi,

I am trying to add a new vertex to the model, but the new vertex gets added only if it satisfies the delaunay constraint. Well, I am performing the delaunay constraint check on my own (since I could not find a construct that would do it for me with a given polyhedron model and a new point) and my overall algorithm is not working correctly, so I just want to be sure if my understanding and implementation of Delaunay check is sound. As I understand it..

"A model satisfies the Delaunay constraint, iff for all the triangles; the sphere formed by the circumcenter of the triangle, does not contain any other vertex of the model."

And this is how I check for delaunay constraint:

Given points i and j (which lie on my existing model) and new_Point which is the new point that is to be added iff it satisfies the delaunay constraint:

 - center = circumcenter ( i , j , new_Point );
 - sphere = (center, sq_dist ( center, new_Point)

Now I check for all vertices of the model (excluding i and j), and if any of them lie (only) inside the sphere, then the delaunay condition is violated and the new point cannot be added. Delaunay constraint is satisfied if no vertex lies inside the vertex or vertices lie exactly *on* the sphere.

Am I doing something wrong here ?? If you have any suggestions or other words of wisdom, please do let me know.

Thank you for your time.
/Priyank Jain