Cloud Points Triangular Algorithm

Question

I would like to create a simple C ++ application that, given 100 random points (with their convex hull), will triangulate a cloud of these points. I searched this topic and I see that Delaunay triangulation is an option, but I still can’t figure out how to implement this (e.g. in C ++). Also at the next level, I would like to draw all the “illegal” Delaunay triangles in a different color to better show and understand the Delaunay algorithm.

Can someone help me figure out how to triangulate these points? Maybe a small part of the code or even the algorithm that I need to implement?

Answer 1

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

A very bad triangulation algorithm (with an incorrect angle vector) looks something like this:

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

(iiiA) For any other point on the plane, if the point lies in a triangle, draw three triangles from it, connecting the point with the three vertices of the triangle in which it lies. (iiiB) If it lies on an edge (a little unlikely for 100 points, I think you can skip it), connect it to the other two vertices of the four-way in which it lies.

I think you could start with this. The cloud will be fully triangulated, but perhaps more than half of the edges will be illegal. Then you can continue to correct (flip) the necessary edges.

If you find problems with its implementation, I can provide sample code to get you started. Now keep in mind that the return value of the algorithm would be convenient to be the set / vector of triangles; this way you can manipulate them and change your color individually.

Answer 2

I would strongly suggest not coding any Delaunay triangulation algorithm from scratch. If I did this to get an intuitive understanding of what the algorithm looks like, I would take Jonathan Shevchuk's triangle code and change it to assign different colors, etc.

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

Answer 3

If you want to learn about both triangulation algorithms 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, before solving a difficult task, I suggest that you first learn about the algorithmic aspects of triangulation and the basics of C ++ separately .