delaunay (MATLAB Function Reference)

Delaunay triangulation

Syntax

TRI = delaunay(x,y)

TRI = delaunay(x,y,'sorted')

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)

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 the vectors x and y.

To avoid the degeneracy of collinear data, delaunay adds some random fuzz to the data. The default fuzz standard deviation 4*sqrt(eps) has been chosen to maintain about seven digits of accuracy in the data.

tri = delaunay(x,y,fuzz)

uses the specified value for the fuzz standard deviation. It is possible that no value of fuzz produces a correct triangulation. In this unlikely situation, you need to preprocess your data to avoid collinear or nearly collinear data.

TRI = delaunay(x,y,'sorted')

assumes that the points x and y are sorted first by y and then by x and that duplicate points have already been eliminated.

Remarks

The Delaunay triangulation is used with: griddata (to interpolate scattered data), convhull, 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.

Examples

This code plots 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),...
trimesh(TRI,x,y,zeros(size(x))); view(2),...
axis([0 1 0 1]); hold on; 
plot(x,y,'o');
set(gca,'box','on');

Compare the Voronoi diagram of the same points:

[vx, vy] = voronoi(x,y,TRI);
subplot(1,2,2),...
plot(x,y,'r+',vx,vy,'b-'),...
axis([0 1 0 1])