| 1 |
/*<html><pre> -<a href="qh-qhull.htm" |
| 2 |
>-------------------------------</a><a name="TOP">-</a> |
| 3 |
|
| 4 |
qhull.h |
| 5 |
user-level header file for using qhull.a library |
| 6 |
|
| 7 |
see qh-qhull.htm, qhull_a.h |
| 8 |
|
| 9 |
copyright (c) 1993-2003, The Geometry Center |
| 10 |
|
| 11 |
NOTE: access to qh_qh is via the 'qh' macro. This allows |
| 12 |
qh_qh to be either a pointer or a structure. An example |
| 13 |
of using qh is "qh DROPdim" which accesses the DROPdim |
| 14 |
field of qh_qh. Similarly, access to qh_qhstat is via |
| 15 |
the 'qhstat' macro. |
| 16 |
|
| 17 |
includes function prototypes for qhull.c, geom.c, global.c, io.c, user.c |
| 18 |
|
| 19 |
for mem.c, use mem.h |
| 20 |
for qset.c, use qset.h |
| 21 |
|
| 22 |
see unix.c for an example of using qhull.h |
| 23 |
|
| 24 |
recompile qhull if you change this file |
| 25 |
*/ |
| 26 |
|
| 27 |
#ifndef qhDEFqhull |
| 28 |
#define qhDEFqhull 1 |
| 29 |
|
| 30 |
/*=========================== -included files ==============*/ |
| 31 |
|
| 32 |
#include <setjmp.h> |
| 33 |
#include <float.h> |
| 34 |
#include <time.h> |
| 35 |
|
| 36 |
#ifdef __MWERKS__ |
| 37 |
#ifdef __POWERPC__ |
| 38 |
#include <SIOUX.h> |
| 39 |
#include <Files.h> |
| 40 |
#include <Desk.h> |
| 41 |
#endif |
| 42 |
#endif |
| 43 |
|
| 44 |
#ifndef __STDC__ |
| 45 |
#ifndef __cplusplus |
| 46 |
#if !_MSC_VER |
| 47 |
#error Neither __STDC__ nor __cplusplus is defined. Please use strict ANSI C or C++ to compile |
| 48 |
#error Qhull. You may need to turn off compiler extensions in your project configuration. If |
| 49 |
#error your compiler is a standard C compiler, you can delete this warning from qhull.h |
| 50 |
#endif |
| 51 |
#endif |
| 52 |
#endif |
| 53 |
|
| 54 |
/* user defineable constants */ |
| 55 |
#include "QuickHull/user.h" |
| 56 |
|
| 57 |
|
| 58 |
/*============ constants and basic types ====================*/ |
| 59 |
/* defined in global.c */ |
| 60 |
extern char *qh_version; |
| 61 |
|
| 62 |
/*-<a href="qh-geom.htm#TOC" |
| 63 |
>--------------------------------</a><a name="coordT">-</a> |
| 64 |
|
| 65 |
coordT |
| 66 |
coordinates and coefficients are stored as realT (i.e., double) |
| 67 |
|
| 68 |
notes: |
| 69 |
could use 'float' for data and 'double' for calculations (realT vs. coordT) |
| 70 |
This requires many type casts, and adjusted error bounds. |
| 71 |
Also C compilers may do expressions in double anyway. |
| 72 |
*/ |
| 73 |
#define coordT realT |
| 74 |
|
| 75 |
/*-<a href="qh-geom.htm#TOC" |
| 76 |
>--------------------------------</a><a name="pointT">-</a> |
| 77 |
|
| 78 |
pointT |
| 79 |
a point is an array of DIM3 coordinates |
| 80 |
*/ |
| 81 |
#define pointT coordT |
| 82 |
|
| 83 |
/*-<a href="qh-qhull.htm#TOC" |
| 84 |
>--------------------------------</a><a name="flagT">-</a> |
| 85 |
|
| 86 |
flagT |
| 87 |
Boolean flag as a bit |
| 88 |
*/ |
| 89 |
#define flagT unsigned int |
| 90 |
|
| 91 |
/*-<a href="qh-qhull.htm#TOC" |
| 92 |
>--------------------------------</a><a name="boolT">-</a> |
| 93 |
|
| 94 |
boolT |
| 95 |
boolean value, either True or False |
| 96 |
|
| 97 |
notes: |
| 98 |
needed for portability |
| 99 |
*/ |
| 100 |
#define boolT unsigned int |
| 101 |
#ifdef False |
| 102 |
#undef False |
| 103 |
#endif |
| 104 |
#ifdef True |
| 105 |
#undef True |
| 106 |
#endif |
| 107 |
#define False 0 |
| 108 |
#define True 1 |
| 109 |
|
| 110 |
/*-<a href="qh-qhull.htm#TOC" |
| 111 |
>--------------------------------</a><a name="CENTERtype">-</a> |
| 112 |
|
| 113 |
qh_CENTER |
| 114 |
to distinguish facet->center |
| 115 |
*/ |
| 116 |
typedef enum |
| 117 |
{ |
| 118 |
qh_ASnone = 0, qh_ASvoronoi, qh_AScentrum |
| 119 |
} |
| 120 |
qh_CENTER; |
| 121 |
|
| 122 |
/*-<a href="qh-qhull.htm#TOC" |
| 123 |
>--------------------------------</a><a name="qh_PRINT">-</a> |
| 124 |
|
| 125 |
qh_PRINT |
| 126 |
output formats for printing (qh.PRINTout). |
| 127 |
'Fa' 'FV' 'Fc' 'FC' |
| 128 |
|
| 129 |
|
| 130 |
notes: |
| 131 |
some of these names are similar to qh names. The similar names are only |
| 132 |
used in switch statements in qh_printbegin() etc. |
| 133 |
*/ |
| 134 |
typedef enum {qh_PRINTnone= 0, |
| 135 |
qh_PRINTarea, qh_PRINTaverage, /* 'Fa' 'FV' 'Fc' 'FC' */ |
| 136 |
qh_PRINTcoplanars, qh_PRINTcentrums, |
| 137 |
qh_PRINTfacets, qh_PRINTfacets_xridge, /* 'f' 'FF' 'G' 'FI' 'Fi' 'Fn' */ |
| 138 |
qh_PRINTgeom, qh_PRINTids, qh_PRINTinner, qh_PRINTneighbors, |
| 139 |
qh_PRINTnormals, qh_PRINTouter, qh_PRINTmaple, /* 'n' 'Fo' 'i' 'm' 'Fm' 'FM', 'o' */ |
| 140 |
qh_PRINTincidences, qh_PRINTmathematica, qh_PRINTmerges, qh_PRINToff, |
| 141 |
qh_PRINToptions, qh_PRINTpointintersect, /* 'FO' 'Fp' 'FP' 'p' 'FQ' 'FS' */ |
| 142 |
qh_PRINTpointnearest, qh_PRINTpoints, qh_PRINTqhull, qh_PRINTsize, |
| 143 |
qh_PRINTsummary, qh_PRINTtriangles, /* 'Fs' 'Ft' 'Fv' 'FN' 'Fx' */ |
| 144 |
qh_PRINTvertices, qh_PRINTvneighbors, qh_PRINTextremes, |
| 145 |
qh_PRINTEND} qh_PRINT; |
| 146 |
|
| 147 |
/*-<a href="qh-qhull.htm#TOC" |
| 148 |
>--------------------------------</a><a name="qh_ALL">-</a> |
| 149 |
|
| 150 |
qh_ALL |
| 151 |
argument flag for selecting everything |
| 152 |
*/ |
| 153 |
#define qh_ALL True |
| 154 |
/* argument for qh_findbest */ |
| 155 |
#define qh_NOupper True |
| 156 |
/* argument for qh_findbesthorizon */ |
| 157 |
#define qh_IScheckmax True |
| 158 |
/* argument for qh_findbest */ |
| 159 |
#define qh_ISnewfacets True |
| 160 |
/* argument for qh_resetlists */ |
| 161 |
#define qh_RESETvisible True |
| 162 |
|
| 163 |
/*-<a href="qh-qhull.htm#TOC" |
| 164 |
>--------------------------------</a><a name="qh_ERR">-</a> |
| 165 |
|
| 166 |
qh_ERR |
| 167 |
Qhull exit codes, for indicating errors |
| 168 |
*/ |
| 169 |
/* no error occurred during qhull */ |
| 170 |
#define qh_ERRnone 0 |
| 171 |
/* input inconsistency */ |
| 172 |
#define qh_ERRinput 1 |
| 173 |
/* singular input data */ |
| 174 |
#define qh_ERRsingular 2 |
| 175 |
/* precision error */ |
| 176 |
#define qh_ERRprec 3 |
| 177 |
/* insufficient memory, matches mem.h */ |
| 178 |
#define qh_ERRmem 4 |
| 179 |
/* internal error detected, matches mem.h */ |
| 180 |
#define qh_ERRqhull 5 |
| 181 |
|
| 182 |
/* ============ -structures- ==================== |
| 183 |
each of the following structures is defined by a typedef |
| 184 |
all realT and coordT fields occur at the beginning of a structure |
| 185 |
(otherwise space may be wasted due to alignment) |
| 186 |
define all flags together and pack into 32-bit number |
| 187 |
*/ |
| 188 |
|
| 189 |
typedef struct vertexT vertexT; |
| 190 |
typedef struct ridgeT ridgeT; |
| 191 |
typedef struct facetT facetT; |
| 192 |
#ifndef DEFsetT |
| 193 |
#define DEFsetT 1 |
| 194 |
typedef struct setT setT; /* defined in qset.h */ |
| 195 |
#endif |
| 196 |
|
| 197 |
/*-<a href="qh-poly.htm#TOC" |
| 198 |
>--------------------------------</a><a name="facetT">-</a> |
| 199 |
|
| 200 |
facetT |
| 201 |
defines a facet |
| 202 |
|
| 203 |
notes: |
| 204 |
qhull() generates the hull as a list of facets. |
| 205 |
|
| 206 |
topological information: |
| 207 |
f.previous,next doubly-linked list of facets |
| 208 |
f.vertices set of vertices |
| 209 |
f.ridges set of ridges |
| 210 |
f.neighbors set of neighbors |
| 211 |
f.toporient True if facet has top-orientation (else bottom) |
| 212 |
|
| 213 |
geometric information: |
| 214 |
f.offset,normal hyperplane equation |
| 215 |
f.maxoutside offset to outer plane -- all points inside |
| 216 |
f.center centrum for testing convexity |
| 217 |
f.simplicial True if facet is simplicial |
| 218 |
f.flipped True if facet does not include qh.interior_point |
| 219 |
|
| 220 |
for constructing hull: |
| 221 |
f.visible True if facet on list of visible facets (will be deleted) |
| 222 |
f.newfacet True if facet on list of newly created facets |
| 223 |
f.coplanarset set of points coplanar with this facet |
| 224 |
(includes near-inside points for later testing) |
| 225 |
f.outsideset set of points outside of this facet |
| 226 |
f.furthestdist distance to furthest point of outside set |
| 227 |
f.visitid marks visited facets during a loop |
| 228 |
f.replace replacement facet for to-be-deleted, visible facets |
| 229 |
f.samecycle,newcycle cycle of facets for merging into horizon facet |
| 230 |
|
| 231 |
see below for other flags and fields |
| 232 |
*/ |
| 233 |
struct facetT { |
| 234 |
#if !qh_COMPUTEfurthest |
| 235 |
coordT furthestdist;/* distance to furthest point of outsideset */ |
| 236 |
#endif |
| 237 |
#if qh_MAXoutside |
| 238 |
coordT maxoutside; /* max computed distance of point to facet |
| 239 |
Before QHULLfinished this is an approximation |
| 240 |
since maxdist not always set for mergefacet |
| 241 |
Actual outer plane is +DISTround and |
| 242 |
computed outer plane is +2*DISTround */ |
| 243 |
#endif |
| 244 |
coordT offset; /* exact offset of hyperplane from origin */ |
| 245 |
coordT *normal; /* normal of hyperplane, hull_dim coefficients */ |
| 246 |
/* if tricoplanar, shared with a neighbor */ |
| 247 |
union { /* in order of testing */ |
| 248 |
realT area; /* area of facet, only in io.c if ->isarea */ |
| 249 |
facetT *replace; /* replacement facet if ->visible and NEWfacets |
| 250 |
is NULL only if qh_mergedegen_redundant or interior */ |
| 251 |
facetT *samecycle; /* cycle of facets from the same visible/horizon intersection, |
| 252 |
if ->newfacet */ |
| 253 |
facetT *newcycle; /* in horizon facet, current samecycle of new facets */ |
| 254 |
facetT *trivisible; /* visible facet for ->tricoplanar facets during qh_triangulate() */ |
| 255 |
facetT *triowner; /* owner facet for ->tricoplanar, !isarea facets w/ ->keepcentrum */ |
| 256 |
}f; |
| 257 |
coordT *center; /* centrum for convexity, qh CENTERtype == qh_AScentrum */ |
| 258 |
/* Voronoi center, qh CENTERtype == qh_ASvoronoi */ |
| 259 |
/* if tricoplanar, shared with a neighbor */ |
| 260 |
facetT *previous; /* previous facet in the facet_list */ |
| 261 |
facetT *next; /* next facet in the facet_list */ |
| 262 |
setT *vertices; /* vertices for this facet, inverse sorted by ID |
| 263 |
if simplicial, 1st vertex was apex/furthest */ |
| 264 |
setT *ridges; /* explicit ridges for nonsimplicial facets. |
| 265 |
for simplicial facets, neighbors defines ridge */ |
| 266 |
setT *neighbors; /* neighbors of the facet. If simplicial, the kth |
| 267 |
neighbor is opposite the kth vertex, and the first |
| 268 |
neighbor is the horizon facet for the first vertex*/ |
| 269 |
setT *outsideset; /* set of points outside this facet |
| 270 |
if non-empty, last point is furthest |
| 271 |
if NARROWhull, includes coplanars for partitioning*/ |
| 272 |
setT *coplanarset; /* set of points coplanar with this facet |
| 273 |
> qh.min_vertex and <= facet->max_outside |
| 274 |
a point is assigned to the furthest facet |
| 275 |
if non-empty, last point is furthest away */ |
| 276 |
unsigned visitid; /* visit_id, for visiting all neighbors, |
| 277 |
all uses are independent */ |
| 278 |
unsigned id; /* unique identifier from qh facet_id */ |
| 279 |
unsigned nummerge:9; /* number of merges */ |
| 280 |
#define qh_MAXnummerge 511 |
| 281 |
/* 2^9-1, 32 flags total, see "flags:" in io.c */ |
| 282 |
flagT tricoplanar:1; /* True if TRIangulate and simplicial and coplanar with a neighbor */ |
| 283 |
/* all tricoplanars share the same ->center, ->normal, ->offset, ->maxoutside */ |
| 284 |
/* all tricoplanars share the same apex */ |
| 285 |
/* if ->degenerate, does not span facet (one logical ridge) */ |
| 286 |
/* one tricoplanar has ->keepcentrum and ->coplanarset */ |
| 287 |
/* during qh_triangulate, f.trivisible points to original facet */ |
| 288 |
flagT newfacet:1; /* True if facet on qh newfacet_list (new or merged) */ |
| 289 |
flagT visible:1; /* True if visible facet (will be deleted) */ |
| 290 |
flagT toporient:1; /* True if created with top orientation |
| 291 |
after merging, use ridge orientation */ |
| 292 |
flagT simplicial:1;/* True if simplicial facet, ->ridges may be implicit */ |
| 293 |
flagT seen:1; /* used to perform operations only once, like visitid */ |
| 294 |
flagT seen2:1; /* used to perform operations only once, like visitid */ |
| 295 |
flagT flipped:1; /* True if facet is flipped */ |
| 296 |
flagT upperdelaunay:1; /* True if facet is upper envelope of Delaunay triangulation */ |
| 297 |
flagT notfurthest:1; /* True if last point of outsideset is not furthest*/ |
| 298 |
|
| 299 |
/*-------- flags primarily for output ---------*/ |
| 300 |
flagT good:1; /* True if a facet marked good for output */ |
| 301 |
flagT isarea:1; /* True if facet->f.area is defined */ |
| 302 |
|
| 303 |
/*-------- flags for merging ------------------*/ |
| 304 |
flagT dupridge:1; /* True if duplicate ridge in facet */ |
| 305 |
flagT mergeridge:1; /* True if facet or neighbor contains a qh_MERGEridge |
| 306 |
->normal defined (also defined for mergeridge2) */ |
| 307 |
flagT mergeridge2:1; /* True if neighbor contains a qh_MERGEridge (mark_dupridges */ |
| 308 |
flagT coplanar:1; /* True if horizon facet is coplanar at last use */ |
| 309 |
flagT mergehorizon:1; /* True if will merge into horizon (->coplanar) */ |
| 310 |
flagT cycledone:1;/* True if mergecycle_all already done */ |
| 311 |
flagT tested:1; /* True if facet convexity has been tested (false after merge */ |
| 312 |
flagT keepcentrum:1; /* True if keep old centrum after a merge, or marks owner for ->tricoplanar */ |
| 313 |
flagT newmerge:1; /* True if facet is newly merged for reducevertices */ |
| 314 |
flagT degenerate:1; /* True if facet is degenerate (degen_mergeset or ->tricoplanar) */ |
| 315 |
flagT redundant:1; /* True if facet is redundant (degen_mergeset) */ |
| 316 |
}; |
| 317 |
|
| 318 |
|
| 319 |
/*-<a href="qh-poly.htm#TOC" |
| 320 |
>--------------------------------</a><a name="ridgeT">-</a> |
| 321 |
|
| 322 |
ridgeT |
| 323 |
defines a ridge |
| 324 |
|
| 325 |
notes: |
| 326 |
a ridge is DIM3-1 simplex between two neighboring facets. If the |
| 327 |
facets are non-simplicial, there may be more than one ridge between |
| 328 |
two facets. E.G. a 4-d hypercube has two triangles between each pair |
| 329 |
of neighboring facets. |
| 330 |
|
| 331 |
topological information: |
| 332 |
vertices a set of vertices |
| 333 |
top,bottom neighboring facets with orientation |
| 334 |
|
| 335 |
geometric information: |
| 336 |
tested True if ridge is clearly convex |
| 337 |
nonconvex True if ridge is non-convex |
| 338 |
*/ |
| 339 |
struct ridgeT { |
| 340 |
setT *vertices; /* vertices belonging to this ridge, inverse sorted by ID |
| 341 |
NULL if a degen ridge (matchsame) */ |
| 342 |
facetT *top; /* top facet this ridge is part of */ |
| 343 |
facetT *bottom; /* bottom facet this ridge is part of */ |
| 344 |
unsigned id:24; /* unique identifier, =>room for 8 flags */ |
| 345 |
flagT seen:1; /* used to perform operations only once */ |
| 346 |
flagT tested:1; /* True when ridge is tested for convexity */ |
| 347 |
flagT nonconvex:1; /* True if getmergeset detected a non-convex neighbor |
| 348 |
only one ridge between neighbors may have nonconvex */ |
| 349 |
}; |
| 350 |
|
| 351 |
/*-<a href="qh-poly.htm#TOC" |
| 352 |
>--------------------------------</a><a name="vertexT">-</a> |
| 353 |
|
| 354 |
vertexT |
| 355 |
defines a vertex |
| 356 |
|
| 357 |
topological information: |
| 358 |
next,previous doubly-linked list of all vertices |
| 359 |
neighbors set of adjacent facets (only if qh.VERTEXneighbors) |
| 360 |
|
| 361 |
geometric information: |
| 362 |
point array of DIM3 coordinates |
| 363 |
*/ |
| 364 |
struct vertexT { |
| 365 |
vertexT *next; /* next vertex in vertex_list */ |
| 366 |
vertexT *previous; /* previous vertex in vertex_list */ |
| 367 |
pointT *point; /* hull_dim coordinates (coordT) */ |
| 368 |
setT *neighbors; /* neighboring facets of vertex, qh_vertexneighbors() |
| 369 |
inits in io.c or after first merge */ |
| 370 |
unsigned visitid; /* for use with qh vertex_visit */ |
| 371 |
unsigned id:24; /* unique identifier, =>room for 8 flags */ |
| 372 |
flagT seen:1; /* used to perform operations only once */ |
| 373 |
flagT seen2:1; /* another seen flag */ |
| 374 |
flagT delridge:1; /* vertex was part of a deleted ridge */ |
| 375 |
flagT deleted:1; /* true if vertex on qh del_vertices */ |
| 376 |
flagT newlist:1; /* true if vertex on qh newvertex_list */ |
| 377 |
}; |
| 378 |
|
| 379 |
/*======= -global variables -qh ============================*/ |
| 380 |
|
| 381 |
/*-<a href="qh-globa.htm#TOC" |
| 382 |
>--------------------------------</a><a name="qh">-</a> |
| 383 |
|
| 384 |
qh |
| 385 |
all global variables for qhull are in qh, qhmem, and qhstat |
| 386 |
|
| 387 |
notes: |
| 388 |
qhmem is defined in mem.h and qhstat is defined in stat.h |
| 389 |
Access to qh_qh is via the "qh" macro. See qh_QHpointer in user.h |
| 390 |
*/ |
| 391 |
typedef struct qhT qhT; |
| 392 |
#if qh_QHpointer |
| 393 |
#define qh qh_qh-> |
| 394 |
extern qhT *qh_qh; /* allocated in global.c */ |
| 395 |
#else |
| 396 |
#define qh qh_qh. |
| 397 |
extern qhT qh_qh; |
| 398 |
#endif |
| 399 |
|
| 400 |
struct qhT { |
| 401 |
|
| 402 |
/*-<a href="qh-globa.htm#TOC" |
| 403 |
>--------------------------------</a><a name="qh-const">-</a> |
| 404 |
|
| 405 |
qh constants |
| 406 |
configuration flags and constants for Qhull |
| 407 |
|
| 408 |
notes: |
| 409 |
The user configures Qhull by defining flags. They are |
| 410 |
copied into qh by qh_setflags(). qh-quick.htm#options defines the flags. |
| 411 |
*/ |
| 412 |
boolT ALLpoints; /* true 'Qs' if search all points for initial simplex */ |
| 413 |
boolT ANGLEmerge; /* true 'Qa' if sort potential merges by angle */ |
| 414 |
boolT APPROXhull; /* true 'Wn' if MINoutside set */ |
| 415 |
realT MINoutside; /* 'Wn' min. distance for an outside point */ |
| 416 |
boolT ATinfinity; /* true 'Qz' if point num_points-1 is "at-infinity" |
| 417 |
for improving precision in Delaunay triangulations */ |
| 418 |
boolT AVOIDold; /* true 'Q4' if avoid old->new merges */ |
| 419 |
boolT BESToutside; /* true 'Qf' if partition points into best outsideset */ |
| 420 |
boolT CDDinput; /* true 'Pc' if input uses CDD format (1.0/offset first) */ |
| 421 |
boolT CDDoutput; /* true 'PC' if print normals in CDD format (offset first) */ |
| 422 |
boolT CHECKfrequently; /* true 'Tc' if checking frequently */ |
| 423 |
realT premerge_cos; /* 'A-n' cos_max when pre merging */ |
| 424 |
realT postmerge_cos; /* 'An' cos_max when post merging */ |
| 425 |
boolT DELAUNAY; /* true 'd' if computing DELAUNAY triangulation */ |
| 426 |
boolT DOintersections; /* true 'Gh' if print hyperplane intersections */ |
| 427 |
int DROPdim; /* drops dim 'GDn' for 4-d -> 3-d output */ |
| 428 |
boolT FORCEoutput; /* true 'Po' if forcing output despite degeneracies */ |
| 429 |
int GOODpoint; /* 1+n for 'QGn', good facet if visible/not(-) from point n*/ |
| 430 |
pointT *GOODpointp; /* the actual point */ |
| 431 |
boolT GOODthreshold; /* true if qh lower_threshold/upper_threshold defined |
| 432 |
false if qh SPLITthreshold */ |
| 433 |
int GOODvertex; /* 1+n, good facet if vertex for point n */ |
| 434 |
pointT *GOODvertexp; /* the actual point */ |
| 435 |
boolT HALFspace; /* true 'Hn,n,n' if halfspace intersection */ |
| 436 |
int IStracing; /* trace execution, 0=none, 1=least, 4=most, -1=events */ |
| 437 |
int KEEParea; /* 'PAn' number of largest facets to keep */ |
| 438 |
boolT KEEPcoplanar; /* true 'Qc' if keeping nearest facet for coplanar points */ |
| 439 |
boolT KEEPinside; /* true 'Qi' if keeping nearest facet for inside points |
| 440 |
set automatically if 'd Qc' */ |
| 441 |
int KEEPmerge; /* 'PMn' number of facets to keep with most merges */ |
| 442 |
realT KEEPminArea; /* 'PFn' minimum facet area to keep */ |
| 443 |
realT MAXcoplanar; /* 'Un' max distance below a facet to be coplanar*/ |
| 444 |
boolT MERGEexact; /* true 'Qx' if exact merges (coplanar, degen, dupridge, flipped) */ |
| 445 |
boolT MERGEindependent; /* true 'Q2' if merging independent sets */ |
| 446 |
boolT MERGING; /* true if exact-, pre- or post-merging, with angle and centrum tests */ |
| 447 |
realT premerge_centrum; /* 'C-n' centrum_radius when pre merging. Default is round-off */ |
| 448 |
realT postmerge_centrum; /* 'Cn' centrum_radius when post merging. Default is round-off */ |
| 449 |
boolT MERGEvertices; /* true 'Q3' if merging redundant vertices */ |
| 450 |
realT MINvisible; /* 'Vn' min. distance for a facet to be visible */ |
| 451 |
boolT NOnarrow; /* true 'Q10' if no special processing for narrow distributions */ |
| 452 |
boolT NOnearinside; /* true 'Q8' if ignore near-inside points when partitioning */ |
| 453 |
boolT NOpremerge; /* true 'Q0' if no defaults for C-0 or Qx */ |
| 454 |
boolT ONLYgood; /* true 'Qg' if process points with good visible or horizon facets */ |
| 455 |
boolT ONLYmax; /* true 'Qm' if only process points that increase max_outside */ |
| 456 |
boolT PICKfurthest; /* true 'Q9' if process furthest of furthest points*/ |
| 457 |
boolT POSTmerge; /* true if merging after buildhull (Cn or An) */ |
| 458 |
boolT PREmerge; /* true if merging during buildhull (C-n or A-n) */ |
| 459 |
/* NOTE: some of these names are similar to qh_PRINT names */ |
| 460 |
boolT PRINTcentrums; /* true 'Gc' if printing centrums */ |
| 461 |
boolT PRINTcoplanar; /* true 'Gp' if printing coplanar points */ |
| 462 |
int PRINTdim; /* print dimension for Geomview output */ |
| 463 |
boolT PRINTdots; /* true 'Ga' if printing all points as dots */ |
| 464 |
boolT PRINTgood; /* true 'Pg' if printing good facets */ |
| 465 |
boolT PRINTinner; /* true 'Gi' if printing inner planes */ |
| 466 |
boolT PRINTneighbors; /* true 'PG' if printing neighbors of good facets */ |
| 467 |
boolT PRINTnoplanes; /* true 'Gn' if printing no planes */ |
| 468 |
boolT PRINToptions1st; /* true 'FO' if printing options to stderr */ |
| 469 |
boolT PRINTouter; /* true 'Go' if printing outer planes */ |
| 470 |
boolT PRINTprecision; /* false 'Pp' if not reporting precision problems */ |
| 471 |
qh_PRINT PRINTout[qh_PRINTEND]; /* list of output formats to print */ |
| 472 |
boolT PRINTridges; /* true 'Gr' if print ridges */ |
| 473 |
boolT PRINTspheres; /* true 'Gv' if print vertices as spheres */ |
| 474 |
boolT PRINTstatistics; /* true 'Ts' if printing statistics to stderr */ |
| 475 |
boolT PRINTsummary; /* true 's' if printing summary to stderr */ |
| 476 |
boolT PRINTtransparent; /* true 'Gt' if print transparent outer ridges */ |
| 477 |
boolT PROJECTdelaunay; /* true if DELAUNAY, no readpoints() and |
| 478 |
need projectinput() for Delaunay in qh_init_B */ |
| 479 |
int PROJECTinput; /* number of projected dimensions 'bn:0Bn:0' */ |
| 480 |
boolT QUICKhelp; /* true if quick help message for degen input */ |
| 481 |
boolT RANDOMdist; /* true if randomly change distplane and setfacetplane */ |
| 482 |
realT RANDOMfactor; /* maximum random perturbation */ |
| 483 |
realT RANDOMa; /* qh_randomfactor is randr * RANDOMa + RANDOMb */ |
| 484 |
realT RANDOMb; |
| 485 |
boolT RANDOMoutside; /* true if select a random outside point */ |
| 486 |
int REPORTfreq; /* buildtracing reports every n facets */ |
| 487 |
int REPORTfreq2; /* tracemerging reports every REPORTfreq/2 facets */ |
| 488 |
int RERUN; /* 'TRn' rerun qhull n times (qh.build_cnt) */ |
| 489 |
int ROTATErandom; /* 'QRn' seed, 0 time, >= rotate input */ |
| 490 |
boolT SCALEinput; /* true 'Qbk' if scaling input */ |
| 491 |
boolT SCALElast; /* true 'Qbb' if scale last coord to max prev coord */ |
| 492 |
boolT SETroundoff; /* true 'E' if qh DISTround is predefined */ |
| 493 |
boolT SKIPcheckmax; /* true 'Q5' if skip qh_check_maxout */ |
| 494 |
boolT SKIPconvex; /* true 'Q6' if skip convexity testing during pre-merge */ |
| 495 |
boolT SPLITthresholds; /* true if upper_/lower_threshold defines a region |
| 496 |
used only for printing (not for qh ONLYgood) */ |
| 497 |
int STOPcone; /* 'TCn' 1+n for stopping after cone for point n*/ |
| 498 |
/* also used by qh_build_withresart for err exit*/ |
| 499 |
int STOPpoint; /* 'TVn' 'TV-n' 1+n for stopping after/before(-) |
| 500 |
adding point n */ |
| 501 |
int TESTpoints; /* 'QTn' num of test points after qh.num_points. Test points always coplanar. */ |
| 502 |
boolT TESTvneighbors; /* true 'Qv' if test vertex neighbors at end */ |
| 503 |
int TRACElevel; /* 'Tn' conditional IStracing level */ |
| 504 |
int TRACElastrun; /* qh.TRACElevel applies to last qh.RERUN */ |
| 505 |
int TRACEpoint; /* 'TPn' start tracing when point n is a vertex */ |
| 506 |
realT TRACEdist; /* 'TWn' start tracing when merge distance too big */ |
| 507 |
int TRACEmerge; /* 'TMn' start tracing before this merge */ |
| 508 |
boolT TRIangulate; /* true 'Qt' if triangulate non-simplicial facets */ |
| 509 |
boolT TRInormals; /* true 'Q11' if triangulate duplicates normals (sets Qt) */ |
| 510 |
boolT UPPERdelaunay; /* true 'Qu' if computing furthest-site Delaunay */ |
| 511 |
boolT VERIFYoutput; /* true 'Tv' if verify output at end of qhull */ |
| 512 |
boolT VIRTUALmemory; /* true 'Q7' if depth-first processing in buildhull */ |
| 513 |
boolT VORONOI; /* true 'v' if computing Voronoi diagram */ |
| 514 |
|
| 515 |
/*--------input constants ---------*/ |
| 516 |
realT AREAfactor; /* 1/(hull_dim-1)! for converting det's to area */ |
| 517 |
boolT DOcheckmax; /* true if calling qh_check_maxout (qh_initqhull_globals) */ |
| 518 |
char *feasible_string; /* feasible point 'Hn,n,n' for halfspace intersection */ |
| 519 |
coordT *feasible_point; /* as coordinates, both malloc'd */ |
| 520 |
boolT GETarea; /* true 'Fa', 'FA', 'FS', 'PAn', 'PFn' if compute facet area/Voronoi volume in io.c */ |
| 521 |
boolT KEEPnearinside; /* true if near-inside points in coplanarset */ |
| 522 |
int hull_dim; /* dimension of hull, set by initbuffers */ |
| 523 |
int input_dim; /* dimension of input, set by initbuffers */ |
| 524 |
int num_points; /* number of input points */ |
| 525 |
pointT *first_point; /* array of input points, see POINTSmalloc */ |
| 526 |
boolT POINTSmalloc; /* true if qh first_point/num_points allocated */ |
| 527 |
pointT *input_points; /* copy of original qh.first_point for input points for qh_joggleinput */ |
| 528 |
boolT input_malloc; /* true if qh input_points malloc'd */ |
| 529 |
char qhull_command[256];/* command line that invoked this program */ |
| 530 |
char rbox_command[256]; /* command line that produced the input points */ |
| 531 |
char qhull_options[512];/* descriptive list of options */ |
| 532 |
int qhull_optionlen; /* length of last line */ |
| 533 |
int qhull_optionsiz; /* size of qhull_options before qh_initbuild */ |
| 534 |
boolT VERTEXneighbors; /* true if maintaining vertex neighbors */ |
| 535 |
boolT ZEROcentrum; /* true if 'C-0' or 'C-0 Qx'. sets ZEROall_ok */ |
| 536 |
realT *upper_threshold; /* don't print if facet->normal[k]>=upper_threshold[k] |
| 537 |
must set either GOODthreshold or SPLITthreshold |
| 538 |
if Delaunay, default is 0.0 for upper envelope */ |
| 539 |
realT *lower_threshold; /* don't print if facet->normal[k] <=lower_threshold[k] */ |
| 540 |
realT *upper_bound; /* scale point[k] to new upper bound */ |
| 541 |
realT *lower_bound; /* scale point[k] to new lower bound |
| 542 |
project if both upper_ and lower_bound == 0 */ |
| 543 |
|
| 544 |
/*-<a href="qh-globa.htm#TOC" |
| 545 |
>--------------------------------</a><a name="qh-prec">-</a> |
| 546 |
|
| 547 |
qh precision constants |
| 548 |
precision constants for Qhull |
| 549 |
|
| 550 |
notes: |
| 551 |
qh_detroundoff() computes the maximum roundoff error for distance |
| 552 |
and other computations. It also sets default values for the |
| 553 |
qh constants above. |
| 554 |
*/ |
| 555 |
realT ANGLEround; /* max round off error for angles */ |
| 556 |
realT centrum_radius; /* max centrum radius for convexity (roundoff added) */ |
| 557 |
realT cos_max; /* max cosine for convexity (roundoff added) */ |
| 558 |
realT DISTround; /* max round off error for distances, 'E' overrides */ |
| 559 |
realT MAXabs_coord; /* max absolute coordinate */ |
| 560 |
realT MAXlastcoord; /* max last coordinate for qh_scalelast */ |
| 561 |
realT MAXsumcoord; /* max sum of coordinates */ |
| 562 |
realT MAXwidth; /* max rectilinear width of point coordinates */ |
| 563 |
realT MINdenom_1; /* min. abs. value for 1/x */ |
| 564 |
realT MINdenom; /* use divzero if denominator < MINdenom */ |
| 565 |
realT MINdenom_1_2; /* min. abs. val for 1/x that allows normalization */ |
| 566 |
realT MINdenom_2; /* use divzero if denominator < MINdenom_2 */ |
| 567 |
realT MINlastcoord; /* min. last coordinate for qh_scalelast */ |
| 568 |
boolT NARROWhull; /* set in qh_initialhull if angle < qh_MAXnarrow */ |
| 569 |
realT *NEARzero; /* hull_dim array for near zero in gausselim */ |
| 570 |
realT NEARinside; /* keep points for qh_check_maxout if close to facet */ |
| 571 |
realT ONEmerge; /* max distance for merging simplicial facets */ |
| 572 |
realT outside_err; /* application's epsilon for coplanar points |
| 573 |
qh_check_bestdist() qh_check_points() reports error if point outside */ |
| 574 |
realT WIDEfacet; /* size of wide facet for skipping ridge in |
| 575 |
area computation and locking centrum */ |
| 576 |
|
| 577 |
/*-<a href="qh-globa.htm#TOC" |
| 578 |
>--------------------------------</a><a name="qh-intern">-</a> |
| 579 |
|
| 580 |
qh internal constants |
| 581 |
internal constants for Qhull |
| 582 |
*/ |
| 583 |
char qhull[sizeof("qhull")]; /* for checking ownership */ |
| 584 |
void *old_stat; /* pointer to saved qh_qhstat, qh_save_qhull */ |
| 585 |
jmp_buf errexit; /* exit label for qh_errexit, defined by setjmp() */ |
| 586 |
char jmpXtra[40]; /* extra bytes in case jmp_buf is defined wrong by compiler */ |
| 587 |
jmp_buf restartexit; /* restart label for qh_errexit, defined by setjmp() */ |
| 588 |
char jmpXtra2[40]; /* extra bytes in case jmp_buf is defined wrong by compiler*/ |
| 589 |
FILE *fin; /* pointer to input file, init by qh_meminit */ |
| 590 |
FILE *fout; /* pointer to output file */ |
| 591 |
FILE *ferr; /* pointer to error file */ |
| 592 |
pointT *interior_point; /* center point of the initial simplex*/ |
| 593 |
int normal_size; /* size in bytes for facet normals and point coords*/ |
| 594 |
int center_size; /* size in bytes for Voronoi centers */ |
| 595 |
int TEMPsize; /* size for small, temporary sets (in quick mem) */ |
| 596 |
|
| 597 |
/*-<a href="qh-globa.htm#TOC" |
| 598 |
>--------------------------------</a><a name="qh-lists">-</a> |
| 599 |
|
| 600 |
qh facet and vertex lists |
| 601 |
defines lists of facets, new facets, visible facets, vertices, and |
| 602 |
new vertices. Includes counts, next ids, and trace ids. |
| 603 |
see: |
| 604 |
qh_resetlists() |
| 605 |
*/ |
| 606 |
facetT *facet_list; /* first facet */ |
| 607 |
facetT *facet_tail; /* end of facet_list (dummy facet) */ |
| 608 |
facetT *facet_next; /* next facet for buildhull() |
| 609 |
previous facets do not have outside sets |
| 610 |
NARROWhull: previous facets may have coplanar outside sets for qh_outcoplanar */ |
| 611 |
facetT *newfacet_list; /* list of new facets to end of facet_list */ |
| 612 |
facetT *visible_list; /* list of visible facets preceeding newfacet_list, |
| 613 |
facet->visible set */ |
| 614 |
int num_visible; /* current number of visible facets */ |
| 615 |
unsigned tracefacet_id; /* set at init, then can print whenever */ |
| 616 |
facetT *tracefacet; /* set in newfacet/mergefacet, undone in delfacet*/ |
| 617 |
unsigned tracevertex_id; /* set at buildtracing, can print whenever */ |
| 618 |
vertexT *tracevertex; /* set in newvertex, undone in delvertex*/ |
| 619 |
vertexT *vertex_list; /* list of all vertices, to vertex_tail */ |
| 620 |
vertexT *vertex_tail; /* end of vertex_list (dummy vertex) */ |
| 621 |
vertexT *newvertex_list; /* list of vertices in newfacet_list, to vertex_tail |
| 622 |
all vertices have 'newlist' set */ |
| 623 |
int num_facets; /* number of facets in facet_list |
| 624 |
includes visble faces (num_visible) */ |
| 625 |
int num_vertices; /* number of vertices in facet_list */ |
| 626 |
int num_outside; /* number of points in outsidesets (for tracing and RANDOMoutside) |
| 627 |
includes coplanar outsideset points for NARROWhull/qh_outcoplanar() */ |
| 628 |
int num_good; /* number of good facets (after findgood_all) */ |
| 629 |
unsigned facet_id; /* ID of next, new facet from newfacet() */ |
| 630 |
unsigned ridge_id; /* ID of next, new ridge from newridge() */ |
| 631 |
unsigned vertex_id; /* ID of next, new vertex from newvertex() */ |
| 632 |
|
| 633 |
/*-<a href="qh-globa.htm#TOC" |
| 634 |
>--------------------------------</a><a name="qh-var">-</a> |
| 635 |
|
| 636 |
qh global variables |
| 637 |
defines minimum and maximum distances, next visit ids, several flags, |
| 638 |
and other global variables. |
| 639 |
initialize in qh_initbuild or qh_maxmin if used in qh_buildhull |
| 640 |
*/ |
| 641 |
unsigned long hulltime; /* ignore time to set up input and randomize */ |
| 642 |
/* use unsigned to avoid wrap-around errors */ |
| 643 |
boolT ALLOWrestart; /* true if qh_precision can use qh.restartexit */ |
| 644 |
int build_cnt; /* number of calls to qh_initbuild */ |
| 645 |
qh_CENTER CENTERtype; /* current type of facet->center, qh_CENTER */ |
| 646 |
int furthest_id; /* pointid of furthest point, for tracing */ |
| 647 |
facetT *GOODclosest; /* closest facet to GOODthreshold in qh_findgood */ |
| 648 |
realT JOGGLEmax; /* set 'QJn' if randomly joggle input */ |
| 649 |
boolT maxoutdone; /* set qh_check_maxout(), cleared by qh_addpoint() */ |
| 650 |
realT max_outside; /* maximum distance from a point to a facet, |
| 651 |
before roundoff, not simplicial vertices |
| 652 |
actual outer plane is +DISTround and |
| 653 |
computed outer plane is +2*DISTround */ |
| 654 |
realT max_vertex; /* maximum distance (>0) from vertex to a facet, |
| 655 |
before roundoff, due to a merge */ |
| 656 |
realT min_vertex; /* minimum distance (<0) from vertex to a facet, |
| 657 |
before roundoff, due to a merge |
| 658 |
if qh.JOGGLEmax, qh_makenewplanes sets it |
| 659 |
recomputed if qh.DOcheckmax, default -qh.DISTround */ |
| 660 |
boolT NEWfacets; /* true while visible facets invalid due to new or merge |
| 661 |
from makecone/attachnewfacets to deletevisible */ |
| 662 |
boolT findbestnew; /* true if partitioning calls qh_findbestnew */ |
| 663 |
boolT findbest_notsharp; /* true if new facets are at least 90 degrees */ |
| 664 |
boolT NOerrexit; /* true if qh.errexit is not available */ |
| 665 |
realT PRINTcradius; /* radius for printing centrums */ |
| 666 |
realT PRINTradius; /* radius for printing vertex spheres and points */ |
| 667 |
boolT POSTmerging; /* true when post merging */ |
| 668 |
int printoutvar; /* temporary variable for qh_printbegin, etc. */ |
| 669 |
int printoutnum; /* number of facets printed */ |
| 670 |
boolT QHULLfinished; /* True after qhull() is finished */ |
| 671 |
realT totarea; /* 'FA': total facet area computed by qh_getarea */ |
| 672 |
realT totvol; /* 'FA': total volume computed by qh_getarea */ |
| 673 |
unsigned int visit_id; /* unique ID for searching neighborhoods, */ |
| 674 |
unsigned int vertex_visit; /* unique ID for searching vertices */ |
| 675 |
boolT ZEROall_ok; /* True if qh_checkzero always succeeds */ |
| 676 |
boolT WAScoplanar; /* True if qh_partitioncoplanar (qh_check_maxout) */ |
| 677 |
|
| 678 |
/*-<a href="qh-globa.htm#TOC" |
| 679 |
>--------------------------------</a><a name="qh-set">-</a> |
| 680 |
|
| 681 |
qh global sets |
| 682 |
defines sets for merging, initial simplex, hashing, extra input points, |
| 683 |
and deleted vertices |
| 684 |
*/ |
| 685 |
setT *facet_mergeset; /* temporary set of merges to be done */ |
| 686 |
setT *degen_mergeset; /* temporary set of degenerate and redundant merges */ |
| 687 |
setT *hash_table; /* hash table for matching ridges in qh_matchfacets |
| 688 |
size is setsize() */ |
| 689 |
setT *other_points; /* additional points (first is qh interior_point) */ |
| 690 |
setT *del_vertices; /* vertices to partition and delete with visible |
| 691 |
facets. Have deleted set for checkfacet */ |
| 692 |
|
| 693 |
/*-<a href="qh-globa.htm#TOC" |
| 694 |
>--------------------------------</a><a name="qh-buf">-</a> |
| 695 |
|
| 696 |
qh global buffers |
| 697 |
defines buffers for maxtrix operations, input, and error messages |
| 698 |
*/ |
| 699 |
coordT *gm_matrix; /* (dim+1)Xdim matrix for geom.c */ |
| 700 |
coordT **gm_row; /* array of gm_matrix rows */ |
| 701 |
char* line; /* malloc'd input line of maxline+1 chars */ |
| 702 |
int maxline; |
| 703 |
coordT *half_space; /* malloc'd input array for halfspace (qh normal_size+coordT) */ |
| 704 |
coordT *temp_malloc; /* malloc'd input array for points */ |
| 705 |
|
| 706 |
/*-<a href="qh-globa.htm#TOC" |
| 707 |
>--------------------------------</a><a name="qh-static">-</a> |
| 708 |
|
| 709 |
qh static variables |
| 710 |
defines static variables for individual functions |
| 711 |
|
| 712 |
notes: |
| 713 |
do not use 'static' within a function. Multiple instances of qhull |
| 714 |
may exist. |
| 715 |
|
| 716 |
do not assume zero initialization, 'QPn' may cause a restart |
| 717 |
*/ |
| 718 |
boolT ERREXITcalled; /* true during errexit (prevents duplicate calls */ |
| 719 |
boolT firstcentrum; /* for qh_printcentrum */ |
| 720 |
realT last_low; /* qh_scalelast parameters for qh_setdelaunay */ |
| 721 |
realT last_high; |
| 722 |
realT last_newhigh; |
| 723 |
unsigned lastreport; /* for qh_buildtracing */ |
| 724 |
int mergereport; /* for qh_tracemerging */ |
| 725 |
boolT old_randomdist; /* save RANDOMdist when io, tracing, or statistics */ |
| 726 |
int ridgeoutnum; /* number of ridges in 4OFF output */ |
| 727 |
void *old_qhstat; /* for saving qh_qhstat in save_qhull() */ |
| 728 |
setT *old_tempstack; /* for saving qhmem.tempstack in save_qhull */ |
| 729 |
setT *coplanarset; /* set of coplanar facets for searching qh_findbesthorizon() */ |
| 730 |
}; |
| 731 |
|
| 732 |
/*=========== -macros- =========================*/ |
| 733 |
|
| 734 |
/*-<a href="qh-poly.htm#TOC" |
| 735 |
>--------------------------------</a><a name="otherfacet_">-</a> |
| 736 |
|
| 737 |
otherfacet_(ridge, facet) |
| 738 |
return neighboring facet for a ridge in facet |
| 739 |
*/ |
| 740 |
#define otherfacet_(ridge, facet) \ |
| 741 |
(((ridge)->top == (facet)) ? (ridge)->bottom : (ridge)->top) |
| 742 |
|
| 743 |
/*-<a href="qh-poly.htm#TOC" |
| 744 |
>--------------------------------</a><a name="getid_">-</a> |
| 745 |
|
| 746 |
getid_(p) |
| 747 |
return ID for facet, ridge, or vertex |
| 748 |
return MAXINT if NULL (-1 causes type conversion error ) |
| 749 |
*/ |
| 750 |
#define getid_(p) ((p) ? (p)->id : -1) |
| 751 |
|
| 752 |
/*============== FORALL macros ===================*/ |
| 753 |
|
| 754 |
/*-<a href="qh-poly.htm#TOC" |
| 755 |
>--------------------------------</a><a name="FORALLfacets">-</a> |
| 756 |
|
| 757 |
FORALLfacets { ... } |
| 758 |
assign 'facet' to each facet in qh.facet_list |
| 759 |
|
| 760 |
notes: |
| 761 |
uses 'facetT *facet;' |
| 762 |
assumes last facet is a sentinel |
| 763 |
|
| 764 |
see: |
| 765 |
FORALLfacet_( facetlist ) |
| 766 |
*/ |
| 767 |
#define FORALLfacets for (facet=qh facet_list;facet && facet->next;facet=facet->next) |
| 768 |
|
| 769 |
/*-<a href="qh-poly.htm#TOC" |
| 770 |
>--------------------------------</a><a name="FORALLpoints">-</a> |
| 771 |
|
| 772 |
FORALLpoints { ... } |
| 773 |
assign 'point' to each point in qh.first_point, qh.num_points |
| 774 |
|
| 775 |
declare: |
| 776 |
coordT *point, *pointtemp; |
| 777 |
*/ |
| 778 |
#define FORALLpoints FORALLpoint_(qh first_point, qh num_points) |
| 779 |
|
| 780 |
/*-<a href="qh-poly.htm#TOC" |
| 781 |
>--------------------------------</a><a name="FORALLpoint_">-</a> |
| 782 |
|
| 783 |
FORALLpoint_( points, num) { ... } |
| 784 |
assign 'point' to each point in points array of num points |
| 785 |
|
| 786 |
declare: |
| 787 |
coordT *point, *pointtemp; |
| 788 |
*/ |
| 789 |
#define FORALLpoint_(points, num) for(point= (points), \ |
| 790 |
pointtemp= (points)+qh hull_dim*(num); point < pointtemp; point += qh hull_dim) |
| 791 |
|
| 792 |
/*-<a href="qh-poly.htm#TOC" |
| 793 |
>--------------------------------</a><a name="FORALLvertices">-</a> |
| 794 |
|
| 795 |
FORALLvertices { ... } |
| 796 |
assign 'vertex' to each vertex in qh.vertex_list |
| 797 |
|
| 798 |
declare: |
| 799 |
vertexT *vertex; |
| 800 |
|
| 801 |
notes: |
| 802 |
assumes qh.vertex_list terminated with a sentinel |
| 803 |
*/ |
| 804 |
#define FORALLvertices for (vertex=qh vertex_list;vertex && vertex->next;vertex= vertex->next) |
| 805 |
|
| 806 |
/*-<a href="qh-poly.htm#TOC" |
| 807 |
>--------------------------------</a><a name="FOREACHfacet_">-</a> |
| 808 |
|
| 809 |
FOREACHfacet_( facets ) { ... } |
| 810 |
assign 'facet' to each facet in facets |
| 811 |
|
| 812 |
declare: |
| 813 |
facetT *facet, **facetp; |
| 814 |
|
| 815 |
see: |
| 816 |
<a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a> |
| 817 |
*/ |
| 818 |
#define FOREACHfacet_(facets) FOREACHsetelement_(facetT, facets, facet) |
| 819 |
|
| 820 |
/*-<a href="qh-poly.htm#TOC" |
| 821 |
>--------------------------------</a><a name="FOREACHneighbor_">-</a> |
| 822 |
|
| 823 |
FOREACHneighbor_( facet ) { ... } |
| 824 |
assign 'neighbor' to each neighbor in facet->neighbors |
| 825 |
|
| 826 |
FOREACHneighbor_( vertex ) { ... } |
| 827 |
assign 'neighbor' to each neighbor in vertex->neighbors |
| 828 |
|
| 829 |
declare: |
| 830 |
facetT *neighbor, **neighborp; |
| 831 |
|
| 832 |
see: |
| 833 |
<a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a> |
| 834 |
*/ |
| 835 |
#define FOREACHneighbor_(facet) FOREACHsetelement_(facetT, facet->neighbors, neighbor) |
| 836 |
|
| 837 |
/*-<a href="qh-poly.htm#TOC" |
| 838 |
>--------------------------------</a><a name="FOREACHpoint_">-</a> |
| 839 |
|
| 840 |
FOREACHpoint_( points ) { ... } |
| 841 |
assign 'point' to each point in points set |
| 842 |
|
| 843 |
declare: |
| 844 |
pointT *point, **pointp; |
| 845 |
|
| 846 |
see: |
| 847 |
<a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a> |
| 848 |
*/ |
| 849 |
#define FOREACHpoint_(points) FOREACHsetelement_(pointT, points, point) |
| 850 |
|
| 851 |
/*-<a href="qh-poly.htm#TOC" |
| 852 |
>--------------------------------</a><a name="FOREACHridge_">-</a> |
| 853 |
|
| 854 |
FOREACHridge_( ridges ) { ... } |
| 855 |
assign 'ridge' to each ridge in ridges set |
| 856 |
|
| 857 |
declare: |
| 858 |
ridgeT *ridge, **ridgep; |
| 859 |
|
| 860 |
see: |
| 861 |
<a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a> |
| 862 |
*/ |
| 863 |
#define FOREACHridge_(ridges) FOREACHsetelement_(ridgeT, ridges, ridge) |
| 864 |
|
| 865 |
/*-<a href="qh-poly.htm#TOC" |
| 866 |
>--------------------------------</a><a name="FOREACHvertex_">-</a> |
| 867 |
|
| 868 |
FOREACHvertex_( vertices ) { ... } |
| 869 |
assign 'vertex' to each vertex in vertices set |
| 870 |
|
| 871 |
declare: |
| 872 |
vertexT *vertex, **vertexp; |
| 873 |
|
| 874 |
see: |
| 875 |
<a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a> |
| 876 |
*/ |
| 877 |
#define FOREACHvertex_(vertices) FOREACHsetelement_(vertexT, vertices,vertex) |
| 878 |
|
| 879 |
/*-<a href="qh-poly.htm#TOC" |
| 880 |
>--------------------------------</a><a name="FOREACHfacet_i_">-</a> |
| 881 |
|
| 882 |
FOREACHfacet_i_( facets ) { ... } |
| 883 |
assign 'facet' and 'facet_i' for each facet in facets set |
| 884 |
|
| 885 |
declare: |
| 886 |
facetT *facet; |
| 887 |
int facet_n, facet_i; |
| 888 |
|
| 889 |
see: |
| 890 |
<a href="qset.h#FOREACHsetelement_i_">FOREACHsetelement_i_</a> |
| 891 |
*/ |
| 892 |
#define FOREACHfacet_i_(facets) FOREACHsetelement_i_(facetT, facets, facet) |
| 893 |
|
| 894 |
/*-<a href="qh-poly.htm#TOC" |
| 895 |
>--------------------------------</a><a name="FOREACHneighbor_i_">-</a> |
| 896 |
|
| 897 |
FOREACHneighbor_i_( facet ) { ... } |
| 898 |
assign 'neighbor' and 'neighbor_i' for each neighbor in facet->neighbors |
| 899 |
|
| 900 |
FOREACHneighbor_i_( vertex ) { ... } |
| 901 |
assign 'neighbor' and 'neighbor_i' for each neighbor in vertex->neighbors |
| 902 |
|
| 903 |
declare: |
| 904 |
facetT *neighbor; |
| 905 |
int neighbor_n, neighbor_i; |
| 906 |
|
| 907 |
see: |
| 908 |
<a href="qset.h#FOREACHsetelement_i_">FOREACHsetelement_i_</a> |
| 909 |
*/ |
| 910 |
#define FOREACHneighbor_i_(facet) FOREACHsetelement_i_(facetT, facet->neighbors, neighbor) |
| 911 |
|
| 912 |
/*-<a href="qh-poly.htm#TOC" |
| 913 |
>--------------------------------</a><a name="FOREACHpoint_i_">-</a> |
| 914 |
|
| 915 |
FOREACHpoint_i_( points ) { ... } |
| 916 |
assign 'point' and 'point_i' for each point in points set |
| 917 |
|
| 918 |
declare: |
| 919 |
pointT *point; |
| 920 |
int point_n, point_i; |
| 921 |
|
| 922 |
see: |
| 923 |
<a href="qset.h#FOREACHsetelement_i_">FOREACHsetelement_i_</a> |
| 924 |
*/ |
| 925 |
#define FOREACHpoint_i_(points) FOREACHsetelement_i_(pointT, points, point) |
| 926 |
|
| 927 |
/*-<a href="qh-poly.htm#TOC" |
| 928 |
>--------------------------------</a><a name="FOREACHridge_i_">-</a> |
| 929 |
|
| 930 |
FOREACHridge_i_( ridges ) { ... } |
| 931 |
assign 'ridge' and 'ridge_i' for each ridge in ridges set |
| 932 |
|
| 933 |
declare: |
| 934 |
ridgeT *ridge; |
| 935 |
int ridge_n, ridge_i; |
| 936 |
|
| 937 |
see: |
| 938 |
<a href="qset.h#FOREACHsetelement_i_">FOREACHsetelement_i_</a> |
| 939 |
*/ |
| 940 |
#define FOREACHridge_i_(ridges) FOREACHsetelement_i_(ridgeT, ridges, ridge) |
| 941 |
|
| 942 |
/*-<a href="qh-poly.htm#TOC" |
| 943 |
>--------------------------------</a><a name="FOREACHvertex_i_">-</a> |
| 944 |
|
| 945 |
FOREACHvertex_i_( vertices ) { ... } |
| 946 |
assign 'vertex' and 'vertex_i' for each vertex in vertices set |
| 947 |
|
| 948 |
declare: |
| 949 |
vertexT *vertex; |
| 950 |
int vertex_n, vertex_i; |
| 951 |
|
| 952 |
see: |
| 953 |
<a href="qset.h#FOREACHsetelement_i_">FOREACHsetelement_i_</a> |
| 954 |
*/ |
| 955 |
#define FOREACHvertex_i_(vertices) FOREACHsetelement_i_(vertexT, vertices,vertex) |
| 956 |
|
| 957 |
/********* -qhull.c prototypes (duplicated from qhull_a.h) **********************/ |
| 958 |
|
| 959 |
void qh_qhull (void); |
| 960 |
boolT qh_addpoint (pointT *furthest, facetT *facet, boolT checkdist); |
| 961 |
void qh_printsummary(FILE *fp); |
| 962 |
|
| 963 |
/********* -user.c prototypes (alphabetical) **********************/ |
| 964 |
|
| 965 |
void qh_errexit(int exitcode, facetT *facet, ridgeT *ridge); |
| 966 |
void qh_errprint(char* string, facetT *atfacet, facetT *otherfacet, ridgeT *atridge, vertexT *atvertex); |
| 967 |
int qh_new_qhull (int dim, int numpoints, coordT *points, boolT ismalloc, |
| 968 |
char *qhull_cmd, FILE *outfile, FILE *errfile); |
| 969 |
void qh_printfacetlist(facetT *facetlist, setT *facets, boolT printall); |
| 970 |
void qh_user_memsizes (void); |
| 971 |
|
| 972 |
/***** -geom.c/geom2.c prototypes (duplicated from geom.h) ****************/ |
| 973 |
|
| 974 |
facetT *qh_findbest (pointT *point, facetT *startfacet, |
| 975 |
boolT bestoutside, boolT newfacets, boolT noupper, |
| 976 |
realT *dist, boolT *isoutside, int *numpart); |
| 977 |
facetT *qh_findbestnew (pointT *point, facetT *startfacet, |
| 978 |
realT *dist, boolT bestoutside, boolT *isoutside, int *numpart); |
| 979 |
boolT qh_gram_schmidt(int dim, realT **rows); |
| 980 |
void qh_outerinner (facetT *facet, realT *outerplane, realT *innerplane); |
| 981 |
void qh_printsummary(FILE *fp); |
| 982 |
void qh_projectinput (void); |
| 983 |
void qh_randommatrix (realT *buffer, int dim, realT **row); |
| 984 |
void qh_rotateinput (realT **rows); |
| 985 |
void qh_scaleinput (void); |
| 986 |
void qh_setdelaunay (int dim, int count, pointT *points); |
| 987 |
coordT *qh_sethalfspace_all (int dim, int count, coordT *halfspaces, pointT *feasible); |
| 988 |
|
| 989 |
/***** -global.c prototypes (alphabetical) ***********************/ |
| 990 |
|
| 991 |
unsigned long qh_clock (void); |
| 992 |
void qh_checkflags (char *command, char *hiddenflags); |
| 993 |
void qh_freebuffers (void); |
| 994 |
void qh_freeqhull (boolT allmem); |
| 995 |
void qh_init_A (FILE *infile, FILE *outfile, FILE *errfile, int argc, char *argv[]); |
| 996 |
void qh_init_B (coordT *points, int numpoints, int dim, boolT ismalloc); |
| 997 |
void qh_init_qhull_command (int argc, char *argv[]); |
| 998 |
void qh_initbuffers (coordT *points, int numpoints, int dim, boolT ismalloc); |
| 999 |
void qh_initflags (char *command); |
| 1000 |
void qh_initqhull_buffers (void); |
| 1001 |
void qh_initqhull_globals (coordT *points, int numpoints, int dim, boolT ismalloc); |
| 1002 |
void qh_initqhull_mem (void); |
| 1003 |
void qh_initqhull_start (FILE *infile, FILE *outfile, FILE *errfile); |
| 1004 |
void qh_initthresholds (char *command); |
| 1005 |
void qh_option (char *option, int *i, realT *r); |
| 1006 |
#if qh_QHpointer |
| 1007 |
void qh_restore_qhull (qhT **oldqh); |
| 1008 |
qhT *qh_save_qhull (void); |
| 1009 |
#endif |
| 1010 |
|
| 1011 |
/***** -io.c prototypes (duplicated from io.h) ***********************/ |
| 1012 |
|
| 1013 |
void dfacet( unsigned id); |
| 1014 |
void dvertex( unsigned id); |
| 1015 |
void qh_printneighborhood (FILE *fp, int format, facetT *facetA, facetT *facetB, boolT printall); |
| 1016 |
void qh_produce_output(void); |
| 1017 |
coordT *qh_readpoints(int *numpoints, int *dimension, boolT *ismalloc); |
| 1018 |
|
| 1019 |
|
| 1020 |
/********* -mem.c prototypes (duplicated from mem.h) **********************/ |
| 1021 |
|
| 1022 |
void qh_meminit (FILE *ferr); |
| 1023 |
void qh_memfreeshort (int *curlong, int *totlong); |
| 1024 |
|
| 1025 |
/********* -poly.c/poly2.c prototypes (duplicated from poly.h) **********************/ |
| 1026 |
|
| 1027 |
void qh_check_output (void); |
| 1028 |
void qh_check_points (void); |
| 1029 |
setT *qh_facetvertices (facetT *facetlist, setT *facets, boolT allfacets); |
| 1030 |
facetT *qh_findbestfacet (pointT *point, boolT bestoutside, |
| 1031 |
realT *bestdist, boolT *isoutside); |
| 1032 |
vertexT *qh_nearvertex (facetT *facet, pointT *point, realT *bestdistp); |
| 1033 |
pointT *qh_point (int id); |
| 1034 |
setT *qh_pointfacet (void /*qh.facet_list*/); |
| 1035 |
int qh_pointid (pointT *point); |
| 1036 |
setT *qh_pointvertex (void /*qh.facet_list*/); |
| 1037 |
void qh_setvoronoi_all (void); |
| 1038 |
void qh_triangulate (void /*qh facet_list*/); |
| 1039 |
|
| 1040 |
/********* -stat.c prototypes (duplicated from stat.h) **********************/ |
| 1041 |
|
| 1042 |
void qh_collectstatistics (void); |
| 1043 |
void qh_printallstatistics (FILE *fp, char *string); |
| 1044 |
|
| 1045 |
#endif /* qhDEFqhull */ |
