3
<title>Delaunay Triangulation - Untitled</title>
4
<meta http-equiv="Content-Type" content="text/html">
5
<meta name="description" content="Untitled">
6
<meta name="generator" content="makeinfo 4.11">
7
<link title="Top" rel="start" href="index.html#Top">
8
<link rel="up" href="Geometry.html#Geometry" title="Geometry">
9
<link rel="next" href="Voronoi-Diagrams.html#Voronoi-Diagrams" title="Voronoi Diagrams">
10
<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
11
<meta http-equiv="Content-Style-Type" content="text/css">
12
<style type="text/css"><!--
13
pre.display { font-family:inherit }
14
pre.format { font-family:inherit }
15
pre.smalldisplay { font-family:inherit; font-size:smaller }
16
pre.smallformat { font-family:inherit; font-size:smaller }
17
pre.smallexample { font-size:smaller }
18
pre.smalllisp { font-size:smaller }
19
span.sc { font-variant:small-caps }
20
span.roman { font-family:serif; font-weight:normal; }
21
span.sansserif { font-family:sans-serif; font-weight:normal; }
27
<a name="Delaunay-Triangulation"></a>
28
Next: <a rel="next" accesskey="n" href="Voronoi-Diagrams.html#Voronoi-Diagrams">Voronoi Diagrams</a>,
29
Up: <a rel="up" accesskey="u" href="Geometry.html#Geometry">Geometry</a>
33
<h3 class="section">29.1 Delaunay Triangulation</h3>
35
<p>The Delaunay triangulation is constructed from a set of
36
circum-circles. These circum-circles are chosen so that there are at
37
least three of the points in the set to triangulation on the
38
circumference of the circum-circle. None of the points in the set of
39
points falls within any of the circum-circles.
41
<p>In general there are only three points on the circumference of any
42
circum-circle. However, in the some cases, and in particular for the
43
case of a regular grid, 4 or more points can be on a single
44
circum-circle. In this case the Delaunay triangulation is not unique.
46
<p><a name="doc_002ddelaunay"></a>
49
— Function File: <var>tri</var>= <b>delaunay</b> (<var>x, y</var>)<var><a name="index-delaunay-1632"></a></var><br>
50
— Function File: <var>tri</var>= <b>delaunay</b> (<var>x, y, opt</var>)<var><a name="index-delaunay-1633"></a></var><br>
51
<blockquote><p>The return matrix of size [n, 3] contains a set triangles which are
52
described by the indices to the data point x and y vector.
53
The triangulation satisfies the Delaunay circumcircle criterion.
54
No other data point is in the circumcircle of the defining triangle.
56
<p>A third optional argument, which must be a string, contains extra options
57
passed to the underlying qhull command. See the documentation for the
58
Qhull library for details.
60
<pre class="example"> x = rand (1, 10);
63
X = [x(T(:,1)); x(T(:,2)); x(T(:,3)); x(T(:,1))];
64
Y = [y(T(:,1)); y(T(:,2)); y(T(:,3)); y(T(:,1))];
66
plot (X, Y, "b", x, y, "r*");
71
<strong>See also:</strong> voronoi, delaunay3, delaunayn.
72
</p></blockquote></div>
74
<p>The 3- and N-dimensional extension of the Delaunay triangulation are
75
given by <code>delaunay3</code> and <code>delaunayn</code> respectively.
76
<code>delaunay3</code> returns a set of tetrahedra that satisfy the
77
Delaunay circum-circle criteria. Similarly, <code>delaunayn</code> returns the
78
N-dimensional simplex satisfying the Delaunay circum-circle criteria.
79
The N-dimensional extension of a triangulation is called a tessellation.
81
<p><a name="doc_002ddelaunay3"></a>
84
— Function File: <var>T</var> = <b>delaunay3</b> (<var>x, y, z</var>)<var><a name="index-delaunay3-1634"></a></var><br>
85
— Function File: <var>T</var> = <b>delaunay3</b> (<var>x, y, z, opt</var>)<var><a name="index-delaunay3-1635"></a></var><br>
86
<blockquote><p>A matrix of size [n, 4] is returned. Each row contains a
87
set of tetrahedron which are
88
described by the indices to the data point vectors (x,y,z).
90
<p>A fourth optional argument, which must be a string or cell array of strings,
91
contains extra options passed to the underlying qhull command. See the
92
documentation for the Qhull library for details.
96
<strong>See also:</strong> delaunay,delaunayn.
97
</p></blockquote></div>
99
<p><a name="doc_002ddelaunayn"></a>
102
— Function File: <var>T</var> = <b>delaunayn</b> (<var>P</var>)<var><a name="index-delaunayn-1636"></a></var><br>
103
— Function File: <var>T</var> = <b>delaunayn</b> (<var>P, opt</var>)<var><a name="index-delaunayn-1637"></a></var><br>
104
<blockquote><p>Form the Delaunay triangulation for a set of points.
105
The Delaunay triangulation is a tessellation of the convex hull of the
106
points such that no n-sphere defined by the n-triangles contains
107
any other points from the set.
108
The input matrix <var>P</var> of size <code>[n, dim]</code> contains <var>n</var>
109
points in a space of dimension dim. The return matrix <var>T</var> has the
110
size <code>[m, dim+1]</code>. It contains for each row a set of indices to
111
the points, which describes a simplex of dimension dim. For example,
112
a 2d simplex is a triangle and 3d simplex is a tetrahedron.
114
<p>Extra options for the underlying Qhull command can be specified by the
115
second argument. This argument is a cell array of strings. The default
116
options depend on the dimension of the input:
119
<li>2D and 3D: <var>opt</var> = <code>{"Qt", "Qbb", "Qc"}</code>
120
<li>4D and higher: <var>opt</var> = <code>{"Qt", "Qbb", "Qc", "Qz"}</code>
123
<p>If <var>opt</var> is [], then the default arguments are used. If <var>opt</var>
124
is <code>{"<!-- /@w -->"}</code>, then none of the default arguments are used by Qhull.
125
See the Qhull documentation for the available options.
127
<p>All options can also be specified as single string, for example
128
<code>"Qt Qbb Qc Qz"</code>.
132
<p>An example of a Delaunay triangulation of a set of points is
134
<pre class="example"> rand ("state", 2);
138
X = [ x(T(:,1)); x(T(:,2)); x(T(:,3)); x(T(:,1)) ];
139
Y = [ y(T(:,1)); y(T(:,2)); y(T(:,3)); y(T(:,1)) ];
141
plot(X, Y, "b", x, y, "r*");
144
<li><a accesskey="1" href="Plotting-the-Triangulation.html#Plotting-the-Triangulation">Plotting the Triangulation</a>
145
<li><a accesskey="2" href="Identifying-points-in-Triangulation.html#Identifying-points-in-Triangulation">Identifying points in Triangulation</a>
added
removed
doc/interpreter/HTML/Delaunay-Triangulation.html
