pelqhull.h

Gambit 是一个游戏库理论软件

  boolT MERGING;          /* true if merging, with angle and centrum tests */
  realT   premerge_centrum;  /*   'R-n' centrum_radius when pre merging */
  realT   postmerge_centrum; /*   'Rn' centrum_radius when post merging */
  realT MINvisible;       /* min. distance for a facet to be visible */
  boolT ONLYgood; 	  /* only process points with good visible or horizon facets */
  boolT ONLYmax; 	  /* only process points that increase max_outside */
  boolT POINTSmalloc;     /* true if qh first_point/num_points allocated */
  boolT POSTmerge;        /* true if merging after buildhull (C-n or R-n) */
  boolT PREmerge;         /* true if merging during buildhull (Cn or Rn) */
  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 PRINTouter;	  /* true 'Go' if printing outer planes */
  boolT PRINTprecision;   /* false 'Pp' if not reporting precision problems */
  int   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	ROTATErandom;	  /* 'QRn' seed, 0 time, >= rotate input */
  boolT SCALEinput;       /* true if scaling input, 'Qb' */
  boolT SETroundoff;      /* true 'E' if qh DISTround is predefined */
  boolT SPLITthresholds;  /* true if upper_/lower_threshold defines a region
                               used only for printing (not for qh ONLYgood) */
  int	STOPcone;         /* 1+n for stopping after building cone for point n*/
  int	STOPpoint;        /* 1+n for stopping after/before(-) adding point n*/
  int   TRACElevel;       /* conditional IStracing level */
  int   TRACEpoint;       /* start tracing when point n becomes a vertex */
  realT TRACEdist;        /* start tracing when merge distance too big */
  int   TRACEmerge;       /* start tracing before this merge */
  boolT VERIFYoutput;     /* true 'Tv' if verify output at end of qhull */
  boolT VERTEXneighbors;  /* true if maintaining vertex neighbors */
  boolT VIRTUALmemory;    /* true if depth-first processing in buildhull */
  boolT VORONOI;	  /* true 'v' if computing Voronoi diagram */

  /* -input constants */
  int 	input_dim;	  /* dimension of input, set by initbuffers */
  int 	num_points;       /* number of input points */
  pointT *first_point;    /* first input point */
  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 */
  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 centrum_radius;   /* max centrum radius for convexity (roundoff added) */
  realT cos_max;	  /* max cosine for convexity (roundoff added) */
  realT maxmaxcoord;      /* max coordinate in any dimension */
  realT DISTround;        /* max round off error for distances, 'E' overrides */
  realT ONEmerge;         /* max distance for merging simplicial facets */
  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 *NEARzero;        /* hull_dim array for near zero in gausselim */
  
  /* -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 */
  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_next;     /* next facet for buildhull()
    			     all previous facets do not have outside sets*/
  facetT *visible_list;   /* list of visible facets, with visible set */
  int       num_visible;  /* current number of visible facets */
  facetT *newfacet_list;  /* list of new facets to end of facet_list */
  facetT *facet_tail;     /* end of facet_list (dummy facet) */
  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 
                             all vertices have 'new' 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 */
  int 	num_coplanar; 	  /* number of coplanar points */
  int   num_good;         /* number of good facets (after findgood_all) */
  unsigned newfacet_id;   /* new facet if facet->id >= newfacet_id */
  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 */
  
  clock_t hulltime;       /* ignore time to set up input and randomize */
  int	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 */
  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 
			       defines coplanar points */
  boolT NEWfacets;        /* true while visible facets invalid
			      from makecone/attachnewfacets to deletevisible */
  boolT NEWmerges;        /* true while merging,
			     facet->flipped is defined as facet->newmerge */
  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 */
  int 	visit_id;         /* unique id for searching neighborhoods, */
  int 	vertex_visit;     /* unique id for searching vertices */
  
  /* -sets */
  setT *facet_mergeset;   /* temporary set of merges to be done */
  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) */
  setT *del_vertices;     /* vertices to partition and delete with visible 
                             facets.  Have deleted set for checkfacet */

  /* -buffers */
  coordT *gm_matrix;      /* (dim+1)Xdim matrix for geom.c */
  coordT **gm_row;        /* array of gm_matrix rows */
  char* line;             /* malloc'd input line of maxline+1 chars */
  int maxline;
  
  /* -statics */
  boolT firstcentrum; 	  /* for qh_printcentrum */
  int  lastreport;        /* for qh_buildtracing */
  int  mergereport;       /* for qh_tracemerging */
  boolT old_randomdist;   /* save in io.c for RANDOMdist */
  int   ridgeoutnum;      /* number of ridges in 4OFF output */
  void *old_qhstat;       /* for saving qh_qhstat in save_qhull() */
  setT *old_tempstack;     /* for saving qhmem.tempstack in save_qhull */
};

/* =========== -macros- ========================= 
-otherfacet_(ridge, facet)   return neighboring facet for a ridge in facet
-getid_(p)		     return id or -1 if NULL
*/

#define otherfacet_(ridge, facet) \
                        (((ridge)->top == (facet)) ? (ridge)->bottom : (ridge)->top)
#define getid_(p)       ((p) ? (p)->id : -1)

/* ---------------------------------------------
-FORALL and FOREACH macros

   These all iterate using a variable of the same name, e.g. FORALLfacets
   and FOREACHfacet_ uses 'facet' declared by 'facetT *facet'.  The macros
   may use auxiliary variables as indicated.

-FORALLfacets                iterate over all facets in facetlist 
-FORALLpoint_(points, num)   iterate over num points (uses 'pointT *pointtemp')
-FORALLvertices              iterate over all vertices in vertex_list

-FOREACHfacet_(facets)	     iterate over facet set (uses 'facetT **facetp')
-FOREACHneighbor_(facet)     iterate over facet->neighbors (uses 'facetT **neighborp')
-FOREACHpoint_(points)       iterate over point set (uses 'pointT **pointp')
-FOREACHridge_(ridges)	     iterate over ridge set (uses 'ridgeT **ridgep')
-FOREACHvertex_(vertice)     iterate over vertex set (uses 'vertexT **vertexp')
-FOREACHadjacent_(vertex)    iterate over adjacent vertices to vertex 
-FOREACHneighbor_(vertex)    iterate over neighboring facets to vertex 

-FOREACHfacet_i_(facets)    iterate over facets by facet_i and facet_n
-FOREACHneighbor_i_(facet)  iterate over facet->neighbors by neighbor_i, neighbor_n
-FOREACHvertex_i_(vertices) iterate over vertices by vertex_i, vertex_n
-FOREACHpoint_i_(points)    iterate over points by point_i, point_n
-FOREACHridge_i_(ridges)    iterate over ridges by ridge_i, ridge_n
-FOREACHadjacent_i_(vertex) iterate over adjacents by adjacent_i, adjacent_n
-FOREACHneighbor_i_(vertex) iterate over vertex->neighbors by neighbor_i, neighbor_n

 WARNING: nested loops can't use the same variable (define another FOREACH)
 WARNING: strange behavior if don't fully brace when nested (including
        intervening blocks, e.g. FOREACH...{ if () FOREACH...} )
 poly.h defines other FOREACH/FORALL macros
 set.h  defines FOREACHsetelement and contains additional notes
*/
#define FORALLfacets for (facet=qh facet_list;facet && facet->next;facet=facet->next)
#define FORALLpoints FORALLpoint_(qh first_point, qh num_points)
#define FORALLvertices for (vertex=qh vertex_list;vertex && vertex->next;vertex= vertex->next)

#define FORALLpoint_(points, num) for(point= (points), \
      pointtemp= (points)+qh hull_dim*(num); point < pointtemp; point += qh hull_dim)
#define FOREACHfacet_(facets)    FOREACHsetelement_(facetT, facets, facet)
#define FOREACHneighbor_(facet)  FOREACHsetelement_(facetT, facet->neighbors, neighbor)
#define FOREACHpoint_(points)    FOREACHsetelement_(pointT, points, point)
#define FOREACHridge_(ridges)    FOREACHsetelement_(ridgeT, ridges, ridge)
#define FOREACHvertex_(vertices) FOREACHsetelement_(vertexT, vertices,vertex)
#define FOREACHadjacent_(vertex) FOREACHsetelement_(vertexT, vertex->adjacencies, adjacent)

#define FOREACHfacet_i_(facets)    FOREACHsetelement_i_(facetT, facets, facet)
#define FOREACHneighbor_i_(facet)  FOREACHsetelement_i_(facetT, facet->neighbors, neighbor)
#define FOREACHpoint_i_(points)    FOREACHsetelement_i_(pointT, points, point)
#define FOREACHridge_i_(ridges)    FOREACHsetelement_i_(ridgeT, ridges, ridge)
#define FOREACHvertex_i_(vertices) FOREACHsetelement_i_(vertexT, vertices,vertex)

/* ======= -functions =========== 

  	see corresponding .c file for definitions

	Qhull functions (see qhull.c and qhull_a.h)
-qhull		construct the convex hull of a set of points
-addpoint       add point to hull (must be above facet)
-delpoint       delete vertex for point from hull

	User redefinable functions (see user.c)
-errexit	 	return exitcode to system after an error
-errprint		print erroneous facets, ridge, and vertex
-printfacetlist		print all fields for a list of facets
-user_memsizes          define up to 10 additional quick allocation sizes
  	
	Geometric functions (see geom.c and geom.h, other useful functions)
-gram_schmidt   implements Gram-Schmidt orthogonalization by rows
-projectinput  project input along one or more dimensions + Delaunay projection
-randommatrix   generate a random dimXdim matrix in range (-1,1)
-rotatepoints   rotate numpoints points by a row matrix
-scaleinput    scale input to new lowbound and highbound
-findbest      find visible facet for a point starting at a facet

	Global init/free functions (see global.c and qhull_a.h)
-freeqhull	     free memory used by qhull
-init_qhull_command  build qhull_command from argc/argv
-initflags	     set flags and initialized constants from command line
-initqhull_buffers   initialize global memory buffers
-initqhull_globals   initialize globals
-initqhull_mem	initialize mem.c for qhull
-initqhull_start     start initialization of qhull
-initthresholds	     set thresholds for printing and scaling from command line
-restore_qhull       restores a saved qhull
-save_qhull          saves qhull for later restoring

	Input/output functions (see io.c and io.h)
-readpoints     read points from input

	Polyhedron functions (see poly.c)
-check_output	check output data structure according to user flags
-check_points	verify that all points are inside the hull

-point          return point for a point id, or NULL if unknown
-pointid        return id for a point, or -1 if not known

-facetvertices  returns temporary set of vertices in a set of facets
-pointfacet	return temporary set of facets indexed by point id
-pointvertex	return temporary set of vertices indexed by point id
*/

/********* -qhull.c prototypes (duplicated from qhull_a.h) ***************/

void    qh_qhull (void);
boolT   qh_addpoint (pointT *furthest, facetT *facet, boolT checkdist);
boolT   qh_delpoint (pointT *point, facetT *facet);