PDA

View Full Version : delaunay triangulation

santhosh2708
03-07-2003, 07:26 PM
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.

regards
--
Santhosh
[please cc to santhosh@gdit.iiit.net ]

rgpc
03-07-2003, 09:16 PM
*sigh*

YANOQ - Yet Another Non-Opengl Question.

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

JustHanging
03-07-2003, 11:27 PM
Hi, have you tried the glu tesselators?

-Ilkka

jwatte
03-08-2003, 10:07 AM
JustHanging,

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

oliii
03-08-2003, 05:30 PM
have a look at that one
http://www.dlc.fi/~dkpa/

no source code, just a library.

oliii
03-08-2003, 05:41 PM
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.

JustHanging
03-09-2003, 03:19 AM
Oops, thought this was about something else. Sorry.

-Ilkka