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