Delaunay triangulation is an algorithm for generating a mesh of triangles out of an irregular set of points. The algorithm minimizes the maximum angle over all possible triangulations (thus avoiding "skinny" triangles).

It is based on the following "rule"; Given a finite set of points in a plane, three points contribute to a triangle if the circumcircle - a circle whose circumference goes through the points - contains no other point in its interior.

Given an appropriate handling of degeneracies, e.g. 4 or more co-circular points, this will produce a unique triangulation.

In combinatorics, the Delaunay triangulation is the nerve of the cells of a Voronoi diagram. The Delaunay triangulation corresponding to a Voronoi diagram in R^2 is its planar dual. For point sites in general position, the Delaunay triangulation is a triangulation of the sites' convex hull.

--back to combinatorics--
Hmm, I thought it might be useful to note that this can be used for interpolation of a two dimensional function when only a certain number of points is known.
Also note that extrapolation is not possible, in the same way.

An example of use, would be a terrain map. You could plug the basic points of a simple terrain in, and have it generate a list of triangles, and merely send those to opengl for rendering. You could also, when you want to check collisions, check which triangle the point you're checking for is in, and then interpolate the heights of the points of that triangle to the point you're checking, in a method similar to Gouraud shading.

Just thought it might've been worthwhile to note a use of this - when I first read this algorithm, I thought it was cool, but didn't quite see a use for it.

Log in or register to write something here or to contact authors.