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.