`delaunay`

Delaunay triangulation of 2-D or 3-D points, as a matrix of triangle or tetrahedron indices.

Category: Mathematics > Computational Geometry

Syntax

T = delaunay(x, y)

Triangulates 2-D points given as column vectors.

T = delaunay(x, y, z)

Tetrahedral triangulation of 3-D points.

T = delaunay(P)

Points given as rows of a matrix with two or three columns.

Description

A Delaunay triangulation connects the points so that no point lies inside the circumcircle (circumsphere) of any triangle (tetrahedron). This avoids long thin triangles when possible and makes it a standard base for meshing and scattered-data interpolation.

The result is not unique for degenerate inputs, such as four points exactly on one circle. The order of rows and the starting vertex of each triangle can differ from MATLAB.

Input arguments

x, y, z: Coordinates of the points, as column vectors.
P: Matrix with one point per row.

Output arguments

T: Connectivity matrix: each row lists the point indices of one triangle (3 columns) or tetrahedron (4 columns).

Example

Triangulate a square with a center point

x = [0 1 1 0 0.5]';
y = [0 0 1 1 0.5]';
T = delaunay(x, y)
size(T)

Output

T = 4×3

     5     2     3
     1     2     5
     5     4     1
     3     4     5
ans = 1×2

     4     3

delaunay