Mercurial > octave-nkf
annotate src/DLD-FUNCTIONS/__voronoi__.cc @ 13862:6d7e133a4bed
compatibility fixes for __voronoi__
* __voronoi__.cc (F__voronoi__): Use Fv option for Qhull, not FV.
Delete unused variable fidx. Count vertices to get size of NI array.
Skip facets that contain only one point. Always return AtInf. Use a
list of accumulate vertex lists. Pad the cell array of facet vertex
lists with empty matrices if there are fewer facets than points.
author | John W. Eaton <jwe@octave.org> |
---|---|
date | Mon, 14 Nov 2011 04:14:04 -0500 |
parents | 7ff0bdc3dc4c |
children | adf60d6dc1dd |
rev | line source |
---|---|
6823 | 1 /* |
2 | |
11523 | 3 Copyright (C) 2000-2011 Kai Habel |
6823 | 4 |
5 This file is part of Octave. | |
6 | |
7 Octave is free software; you can redistribute it and/or modify it | |
8 under the terms of the GNU General Public License as published by the | |
7016 | 9 Free Software Foundation; either version 3 of the License, or (at your |
10 option) any later version. | |
6823 | 11 |
12 Octave is distributed in the hope that it will be useful, but WITHOUT | |
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 for more details. | |
16 | |
17 You should have received a copy of the GNU General Public License | |
7016 | 18 along with Octave; see the file COPYING. If not, see |
19 <http://www.gnu.org/licenses/>. | |
6823 | 20 |
21 */ | |
22 | |
23 /* | |
24 20. Augiust 2000 - Kai Habel: first release | |
25 */ | |
26 | |
27 /* | |
28 2003-12-14 Rafael Laboissiere <rafael@laboissiere.net> | |
29 Added optional second argument to pass options to the underlying | |
30 qhull command | |
31 */ | |
32 | |
33 #ifdef HAVE_CONFIG_H | |
34 #include <config.h> | |
35 #endif | |
9786
2c279308f6ab
fix includes in some src/DLD-FUNCTIONS files
John W. Eaton <jwe@octave.org>
parents:
9003
diff
changeset
|
36 |
2c279308f6ab
fix includes in some src/DLD-FUNCTIONS files
John W. Eaton <jwe@octave.org>
parents:
9003
diff
changeset
|
37 #include <cstdio> |
2c279308f6ab
fix includes in some src/DLD-FUNCTIONS files
John W. Eaton <jwe@octave.org>
parents:
9003
diff
changeset
|
38 |
13862
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
39 #include <list> |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
40 |
9003
0631d397fbe0
replace lo_ieee_isnan by xisnan, add missing includes
Jaroslav Hajek <highegg@gmail.com>
parents:
8920
diff
changeset
|
41 #include "lo-ieee.h" |
9786
2c279308f6ab
fix includes in some src/DLD-FUNCTIONS files
John W. Eaton <jwe@octave.org>
parents:
9003
diff
changeset
|
42 |
6823 | 43 #include "Cell.h" |
9786
2c279308f6ab
fix includes in some src/DLD-FUNCTIONS files
John W. Eaton <jwe@octave.org>
parents:
9003
diff
changeset
|
44 #include "defun-dld.h" |
2c279308f6ab
fix includes in some src/DLD-FUNCTIONS files
John W. Eaton <jwe@octave.org>
parents:
9003
diff
changeset
|
45 #include "error.h" |
2c279308f6ab
fix includes in some src/DLD-FUNCTIONS files
John W. Eaton <jwe@octave.org>
parents:
9003
diff
changeset
|
46 #include "oct-obj.h" |
6823 | 47 |
48 #ifdef HAVE_QHULL | |
49 extern "C" { | |
50 #include <qhull/qhull_a.h> | |
51 } | |
52 | |
53 #ifdef NEED_QHULL_VERSION | |
54 char qh_version[] = "__voronoi__.oct 2007-07-24"; | |
55 #endif | |
56 #endif | |
57 | |
13862
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
58 DEFUN_DLD (__voronoi__, args, , |
6823 | 59 "-*- texinfo -*-\n\ |
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
60 @deftypefn {Loadable Function} {@var{C}, @var{F} =} __voronoi__ (@var{pts})\n\ |
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
61 @deftypefnx {Loadable Function} {@var{C}, @var{F} =} __voronoi__ (@var{pts}, @var{options})\n\ |
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
62 @deftypefnx {Loadable Function} {@var{C}, @var{F}, @var{Inf_Pts} =} __voronoi__ (@dots{})\n\ |
6945 | 63 Undocumented internal function.\n\ |
6823 | 64 @end deftypefn") |
65 { | |
66 octave_value_list retval; | |
6945 | 67 |
6823 | 68 #ifdef HAVE_QHULL |
6945 | 69 |
6823 | 70 retval(0) = 0.0; |
71 | |
6945 | 72 int nargin = args.length (); |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
73 if (nargin < 1 || nargin > 2) |
6823 | 74 { |
75 print_usage (); | |
76 return retval; | |
77 } | |
78 | |
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
79 std::string options = ""; |
6880 | 80 |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
81 if (nargin == 2) |
6823 | 82 { |
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
83 if (args(1).is_string ()) |
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
84 options = args(1).string_value (); |
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
85 else if (args(1).is_empty ()) |
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
86 ; // Use default options |
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
87 else if (args(1).is_cellstr ()) |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
88 { |
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
89 options = ""; |
13203
b6aba5b4edb1
voronoin: accept options as a cell array of character strings
John W. Eaton <jwe@octave.org>
parents:
12805
diff
changeset
|
90 Array<std::string> tmp = args(1).cellstr_value (); |
b6aba5b4edb1
voronoin: accept options as a cell array of character strings
John W. Eaton <jwe@octave.org>
parents:
12805
diff
changeset
|
91 |
b6aba5b4edb1
voronoin: accept options as a cell array of character strings
John W. Eaton <jwe@octave.org>
parents:
12805
diff
changeset
|
92 for (octave_idx_type i = 0; i < tmp.numel (); i++) |
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
93 options += tmp(i) + " "; |
13203
b6aba5b4edb1
voronoin: accept options as a cell array of character strings
John W. Eaton <jwe@octave.org>
parents:
12805
diff
changeset
|
94 } |
b6aba5b4edb1
voronoin: accept options as a cell array of character strings
John W. Eaton <jwe@octave.org>
parents:
12805
diff
changeset
|
95 else |
b6aba5b4edb1
voronoin: accept options as a cell array of character strings
John W. Eaton <jwe@octave.org>
parents:
12805
diff
changeset
|
96 { |
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
97 error ("__voronoi__: OPTIONS argument must be a string, cell array of strings, or empty"); |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
98 return retval; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
99 } |
6823 | 100 } |
101 | |
6945 | 102 Matrix p (args(0).matrix_value ()); |
103 const octave_idx_type dim = p.columns (); | |
104 const octave_idx_type np = p.rows (); | |
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
105 |
6945 | 106 p = p.transpose (); |
107 double *pt_array = p.fortran_vec (); | |
108 | |
6823 | 109 boolT ismalloc = false; |
110 | |
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
111 // Replace the 0 pointer with stdout for debugging information |
6945 | 112 FILE *outfile = 0; |
6880 | 113 FILE *errfile = stderr; |
114 | |
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
115 // Qhull flags argument is not const char* |
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
116 OCTAVE_LOCAL_BUFFER (char, flags, 12 + options.length ()); |
13203
b6aba5b4edb1
voronoin: accept options as a cell array of character strings
John W. Eaton <jwe@octave.org>
parents:
12805
diff
changeset
|
117 |
13862
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
118 sprintf (flags, "qhull v Fv %s", options.c_str ()); |
13203
b6aba5b4edb1
voronoin: accept options as a cell array of character strings
John W. Eaton <jwe@octave.org>
parents:
12805
diff
changeset
|
119 |
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
120 int exitcode = qh_new_qhull (dim, np, pt_array, |
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
121 ismalloc, flags, outfile, errfile); |
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
122 if (! exitcode) |
6823 | 123 { |
124 facetT *facet; | |
125 vertexT *vertex; | |
126 | |
13862
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
127 octave_idx_type i = 0, n = 1, k = 0, m = 0, j = 0, r = 0; |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
128 |
13862
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
129 // Count number of vertices for size of NI. FIXME -- does Qhull |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
130 // have a way to query this value directly? |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
131 octave_idx_type nv = 0; |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
132 FORALLvertices |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
133 { |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
134 nv++; |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
135 } |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
136 |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
137 OCTAVE_LOCAL_BUFFER (octave_idx_type, ni, nv); |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
138 |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
139 for (i = 0; i < nv; i++) |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
140 ni[i] = 0; |
13862
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
141 |
6945 | 142 qh_setvoronoi_all (); |
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
143 |
6823 | 144 bool infinity_seen = false; |
6945 | 145 facetT *neighbor, **neighborp; |
6823 | 146 coordT *voronoi_vertex; |
6945 | 147 |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
148 FORALLfacets |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
149 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
150 facet->seen = false; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
151 } |
6945 | 152 |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
153 FORALLvertices |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
154 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
155 if (qh hull_dim == 3) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
156 qh_order_vertexneighbors (vertex); |
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
157 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
158 infinity_seen = false; |
6945 | 159 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
160 FOREACHneighbor_ (vertex) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
161 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
162 if (! neighbor->upperdelaunay) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
163 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
164 if (! neighbor->seen) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
165 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
166 n++; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
167 neighbor->seen = true; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
168 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
169 ni[k]++; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
170 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
171 else if (! infinity_seen) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
172 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
173 infinity_seen = true; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
174 ni[k]++; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
175 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
176 } |
13862
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
177 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
178 k++; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
179 } |
6823 | 180 |
6945 | 181 Matrix v (n, dim); |
6823 | 182 for (octave_idx_type d = 0; d < dim; d++) |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
183 v(0,d) = octave_Inf; |
6823 | 184 |
13862
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
185 boolMatrix AtInf (nv, 1, false); |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
186 std::list<RowVector> F; |
6823 | 187 k = 0; |
188 i = 0; | |
6945 | 189 |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
190 FORALLfacets |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
191 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
192 facet->seen = false; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
193 } |
6945 | 194 |
6823 | 195 FORALLvertices |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
196 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
197 if (qh hull_dim == 3) |
13862
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
198 qh_order_vertexneighbors (vertex); |
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
199 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
200 infinity_seen = false; |
13862
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
201 |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
202 octave_idx_type n_vertices = ni[k++]; |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
203 |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
204 // Qhull seems to sometimes produce "facets" with a single |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
205 // vertex. Is that a bug? How can a facet have just one |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
206 // vertex? Let's skip it. |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
207 |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
208 if (n_vertices == 1) |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
209 continue; |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
210 |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
211 RowVector facet_list (n_vertices); |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
212 m = 0; |
6945 | 213 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
214 FOREACHneighbor_(vertex) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
215 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
216 if (neighbor->upperdelaunay) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
217 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
218 if (! infinity_seen) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
219 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
220 infinity_seen = true; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
221 facet_list(m++) = 1; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
222 AtInf(j) = true; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
223 } |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
224 } |
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
225 else |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
226 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
227 if (! neighbor->seen) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
228 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
229 voronoi_vertex = neighbor->center; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
230 i++; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
231 for (octave_idx_type d = 0; d < dim; d++) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
232 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
233 v(i,d) = *(voronoi_vertex++); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
234 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
235 neighbor->seen = true; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
236 neighbor->visitid = i; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
237 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
238 facet_list(m++) = neighbor->visitid + 1; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
239 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
240 } |
13862
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
241 F.push_back (facet_list); |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
242 j++; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9786
diff
changeset
|
243 } |
6823 | 244 |
13862
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
245 // For compatibility with Matlab, pad the cell array of vertex |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
246 // lists with empty matrices if there are fewer facets than |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
247 // points. |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
248 octave_idx_type f_len = F.size (); |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
249 Cell C(np > f_len ? np : f_len, 1); |
6823 | 250 |
13862
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
251 i = 0; |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
252 for (std::list<RowVector>::const_iterator it = F.begin (); |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
253 it != F.end (); it++) |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
254 C.elem (i++) = *it; |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
255 |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
256 F.clear (); |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
257 |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
258 AtInf.resize (f_len, 1); |
6d7e133a4bed
compatibility fixes for __voronoi__
John W. Eaton <jwe@octave.org>
parents:
13746
diff
changeset
|
259 retval(2) = AtInf; |
6823 | 260 retval(1) = C; |
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
261 retval(0) = v; |
6823 | 262 } |
6945 | 263 else |
264 error ("__voronoi__: qhull failed"); | |
265 | |
13746
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
266 // free memory from Qhull |
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
267 qh_freeqhull (! qh_ALL); |
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
268 |
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
269 int curlong, totlong; |
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
270 qh_memfreeshort (&curlong, &totlong); |
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
271 |
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
272 if (curlong || totlong) |
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
273 warning ("__voronoi__: did not free %d bytes of long memory (%d pieces)", |
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
274 totlong, curlong); |
7ff0bdc3dc4c
Revamp geometry functions dependent on Qhull (Bug #34604, Bug #33346)
Rik <octave@nomad.inbox5.com>
parents:
13203
diff
changeset
|
275 |
6823 | 276 #else |
277 error ("__voronoi__: not available in this version of Octave"); | |
278 #endif | |
6945 | 279 |
6823 | 280 return retval; |
281 } | |
12805
3641167e5b75
codesprint: *.cc helper functions do not need tests
Rik <octave@nomad.inbox5.com>
parents:
11586
diff
changeset
|
282 |
3641167e5b75
codesprint: *.cc helper functions do not need tests
Rik <octave@nomad.inbox5.com>
parents:
11586
diff
changeset
|
283 /* |
3641167e5b75
codesprint: *.cc helper functions do not need tests
Rik <octave@nomad.inbox5.com>
parents:
11586
diff
changeset
|
284 |
3641167e5b75
codesprint: *.cc helper functions do not need tests
Rik <octave@nomad.inbox5.com>
parents:
11586
diff
changeset
|
285 ## No test needed for internal helper function. |
3641167e5b75
codesprint: *.cc helper functions do not need tests
Rik <octave@nomad.inbox5.com>
parents:
11586
diff
changeset
|
286 %!assert (1) |
3641167e5b75
codesprint: *.cc helper functions do not need tests
Rik <octave@nomad.inbox5.com>
parents:
11586
diff
changeset
|
287 |
3641167e5b75
codesprint: *.cc helper functions do not need tests
Rik <octave@nomad.inbox5.com>
parents:
11586
diff
changeset
|
288 */ |