<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>