Hi,

check the link. I hope it will help you.

http://www.s-hull.org

Here is a C example and theory. Never tried it out.

http://www.codeproject.com/Articles/587629/A-Delaunay-triangulation-function-in-C

http://www.cse.iitm.ac.in/~augustine/cs6100_even2012/slides/09_DelaunayTriangulation.pdf

http://www.comp.nus.edu.sg/~tantc/ioi_training/CG/l10cs4235.pdf

http://www.personal.psu.edu/faculty/c/x/cxc11/AERSP560/DELAUNEY/13_Two_algorithms_Delauney.pdf

Regards,

Joachim

Thanks a lot . They are very helpful. 

Regards, 

Mahmoud.

If you want an industrial strength Delaunay triangulation, i.e. numerically robust and supporting difficult cases (exactly colinear points, etc.) I suggest you take a look at the CGAL library.

Given that the quality of many geometric algorithms rely on a solid Delaunay triangulation, I encourage you to try it!

http://www.cgal.org/

Hi,

In general the best advice is to use existing libraries where possible. If it is possible in your case you should listen to the previous answers. The other question is if it is actually just the simple 2D Delaunay or if you need it for 3D (with tetrahedra instead of triangles).

If you have to implement it yourself the sweep-line strategy is the easiest. Here is a short outline for this:

1. Sort all point by their x-coordinate first and by the y-coordinate if the x-coordinate of two points is identical.

2. Take the three first points of the sorted list to form the first triangle. You will need another data structure to remember the convex hull of the points you already have connected. At first, it is all the three line of the first triangle.

3. Now iterate over your sorted list of points. For each point check if you need to connect with the two points of the line segments of the convex hull. This can form a new triangle. If it does you need to check as well if you have to flip the edge of the newly formed triangle and the existing neighboring one. Don't forget to update the convex hull.

Actually, the convex hull is not necessary for the algorithm to work. But, it will speed things up significantly and is not very hard to implement. (Remove an edge from the convex hull if it is part of a new triangle and add the other edges of the new triangle to the convex hull.)

You need data structures that work both ways: A triangle needs to know all its edges and vertices. And the edges need to know the corresponding triangles and its vertices. You should store all this information explicitly. It is easiest to use STL vectors of triangles, edges, and vertices and use indices within the data types for triangles and edges.

Bruno Martin,

Thanks a lot , 

Simon Schröder,

Thanks  very much for your answer , it helps a lot . 

OpenSceneGraph (www.openscenegraph.org) has a C++ utility class "DelaunayTriangulator" that triangulates an irregular network of sample points. In your program, you just assign it the sample point array and call the triangulate() method to triangulate the data. Afterwards, you can obtain the generated primitive by calling the getTriangles() method (per the OpenSceneGraph documentation).

HTH...

Thanks a lot Shayne Tuller, this looks great.