<html lang="en">
<head>
<title>Voronoi Diagrams - GNU Octave</title>
<meta http-equiv="Content-Type" content="text/html">
<meta name="description" content="GNU Octave">
<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">30.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
simplices of the Delaunay tessellation.
<!-- voronoi scripts/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-2797"></a></var><br>
— Function File: <b>voronoi</b> (<var>x, y, options</var>)<var><a name="index-voronoi-2798"></a></var><br>
— Function File: <b>voronoi</b> (<var><small class="dots">...</small>, "linespec"</var>)<var><a name="index-voronoi-2799"></a></var><br>
— Function File: <b>voronoi</b> (<var>hax, <small class="dots">...</small></var>)<var><a name="index-voronoi-2800"></a></var><br>
— Function File: <var>h</var> = <b>voronoi</b> (<var><small class="dots">...</small></var>)<var><a name="index-voronoi-2801"></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-2802"></a></var><br>
<blockquote><p>Plot the 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.
<p>If "linespec" is given it is used to set the color and line style of the
plot. If an axis graphics handle <var>hax</var> is supplied then the Voronoi
diagram is drawn on the specified axis rather than in a new figure.
<p>The <var>options</var> 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>.
<p>If a single output argument is requested then the Voronoi diagram will be
plotted and a graphics handle <var>h</var> to the plot is returned.
[<var>vx</var>, <var>vy</var>] = voronoi(<small class="dots">...</small>) returns the Voronoi vertices
instead of plotting the diagram.
<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>
<!-- voronoin scripts/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-2803"></a></var><br>
— Function File: [<var>C</var>, <var>F</var>] = <b>voronoin</b> (<var>pts, options</var>)<var><a name="index-voronoin-2804"></a></var><br>
<blockquote><p>Compute N-dimensional Voronoi facets. The input matrix <var>pts</var>
of size [n, dim] contains n points in a space 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>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>.
<!-- 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_002dconvhulln.html#doc_002dconvhulln">convhulln</a>, <a href="doc_002ddelaunayn.html#doc_002ddelaunayn">delaunayn</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 class="noindent">The result of which can be seen in <a href="fig_003avoronoi.html#fig_003avoronoi">fig:voronoi</a>. Note that the
circum-circle of one of the triangles has been added to this figure, to
make the relationship between the Delaunay tessellation and the Voronoi
diagram clearer.
<div class="float">
<a name="fig_003avoronoi"></a><div align="center"><img src="voronoi.png" alt="voronoi.png"></div>
<p><strong class="float-caption">Figure 30.3: Delaunay triangulation and Voronoi diagram of a random set of points</strong></p></div>
<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.
<!-- polyarea scripts/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-2805"></a></var><br>
— Function File: <b>polyarea</b> (<var>x, y, dim</var>)<var><a name="index-polyarea-2806"></a></var><br>
<blockquote>
<p>Determine 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>
<!-- rectint scripts/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-2807"></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>
<!-- inpolygon scripts/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, yv</var>)<var><a name="index-inpolygon-2808"></a></var><br>
<blockquote>
<p>For a polygon defined by vertex points <code>(</code><var>xv</var><code>, </code><var>yv</var><code>)</code>, 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>
<p class="noindent">The result of which can be seen in <a href="fig_003ainpolygon.html#fig_003ainpolygon">fig:inpolygon</a>.
<div class="float">
<a name="fig_003ainpolygon"></a><div align="center"><img src="inpolygon.png" alt="inpolygon.png"></div>
<p><strong class="float-caption">Figure 30.4: Demonstration of the <code>inpolygon</code> function to determine the
points inside a polygon</strong></p></div>
</body></html>
