qhull.h

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

   qhmem is defined in mem.h and qhstat is defined in stat.h

   access to qh_qh is via the "qh" macro.  See qh_QHpointer in user.h
*/

typedef struct qhT qhT;    
#if qh_QHpointer
#define qh qh_qh->
extern qhT *qh_qh;     /* allocated in global.c */
#else
#define qh qh_qh.
extern qhT qh_qh;
#endif
extern char qh_version[];  /* defined in unix.c */

struct qhT {

  /*-user flags */

  boolT ALLpoints;        /* true 'Qi' if search all points for initial simplex */
  boolT ANGLEmerge;	  /* true 'Qa' if sort potential merges by angle */
  boolT APPROXhull;       /* true 'Wn' if MINoutside set */
  realT MINoutside;       /*   'Wn' min. distance for an outside point */
  boolT ATinfinity;       /* true 'd' if point num_points-1 is "at-infinity"
                             false 'Qu' if upper hull (no point at-infinity) */
  boolT AVOIDold;         /* true 'Q4' if avoid old->new merges */
  boolT BESToutside;      /* true 'Qf' if partition points into best outsideset */
  boolT CDDinput;         /* true 'Pc' if input uses CDD format (1.0/offset first) */
  boolT CDDoutput;        /* true 'PC' if print normals in CDD format (offset first) */
  boolT CHECKfrequently;  /* true 'Tc' if checking frequently */
  realT premerge_cos;     /*   'A-n'   cos_max when pre merging */
  realT postmerge_cos;    /*   'An'    cos_max when post merging */
  boolT DELAUNAY;         /* true 'd' if computing DELAUNAY triangulation */
  boolT DOintersections;  /* true 'Gh' if print hyperplane intersections */
  int   DROPdim;          /* drops dim 'GDn' for 4-d -> 3-d output */
  boolT FORCEoutput;      /* true 'Po' if forcing output despite degeneracies */
  int   GOODpoint;        /* 1+n for 'QGn', good facet if visible/not(-) from point n*/
  pointT *GOODpointp;     /*   the actual point */
  boolT GOODthreshold;    /* true if qh lower_threshold/upper_threshold defined 
  			     false if qh SPLITthreshold */
  int   GOODvertex;       /* 1+n, good facet if vertex for point n */
  pointT *GOODvertexp;     /*   the actual point */
  boolT HALFspace;        /* true 'Hn,n,n' if half-space intersection */
  int   IStracing;        /* trace execution, 0=none, 1=least, 4=most, -1=events */
  int   KEEParea;         /* 'PAn' number of largest facets to keep */
  boolT KEEPcoplanar;     /* true if keeping nearest facet for coplanar points */
  boolT KEEPinside;       /* true if keeping nearest facet for inside points */
  int   KEEPmerge;         /* 'PMn' number of facets to keep with most merges */
  realT KEEPminArea;      /* 'PFn' minimum facet area to keep */
  boolT MERGEexact;	  /* true 'Qx' if exact merges (coplanar, degen, dupridge, flipped) */
  boolT MERGEindependent; /* true 'Q2' if merging independent sets */
  boolT MERGING;          /* true if exact-, pre- or post-merging, with angle and centrum tests */
  realT   premerge_centrum;  /*   'C-n' centrum_radius when pre merging */
  realT   postmerge_centrum; /*   'Cn' centrum_radius when post merging */
  boolT MERGEvertices;	  /* true 'Q3' if merging redundant vertices */
  realT MAXcoplanar;      /* 'Un' max distance below a facet to be coplanar*/
  realT MINvisible;       /* 'Vn' min. distance for a facet to be visible */
  boolT NOnearinside;     /* true 'Q8' if ignore near-inside points when partitioning */
  boolT ONLYgood; 	  /* true 'Qg' if process points with good visible or horizon facets */
  boolT ONLYmax; 	  /* true 'Qm' if only process points that increase max_outside */
  boolT POINTSmalloc;     /* true if qh first_point/num_points allocated */
  boolT POSTmerge;        /* true if merging after buildhull (Cn or An) */
  boolT PREmerge;         /* true if merging during buildhull (C-n or A-n) */
  			/* NOTE: some of these names are similar to qh_PRINT names */
  boolT PRINTcentrums;	  /* true 'Gc' if printing centrums */
  boolT PRINTcoplanar;    /* true 'Gp' if printing coplanar points */
  int	PRINTdim;      	  /* print dimension for Geomview output */
  boolT PRINTdots;        /* true 'Ga' if printing all points as dots */
  boolT PRINTgood;        /* true 'Pg' if printing good facets */
  boolT PRINTinner;	  /* true 'Gi' if printing inner planes */
  boolT PRINTneighbors;	  /* true 'PG' if printing neighbors of good facets */
  boolT PRINTnoplanes;	  /* true 'Gn' if printing no planes */
  boolT PRINToptions1st;  /* true 'FO' if printing options to stderr */
  boolT PRINTouter;	  /* true 'Go' if printing outer planes */
  boolT PRINTprecision;   /* false 'Pp' if not reporting precision problems */
  qh_PRINT PRINTout[qh_PRINTEND]; /* list of output formats to print */
  boolT PRINTridges;      /* true 'Gr' if print ridges */
  boolT PRINTspheres;     /* true 'Gv' if print vertices as spheres */
  boolT PRINTstatistics;  /* true 'Ts' if printing statistics to stderr */
  boolT PRINTsummary;     /* true 's' if printing summary to stderr */
  boolT PROJECTdelaunay;  /* true if DELAUNAY, no readpoints() and
			     need projectinput() for Delaunay */
  int   PROJECTinput;     /* number of projected dimensions 'bn:0Bn:0' */
  boolT QUICKhelp;	  /* true if quick help message for degen input */
  boolT RANDOMdist;       /* true if randomly change distplane and setfacetplane */
  realT RANDOMfactor;     /*    maximum perturbation */
  realT RANDOMa;         /*  qh_randomfactor is randr * RANDOMa + RANDOMb */
  realT RANDOMb;
  boolT RANDOMoutside;    /* true if select a random outside point */
  int	REPORTfreq;       /* buildtracing reports every n facets */
  int   REPORTfreq2;	  /* tracemerging reports every REPORTfreq/2 facets */
  int	ROTATErandom;	  /* 'QRn' seed, 0 time, >= rotate input */
  boolT SCALEinput;       /* true if scaling input, 'Qb' */
  boolT SETroundoff;      /* true 'E' if qh DISTround is predefined */
  boolT SKIPcheckmax;	  /* true 'Q5' if skip qh_check_maxout */
  boolT SKIPconvex;       /* true 'Q6' if skip convexity testing during pre-merge */
  boolT SPLITthresholds;  /* true if upper_/lower_threshold defines a region
                               used only for printing (not for qh ONLYgood) */
  int	STOPcone;         /* 'TCn' 1+n for stopping after cone for point n*/
  int	STOPpoint;        /* 'TVn' 'TV-n' 1+n for stopping after/before(-) 
			                adding point n */
  boolT TESTvneighbors;   /*  true 'Qv' if test vertex neighbors at end */
  int   TRACElevel;       /* 'Tn' conditional IStracing level */
  int   TRACEpoint;       /* 'TPn' start tracing when point n is a vertex */
  realT TRACEdist;        /* 'TWn' start tracing when merge distance too big */
  int   TRACEmerge;       /* 'TMn' start tracing before this merge */
  boolT VERIFYoutput;     /* true 'Tv' if verify output at end of qhull */
  boolT VIRTUALmemory;    /* true 'Q7' if depth-first processing in buildhull */
  boolT VORONOI;	  /* true 'v' if computing Voronoi diagram */

  /* -input constants */
  realT AREAfactor;       /* 1/(hull_dim-1)! for converting det's to area */
  boolT DOcheckmax;       /* true if calling qh_check_maxout (qh_initqhull_globals) */
  char	*feasible_string;  /* feasible point 'Hn,n,n' for half-space intersection */
  coordT *feasible_point;  /*    as coordinates, both malloc'd */
  boolT GETarea;          /* true if need to compute facet areas in io.c */
  boolT KEEPnearinside;   /* true if near-inside points in coplanarset */
  int 	input_dim;	  /* dimension of input, set by initbuffers */
  int 	num_points;       /* number of input points */
  pointT *first_point;    /* array of input points, malloc'd */
  int 	hull_dim;         /* dimension of hull, set by initbuffers */
  char 	qhull_command[256];/* command line that invoked this program */
  char 	rbox_command[256]; /* command line that produced the input points */
  char  qhull_options[512]; /* descriptive list of options */
  int   qhull_optionslen; /*    length of line */
  boolT VERTEXneighbors;  /* true if maintaining vertex neighbors */
  boolT ZEROcentrum;      /* true if 'C-0' or 'C-0 Qx'.  sets ZEROall_ok */
  realT *upper_threshold; /* don't print if facet->normal[k]>=upper_threshold[k]
                             must set either GOODthreshold or SPLITthreshold
  			     if Delaunay, default is 0.0 for upper envelope */
  realT *lower_threshold; /* don't print if facet->normal[k] <=lower_threshold[k] */
  realT *upper_bound;     /* scale point[k] to new upper bound */
  realT *lower_bound;     /* scale point[k] to new lower bound 
  			     project if both upper_ and lower_bound == 0 */

  /* -precision constants, computed in qh_maxmin */
  
  realT ANGLEround;       /* max round off error for angles */
  realT centrum_radius;   /* max centrum radius for convexity (roundoff added) */
  realT cos_max;	  /* max cosine for convexity (roundoff added) */
  realT DISTround;        /* max round off error for distances, 'E' overrides */
  realT maxmaxcoord;      /* max coordinate in any dimension */
  realT MINdenom_1;       /* min. abs. value for 1/x */
  realT MINdenom;         /*    use divzero if denominator < MINdenom */
  realT MINdenom_1_2;     /* min. abs. val for 1/x that allows normalization */
  realT MINdenom_2;       /*    use divzero if denominator < MINdenom_2 */
  realT MINnorm;          /* min. norm for not redoing qh_sethyperplane_det */
  realT *NEARzero;        /* hull_dim array for near zero in gausselim */
  realT NEARinside;       /* keep points for qh_check_maxout if close to facet */
  realT ONEmerge;         /* max distance for merging simplicial facets */
  realT WIDEfacet;        /* size of wide facet for skipping ridge in
			     area computation and locking centrum */
  
  /* -internal constants */

  char qhull[sizeof("qhull")]; /* for checking ownership */
  void *old_stat;         /* pointer to saved qh_qhstat, qh_save_qhull */
  jmp_buf errexit;        /* exit label for qh_errexit, defined by setjmp() */
  char jmpXtra[40];       /* extra bytes in case jmp_buf is defined wrong */
  FILE *fin;              /* pointer to input file, init by qh_meminit */
  FILE *fout;             /* pointer to output file */
  FILE *ferr;             /* pointer to error file */
  pointT *interior_point; /* center point of the initial simplex*/
  int   normal_size;      /* size in bytes for facet normals and point coords*/
  int   center_size;      /* size in bytes for Voronoi centers */
  int   TEMPsize;         /* size for small, temporary sets (in quick mem) */

  /* -list of all facets, from facet_list to facet_tail, see qh_appendfacet */
 
  facetT *facet_list;     /* first facet */
  facetT  *facet_tail;     /* end of facet_list (dummy facet) */
  facetT *facet_next;     /* next facet for buildhull()
    			     all previous facets do not have outside sets*/
  facetT *newfacet_list;  /* list of new facets to end of facet_list */
  facetT *visible_list;   /* list of visible facets preceeding newfacet_list,
                             facet->visible set */
  int       num_visible;  /* current number of visible facets */
  unsigned tracefacet_id;  /* set at init, then can print whenever */
  facetT *tracefacet;     /*   set in newfacet/mergefacet, undone in delfacet*/
  unsigned tracevertex_id;  /* set at buildtracing, can print whenever */
  vertexT *tracevertex;     /*   set in newvertex, undone in delvertex*/
  vertexT *vertex_list;   /* list of all vertices, to vertex_tail */
  vertexT  *vertex_tail;   
  vertexT *newvertex_list; /* list of vertices in newfacet_list, to vertex_tail
                             all vertices have 'newlist' set */
  int 	num_facets;	  /* number of facets in facet_list
			     includes visble faces (num_visible) */
  int 	num_vertices;     /* number of vertices in facet_list */
  int   num_outside;      /* number of points in outsidesets (for tracing) */
  int   num_good;         /* number of good facets (after findgood_all) */
  int 	facet_id;         /* id of next, new facet from newfacet() */
  int 	ridge_id;         /* id of next, new ridge from newridge() */
  unsigned vertex_id;        /* id of next, new vertex from newvertex() */

  /* -variables */
  
  unsigned hulltime;       /* ignore time to set up input and randomize */
  qh_CENTER CENTERtype;       /* current type of facet->center, qh_CENTER */
  int 	furthest_id;      /* pointid of furthest point, for tracing */
  facetT *GOODclosest;    /* closest facet to GOODthreshold in qh_findgood */
  realT max_outside;      /* maximum distance from a point to a facet,
			       before roundoff, not simplicial vertices
			       actual outer plane is +DISTround and
			       computed outer plane is +2*DISTround */
  realT max_vertex;       /* maximum distance (>0) from vertex to a facet,
			       before roundoff, not simplicial vertices */
  realT min_vertex;       /* minimum distance (<0) from vertex to a facet,
			       before roundoff, not simplicial vertices 
			       actual inner plane is -DISTround and
			       computed inner plane is -2*DISTround */
  boolT NEWfacets;        /* true while visible facets invalid due to new or merge
			      from makecone/attachnewfacets to deletevisible */
  boolT findbestnew;	  /* true if partitioning calls qh_findbestnew */
  boolT findbest_notsharp; /* true if new facets are at least 90 degrees */
  boolT NOerrexit;        /* true if qh_errexit is not available */
  realT PRINTcradius;     /* radius for printing centrums */
  realT PRINTradius;      /* radius for printing vertex spheres and points */
  boolT POSTmerging;      /* true when post merging */
  int 	printoutvar;	  /* temporary variable for qh_printbegin, etc. */
  int 	printoutnum;	  /* number of facets printed */
  boolT QHULLfinished;    /* True after qhull() is finished */
  realT totarea;          /* total facet area computed by qh_getarea */
  realT totvol;           /* total volume computed by qh_getarea */
  int 	visit_id;         /* unique id for searching neighborhoods, */
  int 	vertex_visit;     /* unique id for searching vertices */
  boolT ZEROall_ok;       /* True if qh_checkzero always succeeds */
  
  /* -sets */
  setT *facet_mergeset;   /* temporary set of merges to be done */
  setT *degen_mergeset;   /* temporary set of degenerate and redundant merges */
  setT *initial_points;   /* initial simplex for buildhull() */
  setT *hash_table;	  /* hash table for matching ridges in qh_matchfacets 
                             size is setsize() */
  int   num_hashentries;  /* current number of hashentries */
  setT *other_points;     /* additional points (first is qh interior_point) */