Delaunay Triangulations

Delaunay triangulations are widely used in scientific computing in many diverse applications. While there are numerous algorithms for computing triangulations, it is the favorable geometric properties of the Delaunay triangulation that make it so useful.

The fundamental property is the Delaunay criterion. In the case of 2-D triangulations, this is often called the empty circumcircle criterion. For a set of points in 2-D, a Delaunay triangulation of these points ensures the circumcircle associated with each triangle contains no other point in its interior. This property is important. In the illustration below, the circumcircle associated with T1 is empty. It does not contain a point in its interior. The circumcircle associated with T2 is empty. It does not contain a point in its interior. This triangulation is a Delaunay triangulation.

The triangles below are different. The circumcircle associated with T1 is not empty. It contains V3 in its interior. The circumcircle associated with T2 is not empty. It contains V1 in its interior. This triangulation is not a Delaunay triangulation.

Delaunay triangles are said to be “well shaped” because in fulfilling the empty circumcircle property, triangles with large internal angles are selected over ones with small internal angles. The triangles in the non-Delaunay triangulation have sharp angles at vertices V2 and V4. If the edge {V2, V4} were replaced by an edge joining V1 and V3, the minimum angle would be maximized and the triangulation would become a Delaunay triangulation. Also, the Delaunay triangulation connects points in a nearest-neighbor manner. These two characteristics, well-shaped triangles and the nearest-neighbor relation, have important implications in practice and motivate the use of Delaunay triangulations in scattered data interpolation.

While the Delaunay property is well defined, the topology of the triangulation is not unique in the presence of degenerate point sets. In two dimensions, degeneracies arise when four or more unique points lie on the same circle. The vertices of a square, for example, have a nonunique Delaunay triangulation.

The properties of Delaunay triangulations extend to higher dimensions. The triangulation of a 3-D set of points is composed of tetrahedra. The next illustration shows a simple 3-D Delaunay triangulation made up of two tetrahedra. The circumsphere of one tetrahedron is shown to highlight the empty circumsphere criterion.

A 3-D Delaunay triangulation produces tetrahedra that satisfy the empty circumsphere criterion.

MATLAB^® provides two ways to create Delaunay triangulations:

• delaunayTriangulation creates a special kind of a triangulation object. You can perform any triangulation query on your data, as well as any Delaunay-specific query. In more formal MATLAB language terms, delaunayTriangulation is a subclass of triangulation.

• delaunay and delaunayn create basic Delaunay triangulation representations. The delaunay function supports the creation of 2-D and 3-D Delaunay triangulations. The delaunayn function supports creating Delaunay triangulations in 4-D and higher.

Tip

Creating Delaunay triangulations in dimensions higher than 6-D is generally not practical for moderate to large point sets due to the exponential growth in required memory.

The delaunayTriangulation class supports creating Delaunay triangulations in 2-D and 3-D. It provides many methods that are useful for developing triangulation-based algorithms. These class methods are like functions, but they are restricted to work with triangulations created using delaunayTriangulation.

The delaunayTriangulation class offers more functionality for developing triangulation-based applications. It is useful when you require the triangulation and you want to perform any of these operations:

• Search the triangulation for triangles or tetrahedra enclosing a query point.

• Use the triangulation to perform a nearest-neighbor point search.

• Query the triangulation's topological adjacency or geometric properties.

• Modify the triangulation to insert or remove points.

• Constrain edges in the triangulation—this is called a constrained Delaunay triangulation.

• Triangulate a polygon and optionally remove the triangles that are outside of the domain.

• Use the Delaunay triangulation to compute the convex hull or Voronoi diagram.