stat.c

这是一个新的用于图像处理的工具箱

/* stat.c - contains all statistics that are collected for qhull

   see README and stat.h

   copyright (c) 1993-1995, The Geometry Center
*/

#include "qhull_a.h"

#if qh_QHpointer
qhstatT *qh_qhstat=NULL;  /* global data structure */
#else
qhstatT qh_qhstat={0};   /* remove "={0}" if this causes a compiler error */
#endif


/*-------------------------------------------------
-allstatA -- define statistics in groups of 20
  (otherwise, 'gcc -O2' uses too much memory)
  uses qhstat next
*/
void qh_allstatA (void) {
  
   /* zdef_(type,name,doc,average) */
  zzdef_(zdoc, Zdoc2, "precision statistics", -1);
  zdef_(zinc, Znewvertex, NULL, -1);
  zdef_(wadd, Wnewvertex, "ave. distance of a new vertex to a facet (not 0s)", Znewvertex);
  zdef_(wmax, Wnewvertexmax, "max. distance of a new vertex to a facet", -1);
  zdef_(wmax, Wvertexmax, "max. distance of an output vertex to a facet", -1);
  zdef_(wmin, Wvertexmin, "min. distance of an output vertex to a facet", -1);
  zdef_(wmin, Wmindenom, "min. denominator in hyperplane computation", -1);

  qhstat precision= qhstat next;
  zzdef_(zdoc, Zdoc3, "precision problems", -1);
  zzdef_(zinc, Zcoplanarridges, "coplanar half ridges in output", -1);
  zzdef_(zinc, Zconcaveridges, "concave half ridges in output", -1);
  zzdef_(zinc, Zflippedfacets, "flipped facets", -1);
  zzdef_(zinc, Zcoplanarhorizon, "coplanar horizon facets for new vertices", -1);
  zzdef_(zinc, Zcoplanarpart, "coplanar points during partitioning", -1);
  zzdef_(zinc, Zminnorm, "degenerate hyperplanes recomputed with gaussian elimination", -1);
  zzdef_(zinc, Znearlysingular, "nearly singular or axis-parallel hyperplanes", -1);
  zzdef_(zinc, Zback0, "zero divisors during back substitute", -1);
  zzdef_(zinc, Zgauss0, "zero divisors during gaussian elimination", -1);
  zzdef_(zinc, Zmultiridge, "ridges with multiple neighbors", -1);
}
void qh_allstatB (void) {
  zzdef_(zdoc, Zdoc1, "summary information", -1);
  zdef_(zinc, Zvertices, "number of vertices in output", -1);
  zdef_(zinc, Znumfacets, "number of facets in output", -1);
  zdef_(zinc, Znumridges, "number of ridges in output", -1);
  zdef_(zadd, Znumridges, "average number of ridges per facet", Znumfacets);
  zdef_(zmax, Zmaxridges, "maximum number of ridges", -1);
  zdef_(zadd, Znumneighbors, "average number of neighbors per facet", Znumfacets);
  zdef_(zmax, Zmaxneighbors, "maximum number of neighbors", -1);
  zdef_(zadd, Znumvertices, "average number of vertices per facet", Znumfacets);
  zdef_(zmax, Zmaxvertices, "maximum number of vertices", -1);
  zdef_(zadd, Znumvneighbors, "average number of neighbors per vertex", Zvertices);
  zdef_(zmax, Zmaxvneighbors, "maximum number of neighbors", -1);
  zdef_(wadd, Wcpu, "cpu seconds for qhull after input", -1);
  zdef_(zinc, Ztotvertices, "vertices created altogether", -1);
  zzdef_(zinc, Zsetplane, "facets created altogether", -1);
  zdef_(zinc, Ztotridges, "ridges created altogether", -1);
  zdef_(zinc, Zpostfacets, "facets before post merge", -1);
  zdef_(zadd, Znummergetot, "average merges per facet (at most 511)", Znumfacets);
  zdef_(zmax, Znummergemax, "  maximum merges for a facet (at most 511)", -1);
  zdef_(zinc, Zangle, NULL, -1);
  zdef_(wadd, Wangle, "average angle (cosine) for all ridges", Zangle);
  zdef_(wmax, Wanglemax, "  maximum angle (cosine) of a ridge", -1);
  zdef_(wmin, Wanglemin, "  minimum angle (cosine) of a ridge", -1);
  zdef_(wadd, Wareatot, "total area of facets", -1);
  zdef_(wmax, Wareamax, "  maximum facet area", -1);
  zdef_(wmin, Wareamin, "  minimum facet area", -1);
}  
void qh_allstatC (void) {
  zdef_(zdoc, Zdoc9, "build hull statistics", -1);
  zzdef_(zinc, Zprocessed, "points processed", -1);
  zdef_(zmax, Zmaxvertex, "max. vertices at any one time", -1);
  zdef_(zinc, Ztotvisible, "ave. visible facets per iteration", Zprocessed);
  zdef_(zinc, Zinsidevisible, "  ave. visible facets without an horizon neighbor", Zprocessed);
  zdef_(zadd, Zvisfacettot,  "  ave. facets deleted per iteration", Zprocessed);
  zdef_(zmax, Zvisfacetmax,  "    maximum", -1);
  zdef_(zadd, Zvisvertextot, "ave. visible vertices per iteration", Zprocessed);
  zdef_(zmax, Zvisvertexmax, "    maximum", -1);
  zdef_(zadd, Zdelvertextot, "  ave. vertices deleted per iteration", Zprocessed);
  zdef_(zmax, Zdelvertexmax, "    maximum vertices deleted", -1);
  zdef_(zinc, Ztothorizon, "ave. horizon facets per iteration", Zprocessed);
  zdef_(zadd, Znewfacettot,  "ave. new or merged facets per iteration", Zprocessed);
  zdef_(zmax, Znewfacetmax,  "    maximum (includes initial simplex)", -1);
  zdef_(wadd, Wnewbalance, "average new facet balance", Zprocessed);
  zdef_(wadd, Wnewbalance2, "  standard deviation", -1);
  zdef_(wadd, Wpbalance, "average partition balance", Zpbalance);
  zdef_(wadd, Wpbalance2, "  standard deviation", -1);
  zdef_(zinc, Zsearchpoints, "searches of all points for initial simplex", -1);
  zdef_(zinc, Zdetsimplex, "determinants computed (area & initial hull)", -1);
  zdef_(zinc, Znoarea, "determinants not computed because vertex too low", -1);
  zdef_(zinc, Znotmax, "points ignored (not above max_outside)", -1);
  zdef_(zinc, Znotgood, "points ignored (not above a good facet)", -1);
  zdef_(zinc, Znotgoodnew, "points ignored (didn't create a good new facet)", -1);
  zdef_(zinc, Zgoodfacet, "good facets found", -1);
  zzdef_(zinc, Znumvisibility, "distance tests for facet visibility", -1);
  zdef_(zinc, Zdistvertex, "distance tests to report minimum vertex", -1);
  zdef_(zinc, Ztotcheck, "points checked for facets' outer planes", -1);
  zdef_(zinc, Zcheckpart, "  ave. distance tests per check", Ztotcheck);
}
void qh_allstatD(void) {
  zdef_(zdoc, Zdoc4, "partitioning statistics", -1);
  zdef_(zinc, Zpartinside, "inside points", -1);
  zdef_(zinc, Zpartnear, "  inside points kept with a facet", -1);
  zdef_(zinc, Zcoplanarinside, "  inside points that were coplanar with a facet", -1);
  zdef_(wadd, Wmaxout, "difference in max_outside at final check", -1);
  
  zzdef_(zinc, Zpartitionall, "distance tests for initial partition", -1);
  zdef_(zinc, Ztotpartition, "partitions of a point", -1);
  zzdef_(zinc, Zpartition, "distance tests for partitioning", -1);
  zzdef_(zinc, Zdistcheck, "distance tests for checking flipped facets", -1); 
  zzdef_(zinc, Zdistconvex, "distance tests for checking convexity", -1); 
  zdef_(zinc, Zdistgood, "distance tests for checking good point", -1); 
  zdef_(zinc, Zdistio, "distance tests for output", -1); 
  zdef_(zinc, Zdiststat, "distance tests for statistics", -1); 
  zdef_(zinc, Zdistplane, "total number of distance tests", -1);
  zdef_(zinc, Ztotpartcoplanar, "partitions of coplanar points or deleted vertices", -1);
  zzdef_(zinc, Zpartcoplanar, "   distance tests for these partitions", -1);
  zdef_(zinc, Zcomputefurthest, "distance tests for computing furthest", -1);
}
void qh_allstatE(void) {
  zdef_(zdoc, Zdoc5, "statistics for matching ridges", -1);
  zdef_(zinc, Zhashlookup, "total lookups for matching ridges of new facets", -1);
  zdef_(zinc, Zhashtests, "average number of tests to match a ridge", Zhashlookup);
  zdef_(zinc, Zhashridge, "total lookups of subridges (duplicates and boundary)", -1);
  zdef_(zinc, Zhashridgetest, "average number of tests per subridge", Zhashridge);
  zdef_(zinc, Zdupsame, "duplicated ridges in same merge cycle", -1);
  zdef_(zinc, Zdupflip, "duplicated ridges with flipped facets", -1);

  zdef_(zdoc, Zdoc6, "statistics for determining merges", -1);
  zdef_(zinc, Zangletests, "angles computed for ridge convexity", -1);
  zdef_(zinc, Zbestcentrum, "best merges used centrum instead of vertices",-1);
  zzdef_(zinc, Zbestdist, "distance tests for best merge", -1);
  zzdef_(zinc, Zcentrumtests, "distance tests for centrum convexity", -1);
  zzdef_(zinc, Zdistzero, "distance tests for checking simplicial convexity", -1);
  zdef_(zinc, Zcoplanarangle, "coplanar angles in getmergeset", -1);
  zdef_(zinc, Zcoplanarcentrum, "coplanar centrums in getmergeset", -1);
  zdef_(zinc, Zconcaveridge, "concave ridges in getmergeset", -1);
}
void qh_allstatF(void) {
  zdef_(zdoc, Zdoc7, "statistics for merging", -1);
  zdef_(zinc, Zpremergetot, "merge iterations", -1);
  zdef_(zadd, Zmergeinittot, "ave. initial non-convex ridges per iteration", Zpremergetot);
  zdef_(zadd, Zmergeinitmax, "  maximum", -1);
  zdef_(zadd, Zmergesettot, "  ave. additional non-convex ridges per iteration", Zpremergetot);
  zdef_(zadd, Zmergesetmax, "  maximum additional in one pass", -1);
  zdef_(zadd, Zmergeinittot2, "initial non-convex ridges for post merging", -1);
  zdef_(zadd, Zmergesettot2, "  additional non-convex ridges", -1);
  zdef_(wmax, Wmaxoutside, "max distance of vertex or coplanar point above facet (w/roundoff)", -1);
  zdef_(wmin, Wminvertex, "max distance of merged vertex below facet (or roundoff)", -1);
  zdef_(zinc, Zwidefacet, "centrums frozen due to a wide merge", -1);
  zdef_(zinc, Zwidevertices, "centrums frozen due to extra vertices", -1);
  zzdef_(zinc, Ztotmerge, "total number of facets or cycles of facets merged", -1);
  zdef_(zinc, Zmergesimplex, "merged a simplex", -1);
  zdef_(zinc, Zonehorizon, "simplices merged into coplanar horizon", -1);
  zzdef_(zinc, Zcyclehorizon, "cycles of facets merged into coplanar horizon", -1);
  zzdef_(zadd, Zcyclefacettot, "  ave. facets per cycle", Zcyclehorizon);
  zdef_(zmax, Zcyclefacetmax, "  max. facets", -1);
  zdef_(zinc, Zmergeintohorizon, "new facets merged into horizon", -1);
  zdef_(zinc, Zmergenew, "new facets merged", -1);
  zdef_(zinc, Zmergehorizon, "horizon facets merged into new facets", -1);
  zdef_(zinc, Zmergevertex, "vertices deleted by merging", -1);
  zdef_(zinc, Zcyclevertex, "vertices deleted by merging into coplanar horizon", -1);
  zdef_(zinc, Zdegenvertex, "vertices deleted by degenerate facet", -1);
  zdef_(zinc, Zmergeflipdup, "merges due to flipped facets in duplicated ridge", -1);
  zdef_(zinc, Zneighbor, "merges due to redundant neighbors", -1);
  zdef_(zadd, Ztestvneighbor, "non-convex vertex neighbors", -1); 
}
void qh_allstatG(void) {
  zdef_(zinc, Zacoplanar, "merges due to angle coplanar facets", -1);
  zdef_(wadd, Wacoplanartot, "  average merge distance", Zacoplanar);
  zdef_(wmax, Wacoplanarmax, "  maximum merge distance", -1);
  zdef_(zinc, Zcoplanar, "merges due to coplanar facets", -1);
  zdef_(wadd, Wcoplanartot, "  average merge distance", Zcoplanar);
  zdef_(wmax, Wcoplanarmax, "  maximum merge distance", -1);
  zdef_(zinc, Zconcave, "merges due to concave facets", -1);
  zdef_(wadd, Wconcavetot, "  average merge distance", Zconcave);
  zdef_(wmax, Wconcavemax, "  maximum merge distance", -1);
  zdef_(zinc, Zavoidold, "coplanar/concave merges due to avoiding old merge", -1);
  zdef_(wadd, Wavoidoldtot, "  average merge distance", Zavoidold);
  zdef_(wmax, Wavoidoldmax, "  maximum merge distance", -1);
  zdef_(zinc, Zdegen, "merges due to degenerate facets", -1);
  zdef_(wadd, Wdegentot, "  average merge distance", Zdegen);
  zdef_(wmax, Wdegenmax, "  maximum merge distance", -1);
  zdef_(zinc, Zflipped, "merges due to removing flipped facets", -1);
  zdef_(wadd, Wflippedtot, "  average merge distance", Zflipped);
  zdef_(wmax, Wflippedmax, "  maximum merge distance", -1);
  zdef_(zinc, Zduplicate, "merges due to duplicated ridges", -1);
  zdef_(wadd, Wduplicatetot, "  average merge distance", Zduplicate);
  zdef_(wmax, Wduplicatemax, "  maximum merge distance", -1);

}
void qh_allstatH(void) {
  zdef_(zdoc, Zdoc8, "renamed vertex statistics", -1);
  zdef_(zinc, Zrenameshare, "renamed vertices shared by two facets", -1);
  zdef_(zinc, Zrenamepinch, "renamed vertices in a pinched facet", -1);
  zdef_(zinc, Zrenameall, "renamed vertices shared by multiple facets", -1);
  zdef_(zinc, Zfindfail, "rename failures due to duplicated ridges", -1);
  zdef_(zinc, Zdupridge, "  duplicate ridges detected", -1);
  zdef_(zinc, Zdelridge, "deleted ridges due to renamed vertices", -1);
  zdef_(zinc, Zdropneighbor, "dropped neighbors due to renamed vertices", -1);
  zdef_(zinc, Zdropdegen, "degenerate facets due to dropped neighbors", -1);
  zdef_(zinc, Zdelfacetdup, "  facets deleted because of no neighbors", -1);
  zdef_(zinc, Zremvertex, "vertices removed from facets due to no ridges", -1);
  zdef_(zinc, Zremvertexdel, "  deleted", -1);
  zdef_(zinc, Zintersectnum, "vertex intersections for locating redundant vertices", -1);
  zdef_(zinc, Zintersectfail, "intersections failed to find a redundant vertex", -1);
  zdef_(zinc, Zintersect, "intersections found redundant vertices", -1);
  zdef_(zadd, Zintersecttot, "   ave. number found per vertex", Zintersect);
  zdef_(zmax, Zintersectmax, "   max. found for a vertex", -1);
  zdef_(zinc, Zvertexridge, NULL, -1);
  zdef_(zadd, Zvertexridgetot, "  ave. number of ridges per tested vertex", Zvertexridge);
  zdef_(zmax, Zvertexridgemax, "  max. number of ridges per tested vertex", -1);

  zdef_(zdoc, Zdoc10, "memory usage statistics (in bytes)", -1);
  zdef_(zadd, Zmemfacets, "for facets and their normals, neighbor and vertex sets", -1);
  zdef_(zadd, Zmemvertices, "for vertices and their neighbor sets", -1);
  zdef_(zadd, Zmempoints, "for input points and outside and coplanar sets",-1);
  zdef_(zadd, Zmemridges, "for ridges and their vertex sets", -1);
} /* allstat */


/*-------------------------------------------
-allstatistics- reset printed flag for all statistics
*/
void qh_allstatistics (void) {
  int i;
  
  for (i=ZEND; i--; ) 
    qhstat printed[i]= False;
} /* allstatistics */

#if qh_KEEPstatistics
/*-------------------------------------------------
-collectstatistics- collect statistics for qh facet_list
*/
void qh_collectstatistics (void) {
  facetT *facet, *neighbor, **neighborp;
  vertexT *vertex, **vertexp;
  realT dotproduct, dist;
  int sizneighbors, sizridges, sizvertices;
  
  zval_(Zmempoints)= qh num_points * qh normal_size + 
                             sizeof (qhT) + sizeof (qhstatT);
  zval_(Zmemfacets)= 0;
  zval_(Zmemridges)= 0;
  zval_(Zmemvertices)= 0;
  zval_(Zangle)= 0;
  wval_(Wangle)= 0.0;
  zval_(Znumridges)= 0;
  zval_(Znumfacets)= 0;
  zval_(Znumneighbors)= 0;
  zval_(Znumvertices)= 0;
  zval_(Znumvneighbors)= 0;
  zval_(Znummergetot)= 0;
  zval_(Znummergemax)= 0;
  zval_(Zvertices)= qh num_vertices - qh_setsize (qh del_vertices);
  if (qh MERGING || qh APPROXhull)
    wmax_(Wmaxoutside, qh max_outside);
  if (qh MERGING)
    wmin_(Wminvertex, qh min_vertex);
  FORALLfacets
    facet->seen= False;
  if (qh DELAUNAY) {
    FORALLfacets {
      if (facet->upperdelaunay)
        facet->seen= True; /* remove from angle statistics */
    }
  }
  FORALLfacets {
    if (facet->visible && qh NEWfacets)
      continue;
    sizvertices= qh_setsize (facet->vertices);
    sizneighbors= qh_setsize (facet->neighbors);
    sizridges= qh_setsize (facet->ridges);
    zinc_(Znumfacets);
    zadd_(Znumvertices, sizvertices);
    zmax_(Zmaxvertices, sizvertices);
    zadd_(Znumneighbors, sizneighbors);
    zmax_(Zmaxneighbors, sizneighbors);
    zadd_(Znummergetot, facet->nummerge);
    zmax_(Znummergemax, facet->nummerge);