Mercurial > octave

annotate scripts/geometry/voronoi.m @ 30564:796f54d4ddbf stable

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update Octave Project Developers copyright for the new year In files that have the "Octave Project Developers" copyright notice, update for 2021. In all .txi and .texi files except gpl.txi and gpl.texi in the doc/liboctave and doc/interpreter directories, change the copyright to "Octave Project Developers", the same as used for other source files. Update copyright notices for 2022 (not done since 2019). For gpl.txi and gpl.texi, change the copyright notice to be "Free Software Foundation, Inc." and leave the date at 2007 only because this file only contains the text of the GPL, not anything created by the Octave Project Developers. Add Paul Thomas to contributors.in.
author John W. Eaton <jwe@octave.org>
date Tue, 28 Dec 2021 18:22:40 -0500
parents 7854d5752dd2
children 597f3ee61a48
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
27923
bd51beb6205e update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents: 27919
diff changeset
1 ########################################################################
bd51beb6205e update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents: 27919
diff changeset
2 ##
30564
796f54d4ddbf update Octave Project Developers copyright for the new year
John W. Eaton <jwe@octave.org>
parents: 29359
diff changeset
3 ## Copyright (C) 2000-2022 The Octave Project Developers
27918
b442ec6dda5c use centralized file for copyright info for individual contributors
John W. Eaton <jwe@octave.org>
parents: 26376
diff changeset
4 ##
27923
bd51beb6205e update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents: 27919
diff changeset
5 ## See the file COPYRIGHT.md in the top-level directory of this
bd51beb6205e update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents: 27919
diff changeset
6 ## distribution or <https://octave.org/copyright/>.
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
7 ##
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
8 ## This file is part of Octave.
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
9 ##
24534
194eb4bd202b maint: Update punctuation for GPL v3 license text.
Rik <rik@octave.org>
parents: 24432
diff changeset
10 ## Octave is free software: you can redistribute it and/or modify it
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
11 ## under the terms of the GNU General Public License as published by
24534
194eb4bd202b maint: Update punctuation for GPL v3 license text.
Rik <rik@octave.org>
parents: 24432
diff changeset
12 ## the Free Software Foundation, either version 3 of the License, or
22755
3a2b891d0b33 maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents: 22707
diff changeset
13 ## (at your option) any later version.
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
14 ##
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
15 ## Octave is distributed in the hope that it will be useful, but
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
16 ## WITHOUT ANY WARRANTY; without even the implied warranty of
22755
3a2b891d0b33 maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents: 22707
diff changeset
17 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
3a2b891d0b33 maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents: 22707
diff changeset
18 ## GNU General Public License for more details.
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
19 ##
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
20 ## You should have received a copy of the GNU General Public License
7016
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 6852
diff changeset
21 ## along with Octave; see the file COPYING. If not, see
24534
194eb4bd202b maint: Update punctuation for GPL v3 license text.
Rik <rik@octave.org>
parents: 24432
diff changeset
22 ## <https://www.gnu.org/licenses/>.
27923
bd51beb6205e update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents: 27919
diff changeset
23 ##
bd51beb6205e update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents: 27919
diff changeset
24 ########################################################################
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
25
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
26 ## -*- texinfo -*-
20852
516bb87ea72e 2015 Code Sprint: remove class of function from docstring for all m-files.
Rik <rik@octave.org>
parents: 20835
diff changeset
27 ## @deftypefn {} {} voronoi (@var{x}, @var{y})
516bb87ea72e 2015 Code Sprint: remove class of function from docstring for all m-files.
Rik <rik@octave.org>
parents: 20835
diff changeset
28 ## @deftypefnx {} {} voronoi (@var{x}, @var{y}, @var{options})
516bb87ea72e 2015 Code Sprint: remove class of function from docstring for all m-files.
Rik <rik@octave.org>
parents: 20835
diff changeset
29 ## @deftypefnx {} {} voronoi (@dots{}, "linespec")
516bb87ea72e 2015 Code Sprint: remove class of function from docstring for all m-files.
Rik <rik@octave.org>
parents: 20835
diff changeset
30 ## @deftypefnx {} {} voronoi (@var{hax}, @dots{})
516bb87ea72e 2015 Code Sprint: remove class of function from docstring for all m-files.
Rik <rik@octave.org>
parents: 20835
diff changeset
31 ## @deftypefnx {} {@var{h} =} voronoi (@dots{})
516bb87ea72e 2015 Code Sprint: remove class of function from docstring for all m-files.
Rik <rik@octave.org>
parents: 20835
diff changeset
32 ## @deftypefnx {} {[@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
33 ## Plot the Voronoi diagram of points @code{(@var{x}, @var{y})}.
20158
7503499a252b doc: Update docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19833
diff changeset
34 ##
10791
3140cb7a05a1 Add spellchecker scripts for Octave and run spellcheck of documentation
Rik <octave@nomad.inbox5.com>
parents: 10549
diff changeset
35 ## The Voronoi facets with points at infinity are not drawn.
19593
446c46af4b42 strip trailing whitespace from most source files
John W. Eaton <jwe@octave.org>
parents: 17744
diff changeset
36 ##
13746
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 12931
diff changeset
37 ## 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
38 ## 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
39 ## 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
40 ## @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
41 ##
20158
7503499a252b doc: Update docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19833
diff changeset
42 ## If @qcode{"linespec"} is given it is used to set the color and line style of
7503499a252b doc: Update docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19833
diff changeset
43 ## the plot.
7503499a252b doc: Update docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19833
diff changeset
44 ##
24431
0c6cedafc71e doc: Use 'axes' rather than 'axis' appropriately in docstrings.
Rik <rik@octave.org>
parents: 23219
diff changeset
45 ## If an axes graphics handle @var{hax} is supplied then the Voronoi diagram is
0c6cedafc71e doc: Use 'axes' rather than 'axis' appropriately in docstrings.
Rik <rik@octave.org>
parents: 23219
diff changeset
46 ## drawn on the specified axes rather than in a new figure.
20158
7503499a252b doc: Update docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19833
diff changeset
47 ##
13746
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 12931
diff changeset
48 ## If a single output argument is requested then the Voronoi diagram will be
14001
5f0bb45e615c doc: Update documentation for functions returning a graphics handle h (Bug #34761)
Rik <octave@nomad.inbox5.com>
parents: 13879
diff changeset
49 ## plotted and a graphics handle @var{h} to the plot is returned.
20158
7503499a252b doc: Update docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents: 19833
diff changeset
50 ##
14868
5d3a684236b0 maint: Use Octave coding conventions for cuddling parentheses in scripts directory
Rik <octave@nomad.inbox5.com>
parents: 14335
diff changeset
51 ## [@var{vx}, @var{vy}] = voronoi (@dots{}) returns the Voronoi vertices
13746
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 12931
diff changeset
52 ## instead of plotting the diagram.
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
53 ##
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
54 ## @example
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
55 ## @group
14327
4d917a6a858b doc: Use Octave coding conventions in @example blocks of docstrings.
Rik <octave@nomad.inbox5.com>
parents: 14138
diff changeset
56 ## x = rand (10, 1);
4d917a6a858b doc: Use Octave coding conventions in @example blocks of docstrings.
Rik <octave@nomad.inbox5.com>
parents: 14138
diff changeset
57 ## y = rand (size (x));
4d917a6a858b doc: Use Octave coding conventions in @example blocks of docstrings.
Rik <octave@nomad.inbox5.com>
parents: 14138
diff changeset
58 ## h = convhull (x, y);
4d917a6a858b doc: Use Octave coding conventions in @example blocks of docstrings.
Rik <octave@nomad.inbox5.com>
parents: 14138
diff changeset
59 ## [vx, vy] = voronoi (x, y);
4d917a6a858b doc: Use Octave coding conventions in @example blocks of docstrings.
Rik <octave@nomad.inbox5.com>
parents: 14138
diff changeset
60 ## plot (vx, vy, "-b", x, y, "o", x(h), y(h), "-g");
4d917a6a858b doc: Use Octave coding conventions in @example blocks of docstrings.
Rik <octave@nomad.inbox5.com>
parents: 14138
diff changeset
61 ## legend ("", "points", "hull");
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
62 ## @end group
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
63 ## @end example
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
64 ##
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
65 ## @seealso{voronoin, delaunay, convhull}
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
66 ## @end deftypefn
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
67
13746
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 12931
diff changeset
68 function [vx, vy] = voronoi (varargin)
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
69
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
70 if (nargin < 1)
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
71 print_usage ();
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
72 endif
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
73
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
74 narg = 1;
18201
0ecd4618b1fc voronoi.m: Fix input validation so it doesn't open blank figure window.
Rik <rik@octave.org>
parents: 18193
diff changeset
75 hax = NaN;
24423
1d52db450db4 Change ishandle to return true for Java objects for Matlab compatibility.
Rik <rik@octave.org>
parents: 23573
diff changeset
76 if (isscalar (varargin{1}) && ishghandle (varargin{1}))
17125
b5d6314314fc Change various plot functions to take advantage of new isaxes() function.
Rik <rik@octave.org>
parents: 15393
diff changeset
77 hax = varargin{1};
18193
31d8e19a745d voronoi.m: Add input validation test for 2 points (bug #40996)
Rik <rik@octave.org>
parents: 17744
diff changeset
78 if (! isaxes (hax))
31d8e19a745d voronoi.m: Add input validation test for 2 points (bug #40996)
Rik <rik@octave.org>
parents: 17744
diff changeset
79 error ("voronoi: HAX argument must be an axes object");
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
80 endif
20735
418ae0cb752f Replace ++,-- with in-place operators for performance.
Rik <rik@octave.org>
parents: 20158
diff changeset
81 narg += 1;
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
82 endif
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
83
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
84 if (nargin < 1 + narg || nargin > 3 + narg)
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
85 print_usage ();
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
86 endif
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
87
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
88 x = varargin{narg++};
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
89 y = varargin{narg++};
11587
c792872f8942 all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents: 11523
diff changeset
90
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
91 opts = {};
11587
c792872f8942 all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents: 11523
diff changeset
92 if (narg <= nargin)
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
93 if (iscell (varargin{narg}))
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
94 opts = varargin(narg++);
13746
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 12931
diff changeset
95 elseif (isnumeric (varargin{narg}))
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 12931
diff changeset
96 ## Accept, but ignore, the triangulation
20735
418ae0cb752f Replace ++,-- with in-place operators for performance.
Rik <rik@octave.org>
parents: 20158
diff changeset
97 narg += 1;
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
98 endif
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
99 endif
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
100
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
101 linespec = {"b"};
13746
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 12931
diff changeset
102 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
103 linespec = varargin(narg);
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
104 endif
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
105
22697
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
106 if (! isvector (x) || ! isvector (y) || numel (x) != numel (y))
13746
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 12931
diff changeset
107 error ("voronoi: X and Y must be vectors of the same length");
22697
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
108 elseif (numel (x) < 2)
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
109 error ("voronoi: minimum of 2 points required");
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
110 endif
22697
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
111 x = x(:);
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
112 y = y(:);
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
113
21751
b571fc85953f maint: Use two spaces after period to indicate sentence break.
Rik <rik@octave.org>
parents: 20852
diff changeset
114 ## Add box to approximate rays to infinity. For Voronoi diagrams the
22697
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
115 ## box should be close to the points themselves. To make the job of
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
116 ## finding the exterior edges easier it should be bigger than the area
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
117 ## enclosed by the points themselves.
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
118 ## NOTE: Octave uses a factor of 2 although we don't have an mathematical
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
119 ## justification for that.
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
120
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
121 xmin = min (x);
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
122 xmax = max (x);
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
123 ymin = min (y);
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
124 ymax = max (y);
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
125 ## Factor for size of bounding box
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
126 scale = 2;
6852
a34d59fc7a91 [project @ 2007-08-31 20:51:58 by dbateman]
dbateman
parents: 6826
diff changeset
127 xdelta = xmax - xmin;
a34d59fc7a91 [project @ 2007-08-31 20:51:58 by dbateman]
dbateman
parents: 6826
diff changeset
128 ydelta = ymax - ymin;
22697
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
129 xbox = [xmin - scale * xdelta; xmin - scale * xdelta;
10549
95c3e38098bf Untabify .m scripts
Rik <code@nomad.inbox5.com>
parents: 9051
diff changeset
130 xmax + scale * xdelta; xmax + scale * xdelta];
22697
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
131 ybox = [ymin - scale * ydelta; ymax + scale * ydelta;
14865
70f86a64c412 * voronoi.m: Fix cut and paste error.
Nicholas Musolino <musolino@mit.edu>
parents: 14327
diff changeset
132 ymax + scale * ydelta; ymin - scale * ydelta];
6852
a34d59fc7a91 [project @ 2007-08-31 20:51:58 by dbateman]
dbateman
parents: 6826
diff changeset
133
22697
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
134 [p, c, infi] = __voronoi__ ("voronoi", [[x; xbox], [y; ybox]], opts{:});
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
135
22697
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
136 ## Build list of edges from points in facet.
15393
b99c52303d0b voronoi.m: Fix bug when there are multiple identical input points (bug #37270)
Rik <rik@octave.org>
parents: 14881
diff changeset
137 c = c(! infi).';
22697
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
138 edges = zeros (2, 0);
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
139 for i = 1:numel (c)
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
140 facet = c{i};
22707
413a19bca7f3 maint: Strip trailing whitespace from source files.
John W. Eaton <jwe@octave.org>
parents: 22697
diff changeset
141 if (isempty (facet))
22697
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
142 continue;
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
143 endif
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
144 edges = [edges, [facet; [facet(end), facet(1:end-1)]]];
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
145 endfor
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
146
22697
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
147 ## Keep only the unique edges of the Voronoi diagram
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
148 edges = sortrows (sort (edges).').';
22697
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
149 edges = edges(:, [any(diff(edges, 1, 2)), true]);
6852
a34d59fc7a91 [project @ 2007-08-31 20:51:58 by dbateman]
dbateman
parents: 6826
diff changeset
150
18203
5646f999245d voronoi.m: Add special handling for 2-point input (bug #40996).
Rik <rik@octave.org>
parents: 18201
diff changeset
151 if (numel (x) > 2)
22697
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
152 ## Eliminate the edges of the diagram representing the box.
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
153 ## Exclude points outside a certain radius from the center of distribution.
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
154 ## FIXME: Factor should be at least 1.0. Octave uses 1.1 for margin.
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
155 ## There is no theoretical justification for this choice.
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
156 ctr = [(xmax + xmin)/2 , (ymax + ymin)/2];
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
157 radius = 1.1 * sumsq ([xmin, ymin] - ctr);
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
158 dist = sumsq (p - ctr, 2);
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
159
22707
413a19bca7f3 maint: Strip trailing whitespace from source files.
John W. Eaton <jwe@octave.org>
parents: 22697
diff changeset
160 p_inside = (1:rows (p))(dist < radius);
22697
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
161 edge_inside = any (ismember (edges, p_inside));
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
162 edges = edges(:, edge_inside);
18203
5646f999245d voronoi.m: Add special handling for 2-point input (bug #40996).
Rik <rik@octave.org>
parents: 18201
diff changeset
163 else
5646f999245d voronoi.m: Add special handling for 2-point input (bug #40996).
Rik <rik@octave.org>
parents: 18201
diff changeset
164 ## look for the edge between the two given points
22697
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
165 for edge = edges
18203
5646f999245d voronoi.m: Add special handling for 2-point input (bug #40996).
Rik <rik@octave.org>
parents: 18201
diff changeset
166 if (det ([[[1;1],p(edge,1:2)];1,x(1),y(1)])
5646f999245d voronoi.m: Add special handling for 2-point input (bug #40996).
Rik <rik@octave.org>
parents: 18201
diff changeset
167 * det ([[[1;1],p(edge,1:2)];1,x(2),y(2)]) < 0)
5646f999245d voronoi.m: Add special handling for 2-point input (bug #40996).
Rik <rik@octave.org>
parents: 18201
diff changeset
168 edges = edge;
5646f999245d voronoi.m: Add special handling for 2-point input (bug #40996).
Rik <rik@octave.org>
parents: 18201
diff changeset
169 break;
5646f999245d voronoi.m: Add special handling for 2-point input (bug #40996).
Rik <rik@octave.org>
parents: 18201
diff changeset
170 endif
5646f999245d voronoi.m: Add special handling for 2-point input (bug #40996).
Rik <rik@octave.org>
parents: 18201
diff changeset
171 endfor
5646f999245d voronoi.m: Add special handling for 2-point input (bug #40996).
Rik <rik@octave.org>
parents: 18201
diff changeset
172 ## Use larger plot limits to make it more likely single bisector is shown.
5646f999245d voronoi.m: Add special handling for 2-point input (bug #40996).
Rik <rik@octave.org>
parents: 18201
diff changeset
173 xdelta = ydelta = max (xdelta, ydelta);
5646f999245d voronoi.m: Add special handling for 2-point input (bug #40996).
Rik <rik@octave.org>
parents: 18201
diff changeset
174 endif
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
175
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
176 ## 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
177 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
178 Vvy = reshape (p(edges, 2), size (edges));
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
179
11587
c792872f8942 all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents: 11523
diff changeset
180 if (nargout < 2)
18201
0ecd4618b1fc voronoi.m: Fix input validation so it doesn't open blank figure window.
Rik <rik@octave.org>
parents: 18193
diff changeset
181 if (isnan (hax))
0ecd4618b1fc voronoi.m: Fix input validation so it doesn't open blank figure window.
Rik <rik@octave.org>
parents: 18193
diff changeset
182 hax = gca ();
0ecd4618b1fc voronoi.m: Fix input validation so it doesn't open blank figure window.
Rik <rik@octave.org>
parents: 18193
diff changeset
183 endif
17125
b5d6314314fc Change various plot functions to take advantage of new isaxes() function.
Rik <rik@octave.org>
parents: 15393
diff changeset
184 h = plot (hax, Vvx, Vvy, linespec{:}, x, y, '+');
6852
a34d59fc7a91 [project @ 2007-08-31 20:51:58 by dbateman]
dbateman
parents: 6826
diff changeset
185 lim = [xmin, xmax, ymin, ymax];
15393
b99c52303d0b voronoi.m: Fix bug when there are multiple identical input points (bug #37270)
Rik <rik@octave.org>
parents: 14881
diff changeset
186 axis (lim + 0.1 * [[-1, 1] * xdelta, [-1, 1] * ydelta]);
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
187 if (nargout == 1)
13746
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 12931
diff changeset
188 vx = h;
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
189 endif
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
190 else
13746
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 12931
diff changeset
191 vx = Vvx;
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 12931
diff changeset
192 vy = Vvy;
6823
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
193 endif
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
194
9fddcc586065 [project @ 2007-08-24 08:27:27 by dbateman]
dbateman
parents:
diff changeset
195 endfunction
12824
819a60a05a65 codesprint: add test and demo for voronoi.m
Kai Habel <kai.habel@gmx.de>
parents: 12575
diff changeset
196
819a60a05a65 codesprint: add test and demo for voronoi.m
Kai Habel <kai.habel@gmx.de>
parents: 12575
diff changeset
197
819a60a05a65 codesprint: add test and demo for voronoi.m
Kai Habel <kai.habel@gmx.de>
parents: 12575
diff changeset
198 %!demo
14237
11949c9795a0 Revamp %!demos in m-files to use Octave coding conventions on spacing, etc.
Rik <octave@nomad.inbox5.com>
parents: 14138
diff changeset
199 %! 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
200
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 12931
diff changeset
201 %!testif HAVE_QHULL
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 12931
diff changeset
202 %! 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
203 %! [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
204 %! [vx,vy] = voronoi (x,y);
14868
5d3a684236b0 maint: Use Octave coding conventions for cuddling parentheses in scripts directory
Rik <octave@nomad.inbox5.com>
parents: 14335
diff changeset
205 %! assert (vx(2,:), zeros (1, columns (vx)), eps);
5d3a684236b0 maint: Use Octave coding conventions for cuddling parentheses in scripts directory
Rik <octave@nomad.inbox5.com>
parents: 14335
diff changeset
206 %! assert (vy(2,:), zeros (1, columns (vy)), eps);
13746
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 12931
diff changeset
207
23573
1b4f4ec53b4a use new script to tag fixed bugs in tests
John W. Eaton <jwe@octave.org>
parents: 23572
diff changeset
208 %!testif HAVE_QHULL <*40996>
18203
5646f999245d voronoi.m: Add special handling for 2-point input (bug #40996).
Rik <rik@octave.org>
parents: 18201
diff changeset
209 %! ## Special case of just 2 points
5646f999245d voronoi.m: Add special handling for 2-point input (bug #40996).
Rik <rik@octave.org>
parents: 18201
diff changeset
210 %! x = [0 1]; y = [1 0];
5646f999245d voronoi.m: Add special handling for 2-point input (bug #40996).
Rik <rik@octave.org>
parents: 18201
diff changeset
211 %! [vx, vy] = voronoi (x,y);
5646f999245d voronoi.m: Add special handling for 2-point input (bug #40996).
Rik <rik@octave.org>
parents: 18201
diff changeset
212 %! assert (vx, [-0.7; 1.7], eps);
5646f999245d voronoi.m: Add special handling for 2-point input (bug #40996).
Rik <rik@octave.org>
parents: 18201
diff changeset
213 %! assert (vy, [-0.7; 1.7], eps);
13746
7ff0bdc3dc4c Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents: 12931
diff changeset
214
23573
1b4f4ec53b4a use new script to tag fixed bugs in tests
John W. Eaton <jwe@octave.org>
parents: 23572
diff changeset
215 %!testif HAVE_QHULL <*38295>
22697
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
216 %! x = [1,2,3]; y = [2,3,1];
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
217 %! [vx, vy] = voronoi (x,y);
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
218 %! assert (columns (vx), 3);
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
219
23573
1b4f4ec53b4a use new script to tag fixed bugs in tests
John W. Eaton <jwe@octave.org>
parents: 23572
diff changeset
220 %!testif HAVE_QHULL <*37270>
22697
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
221 %! ## Duplicate points can cause an internal error
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
222 %! x = [1,2,3, 3]; y = [2,3,1, 1];
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
223 %! [vx, vy] = voronoi (x,y);
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
224
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
225
19833
9fc020886ae9 maint: Clean up m-files to follow Octave coding conventions.
Rik <rik@octave.org>
parents: 19697
diff changeset
226 ## Input validation tests
28896
90fea9cc9caa test: Add expected error message <Invalid call> to BIST tests for nargin.
Rik <rik@octave.org>
parents: 27978
diff changeset
227 %!error <Invalid call> voronoi ()
18193
31d8e19a745d voronoi.m: Add input validation test for 2 points (bug #40996)
Rik <rik@octave.org>
parents: 17744
diff changeset
228 %!error voronoi (ones (3,1))
20835
14cd86258b3d use 'invalid' instead of 'bogus' in source files
John W. Eaton <jwe@octave.org>
parents: 20735
diff changeset
229 %!error voronoi (ones (3,1), ones (3,1), "invalid1", "invalid2", "invalid3")
18193
31d8e19a745d voronoi.m: Add input validation test for 2 points (bug #40996)
Rik <rik@octave.org>
parents: 17744
diff changeset
230 %!error <HAX argument must be an axes object> voronoi (0, ones (3,1), ones (3,1))
31d8e19a745d voronoi.m: Add input validation test for 2 points (bug #40996)
Rik <rik@octave.org>
parents: 17744
diff changeset
231 %!error <X and Y must be vectors of the same length> voronoi (ones (3,1), ones (4,1))
22697
8acad59ecec0 voronoi.m: Overhaul function to produce correct number of edges (bug #38295).
Rik <rik@octave.org>
parents: 22323
diff changeset
232 %!error <minimum of 2 points required> voronoi (2.5, 3.5)