delaunayn (MATLAB Functions)

n-D Delaunay tessellation

Syntax

```
T = delaunayn(X)
```

Description

T = delaunayn(X) computes a set of simplices such that no data points of X are contained in any circumspheres of the simplices. The set of simplices forms the Delaunay tessellation. X is an m-by-n array representing m points in n-D space. T is a numt-by-(n+1) array where each row contains the indices into X of the vertices of the corresponding simplex.

Visualization

Plotting the output of delaunayn depends of the value of n:

For n = 2, use triplot, trisurf, or trimesh as you would for delaunay.
For n = 3, use tetramesh as you would for delaunay3.

For more control over the color of the facets, use patch to plot the output. For an example, see Tessellation and Interpolation of Scattered Data in Higher Dimensions in the MATLAB documentation.

You cannot plot delaunayn output for n > 3.

Example

This example generates an n-D Delaunay tessellation, where n = 3.

d = [-1 1];
[x,y,z] = meshgrid(d,d,d);  % A cube
x = [x(:);0];
y = [y(:);0];
z = [z(:);0];
% [x,y,z] are corners of a cube plus the center.
X = [x(:) y(:) z(:)];
Tes = delaunayn(X)

Tes =
   9  1  5  6
   3  9  1  5
   2  9  1  6
   2  3  9  4
   2  3  9  1
   7  9  5  6
   7  3  9  5
   8  7  9  6
   8  2  9  6
   8  2  9  4
   8  3  9  4
   8  7  3  9

You can use tetramesh to visualize the tetrahedrons that form the corresponding simplex. camorbit rotates the camera position to provide a meaningful view of the figure.

```
tetramesh(Tes,X);camorbit(20,0)
```

Algorithm

delaunayn is based on Qhull [2],. 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.

Reference

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

delaunay3 delete