|
6823
|
1 /* |
|
|
2 |
|
|
3 Copyright (C) 2000 Kai Habel |
|
|
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 |
|
|
9 Free Software Foundation; either version 2, or (at your option) any |
|
|
10 later version. |
|
|
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 |
|
|
18 along with Octave; see the file COPYING. If not, write to the Free |
|
|
19 Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA |
|
|
20 02110-1301, USA. |
|
|
21 |
|
|
22 */ |
|
|
23 |
|
|
24 /* |
|
|
25 20. Augiust 2000 - Kai Habel: first release |
|
|
26 */ |
|
|
27 |
|
|
28 /* |
|
|
29 2003-12-14 Rafael Laboissiere <rafael@laboissiere.net> |
|
|
30 Added optional second argument to pass options to the underlying |
|
|
31 qhull command |
|
|
32 */ |
|
|
33 |
|
|
34 #include <iostream> |
|
|
35 #ifdef HAVE_CONFIG_H |
|
|
36 #include <config.h> |
|
|
37 #endif |
|
|
38 #include "oct.h" |
|
|
39 #include "Cell.h" |
|
|
40 |
|
|
41 #ifdef HAVE_QHULL |
|
|
42 extern "C" { |
|
|
43 #include <qhull/qhull_a.h> |
|
|
44 } |
|
|
45 |
|
|
46 #ifdef NEED_QHULL_VERSION |
|
|
47 char qh_version[] = "__voronoi__.oct 2007-07-24"; |
|
|
48 #endif |
|
|
49 #endif |
|
|
50 |
|
|
51 DEFUN_DLD (__voronoi__, args, , |
|
|
52 "-*- texinfo -*-\n\ |
|
|
53 @deftypefn {Loadable Function} {@var{tri} =} __voronoi__ (@var{point})\n\ |
|
|
54 @deftypefnx {Loadable Function} {@var{tri} =} __voronoi__ (@var{point}, @var{options})\n\ |
|
|
55 Internal function for voronoi.\n\ |
|
|
56 @end deftypefn") |
|
|
57 { |
|
|
58 octave_value_list retval; |
|
|
59 #ifdef HAVE_QHULL |
|
|
60 retval(0) = 0.0; |
|
|
61 |
|
|
62 int nargin = args.length(); |
|
|
63 if (nargin < 1 || nargin > 2) |
|
|
64 { |
|
|
65 print_usage (); |
|
|
66 return retval; |
|
|
67 } |
|
|
68 |
|
6880
|
69 const char *options; |
|
|
70 |
|
6823
|
71 if (nargin == 2) |
|
|
72 { |
|
|
73 if (!args (1).is_string ()) |
|
|
74 { |
|
|
75 error ("__voronoi__: second argument must be a string"); |
|
|
76 return retval; |
|
|
77 } |
|
|
78 options = args (1).string_value().c_str(); |
|
|
79 } |
|
|
80 else |
|
|
81 options = ""; |
|
|
82 |
|
|
83 Matrix p(args(0).matrix_value()); |
|
|
84 |
|
|
85 const octave_idx_type dim = p.columns(); |
|
|
86 const octave_idx_type np = p.rows(); |
|
|
87 p = p.transpose(); |
|
|
88 |
|
|
89 double *pt_array = p.fortran_vec(); |
|
|
90 //double pt_array[dim * np]; |
|
|
91 //for (int i = 0; i < np; i++) |
|
|
92 // { |
|
|
93 // for (int j = 0; j < dim; j++) |
|
|
94 // { |
|
|
95 // pt_array[j+i*dim] = p(i,j); |
|
|
96 // } |
|
|
97 // } |
|
|
98 |
|
|
99 boolT ismalloc = false; |
|
|
100 |
|
6880
|
101 OCTAVE_LOCAL_BUFFER(char, flags, 250); |
|
|
102 |
|
6823
|
103 // hmm lot's of options for qhull here |
|
|
104 sprintf(flags,"qhull v Fv T0 %s",options); |
|
6880
|
105 |
|
|
106 // If you want some debugging information replace the NULL |
|
|
107 // pointer with outfile. |
|
|
108 FILE *outfile = stdout; |
|
|
109 FILE *errfile = stderr; |
|
|
110 |
|
6823
|
111 if (!qh_new_qhull (dim, np, pt_array, ismalloc, flags, NULL, errfile)) |
|
|
112 { |
|
|
113 |
|
|
114 // If you want some debugging information replace the NULL |
|
|
115 // pointer with outfile. |
|
|
116 facetT *facet; |
|
|
117 vertexT *vertex; |
|
|
118 |
|
|
119 octave_idx_type i = 0, n = 1, k = 0, m = 0, fidx = 0, j = 0, r = 0; |
|
|
120 OCTAVE_LOCAL_BUFFER(octave_idx_type, ni, np); |
|
|
121 |
|
|
122 for (i = 0; i < np; i++) |
|
|
123 ni[i] = 0; |
|
|
124 qh_setvoronoi_all(); |
|
|
125 bool infinity_seen = false; |
|
|
126 facetT *neighbor,**neighborp; |
|
|
127 coordT *voronoi_vertex; |
|
|
128 FORALLfacets |
|
|
129 { |
|
|
130 facet->seen = false; |
|
|
131 } |
|
|
132 FORALLvertices |
|
|
133 { |
|
|
134 if (qh hull_dim == 3) |
|
|
135 qh_order_vertexneighbors(vertex); |
|
|
136 infinity_seen = false; |
|
|
137 FOREACHneighbor_(vertex) |
|
|
138 { |
|
|
139 if (!neighbor->upperdelaunay) |
|
|
140 { |
|
|
141 if (!neighbor->seen) |
|
|
142 { |
|
|
143 n++; |
|
|
144 neighbor->seen=True; |
|
|
145 } |
|
|
146 ni[k]++; |
|
|
147 } |
|
|
148 else if (!infinity_seen) |
|
|
149 { |
|
|
150 infinity_seen = true; |
|
|
151 ni[k]++; |
|
|
152 } |
|
|
153 } |
|
|
154 k++; |
|
|
155 } |
|
|
156 |
|
|
157 Matrix v(n, dim); |
|
|
158 for (octave_idx_type d = 0; d < dim; d++) |
|
|
159 v(0,d) = octave_Inf; |
|
|
160 |
|
|
161 boolMatrix AtInf(np, 1); |
|
|
162 for (i = 0; i < np; i++) |
|
|
163 AtInf(i) = false; |
|
|
164 octave_value_list F; |
|
|
165 k = 0; |
|
|
166 i = 0; |
|
|
167 FORALLfacets |
|
|
168 { |
|
|
169 facet->seen = false; |
|
|
170 } |
|
|
171 FORALLvertices |
|
|
172 { |
|
|
173 if (qh hull_dim == 3) |
|
|
174 qh_order_vertexneighbors(vertex); |
|
|
175 infinity_seen = false; |
|
|
176 RowVector facet_list(ni[k++]); |
|
|
177 m = 0; |
|
|
178 FOREACHneighbor_(vertex) |
|
|
179 { |
|
|
180 if (neighbor->upperdelaunay) |
|
|
181 { |
|
|
182 if (!infinity_seen) |
|
|
183 { |
|
|
184 infinity_seen = true; |
|
|
185 facet_list(m++) = 1; |
|
|
186 AtInf(j) = true; |
|
|
187 } |
|
|
188 } |
|
|
189 else |
|
|
190 { |
|
|
191 if (!neighbor->seen) |
|
|
192 { |
|
|
193 voronoi_vertex = neighbor->center; |
|
|
194 fidx = neighbor->id; |
|
|
195 i++; |
|
|
196 for (octave_idx_type d = 0; d < dim; d++) |
|
|
197 { |
|
|
198 v(i,d) = *(voronoi_vertex++); |
|
|
199 } |
|
|
200 neighbor->seen = true; |
|
|
201 neighbor->visitid = i; |
|
|
202 } |
|
|
203 facet_list(m++)=neighbor->visitid + 1; |
|
|
204 } |
|
|
205 } |
|
|
206 F(r++) = facet_list; |
|
|
207 j++; |
|
|
208 } |
|
|
209 |
|
|
210 Cell C(r, 1); |
|
|
211 for (i = 0; i < r; i++) |
|
|
212 C.elem (i) = F(i); |
|
|
213 |
|
|
214 retval(0) = v; |
|
|
215 retval(1) = C; |
|
|
216 retval(2) = AtInf; |
|
|
217 |
|
|
218 //free long memory |
|
|
219 qh_freeqhull(!qh_ALL); |
|
|
220 |
|
|
221 //free short memory and memory allocator |
|
|
222 int curlong, totlong; |
|
|
223 qh_memfreeshort (&curlong, &totlong); |
|
|
224 |
|
|
225 if (curlong || totlong) { |
|
|
226 warning("__voronoi__: did not free %d bytes of long memory (%d pieces)", totlong, curlong); |
|
|
227 } |
|
|
228 } |
|
|
229 #else |
|
|
230 error ("__voronoi__: not available in this version of Octave"); |
|
|
231 #endif |
|
|
232 return retval; |
|
|
233 } |
