Sometimes You Get a Gift

Sometimes you get really lucky and a library has a routine that just does exactly what you want.

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!