MATLAB Function Reference

delaunayn - N-D Delaunay tessellation

Syntax

T = delaunayn(X) T = delaunayn(X, options)

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-dimensional space. T is a numt-by-(n+1) array where each row contains the indices into X of the vertices of the corresponding simplex.

delaunayn uses Qhull.

T = delaunayn(X, options) specifies a cell array of strings options to be used as options in Qhull. The default options are:

{'Qt','Qbb','Qc'} for 2- and 3-dimensional input
{'Qt','Qbb','Qc','Qx'} for 4 and higher-dimensional input

If options is [], the default options 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.

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 in the MATLAB^® documentation.
You cannot plot delaunayn output for n > 3.

Examples

Example 1

This example generates an n-dimensional 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)

Example 2

The following example illustrates the options input for delaunayn.

X = [-0.5 -0.5  -0.5;...
            -0.5 -0.5   0.5;...
            -0.5  0.5  -0.5;...
            -0.5  0.5   0.5;...
             0.5 -0.5  -0.5;...
             0.5 -0.5   0.5;...
             0.5  0.5  -0.5;...
             0.5  0.5   0.5];

The command

T = delaunayn(X);

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.

This suggests that you add 'Qz' to the default options.

T = delaunayn(X,{'Qt','Qbb','Qc','Qz'});

To visualize this answer you can use the tetramesh function:

tetramesh(T,X)

Algorithm

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

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.

delaunay3

delete