Does it always produce a unique mesh?

No. Degenerate configurations, including cocircular points, can admit multiple valid choices.

Does it fill the space between points?

An ordinary unconstrained planar triangulation covers the convex hull, which may include unwanted regions.

Is it limited to two dimensions?

No. Higher-dimensional versions use simplices rather than planar triangles.

AI Glossary / Computer vision and multimodal AI / Advanced

Delaunay triangulation

Definition

Delaunay triangulation divides a set of planar points into non-overlapping triangles such that no input point lies strictly inside any triangle's circumcircle. A circumcircle passes through a triangle's three vertices. The construction connects the supplied points and covers their convex hull, subject to geometric degeneracies and the numerical behavior of the implementation.

What it means

The method provides a principled way to connect scattered locations into a mesh. It often avoids unnecessarily thin triangles compared with alternative triangulations of the same points, but it does not guarantee well-shaped triangles when the input geometry itself is unfavorable. The empty-circle condition concerns every input point, including points that are not vertices of the triangle being checked. Points on the circle require care: when four points share a circle, more than one valid triangulation may exist. Consequently, valid software implementations need not always return identical diagonals.

How it works

Algorithms construct and adjust connections while satisfying the geometric condition, using operations such as inserting points and replacing unsuitable edges. Implementations must handle orientation tests, nearly coincident coordinates and other numerical difficulties. In ordinary two-dimensional use, the output contains triangles and their relationships. Higher-dimensional Delaunay constructions use simplices, such as tetrahedra in three dimensions. Constraints, holes and desired object boundaries require additional treatment: an unconstrained triangulation of locations does not infer which edges represent a real physical boundary. Check the chosen library's treatment of omitted or degenerate input points.

Three practical examples

A mapping team connects surveyed locations into triangles for an interpolation surface, while separately defining the surveyed region's boundary and handling gaps.
An image-warping tool triangulates matched landmarks so each triangle can support a local mapping between corresponding images.
A researcher creates a mesh from scattered measurements and inspects thin triangles near nearly collinear points before using it in subsequent calculations.

Think of it this way

Imagine stretching a circular hoop through three pegs on a board. A proposed triangle passes the test only if no other peg sits strictly inside that hoop. This is a geometric test, not a physical algorithm, and a peg exactly on the hoop does not violate the strict interior condition. Repeating the idea across the mesh explains why adding a new point can require changes to neighboring connections. It also explains why several arrangements can be equally valid for special point configurations.

Worked example

In an original example, a triangle has vertices (0,0), (4,0) and (0,3). Its circumcenter is (2,1.5), and its circumradius is 2.5 because the squared distance to each vertex is 6.25. Suppose the input set also contains point (1,1). Its squared distance to the circumcenter is 1.25, which is less than 6.25. It lies inside the circumcircle, so the original triangle cannot be a triangle of a Delaunay triangulation of the complete set. This calculation rejects one candidate; it does not by itself construct the entire triangulation or specify how numerical tolerances should be chosen.

Illustrative case study

A fictional heritage team builds a surface from measured points around a courtyard containing a fountain. Its first unconstrained mesh spans the fountain's unmeasured interior because the triangulation covers the point set's convex hull. The team adds an explicit boundary and appropriate constraints rather than assuming that an empty area in the measurements will automatically remain a hole. It then checks mesh geometry and interpolation behavior near the fountain edge. This scenario illustrates the difference between connecting points and representing a physical domain. It does not claim that every triangulation library supports the same boundary or constraint features.

Common misconceptions and mistakes

Delaunay triangulation is not a method for recognizing object outlines. It does not automatically preserve holes, coastlines or a particular set of supplied edges. Another mistake is expecting uniqueness for cocircular points or stable topology when coordinates are changed slightly near a degeneracy. Thin triangles can still arise from unfavorable point placement. Duplicate and nearly collinear points need deliberate handling. Finally, a visually reasonable triangulation does not establish that interpolated values between its vertices are accurate or that the measurements themselves are reliable.

Business use

The construction supports mapping, visualization, image deformation and some simulation workflows. A business should validate the domain boundaries, coordinate units and measurement quality alongside the mesh. If the mesh feeds decisions about distances or surfaces, check how missing regions and outliers affect the result. Preserve enough information to reproduce the triangulation, including relevant options and point preprocessing. Different valid triangulations of a degenerate configuration can change a downstream piecewise interpolation, so reproducibility requirements should cover more than simply retaining the input point count.

Check your understanding

Why did the candidate triangle fail in the example?

Answer: Another input point was strictly inside its circumcircle.

Would a point exactly on the circle violate that strict condition?

Answer: No, although it can create a non-unique choice.

Why might a courtyard mesh cover a fountain?

Answer: The physical hole was not represented by domain constraints.

Related terms

Convex hull
Barycentric coordinates
Voronoi diagram
triangulated irregular network
constrained triangulation
mesh generation

Learn next

Draw four cocircular points and compare the two possible diagonals. Then add an interior point and inspect which triangles change. Study constrained triangulation before applying an unconstrained point mesh to a domain containing holes or required edges.

Sources

SciPy, scipy.spatial.Delaunay reference: https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.Delaunay.html The coordinate calculation, hoop analogy and heritage-team case are original educational illustrations. Library-specific precision and degeneracy handling should be checked for the implementation used.

Previous: Degrees-of-freedom ladder Next: Delete list