MATLAB Function Reference
delaunay

Delaunay triangulation

Syntax

• ```TRI = delaunay(x,y)
```

Definition

Given a set of data points, the Delaunay triangulation is a set of lines connecting each point to its natural neighbors. The Delaunay triangulation is related to the Voronoi diagram-- the circle circumscribed about a Delaunay triangle has its center at the vertex of a Voronoi polygon.

Description

```TRI = delaunay(x,y) ``` for the data points defined by vectors `x` and `y`, returns a set of triangles such that no data points are contained in any triangle's circumscribed circle. Each row of the `m`-by-3 matrix `TRI` defines one such triangle and contains indices into `x` and `y`. If the original data points are collinear or `x` is empty, the triangles cannot be computed and `delaunay` returns an empty matrix.

Remarks

The Delaunay triangulation is used by: `griddata` (to interpolate scattered data), `voronoi` (to compute the `voronoi` diagram), and is useful by itself to create a triangular grid for scattered data points.

The functions `dsearch` and `tsearch` search the triangulation to find nearest neighbor points or enclosing triangles, respectively.

Visualization

Use one of these functions to plot the output of `delaunay`:

 `triplot` Displays the triangles defined in the `m`-by-3 matrix `TRI`. See Example 1. `trisurf` Displays each triangle defined in the `m`-by-3 matrix `TRI` as a surface in 3-D space. To see a 2-D surface, you can supply a vector of some constant value for the third dimension. For example```trisurf(TRI,x,y,zeros(size(x))) ``` See Example 2. `trimesh` Displays each triangle defined in the `m`-by-3 matrix `TRI` as a mesh in 3-D space. To see a 2-D surface, you can supply a vector of some constant value for the third dimension. For example,```trimesh(TRI,x,y,zeros(size(x))) ``` produces almost the same result as `triplot`, except in 3-D space. See Example 2.

Examples

Example 1. Plot the Delaunay triangulation for 10 randomly generated points.

• ```rand('state',0);
x = rand(1,10);
y = rand(1,10);
TRI = delaunay(x,y);
subplot(1,2,1),...
triplot(TRI,x,y)
axis([0 1 0 1]);
hold on;
plot(x,y,'or');
hold off
```

Compare the Voronoi diagram of the same points:

• ```[vx, vy] = voronoi(x,y,TRI);
subplot(1,2,2),...
plot(x,y,'r+',vx,vy,'b-'),...
axis([0 1 0 1])

```

Example 2. Create a 2-D grid then use `trisurf` to plot its Delaunay triangulation in 3-D space by using `0`s for the third dimension.

• ```[x,y] = meshgrid(1:15,1:15);
tri = delaunay(x,y);
trisurf(tri,x,y,zeros(size(x)))

```

Next, generate `peaks` data as a 15-by-15 matrix, and use that data with the Delaunay triangulation to produce a surface in 3-D space.

• ```z = peaks(15);
trisurf(tri,x,y,z)

```

You can use the same data with `trimesh` to produce a mesh in 3-D space.

• ```trimesh(tri,x,y,z)

```

Algorithm

`delaunay` is based on Qhull . It uses the Qhull joggle option (`'QJ'`). For information about `qhull`, see http://www.geom.umn.edu/software/qhull/. For copyright information, see http://www.geom.umn.edu/software/download/COPYING.html.

`delaunay3`, `delaunayn`, `dsearch`, `griddata`, `plot`, `triplot`, `trimesh`, `trisurf`, `tsearch`, `voronoi`