Doxygen Source Code Documentation
qhull.h
Go to the documentation of this file.00001 /*<html><pre> -<a href="qh-qhull.htm" 00002 >-------------------------------</a><a name="TOP">-</a> 00003 00004 qhull.h 00005 user-level header file for using qhull.a library 00006 00007 see qh-qhull.htm, qhull_a.h 00008 00009 copyright (c) 1993-2001, The Geometry Center 00010 00011 defines qh_qh, global data structure for qhull. 00012 00013 NOTE: access to qh_qh is via the 'qh' macro. This allows 00014 qh_qh to be either a pointer or a structure. An example 00015 of using qh is "qh DROPdim" which accesses the DROPdim 00016 field of qh_qh. Similarly, access to qh_qhstat is via 00017 the 'qhstat' macro. 00018 00019 includes function prototypes for qhull.c, geom.c, global.c, io.c, user.c 00020 00021 use mem.h for mem.c 00022 use qset.h for qset.c 00023 00024 see unix.c for an example of using qhull.h 00025 00026 recompile qhull if you change this file 00027 */ 00028 00029 #ifndef qhDEFqhull 00030 #define qhDEFqhull 1 00031 00032 /*=========================== -included files ==============*/ 00033 00034 #include <setjmp.h> 00035 #include <float.h> 00036 #include <time.h> 00037 00038 #if __MWERKS__ && __POWERPC__ 00039 #include <SIOUX.h> 00040 #include <Files.h> 00041 #include <Desk.h> 00042 #endif 00043 00044 #ifndef __STDC__ 00045 #ifndef __cplusplus 00046 #if !_MSC_VER 00047 #error Neither __STDC__ nor __cplusplus is defined. Please use strict ANSI C or C++ to compile 00048 #error Qhull. You may need to turn off compiler extensions in your project configuration. If 00049 #error your compiler is a standard C compiler, you can delete this warning from qhull.h 00050 #endif 00051 #endif 00052 #endif 00053 00054 #include "user.h" /* user defineable constants */ 00055 00056 /*============ constants and basic types ====================*/ 00057 00058 /*-<a href="qh-geom.htm#TOC" 00059 >--------------------------------</a><a name="coordT">-</a> 00060 00061 coordT 00062 coordinates and coefficients are stored as realT (i.e., double) 00063 00064 notes: 00065 could use 'float' for data and 'double' for calculations (realT vs. coordT) 00066 This requires many type casts, and adjusted error bounds. 00067 Also C compilers may do expressions in double anyway. 00068 */ 00069 #define coordT realT 00070 /*-<a href="qh-geom.htm#TOC" 00071 >--------------------------------</a><a name="pointT">-</a> 00072 00073 pointT 00074 a point is an array of DIM3 coordinates 00075 */ 00076 #define pointT coordT 00077 00078 /*-<a href="qh-qhull.htm#TOC" 00079 >--------------------------------</a><a name="flagT">-</a> 00080 00081 flagT 00082 Boolean flag as a bit 00083 */ 00084 #define flagT unsigned int 00085 00086 /*-<a href="qh-qhull.htm#TOC" 00087 >--------------------------------</a><a name="boolT">-</a> 00088 00089 boolT 00090 boolean value, either True or False 00091 00092 notes: 00093 needed for portability 00094 */ 00095 #define boolT unsigned int 00096 #ifdef False 00097 #undef False 00098 #endif 00099 #ifdef True 00100 #undef True 00101 #endif 00102 #define False 0 00103 #define True 1 00104 00105 /*-<a href="qh-qhull.htm#TOC" 00106 >--------------------------------</a><a name="CENTERtype">-</a> 00107 00108 qh_CENTER 00109 to distinguish facet->center 00110 */ 00111 typedef enum 00112 { 00113 qh_ASnone = 0, qh_ASvoronoi, qh_AScentrum 00114 } 00115 qh_CENTER; 00116 00117 /*-<a href="qh-qhull.htm#TOC" 00118 >--------------------------------</a><a name="qh_PRINT">-</a> 00119 00120 qh_PRINT 00121 output formats for printing (qh.PRINTout). 00122 'Fa' 'FV' 'Fc' 'FC' 00123 00124 00125 notes: 00126 some of these names are similar to qh names. The similar names are only 00127 used in switch statements in qh_printbegin() etc. 00128 */ 00129 typedef enum {qh_PRINTnone= 0, 00130 qh_PRINTarea, qh_PRINTaverage, /* 'Fa' 'FV' 'Fc' 'FC' */ 00131 qh_PRINTcoplanars, qh_PRINTcentrums, 00132 qh_PRINTfacets, qh_PRINTfacets_xridge, /* 'f' 'FF' 'G' 'FI' 'Fi' 'Fn' */ 00133 qh_PRINTgeom, qh_PRINTids, qh_PRINTinner, qh_PRINTneighbors, 00134 qh_PRINTnormals, qh_PRINTouter, /* 'n' 'Fo' 'i' 'm' 'Fm' 'o' */ 00135 qh_PRINTincidences, qh_PRINTmathematica, qh_PRINTmerges, qh_PRINToff, 00136 qh_PRINToptions, qh_PRINTpointintersect, /* 'FO' 'Fp' 'FP' 'p' 'FQ' 'FS' */ 00137 qh_PRINTpointnearest, qh_PRINTpoints, qh_PRINTqhull, qh_PRINTsize, 00138 qh_PRINTsummary, qh_PRINTtriangles, /* 'Fs' 'Ft' 'Fv' 'FN' 'Fx' */ 00139 qh_PRINTvertices, qh_PRINTvneighbors, qh_PRINTextremes, 00140 qh_PRINTEND} qh_PRINT; 00141 00142 /*-<a href="qh-qhull.htm#TOC" 00143 >--------------------------------</a><a name="qh_ALL">-</a> 00144 00145 qh_ALL 00146 argument flag for selecting everything 00147 */ 00148 #define qh_ALL True 00149 #define qh_NOupper True /* argument for qh_findbest */ 00150 00151 /*-<a href="qh-qhull.htm#TOC" 00152 >--------------------------------</a><a name="qh_ERR">-</a> 00153 00154 qh_ERR 00155 Qhull exit codes, for indicating errors 00156 */ 00157 #define qh_ERRnone 0 /* no error occurred during qhull */ 00158 #define qh_ERRinput 1 /* input inconsistency */ 00159 #define qh_ERRsingular 2 /* singular input data */ 00160 #define qh_ERRprec 3 /* precision error */ 00161 #define qh_ERRmem 4 /* insufficient memory, matches mem.h */ 00162 #define qh_ERRqhull 5 /* internal error detected, matches mem.h */ 00163 00164 /* ============ -structures- ==================== 00165 each of the following structures is defined by a typedef 00166 all realT and coordT fields occur at the beginning of a structure 00167 (otherwise space may be wasted due to alignment) 00168 define all flags together and pack into 32-bit number 00169 */ 00170 00171 typedef struct vertexT vertexT; 00172 typedef struct ridgeT ridgeT; 00173 typedef struct facetT facetT; 00174 #ifndef DEFsetT 00175 #define DEFsetT 1 00176 typedef struct setT setT; /* defined in qset.h */ 00177 #endif 00178 00179 /*-<a href="qh-poly.htm#TOC" 00180 >--------------------------------</a><a name="facetT">-</a> 00181 00182 facetT 00183 defines a facet 00184 00185 notes: 00186 qhull() generates the hull as a list of facets. 00187 00188 topological information: 00189 f.previous,next doubly-linked list of facets 00190 f.vertices set of vertices 00191 f.ridges set of ridges 00192 f.neighbors set of neighbors 00193 f.toporient True if facet has top-orientation (else bottom) 00194 00195 geometric information: 00196 f.offset,normal hyperplane equation 00197 f.maxoutside offset to outer plane -- all points inside 00198 f.center centrum for testing convexity 00199 f.simplicial True if facet is simplicial 00200 f.flipped True if facet does not include qh.interior_point 00201 00202 for constructing hull: 00203 f.visible True if facet on list of visible facets (will be deleted) 00204 f.newfacet True if facet on list of newly created facets 00205 f.coplanarset set of points coplanar with this facet 00206 (includes near-inside points for later testing) 00207 f.outsideset set of points outside of this facet 00208 f.furthestdist distance to furthest point of outside set 00209 f.visitid marks visited facets during a loop 00210 f.replace replacement facet for to-be-deleted, visible facets 00211 f.samecycle,newcycle cycle of facets for merging into horizon facet 00212 00213 see below for other flags and fields 00214 */ 00215 struct facetT { 00216 #if !qh_COMPUTEfurthest 00217 coordT furthestdist;/* distance to furthest point of outsideset */ 00218 #endif 00219 #if qh_MAXoutside 00220 coordT maxoutside; /* max computed distance of point to facet 00221 Before QHULLfinished this is an approximation 00222 since maxdist not always set for mergefacet 00223 Actual outer plane is +DISTround and 00224 computed outer plane is +2*DISTround */ 00225 #endif 00226 coordT offset; /* exact offset of hyperplane from origin */ 00227 coordT *normal; /* normal of hyperplane, hull_dim coefficients */ 00228 union { /* in order of testing */ 00229 realT area; /* area of facet, only in io.c if ->isarea */ 00230 facetT *replace; /* replacement facet if ->visible and NEWfacets 00231 is NULL only if qh_mergedegen_redundant or interior */ 00232 facetT *samecycle; /* cycle of facets from the same visible/horizon intersection, 00233 if ->newfacet */ 00234 facetT *newcycle; /* in horizon facet, current samecycle of new facets */ 00235 }f; 00236 coordT *center; /* centrum for convexity, qh CENTERtype == qh_AScentrum */ 00237 /* Voronoi center, qh CENTERtype == qh_ASvoronoi */ 00238 facetT *previous; /* previous facet in the facet_list */ 00239 facetT *next; /* next facet in the facet_list */ 00240 setT *vertices; /* vertices for this facet, inverse sorted by ID 00241 if simplicial, 1st vertex was apex/furthest */ 00242 setT *ridges; /* explicit ridges for nonsimplicial facets. 00243 for simplicial facets, neighbors defines ridge */ 00244 setT *neighbors; /* neighbors of the facet. If simplicial, the kth 00245 neighbor is opposite the kth vertex, and the first 00246 neighbor is the horizon facet for the first vertex*/ 00247 setT *outsideset; /* set of points outside this facet 00248 if non-empty, last point is furthest 00249 if NARROWhull, includes coplanars for partitioning*/ 00250 setT *coplanarset; /* set of points coplanar with this facet 00251 > qh.min_vertex and <= facet->max_outside 00252 a point is assigned to the furthest facet 00253 if non-empty, last point is furthest away */ 00254 unsigned visitid; /* visit_id, for visiting all neighbors, 00255 all uses are independent */ 00256 unsigned id; /* unique identifier from qh facet_id */ 00257 unsigned nummerge:9; /* number of merges */ 00258 #define qh_MAXnummerge 511 /* 2^9-1 */ 00259 flagT newfacet:1; /* True if facet on qh newfacet_list (new or merged) */ 00260 flagT visible:1; /* True if visible facet (will be deleted) */ 00261 flagT toporient:1; /* True if created with top orientation 00262 after merging, use ridge orientation */ 00263 flagT simplicial:1;/* True if simplicial facet, ->ridges may be implicit */ 00264 flagT seen:1; /* used to perform operations only once, like visitid */ 00265 flagT seen2:1; /* used to perform operations only once, like visitid */ 00266 flagT flipped:1; /* True if facet is flipped */ 00267 flagT upperdelaunay:1; /* True if facet is upper envelope of Delaunay triangulation */ 00268 flagT notfurthest:1; /* True if last point of outsideset is not furthest*/ 00269 00270 /*-------- flags primarily for output ---------*/ 00271 flagT good:1; /* True if a facet marked good for output */ 00272 flagT isarea:1; /* True if facet->f.area is defined */ 00273 00274 /*-------- flags for merging ------------------*/ 00275 flagT dupridge:1; /* True if duplicate ridge in facet */ 00276 flagT mergeridge:1; /* True if facet or neighbor contains a qh_MERGEridge 00277 ->normal defined (also defined for mergeridge2) */ 00278 flagT mergeridge2:1; /* True if neighbor contains a qh_MERGEridge (mark_dupridges */ 00279 flagT coplanar:1; /* True if horizon facet is coplanar at last use */ 00280 flagT mergehorizon:1; /* True if will merge into horizon (->coplanar) */ 00281 flagT cycledone:1;/* True if mergecycle_all already done */ 00282 flagT tested:1; /* True if facet convexity has been tested (false after merge */ 00283 flagT keepcentrum:1; /* True if keep old centrum after a merge */ 00284 flagT newmerge:1; /* True if facet is newly merged for reducevertices */ 00285 flagT degenerate:1; /* True if facet is degenerate (degen_mergeset) */ 00286 flagT redundant:1; /* True if facet is redundant (degen_mergeset) */ 00287 }; 00288 00289 00290 /*-<a href="qh-poly.htm#TOC" 00291 >--------------------------------</a><a name="ridgeT">-</a> 00292 00293 ridgeT 00294 defines a ridge 00295 00296 notes: 00297 a ridge is DIM3-1 simplex between two neighboring facets. If the 00298 facets are non-simplicial, there may be more than one ridge between 00299 two facets. E.G. a 4-d hypercube has two triangles between each pair 00300 of neighboring facets. 00301 00302 topological information: 00303 vertices a set of vertices 00304 top,bottom neighboring facets with orientation 00305 00306 geometric information: 00307 tested True if ridge is clearly convex 00308 nonconvex True if ridge is non-convex 00309 */ 00310 struct ridgeT { 00311 setT *vertices; /* vertices belonging to this ridge, inverse sorted by ID 00312 NULL if a degen ridge (matchsame) */ 00313 facetT *top; /* top facet this ridge is part of */ 00314 facetT *bottom; /* bottom facet this ridge is part of */ 00315 unsigned id:24; /* unique identifier, =>room for 8 flags */ 00316 flagT seen:1; /* used to perform operations only once */ 00317 flagT tested:1; /* True when ridge is tested for convexity */ 00318 flagT nonconvex:1; /* True if getmergeset detected a non-convex neighbor 00319 only one ridge between neighbors may have nonconvex */ 00320 }; 00321 00322 /*-<a href="qh-poly.htm#TOC" 00323 >--------------------------------</a><a name="vertexT">-</a> 00324 00325 vertexT 00326 defines a vertex 00327 00328 topological information: 00329 next,previous doubly-linked list of all vertices 00330 neighbors set of adjacent facets (only if qh.VERTEXneighbors) 00331 00332 geometric information: 00333 point array of DIM3 coordinates 00334 */ 00335 struct vertexT { 00336 vertexT *next; /* next vertex in vertex_list */ 00337 vertexT *previous; /* previous vertex in vertex_list */ 00338 pointT *point; /* hull_dim coordinates (coordT) */ 00339 setT *neighbors; /* neighboring facets of vertex, qh_vertexneighbors() 00340 inits in io.c or after first merge */ 00341 unsigned visitid; /* for use with qh vertex_visit */ 00342 unsigned id:24; /* unique identifier, =>room for 8 flags */ 00343 flagT seen:1; /* used to perform operations only once */ 00344 flagT seen2:1; /* another seen flag */ 00345 flagT delridge:1; /* vertex was part of a deleted ridge */ 00346 flagT deleted:1; /* true if vertex on qh del_vertices */ 00347 flagT newlist:1; /* true if vertex on qh newvertex_list */ 00348 }; 00349 00350 /*======= -global variables -qh ============================*/ 00351 00352 extern char qh_version[]; /* defined in unix.c etc. */ 00353 00354 /*-<a href="qh-globa.htm#TOC" 00355 >--------------------------------</a><a name="qh">-</a> 00356 00357 qh 00358 all global variables for qhull are in qh, qhmem, and qhstat 00359 00360 notes: 00361 qhmem is defined in mem.h and qhstat is defined in stat.h 00362 access to qh_qh is via the "qh" macro. See qh_QHpointer in user.h 00363 */ 00364 typedef struct qhT qhT; 00365 #if qh_QHpointer 00366 #define qh qh_qh-> 00367 extern qhT *qh_qh; /* allocated in global.c */ 00368 #else 00369 #define qh qh_qh. 00370 extern qhT qh_qh; 00371 #endif 00372 00373 struct qhT { 00374 00375 /*-<a href="qh-globa.htm#TOC" 00376 >--------------------------------</a><a name="qh-const">-</a> 00377 00378 qh constants 00379 configuration flags and constants for Qhull 00380 00381 notes: 00382 The user configures Qhull by defining flags. They are 00383 copied into qh by qh_setflags(). qh-quick.htm#options defines the flags. 00384 */ 00385 boolT ALLpoints; /* true 'Qs' if search all points for initial simplex */ 00386 boolT ANGLEmerge; /* true 'Qa' if sort potential merges by angle */ 00387 boolT APPROXhull; /* true 'Wn' if MINoutside set */ 00388 realT MINoutside; /* 'Wn' min. distance for an outside point */ 00389 boolT ATinfinity; /* true 'Qz' if point num_points-1 is "at-infinity" 00390 for improving precision in Delaunay triangulations */ 00391 boolT AVOIDold; /* true 'Q4' if avoid old->new merges */ 00392 boolT BESToutside; /* true 'Qf' if partition points into best outsideset */ 00393 boolT CDDinput; /* true 'Pc' if input uses CDD format (1.0/offset first) */ 00394 boolT CDDoutput; /* true 'PC' if print normals in CDD format (offset first) */ 00395 boolT CHECKfrequently; /* true 'Tc' if checking frequently */ 00396 realT premerge_cos; /* 'A-n' cos_max when pre merging */ 00397 realT postmerge_cos; /* 'An' cos_max when post merging */ 00398 boolT DELAUNAY; /* true 'd' if computing DELAUNAY triangulation */ 00399 boolT DOintersections; /* true 'Gh' if print hyperplane intersections */ 00400 int DROPdim; /* drops dim 'GDn' for 4-d -> 3-d output */ 00401 boolT FORCEoutput; /* true 'Po' if forcing output despite degeneracies */ 00402 int GOODpoint; /* 1+n for 'QGn', good facet if visible/not(-) from point n*/ 00403 pointT *GOODpointp; /* the actual point */ 00404 boolT GOODthreshold; /* true if qh lower_threshold/upper_threshold defined 00405 false if qh SPLITthreshold */ 00406 int GOODvertex; /* 1+n, good facet if vertex for point n */ 00407 pointT *GOODvertexp; /* the actual point */ 00408 boolT HALFspace; /* true 'Hn,n,n' if halfspace intersection */ 00409 int IStracing; /* trace execution, 0=none, 1=least, 4=most, -1=events */ 00410 int KEEParea; /* 'PAn' number of largest facets to keep */ 00411 boolT KEEPcoplanar; /* true 'Qc' if keeping nearest facet for coplanar points */ 00412 boolT KEEPinside; /* true 'Qi' if keeping nearest facet for inside points 00413 set automatically if 'd Qc' */ 00414 int KEEPmerge; /* 'PMn' number of facets to keep with most merges */ 00415 realT KEEPminArea; /* 'PFn' minimum facet area to keep */ 00416 realT MAXcoplanar; /* 'Un' max distance below a facet to be coplanar*/ 00417 boolT MERGEexact; /* true 'Qx' if exact merges (coplanar, degen, dupridge, flipped) */ 00418 boolT MERGEindependent; /* true 'Q2' if merging independent sets */ 00419 boolT MERGING; /* true if exact-, pre- or post-merging, with angle and centrum tests */ 00420 realT premerge_centrum; /* 'C-n' centrum_radius when pre merging. Default is round-off */ 00421 realT postmerge_centrum; /* 'Cn' centrum_radius when post merging. Default is round-off */ 00422 boolT MERGEvertices; /* true 'Q3' if merging redundant vertices */ 00423 realT MINvisible; /* 'Vn' min. distance for a facet to be visible */ 00424 boolT NOnearinside; /* true 'Q8' if ignore near-inside points when partitioning */ 00425 boolT NOpremerge; /* true 'Q0' if no defaults for C-0 or Qx */ 00426 boolT ONLYgood; /* true 'Qg' if process points with good visible or horizon facets */ 00427 boolT ONLYmax; /* true 'Qm' if only process points that increase max_outside */ 00428 boolT PICKfurthest; /* true 'Q9' if process furthest of furthest points*/ 00429 boolT POSTmerge; /* true if merging after buildhull (Cn or An) */ 00430 boolT PREmerge; /* true if merging during buildhull (C-n or A-n) */ 00431 /* NOTE: some of these names are similar to qh_PRINT names */ 00432 boolT PRINTcentrums; /* true 'Gc' if printing centrums */ 00433 boolT PRINTcoplanar; /* true 'Gp' if printing coplanar points */ 00434 int PRINTdim; /* print dimension for Geomview output */ 00435 boolT PRINTdots; /* true 'Ga' if printing all points as dots */ 00436 boolT PRINTgood; /* true 'Pg' if printing good facets */ 00437 boolT PRINTinner; /* true 'Gi' if printing inner planes */ 00438 boolT PRINTneighbors; /* true 'PG' if printing neighbors of good facets */ 00439 boolT PRINTnoplanes; /* true 'Gn' if printing no planes */ 00440 boolT PRINToptions1st; /* true 'FO' if printing options to stderr */ 00441 boolT PRINTouter; /* true 'Go' if printing outer planes */ 00442 boolT PRINTprecision; /* false 'Pp' if not reporting precision problems */ 00443 qh_PRINT PRINTout[qh_PRINTEND]; /* list of output formats to print */ 00444 boolT PRINTridges; /* true 'Gr' if print ridges */ 00445 boolT PRINTspheres; /* true 'Gv' if print vertices as spheres */ 00446 boolT PRINTstatistics; /* true 'Ts' if printing statistics to stderr */ 00447 boolT PRINTsummary; /* true 's' if printing summary to stderr */ 00448 boolT PRINTtransparent; /* true 'Gt' if print transparent outer ridges */ 00449 boolT PROJECTdelaunay; /* true if DELAUNAY, no readpoints() and 00450 need projectinput() for Delaunay in qh_init_B */ 00451 int PROJECTinput; /* number of projected dimensions 'bn:0Bn:0' */ 00452 boolT QUICKhelp; /* true if quick help message for degen input */ 00453 boolT RANDOMdist; /* true if randomly change distplane and setfacetplane */ 00454 realT RANDOMfactor; /* maximum random perturbation */ 00455 realT RANDOMa; /* qh_randomfactor is randr * RANDOMa + RANDOMb */ 00456 realT RANDOMb; 00457 boolT RANDOMoutside; /* true if select a random outside point */ 00458 int REPORTfreq; /* buildtracing reports every n facets */ 00459 int REPORTfreq2; /* tracemerging reports every REPORTfreq/2 facets */ 00460 int RERUN; /* 'TRn' rerun qhull n times (qh.build_cnt) */ 00461 int ROTATErandom; /* 'QRn' seed, 0 time, >= rotate input */ 00462 boolT SCALEinput; /* true 'Qbk' if scaling input */ 00463 boolT SCALElast; /* true 'Qbb' if scale last coord to max prev coord */ 00464 boolT SETroundoff; /* true 'E' if qh DISTround is predefined */ 00465 boolT SKIPcheckmax; /* true 'Q5' if skip qh_check_maxout */ 00466 boolT SKIPconvex; /* true 'Q6' if skip convexity testing during pre-merge */ 00467 boolT SPLITthresholds; /* true if upper_/lower_threshold defines a region 00468 used only for printing (not for qh ONLYgood) */ 00469 int STOPcone; /* 'TCn' 1+n for stopping after cone for point n*/ 00470 /* also used by qh_build_withresart for err exit*/ 00471 int STOPpoint; /* 'TVn' 'TV-n' 1+n for stopping after/before(-) 00472 adding point n */ 00473 boolT TESTvneighbors; /* true 'Qv' if test vertex neighbors at end */ 00474 int TRACElevel; /* 'Tn' conditional IStracing level */ 00475 int TRACElastrun; /* qh.TRACElevel applies to last qh.RERUN */ 00476 int TRACEpoint; /* 'TPn' start tracing when point n is a vertex */ 00477 realT TRACEdist; /* 'TWn' start tracing when merge distance too big */ 00478 int TRACEmerge; /* 'TMn' start tracing before this merge */ 00479 boolT UPPERdelaunay; /* true 'Qu' if computing furthest-site Delaunay */ 00480 boolT VERIFYoutput; /* true 'Tv' if verify output at end of qhull */ 00481 boolT VIRTUALmemory; /* true 'Q7' if depth-first processing in buildhull */ 00482 boolT VORONOI; /* true 'v' if computing Voronoi diagram */ 00483 00484 /*--------input constants ---------*/ 00485 realT AREAfactor; /* 1/(hull_dim-1)! for converting det's to area */ 00486 boolT DOcheckmax; /* true if calling qh_check_maxout (qh_initqhull_globals) */ 00487 char *feasible_string; /* feasible point 'Hn,n,n' for halfspace intersection */ 00488 coordT *feasible_point; /* as coordinates, both malloc'd */ 00489 boolT GETarea; /* true if need to compute facet areas in io.c */ 00490 boolT KEEPnearinside; /* true if near-inside points in coplanarset */ 00491 int hull_dim; /* dimension of hull, set by initbuffers */ 00492 int input_dim; /* dimension of input, set by initbuffers */ 00493 int num_points; /* number of input points */ 00494 pointT *first_point; /* array of input points, see POINTSmalloc */ 00495 boolT POINTSmalloc; /* true if qh first_point/num_points allocated */ 00496 pointT *input_points; /* copy of original qh.first_point for input points for qh_joggleinput */ 00497 boolT input_malloc; /* true if qh input_points malloc'd */ 00498 char qhull_command[256];/* command line that invoked this program */ 00499 char rbox_command[256]; /* command line that produced the input points */ 00500 char qhull_options[512];/* descriptive list of options */ 00501 int qhull_optionlen; /* length of last line */ 00502 int qhull_optionsiz; /* size of qhull_options before qh_initbuild */ 00503 boolT VERTEXneighbors; /* true if maintaining vertex neighbors */ 00504 boolT ZEROcentrum; /* true if 'C-0' or 'C-0 Qx'. sets ZEROall_ok */ 00505 realT *upper_threshold; /* don't print if facet->normal[k]>=upper_threshold[k] 00506 must set either GOODthreshold or SPLITthreshold 00507 if Delaunay, default is 0.0 for upper envelope */ 00508 realT *lower_threshold; /* don't print if facet->normal[k] <=lower_threshold[k] */ 00509 realT *upper_bound; /* scale point[k] to new upper bound */ 00510 realT *lower_bound; /* scale point[k] to new lower bound 00511 project if both upper_ and lower_bound == 0 */ 00512 00513 /*-<a href="qh-globa.htm#TOC" 00514 >--------------------------------</a><a name="qh-prec">-</a> 00515 00516 qh precision constants 00517 precision constants for Qhull 00518 00519 notes: 00520 qh_detroundoff() computes the maximum roundoff error for distance 00521 and other computations. It also sets default values for the 00522 qh constants above. 00523 */ 00524 realT ANGLEround; /* max round off error for angles */ 00525 realT centrum_radius; /* max centrum radius for convexity (roundoff added) */ 00526 realT cos_max; /* max cosine for convexity (roundoff added) */ 00527 realT DISTround; /* max round off error for distances, 'E' overrides */ 00528 realT MAXabs_coord; /* max absolute coordinate */ 00529 realT MAXlastcoord; /* max last coordinate for qh_scalelast */ 00530 realT MAXsumcoord; /* max sum of coordinates */ 00531 realT MAXwidth; /* max rectilinear width of point coordinates */ 00532 realT MINdenom_1; /* min. abs. value for 1/x */ 00533 realT MINdenom; /* use divzero if denominator < MINdenom */ 00534 realT MINdenom_1_2; /* min. abs. val for 1/x that allows normalization */ 00535 realT MINdenom_2; /* use divzero if denominator < MINdenom_2 */ 00536 realT MINlastcoord; /* min. last coordinate for qh_scalelast */ 00537 boolT NARROWhull; /* set in qh_initialhull if angle < qh_MAXnarrow */ 00538 realT *NEARzero; /* hull_dim array for near zero in gausselim */ 00539 realT NEARinside; /* keep points for qh_check_maxout if close to facet */ 00540 realT ONEmerge; /* max distance for merging simplicial facets */ 00541 realT outside_err; /* application's epsilon for coplanar points 00542 qh_check_bestdist() qh_check_points() reports error if point outside */ 00543 realT WIDEfacet; /* size of wide facet for skipping ridge in 00544 area computation and locking centrum */ 00545 00546 /*-<a href="qh-globa.htm#TOC" 00547 >--------------------------------</a><a name="qh-intern">-</a> 00548 00549 qh internal constants 00550 internal constants for Qhull 00551 */ 00552 char qhull[sizeof("qhull")]; /* for checking ownership */ 00553 void *old_stat; /* pointer to saved qh_qhstat, qh_save_qhull */ 00554 jmp_buf errexit; /* exit label for qh_errexit, defined by setjmp() */ 00555 char jmpXtra[40]; /* extra bytes in case jmp_buf is defined wrong by compiler */ 00556 jmp_buf restartexit; /* restart label for qh_errexit, defined by setjmp() */ 00557 char jmpXtra2[40]; /* extra bytes in case jmp_buf is defined wrong by compiler*/ 00558 FILE *fin; /* pointer to input file, init by qh_meminit */ 00559 FILE *fout; /* pointer to output file */ 00560 FILE *ferr; /* pointer to error file */ 00561 pointT *interior_point; /* center point of the initial simplex*/ 00562 int normal_size; /* size in bytes for facet normals and point coords*/ 00563 int center_size; /* size in bytes for Voronoi centers */ 00564 int TEMPsize; /* size for small, temporary sets (in quick mem) */ 00565 00566 /*-<a href="qh-globa.htm#TOC" 00567 >--------------------------------</a><a name="qh-lists">-</a> 00568 00569 qh facet and vertex lists 00570 defines lists of facets, new facets, visible facets, vertices, and 00571 new vertices. Includes counts, next ids, and trace ids. 00572 see: 00573 qh_resetlists() 00574 */ 00575 facetT *facet_list; /* first facet */ 00576 facetT *facet_tail; /* end of facet_list (dummy facet) */ 00577 facetT *facet_next; /* next facet for buildhull() 00578 previous facets do not have outside sets 00579 NARROWhull: previous facets may have coplanar outside sets for qh_outcoplanar */ 00580 facetT *newfacet_list; /* list of new facets to end of facet_list */ 00581 facetT *visible_list; /* list of visible facets preceeding newfacet_list, 00582 facet->visible set */ 00583 int num_visible; /* current number of visible facets */ 00584 unsigned tracefacet_id; /* set at init, then can print whenever */ 00585 facetT *tracefacet; /* set in newfacet/mergefacet, undone in delfacet*/ 00586 unsigned tracevertex_id; /* set at buildtracing, can print whenever */ 00587 vertexT *tracevertex; /* set in newvertex, undone in delvertex*/ 00588 vertexT *vertex_list; /* list of all vertices, to vertex_tail */ 00589 vertexT *vertex_tail; 00590 vertexT *newvertex_list; /* list of vertices in newfacet_list, to vertex_tail 00591 all vertices have 'newlist' set */ 00592 int num_facets; /* number of facets in facet_list 00593 includes visble faces (num_visible) */ 00594 int num_vertices; /* number of vertices in facet_list */ 00595 int num_outside; /* number of points in outsidesets (for tracing and RANDOMoutside) 00596 includes coplanar outsideset points for NARROWhull/qh_outcoplanar() */ 00597 int num_good; /* number of good facets (after findgood_all) */ 00598 unsigned facet_id; /* ID of next, new facet from newfacet() */ 00599 unsigned ridge_id; /* ID of next, new ridge from newridge() */ 00600 unsigned vertex_id; /* ID of next, new vertex from newvertex() */ 00601 00602 /*-<a href="qh-globa.htm#TOC" 00603 >--------------------------------</a><a name="qh-var">-</a> 00604 00605 qh global variables 00606 defines minimum and maximum distances, next visit ids, several flags, 00607 and other global variables. 00608 initialize in qh_initbuild or qh_maxmin if used in qh_buildhull 00609 */ 00610 unsigned long hulltime; /* ignore time to set up input and randomize */ 00611 /* use unsigned to avoid wrap-around errors */ 00612 boolT ALLOWrestart; /* true if qh_precision can use qh.restartexit */ 00613 int build_cnt; /* number of calls to qh_initbuild */ 00614 qh_CENTER CENTERtype; /* current type of facet->center, qh_CENTER */ 00615 int furthest_id; /* pointid of furthest point, for tracing */ 00616 facetT *GOODclosest; /* closest facet to GOODthreshold in qh_findgood */ 00617 realT JOGGLEmax; /* set 'QJn' if randomly joggle input */ 00618 boolT maxoutdone; /* set qh_check_maxout(), cleared by qh_addpoint() */ 00619 realT max_outside; /* maximum distance from a point to a facet, 00620 before roundoff, not simplicial vertices 00621 actual outer plane is +DISTround and 00622 computed outer plane is +2*DISTround */ 00623 realT max_vertex; /* maximum distance (>0) from vertex to a facet, 00624 before roundoff, due to a merge */ 00625 realT min_vertex; /* minimum distance (<0) from vertex to a facet, 00626 before roundoff, due to a merge 00627 if qh.JOGGLEmax, qh_makenewplanes sets it 00628 recomputed if qh.DOcheckmax, default -qh.DISTround */ 00629 boolT NEWfacets; /* true while visible facets invalid due to new or merge 00630 from makecone/attachnewfacets to deletevisible */ 00631 boolT findbestnew; /* true if partitioning calls qh_findbestnew */ 00632 boolT findbest_notsharp; /* true if new facets are at least 90 degrees */ 00633 boolT NOerrexit; /* true if qh.errexit is not available */ 00634 realT PRINTcradius; /* radius for printing centrums */ 00635 realT PRINTradius; /* radius for printing vertex spheres and points */ 00636 boolT POSTmerging; /* true when post merging */ 00637 int printoutvar; /* temporary variable for qh_printbegin, etc. */ 00638 int printoutnum; /* number of facets printed */ 00639 boolT QHULLfinished; /* True after qhull() is finished */ 00640 realT totarea; /* total facet area computed by qh_getarea */ 00641 realT totvol; /* total volume computed by qh_getarea */ 00642 unsigned int visit_id; /* unique ID for searching neighborhoods, */ 00643 unsigned int vertex_visit; /* unique ID for searching vertices */ 00644 boolT ZEROall_ok; /* True if qh_checkzero always succeeds */ 00645 boolT WAScoplanar; /* True if qh_partitioncoplanar (qh_check_maxout) */ 00646 00647 /*-<a href="qh-globa.htm#TOC" 00648 >--------------------------------</a><a name="qh-set">-</a> 00649 00650 qh global sets 00651 defines sets for merging, initial simplex, hashing, extra input points, 00652 and deleted vertices 00653 */ 00654 setT *facet_mergeset; /* temporary set of merges to be done */ 00655 setT *degen_mergeset; /* temporary set of degenerate and redundant merges */ 00656 setT *hash_table; /* hash table for matching ridges in qh_matchfacets 00657 size is setsize() */ 00658 setT *other_points; /* additional points (first is qh interior_point) */ 00659 setT *del_vertices; /* vertices to partition and delete with visible 00660 facets. Have deleted set for checkfacet */ 00661 00662 /*-<a href="qh-globa.htm#TOC" 00663 >--------------------------------</a><a name="qh-buf">-</a> 00664 00665 qh global buffers 00666 defines buffers for maxtrix operations, input, and error messages 00667 */ 00668 coordT *gm_matrix; /* (dim+1)Xdim matrix for geom.c */ 00669 coordT **gm_row; /* array of gm_matrix rows */ 00670 char* line; /* malloc'd input line of maxline+1 chars */ 00671 int maxline; 00672 coordT *half_space; /* malloc'd input array for halfspace (qh normal_size+coordT) */ 00673 coordT *temp_malloc; /* malloc'd input array for points */ 00674 00675 /*-<a href="qh-globa.htm#TOC" 00676 >--------------------------------</a><a name="qh-static">-</a> 00677 00678 qh static variables 00679 defines static variables for individual functions 00680 00681 notes: 00682 do not use 'static' within a function. Multiple instances of qhull 00683 may exist. 00684 00685 do not assume zero initialization, 'QPn' may cause a restart 00686 */ 00687 boolT ERREXITcalled; /* true during errexit (prevents duplicate calls */ 00688 boolT firstcentrum; /* for qh_printcentrum */ 00689 realT last_low; /* qh_scalelast parameters for qh_setdelaunay */ 00690 realT last_high; 00691 realT last_newhigh; 00692 unsigned lastreport; /* for qh_buildtracing */ 00693 int mergereport; /* for qh_tracemerging */ 00694 boolT old_randomdist; /* save RANDOMdist when io, tracing, or statistics */ 00695 int ridgeoutnum; /* number of ridges in 4OFF output */ 00696 void *old_qhstat; /* for saving qh_qhstat in save_qhull() */ 00697 setT *old_tempstack; /* for saving qhmem.tempstack in save_qhull */ 00698 setT *searchset; /* set of facets for searching in qh_findbest() */ 00699 }; 00700 00701 /*=========== -macros- =========================*/ 00702 00703 /*-<a href="qh-poly.htm#TOC" 00704 >--------------------------------</a><a name="otherfacet_">-</a> 00705 00706 otherfacet_(ridge, facet) 00707 return neighboring facet for a ridge in facet 00708 */ 00709 #define otherfacet_(ridge, facet) \ 00710 (((ridge)->top == (facet)) ? (ridge)->bottom : (ridge)->top) 00711 00712 /*-<a href="qh-poly.htm#TOC" 00713 >--------------------------------</a><a name="getid_">-</a> 00714 00715 getid_(p) 00716 return ID for facet, ridge, or vertex 00717 return MAXINT if NULL (-1 causes type conversion error ) 00718 */ 00719 #define getid_(p) ((p) ? (p)->id : -1) 00720 00721 /*============== FORALL macros ===================*/ 00722 00723 /*-<a href="qh-poly.htm#TOC" 00724 >--------------------------------</a><a name="FORALLfacets">-</a> 00725 00726 FORALLfacets { ... } 00727 assign 'facet' to each facet in qh.facet_list 00728 00729 notes: 00730 uses 'facetT *facet;' 00731 assumes last facet is a sentinel 00732 00733 see: 00734 FORALLfacet_( facetlist ) 00735 */ 00736 #define FORALLfacets for (facet=qh facet_list;facet && facet->next;facet=facet->next) 00737 00738 /*-<a href="qh-poly.htm#TOC" 00739 >--------------------------------</a><a name="FORALLpoints">-</a> 00740 00741 FORALLpoints { ... } 00742 assign 'point' to each point in qh.first_point, qh.num_points 00743 00744 declare: 00745 coordT *point, *pointtemp; 00746 */ 00747 #define FORALLpoints FORALLpoint_(qh first_point, qh num_points) 00748 00749 /*-<a href="qh-poly.htm#TOC" 00750 >--------------------------------</a><a name="FORALLpoint_">-</a> 00751 00752 FORALLpoint_( points, num) { ... } 00753 assign 'point' to each point in points array of num points 00754 00755 declare: 00756 coordT *point, *pointtemp; 00757 */ 00758 #define FORALLpoint_(points, num) for(point= (points), \ 00759 pointtemp= (points)+qh hull_dim*(num); point < pointtemp; point += qh hull_dim) 00760 00761 /*-<a href="qh-poly.htm#TOC" 00762 >--------------------------------</a><a name="FORALLvertices">-</a> 00763 00764 FORALLvertices { ... } 00765 assign 'vertex' to each vertex in qh.vertex_list 00766 00767 declare: 00768 vertexT *vertex; 00769 00770 notes: 00771 assumes qh.vertex_list terminated with a sentinel 00772 */ 00773 #define FORALLvertices for (vertex=qh vertex_list;vertex && vertex->next;vertex= vertex->next) 00774 00775 /*-<a href="qh-poly.htm#TOC" 00776 >--------------------------------</a><a name="FOREACHfacet_">-</a> 00777 00778 FOREACHfacet_( facets ) { ... } 00779 assign 'facet' to each facet in facets 00780 00781 declare: 00782 facetT *facet, **facetp; 00783 00784 see: 00785 <a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a> 00786 */ 00787 #define FOREACHfacet_(facets) FOREACHsetelement_(facetT, facets, facet) 00788 00789 /*-<a href="qh-poly.htm#TOC" 00790 >--------------------------------</a><a name="FOREACHneighbor_">-</a> 00791 00792 FOREACHneighbor_( facet ) { ... } 00793 assign 'neighbor' to each neighbor in facet->neighbors 00794 00795 FOREACHneighbor_( vertex ) { ... } 00796 assign 'neighbor' to each neighbor in vertex->neighbors 00797 00798 declare: 00799 facetT *neighbor, **neighborp; 00800 00801 see: 00802 <a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a> 00803 */ 00804 #define FOREACHneighbor_(facet) FOREACHsetelement_(facetT, facet->neighbors, neighbor) 00805 00806 /*-<a href="qh-poly.htm#TOC" 00807 >--------------------------------</a><a name="FOREACHpoint_">-</a> 00808 00809 FOREACHpoint_( points ) { ... } 00810 assign 'point' to each point in points set 00811 00812 declare: 00813 pointT *point, **pointp; 00814 00815 see: 00816 <a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a> 00817 */ 00818 #define FOREACHpoint_(points) FOREACHsetelement_(pointT, points, point) 00819 00820 /*-<a href="qh-poly.htm#TOC" 00821 >--------------------------------</a><a name="FOREACHridge_">-</a> 00822 00823 FOREACHridge_( ridges ) { ... } 00824 assign 'ridge' to each ridge in ridges set 00825 00826 declare: 00827 ridgeT *ridge, **ridgep; 00828 00829 see: 00830 <a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a> 00831 */ 00832 #define FOREACHridge_(ridges) FOREACHsetelement_(ridgeT, ridges, ridge) 00833 00834 /*-<a href="qh-poly.htm#TOC" 00835 >--------------------------------</a><a name="FOREACHvertex_">-</a> 00836 00837 FOREACHvertex_( vertices ) { ... } 00838 assign 'vertex' to each vertex in vertices set 00839 00840 declare: 00841 vertexT *vertex, **vertexp; 00842 00843 see: 00844 <a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a> 00845 */ 00846 #define FOREACHvertex_(vertices) FOREACHsetelement_(vertexT, vertices,vertex) 00847 00848 /*-<a href="qh-poly.htm#TOC" 00849 >--------------------------------</a><a name="FOREACHfacet_i_">-</a> 00850 00851 FOREACHfacet_i_( facets ) { ... } 00852 assign 'facet' and 'facet_i' for each facet in facets set 00853 00854 declare: 00855 facetT *facet; 00856 int facet_n, facet_i; 00857 00858 see: 00859 <a href="qset.h#FOREACHsetelement_i_">FOREACHsetelement_i_</a> 00860 */ 00861 #define FOREACHfacet_i_(facets) FOREACHsetelement_i_(facetT, facets, facet) 00862 00863 /*-<a href="qh-poly.htm#TOC" 00864 >--------------------------------</a><a name="FOREACHneighbor_i_">-</a> 00865 00866 FOREACHneighbor_i_( facet ) { ... } 00867 assign 'neighbor' and 'neighbor_i' for each neighbor in facet->neighbors 00868 00869 FOREACHneighbor_i_( vertex ) { ... } 00870 assign 'neighbor' and 'neighbor_i' for each neighbor in vertex->neighbors 00871 00872 declare: 00873 facetT *neighbor; 00874 int neighbor_n, neighbor_i; 00875 00876 see: 00877 <a href="qset.h#FOREACHsetelement_i_">FOREACHsetelement_i_</a> 00878 */ 00879 #define FOREACHneighbor_i_(facet) FOREACHsetelement_i_(facetT, facet->neighbors, neighbor) 00880 00881 /*-<a href="qh-poly.htm#TOC" 00882 >--------------------------------</a><a name="FOREACHpoint_i_">-</a> 00883 00884 FOREACHpoint_i_( points ) { ... } 00885 assign 'point' and 'point_i' for each point in points set 00886 00887 declare: 00888 pointT *point; 00889 int point_n, point_i; 00890 00891 see: 00892 <a href="qset.h#FOREACHsetelement_i_">FOREACHsetelement_i_</a> 00893 */ 00894 #define FOREACHpoint_i_(points) FOREACHsetelement_i_(pointT, points, point) 00895 00896 /*-<a href="qh-poly.htm#TOC" 00897 >--------------------------------</a><a name="FOREACHridge_i_">-</a> 00898 00899 FOREACHridge_i_( ridges ) { ... } 00900 assign 'ridge' and 'ridge_i' for each ridge in ridges set 00901 00902 declare: 00903 ridgeT *ridge; 00904 int ridge_n, ridge_i; 00905 00906 see: 00907 <a href="qset.h#FOREACHsetelement_i_">FOREACHsetelement_i_</a> 00908 */ 00909 #define FOREACHridge_i_(ridges) FOREACHsetelement_i_(ridgeT, ridges, ridge) 00910 00911 /*-<a href="qh-poly.htm#TOC" 00912 >--------------------------------</a><a name="FOREACHvertex_i_">-</a> 00913 00914 FOREACHvertex_i_( vertices ) { ... } 00915 assign 'vertex' and 'vertex_i' for each vertex in vertices set 00916 00917 declare: 00918 vertexT *vertex; 00919 int vertex_n, vertex_i; 00920 00921 see: 00922 <a href="qset.h#FOREACHsetelement_i_">FOREACHsetelement_i_</a> 00923 */ 00924 #define FOREACHvertex_i_(vertices) FOREACHsetelement_i_(vertexT, vertices,vertex) 00925 00926 /********* -qhull.c prototypes (duplicated from qhull_a.h) **********************/ 00927 00928 void qh_qhull (void); 00929 boolT qh_addpoint (pointT *furthest, facetT *facet, boolT checkdist); 00930 void qh_printsummary(FILE *fp); 00931 00932 /********* -user.c prototypes (alphabetical) **********************/ 00933 00934 void qh_errexit(int exitcode, facetT *facet, ridgeT *ridge); 00935 void qh_errprint(char* string, facetT *atfacet, facetT *otherfacet, ridgeT *atridge, vertexT *atvertex); 00936 int qh_new_qhull (int dim, int numpoints, coordT *points, boolT ismalloc, 00937 char *qhull_cmd, FILE *outfile, FILE *errfile); 00938 void qh_printfacetlist(facetT *facetlist, setT *facets, boolT printall); 00939 void qh_user_memsizes (void); 00940 00941 /***** -geom.c/geom2.c prototypes (duplicated from geom.h) ****************/ 00942 00943 facetT *qh_findbest (pointT *point, facetT *startfacet, 00944 boolT bestoutside, boolT newfacets, boolT noupper, 00945 realT *dist, boolT *isoutside, int *numpart); 00946 facetT *qh_findbestnew (pointT *point, facetT *startfacet, 00947 realT *dist, boolT *isoutside, int *numpart); 00948 boolT qh_gram_schmidt(int dim, realT **rows); 00949 void qh_outerinner (facetT *facet, realT *outerplane, realT *innerplane); 00950 void qh_printsummary(FILE *fp); 00951 void qh_projectinput (void); 00952 void qh_randommatrix (realT *buffer, int dim, realT **row); 00953 void qh_rotateinput (realT **rows); 00954 void qh_scaleinput (void); 00955 void qh_setdelaunay (int dim, int count, pointT *points); 00956 coordT *qh_sethalfspace_all (int dim, int count, coordT *halfspaces, pointT *feasible); 00957 00958 /***** -global.c prototypes (alphabetical) ***********************/ 00959 00960 unsigned long qh_clock (void); 00961 void qh_checkflags (char *command, char *hiddenflags); 00962 void qh_freebuffers (void); 00963 void qh_freeqhull (boolT allmem); 00964 void qh_init_A (FILE *infile, FILE *outfile, FILE *errfile, int argc, char *argv[]); 00965 void qh_init_B (coordT *points, int numpoints, int dim, boolT ismalloc); 00966 void qh_init_qhull_command (int argc, char *argv[]); 00967 void qh_initbuffers (coordT *points, int numpoints, int dim, boolT ismalloc); 00968 void qh_initflags (char *command); 00969 void qh_initqhull_buffers (void); 00970 void qh_initqhull_globals (coordT *points, int numpoints, int dim, boolT ismalloc); 00971 void qh_initqhull_mem (void); 00972 void qh_initqhull_start (FILE *infile, FILE *outfile, FILE *errfile); 00973 void qh_initthresholds (char *command); 00974 #if qh_QHpointer 00975 void qh_restore_qhull (qhT **oldqh); 00976 qhT *qh_save_qhull (void); 00977 #endif 00978 00979 /***** -io.c prototypes (duplicated from io.h) ***********************/ 00980 00981 void dfacet( unsigned id); 00982 void dvertex( unsigned id); 00983 void qh_printneighborhood (FILE *fp, int format, facetT *facetA, facetT *facetB, boolT printall); 00984 void qh_produce_output(void); 00985 coordT *qh_readpoints(int *numpoints, int *dimension, boolT *ismalloc); 00986 00987 00988 /********* -mem.c prototypes (duplicated from mem.h) **********************/ 00989 00990 void qh_meminit (FILE *ferr); 00991 void qh_memfreeshort (int *curlong, int *totlong); 00992 00993 /********* -poly.c/poly2.c prototypes (duplicated from poly.h) **********************/ 00994 00995 void qh_check_output (void); 00996 void qh_check_points (void); 00997 setT *qh_facetvertices (facetT *facetlist, setT *facets, boolT allfacets); 00998 facetT *qh_findbestfacet (pointT *point, boolT bestoutside, 00999 realT *bestdist, boolT *isoutside); 01000 vertexT *qh_nearvertex (facetT *facet, pointT *point, realT *bestdistp); 01001 pointT *qh_point (int id); 01002 setT *qh_pointfacet (void /*qh.facet_list*/); 01003 int qh_pointid (pointT *point); 01004 setT *qh_pointvertex (void /*qh.facet_list*/); 01005 void qh_setvoronoi_all (void); 01006 01007 /********* -stat.c prototypes (duplicated from stat.h) **********************/ 01008 01009 void qh_collectstatistics (void); 01010 void qh_printallstatistics (FILE *fp, char *string); 01011 01012 #endif /* qhDEFqhull */