CGAL Using Locate() to Find Cell on Triangulation

Question

Using CGAL, I have a 3D Delaunay Triangulation of a set of random points on the unit sphere, that I obtained via:

Delaunay T(points.begin(), points.end());

Now, what I would like to be able to do is query T (using locate() or something like that) to find the three vertices of the surface facet that an arbitrary point (also on the unit sphere) is contained inside.

When I use locate(), I get interior cells as results sometimes, which include the infinite vertex. I don't want any of these. I just want the surface facets and to be able to do this for any arbitrary point I try to find that is also on the unit sphere. Trying to figure this out has taken a lot longer than I thought it would.

Any help would be much obliged. Thanks.

Answer 1

So I would use find_conflit(), with CGAL::Emptyset_iterator for cit because you don't need these. In bfit, you will get the facets of the boundary of the "hole", and the hole is all tetrahedra in conflict with your point (whose circumscribing sphere contains the point, with a natural extension to the infinite vertex). So, for bfit, put them in a standard container using std::back_inserter for example. Then, iterate over these, tests if they are finite facets. The finite facets you get are those that separate your point from the rest of the triangulation, so, you can then do orientation() tests with the center of the sphere to get the one you are interested in.