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.

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

specifies a cell array of strings `options`

to be used in Qhull via `delaunayn`

. The default options are `{'Qt','Qbb','Qc'}`

.

If `options`

is `[]`

, the default options are used. If `options`

is `{''}`

, no options are used, not even the default. For more information on Qhull and its options, see http://www.qhull.org.

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

**Example 3.** The following example illustrates the `options`

input for `delaunay`

.

returns the following error message.

??? qhull input error: can not scale last coordinate. Input is cocircular or cospherical. Use option 'Qz' to add a point at infinity.

The error message indicates that you should add `'Qz'`

to the default Qhull options.

**Algorithm**

`delaunay`

is based on Qhull. For information about Qhull, see http://www.qhull.org/. For copyright information, see http://www.qhull.org/COPYING.txt.

**See Also**

`delaunay3`

, `delaunay`

, `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 PDF format at http://www.acm.org/pubs/
citations/journals/toms/1996-22-4/p469-barber/.

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

del2 | delaunay3 |

© 1994-2005 The MathWorks, Inc.