Home > Delaunay Triangulation

A triangulation is the division of a set of points into a set of triangles, usually with the restriction that each triangle side is entirely shared by two adjacent triangles.

A Delaunay Triangulation of a set of points is a triangulation with the property that every edge is contained in a circle that contains no other points of the set. This implies that the circumcircle, or outcircle, of each triangle contains no other points from the set. The Delaunay Triangulation guarantees that the smallest angle will be maximal which gives well shaped triangles.


Interesting Fact

One would hope that the Delaunay Triangulation would be the result of repeatedly joining the two closest points unless doing so would cross an edge you already have, but sadly that turns out not to be the case. For example, take a kite with its head angle close to 180 degrees and its tail angle quite small. The two closest points are the side points, but the DelaunayTriangulation joins the head to the tail.