1 /*<html><pre> -<a href="qh-stat.htm"
2 >-------------------------------</a><a name="TOP">-</a>
3
4 stat.c
5 contains all statistics that are collected for qhull
6
7 see qh-stat.htm and stat.h
8
9 Copyright (c) 1993-2012 The Geometry Center.
10 $Id: //main/2011/qhull/src/libqhull/stat.c#3 $$Change: 1464 $
11 $DateTime: 2012/01/25 22:58:41 $$Author: bbarber $
12 */
13
14 #include "qhull_a.h"
15
16 /*============ global data structure ==========*/
17
18 #if qh_QHpointer
19 qhstatT *qh_qhstat=NULL; /* global data structure */
20 #else
21 qhstatT qh_qhstat; /* add "={0}" if this causes a compiler error */
22 #endif
23
24 /*========== functions in alphabetic order ================*/
25
26 /*-<a href="qh-stat.htm#TOC"
27 >-------------------------------</a><a name="allstatA">-</a>
28
29 qh_allstatA()
30 define statistics in groups of 20
31
32 notes:
33 (otherwise, 'gcc -O2' uses too much memory)
34 uses qhstat.next
35 */
qh_allstatA(void)36 void qh_allstatA(void) {
37
38 /* zdef_(type,name,doc,average) */
39 zzdef_(zdoc, Zdoc2, "precision statistics", -1);
40 zdef_(zinc, Znewvertex, NULL, -1);
41 zdef_(wadd, Wnewvertex, "ave. distance of a new vertex to a facet(!0s)", Znewvertex);
42 zzdef_(wmax, Wnewvertexmax, "max. distance of a new vertex to a facet", -1);
43 zdef_(wmax, Wvertexmax, "max. distance of an output vertex to a facet", -1);
44 zdef_(wmin, Wvertexmin, "min. distance of an output vertex to a facet", -1);
45 zdef_(wmin, Wmindenom, "min. denominator in hyperplane computation", -1);
46
47 qhstat precision= qhstat next; /* call qh_precision for each of these */
48 zzdef_(zdoc, Zdoc3, "precision problems (corrected unless 'Q0' or an error)", -1);
49 zzdef_(zinc, Zcoplanarridges, "coplanar half ridges in output", -1);
50 zzdef_(zinc, Zconcaveridges, "concave half ridges in output", -1);
51 zzdef_(zinc, Zflippedfacets, "flipped facets", -1);
52 zzdef_(zinc, Zcoplanarhorizon, "coplanar horizon facets for new vertices", -1);
53 zzdef_(zinc, Zcoplanarpart, "coplanar points during partitioning", -1);
54 zzdef_(zinc, Zminnorm, "degenerate hyperplanes recomputed with gaussian elimination", -1);
55 zzdef_(zinc, Znearlysingular, "nearly singular or axis-parallel hyperplanes", -1);
56 zzdef_(zinc, Zback0, "zero divisors during back substitute", -1);
57 zzdef_(zinc, Zgauss0, "zero divisors during gaussian elimination", -1);
58 zzdef_(zinc, Zmultiridge, "ridges with multiple neighbors", -1);
59 }
qh_allstatB(void)60 void qh_allstatB(void) {
61 zzdef_(zdoc, Zdoc1, "summary information", -1);
62 zdef_(zinc, Zvertices, "number of vertices in output", -1);
63 zdef_(zinc, Znumfacets, "number of facets in output", -1);
64 zdef_(zinc, Znonsimplicial, "number of non-simplicial facets in output", -1);
65 zdef_(zinc, Znowsimplicial, "number of simplicial facets that were merged", -1);
66 zdef_(zinc, Znumridges, "number of ridges in output", -1);
67 zdef_(zadd, Znumridges, "average number of ridges per facet", Znumfacets);
68 zdef_(zmax, Zmaxridges, "maximum number of ridges", -1);
69 zdef_(zadd, Znumneighbors, "average number of neighbors per facet", Znumfacets);
70 zdef_(zmax, Zmaxneighbors, "maximum number of neighbors", -1);
71 zdef_(zadd, Znumvertices, "average number of vertices per facet", Znumfacets);
72 zdef_(zmax, Zmaxvertices, "maximum number of vertices", -1);
73 zdef_(zadd, Znumvneighbors, "average number of neighbors per vertex", Zvertices);
74 zdef_(zmax, Zmaxvneighbors, "maximum number of neighbors", -1);
75 zdef_(wadd, Wcpu, "cpu seconds for qhull after input", -1);
76 zdef_(zinc, Ztotvertices, "vertices created altogether", -1);
77 zzdef_(zinc, Zsetplane, "facets created altogether", -1);
78 zdef_(zinc, Ztotridges, "ridges created altogether", -1);
79 zdef_(zinc, Zpostfacets, "facets before post merge", -1);
80 zdef_(zadd, Znummergetot, "average merges per facet(at most 511)", Znumfacets);
81 zdef_(zmax, Znummergemax, " maximum merges for a facet(at most 511)", -1);
82 zdef_(zinc, Zangle, NULL, -1);
83 zdef_(wadd, Wangle, "average angle(cosine) of facet normals for all ridges", Zangle);
84 zdef_(wmax, Wanglemax, " maximum angle(cosine) of facet normals across a ridge", -1);
85 zdef_(wmin, Wanglemin, " minimum angle(cosine) of facet normals across a ridge", -1);
86 zdef_(wadd, Wareatot, "total area of facets", -1);
87 zdef_(wmax, Wareamax, " maximum facet area", -1);
88 zdef_(wmin, Wareamin, " minimum facet area", -1);
89 }
qh_allstatC(void)90 void qh_allstatC(void) {
91 zdef_(zdoc, Zdoc9, "build hull statistics", -1);
92 zzdef_(zinc, Zprocessed, "points processed", -1);
93 zzdef_(zinc, Zretry, "retries due to precision problems", -1);
94 zdef_(wmax, Wretrymax, " max. random joggle", -1);
95 zdef_(zmax, Zmaxvertex, "max. vertices at any one time", -1);
96 zdef_(zinc, Ztotvisible, "ave. visible facets per iteration", Zprocessed);
97 zdef_(zinc, Zinsidevisible, " ave. visible facets without an horizon neighbor", Zprocessed);
98 zdef_(zadd, Zvisfacettot, " ave. facets deleted per iteration", Zprocessed);
99 zdef_(zmax, Zvisfacetmax, " maximum", -1);
100 zdef_(zadd, Zvisvertextot, "ave. visible vertices per iteration", Zprocessed);
101 zdef_(zmax, Zvisvertexmax, " maximum", -1);
102 zdef_(zinc, Ztothorizon, "ave. horizon facets per iteration", Zprocessed);
103 zdef_(zadd, Znewfacettot, "ave. new or merged facets per iteration", Zprocessed);
104 zdef_(zmax, Znewfacetmax, " maximum(includes initial simplex)", -1);
105 zdef_(wadd, Wnewbalance, "average new facet balance", Zprocessed);
106 zdef_(wadd, Wnewbalance2, " standard deviation", -1);
107 zdef_(wadd, Wpbalance, "average partition balance", Zpbalance);
108 zdef_(wadd, Wpbalance2, " standard deviation", -1);
109 zdef_(zinc, Zpbalance, " number of trials", -1);
110 zdef_(zinc, Zsearchpoints, "searches of all points for initial simplex", -1);
111 zdef_(zinc, Zdetsimplex, "determinants computed(area & initial hull)", -1);
112 zdef_(zinc, Znoarea, "determinants not computed because vertex too low", -1);
113 zdef_(zinc, Znotmax, "points ignored(!above max_outside)", -1);
114 zdef_(zinc, Znotgood, "points ignored(!above a good facet)", -1);
115 zdef_(zinc, Znotgoodnew, "points ignored(didn't create a good new facet)", -1);
116 zdef_(zinc, Zgoodfacet, "good facets found", -1);
117 zzdef_(zinc, Znumvisibility, "distance tests for facet visibility", -1);
118 zdef_(zinc, Zdistvertex, "distance tests to report minimum vertex", -1);
119 zzdef_(zinc, Ztotcheck, "points checked for facets' outer planes", -1);
120 zzdef_(zinc, Zcheckpart, " ave. distance tests per check", Ztotcheck);
121 }
qh_allstatD(void)122 void qh_allstatD(void) {
123 zdef_(zinc, Zvisit, "resets of visit_id", -1);
124 zdef_(zinc, Zvvisit, " resets of vertex_visit", -1);
125 zdef_(zmax, Zvisit2max, " max visit_id/2", -1);
126 zdef_(zmax, Zvvisit2max, " max vertex_visit/2", -1);
127
128 zdef_(zdoc, Zdoc4, "partitioning statistics(see previous for outer planes)", -1);
129 zzdef_(zadd, Zdelvertextot, "total vertices deleted", -1);
130 zdef_(zmax, Zdelvertexmax, " maximum vertices deleted per iteration", -1);
131 zdef_(zinc, Zfindbest, "calls to findbest", -1);
132 zdef_(zadd, Zfindbesttot, " ave. facets tested", Zfindbest);
133 zdef_(zmax, Zfindbestmax, " max. facets tested", -1);
134 zdef_(zadd, Zfindcoplanar, " ave. coplanar search", Zfindbest);
135 zdef_(zinc, Zfindnew, "calls to findbestnew", -1);
136 zdef_(zadd, Zfindnewtot, " ave. facets tested", Zfindnew);
137 zdef_(zmax, Zfindnewmax, " max. facets tested", -1);
138 zdef_(zinc, Zfindnewjump, " ave. clearly better", Zfindnew);
139 zdef_(zinc, Zfindnewsharp, " calls due to qh_sharpnewfacets", -1);
140 zdef_(zinc, Zfindhorizon, "calls to findhorizon", -1);
141 zdef_(zadd, Zfindhorizontot, " ave. facets tested", Zfindhorizon);
142 zdef_(zmax, Zfindhorizonmax, " max. facets tested", -1);
143 zdef_(zinc, Zfindjump, " ave. clearly better", Zfindhorizon);
144 zdef_(zinc, Zparthorizon, " horizon facets better than bestfacet", -1);
145 zdef_(zinc, Zpartangle, "angle tests for repartitioned coplanar points", -1);
146 zdef_(zinc, Zpartflip, " repartitioned coplanar points for flipped orientation", -1);
147 }
qh_allstatE(void)148 void qh_allstatE(void) {
149 zdef_(zinc, Zpartinside, "inside points", -1);
150 zdef_(zinc, Zpartnear, " inside points kept with a facet", -1);
151 zdef_(zinc, Zcoplanarinside, " inside points that were coplanar with a facet", -1);
152 zdef_(zinc, Zbestlower, "calls to findbestlower", -1);
153 zdef_(zinc, Zbestlowerv, " with search of vertex neighbors", -1);
154 zdef_(wadd, Wmaxout, "difference in max_outside at final check", -1);
155 zzdef_(zinc, Zpartitionall, "distance tests for initial partition", -1);
156 zdef_(zinc, Ztotpartition, "partitions of a point", -1);
157 zzdef_(zinc, Zpartition, "distance tests for partitioning", -1);
158 zzdef_(zinc, Zdistcheck, "distance tests for checking flipped facets", -1);
159 zzdef_(zinc, Zdistconvex, "distance tests for checking convexity", -1);
160 zdef_(zinc, Zdistgood, "distance tests for checking good point", -1);
161 zdef_(zinc, Zdistio, "distance tests for output", -1);
162 zdef_(zinc, Zdiststat, "distance tests for statistics", -1);
163 zdef_(zinc, Zdistplane, "total number of distance tests", -1);
164 zdef_(zinc, Ztotpartcoplanar, "partitions of coplanar points or deleted vertices", -1);
165 zzdef_(zinc, Zpartcoplanar, " distance tests for these partitions", -1);
166 zdef_(zinc, Zcomputefurthest, "distance tests for computing furthest", -1);
167 }
qh_allstatE2(void)168 void qh_allstatE2(void) {
169 zdef_(zdoc, Zdoc5, "statistics for matching ridges", -1);
170 zdef_(zinc, Zhashlookup, "total lookups for matching ridges of new facets", -1);
171 zdef_(zinc, Zhashtests, "average number of tests to match a ridge", Zhashlookup);
172 zdef_(zinc, Zhashridge, "total lookups of subridges(duplicates and boundary)", -1);
173 zdef_(zinc, Zhashridgetest, "average number of tests per subridge", Zhashridge);
174 zdef_(zinc, Zdupsame, "duplicated ridges in same merge cycle", -1);
175 zdef_(zinc, Zdupflip, "duplicated ridges with flipped facets", -1);
176
177 zdef_(zdoc, Zdoc6, "statistics for determining merges", -1);
178 zdef_(zinc, Zangletests, "angles computed for ridge convexity", -1);
179 zdef_(zinc, Zbestcentrum, "best merges used centrum instead of vertices",-1);
180 zzdef_(zinc, Zbestdist, "distance tests for best merge", -1);
181 zzdef_(zinc, Zcentrumtests, "distance tests for centrum convexity", -1);
182 zzdef_(zinc, Zdistzero, "distance tests for checking simplicial convexity", -1);
183 zdef_(zinc, Zcoplanarangle, "coplanar angles in getmergeset", -1);
184 zdef_(zinc, Zcoplanarcentrum, "coplanar centrums in getmergeset", -1);
185 zdef_(zinc, Zconcaveridge, "concave ridges in getmergeset", -1);
186 }
qh_allstatF(void)187 void qh_allstatF(void) {
188 zdef_(zdoc, Zdoc7, "statistics for merging", -1);
189 zdef_(zinc, Zpremergetot, "merge iterations", -1);
190 zdef_(zadd, Zmergeinittot, "ave. initial non-convex ridges per iteration", Zpremergetot);
191 zdef_(zadd, Zmergeinitmax, " maximum", -1);
192 zdef_(zadd, Zmergesettot, " ave. additional non-convex ridges per iteration", Zpremergetot);
193 zdef_(zadd, Zmergesetmax, " maximum additional in one pass", -1);
194 zdef_(zadd, Zmergeinittot2, "initial non-convex ridges for post merging", -1);
195 zdef_(zadd, Zmergesettot2, " additional non-convex ridges", -1);
196 zdef_(wmax, Wmaxoutside, "max distance of vertex or coplanar point above facet(w/roundoff)", -1);
197 zdef_(wmin, Wminvertex, "max distance of merged vertex below facet(or roundoff)", -1);
198 zdef_(zinc, Zwidefacet, "centrums frozen due to a wide merge", -1);
199 zdef_(zinc, Zwidevertices, "centrums frozen due to extra vertices", -1);
200 zzdef_(zinc, Ztotmerge, "total number of facets or cycles of facets merged", -1);
201 zdef_(zinc, Zmergesimplex, "merged a simplex", -1);
202 zdef_(zinc, Zonehorizon, "simplices merged into coplanar horizon", -1);
203 zzdef_(zinc, Zcyclehorizon, "cycles of facets merged into coplanar horizon", -1);
204 zzdef_(zadd, Zcyclefacettot, " ave. facets per cycle", Zcyclehorizon);
205 zdef_(zmax, Zcyclefacetmax, " max. facets", -1);
206 zdef_(zinc, Zmergeintohorizon, "new facets merged into horizon", -1);
207 zdef_(zinc, Zmergenew, "new facets merged", -1);
208 zdef_(zinc, Zmergehorizon, "horizon facets merged into new facets", -1);
209 zdef_(zinc, Zmergevertex, "vertices deleted by merging", -1);
210 zdef_(zinc, Zcyclevertex, "vertices deleted by merging into coplanar horizon", -1);
211 zdef_(zinc, Zdegenvertex, "vertices deleted by degenerate facet", -1);
212 zdef_(zinc, Zmergeflipdup, "merges due to flipped facets in duplicated ridge", -1);
213 zdef_(zinc, Zneighbor, "merges due to redundant neighbors", -1);
214 zdef_(zadd, Ztestvneighbor, "non-convex vertex neighbors", -1);
215 }
qh_allstatG(void)216 void qh_allstatG(void) {
217 zdef_(zinc, Zacoplanar, "merges due to angle coplanar facets", -1);
218 zdef_(wadd, Wacoplanartot, " average merge distance", Zacoplanar);
219 zdef_(wmax, Wacoplanarmax, " maximum merge distance", -1);
220 zdef_(zinc, Zcoplanar, "merges due to coplanar facets", -1);
221 zdef_(wadd, Wcoplanartot, " average merge distance", Zcoplanar);
222 zdef_(wmax, Wcoplanarmax, " maximum merge distance", -1);
223 zdef_(zinc, Zconcave, "merges due to concave facets", -1);
224 zdef_(wadd, Wconcavetot, " average merge distance", Zconcave);
225 zdef_(wmax, Wconcavemax, " maximum merge distance", -1);
226 zdef_(zinc, Zavoidold, "coplanar/concave merges due to avoiding old merge", -1);
227 zdef_(wadd, Wavoidoldtot, " average merge distance", Zavoidold);
228 zdef_(wmax, Wavoidoldmax, " maximum merge distance", -1);
229 zdef_(zinc, Zdegen, "merges due to degenerate facets", -1);
230 zdef_(wadd, Wdegentot, " average merge distance", Zdegen);
231 zdef_(wmax, Wdegenmax, " maximum merge distance", -1);
232 zdef_(zinc, Zflipped, "merges due to removing flipped facets", -1);
233 zdef_(wadd, Wflippedtot, " average merge distance", Zflipped);
234 zdef_(wmax, Wflippedmax, " maximum merge distance", -1);
235 zdef_(zinc, Zduplicate, "merges due to duplicated ridges", -1);
236 zdef_(wadd, Wduplicatetot, " average merge distance", Zduplicate);
237 zdef_(wmax, Wduplicatemax, " maximum merge distance", -1);
238 }
qh_allstatH(void)239 void qh_allstatH(void) {
240 zdef_(zdoc, Zdoc8, "renamed vertex statistics", -1);
241 zdef_(zinc, Zrenameshare, "renamed vertices shared by two facets", -1);
242 zdef_(zinc, Zrenamepinch, "renamed vertices in a pinched facet", -1);
243 zdef_(zinc, Zrenameall, "renamed vertices shared by multiple facets", -1);
244 zdef_(zinc, Zfindfail, "rename failures due to duplicated ridges", -1);
245 zdef_(zinc, Zdupridge, " duplicate ridges detected", -1);
246 zdef_(zinc, Zdelridge, "deleted ridges due to renamed vertices", -1);
247 zdef_(zinc, Zdropneighbor, "dropped neighbors due to renamed vertices", -1);
248 zdef_(zinc, Zdropdegen, "degenerate facets due to dropped neighbors", -1);
249 zdef_(zinc, Zdelfacetdup, " facets deleted because of no neighbors", -1);
250 zdef_(zinc, Zremvertex, "vertices removed from facets due to no ridges", -1);
251 zdef_(zinc, Zremvertexdel, " deleted", -1);
252 zdef_(zinc, Zintersectnum, "vertex intersections for locating redundant vertices", -1);
253 zdef_(zinc, Zintersectfail, "intersections failed to find a redundant vertex", -1);
254 zdef_(zinc, Zintersect, "intersections found redundant vertices", -1);
255 zdef_(zadd, Zintersecttot, " ave. number found per vertex", Zintersect);
256 zdef_(zmax, Zintersectmax, " max. found for a vertex", -1);
257 zdef_(zinc, Zvertexridge, NULL, -1);
258 zdef_(zadd, Zvertexridgetot, " ave. number of ridges per tested vertex", Zvertexridge);
259 zdef_(zmax, Zvertexridgemax, " max. number of ridges per tested vertex", -1);
260
261 zdef_(zdoc, Zdoc10, "memory usage statistics(in bytes)", -1);
262 zdef_(zadd, Zmemfacets, "for facets and their normals, neighbor and vertex sets", -1);
263 zdef_(zadd, Zmemvertices, "for vertices and their neighbor sets", -1);
264 zdef_(zadd, Zmempoints, "for input points and outside and coplanar sets",-1);
265 zdef_(zadd, Zmemridges, "for ridges and their vertex sets", -1);
266 } /* allstat */
267
qh_allstatI(void)268 void qh_allstatI(void) {
269 qhstat vridges= qhstat next;
270 zzdef_(zdoc, Zdoc11, "Voronoi ridge statistics", -1);
271 zzdef_(zinc, Zridge, "non-simplicial Voronoi vertices for all ridges", -1);
272 zzdef_(wadd, Wridge, " ave. distance to ridge", Zridge);
273 zzdef_(wmax, Wridgemax, " max. distance to ridge", -1);
274 zzdef_(zinc, Zridgemid, "bounded ridges", -1);
275 zzdef_(wadd, Wridgemid, " ave. distance of midpoint to ridge", Zridgemid);
276 zzdef_(wmax, Wridgemidmax, " max. distance of midpoint to ridge", -1);
277 zzdef_(zinc, Zridgeok, "bounded ridges with ok normal", -1);
278 zzdef_(wadd, Wridgeok, " ave. angle to ridge", Zridgeok);
279 zzdef_(wmax, Wridgeokmax, " max. angle to ridge", -1);
280 zzdef_(zinc, Zridge0, "bounded ridges with near-zero normal", -1);
281 zzdef_(wadd, Wridge0, " ave. angle to ridge", Zridge0);
282 zzdef_(wmax, Wridge0max, " max. angle to ridge", -1);
283
284 zdef_(zdoc, Zdoc12, "Triangulation statistics(Qt)", -1);
285 zdef_(zinc, Ztricoplanar, "non-simplicial facets triangulated", -1);
286 zdef_(zadd, Ztricoplanartot, " ave. new facets created(may be deleted)", Ztricoplanar);
287 zdef_(zmax, Ztricoplanarmax, " max. new facets created", -1);
288 zdef_(zinc, Ztrinull, "null new facets deleted(duplicated vertex)", -1);
289 zdef_(zinc, Ztrimirror, "mirrored pairs of new facets deleted(same vertices)", -1);
290 zdef_(zinc, Ztridegen, "degenerate new facets in output(same ridge)", -1);
291 } /* allstat */
292
293 /*-<a href="qh-stat.htm#TOC"
294 >-------------------------------</a><a name="allstatistics">-</a>
295
296 qh_allstatistics()
297 reset printed flag for all statistics
298 */
qh_allstatistics(void)299 void qh_allstatistics(void) {
300 int i;
301
302 for(i=ZEND; i--; )
303 qhstat printed[i]= False;
304 } /* allstatistics */
305
306 #if qh_KEEPstatistics
307 /*-<a href="qh-stat.htm#TOC"
308 >-------------------------------</a><a name="collectstatistics">-</a>
309
310 qh_collectstatistics()
311 collect statistics for qh.facet_list
312
313 */
qh_collectstatistics(void)314 void qh_collectstatistics(void) {
315 facetT *facet, *neighbor, **neighborp;
316 vertexT *vertex, **vertexp;
317 realT dotproduct, dist;
318 int sizneighbors, sizridges, sizvertices, i;
319
320 qh old_randomdist= qh RANDOMdist;
321 qh RANDOMdist= False;
322 zval_(Zmempoints)= qh num_points * qh normal_size +
323 sizeof(qhT) + sizeof(qhstatT);
324 zval_(Zmemfacets)= 0;
325 zval_(Zmemridges)= 0;
326 zval_(Zmemvertices)= 0;
327 zval_(Zangle)= 0;
328 wval_(Wangle)= 0.0;
329 zval_(Znumridges)= 0;
330 zval_(Znumfacets)= 0;
331 zval_(Znumneighbors)= 0;
332 zval_(Znumvertices)= 0;
333 zval_(Znumvneighbors)= 0;
334 zval_(Znummergetot)= 0;
335 zval_(Znummergemax)= 0;
336 zval_(Zvertices)= qh num_vertices - qh_setsize(qh del_vertices);
337 if (qh MERGING || qh APPROXhull || qh JOGGLEmax < REALmax/2)
338 wmax_(Wmaxoutside, qh max_outside);
339 if (qh MERGING)
340 wmin_(Wminvertex, qh min_vertex);
341 FORALLfacets
342 facet->seen= False;
343 if (qh DELAUNAY) {
344 FORALLfacets {
345 if (facet->upperdelaunay != qh UPPERdelaunay)
346 facet->seen= True; /* remove from angle statistics */
347 }
348 }
349 FORALLfacets {
350 if (facet->visible && qh NEWfacets)
351 continue;
352 sizvertices= qh_setsize(facet->vertices);
353 sizneighbors= qh_setsize(facet->neighbors);
354 sizridges= qh_setsize(facet->ridges);
355 zinc_(Znumfacets);
356 zadd_(Znumvertices, sizvertices);
357 zmax_(Zmaxvertices, sizvertices);
358 zadd_(Znumneighbors, sizneighbors);
359 zmax_(Zmaxneighbors, sizneighbors);
360 zadd_(Znummergetot, facet->nummerge);
361 i= facet->nummerge; /* avoid warnings */
362 zmax_(Znummergemax, i);
363 if (!facet->simplicial) {
364 if (sizvertices == qh hull_dim) {
365 zinc_(Znowsimplicial);
366 }else {
367 zinc_(Znonsimplicial);
368 }
369 }
370 if (sizridges) {
371 zadd_(Znumridges, sizridges);
372 zmax_(Zmaxridges, sizridges);
373 }
374 zadd_(Zmemfacets, sizeof(facetT) + qh normal_size + 2*sizeof(setT)
375 + SETelemsize * (sizneighbors + sizvertices));
376 if (facet->ridges) {
377 zadd_(Zmemridges,
378 sizeof(setT) + SETelemsize * sizridges + sizridges *
379 (sizeof(ridgeT) + sizeof(setT) + SETelemsize * (qh hull_dim-1))/2);
380 }
381 if (facet->outsideset)
382 zadd_(Zmempoints, sizeof(setT) + SETelemsize * qh_setsize(facet->outsideset));
383 if (facet->coplanarset)
384 zadd_(Zmempoints, sizeof(setT) + SETelemsize * qh_setsize(facet->coplanarset));
385 if (facet->seen) /* Delaunay upper envelope */
386 continue;
387 facet->seen= True;
388 FOREACHneighbor_(facet) {
389 if (neighbor == qh_DUPLICATEridge || neighbor == qh_MERGEridge
390 || neighbor->seen || !facet->normal || !neighbor->normal)
391 continue;
392 dotproduct= qh_getangle(facet->normal, neighbor->normal);
393 zinc_(Zangle);
394 wadd_(Wangle, dotproduct);
395 wmax_(Wanglemax, dotproduct)
396 wmin_(Wanglemin, dotproduct)
397 }
398 if (facet->normal) {
399 FOREACHvertex_(facet->vertices) {
400 zinc_(Zdiststat);
401 qh_distplane(vertex->point, facet, &dist);
402 wmax_(Wvertexmax, dist);
403 wmin_(Wvertexmin, dist);
404 }
405 }
406 }
407 FORALLvertices {
408 if (vertex->deleted)
409 continue;
410 zadd_(Zmemvertices, sizeof(vertexT));
411 if (vertex->neighbors) {
412 sizneighbors= qh_setsize(vertex->neighbors);
413 zadd_(Znumvneighbors, sizneighbors);
414 zmax_(Zmaxvneighbors, sizneighbors);
415 zadd_(Zmemvertices, sizeof(vertexT) + SETelemsize * sizneighbors);
416 }
417 }
418 qh RANDOMdist= qh old_randomdist;
419 } /* collectstatistics */
420 #endif /* qh_KEEPstatistics */
421
422 /*-<a href="qh-stat.htm#TOC"
423 >-------------------------------</a><a name="freestatistics">-</a>
424
425 qh_freestatistics( )
426 free memory used for statistics
427 */
qh_freestatistics(void)428 void qh_freestatistics(void) {
429
430 #if qh_QHpointer
431 qh_free(qh_qhstat);
432 qh_qhstat= NULL;
433 #endif
434 } /* freestatistics */
435
436 /*-<a href="qh-stat.htm#TOC"
437 >-------------------------------</a><a name="initstatistics">-</a>
438
439 qh_initstatistics( )
440 allocate and initialize statistics
441
442 notes:
443 uses qh_malloc() instead of qh_memalloc() since mem.c not set up yet
444 NOerrors -- qh_initstatistics can not use qh_errexit(). One first call, qh_memalloc is not initialized. Also invoked by QhullQh().
445 */
qh_initstatistics(void)446 void qh_initstatistics(void) {
447 int i;
448 realT realx;
449 int intx;
450
451 #if qh_QHpointer
452 if(qh_qhstat){ /* qh_initstatistics may be called from Qhull::resetStatistics() */
453 qh_free(qh_qhstat);
454 qh_qhstat= 0;
455 }
456 if (!(qh_qhstat= (qhstatT *)qh_malloc(sizeof(qhstatT)))) {
457 qh_fprintf(qhmem.ferr, 6183, "qhull error (qh_initstatistics): insufficient memory\n");
458 qh_exit(qh_ERRmem); /* can not use qh_errexit() */
459 }
460 #endif
461
462 qhstat next= 0;
463 qh_allstatA();
464 qh_allstatB();
465 qh_allstatC();
466 qh_allstatD();
467 qh_allstatE();
468 qh_allstatE2();
469 qh_allstatF();
470 qh_allstatG();
471 qh_allstatH();
472 qh_allstatI();
473 if (qhstat next > (int)sizeof(qhstat id)) {
474 qh_fprintf(qhmem.ferr, 6184, "qhull error (qh_initstatistics): increase size of qhstat.id[].\n\
475 qhstat.next %d should be <= sizeof(qhstat id) %d\n", qhstat next, (int)sizeof(qhstat id));
476 #if 0 /* for locating error, Znumridges should be duplicated */
477 for(i=0; i < ZEND; i++) {
478 int j;
479 for(j=i+1; j < ZEND; j++) {
480 if (qhstat id[i] == qhstat id[j]) {
481 qh_fprintf(qhmem.ferr, 6185, "qhull error (qh_initstatistics): duplicated statistic %d at indices %d and %d\n",
482 qhstat id[i], i, j);
483 }
484 }
485 }
486 #endif
487 qh_exit(qh_ERRqhull); /* can not use qh_errexit() */
488 }
489 qhstat init[zinc].i= 0;
490 qhstat init[zadd].i= 0;
491 qhstat init[zmin].i= INT_MAX;
492 qhstat init[zmax].i= INT_MIN;
493 qhstat init[wadd].r= 0;
494 qhstat init[wmin].r= REALmax;
495 qhstat init[wmax].r= -REALmax;
496 for(i=0; i < ZEND; i++) {
497 if (qhstat type[i] > ZTYPEreal) {
498 realx= qhstat init[(unsigned char)(qhstat type[i])].r;
499 qhstat stats[i].r= realx;
500 }else if (qhstat type[i] != zdoc) {
501 intx= qhstat init[(unsigned char)(qhstat type[i])].i;
502 qhstat stats[i].i= intx;
503 }
504 }
505 } /* initstatistics */
506
507 /*-<a href="qh-stat.htm#TOC"
508 >-------------------------------</a><a name="newstats">-</a>
509
510 qh_newstats( )
511 returns True if statistics for zdoc
512
513 returns:
514 next zdoc
515 */
qh_newstats(int idx,int * nextindex)516 boolT qh_newstats(int idx, int *nextindex) {
517 boolT isnew= False;
518 int start, i;
519
520 if (qhstat type[qhstat id[idx]] == zdoc)
521 start= idx+1;
522 else
523 start= idx;
524 for(i= start; i < qhstat next && qhstat type[qhstat id[i]] != zdoc; i++) {
525 if (!qh_nostatistic(qhstat id[i]) && !qhstat printed[qhstat id[i]])
526 isnew= True;
527 }
528 *nextindex= i;
529 return isnew;
530 } /* newstats */
531
532 /*-<a href="qh-stat.htm#TOC"
533 >-------------------------------</a><a name="nostatistic">-</a>
534
535 qh_nostatistic( index )
536 true if no statistic to print
537 */
qh_nostatistic(int i)538 boolT qh_nostatistic(int i) {
539
540 if ((qhstat type[i] > ZTYPEreal
541 &&qhstat stats[i].r == qhstat init[(unsigned char)(qhstat type[i])].r)
542 || (qhstat type[i] < ZTYPEreal
543 &&qhstat stats[i].i == qhstat init[(unsigned char)(qhstat type[i])].i))
544 return True;
545 return False;
546 } /* nostatistic */
547
548 #if qh_KEEPstatistics
549 /*-<a href="qh-stat.htm#TOC"
550 >-------------------------------</a><a name="printallstatistics">-</a>
551
552 qh_printallstatistics( fp, string )
553 print all statistics with header 'string'
554 */
qh_printallstatistics(FILE * fp,const char * string)555 void qh_printallstatistics(FILE *fp, const char *string) {
556
557 qh_allstatistics();
558 qh_collectstatistics();
559 qh_printstatistics(fp, string);
560 qh_memstatistics(fp);
561 }
562
563
564 /*-<a href="qh-stat.htm#TOC"
565 >-------------------------------</a><a name="printstatistics">-</a>
566
567 qh_printstatistics( fp, string )
568 print statistics to a file with header 'string'
569 skips statistics with qhstat.printed[] (reset with qh_allstatistics)
570
571 see:
572 qh_printallstatistics()
573 */
qh_printstatistics(FILE * fp,const char * string)574 void qh_printstatistics(FILE *fp, const char *string) {
575 int i, k;
576 realT ave;
577
578 if (qh num_points != qh num_vertices) {
579 wval_(Wpbalance)= 0;
580 wval_(Wpbalance2)= 0;
581 }else
582 wval_(Wpbalance2)= qh_stddev(zval_(Zpbalance), wval_(Wpbalance),
583 wval_(Wpbalance2), &ave);
584 wval_(Wnewbalance2)= qh_stddev(zval_(Zprocessed), wval_(Wnewbalance),
585 wval_(Wnewbalance2), &ave);
586 qh_fprintf(fp, 9350, "\n\
587 %s\n\
588 qhull invoked by: %s | %s\n%s with options:\n%s\n", string, qh rbox_command,
589 qh qhull_command, qh_version, qh qhull_options);
590 qh_fprintf(fp, 9351, "\nprecision constants:\n\
591 %6.2g max. abs. coordinate in the (transformed) input('Qbd:n')\n\
592 %6.2g max. roundoff error for distance computation('En')\n\
593 %6.2g max. roundoff error for angle computations\n\
594 %6.2g min. distance for outside points ('Wn')\n\
595 %6.2g min. distance for visible facets ('Vn')\n\
596 %6.2g max. distance for coplanar facets ('Un')\n\
597 %6.2g max. facet width for recomputing centrum and area\n\
598 ",
599 qh MAXabs_coord, qh DISTround, qh ANGLEround, qh MINoutside,
600 qh MINvisible, qh MAXcoplanar, qh WIDEfacet);
601 if (qh KEEPnearinside)
602 qh_fprintf(fp, 9352, "\
603 %6.2g max. distance for near-inside points\n", qh NEARinside);
604 if (qh premerge_cos < REALmax/2) qh_fprintf(fp, 9353, "\
605 %6.2g max. cosine for pre-merge angle\n", qh premerge_cos);
606 if (qh PREmerge) qh_fprintf(fp, 9354, "\
607 %6.2g radius of pre-merge centrum\n", qh premerge_centrum);
608 if (qh postmerge_cos < REALmax/2) qh_fprintf(fp, 9355, "\
609 %6.2g max. cosine for post-merge angle\n", qh postmerge_cos);
610 if (qh POSTmerge) qh_fprintf(fp, 9356, "\
611 %6.2g radius of post-merge centrum\n", qh postmerge_centrum);
612 qh_fprintf(fp, 9357, "\
613 %6.2g max. distance for merging two simplicial facets\n\
614 %6.2g max. roundoff error for arithmetic operations\n\
615 %6.2g min. denominator for divisions\n\
616 zero diagonal for Gauss: ", qh ONEmerge, REALepsilon, qh MINdenom);
617 for(k=0; k < qh hull_dim; k++)
618 qh_fprintf(fp, 9358, "%6.2e ", qh NEARzero[k]);
619 qh_fprintf(fp, 9359, "\n\n");
620 for(i=0 ; i < qhstat next; )
621 qh_printstats(fp, i, &i);
622 } /* printstatistics */
623 #endif /* qh_KEEPstatistics */
624
625 /*-<a href="qh-stat.htm#TOC"
626 >-------------------------------</a><a name="printstatlevel">-</a>
627
628 qh_printstatlevel( fp, id )
629 print level information for a statistic
630
631 notes:
632 nop if id >= ZEND, printed, or same as initial value
633 */
qh_printstatlevel(FILE * fp,int id,int start)634 void qh_printstatlevel(FILE *fp, int id, int start) {
635 #define NULLfield " "
636
637 if (id >= ZEND || qhstat printed[id])
638 return;
639 if (qhstat type[id] == zdoc) {
640 qh_fprintf(fp, 9360, "%s\n", qhstat doc[id]);
641 return;
642 }
643 start= 0; /* not used */
644 if (qh_nostatistic(id) || !qhstat doc[id])
645 return;
646 qhstat printed[id]= True;
647 if (qhstat count[id] != -1
648 && qhstat stats[(unsigned char)(qhstat count[id])].i == 0)
649 qh_fprintf(fp, 9361, " *0 cnt*");
650 else if (qhstat type[id] >= ZTYPEreal && qhstat count[id] == -1)
651 qh_fprintf(fp, 9362, "%7.2g", qhstat stats[id].r);
652 else if (qhstat type[id] >= ZTYPEreal && qhstat count[id] != -1)
653 qh_fprintf(fp, 9363, "%7.2g", qhstat stats[id].r/ qhstat stats[(unsigned char)(qhstat count[id])].i);
654 else if (qhstat type[id] < ZTYPEreal && qhstat count[id] == -1)
655 qh_fprintf(fp, 9364, "%7d", qhstat stats[id].i);
656 else if (qhstat type[id] < ZTYPEreal && qhstat count[id] != -1)
657 qh_fprintf(fp, 9365, "%7.3g", (realT) qhstat stats[id].i / qhstat stats[(unsigned char)(qhstat count[id])].i);
658 qh_fprintf(fp, 9366, " %s\n", qhstat doc[id]);
659 } /* printstatlevel */
660
661
662 /*-<a href="qh-stat.htm#TOC"
663 >-------------------------------</a><a name="printstats">-</a>
664
665 qh_printstats( fp, index, nextindex )
666 print statistics for a zdoc group
667
668 returns:
669 next zdoc if non-null
670 */
qh_printstats(FILE * fp,int idx,int * nextindex)671 void qh_printstats(FILE *fp, int idx, int *nextindex) {
672 int j, nexti;
673
674 if (qh_newstats(idx, &nexti)) {
675 qh_fprintf(fp, 9367, "\n");
676 for (j=idx; j<nexti; j++)
677 qh_printstatlevel(fp, qhstat id[j], 0);
678 }
679 if (nextindex)
680 *nextindex= nexti;
681 } /* printstats */
682
683 #if qh_KEEPstatistics
684
685 /*-<a href="qh-stat.htm#TOC"
686 >-------------------------------</a><a name="stddev">-</a>
687
688 qh_stddev( num, tot, tot2, ave )
689 compute the standard deviation and average from statistics
690
691 tot2 is the sum of the squares
692 notes:
693 computes r.m.s.:
694 (x-ave)^2
695 == x^2 - 2x tot/num + (tot/num)^2
696 == tot2 - 2 tot tot/num + tot tot/num
697 == tot2 - tot ave
698 */
qh_stddev(int num,realT tot,realT tot2,realT * ave)699 realT qh_stddev(int num, realT tot, realT tot2, realT *ave) {
700 realT stddev;
701
702 *ave= tot/num;
703 stddev= sqrt(tot2/num - *ave * *ave);
704 return stddev;
705 } /* stddev */
706
707 #endif /* qh_KEEPstatistics */
708
709 #if !qh_KEEPstatistics
qh_collectstatistics(void)710 void qh_collectstatistics(void) {}
qh_printallstatistics(FILE * fp,char * string)711 void qh_printallstatistics(FILE *fp, char *string) {};
qh_printstatistics(FILE * fp,char * string)712 void qh_printstatistics(FILE *fp, char *string) {}
713 #endif
714
715