delaunay triangulation

I have a set of 2D points which have to be triangulated.
Can you suggest me a faster 2D Delaunay triangulation code in C or C++.

I tried 2 of the available ones.
One from RMIT
Author: Geoff Leach, Department of Computer Science, RMIT.
When 2D points are linear, triangulation is skewed.
Its not a convex hull anymore.

The other is from INRIA
Author: Oliver Devillers, SOP, INRIA
This does not give triangles, but edges only from a set of 2D points
I tried to extract triangles. Sometimes, I find holes i.e. lose a few
It took about 113 mSecs for 3600 vertices.

Please suggest a tried out code for 2D delaunay triangulation for
a set of vertices.


[please cc to ]


YANOQ - Yet Another Non-Opengl Question.

Perhaps you would be better off asking this question on the Algorithms mailing list.

Hi, have you tried the glu tesselators?



Please explain to me how the GLU tesselators can turn a point cloud into a flat triangle mesh.

have a look at that one

no source code, just a library.

I’ve got a friend doing a PhD at the IRISA, using a constrained delaunay triangulation to simulate a crowd of people in a busy city. Quite clever. He puts constrains on some edges to simulate thick walls and obstacles, and the moving points do a radius check with only the neighbouring points and the constrained edges, so it’s pretty fast. He recons he can animate 10,000s of points at a good frame rate.

He also uses a delaunay triangulation on the constrained parts to do path planning. Uses a tree structure to organise the triangles into convex hulls, in turn binded together into bigger convex hulls. So path planning is pretty damn quick too.

Oops, thought this was about something else. Sorry.