Mercurial > hg > octave-lyh
annotate scripts/geometry/voronoi.m @ 13746:7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
* NEWS : Document new options being passed to Qhull
* convhull.m, delaunay.m, delaunay3.m, delaunayn.m, voronoi.m, voronoin.m:
Update docstrings. Put input validation first. Use same variable names
as Matlab. Restore random state altered in demos.
* __delaunayn__.cc: Use common syntax for parsing OPTIONS input.
Add 'Qz' option to qhull command for 2D,3D data. Correctly free
all Qhull memory and avoid segfault with non-simplicial facets.
* __voronoi__.cc: Use common syntax for parsing OPTIONS input.
Correctly free all Qhull memory.
* convhulln.cc: Use common syntax for parsing OPTIONS input.
Use Matlab-compatible options for qhull command.
Correctly free all Qhull memory. Allow return of non-simplicial
facets without causing a segfault.
| author | Rik <octave@nomad.inbox5.com> |
|---|---|
| date | Tue, 25 Oct 2011 10:17:23 -0700 |
| parents | cefd568ea073 |
| children | 440d7914cf01 |
| rev | line source |
|---|---|
| 11523 | 1 ## Copyright (C) 2000-2011 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 -*- | |
|
10793
be55736a0783
Grammarcheck the documentation from m-files.
Rik <octave@nomad.inbox5.com>
parents:
10791
diff
changeset
|
20 ## @deftypefn {Function File} {} voronoi (@var{x}, @var{y}) |
|
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
21 ## @deftypefnx {Function File} {} voronoi (@var{x}, @var{y}, @var{options}) |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
22 ## @deftypefnx {Function File} {} voronoi (@dots{}, "linespec") |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
23 ## @deftypefnx {Function File} {} voronoi (@var{hax}, @dots{}) |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
24 ## @deftypefnx {Function File} {@var{h} =} voronoi (@dots{}) |
| 6823 | 25 ## @deftypefnx {Function File} {[@var{vx}, @var{vy}] =} voronoi (@dots{}) |
|
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
26 ## Plot the Voronoi diagram of points @code{(@var{x}, @var{y})}. |
|
10791
3140cb7a05a1
Add spellchecker scripts for Octave and run spellcheck of documentation
Rik <octave@nomad.inbox5.com>
parents:
10549
diff
changeset
|
27 ## The Voronoi facets with points at infinity are not drawn. |
|
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
28 ## |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
29 ## If "linespec" is given it is used to set the color and line style of the |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
30 ## plot. If an axis graphics handle @var{hax} is supplied then the Voronoi |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
31 ## diagram is drawn on the specified axis rather than in a new figure. |
| 6823 | 32 ## |
|
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
33 ## The @var{options} argument, which must be a string or cell array of strings, |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
34 ## contains options passed to the underlying qhull command. |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
35 ## See the documentation for the Qhull library for details |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
36 ## @url{http://www.qhull.org/html/qh-quick.htm#options}. |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
37 ## |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
38 ## If a single output argument is requested then the Voronoi diagram will be |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
39 ## plotted and a graphics handle to the plot is returned. |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
40 ## [@var{vx}, @var{vy}] = voronoi(@dots{}) returns the Voronoi vertices |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
41 ## instead of plotting the diagram. |
| 6823 | 42 ## |
| 43 ## @example | |
| 44 ## @group | |
| 6826 | 45 ## x = rand (10, 1); |
| 46 ## y = rand (size (x)); | |
| 47 ## h = convhull (x, y); | |
| 48 ## [vx, vy] = voronoi (x, y); | |
| 49 ## plot (vx, vy, "-b", x, y, "o", x(h), y(h), "-g") | |
| 50 ## legend ("", "points", "hull"); | |
| 6823 | 51 ## @end group |
| 52 ## @end example | |
| 53 ## | |
| 54 ## @seealso{voronoin, delaunay, convhull} | |
| 55 ## @end deftypefn | |
| 56 | |
| 57 ## Author: Kai Habel <kai.habel@gmx.de> | |
| 58 ## First Release: 20/08/2000 | |
| 59 | |
| 60 ## 2002-01-04 Paul Kienzle <pkienzle@users.sf.net> | |
| 61 ## * limit the default graph to the input points rather than the whole diagram | |
| 62 ## * provide example | |
| 63 ## * use unique(x,"rows") rather than __unique_rows__ | |
| 64 | |
| 65 ## 2003-12-14 Rafael Laboissiere <rafael@laboissiere.net> | |
| 66 ## Added optional fourth argument to pass options to the underlying | |
| 67 ## qhull command | |
| 68 | |
|
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
69 function [vx, vy] = voronoi (varargin) |
| 6823 | 70 |
| 71 if (nargin < 1) | |
| 72 print_usage (); | |
|
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
73 elseif (nargout > 2) |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
74 error ("voronoi: No more than two output arguments supported"); |
| 6823 | 75 endif |
| 76 | |
| 77 narg = 1; | |
| 78 if (isscalar (varargin{1}) && ishandle (varargin{1})) | |
| 79 handl = varargin{1}; | |
| 6826 | 80 if (! strcmp (get (handl, "type"), "axes")) |
| 6823 | 81 error ("voronoi: expecting first argument to be an axes object"); |
| 82 endif | |
|
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
83 narg++; |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
84 elseif (nargout < 2) |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
85 handl = gca (); |
| 6823 | 86 endif |
| 87 | |
| 88 if (nargin < 1 + narg || nargin > 3 + narg) | |
| 89 print_usage (); | |
| 90 endif | |
| 91 | |
| 92 x = varargin{narg++}; | |
| 93 y = varargin{narg++}; | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
94 |
| 6823 | 95 opts = {}; |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
96 if (narg <= nargin) |
| 6823 | 97 if (iscell (varargin{narg})) |
| 98 opts = varargin(narg++); | |
|
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
99 elseif (isnumeric (varargin{narg})) |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
100 ## Accept, but ignore, the triangulation |
| 6823 | 101 narg++; |
| 102 endif | |
| 103 endif | |
| 104 | |
| 105 linespec = {"b"}; | |
|
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
106 if (narg <= nargin && ischar (varargin{narg})) |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
107 linespec = varargin(narg); |
| 6823 | 108 endif |
| 109 | |
| 110 lx = length (x); | |
| 111 ly = length (y); | |
| 112 | |
| 113 if (lx != ly) | |
|
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
114 error ("voronoi: X and Y must be vectors of the same length"); |
| 6823 | 115 endif |
| 116 | |
|
8440
e792c736b1ac
Fix for dense grids and speed up for voronoi function
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
117 ## 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
|
118 ## 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
|
119 ## 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
|
120 ## delta below however |
| 6852 | 121 xmax = max (x(:)); |
| 122 xmin = min (x(:)); | |
| 123 ymax = max (y(:)); | |
| 124 ymin = min (y(:)); | |
| 125 xdelta = xmax - xmin; | |
| 126 ydelta = ymax - ymin; | |
|
8440
e792c736b1ac
Fix for dense grids and speed up for voronoi function
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
127 scale = 2; |
| 6852 | 128 |
| 129 xbox = [xmin - scale * xdelta; xmin - scale * xdelta; ... | |
| 10549 | 130 xmax + scale * xdelta; xmax + scale * xdelta]; |
| 6852 | 131 ybox = [xmin - scale * xdelta; xmax + scale * xdelta; ... |
| 10549 | 132 xmax + scale * xdelta; xmin - scale * xdelta]; |
| 6852 | 133 |
|
8440
e792c736b1ac
Fix for dense grids and speed up for voronoi function
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
134 [p, c, infi] = __voronoi__ ([[x(:) ; xbox(:)], [y(:); ybox(:)]], opts{:}); |
| 6823 | 135 |
|
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
136 idx = find (! infi); |
| 6823 | 137 ll = length (idx); |
|
8440
e792c736b1ac
Fix for dense grids and speed up for voronoi function
David Bateman <dbateman@free.fr>
parents:
8347
diff
changeset
|
138 c = c(idx).'; |
|
12931
cefd568ea073
Replace function handles with function names in cellfun calls for 15% speedup.
Rik <octave@nomad.inbox5.com>
parents:
12824
diff
changeset
|
139 k = sum (cellfun ("length", c)); |
|
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
140 edges = cell2mat (cellfun (@(x) [x ; [x(end), x(1:end-1)]], c, |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
141 "uniformoutput", false)); |
| 6823 | 142 |
| 143 ## Identify the unique edges of the Voronoi diagram | |
| 144 edges = sortrows (sort (edges).').'; | |
| 6852 | 145 edges = edges (:, [(edges(1, 1: end - 1) != edges(1, 2 : end) | ... |
| 10549 | 146 edges(2, 1 :end - 1) != edges(2, 2 : end)), true]); |
| 6852 | 147 |
| 148 ## Eliminate the edges of the diagram representing the box | |
| 149 poutside = (1 : rows(p)) ... | |
| 150 (p (:, 1) < xmin - xdelta | p (:, 1) > xmax + xdelta | ... | |
| 151 p (:, 2) < ymin - ydelta | p (:, 2) > ymax + ydelta); | |
| 152 edgeoutside = ismember (edges (1, :), poutside) & ... | |
| 153 ismember (edges (2, :), poutside); | |
| 154 edges (:, edgeoutside) = []; | |
| 6823 | 155 |
| 156 ## Get points of the diagram | |
|
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
157 Vvx = reshape (p(edges, 1), size (edges)); |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
158 Vvy = reshape (p(edges, 2), size (edges)); |
| 6823 | 159 |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
160 if (nargout < 2) |
| 6852 | 161 lim = [xmin, xmax, ymin, ymax]; |
|
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
162 h = plot (handl, Vvx, Vvy, linespec{:}, x, y, '+'); |
| 6852 | 163 axis (lim + 0.1 * [[-1, 1] * (lim (2) - lim (1)), ... |
| 10549 | 164 [-1, 1] * (lim (4) - lim (3))]); |
| 6823 | 165 if (nargout == 1) |
|
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
166 vx = h; |
| 6823 | 167 endif |
| 168 else | |
|
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
169 vx = Vvx; |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
170 vy = Vvy; |
| 6823 | 171 endif |
| 172 | |
| 173 endfunction | |
|
12824
819a60a05a65
codesprint: add test and demo for voronoi.m
Kai Habel <kai.habel@gmx.de>
parents:
12575
diff
changeset
|
174 |
|
819a60a05a65
codesprint: add test and demo for voronoi.m
Kai Habel <kai.habel@gmx.de>
parents:
12575
diff
changeset
|
175 |
|
819a60a05a65
codesprint: add test and demo for voronoi.m
Kai Habel <kai.habel@gmx.de>
parents:
12575
diff
changeset
|
176 %!demo |
|
819a60a05a65
codesprint: add test and demo for voronoi.m
Kai Habel <kai.habel@gmx.de>
parents:
12575
diff
changeset
|
177 %! voronoi (rand(10,1), rand(10,1)); |
|
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
178 |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
179 %!testif HAVE_QHULL |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
180 %! phi = linspace (-pi, 3/4*pi, 8); |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
181 %! [x,y] = pol2cart (phi, 1); |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
182 %! [vx,vy] = voronoi (x,y); |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
183 %! assert(vx(2,:), zeros (1, columns (vx)), eps); |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
184 %! assert(vy(2,:), zeros (1, columns (vy)), eps); |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
185 |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
186 %% FIXME: Need input validation tests |
|
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
12931
diff
changeset
|
187 |