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 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.

Answer 2

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 3

If you want to learn about both algorithms of triangulation and their coding in C++, then the combined project of coding triangulation in C++ may seem tempting, but it is certainly too difficult for a beginner. Therefore, I suggest you first learn about the algorithmic aspects of triangulation and the basics of C++ seperately before you tackle the combined problem.