How to enforce convexity of triangulation output?

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.

• As I noted in this answer an earlier question from you, it is not enough to construct a triangle that only contains the point set, the triangle should be large enough to be outside any circle defined by the points in the input set. As such a triangle is unreasonably large, you can treat the vertices symbolically, as explained in the answer. Does this previous answer solve your problem? If not, can you specify why it doesn't? Sep 8, 2023 at 9:24