1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
|
<html lang="en">
<head>
<title>Delaunay Triangulation - Untitled</title>
<meta http-equiv="Content-Type" content="text/html">
<meta name="description" content="Untitled">
<meta name="generator" content="makeinfo 4.11">
<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">
<p>
<a name="Delaunay-Triangulation"></a>
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">29.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.
<!-- ./geometry/delaunay.m -->
<p><a name="doc_002ddelaunay"></a>
<div class="defun">
— Function File: <var>tri</var> = <b>delaunay</b> (<var>x, y</var>)<var><a name="index-delaunay-2084"></a></var><br>
— Function File: <var>tri</var> = <b>delaunay</b> (<var>x, y, opt</var>)<var><a name="index-delaunay-2085"></a></var><br>
<blockquote><p>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 circum-circle criterion.
No other data point is in the circum-circle of the defining triangle.
<p>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.
<pre class="example"> 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*");
</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_002dvoronoi.html#doc_002dvoronoi">voronoi</a>, <a href="doc_002ddelaunay3.html#doc_002ddelaunay3">delaunay3</a>, <a href="doc_002ddelaunayn.html#doc_002ddelaunayn">delaunayn</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.
<!-- ./geometry/delaunay3.m -->
<p><a name="doc_002ddelaunay3"></a>
<div class="defun">
— Function File: <var>T</var> = <b>delaunay3</b> (<var>x, y, z</var>)<var><a name="index-delaunay3-2086"></a></var><br>
— Function File: <var>T</var> = <b>delaunay3</b> (<var>x, y, z, opt</var>)<var><a name="index-delaunay3-2087"></a></var><br>
<blockquote><p>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).
<p>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.
<!-- 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>.
</p></blockquote></div>
<!-- ./geometry/delaunayn.m -->
<p><a name="doc_002ddelaunayn"></a>
<div class="defun">
— Function File: <var>T</var> = <b>delaunayn</b> (<var>P</var>)<var><a name="index-delaunayn-2088"></a></var><br>
— Function File: <var>T</var> = <b>delaunayn</b> (<var>P, opt</var>)<var><a name="index-delaunayn-2089"></a></var><br>
<blockquote><p>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 <var>P</var> of size <code>[n, dim]</code> contains <var>n</var>
points in a space of dimension dim. The return matrix <var>T</var> has the
size <code>[m, dim+1]</code>. 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.
<p>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:
<ul>
<li>2D and 3D: <var>opt</var> = <code>{"Qt", "Qbb", "Qc"}</code>
<li>4D and higher: <var>opt</var> = <code>{"Qt", "Qbb", "Qc", "Qz"}</code>
</ul>
<p>If <var>opt</var> is [], then the default arguments are used. If <var>opt</var>
is <code>{"<!-- /@w -->"}</code>, then none of the default arguments are used by Qhull.
See the Qhull documentation for the available options.
<p>All options can also be specified as single string, for example
<code>"Qt Qbb Qc Qz"</code>.
</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>
<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>
|
