📄 qhull.h
字号:
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 ============================*/
extern char qh_version[]; /* defined in unix.c */
/*-<a href="qh-c.htm#global"
>--------------------------------</a><a name="qh">-</a>
qh
all global variables for qhull are in qh, qhmem, and qhstat
notes:
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
struct qhT {
/*-<a href="qh-c.htm#global"
>--------------------------------</a><a name="qh-const">-</a>
qh constants
configuration flags and constants for Qhull
notes:
The user configures Qhull by defining flags. They are
copied into qh by qh_setflags(). qh-opt.htm defines the 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 halfspace 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 */
realT MAXcoplanar; /* 'Un' max distance below a facet to be coplanar*/
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 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 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 random 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 RERUN; /* 'TRn' rerun qhull n times (qh.build_cnt) */
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*/
/* also used by qh_build_withresart for err exit*/
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 TRACElastrun; /* qh.TRACElevel applies to last qh.RERUN */
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 halfspace 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 hull_dim; /* dimension of hull, set by initbuffers */
int input_dim; /* dimension of input, set by initbuffers */
int num_points; /* number of input points */
pointT *first_point; /* array of input points, see POINTSmalloc */
boolT POINTSmalloc; /* true if qh first_point/num_points allocated */
pointT *input_points; /* copy of original qh.first_point for input points for qh_joggleinput */
boolT input_malloc; /* true if qh input_points malloc'd */
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_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-c.htm#global"
>--------------------------------</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-c.htm#global"
>--------------------------------</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-c.htm#global"
>--------------------------------</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;
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-c.htm#global"
>--------------------------------</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; /* 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) */
/*-<a href="qh-c.htm#global"
>--------------------------------</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-c.htm#global"
>--------------------------------</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-c.htm#global"
>--------------------------------</a><a name="qh-static">-</a>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -