qhull.h

DT三角化实现

  int   qhull_optionlen;  /*    length of last line */
  int   qhull_optionsiz;  /*     size of qhull_options before qh_initbuild */
  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 */

/*-<a                             href="qh-globa.htm#TOC"
  >--------------------------------</a><a name="qh-prec">-</a>

  qh precision constants
    precision constants for Qhull

  notes:
    qh_detroundoff() computes the maximum roundoff error for distance
    and other computations.  It also sets default values for the
    qh constants above.
*/
  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 MAXabs_coord;     /* max absolute coordinate */
  realT MAXlastcoord;     /* max last coordinate for qh_scalelast */
  realT MAXsumcoord;      /* max sum of coordinates */
  realT MAXwidth;         /* max rectilinear width of point coordinates */
  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 MINlastcoord;     /* min. last coordinate for qh_scalelast */
  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 outside_err;      /* application's epsilon for coplanar points
                             qh_check_bestdist() qh_check_points() reports error if point outside */
  realT WIDEfacet;        /* size of wide facet for skipping ridge in
			     area computation and locking centrum */
  
/*-<a                             href="qh-globa.htm#TOC"
  >--------------------------------</a><a name="qh-intern">-</a>

  qh internal constants
    internal constants for Qhull
*/
  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 by compiler */
  jmp_buf restartexit;    /* restart label for qh_errexit, defined by setjmp() */
  char jmpXtra2[40];      /* extra bytes in case jmp_buf is defined wrong by compiler*/
  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) */

/*-<a                             href="qh-globa.htm#TOC"
  >--------------------------------</a><a name="qh-lists">-</a>

  qh facet and vertex lists
    defines lists of facets, new facets, visible facets, vertices, and
    new vertices.  Includes counts, next ids, and trace ids.
  see:
    qh_resetlists()
*/
  facetT *facet_list;     /* first facet */
  facetT  *facet_tail;     /* end of facet_list (dummy facet) */
  facetT *facet_next;     /* next facet for buildhull()
    			     previous facets do not have outside sets
                             NARROWhull: previous facets may have coplanar outside sets for qh_outcoplanar */
  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;    /*      end of vertex_list (dummy vertex) */
  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 and RANDOMoutside)
                               includes coplanar outsideset points for NARROWhull/qh_outcoplanar() */
  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() */

/*-<a                             href="qh-globa.htm#TOC"
  >--------------------------------</a><a name="qh-var">-</a>

  qh global variables
    defines minimum and maximum distances, next visit ids, several flags,
    and other global variables.
    initialize in qh_initbuild or qh_maxmin if used in qh_buildhull
*/
  unsigned long hulltime; /* ignore time to set up input and randomize */
                          /*   use unsigned to avoid wrap-around errors */
  boolT ALLOWrestart;     /* true if qh_precision can use qh.restartexit */
  int   build_cnt;        /* number of calls to qh_initbuild */
  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 JOGGLEmax;        /* set 'QJn' if randomly joggle input */
  boolT maxoutdone;       /* set qh_check_maxout(), cleared by qh_addpoint() */
  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, due to a merge */
  realT min_vertex;       /* minimum distance (<0) from vertex to a facet,
			       before roundoff, due to a merge
			       if qh.JOGGLEmax, qh_makenewplanes sets it
  			       recomputed if qh.DOcheckmax, default -qh.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;          /* 'FA': total facet area computed by qh_getarea */
  realT totvol;           /* 'FA': 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) */
  
/*-<a                             href="qh-globa.htm#TOC"
  >--------------------------------</a><a name="qh-set">-</a>

  qh global sets
    defines sets for merging, initial simplex, hashing, extra input points,
    and deleted vertices
*/
  setT *facet_mergeset;   /* temporary set of merges to be done */
  setT *degen_mergeset;   /* temporary set of degenerate and redundant merges */
  setT *hash_table;	  /* hash table for matching ridges in qh_matchfacets
                             size is setsize() */
  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 */

/*-<a                             href="qh-globa.htm#TOC"
  >--------------------------------</a><a name="qh-buf">-</a>

  qh global buffers
    defines buffers for maxtrix operations, input, and error messages
*/
  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 */
  
/*-<a                             href="qh-globa.htm#TOC"
  >--------------------------------</a><a name="qh-static">-</a>

  qh static variables
    defines static variables for individual functions

  notes:
    do not use 'static' within a function.  Multiple instances of qhull
    may exist.

    do not assume zero initialization, 'QPn' may cause a restart
*/
  boolT ERREXITcalled;    /* true during errexit (prevents duplicate calls */
  boolT firstcentrum; 	  /* for qh_printcentrum */
  realT last_low;         /* qh_scalelast parameters for qh_setdelaunay */
  realT last_high;
  realT last_newhigh;
  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 *coplanarset;      /* set of coplanar facets for searching qh_findbesthorizon() */
};

/*=========== -macros- =========================*/

/*-<a                             href="qh-poly.htm#TOC"
  >--------------------------------</a><a name="otherfacet_">-</a>

  otherfacet_(ridge, facet)
    return neighboring facet for a ridge in facet
*/
#define otherfacet_(ridge, facet) \
                        (((ridge)->top == (facet)) ? (ridge)->bottom : (ridge)->top)

/*-<a                             href="qh-poly.htm#TOC"
  >--------------------------------</a><a name="getid_">-</a>

  getid_(p)
    return ID for facet, ridge, or vertex
    return MAXINT if NULL (-1 causes type conversion error )
*/
#define getid_(p)       ((p) ? (p)->id : -1)

/*============== FORALL macros ===================*/

/*-<a                             href="qh-poly.htm#TOC"
  >--------------------------------</a><a name="FORALLfacets">-</a>

  FORALLfacets { ... }
    assign 'facet' to each facet in qh.facet_list

  notes:
    uses 'facetT *facet;'
    assumes last facet is a sentinel

  see:
    FORALLfacet_( facetlist )
*/
#define FORALLfacets for (facet=qh facet_list;facet && facet->next;facet=facet->next)

/*-<a                             href="qh-poly.htm#TOC"
  >--------------------------------</a><a name="FORALLpoints">-</a>

  FORALLpoints { ... }
    assign 'point' to each point in qh.first_point, qh.num_points

  declare:
    coordT *point, *pointtemp;
*/
#define FORALLpoints FORALLpoint_(qh first_point, qh num_points)

/*-<a                             href="qh-poly.htm#TOC"
  >--------------------------------</a><a name="FORALLpoint_">-</a>

  FORALLpoint_( points, num) { ... }
    assign 'point' to each point in points array of num points

  declare:
    coordT *point, *pointtemp;
*/
#define FORALLpoint_(points, num) for(point= (points), \