I got lucky the other day, thanks to this function: make_conforming_Delaunay_2.
The X-Plane scenery tools creates a mesh by triangulating a big pile of points, prioritizing the points that are most important to capturing the "shape" of the terrain. It also adds in a series of edges ("constraints") that must exist, to ensure that the borders between land-water are triangle edges.
The problem is that these edges reduce the "quality" of the triangulation - a long forced edge can force a long thin triangle, which in turn looks ugly. For example, in this picture, the red edges are forced into the triangulation, causing a lot of long thin triangles.
CGAL::make_conforming_Delaunay_2 is like a one-stop spa and resort for your mesh...it adds the necessary points to cut long thin triangles into more balanced ones, like this.
I don't expect that kind of service from a code library, but when it happens, I like it!