allegiance/qhull/qhull.h

/* qhull.h -- user-level header file for using qhull.a library
   
   see README, qhull_a.h
   
   see user.h for all user defineable constants

   copyright (c) 1993, 1997 The Geometry Center

   defines qh_qh, global data structure for qhull.  
   
   NOTE: access to qh_qh is via the 'qh' macro.  This allows
   qh_qh to be either a pointer or a structure.  An example
   of using qh is "qh DROPdim" which accesses the DROPdim
   field of qh_qh.  Similarly, access to qh_qhstat is via
   the 'qhstat' macro.
   
   includes function prototypes for qhull.c, geom.c, global.c, io.c, user.c

   use mem.h for mem.c
   use set.h for set.c
   
   see unix.c for an example of using qhull.h
   
   recompile qhull if you change this file
*/

#ifndef qhDEFqhull
#define qhDEFqhull 1

/* =========================== -included files ============== */

#include <setjmp.h>
#include <float.h>
#include <time.h>

#if __MWERKS__ && __POWERPC__
#include  <SIOUX.h>
#include  <Files.h>
#include	<Desk.h>
#endif

#ifndef __STDC__ 
#ifndef __cplusplus
#error  neither __STDC__ nor __cplusplus are defined.  Please use ANSI C or C++ to compile Qhull.
#endif
#endif

#include "user.h"      /* user defineable constants */

/* ============ -types- ==================== 

   Note: could use 'float' for data and 'double' for calculations (realT vs. coordT)
        This requires many type casts, and adjusted error bounds.
        Also C compilers may do expressions in double anyway.

*/


#define coordT realT  /* for stored coordinates and coefficients */
#define pointT coordT                 /* array of hull_dim coordinates */
#define flagT unsigned int            /* Boolean flag */
#define boolT unsigned int            /* Boolean value, nothing much is portable */
#ifdef False
#undef False
#endif
#ifdef True
#undef True
#endif
#define False 0
#define True 1

/* -CENTERtype to distinguish facet->center */
typedef enum {qh_ASnone= 0, qh_ASvoronoi, qh_AScentrum} qh_CENTER;

/* -output formats for printing (qh PRINTout).
notes:
  some of these names are similar to qh names.  The similar names are only
  used in switch statements in qh_printbegin() etc.
*/
typedef enum {qh_PRINTnone= 0, qh_PRINTarea, qh_PRINTaverage, 
  qh_PRINTcoplanars, qh_PRINTcentrums, 
  qh_PRINTfacets, qh_PRINTfacets_xridge, 
  qh_PRINTgeom, qh_PRINTids, qh_PRINTinner, qh_PRINTneighbors, 
  qh_PRINTnormals, qh_PRINTouter, qh_PRINTincidences, 
  qh_PRINTmathematica, qh_PRINTmerges, qh_PRINToff, 
  qh_PRINToptions, qh_PRINTpointintersect, qh_PRINTpointnearest,
  qh_PRINTpoints, qh_PRINTqhull, qh_PRINTsize, qh_PRINTsummary, 
  qh_PRINTtriangles, qh_PRINTvertices, qh_PRINTvneighbors,
  qh_PRINTEND} qh_PRINT;

/*---------------------------
       arguments
*/
#define qh_ALL 	    True     /* argument for printall and checkall parameters*/
#define qh_NOupper  True     /* argument for qh_findbest */


/*-------------------------------------------
-ERR - qhull exit codes, for indicating errors
*/
#define qh_ERRnone  0    /* no error occurred during qhull */
#define qh_ERRinput 1    /* input inconsistency */
#define qh_ERRsingular 2 /* singular input data */
#define qh_ERRprec  3    /* precision error */
#define qh_ERRmem   4    /* insufficient memory, matches mem.h */
#define qh_ERRqhull 5    /* internal error detected, matches mem.h */

/* ============ -structures- ====================
   each of the following structures is defined by a typedef
   all realT and coordT fields occur at the beginning of a structure
        (otherwise space may be wasted due to alignment)
   define all flags together and pack into 32-bit number
*/

typedef struct vertexT vertexT;
typedef struct ridgeT ridgeT;
typedef struct facetT facetT;
#ifndef DEFsetT
#define DEFsetT 1
typedef struct setT setT;          /* defined in set.h */
#endif

/* ----------------------------------------------
-facetT- specifies a facet. 

  qhull() generates the hull as a list of facets.  
*/

struct facetT {
#if !qh_COMPUTEfurthest
  coordT   furthestdist;/* distance to furthest point of outsideset */
#endif
#if qh_MAXoutside
  coordT   maxoutside;  /* max computed distance of point to facet
  			Before QHULLfinished this is an approximation
  			since maxdist not always set for mergefacet
			Actual outer plane is +DISTround and
			computed outer plane is +2*DISTround */
#endif
  coordT   offset;      /* exact offset of hyperplane from origin */ 
  coordT  *normal;      /* normal of hyperplane, hull_dim coefficients */
  union {               /* in order of testing */
   realT   area;        /* area of facet, only in io.c if  ->isarea */
   facetT *replace;	/*  replacement facet if ->visible and NEWfacets
  			     is NULL only if qh_mergedegen_redundant or interior */
   facetT *samecycle;   /*  cycle of facets from the same visible/horizon intersection,
   			     if ->newfacet */
   facetT *newcycle;    /*  in horizon facet, current samecycle of new facets */ 
  }f;
  coordT  *center;      /*  centrum for convexity, qh CENTERtype == qh_AScentrum */
      			/*  Voronoi center, qh CENTERtype == qh_ASvoronoi */
  facetT  *previous;    /* previous facet in the facet_list */
  facetT  *next;        /* next facet in the facet_list */
  setT    *vertices;    /* vertices for this facet, inverse sorted by id 
                           if simplicial, 1st vertex was apex/furthest */
  setT    *ridges;      /* explicit ridges for nonsimplicial facets.
  			   for simplicial facets, neighbors defines ridge */
  setT    *neighbors;   /* neighbors of the facet.  If simplicial, the kth 
			   neighbor is opposite the kth vertex, and the first
			   neighbor is the horizon facet for the first vertex*/
  setT    *outsideset;  /* set of points outside this facet
		           if non-empty, last point is furthest
			   if NARROWhull, includes coplanars for partitioning*/
  setT    *coplanarset; /* set of points coplanar with this facet
  			   > min_vertex and <= facet->max_outside
                           a point is assigned to the furthest facet
		           if non-empty, last point is furthest away */
  unsigned visitid;     /* visit_id, for visiting all neighbors,
			   all uses are independent */
  unsigned id;	        /* unique identifier from qh facet_id */
  unsigned nummerge:9;  /* number of merges */
#define qh_MAXnummerge 511 /*     2^9-1 */
  flagT	   newfacet:1;  /* True if facet on qh newfacet_list (new or merged) */
  flagT	   visible:1;   /* True if visible facet (will be deleted) */
  flagT    toporient:1; /* True if created with top orientation
			   after merging, use ridge orientation */
  flagT    simplicial:1;/* True if simplicial facet, ->ridges may be implicit */
  flagT    seen:1;      /* used to perform operations only once, like visitid */
  flagT	   flipped:1;   /* True if facet is flipped */
  flagT    upperdelaunay:1; /* True if facet is upper envelope of Delaunay triangulation */
  flagT    notfurthest:1; /* True if last point of outsideset is not furthest*/
  		/* flags primarily for output */
  flagT	   good:1;      /* True if a facet marked good for output */
  flagT    isarea:1;    /* True if facet->f.area is defined */
		/* flags for merging */
  flagT    dupridge:1;  /* True if duplicate ridge in facet */
  flagT    mergeridge:1; /* True if facet or neighbor contains a qh_MERGEridge
                            ->normal defined (also defined for mergeridge2) */
  flagT    mergeridge2:1; /* True if neighbor contains a qh_MERGEridge (mark_dupridges */
  flagT    coplanar:1;  /* True if horizon facet is coplanar at last use */
  flagT     mergehorizon:1; /* True if will merge into horizon (->coplanar) */
  flagT	    cycledone:1;/* True if mergecycle_all already done */
  flagT    tested:1;    /* True if facet convexity has been tested (false after merge */
  flagT    keepcentrum:1; /* True if keep old centrum after a merge */
  flagT	   newmerge:1;  /* True if facet is newly merged for reducevertices */
  flagT	   degenerate:1; /* True if facet is degenerate (degen_mergeset) */
  flagT	   redundant:1;  /* True if facet is redundant (degen_mergeset) */
};


/*----------------------------------------------
-ridgeT- specifies a ridge

  a ridge is hull_dim-1 simplex between two neighboring facets.  If the
  facets are non-simplicial, there may be more than one ridge between
  two facets.  E.G. a 4-d hypercube has two triangles between each pair
  of neighboring facets.
*/

struct ridgeT {
  setT    *vertices;    /* vertices belonging to this ridge, inverse sorted by id 
                           NULL if a degen ridge (matchsame) */
  facetT  *top;         /* top facet this ridge is part of */
  facetT  *bottom;      /* bottom facet this ridge is part of */
  unsigned id:24;       /* unique identifier, =>room for 8 flags */
  flagT    seen:1;      /* used to perform operations only once */
  flagT    tested:1;    /* True when ridge is tested for convexity */
  flagT    nonconvex:1; /* True if getmergeset detected a non-convex neighbor 
			   only one ridge between neighbors may have nonconvex */
};

/* ----------------------------------------------
-vertexT- specifies a vertex
*/

struct vertexT {
  vertexT *next;        /* next vertex in vertex_list */
  vertexT *previous;    /* previous vertex in vertex_list */
  pointT  *point;       /* hull_dim coordinates (coordT) */
  setT    *neighbors;   /* neighboring facets of vertex, qh_vertexneighbors()
			   inits in io.c or after first merge */
  unsigned visitid; /* for use with qh vertex_visit */
  unsigned id:24;   /* unique identifier, =>room for 8 flags */
  flagT    seen:1;      /* used to perform operations only once */
  flagT    seen2:1;     /* another seen flag */
  flagT    delridge:1;  /* vertex was part of a deleted ridge */
  flagT	   deleted:1;   /* true if vertex on qh del_vertices */
  flagT    newlist:1;   /* true if vertex on qh newvertex_list */
};

/* ======= -global variables -qh ============================ 

   all global variables for qhull are in qh, qhmem, and qhstat
   
   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 'Qs' 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 'Qz' if point num_points-1 is "at-infinity"
                             for improving precision in Delaunay triangulations */ 
  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 'Qc' if keeping nearest facet for coplanar points */
  boolT KEEPinside;       /* true 'Qi' if keeping nearest facet for inside points 
			      set automatically if 'd Qc' */
  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.  Default is round-off */
  realT   postmerge_centrum; /*   'Cn' centrum_radius when post merging.  Default is round-off */
  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 NOpremerge;       /* true 'Q0' if no defaults for C-0 or Qx */
  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 PICKfurthest;     /* true 'Q9' if process furthest of furthest points*/
  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 PRINTtransparent; /* true 'Gt' if print transparent outer ridges */
  boolT PROJECTdelaunay;  /* true if DELAUNAY, no readpoints() and
			     need projectinput() for Delaunay in qh_init_B */
  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 'Qbk' if scaling input */
  boolT SCALElast;        /* true 'Qbb' if scale last coord to max prev coord */
  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 UPPERdelaunay;    /* true 'Qu' if computing furthest-site Delaunay */
  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 MAXlowcoord;      /* max coordinate in all but last dimension */
  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 */
  boolT NARROWhull;       /* set in qh_initialhull if angle < qh_MAXnarrow */
  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) */
  unsigned facet_id;      /* id of next, new facet from newfacet() */
  unsigned ridge_id;      /* id of next, new ridge from newridge() */
  unsigned vertex_id;     /* id of next, new vertex from newvertex() */

  /* -variables */
  
  unsigned long hulltime; /* ignore time to set up input and randomize */
                          /*   use unsigned to avoid wrap-around errors */
  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 */
  unsigned int visit_id;         /* unique id for searching neighborhoods, */
  unsigned int vertex_visit;     /* unique id for searching vertices */
  boolT ZEROall_ok;       /* True if qh_checkzero always succeeds */
  boolT WAScoplanar;      /* True if qh_partitioncoplanar (qh_check_maxout) */
  
  /* -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) */
  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;
  coordT *half_space;     /* malloc'd input array for halfspace (qh normal_size+coordT) */
  coordT *temp_malloc;    /* malloc'd input array for points */
  
  /* -statics */
  boolT ERREXITcalled;    /* true during errexit (prevents duplicate calls */
  boolT firstcentrum; 	  /* for qh_printcentrum */
  unsigned lastreport;    /* for qh_buildtracing */
  int mergereport;        /* for qh_tracemerging */
  boolT old_randomdist;   /* save RANDOMdist when io, tracing, or statistics */
  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 */
  setT *searchset;        /* set of facets for searching in qh_findbest() */
  int   rand_seed;        /* for qh_rand/qh_srand */
};

/* =========== -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')
-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
-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 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)
-printsummary	print summary about the output

	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 for 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
-setdelaunay    project points to paraboloid for Delaunay triangulation
-sethalfspace_all generate dual for halfspace intersection with feasible point


	Global init/free functions (see global.c and qhull_a.h)
-freeqhull	     free memory used by qhull
-init_A              called before error handling initialized
-init_B              called after points are defined
-initflags	     set flags and initialized constants 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)
-dfacet		print facet by id
-dvertex	print vertex by id
-printsummary	print summary about the output
-produce_output prints out the result of qhull in desired format
-readpoints     read points from input

	Polyhedron functions (see poly.c or poly2.c)
-check_output	check output data structure according to user flags
-check_points	verify that all points are inside the hull
-findbestfacet find facet or best facet below a point 
-setvoronoi_all compute Voronoi centers for all facets
-nearvertex     return nearest vertex to point

-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

        Statistics functions (see stat.c)
-printallstatistics print all statistics

	other functions no longer needed by most users
-init_qhull_command  build qhull_command from argc/argv
-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
-findbest            find visible facet for a point starting at a facet
-findbestnew         find best newfacet for point

*/

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

void    qh_qhull (void);
boolT   qh_addpoint (pointT *furthest, facetT *facet, boolT checkdist);
void	qh_printsummary(FILE *fp);

/********* -user.c prototypes (alphabetical) **********************/

void 	qh_errexit(int exitcode, facetT *facet, ridgeT *ridge);
void 	qh_errprint(char* string, facetT *atfacet, facetT *otherfacet, ridgeT *atridge, vertexT *atvertex);
void    qh_printfacetlist(facetT *facetlist, setT *facets, boolT printall);
void 	qh_user_memsizes (void);

/***** -geom.c/geom2.c prototypes (duplicated from geom.h) ****************/

facetT *qh_findbest (pointT *point, facetT *facet, 
		     boolT bestoutside, boolT newfacets, boolT noupper,
		     realT *dist, boolT *isoutside, int *numpart);
facetT *qh_findbestnew (pointT *point, facetT *startfacet,
	   realT *dist, boolT *isoutside, int *numpart);
boolT   qh_gram_schmidt(int dim, realT **rows);
void	qh_printsummary(FILE *fp);
void    qh_projectinput (void);
void    qh_randommatrix (realT *buffer, int dim, realT **row);
void    qh_rotateinput (realT **rows);
void    qh_scaleinput (void);
void    qh_setdelaunay (int dim, int count, pointT *points);
coordT  *qh_sethalfspace_all (int dim, int count, coordT *halfspaces, pointT *feasible);

/***** -global.c prototypes (alphabetical) ***********************/

void 	qh_freebuffers (void);
void    qh_freeqhull (boolT allmem);
void    qh_init_A (FILE *infile, FILE *outfile, FILE *errfile, int argc, char *argv[]);
void    qh_init_B (coordT *points, int numpoints, int dim, boolT ismalloc);
void 	qh_init_qhull_command (int argc, char *argv[]);
void    qh_initbuffers (coordT *points, int numpoints, int dim, boolT ismalloc);
void 	qh_initflags (char *command);
void 	qh_initqhull_buffers (void);
void 	qh_initqhull_globals (coordT *points, int numpoints, int dim, boolT ismalloc);
void    qh_initqhull_mem (void);
void 	qh_initqhull_start (FILE *infile, FILE *outfile, FILE *errfile);
void 	qh_initthresholds (char *command);
#if qh_QHpointer
void 	qh_restore_qhull (qhT **oldqh);
qhT    *qh_save_qhull (void);
#endif

/***** -io.c prototypes (duplicated from io.h) ***********************/

void    dfacet( unsigned id);
void    dvertex( unsigned id);
void	qh_produce_output(void);
coordT *qh_readpoints(int *numpoints, int *dimension, boolT *ismalloc);


/********* -mem.c prototypes (duplicated from mem.h) **********************/

void qh_meminit (FILE *ferr);
void qh_memfreeshort (int *curlong, int *totlong);

/********* -poly.c/poly2.c prototypes (duplicated from poly.h) **********************/

void    qh_check_output (void);
void    qh_check_points (void);
setT   *qh_facetvertices (facetT *facetlist, setT *facets, boolT allfacets);
facetT *qh_findbestfacet (pointT *point, boolT bestoutside,
           realT *bestdist, boolT *isoutside);
vertexT *qh_nearvertex (facetT *facet, pointT *point, realT *bestdistp);
pointT *qh_point (int id);
setT   *qh_pointfacet (void /*qh.facet_list*/);
int     qh_pointid (pointT *point);
setT   *qh_pointvertex (void /*qh.facet_list*/);
void    qh_setvoronoi_all (void);

/********* -stat.c prototypes (duplicated from stat.h) **********************/

void    qh_printallstatistics (FILE *fp, char *string);

#endif /* qhDEFqhull */