MATLAB Function Reference |

**Syntax**

**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 exampleSee 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,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:

**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.

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.

You can use the same data with `trimesh`

to produce a mesh in 3-D space.

**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.

**See Also**

`delaunay3`

, `delaunayn`

, `dsearch`

, `griddata`

, `plot`

, `triplot`

, `trimesh`

, `trisurf`

, `tsearch`

, `voronoi`

**References**

[1] Barber, C. B., D.P. Dobkin, and H.T. Huhdanpaa, "The Quickhull Algorithm for
Convex Hulls," *ACM Transactions on Mathematical Software*, Vol. 22, No. 4,
Dec. 1996, p. 469-483. Available in HTML format at http://www.acm.org/
pubs/citations/journals/toms/1996-22-4/p469-barber/ and in PostScript
format at ftp://geom.umn.edu/pub/software/qhull-96.ps.

[2] National Science and Technology Research Center for Computation and Visualization of Geometric Structures (The Geometry Center), University of Minnesota. 1993.

del2 | delaunay3 |