I implemented an incremental Delaunay triangulation algorithm. It basically works except it has this weird issue.
The algorithm starts by creating a bounding triangle that it then splits recursively as new points are inserted. Then the 3 extra points are deleted. This yields these kind of meshes before deleting the point:
There's 2 edges in there, which are 100% delaunay, flipping them would make the triangulation non delaunay.
But when I take these points out, I will delete the edges, creating a non convex triangulation.
I could just grab the convex hull of the result and try to add the missing edges but that's very inelegant. I am wondering if there is a better way. For what is worth I implemented the algorithm described here.