sample_nickname sample_nickname -4 years ago 117
C++ Question

Points cloud Triangulation algorithm

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 Source

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download