<html lang="en">
<head>
<title>Delaunay Triangulation - GNU Octave</title>
<meta http-equiv="Content-Type" content="text/html">
<meta name="description" content="GNU Octave">
<meta name="generator" content="makeinfo 4.13">
<link title="Top" rel="start" href="index.html#Top">
<link rel="up" href="Geometry.html#Geometry" title="Geometry">
<link rel="next" href="Voronoi-Diagrams.html#Voronoi-Diagrams" title="Voronoi Diagrams">
<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
<meta http-equiv="Content-Style-Type" content="text/css">
<style type="text/css"><!--
pre.display { font-family:inherit }
pre.format { font-family:inherit }
pre.smalldisplay { font-family:inherit; font-size:smaller }
pre.smallformat { font-family:inherit; font-size:smaller }
pre.smallexample { font-size:smaller }
pre.smalllisp { font-size:smaller }
span.sc { font-variant:small-caps }
span.roman { font-family:serif; font-weight:normal; }
span.sansserif { font-family:sans-serif; font-weight:normal; }
--></style>
</head>
<body>
<div class="node">
<a name="Delaunay-Triangulation"></a>
<p>
Next: <a rel="next" accesskey="n" href="Voronoi-Diagrams.html#Voronoi-Diagrams">Voronoi Diagrams</a>,
Up: <a rel="up" accesskey="u" href="Geometry.html#Geometry">Geometry</a>
<hr>
</div>
<h3 class="section">30.1 Delaunay Triangulation</h3>
<p>The Delaunay triangulation is constructed from a set of
circum-circles. These circum-circles are chosen so that there are at
least three of the points in the set to triangulation on the
circumference of the circum-circle. None of the points in the set of
points falls within any of the circum-circles.
<p>In general there are only three points on the circumference of any
circum-circle. However, in 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.
<!-- delaunay scripts/geometry/delaunay.m -->
<p><a name="doc_002ddelaunay"></a>
<div class="defun">
— Function File: <b>delaunay</b> (<var>x, y</var>)<var><a name="index-delaunay-2775"></a></var><br>
— Function File: <var>tri</var> = <b>delaunay</b> (<var>x, y</var>)<var><a name="index-delaunay-2776"></a></var><br>
— Function File: <var>tri</var> = <b>delaunay</b> (<var>x, y, options</var>)<var><a name="index-delaunay-2777"></a></var><br>
<blockquote><p>Compute the Delaunay triangulation for a 2-D set of points.
The return value <var>tri</var> is a set of triangles which satisfies the
Delaunay circum-circle criterion, i.e., only a single data point from
[<var>x</var>, <var>y</var>] is within the circum-circle of the defining triangle.
<p>The set of triangles <var>tri</var> is a matrix of size [n, 3]. Each
row defines a triangle and the three columns are the three vertices
of the triangle. The value of <var>tri</var><code>(i,j)</code> is an index into
<var>x</var> and <var>y</var> for the location of the j-th vertex of the i-th
triangle.
<p>An optional third argument, which must be a string or cell array of strings,
contains options passed to the underlying qhull command.
See the documentation for the Qhull library for details
<a href="http://www.qhull.org/html/qh-quick.htm#options">http://www.qhull.org/html/qh-quick.htm#options</a>.
The default options are <code>{"Qt", "Qbb", "Qc", "Qz"}</code>.
<p>If <var>options</var> is not present or <code>[]</code> then the default arguments are
used. Otherwise, <var>options</var> replaces the default argument list.
To append user options to the defaults it is necessary to repeat the
default arguments in <var>options</var>. Use a null string to pass no arguments.
<p>If no output argument is specified the resulting Delaunay triangulation
is plotted along with the original set of points.
<pre class="example"> x = rand (1, 10);
y = rand (1, 10);
T = delaunay (x, y);
VX = [ x(T(:,1)); x(T(:,2)); x(T(:,3)); x(T(:,1)) ];
VY = [ y(T(:,1)); y(T(:,2)); y(T(:,3)); y(T(:,1)) ];
axis ([0,1,0,1]);
plot (VX, VY, "b", x, y, "r*");
</pre>
<!-- Texinfo @sp should work but in practice produces ugly results for HTML. -->
<!-- A simple blank line produces the correct behavior. -->
<!-- @sp 1 -->
<p class="noindent"><strong>See also:</strong> <a href="doc_002ddelaunay3.html#doc_002ddelaunay3">delaunay3</a>, <a href="doc_002ddelaunayn.html#doc_002ddelaunayn">delaunayn</a>, <a href="doc_002dconvhull.html#doc_002dconvhull">convhull</a>, <a href="doc_002dvoronoi.html#doc_002dvoronoi">voronoi</a>.
</p></blockquote></div>
<p>The 3- and N-dimensional extension of the Delaunay triangulation are
given by <code>delaunay3</code> and <code>delaunayn</code> respectively.
<code>delaunay3</code> returns a set of tetrahedra that satisfy the
Delaunay circum-circle criteria. Similarly, <code>delaunayn</code> returns the
N-dimensional simplex satisfying the Delaunay circum-circle criteria.
The N-dimensional extension of a triangulation is called a tessellation.
<!-- delaunay3 scripts/geometry/delaunay3.m -->
<p><a name="doc_002ddelaunay3"></a>
<div class="defun">
— Function File: <var>tetr</var> = <b>delaunay3</b> (<var>x, y, z</var>)<var><a name="index-delaunay3-2778"></a></var><br>
— Function File: <var>tetr</var> = <b>delaunay3</b> (<var>x, y, z, options</var>)<var><a name="index-delaunay3-2779"></a></var><br>
<blockquote><p>Compute the Delaunay triangulation for a 3-D set of points.
The return value <var>tetr</var> is a set of tetrahedrons which satisfies the
Delaunay circum-circle criterion, i.e., only a single data point from
[<var>x</var>, <var>y</var>, <var>z</var>] is within the circum-circle of the defining
tetrahedron.
<p>The set of tetrahedrons <var>tetr</var> is a matrix of size [n, 4]. Each
row defines a tetrahedron and the four columns are the four vertices
of the tetrahedron. The value of <var>tetr</var><code>(i,j)</code> is an index into
<var>x</var>, <var>y</var>, <var>z</var> for the location of the j-th vertex of the i-th
tetrahedron.
<p>An optional fourth argument, which must be a string or cell array of strings,
contains options passed to the underlying qhull command.
See the documentation for the Qhull library for details
<a href="http://www.qhull.org/html/qh-quick.htm#options">http://www.qhull.org/html/qh-quick.htm#options</a>.
The default options are <code>{"Qt", "Qbb", "Qc", "Qz"}</code>.
<p>If <var>options</var> is not present or <code>[]</code> then the default arguments are
used. Otherwise, <var>options</var> replaces the default argument list.
To append user options to the defaults it is necessary to repeat the
default arguments in <var>options</var>. Use a null string to pass no arguments.
<!-- Texinfo @sp should work but in practice produces ugly results for HTML. -->
<!-- A simple blank line produces the correct behavior. -->
<!-- @sp 1 -->
<p class="noindent"><strong>See also:</strong> <a href="doc_002ddelaunay.html#doc_002ddelaunay">delaunay</a>, <a href="doc_002ddelaunayn.html#doc_002ddelaunayn">delaunayn</a>, <a href="doc_002dconvhull.html#doc_002dconvhull">convhull</a>, <a href="doc_002dvoronoi.html#doc_002dvoronoi">voronoi</a>.
</p></blockquote></div>
<!-- delaunayn scripts/geometry/delaunayn.m -->
<p><a name="doc_002ddelaunayn"></a>
<div class="defun">
— Function File: <var>T</var> = <b>delaunayn</b> (<var>pts</var>)<var><a name="index-delaunayn-2780"></a></var><br>
— Function File: <var>T</var> = <b>delaunayn</b> (<var>pts, options</var>)<var><a name="index-delaunayn-2781"></a></var><br>
<blockquote><p>Compute the Delaunay triangulation for an N-dimensional set of points.
The Delaunay triangulation is a tessellation of the convex hull of a set
of points such that no N-sphere defined by the N-triangles contains
any other points from the set.
<p>The input matrix <var>pts</var> of size [n, dim] contains n points in a space of
dimension dim. The return matrix <var>T</var> has size [m, dim+1]. Each row
of <var>T</var> contains a set of indices back into the original set of points
<var>pts</var> which describes a simplex of dimension dim. For example, a 2-D
simplex is a triangle and 3-D simplex is a tetrahedron.
<p>An optional second argument, which must be a string or cell array of strings,
contains options passed to the underlying qhull command.
See the documentation for the Qhull library for details
<a href="http://www.qhull.org/html/qh-quick.htm#options">http://www.qhull.org/html/qh-quick.htm#options</a>.
The default options depend on the dimension of the input:
<ul>
<li>2-D and 3-D: <var>options</var> = <code>{"Qt", "Qbb", "Qc", "Qz"}</code>
<li>4-D and higher: <var>options</var> = <code>{"Qt", "Qbb", "Qc", "Qx"}</code>
</ul>
<p>If <var>options</var> is not present or <code>[]</code> then the default arguments are
used. Otherwise, <var>options</var> replaces the default argument list.
To append user options to the defaults it is necessary to repeat the
default arguments in <var>options</var>. Use a null string to pass no arguments.
<!-- Texinfo @sp should work but in practice produces ugly results for HTML. -->
<!-- A simple blank line produces the correct behavior. -->
<!-- @sp 1 -->
<p class="noindent"><strong>See also:</strong> <a href="doc_002ddelaunay.html#doc_002ddelaunay">delaunay</a>, <a href="doc_002ddelaunay3.html#doc_002ddelaunay3">delaunay3</a>, <a href="doc_002dconvhulln.html#doc_002dconvhulln">convhulln</a>, <a href="doc_002dvoronoin.html#doc_002dvoronoin">voronoin</a>.
</p></blockquote></div>
<p>An example of a Delaunay triangulation of a set of points is
<pre class="example"> 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*");
</pre>
<p class="noindent">The result of which can be seen in <a href="fig_003adelaunay.html#fig_003adelaunay">fig:delaunay</a>.
<div class="float">
<a name="fig_003adelaunay"></a><div align="center"><img src="delaunay.png" alt="delaunay.png"></div>
<p><strong class="float-caption">Figure 30.1: Delaunay triangulation of a random set of points</strong></p></div>
<ul class="menu">
<li><a accesskey="1" href="Plotting-the-Triangulation.html#Plotting-the-Triangulation">Plotting the Triangulation</a>
<li><a accesskey="2" href="Identifying-Points-in-Triangulation.html#Identifying-Points-in-Triangulation">Identifying Points in Triangulation</a>
</ul>
</body></html>
