- publishing free software manuals
 GNU Octave Manual Version 3 by John W. Eaton, David Bateman, Søren HaubergPaperback (6"x9"), 568 pagesISBN 095461206XRRP £24.95 (\$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*");
```

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.

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*");
```
 ISBN 095461206X GNU Octave Manual Version 3 See the print edition