Points cloud Triangulation algorithm

c++ algorithm graphics triangulation
sample_nickname picture sample_nickname · Mar 28, 2013 · Viewed 13.2k times · Source

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

Rahul Banerjee picture Rahul Banerjee · Mar 28, 2013

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.

Related questions

Rasterizing a 2D polygon

I need to create a binary bitmap from a closed 2D polygon represented as a list of points. Could you please point me to efficient and sufficiently simple algorithms to do that, or, even better, some C++ code? Thanks a …

Read More
How to replace all occurrences of a character in string?

What is the effective way to replace all occurrences of a character with another character in std::string?

Read More
What is the most effective way for float and double comparison?

What would be the most efficient way to compare two double or two float values? Simply doing this is not correct: bool CompareDoubles1 (double A, double B) { return A == B; } But something like: bool CompareDoubles2 (double A, double B) { diff = …

Read More