Mercurial > hg > octave-lyh
annotate scripts/geometry/voronoi.m @ 8664:e07e93c04080
style fixes
| author | John W. Eaton <jwe@octave.org> |
|---|---|
| date | Wed, 04 Feb 2009 10:56:23 -0500 |
| parents | e792c736b1ac |
| children | eb63fbe60fab |
| rev | line source |
|---|---|
| 7017 | 1 ## Copyright (C) 2000, 2007 Kai Habel |
| 6823 | 2 ## |
| 3 ## This file is part of Octave. | |
| 4 ## | |
| 5 ## Octave is free software; you can redistribute it and/or modify it | |
| 6 ## under the terms of the GNU General Public License as published by | |
| 7016 | 7 ## the Free Software Foundation; either version 3 of the License, or (at |
| 8 ## your option) any later version. | |
| 6823 | 9 ## |
| 10 ## Octave is distributed in the hope that it will be useful, but | |
| 11 ## WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 12 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
| 13 ## General Public License for more details. | |
| 14 ## | |
| 15 ## You should have received a copy of the GNU General Public License | |
| 7016 | 16 ## along with Octave; see the file COPYING. If not, see |
| 17 ## <http://www.gnu.org/licenses/>. | |
| 6823 | 18 |
| 19 ## -*- texinfo -*- | |
| 20 ## @deftypefn {Function File} {} voronoi (@var{x}, @var{y}) | |
| 21 ## @deftypefnx {Function File} {} voronoi (@var{x}, @var{y}, "plotstyle") | |
| 22 ## @deftypefnx {Function File} {} voronoi (@var{x}, @var{y}, "plotstyle", @var{options}) | |
| 23 ## @deftypefnx {Function File} {[@var{vx}, @var{vy}] =} voronoi (@dots{}) | |
| 24 ## plots voronoi diagram of points @code{(@var{x}, @var{y})}. | |
| 25 ## The voronoi facets with points at infinity are not drawn. | |
|
8347
fa78cb8d8a5c
corrections for typos
Brian Gough<bjg@network-theory.co.uk>
parents:
7208
diff
changeset
|
26 ## [@var{vx}, @var{vy}] = voronoi(...) returns the vertices instead of plotting the |
| 6823 | 27 ## diagram. plot (@var{vx}, @var{vy}) shows the voronoi diagram. |
| 28 ## | |
| 29 ## A fourth optional argument, which must be a string, contains extra options | |
| 30 ## passed to the underlying qhull command. See the documentation for the | |
| 31 ## Qhull library for details. | |
| 32 ## | |
| 33 ## @example | |
| 34 ## @group | |
| 6826 | 35 ## x = rand (10, 1); |
| 36 ## y = rand (size (x)); | |
| 37 ## h = convhull (x, y); | |
| 38 ## [vx, vy] = voronoi (x, y); | |
| 39 ## plot (vx, vy, "-b", x, y, "o", x(h), y(h), "-g") | |
| 40 ## legend ("", "points", "hull"); | |
| 6823 | 41 ## @end group |
| 42 ## @end example | |
| 43 ## | |
| 44 ## @seealso{voronoin, delaunay, convhull} | |
| 45 ## @end deftypefn | |
| 46 | |
| 47 ## Author: Kai Habel <kai.habel@gmx.de> | |
| 48 ## First Release: 20/08/2000 | |
| 49 | |
| 50 ## 2002-01-04 Paul Kienzle <pkienzle@users.sf.net> | |
| 51 ## * limit the default graph to the input points rather than the whole diagram | |
| 52 ## * provide example | |
| 53 ## * use unique(x,"rows") rather than __unique_rows__ | |
| 54 | |
| 55 ## 2003-12-14 Rafael Laboissiere <rafael@laboissiere.net> | |
| 56 ## Added optional fourth argument to pass options to the underlying | |
| 57 ## qhull command | |
| 58 | |
| 59 function [vvx, vvy] = voronoi (varargin) | |
| 60 | |
| 61 if (nargin < 1) | |
| 62 print_usage (); | |
| 63 endif | |
| 64 | |
| 65 narg = 1; | |
| 66 if (isscalar (varargin{1}) && ishandle (varargin{1})) | |
| 67 handl = varargin{1}; | |
| 68 narg++; | |
| 6826 | 69 if (! strcmp (get (handl, "type"), "axes")) |
| 6823 | 70 error ("voronoi: expecting first argument to be an axes object"); |
| 71 endif | |
| 72 else | |
| 73 if (nargout < 2) | |
| 6826 | 74 handl = gca (); |
| 6823 | 75 endif |
| 76 endif | |
| 77 | |
| 78 if (nargin < 1 + narg || nargin > 3 + narg) | |
| 79 print_usage (); | |
| 80 endif | |
| 81 | |
| 82 x = varargin{narg++}; | |
| 83 y = varargin{narg++}; | |
| 84 | |
| 85 opts = {}; | |
| 86 if (narg <= nargin) | |
| 87 if (iscell (varargin{narg})) | |
| 88 opts = varargin(narg++); | |
| 89 elseif (ismatrix (varargin{narg})) | |
| 90 ## Accept but ignore the triangulation | |
| 91 narg++; | |
| 92 endif | |
| 93 endif | |
| 94 | |
| 95 linespec = {"b"}; | |
| 96 if (narg <= nargin) | |
| 97 if (ischar (varargin{narg})) | |
| 98 linespec = varargin(narg); | |
| 99 endif | |
| 100 endif | |
| 101 | |
| 102 lx = length (x); | |
| 103 ly = length (y); | |
| 104 | |
| 105 if (lx != ly) | |
| 106 error ("voronoi: arguments must be vectors of same length"); | |
| 107 endif | |
| 108 | |
|
8440
e792c736b1ac
Fix for dense grids and speed up for voronoi function
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
109 ## Add box to approximate rays to infinity. For Voronoi diagrams the |
|
e792c736b1ac
Fix for dense grids and speed up for voronoi function
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
110 ## box can (and should) be close to the points themselves. To make the |
|
e792c736b1ac
Fix for dense grids and speed up for voronoi function
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
111 ## job of finding the exterior edges it should be at least two times the |
|
e792c736b1ac
Fix for dense grids and speed up for voronoi function
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
112 ## delta below however |
| 6852 | 113 xmax = max (x(:)); |
| 114 xmin = min (x(:)); | |
| 115 ymax = max (y(:)); | |
| 116 ymin = min (y(:)); | |
| 117 xdelta = xmax - xmin; | |
| 118 ydelta = ymax - ymin; | |
|
8440
e792c736b1ac
Fix for dense grids and speed up for voronoi function
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
119 scale = 2; |
| 6852 | 120 |
| 121 xbox = [xmin - scale * xdelta; xmin - scale * xdelta; ... | |
| 122 xmax + scale * xdelta; xmax + scale * xdelta]; | |
| 123 ybox = [xmin - scale * xdelta; xmax + scale * xdelta; ... | |
| 124 xmax + scale * xdelta; xmin - scale * xdelta]; | |
| 125 | |
|
8440
e792c736b1ac
Fix for dense grids and speed up for voronoi function
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
126 [p, c, infi] = __voronoi__ ([[x(:) ; xbox(:)], [y(:); ybox(:)]], opts{:}); |
| 6823 | 127 |
| 128 idx = find (!infi); | |
| 129 ll = length (idx); | |
|
8440
e792c736b1ac
Fix for dense grids and speed up for voronoi function
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
130 c = c(idx).'; |
|
e792c736b1ac
Fix for dense grids and speed up for voronoi function
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
131 k = sum (cellfun ('length', c)); |
|
e792c736b1ac
Fix for dense grids and speed up for voronoi function
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
132 edges = cell2mat(cellfun (@(x) [x ; [x(end), x(1:end-1)]], c, |
|
e792c736b1ac
Fix for dense grids and speed up for voronoi function
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
133 "UniformOutput", false)); |
| 6823 | 134 |
| 135 ## Identify the unique edges of the Voronoi diagram | |
| 136 edges = sortrows (sort (edges).').'; | |
| 6852 | 137 edges = edges (:, [(edges(1, 1: end - 1) != edges(1, 2 : end) | ... |
| 138 edges(2, 1 :end - 1) != edges(2, 2 : end)), true]); | |
| 139 | |
| 140 ## Eliminate the edges of the diagram representing the box | |
| 141 poutside = (1 : rows(p)) ... | |
| 142 (p (:, 1) < xmin - xdelta | p (:, 1) > xmax + xdelta | ... | |
| 143 p (:, 2) < ymin - ydelta | p (:, 2) > ymax + ydelta); | |
| 144 edgeoutside = ismember (edges (1, :), poutside) & ... | |
| 145 ismember (edges (2, :), poutside); | |
| 146 edges (:, edgeoutside) = []; | |
| 6823 | 147 |
| 148 ## Get points of the diagram | |
| 6852 | 149 vx = reshape (p (edges, 1), size(edges)); |
| 150 vy = reshape (p (edges, 2), size(edges)); | |
| 6823 | 151 |
| 152 if (nargout < 2) | |
| 6852 | 153 lim = [xmin, xmax, ymin, ymax]; |
| 6823 | 154 h = plot (handl, vx, vy, linespec{:}, x, y, '+'); |
| 6852 | 155 axis (lim + 0.1 * [[-1, 1] * (lim (2) - lim (1)), ... |
| 156 [-1, 1] * (lim (4) - lim (3))]); | |
| 6823 | 157 if (nargout == 1) |
| 158 vxx = h; | |
| 159 endif | |
| 160 elseif (nargout == 2) | |
| 161 vvx = vx; | |
| 162 vvy = vy; | |
| 163 else | |
| 8664 | 164 error ("voronoi: only two or zero output arguments supported"); |
| 6823 | 165 endif |
| 166 | |
| 167 endfunction |