GNU Octave Manual Version 3by John W. Eaton, David Bateman, Søren Hauberg Paperback (6"x9"), 568 pages ISBN 095461206X RRP £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*");

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"`

. - 2D and 3D:

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 |