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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
|
<html lang="en">
<head>
<title>Voronoi Diagrams - 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="prev" href="Delaunay-Triangulation.html#Delaunay-Triangulation" title="Delaunay Triangulation">
<link rel="next" href="Convex-Hull.html#Convex-Hull" title="Convex Hull">
<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="Voronoi-Diagrams"></a>
Next: <a rel="next" accesskey="n" href="Convex-Hull.html#Convex-Hull">Convex Hull</a>,
Previous: <a rel="previous" accesskey="p" href="Delaunay-Triangulation.html#Delaunay-Triangulation">Delaunay Triangulation</a>,
Up: <a rel="up" accesskey="u" href="Geometry.html#Geometry">Geometry</a>
<hr>
</div>
<h3 class="section">29.2 Voronoi Diagrams</h3>
<p>A Voronoi diagram or Voronoi tessellation of a set of points <var>s</var> in
an N-dimensional space, is the tessellation of the N-dimensional space
such that all points in <var>v</var><code>(</code><var>p</var><code>)</code>, a partitions of the
tessellation where <var>p</var> is a member of <var>s</var>, are closer to <var>p</var>
than any other point in <var>s</var>. The Voronoi diagram is related to the
Delaunay triangulation of a set of points, in that the vertexes of the
Voronoi tessellation are the centers of the circum-circles of the
simplicies of the Delaunay tessellation.
<!-- ./geometry/voronoi.m -->
<p><a name="doc_002dvoronoi"></a>
<div class="defun">
— Function File: <b>voronoi</b> (<var>x, y</var>)<var><a name="index-voronoi-2103"></a></var><br>
— Function File: <b>voronoi</b> (<var>x, y, "plotstyle"</var>)<var><a name="index-voronoi-2104"></a></var><br>
— Function File: <b>voronoi</b> (<var>x, y, "plotstyle", options</var>)<var><a name="index-voronoi-2105"></a></var><br>
— Function File: [<var>vx</var>, <var>vy</var>] = <b>voronoi</b> (<var><small class="dots">...</small></var>)<var><a name="index-voronoi-2106"></a></var><br>
<blockquote><p>plots voronoi diagram of points <code>(</code><var>x</var><code>, </code><var>y</var><code>)</code>.
The voronoi facets with points at infinity are not drawn.
[<var>vx</var>, <var>vy</var>] = voronoi(<small class="dots">...</small>) returns the vertices instead of plotting the
diagram. plot (<var>vx</var>, <var>vy</var>) shows the voronoi diagram.
<p>A fourth 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 (10, 1);
y = rand (size (x));
h = convhull (x, y);
[vx, vy] = voronoi (x, y);
plot (vx, vy, "-b", x, y, "o", x(h), y(h), "-g")
legend ("", "points", "hull");
</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_002dvoronoin.html#doc_002dvoronoin">voronoin</a>, <a href="doc_002ddelaunay.html#doc_002ddelaunay">delaunay</a>, <a href="doc_002dconvhull.html#doc_002dconvhull">convhull</a>.
</p></blockquote></div>
<!-- ./geometry/voronoin.m -->
<p><a name="doc_002dvoronoin"></a>
<div class="defun">
— Function File: [<var>C</var>, <var>F</var>] = <b>voronoin</b> (<var>pts</var>)<var><a name="index-voronoin-2107"></a></var><br>
— Function File: [<var>C</var>, <var>F</var>] = <b>voronoin</b> (<var>pts, options</var>)<var><a name="index-voronoin-2108"></a></var><br>
<blockquote><p>computes n- dimensional voronoi facets. The input matrix <var>pts</var>
of size [n, dim] contains n points of dimension dim.
<var>C</var> contains the points of the voronoi facets. The list <var>F</var>
contains for each facet the indices of the voronoi points.
<p>A second 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.
<!-- 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_002dvoronoin.html#doc_002dvoronoin">voronoin</a>, <a href="doc_002ddelaunay.html#doc_002ddelaunay">delaunay</a>, <a href="doc_002dconvhull.html#doc_002dconvhull">convhull</a>.
</p></blockquote></div>
<p>An example of the use of <code>voronoi</code> is
<pre class="example"> rand("state",9);
x = rand(10,1);
y = rand(10,1);
tri = delaunay (x, y);
[vx, vy] = voronoi (x, y, tri);
triplot (tri, x, y, "b");
hold on;
plot (vx, vy, "r");
</pre>
<p>Additional information about the size of the facets of a Voronoi
diagram, and which points of a set of points is in a polygon can be had
with the <code>polyarea</code> and <code>inpolygon</code> functions respectively.
<!-- ./general/polyarea.m -->
<p><a name="doc_002dpolyarea"></a>
<div class="defun">
— Function File: <b>polyarea</b> (<var>x, y</var>)<var><a name="index-polyarea-2109"></a></var><br>
— Function File: <b>polyarea</b> (<var>x, y, dim</var>)<var><a name="index-polyarea-2110"></a></var><br>
<blockquote>
<p>Determines area of a polygon by triangle method. The variables
<var>x</var> and <var>y</var> define the vertex pairs, and must therefore have
the same shape. They can be either vectors or arrays. If they are
arrays then the columns of <var>x</var> and <var>y</var> are treated separately
and an area returned for each.
<p>If the optional <var>dim</var> argument is given, then <code>polyarea</code>
works along this dimension of the arrays <var>x</var> and <var>y</var>.
</blockquote></div>
<p>An example of the use of <code>polyarea</code> might be
<pre class="example"> rand ("state", 2);
x = rand (10, 1);
y = rand (10, 1);
[c, f] = voronoin ([x, y]);
af = zeros (size(f));
for i = 1 : length (f)
af(i) = polyarea (c (f {i, :}, 1), c (f {i, :}, 2));
endfor
</pre>
<p>Facets of the Voronoi diagram with a vertex at infinity have infinity
area. A simplified version of <code>polyarea</code> for rectangles is
available with <code>rectint</code>
<!-- ./geometry/rectint.m -->
<p><a name="doc_002drectint"></a>
<div class="defun">
— Function File: <var>area</var> = <b>rectint</b> (<var>a, b</var>)<var><a name="index-rectint-2111"></a></var><br>
<blockquote>
<p>Compute the area of intersection of rectangles in <var>a</var> and
rectangles in <var>b</var>. Rectangles are defined as [x y width height]
where x and y are the minimum values of the two orthogonal
dimensions.
<p>If <var>a</var> or <var>b</var> are matrices, then the output, <var>area</var>, is a
matrix where the i-th row corresponds to the i-th row of a and the j-th
column corresponds to the j-th row of b.
<!-- 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_002dpolyarea.html#doc_002dpolyarea">polyarea</a>.
</p></blockquote></div>
<!-- ./geometry/inpolygon.m -->
<p><a name="doc_002dinpolygon"></a>
<div class="defun">
— Function File: [<var>in</var>, <var>on</var>] = <b>inpolygon</b> (<var>x, y, xv, xy</var>)<var><a name="index-inpolygon-2112"></a></var><br>
<blockquote>
<p>For a polygon defined by <code>(</code><var>xv</var><code>, </code><var>yv</var><code>)</code> points, determine
if the points <code>(</code><var>x</var><code>, </code><var>y</var><code>)</code> are inside or outside the polygon.
The variables <var>x</var>, <var>y</var>, must have the same dimension. The optional
output <var>on</var> gives the points that are on the polygon.
</blockquote></div>
<p>An example of the use of <code>inpolygon</code> might be
<pre class="example"> randn ("state", 2);
x = randn (100, 1);
y = randn (100, 1);
vx = cos (pi * [-1 : 0.1: 1]);
vy = sin (pi * [-1 : 0.1 : 1]);
in = inpolygon (x, y, vx, vy);
plot(vx, vy, x(in), y(in), "r+", x(!in), y(!in), "bo");
axis ([-2, 2, -2, 2]);
</pre>
</body></html>
|
