Hi,
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.
email: gl@cs.rmit.edu.au
When 2D points are linear, triangulation is skewed.
Its not a convex hull anymore.
The other is from INRIA
Author: Oliver Devillers, SOP, INRIA ftp://ftp-sop.inria.fr/prisme/del-hierarchy
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
triangles.
It took about 113 mSecs for 3600 vertices.
Please suggest a tried out code for 2D delaunay triangulation for
a set of vertices.
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.