Points cloud Triangulation algorithm

Question

I would like to create a simple C++ application that, given 100 random points (with their convex hull) it will triangulate this points' cloud. I've searched for this subject and I can see that Delaunay triangulation is an option but I still can't understand how to implement this (in c++ for example). Also at a next level I would like to paint all the Delaunay "illegal" triangles a different colour to better show and understand Delaunay's algorithm.

Could anyone help me understand how to triangulate these points? Maybe a small code part or generally the algorithm that I need to implement?

Answer 1

I would strongly suggest not coding up any Delaunay Triangulation algorithm from scratch. If I were doing this to get an intuitive understanding of what the algorithm's output looks like, I'd take Johnathan Shewchuk's Triangle code and modify it to assign different colors, etc.

If, however, you are sufficiently motivated to implement this from scratch, then my suggestion would be to implement the 2D Delaunay Triangulation first, before you tackle the 3D version.

Answer 2

I guess you need a general triangulation first and then fix everything that is not Delaunay-legal?

A very bad triangulation algorithm (with a bad angle vector) goes something like this:

(i) Get the convex hull of the point cloud (ii) Connect a random point of the CH (it's convenient to use the first one) with every other point of the CH (except of course the next and previous one, with which it already forms an edge).

(iiiA) For every other point in the plane, if the point lies in a triangle then make three triangles out of it by connecting the point with the three vertices of the triangle it lies in. (iiiB) If it lies on an edge (a bit unlikely for 100 points, I guess you can skip it), connect it with the other two vertices of the quadrilateral it lies in.

I guess you could start with this. The cloud will be fully triangulated, but possibly more than half the edges will be Delaunay illegal. Then you can go on on fixing (flipping) the necessary edges.

If you find problems implementing it I could provide some sample code to get you started. For now have in mind that the return value of the algorithm would be convenient to be a set/vector of triangles; that way you can manipulate them and change their color individually.