<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.13">
<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">
<a name="Voronoi-Diagrams"></a>
<p>
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>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
3e60ff9d4d6f58c8fbd17208f14089fa
>
files
>
444
