By Samuel Peterson, University of Minnesota Undergraduate

The Goal:

Implement an algorithm for finding the constrained Delaunay triangulation of a given point set in two dimensions.

The Problem:

There are several ways by which to triangulate any given set of points:

There are three possible triangulations of this set of points.

Sometimes we need a triangulation of the points with certain "nice" properties. One of the most common and useful such triangulations is the Delaunay triangulation. Named for the Russian mathematician, Boris Delaunay (originally spelled Delone, and then changed to the French spelling Delaunay), the Delaunay triangulation of a given set of points is defined by the following property:

AB is an edge of the Delaunay triangulation iff there is a circle passing through A and B so that all other points in the point set, C, where C is not equal to A or B, lie outside the circle.

Equivalently, all triangles in the Delaunay triangulation for a set of points will have empty circumscribed circles. That is, no points lie in the interior of any triangle's circumcircle.

We can immediately see that the first triangulation is delaunay, since all of its circumcircles are empty.

There exists a Delaunay triangulation for any set of points in two dimensions. It is always unique as long as no four points in the point set are co-circular. Because it minimizes small angles and circumscribed circles, the Delaunay triangulation is geometrically nice and, in general, pleasing to the eye.

It is important to note that we ultimately wish to generate constrained Delaunay triangulations. That is, we want to be able to compute a modified version of the Delaunay triangulation in which user-defined edges or "constraints" may be specified. Since the Delaunay triangulation is unique for any point set (with the exception of sets with co-circular points), the constrained Delaunay triangulation will most likely contain some edges which are not Delaunay.

Further Information About Delaunay Triangulations:

The Algorithms: