/usr/share/doc/octave/octave.html/Delaunay-Triangulation.html

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Created by GNU Texinfo 6.5, http://www.gnu.org/software/texinfo/ -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Delaunay Triangulation (GNU Octave)</title>

<meta name="description" content="Delaunay Triangulation (GNU Octave)">
<meta name="keywords" content="Delaunay Triangulation (GNU Octave)">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<link href="index.html#Top" rel="start" title="Top">
<link href="Concept-Index.html#Concept-Index" rel="index" title="Concept Index">
<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
<link href="Geometry.html#Geometry" rel="up" title="Geometry">
<link href="Plotting-the-Triangulation.html#Plotting-the-Triangulation" rel="next" title="Plotting the Triangulation">
<link href="Geometry.html#Geometry" rel="prev" title="Geometry">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.indentedblock {margin-right: 0em}
blockquote.smallindentedblock {margin-right: 0em; font-size: smaller}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smalllisp {margin-left: 3.2em}
kbd {font-style: oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nolinebreak {white-space: nowrap}
span.roman {font-family: initial; font-weight: normal}
span.sansserif {font-family: sans-serif; font-weight: normal}
ul.no-bullet {list-style: none}
-->
</style>
<link rel="stylesheet" type="text/css" href="octave.css">


</head>

<body lang="en">
<a name="Delaunay-Triangulation"></a>
<div class="header">
<p>
Next: <a href="Voronoi-Diagrams.html#Voronoi-Diagrams" accesskey="n" rel="next">Voronoi Diagrams</a>, Up: <a href="Geometry.html#Geometry" accesskey="u" rel="up">Geometry</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Concept-Index.html#Concept-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Delaunay-Triangulation-1"></a>
<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>
<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.
</p>
<a name="XREFdelaunay"></a><dl>
<dt><a name="index-delaunay"></a>: <em><var>tri</var> =</em> <strong>delaunay</strong> <em>(<var>x</var>, <var>y</var>)</em></dt>
<dt><a name="index-delaunay-1"></a>: <em><var>tetr</var> =</em> <strong>delaunay</strong> <em>(<var>x</var>, <var>y</var>, <var>z</var>)</em></dt>
<dt><a name="index-delaunay-2"></a>: <em><var>tri</var> =</em> <strong>delaunay</strong> <em>(<var>x</var>)</em></dt>
<dt><a name="index-delaunay-3"></a>: <em><var>tri</var> =</em> <strong>delaunay</strong> <em>(&hellip;, <var>options</var>)</em></dt>
<dd><p>Compute the Delaunay triangulation for a 2-D or 3-D set of points.
</p>
<p>For 2-D sets, the return value <var>tri</var> is a set of triangles which
satisfies the Delaunay circum-circle criterion, i.e., no data point from
[<var>x</var>, <var>y</var>] is within the circum-circle of the defining triangle.
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 <code><var>tri</var>(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>
<p>For 3-D sets, the return value <var>tetr</var> is a set of tetrahedrons which
satisfies the Delaunay circum-circle criterion, i.e., no data point from
[<var>x</var>, <var>y</var>, <var>z</var>] is within the circum-circle of the defining
tetrahedron.  The set of tetrahedrons 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 <code><var>tetr</var>(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>
<p>The input <var>x</var> may also be a matrix with two or three columns where the
first column contains x-data, the second y-data, and the optional third
column contains z-data.
</p>
<p>The optional last 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>{&quot;Qt&quot;, &quot;Qbb&quot;, &quot;Qc&quot;, &quot;Qz&quot;}</code>.
</p>
<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>
<div class="example">
<pre class="example">x = rand (1, 10);
y = rand (1, 10);
tri = delaunay (x, y);
triplot (tri, x, y);
hold on;
plot (x, y, &quot;r*&quot;);
axis ([0,1,0,1]);
</pre></div>

<p><strong>See also:</strong> <a href="#XREFdelaunayn">delaunayn</a>, <a href="Convex-Hull.html#XREFconvhull">convhull</a>, <a href="Voronoi-Diagrams.html#XREFvoronoi">voronoi</a>, <a href="Plotting-the-Triangulation.html#XREFtriplot">triplot</a>, <a href="Plotting-the-Triangulation.html#XREFtrimesh">trimesh</a>, <a href="Plotting-the-Triangulation.html#XREFtetramesh">tetramesh</a>, <a href="Plotting-the-Triangulation.html#XREFtrisurf">trisurf</a>.
</p></dd></dl>


<p>For 3-D inputs <code>delaunay</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.
</p>
<a name="XREFdelaunayn"></a><dl>
<dt><a name="index-delaunayn"></a>: <em><var>T</var> =</em> <strong>delaunayn</strong> <em>(<var>pts</var>)</em></dt>
<dt><a name="index-delaunayn-1"></a>: <em><var>T</var> =</em> <strong>delaunayn</strong> <em>(<var>pts</var>, <var>options</var>)</em></dt>
<dd><p>Compute the Delaunay triangulation for an N-dimensional set of points.
</p>
<p>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>
<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>
<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:
</p>
<ul>
<li> 2-D and 3-D: <var>options</var> = <code>{&quot;Qt&quot;, &quot;Qbb&quot;, &quot;Qc&quot;, &quot;Qz&quot;}</code>

</li><li> 4-D and higher: <var>options</var> = <code>{&quot;Qt&quot;, &quot;Qbb&quot;, &quot;Qc&quot;, &quot;Qx&quot;}</code>
</li></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.
</p>

<p><strong>See also:</strong> <a href="#XREFdelaunay">delaunay</a>, <a href="Convex-Hull.html#XREFconvhulln">convhulln</a>, <a href="Voronoi-Diagrams.html#XREFvoronoin">voronoin</a>, <a href="Plotting-the-Triangulation.html#XREFtrimesh">trimesh</a>, <a href="Plotting-the-Triangulation.html#XREFtetramesh">tetramesh</a>.
</p></dd></dl>


<p>An example of a Delaunay triangulation of a set of points is
</p>
<div class="example">
<pre class="example">rand (&quot;state&quot;, 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, &quot;b&quot;, x, y, &quot;r*&quot;);
</pre></div>

<p>The result of which can be seen in <a href="#fig_003adelaunay">Figure 30.1</a>.
</p>
<div class="float"><a name="fig_003adelaunay"></a>
<div align="center"><img src="delaunay.png" alt="delaunay">
</div>
<div class="float-caption"><p><strong>Figure 30.1: </strong>Delaunay triangulation of a random set of points</p></div></div>
<table class="menu" border="0" cellspacing="0">
<tr><td align="left" valign="top">&bull; <a href="Plotting-the-Triangulation.html#Plotting-the-Triangulation" accesskey="1">Plotting the Triangulation</a>:</td><td>&nbsp;&nbsp;</td><td align="left" valign="top">
</td></tr>
<tr><td align="left" valign="top">&bull; <a href="Identifying-Points-in-Triangulation.html#Identifying-Points-in-Triangulation" accesskey="2">Identifying Points in Triangulation</a>:</td><td>&nbsp;&nbsp;</td><td align="left" valign="top">
</td></tr>
</table>

<hr>
<div class="header">
<p>
Next: <a href="Voronoi-Diagrams.html#Voronoi-Diagrams" accesskey="n" rel="next">Voronoi Diagrams</a>, Up: <a href="Geometry.html#Geometry" accesskey="u" rel="up">Geometry</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Concept-Index.html#Concept-Index" title="Index" rel="index">Index</a>]</p>
</div>



</body>
</html>
octave-doc 4.2.2-1ubuntu1 / usr / share / doc / octave / octave.html / Delaunay-Triangulation.html
