<!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 (version 5.1.0))</title> <meta name="description" content="Delaunay Triangulation (GNU Octave (version 5.1.0))"> <meta name="keywords" content="Delaunay Triangulation (GNU Octave (version 5.1.0))"> <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> [<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>(…, <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>An optional final 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> <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, "r*"); 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>{"Qt", "Qbb", "Qc", "Qz"}</code> </li><li> 4-D and higher: <var>options</var> = <code>{"Qt", "Qbb", "Qc", "Qx"}</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 ("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></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">• <a href="Plotting-the-Triangulation.html#Plotting-the-Triangulation" accesskey="1">Plotting the Triangulation</a>:</td><td> </td><td align="left" valign="top"> </td></tr> <tr><td align="left" valign="top">• <a href="Identifying-Points-in-Triangulation.html#Identifying-Points-in-Triangulation" accesskey="2">Identifying Points in Triangulation</a>:</td><td> </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> [<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>