In CGAL, we have face handles to access the faces of a Delaunay triangulation. But those face handles are invalidated, as far as I understand, as soon as any modification is done to the triangulation, see Lifecycle for CGAL vertex handles?.

In Chew refinement algorithm, a list of faces to optimize is constructed, and a point is inserted at the circumcenter of the worst face. However, because all the handles are invalidated once the point is added, the list of face to optimize must be reconstructed from scratch.

This is a costly operation. It would be better to be able to keep track of the unmodified faces, discard the faces which are not valid anymore, and check only the new faces created by the Delaunay insertion.

I tried to directly access the face range in the triangulation data structure, and to store the index of the face in the face range, as well as some other data to check the face is still the same as before. But then I have a problem: I need to know the index of a face handle in the face range container. I tried using:

std::size_t index = std::distance(face_range.begin(), face_handle);

And it didn’t work, as I feared:

CGAL ERROR: assertion violation!
Expr: DSC::type(m_ptr) != DSC::START_END
File: /usr/include/CGAL/Compact_container.h
Line: 968

I thus have several questions:

1. Do a face in the face range keep the same index when new faces are added ?
2. Is it possible to obtain the index of a Face_handle (which is an iterator) in the face range ?
3. Is there a way to do what I want to do (keeping track of faces after modifying the triangulation) which I am not aware of ?