Delaunay Triangulation Algorithms

Sorry, but you need Java to see the animation.

This applet demonstrates four algorithms (Incremental, Gift Wrap, Divide and Conquer, QuickHull) computing the Delaunay triangulation of points in two dimensions.

The algorithms demonstrated are actually algorithms for computing 3D convex hulls. This works because the Delaunay triangulation of a set of 2D points with coordinates (x,y) is just the bottom part of the convex hull of 3D points with coordinates (x,y,x2+y2). You can drag the view direction around in the applet window above to see how all the points lie on the paraboloid z=x2+y2.

You might notice that some of the time the algorithms don't seem to be doing anything. That's because they are also computing the top part of the convex hull (which is something called the furthest-point Delaunay triangulation algorithm).


lambert@cse.unsw.edu.au
Last modified: Tue Sep 22 18:17:49 AET 1998