问题:

I'm doing 3D Delaunay, with the incremental method. I've tested it in 2D with an initial triangle for inserting the vertices and it works great, but if I use a triangle for 3D, some vertices do not fall into any circumscribed sphere therefore they don't get inserted. I've tried with a tetrahedron but if the first node falls into the four of the faces, all vertices create new edges towards this new vertex, and deletes all of the initial triangles.

回答1:

Whichever shape you take, you will always have to deal with side effects. The best shape is no shape. This is what we are doing in the CGAL library http://www.cgal.org Look at the manual, chapters "2D triangulations" and "3D triangulations". See also or the journal paper https://hal.inria.fr/inria-00167199/

回答2:

You can read my answer for this question (Bowyer-Watson algorithm: how to fill "holes" left by removing triangles with super triangle vertices). If the supertriangle is too small sometimes you end with circumcircle outside of the supertriangle. You can try a point-in-polygon test to avoid it.