| 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-2003, The Geometry Center |
| 10 |
*/ |
| 11 |
|
| 12 |
#include "QuickHull/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 |
} |
| 141 |
void qh_allstatE(void) { |
| 142 |
zdef_(zinc, Zpartinside, "inside points", -1); |
| 143 |
zdef_(zinc, Zpartnear, " inside points kept with a facet", -1); |
| 144 |
zdef_(zinc, Zcoplanarinside, " inside points that were coplanar with a facet", -1); |
| 145 |
zdef_(zinc, Zbestlower, "calls to findbestlower", -1); |
| 146 |
zdef_(zinc, Zbestlowerv, " with search of vertex neighbors", -1); |
| 147 |
zdef_(wadd, Wmaxout, "difference in max_outside at final check", -1); |
| 148 |
zzdef_(zinc, Zpartitionall, "distance tests for initial partition", -1); |
| 149 |
zdef_(zinc, Ztotpartition, "partitions of a point", -1); |
| 150 |
zzdef_(zinc, Zpartition, "distance tests for partitioning", -1); |
| 151 |
zzdef_(zinc, Zdistcheck, "distance tests for checking flipped facets", -1); |
| 152 |
zzdef_(zinc, Zdistconvex, "distance tests for checking convexity", -1); |
| 153 |
zdef_(zinc, Zdistgood, "distance tests for checking good point", -1); |
| 154 |
zdef_(zinc, Zdistio, "distance tests for output", -1); |
| 155 |
zdef_(zinc, Zdiststat, "distance tests for statistics", -1); |
| 156 |
zdef_(zinc, Zdistplane, "total number of distance tests", -1); |
| 157 |
zdef_(zinc, Ztotpartcoplanar, "partitions of coplanar points or deleted vertices", -1); |
| 158 |
zzdef_(zinc, Zpartcoplanar, " distance tests for these partitions", -1); |
| 159 |
zdef_(zinc, Zcomputefurthest, "distance tests for computing furthest", -1); |
| 160 |
} |
| 161 |
void qh_allstatE2(void) { |
| 162 |
zdef_(zdoc, Zdoc5, "statistics for matching ridges", -1); |
| 163 |
zdef_(zinc, Zhashlookup, "total lookups for matching ridges of new facets", -1); |
| 164 |
zdef_(zinc, Zhashtests, "average number of tests to match a ridge", Zhashlookup); |
| 165 |
zdef_(zinc, Zhashridge, "total lookups of subridges (duplicates and boundary)", -1); |
| 166 |
zdef_(zinc, Zhashridgetest, "average number of tests per subridge", Zhashridge); |
| 167 |
zdef_(zinc, Zdupsame, "duplicated ridges in same merge cycle", -1); |
| 168 |
zdef_(zinc, Zdupflip, "duplicated ridges with flipped facets", -1); |
| 169 |
|
| 170 |
zdef_(zdoc, Zdoc6, "statistics for determining merges", -1); |
| 171 |
zdef_(zinc, Zangletests, "angles computed for ridge convexity", -1); |
| 172 |
zdef_(zinc, Zbestcentrum, "best merges used centrum instead of vertices",-1); |
| 173 |
zzdef_(zinc, Zbestdist, "distance tests for best merge", -1); |
| 174 |
zzdef_(zinc, Zcentrumtests, "distance tests for centrum convexity", -1); |
| 175 |
zzdef_(zinc, Zdistzero, "distance tests for checking simplicial convexity", -1); |
| 176 |
zdef_(zinc, Zcoplanarangle, "coplanar angles in getmergeset", -1); |
| 177 |
zdef_(zinc, Zcoplanarcentrum, "coplanar centrums in getmergeset", -1); |
| 178 |
zdef_(zinc, Zconcaveridge, "concave ridges in getmergeset", -1); |
| 179 |
} |
| 180 |
void qh_allstatF(void) { |
| 181 |
zdef_(zdoc, Zdoc7, "statistics for merging", -1); |
| 182 |
zdef_(zinc, Zpremergetot, "merge iterations", -1); |
| 183 |
zdef_(zadd, Zmergeinittot, "ave. initial non-convex ridges per iteration", Zpremergetot); |
| 184 |
zdef_(zadd, Zmergeinitmax, " maximum", -1); |
| 185 |
zdef_(zadd, Zmergesettot, " ave. additional non-convex ridges per iteration", Zpremergetot); |
| 186 |
zdef_(zadd, Zmergesetmax, " maximum additional in one pass", -1); |
| 187 |
zdef_(zadd, Zmergeinittot2, "initial non-convex ridges for post merging", -1); |
| 188 |
zdef_(zadd, Zmergesettot2, " additional non-convex ridges", -1); |
| 189 |
zdef_(wmax, Wmaxoutside, "max distance of vertex or coplanar point above facet (w/roundoff)", -1); |
| 190 |
zdef_(wmin, Wminvertex, "max distance of merged vertex below facet (or roundoff)", -1); |
| 191 |
zdef_(zinc, Zwidefacet, "centrums frozen due to a wide merge", -1); |
| 192 |
zdef_(zinc, Zwidevertices, "centrums frozen due to extra vertices", -1); |
| 193 |
zzdef_(zinc, Ztotmerge, "total number of facets or cycles of facets merged", -1); |
| 194 |
zdef_(zinc, Zmergesimplex, "merged a simplex", -1); |
| 195 |
zdef_(zinc, Zonehorizon, "simplices merged into coplanar horizon", -1); |
| 196 |
zzdef_(zinc, Zcyclehorizon, "cycles of facets merged into coplanar horizon", -1); |
| 197 |
zzdef_(zadd, Zcyclefacettot, " ave. facets per cycle", Zcyclehorizon); |
| 198 |
zdef_(zmax, Zcyclefacetmax, " max. facets", -1); |
| 199 |
zdef_(zinc, Zmergeintohorizon, "new facets merged into horizon", -1); |
| 200 |
zdef_(zinc, Zmergenew, "new facets merged", -1); |
| 201 |
zdef_(zinc, Zmergehorizon, "horizon facets merged into new facets", -1); |
| 202 |
zdef_(zinc, Zmergevertex, "vertices deleted by merging", -1); |
| 203 |
zdef_(zinc, Zcyclevertex, "vertices deleted by merging into coplanar horizon", -1); |
| 204 |
zdef_(zinc, Zdegenvertex, "vertices deleted by degenerate facet", -1); |
| 205 |
zdef_(zinc, Zmergeflipdup, "merges due to flipped facets in duplicated ridge", -1); |
| 206 |
zdef_(zinc, Zneighbor, "merges due to redundant neighbors", -1); |
| 207 |
zdef_(zadd, Ztestvneighbor, "non-convex vertex neighbors", -1); |
| 208 |
} |
| 209 |
void qh_allstatG(void) { |
| 210 |
zdef_(zinc, Zacoplanar, "merges due to angle coplanar facets", -1); |
| 211 |
zdef_(wadd, Wacoplanartot, " average merge distance", Zacoplanar); |
| 212 |
zdef_(wmax, Wacoplanarmax, " maximum merge distance", -1); |
| 213 |
zdef_(zinc, Zcoplanar, "merges due to coplanar facets", -1); |
| 214 |
zdef_(wadd, Wcoplanartot, " average merge distance", Zcoplanar); |
| 215 |
zdef_(wmax, Wcoplanarmax, " maximum merge distance", -1); |
| 216 |
zdef_(zinc, Zconcave, "merges due to concave facets", -1); |
| 217 |
zdef_(wadd, Wconcavetot, " average merge distance", Zconcave); |
| 218 |
zdef_(wmax, Wconcavemax, " maximum merge distance", -1); |
| 219 |
zdef_(zinc, Zavoidold, "coplanar/concave merges due to avoiding old merge", -1); |
| 220 |
zdef_(wadd, Wavoidoldtot, " average merge distance", Zavoidold); |
| 221 |
zdef_(wmax, Wavoidoldmax, " maximum merge distance", -1); |
| 222 |
zdef_(zinc, Zdegen, "merges due to degenerate facets", -1); |
| 223 |
zdef_(wadd, Wdegentot, " average merge distance", Zdegen); |
| 224 |
zdef_(wmax, Wdegenmax, " maximum merge distance", -1); |
| 225 |
zdef_(zinc, Zflipped, "merges due to removing flipped facets", -1); |
| 226 |
zdef_(wadd, Wflippedtot, " average merge distance", Zflipped); |
| 227 |
zdef_(wmax, Wflippedmax, " maximum merge distance", -1); |
| 228 |
zdef_(zinc, Zduplicate, "merges due to duplicated ridges", -1); |
| 229 |
zdef_(wadd, Wduplicatetot, " average merge distance", Zduplicate); |
| 230 |
zdef_(wmax, Wduplicatemax, " maximum merge distance", -1); |
| 231 |
} |
| 232 |
void qh_allstatH(void) { |
| 233 |
zdef_(zdoc, Zdoc8, "renamed vertex statistics", -1); |
| 234 |
zdef_(zinc, Zrenameshare, "renamed vertices shared by two facets", -1); |
| 235 |
zdef_(zinc, Zrenamepinch, "renamed vertices in a pinched facet", -1); |
| 236 |
zdef_(zinc, Zrenameall, "renamed vertices shared by multiple facets", -1); |
| 237 |
zdef_(zinc, Zfindfail, "rename failures due to duplicated ridges", -1); |
| 238 |
zdef_(zinc, Zdupridge, " duplicate ridges detected", -1); |
| 239 |
zdef_(zinc, Zdelridge, "deleted ridges due to renamed vertices", -1); |
| 240 |
zdef_(zinc, Zdropneighbor, "dropped neighbors due to renamed vertices", -1); |
| 241 |
zdef_(zinc, Zdropdegen, "degenerate facets due to dropped neighbors", -1); |
| 242 |
zdef_(zinc, Zdelfacetdup, " facets deleted because of no neighbors", -1); |
| 243 |
zdef_(zinc, Zremvertex, "vertices removed from facets due to no ridges", -1); |
| 244 |
zdef_(zinc, Zremvertexdel, " deleted", -1); |
| 245 |
zdef_(zinc, Zintersectnum, "vertex intersections for locating redundant vertices", -1); |
| 246 |
zdef_(zinc, Zintersectfail, "intersections failed to find a redundant vertex", -1); |
| 247 |
zdef_(zinc, Zintersect, "intersections found redundant vertices", -1); |
| 248 |
zdef_(zadd, Zintersecttot, " ave. number found per vertex", Zintersect); |
| 249 |
zdef_(zmax, Zintersectmax, " max. found for a vertex", -1); |
| 250 |
zdef_(zinc, Zvertexridge, NULL, -1); |
| 251 |
zdef_(zadd, Zvertexridgetot, " ave. number of ridges per tested vertex", Zvertexridge); |
| 252 |
zdef_(zmax, Zvertexridgemax, " max. number of ridges per tested vertex", -1); |
| 253 |
|
| 254 |
zdef_(zdoc, Zdoc10, "memory usage statistics (in bytes)", -1); |
| 255 |
zdef_(zadd, Zmemfacets, "for facets and their normals, neighbor and vertex sets", -1); |
| 256 |
zdef_(zadd, Zmemvertices, "for vertices and their neighbor sets", -1); |
| 257 |
zdef_(zadd, Zmempoints, "for input points and outside and coplanar sets",-1); |
| 258 |
zdef_(zadd, Zmemridges, "for ridges and their vertex sets", -1); |
| 259 |
} /* allstat */ |
| 260 |
|
| 261 |
void qh_allstatI(void) { |
| 262 |
qhstat vridges= qhstat next; |
| 263 |
zzdef_(zdoc, Zdoc11, "Voronoi ridge statistics", -1); |
| 264 |
zzdef_(zinc, Zridge, "non-simplicial Voronoi vertices for all ridges", -1); |
| 265 |
zzdef_(wadd, Wridge, " ave. distance to ridge", Zridge); |
| 266 |
zzdef_(wmax, Wridgemax, " max. distance to ridge", -1); |
| 267 |
zzdef_(zinc, Zridgemid, "bounded ridges", -1); |
| 268 |
zzdef_(wadd, Wridgemid, " ave. distance of midpoint to ridge", Zridgemid); |
| 269 |
zzdef_(wmax, Wridgemidmax, " max. distance of midpoint to ridge", -1); |
| 270 |
zzdef_(zinc, Zridgeok, "bounded ridges with ok normal", -1); |
| 271 |
zzdef_(wadd, Wridgeok, " ave. angle to ridge", Zridgeok); |
| 272 |
zzdef_(wmax, Wridgeokmax, " max. angle to ridge", -1); |
| 273 |
zzdef_(zinc, Zridge0, "bounded ridges with near-zero normal", -1); |
| 274 |
zzdef_(wadd, Wridge0, " ave. angle to ridge", Zridge0); |
| 275 |
zzdef_(wmax, Wridge0max, " max. angle to ridge", -1); |
| 276 |
|
| 277 |
zdef_(zdoc, Zdoc12, "Triangulation statistics (Qt)", -1); |
| 278 |
zdef_(zinc, Ztricoplanar, "non-simplicial facets triangulated", -1); |
| 279 |
zdef_(zadd, Ztricoplanartot, " ave. new facets created (may be deleted)", Ztricoplanar); |
| 280 |
zdef_(zmax, Ztricoplanarmax, " max. new facets created", -1); |
| 281 |
zdef_(zinc, Ztrinull, "null new facets deleted (duplicated vertex)", -1); |
| 282 |
zdef_(zinc, Ztrimirror, "mirrored pairs of new facets deleted (same vertices)", -1); |
| 283 |
zdef_(zinc, Ztridegen, "degenerate new facets in output (same ridge)", -1); |
| 284 |
} /* allstat */ |
| 285 |
|
| 286 |
/*-<a href="qh-stat.htm#TOC" |
| 287 |
>-------------------------------</a><a name="allstatistics">-</a> |
| 288 |
|
| 289 |
qh_allstatistics() |
| 290 |
reset printed flag for all statistics |
| 291 |
*/ |
| 292 |
void qh_allstatistics (void) { |
| 293 |
int i; |
| 294 |
|
| 295 |
for (i=ZEND; i--; ) |
| 296 |
qhstat printed[i]= False; |
| 297 |
} /* allstatistics */ |
| 298 |
|
| 299 |
#if qh_KEEPstatistics |
| 300 |
/*-<a href="qh-stat.htm#TOC" |
| 301 |
>-------------------------------</a><a name="collectstatistics">-</a> |
| 302 |
|
| 303 |
qh_collectstatistics() |
| 304 |
collect statistics for qh.facet_list |
| 305 |
|
| 306 |
*/ |
| 307 |
void qh_collectstatistics (void) { |
| 308 |
facetT *facet, *neighbor, **neighborp; |
| 309 |
vertexT *vertex, **vertexp; |
| 310 |
realT dotproduct, dist; |
| 311 |
int sizneighbors, sizridges, sizvertices, i; |
| 312 |
|
| 313 |
qh old_randomdist= qh RANDOMdist; |
| 314 |
qh RANDOMdist= False; |
| 315 |
zval_(Zmempoints)= qh num_points * qh normal_size + |
| 316 |
sizeof (qhT) + sizeof (qhstatT); |
| 317 |
zval_(Zmemfacets)= 0; |
| 318 |
zval_(Zmemridges)= 0; |
| 319 |
zval_(Zmemvertices)= 0; |
| 320 |
zval_(Zangle)= 0; |
| 321 |
wval_(Wangle)= 0.0; |
| 322 |
zval_(Znumridges)= 0; |
| 323 |
zval_(Znumfacets)= 0; |
| 324 |
zval_(Znumneighbors)= 0; |
| 325 |
zval_(Znumvertices)= 0; |
| 326 |
zval_(Znumvneighbors)= 0; |
| 327 |
zval_(Znummergetot)= 0; |
| 328 |
zval_(Znummergemax)= 0; |
| 329 |
zval_(Zvertices)= qh num_vertices - qh_setsize (qh del_vertices); |
| 330 |
if (qh MERGING || qh APPROXhull || qh JOGGLEmax < REALmax/2) |
| 331 |
wmax_(Wmaxoutside, qh max_outside); |
| 332 |
if (qh MERGING) |
| 333 |
wmin_(Wminvertex, qh min_vertex); |
| 334 |
FORALLfacets |
| 335 |
facet->seen= False; |
| 336 |
if (qh DELAUNAY) { |
| 337 |
FORALLfacets { |
| 338 |
if (facet->upperdelaunay != qh UPPERdelaunay) |
| 339 |
facet->seen= True; /* remove from angle statistics */ |
| 340 |
} |
| 341 |
} |
| 342 |
FORALLfacets { |
| 343 |
if (facet->visible && qh NEWfacets) |
| 344 |
continue; |
| 345 |
sizvertices= qh_setsize (facet->vertices); |
| 346 |
sizneighbors= qh_setsize (facet->neighbors); |
| 347 |
sizridges= qh_setsize (facet->ridges); |
| 348 |
zinc_(Znumfacets); |
| 349 |
zadd_(Znumvertices, sizvertices); |
| 350 |
zmax_(Zmaxvertices, sizvertices); |
| 351 |
zadd_(Znumneighbors, sizneighbors); |
| 352 |
zmax_(Zmaxneighbors, sizneighbors); |
| 353 |
zadd_(Znummergetot, facet->nummerge); |
| 354 |
i= facet->nummerge; /* avoid warnings */ |
| 355 |
zmax_(Znummergemax, i); |
| 356 |
if (!facet->simplicial) { |
| 357 |
if (sizvertices == qh hull_dim) { |
| 358 |
zinc_(Znowsimplicial); |
| 359 |
}else { |
| 360 |
zinc_(Znonsimplicial); |
| 361 |
} |
| 362 |
} |
| 363 |
if (sizridges) { |
| 364 |
zadd_(Znumridges, sizridges); |
| 365 |
zmax_(Zmaxridges, sizridges); |
| 366 |
} |
| 367 |
zadd_(Zmemfacets, sizeof (facetT) + qh normal_size + 2*sizeof (setT) + SETelemsize * (sizneighbors + sizvertices)); |
| 368 |
if (facet->ridges) { |
| 369 |
zadd_(Zmemridges, sizeof (setT) + SETelemsize * sizridges + sizridges * (sizeof (ridgeT) + sizeof (setT) + SETelemsize * (qh hull_dim-1))/2); |
| 370 |
} |
| 371 |
if (facet->outsideset) |
| 372 |
zadd_(Zmempoints, sizeof (setT) + SETelemsize * qh_setsize (facet->outsideset)); |
| 373 |
if (facet->coplanarset) |
| 374 |
zadd_(Zmempoints, sizeof (setT) + SETelemsize * qh_setsize (facet->coplanarset)); |
| 375 |
if (facet->seen) /* Delaunay upper envelope */ |
| 376 |
continue; |
| 377 |
facet->seen= True; |
| 378 |
FOREACHneighbor_(facet) { |
| 379 |
if (neighbor == qh_DUPLICATEridge || neighbor == qh_MERGEridge |
| 380 |
|| neighbor->seen || !facet->normal || !neighbor->normal) |
| 381 |
continue; |
| 382 |
dotproduct= qh_getangle(facet->normal, neighbor->normal); |
| 383 |
zinc_(Zangle); |
| 384 |
wadd_(Wangle, dotproduct); |
| 385 |
wmax_(Wanglemax, dotproduct) |
| 386 |
wmin_(Wanglemin, dotproduct) |
| 387 |
} |
| 388 |
if (facet->normal) { |
| 389 |
FOREACHvertex_(facet->vertices) { |
| 390 |
zinc_(Zdiststat); |
| 391 |
qh_distplane(vertex->point, facet, &dist); |
| 392 |
wmax_(Wvertexmax, dist); |
| 393 |
wmin_(Wvertexmin, dist); |
| 394 |
} |
| 395 |
} |
| 396 |
} |
| 397 |
FORALLvertices { |
| 398 |
if (vertex->deleted) |
| 399 |
continue; |
| 400 |
zadd_(Zmemvertices, sizeof (vertexT)); |
| 401 |
if (vertex->neighbors) { |
| 402 |
sizneighbors= qh_setsize (vertex->neighbors); |
| 403 |
zadd_(Znumvneighbors, sizneighbors); |
| 404 |
zmax_(Zmaxvneighbors, sizneighbors); |
| 405 |
zadd_(Zmemvertices, sizeof (vertexT) + SETelemsize * sizneighbors); |
| 406 |
} |
| 407 |
} |
| 408 |
qh RANDOMdist= qh old_randomdist; |
| 409 |
} /* collectstatistics */ |
| 410 |
#endif /* qh_KEEPstatistics */ |
| 411 |
|
| 412 |
/*-<a href="qh-stat.htm#TOC" |
| 413 |
>-------------------------------</a><a name="freestatistics">-</a> |
| 414 |
|
| 415 |
qh_freestatistics( ) |
| 416 |
free memory used for statistics |
| 417 |
*/ |
| 418 |
void qh_freestatistics (void) { |
| 419 |
|
| 420 |
#if qh_QHpointer |
| 421 |
free (qh_qhstat); |
| 422 |
qh_qhstat= NULL; |
| 423 |
#endif |
| 424 |
} /* freestatistics */ |
| 425 |
|
| 426 |
/*-<a href="qh-stat.htm#TOC" |
| 427 |
>-------------------------------</a><a name="initstatistics">-</a> |
| 428 |
|
| 429 |
qh_initstatistics( ) |
| 430 |
allocate and initialize statistics |
| 431 |
|
| 432 |
notes: |
| 433 |
uses malloc() instead of qh_memalloc() since mem.c not set up yet |
| 434 |
*/ |
| 435 |
void qh_initstatistics (void) { |
| 436 |
int i; |
| 437 |
realT realx; |
| 438 |
int intx; |
| 439 |
|
| 440 |
#if qh_QHpointer |
| 441 |
if (!(qh_qhstat= (qhstatT *)malloc (sizeof(qhstatT)))) { |
| 442 |
fprintf (qhmem.ferr, "qhull error (qh_initstatistics): insufficient memory\n"); |
| 443 |
exit (1); /* can not use qh_errexit() */ |
| 444 |
} |
| 445 |
#endif |
| 446 |
|
| 447 |
qhstat next= 0; |
| 448 |
qh_allstatA(); |
| 449 |
qh_allstatB(); |
| 450 |
qh_allstatC(); |
| 451 |
qh_allstatD(); |
| 452 |
qh_allstatE(); |
| 453 |
qh_allstatE2(); |
| 454 |
qh_allstatF(); |
| 455 |
qh_allstatG(); |
| 456 |
qh_allstatH(); |
| 457 |
qh_allstatI(); |
| 458 |
if (qhstat next > sizeof(qhstat id)) { |
| 459 |
fprintf (qhmem.ferr, "qhull error (qh_initstatistics): increase size of qhstat.id[].\n\ |
| 460 |
qhstat.next %d should be <= sizeof(qhstat id) %d\n", qhstat next, sizeof(qhstat id)); |
| 461 |
#if 0 |
| 462 |
/* 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 |
|
