GNU Octave Manual Version 3 by John W. Eaton, David Bateman, Søren Hauberg Paperback (6"x9"), 568 pages ISBN 095461206X RRP £24.95 ($39.95) Get a printed copy>>>

GNU Octave Manual Version 3 Buy the book here >>> $39.95

28.1 Delaunay Triangulation

The Delaunay triangulation of a set of points is constructed from a set of circum-circles. These are circles which are chosen so that at least three points in the set lie on each circumference and no point in the set falls inside any circum-circle.

In general there are only three points on the circumference of any circum-circle. However, in the some cases, and in particular for the case of a regular grid, 4 or more points can be on a single circum-circle. In this case the Delaunay triangulation is not unique.

Function File: tri= delaunay (x, y)

Function File: tri= delaunay (x, y, opt)

The return matrix of size [n, 3] contains a set triangles which are described by the indices to the data point x and y vector. The triangulation satisfies the Delaunay circumcircle criterion. No other data point is in the circumcircle of the defining triangle.

A third optional argument, which must be a string, contains extra options passed to the underlying qhull command. See the documentation for the Qhull library for details.

x = rand (1, 10);
y = rand (size (x));
T = delaunay (x, y);
X = [x(T(:,1)); x(T(:,2)); x(T(:,3)); x(T(:,1))];
Y = [y(T(:,1)); y(T(:,2)); y(T(:,3)); y(T(:,1))];
axis ([0,1,0,1]);
plot (X, Y, "b", x, y, "r*");

See also voronoi, delaunay3, delaunayn

The 3- and N-dimensional extension of the Delaunay triangulation are given by delaunay3 and delaunayn respectively. delaunay3 returns a set of tetrahedra that satisfy the Delaunay circum-circle criteria. Similarly, delaunayn returns the N-dimensional simplex satisfying the Delaunay circum-circle criteria. The N-dimensional extension of a triangulation is called a tessellation.

Function File: T = delaunay3 (x, y, z)

Function File: T = delaunay3 (x, y, z, opt)

A matrix of size [n, 4] is returned. Each row contains a set of tetrahedron which are described by the indices to the data point vectors (x,y,z).

A fourth optional argument, which must be a string or cell array of strings, contains extra options passed to the underlying qhull command. See the documentation for the Qhull library for details.

See also delaunay,delaunayn

Function File: T = delaunayn (P)

Function File: T = delaunayn (P, opt)

Form the Delaunay triangulation for a set of points. The Delaunay triangulation is a tessellation of the convex hull of the points such that no n-sphere defined by the n-triangles contains any other points from the set. The input matrix P of size [n, dim] contains n points in a space of dimension dim. The return matrix T has the size [m, dim+1]. It contains for each row a set of indices to the points, which describes a simplex of dimension dim. For example, a 2d simplex is a triangle and 3d simplex is a tetrahedron.

Extra options for the underlying Qhull command can be specified by the second argument. This argument is a cell array of strings. The default options depend on the dimension of the input:

• 2D and 3D: opt = {"Qt", "Qbb", "Qc"}
• 4D and higher: opt = {"Qt", "Qbb", "Qc", "Qz"}

If opt is [], then the default arguments are used. If opt is {""}, then none of the default arguments are used by Qhull. See the Qhull documentation for the available options.

All options can also be specified as single string, for example "Qt Qbb Qc Qz".

An example of a Delaunay triangulation of a set of points is

rand ("state", 2);
x = rand (10, 1);
y = rand (10, 1);
T = delaunay (x, y);
X = [ x(T(:,1)); x(T(:,2)); x(T(:,3)); x(T(:,1)) ];
Y = [ y(T(:,1)); y(T(:,2)); y(T(:,3)); y(T(:,1)) ];
axis ([0, 1, 0, 1]);
plot(X, Y, "b", x, y, "r*");