| 1 |
/* |
| 2 |
<html><pre> -<a href="qh-user.htm" |
| 3 |
>-------------------------------</a><a name="TOP">-</a> |
| 4 |
|
| 5 |
user.h |
| 6 |
user redefinable constants |
| 7 |
|
| 8 |
see qh-user.htm. see COPYING for copyright information. |
| 9 |
|
| 10 |
before reading any code, review qhull.h for data structure definitions and |
| 11 |
the "qh" macro. |
| 12 |
*/ |
| 13 |
|
| 14 |
#ifndef qhDEFuser |
| 15 |
#define qhDEFuser 1 |
| 16 |
|
| 17 |
/*============= data types and configuration macros ==========*/ |
| 18 |
|
| 19 |
/* |
| 20 |
-<a href="qh-user.htm#TOC" |
| 21 |
>--------------------------------</a><a name="realT">-</a> |
| 22 |
|
| 23 |
realT |
| 24 |
set the size of floating point numbers |
| 25 |
|
| 26 |
qh_REALdigits |
| 27 |
maximimum number of significant digits |
| 28 |
|
| 29 |
qh_REAL_1, qh_REAL_2n, qh_REAL_3n |
| 30 |
format strings for printf |
| 31 |
|
| 32 |
qh_REALmax, qh_REALmin |
| 33 |
maximum and minimum (near zero) values |
| 34 |
|
| 35 |
qh_REALepsilon |
| 36 |
machine roundoff. Maximum roundoff error for addition and multiplication. |
| 37 |
|
| 38 |
notes: |
| 39 |
Select whether to store floating point numbers in single precision (float) |
| 40 |
or double precision (double). |
| 41 |
|
| 42 |
Use 'float' to save about 8% in time and 25% in space. This is particularly |
| 43 |
help if high-d where convex hulls are space limited. Using 'float' also |
| 44 |
reduces the printed size of Qhull's output since numbers have 8 digits of |
| 45 |
precision. |
| 46 |
|
| 47 |
Use 'double' when greater arithmetic precision is needed. This is needed |
| 48 |
for Delaunay triangulations and Voronoi diagrams when you are not merging |
| 49 |
facets. |
| 50 |
|
| 51 |
If 'double' gives insufficient precision, your data probably includes |
| 52 |
degeneracies. If so you should use facet merging (done by default) |
| 53 |
or exact arithmetic (see imprecision section of manual, qh-impre.htm). |
| 54 |
You may also use option 'Po' to force output despite precision errors. |
| 55 |
|
| 56 |
You may use 'long double', but many format statements need to be changed |
| 57 |
and you may need a 'long double' square root routine. S. Grundmann |
| 58 |
(sg@eeiwzb.et.tu-dresden.de) has done this. He reports that the code runs |
| 59 |
much slower with little gain in precision. |
| 60 |
|
| 61 |
WARNING: on some machines, int f(){realT a= REALmax;return (a == REALmax);} |
| 62 |
returns False. Use (a > REALmax/2) instead of (a == REALmax). |
| 63 |
|
| 64 |
REALfloat = 1 all numbers are 'float' type |
| 65 |
= 0 all numbers are 'double' type |
| 66 |
*/ |
| 67 |
#ifdef SINGLE_PRECISION |
| 68 |
#define REALfloat 1 |
| 69 |
#else |
| 70 |
#define REALfloat 0 |
| 71 |
#endif |
| 72 |
|
| 73 |
#if (REALfloat == 1) |
| 74 |
#define realT float |
| 75 |
#define REALmax FLT_MAX |
| 76 |
#define REALmin FLT_MIN |
| 77 |
#define REALepsilon FLT_EPSILON |
| 78 |
/* maximum number of significant digits */ |
| 79 |
#define qh_REALdigits 8 |
| 80 |
#define qh_REAL_1 "%6.8g " |
| 81 |
#define qh_REAL_2n "%6.8g %6.8g\n" |
| 82 |
#define qh_REAL_3n "%6.8g %6.8g %6.8g\n" |
| 83 |
|
| 84 |
#elif (REALfloat == 0) |
| 85 |
#define realT double |
| 86 |
#define REALmax DBL_MAX |
| 87 |
#define REALmin DBL_MIN |
| 88 |
#define REALepsilon DBL_EPSILON |
| 89 |
/* maximum number of significant digits */ |
| 90 |
#define qh_REALdigits 16 |
| 91 |
#define qh_REAL_1 "%6.16g " |
| 92 |
#define qh_REAL_2n "%6.16g %6.16g\n" |
| 93 |
#define qh_REAL_3n "%6.16g %6.16g %6.16g\n" |
| 94 |
|
| 95 |
#else |
| 96 |
#error unknown float option |
| 97 |
#endif |
| 98 |
|
| 99 |
/*-<a href="qh-user.htm#TOC" |
| 100 |
>--------------------------------</a><a name="CPUclock">-</a> |
| 101 |
|
| 102 |
qh_CPUclock |
| 103 |
define the clock() function for reporting the total time spent by Qhull |
| 104 |
returns CPU ticks as a 'long int' |
| 105 |
qh_CPUclock is only used for reporting the total time spent by Qhull |
| 106 |
|
| 107 |
qh_SECticks |
| 108 |
the number of clock ticks per second |
| 109 |
|
| 110 |
notes: |
| 111 |
looks for CLOCKS_PER_SEC, CLOCKS_PER_SECOND, or assumes microseconds |
| 112 |
to define a custom clock, set qh_CLOCKtype to 0 |
| 113 |
|
| 114 |
if your system does not use clock() to return CPU ticks, replace |
| 115 |
qh_CPUclock with the corresponding function. It is converted |
| 116 |
to unsigned long to prevent wrap-around during long runs. |
| 117 |
|
| 118 |
|
| 119 |
Set qh_CLOCKtype to |
| 120 |
|
| 121 |
1 for CLOCKS_PER_SEC, CLOCKS_PER_SECOND, or microsecond |
| 122 |
Note: may fail if more than 1 hour elapsed time |
| 123 |
|
| 124 |
2 use qh_clock() with POSIX times() (see global.c) |
| 125 |
*/ |
| 126 |
/* change to the desired number */ |
| 127 |
#define qh_CLOCKtype 1 |
| 128 |
#if (qh_CLOCKtype == 1) |
| 129 |
|
| 130 |
#if defined (CLOCKS_PER_SECOND) |
| 131 |
/* return CPU clock */ |
| 132 |
#define qh_CPUclock ((unsigned long)clock()) |
| 133 |
#define qh_SECticks CLOCKS_PER_SECOND |
| 134 |
|
| 135 |
#elif defined (CLOCKS_PER_SEC) |
| 136 |
/* return CPU clock */ |
| 137 |
#define qh_CPUclock ((unsigned long)clock()) |
| 138 |
#define qh_SECticks CLOCKS_PER_SEC |
| 139 |
|
| 140 |
#elif defined (CLK_TCK) |
| 141 |
/* return CPU clock */ |
| 142 |
#define qh_CPUclock ((unsigned long)clock()) |
| 143 |
#define qh_SECticks CLK_TCK |
| 144 |
|
| 145 |
#else |
| 146 |
/* return CPU clock */ |
| 147 |
#define qh_CPUclock ((unsigned long)clock()) |
| 148 |
#define qh_SECticks 1E6 |
| 149 |
#endif |
| 150 |
|
| 151 |
#elif (qh_CLOCKtype == 2) |
| 152 |
/* return CPU clock */ |
| 153 |
#define qh_CPUclock qh_clock() |
| 154 |
#define qh_SECticks 100 |
| 155 |
|
| 156 |
#else |
| 157 |
/* qh_CLOCKtype == ? */ |
| 158 |
#error unknown clock option |
| 159 |
#endif |
| 160 |
|
| 161 |
/*-<a href="qh-user.htm#TOC" |
| 162 |
>--------------------------------</a><a name="RANDOM">-</a> |
| 163 |
|
| 164 |
qh_RANDOMtype, qh_RANDOMmax, qh_RANDOMseed |
| 165 |
define random number generator |
| 166 |
|
| 167 |
qh_RANDOMint generates a random integer between 0 and qh_RANDOMmax. |
| 168 |
qh_RANDOMseed sets the random number seed for qh_RANDOMint |
| 169 |
|
| 170 |
Set qh_RANDOMtype (default 5) to: |
| 171 |
1 for random() with 31 bits (UCB) |
| 172 |
2 for rand() with RAND_MAX or 15 bits (system 5) |
| 173 |
3 for rand() with 31 bits (Sun) |
| 174 |
4 for lrand48() with 31 bits (Solaris) |
| 175 |
5 for qh_rand() with 31 bits (included with Qhull) |
| 176 |
|
| 177 |
notes: |
| 178 |
Random numbers are used by rbox to generate point sets. Random |
| 179 |
numbers are used by Qhull to rotate the input ('QRn' option), |
| 180 |
simulate a randomized algorithm ('Qr' option), and to simulate |
| 181 |
roundoff errors ('Rn' option). |
| 182 |
|
| 183 |
Random number generators differ between systems. Most systems provide |
| 184 |
rand() but the period varies. The period of rand() is not critical |
| 185 |
since qhull does not normally use random numbers. |
| 186 |
|
| 187 |
The default generator is Park & Miller's minimal standard random |
| 188 |
number generator [CACM 31:1195 '88]. It is included with Qhull. |
| 189 |
|
| 190 |
If qh_RANDOMmax is wrong, qhull will report a warning and Geomview |
| 191 |
output will likely be invisible. |
| 192 |
*/ |
| 193 |
/* *** change to the desired number *** */ |
| 194 |
#define qh_RANDOMtype 5 |
| 195 |
#if (qh_RANDOMtype == 1) |
| 196 |
/* 31 bits, random()/MAX */ |
| 197 |
#define qh_RANDOMmax ((realT)0x7fffffffUL) |
| 198 |
#define qh_RANDOMint random() |
| 199 |
#define qh_RANDOMseed_(seed) srandom(seed); |
| 200 |
|
| 201 |
#elif (qh_RANDOMtype == 2) |
| 202 |
#ifdef RAND_MAX |
| 203 |
#define qh_RANDOMmax ((realT)RAND_MAX) |
| 204 |
#else |
| 205 |
/* 15 bits (System 5) */ |
| 206 |
#define qh_RANDOMmax ((realT)32767) |
| 207 |
#endif |
| 208 |
#define qh_RANDOMint rand() |
| 209 |
#define qh_RANDOMseed_(seed) srand((unsigned)seed); |
| 210 |
|
| 211 |
#elif (qh_RANDOMtype == 3) |
| 212 |
/* 31 bits, Sun */ |
| 213 |
#define qh_RANDOMmax ((realT)0x7fffffffUL) |
| 214 |
#define qh_RANDOMint rand() |
| 215 |
#define qh_RANDOMseed_(seed) srand((unsigned)seed); |
| 216 |
|
| 217 |
#elif (qh_RANDOMtype == 4) |
| 218 |
/* 31 bits, lrand38()/MAX */ |
| 219 |
#define qh_RANDOMmax ((realT)0x7fffffffUL) |
| 220 |
#define qh_RANDOMint lrand48() |
| 221 |
#define qh_RANDOMseed_(seed) srand48(seed); |
| 222 |
|
| 223 |
#elif (qh_RANDOMtype == 5) |
| 224 |
/* 31 bits, qh_rand/MAX */ |
| 225 |
#define qh_RANDOMmax ((realT)2147483646UL) |
| 226 |
#define qh_RANDOMint qh_rand() |
| 227 |
#define qh_RANDOMseed_(seed) qh_srand(seed); |
| 228 |
/* unlike rand(), never returns 0 */ |
| 229 |
|
| 230 |
#else |
| 231 |
#error: unknown random option |
| 232 |
#endif |
| 233 |
|
| 234 |
/*-<a href="qh-user.htm#TOC" |
| 235 |
>--------------------------------</a><a name="ORIENTclock">-</a> |
| 236 |
|
| 237 |
qh_ORIENTclock |
| 238 |
0 for inward pointing normals by Geomview convention |
| 239 |
*/ |
| 240 |
#define qh_ORIENTclock 0 |
| 241 |
|
| 242 |
|
| 243 |
/*========= performance related constants =========*/ |
| 244 |
|
| 245 |
/*-<a href="qh-user.htm#TOC" |
| 246 |
>--------------------------------</a><a name="HASHfactor">-</a> |
| 247 |
|
| 248 |
qh_HASHfactor |
| 249 |
total hash slots / used hash slots. Must be at least 1.1. |
| 250 |
|
| 251 |
notes: |
| 252 |
=2 for at worst 50% occupancy for qh hash_table and normally 25% occupancy |
| 253 |
*/ |
| 254 |
#define qh_HASHfactor 2 |
| 255 |
|
| 256 |
/*-<a href="qh-user.htm#TOC" |
| 257 |
>--------------------------------</a><a name="VERIFYdirect">-</a> |
| 258 |
|
| 259 |
qh_VERIFYdirect |
| 260 |
with 'Tv' verify all points against all facets if op count is smaller |
| 261 |
|
| 262 |
notes: |
| 263 |
if greater, calls qh_check_bestdist() instead |
| 264 |
*/ |
| 265 |
#define qh_VERIFYdirect 1000000 |
| 266 |
|
| 267 |
/*-<a href="qh-user.htm#TOC" |
| 268 |
>--------------------------------</a><a name="INITIALsearch">-</a> |
| 269 |
|
| 270 |
qh_INITIALsearch |
| 271 |
if qh_INITIALmax, search points up to this dimension |
| 272 |
*/ |
| 273 |
#define qh_INITIALsearch 6 |
| 274 |
|
| 275 |
/*-<a href="qh-user.htm#TOC" |
| 276 |
>--------------------------------</a><a name="INITIALmax">-</a> |
| 277 |
|
| 278 |
qh_INITIALmax |
| 279 |
if dim >= qh_INITIALmax, use min/max coordinate points for initial simplex |
| 280 |
|
| 281 |
notes: |
| 282 |
from points with non-zero determinants |
| 283 |
please use option 'Qs' to override (much slower) |
| 284 |
*/ |
| 285 |
#define qh_INITIALmax 8 |
| 286 |
|
| 287 |
/*-<a href="qh-user.htm#TOC" |
| 288 |
>--------------------------------</a><a name="JOGGLEdefault">-</a> |
| 289 |
|
| 290 |
qh_JOGGLEdefault |
| 291 |
default qh.JOGGLEmax is qh.DISTround * qh_JOGGLEdefault |
| 292 |
|
| 293 |
notes: |
| 294 |
rbox s r 100 | qhull QJ1e-15 QR0 generates 90% faults at distround 7e-16 |
| 295 |
rbox s r 100 | qhull QJ1e-14 QR0 generates 70% faults |
| 296 |
rbox s r 100 | qhull QJ1e-13 QR0 generates 35% faults |
| 297 |
rbox s r 100 | qhull QJ1e-12 QR0 generates 8% faults |
| 298 |
rbox s r 100 | qhull QJ1e-11 QR0 generates 1% faults |
| 299 |
rbox s r 100 | qhull QJ1e-10 QR0 generates 0% faults |
| 300 |
rbox 1000 W0 | qhull QJ1e-12 QR0 generates 86% faults |
| 301 |
rbox 1000 W0 | qhull QJ1e-11 QR0 generates 20% faults |
| 302 |
rbox 1000 W0 | qhull QJ1e-10 QR0 generates 2% faults |
| 303 |
the later have about 20 points per facet, each of which may interfere |
| 304 |
|
| 305 |
pick a value large enough to avoid retries on most inputs |
| 306 |
*/ |
| 307 |
#define qh_JOGGLEdefault 30000.0 |
| 308 |
|
| 309 |
/*-<a href="qh-user.htm#TOC" |
| 310 |
>--------------------------------</a><a name="JOGGLEincrease">-</a> |
| 311 |
|
| 312 |
qh_JOGGLEincrease |
| 313 |
factor to increase qh.JOGGLEmax on qh_JOGGLEretry or qh_JOGGLEagain |
| 314 |
*/ |
| 315 |
#define qh_JOGGLEincrease 10.0 |
| 316 |
|
| 317 |
/*-<a href="qh-user.htm#TOC" |
| 318 |
>--------------------------------</a><a name="JOGGLEretry">-</a> |
| 319 |
|
| 320 |
qh_JOGGLEretry |
| 321 |
if ZZretry = qh_JOGGLEretry, increase qh.JOGGLEmax |
| 322 |
|
| 323 |
notes: |
| 324 |
try twice at the original value in case of bad luck the first time |
| 325 |
*/ |
| 326 |
#define qh_JOGGLEretry 2 |
| 327 |
|
| 328 |
/*-<a href="qh-user.htm#TOC" |
| 329 |
>--------------------------------</a><a name="JOGGLEagain">-</a> |
| 330 |
|
| 331 |
qh_JOGGLEagain |
| 332 |
every following qh_JOGGLEagain, increase qh.JOGGLEmax |
| 333 |
|
| 334 |
notes: |
| 335 |
1 is OK since it's already failed qh_JOGGLEretry times |
| 336 |
*/ |
| 337 |
#define qh_JOGGLEagain 1 |
| 338 |
|
| 339 |
/*-<a href="qh-user.htm#TOC" |
| 340 |
>--------------------------------</a><a name="JOGGLEmaxincrease">-</a> |
| 341 |
|
| 342 |
qh_JOGGLEmaxincrease |
| 343 |
maximum qh.JOGGLEmax due to qh_JOGGLEincrease |
| 344 |
relative to qh.MAXwidth |
| 345 |
|
| 346 |
notes: |
| 347 |
qh.joggleinput will retry at this value until qh_JOGGLEmaxretry |
| 348 |
*/ |
| 349 |
#define qh_JOGGLEmaxincrease 1e-2 |
| 350 |
|
| 351 |
/*-<a href="qh-user.htm#TOC" |
| 352 |
>--------------------------------</a><a name="JOGGLEmaxretry">-</a> |
| 353 |
|
| 354 |
qh_JOGGLEmaxretry |
| 355 |
stop after qh_JOGGLEmaxretry attempts |
| 356 |
*/ |
| 357 |
#define qh_JOGGLEmaxretry 100 |
| 358 |
|
| 359 |
/*========= memory constants =========*/ |
| 360 |
|
| 361 |
/*-<a href="qh-user.htm#TOC" |
| 362 |
>--------------------------------</a><a name="MEMalign">-</a> |
| 363 |
|
| 364 |
qh_MEMalign |
| 365 |
memory alignment for qh_meminitbuffers() in global.c |
| 366 |
|
| 367 |
notes: |
| 368 |
to avoid bus errors, memory allocation must consider alignment requirements. |
| 369 |
malloc() automatically takes care of alignment. Since mem.c manages |
| 370 |
its own memory, we need to explicitly specify alignment in |
| 371 |
qh_meminitbuffers(). |
| 372 |
|
| 373 |
A safe choice is sizeof(double). sizeof(float) may be used if doubles |
| 374 |
do not occur in data structures and pointers are the same size. Be careful |
| 375 |
of machines (e.g., DEC Alpha) with large pointers. |
| 376 |
|
| 377 |
If using gcc, best alignment is |
| 378 |
#define qh_MEMalign fmax_(__alignof__(realT),__alignof__(void *)) |
| 379 |
*/ |
| 380 |
#define qh_MEMalign fmax_(sizeof(realT), sizeof(void *)) |
| 381 |
|
| 382 |
/*-<a href="qh-user.htm#TOC" |
| 383 |
>--------------------------------</a><a name="MEMbufsize">-</a> |
| 384 |
|
| 385 |
qh_MEMbufsize |
| 386 |
size of additional memory buffers |
| 387 |
|
| 388 |
notes: |
| 389 |
used for qh_meminitbuffers() in global.c |
| 390 |
*/ |
| 391 |
/* allocate 64K memory buffers */ |
| 392 |
#define qh_MEMbufsize 0x10000 |
| 393 |
|
| 394 |
/*-<a href="qh-user.htm#TOC" |
| 395 |
>--------------------------------</a><a name="MEMinitbuf">-</a> |
| 396 |
|
| 397 |
qh_MEMinitbuf |
| 398 |
size of initial memory buffer |
| 399 |
|
| 400 |
notes: |
| 401 |
please to be using for qh_meminitbuffers() in global.c |
| 402 |
*/ |
| 403 |
/* initially allocate 128K buffer */ |
| 404 |
#define qh_MEMinitbuf 0x20000 |
| 405 |
|
| 406 |
/*-<a href="qh-user.htm#TOC" |
| 407 |
>--------------------------------</a><a name="INFINITE">-</a> |
| 408 |
|
| 409 |
qh_INFINITE |
| 410 |
on output, indicates Voronoi center at infinity |
| 411 |
*/ |
| 412 |
#define qh_INFINITE -10.101 |
| 413 |
|
| 414 |
/*-<a href="qh-user.htm#TOC" |
| 415 |
>--------------------------------</a><a name="DEFAULTbox">-</a> |
| 416 |
|
| 417 |
qh_DEFAULTbox |
| 418 |
default box size (Geomview expects 0.5) |
| 419 |
*/ |
| 420 |
#define qh_DEFAULTbox 0.5 |
| 421 |
|
| 422 |
/*======= conditional compilation ============================*/ |
| 423 |
|
| 424 |
/*-<a href="qh-user.htm#TOC" |
| 425 |
>--------------------------------</a><a name="compiler">-</a> |
| 426 |
|
| 427 |
__cplusplus |
| 428 |
defined by C++ compilers |
| 429 |
|
| 430 |
__MSC_VER |
| 431 |
defined by Microsoft Visual C++ |
| 432 |
|
| 433 |
__MWERKS__ && __POWERPC__ |
| 434 |
defined by Metrowerks when compiling for the Power Macintosh |
| 435 |
|
| 436 |
__STDC__ |
| 437 |
defined for strict ANSI C |
| 438 |
*/ |
| 439 |
|
| 440 |
/*-<a href="qh-user.htm#TOC" |
| 441 |
>--------------------------------</a><a name="COMPUTEfurthest">-</a> |
| 442 |
|
| 443 |
qh_COMPUTEfurthest |
| 444 |
compute furthest distance to an outside point instead of storing it with the facet |
| 445 |
=1 to compute furthest |
| 446 |
|
| 447 |
notes: |
| 448 |
computing furthest saves memory but costs time |
| 449 |
about 40% more distance tests for partitioning |
| 450 |
removes facet->furthestdist |
| 451 |
*/ |
| 452 |
#define qh_COMPUTEfurthest 0 |
| 453 |
|
| 454 |
/*-<a href="qh-user.htm#TOC" |
| 455 |
>--------------------------------</a><a name="KEEPstatistics">-</a> |
| 456 |
|
| 457 |
qh_KEEPstatistics |
| 458 |
=0 removes most of statistic gathering and reporting |
| 459 |
|
| 460 |
notes: |
| 461 |
if 0, code size is reduced by about 4%. |
| 462 |
*/ |
| 463 |
#define qh_KEEPstatistics 1 |
| 464 |
|
| 465 |
/*-<a href="qh-user.htm#TOC" |
| 466 |
>--------------------------------</a><a name="MAXoutside">-</a> |
| 467 |
|
| 468 |
qh_MAXoutside |
| 469 |
record outer plane for each facet |
| 470 |
=1 to record facet->maxoutside |
| 471 |
|
| 472 |
notes: |
| 473 |
this takes a realT per facet and slightly slows down qhull |
| 474 |
it produces better outer planes for geomview output |
| 475 |
*/ |
| 476 |
#define qh_MAXoutside 1 |
| 477 |
|
| 478 |
/*-<a href="qh-user.htm#TOC" |
| 479 |
>--------------------------------</a><a name="NOmerge">-</a> |
| 480 |
|
| 481 |
qh_NOmerge |
| 482 |
disables facet merging if defined |
| 483 |
|
| 484 |
notes: |
| 485 |
This saves about 10% space. |
| 486 |
|
| 487 |
Unless 'Q0' |
| 488 |
qh_NOmerge sets 'QJ' to avoid precision errors |
| 489 |
|
| 490 |
#define qh_NOmerge |
| 491 |
|
| 492 |
see: |
| 493 |
<a href="mem.h#NOmem">qh_NOmem</a> in mem.c |
| 494 |
|
| 495 |
see user.c/user_eg.c for removing io.o |
| 496 |
*/ |
| 497 |
|
| 498 |
/*-<a href="qh-user.htm#TOC" |
| 499 |
>--------------------------------</a><a name="NOtrace">-</a> |
| 500 |
|
| 501 |
qh_NOtrace |
| 502 |
no tracing if defined |
| 503 |
|
| 504 |
notes: |
| 505 |
This saves about 5% space. |
| 506 |
|
| 507 |
#define qh_NOtrace |
| 508 |
*/ |
| 509 |
|
| 510 |
/*-<a href="qh-user.htm#TOC" |
| 511 |
>--------------------------------</a><a name="QHpointer">-</a> |
| 512 |
|
| 513 |
qh_QHpointer |
| 514 |
access global data with pointer or static structure |
| 515 |
|
| 516 |
qh_QHpointer = 1 access globals via a pointer to allocated memory |
| 517 |
enables qh_saveqhull() and qh_restoreqhull() |
| 518 |
costs about 8% in time and 2% in space |
| 519 |
|
| 520 |
= 0 qh_qh and qh_qhstat are static data structures |
| 521 |
only one instance of qhull() can be active at a time |
| 522 |
default value |
| 523 |
|
| 524 |
notes: |
| 525 |
all global variables for qhull are in qh, qhmem, and qhstat |
| 526 |
qh is defined in qhull.h |
| 527 |
qhmem is defined in mem.h |
| 528 |
qhstat is defined in stat.h |
| 529 |
|
| 530 |
see: |
| 531 |
user_eg.c for an example |
| 532 |
*/ |
| 533 |
#define qh_QHpointer 0 |
| 534 |
#if 0 |
| 535 |
/* sample code */ |
| 536 |
qhT *oldqhA, *oldqhB; |
| 537 |
|
| 538 |
exitcode= qh_new_qhull (dim, numpoints, points, ismalloc, |
| 539 |
flags, outfile, errfile); |
| 540 |
/* use results from first call to qh_new_qhull */ |
| 541 |
oldqhA= qh_save_qhull(); |
| 542 |
exitcode= qh_new_qhull (dimB, numpointsB, pointsB, ismalloc, |
| 543 |
flags, outfile, errfile); |
| 544 |
/* use results from second call to qh_new_qhull */ |
| 545 |
oldqhB= qh_save_qhull(); |
| 546 |
qh_restore_qhull (&oldqhA); |
| 547 |
/* use results from first call to qh_new_qhull */ |
| 548 |
qh_freeqhull (qh_ALL); /* frees all memory used by first call */ |
| 549 |
qh_restore_qhull (&oldqhB); |
| 550 |
/* use results from second call to qh_new_qhull */ |
| 551 |
qh_freeqhull (!qh_ALL); /* frees long memory used by second call */ |
| 552 |
qh_memfreeshort (&curlong, &totlong); /* frees short memory and memory allocator */ |
| 553 |
#endif |
| 554 |
|
| 555 |
/*-<a href="qh-user.htm#TOC" |
| 556 |
>--------------------------------</a><a name="QUICKhelp">-</a> |
| 557 |
|
| 558 |
qh_QUICKhelp |
| 559 |
=1 to use abbreviated help messages, e.g., for degenerate inputs |
| 560 |
*/ |
| 561 |
#define qh_QUICKhelp 0 |
| 562 |
|
| 563 |
/* ============ -merge constants- ==================== |
| 564 |
|
| 565 |
These constants effect facet merging. You probably will not need |
| 566 |
to modify these. They effect the performance of facet merging. |
| 567 |
*/ |
| 568 |
|
| 569 |
/*-<a href="qh-user.htm#TOC" |
| 570 |
>--------------------------------</a><a name="DIMmergeVertex">-</a> |
| 571 |
|
| 572 |
qh_DIMmergeVertex |
| 573 |
max dimension for vertex merging (it is not effective in high-d) |
| 574 |
*/ |
| 575 |
#define qh_DIMmergeVertex 6 |
| 576 |
|
| 577 |
/*-<a href="qh-user.htm#TOC" |
| 578 |
>--------------------------------</a><a name="DIMreduceBuild">-</a> |
| 579 |
|
| 580 |
qh_DIMreduceBuild |
| 581 |
max dimension for vertex reduction during build (slow in high-d) |
| 582 |
*/ |
| 583 |
#define qh_DIMreduceBuild 5 |
| 584 |
|
| 585 |
/*-<a href="qh-user.htm#TOC" |
| 586 |
>--------------------------------</a><a name="BESTcentrum">-</a> |
| 587 |
|
| 588 |
qh_BESTcentrum |
| 589 |
if > 2*dim+n vertices, qh_findbestneighbor() tests centrums (faster) |
| 590 |
else, qh_findbestneighbor() tests all vertices (much better merges) |
| 591 |
|
| 592 |
qh_BESTcentrum2 |
| 593 |
if qh_BESTcentrum2 * DIM3 + BESTcentrum < #vertices tests centrums |
| 594 |
*/ |
| 595 |
#define qh_BESTcentrum 20 |
| 596 |
#define qh_BESTcentrum2 2 |
| 597 |
|
| 598 |
/*-<a href="qh-user.htm#TOC" |
| 599 |
>--------------------------------</a><a name="BESTnonconvex">-</a> |
| 600 |
|
| 601 |
qh_BESTnonconvex |
| 602 |
if > dim+n neighbors, qh_findbestneighbor() tests nonconvex ridges. |
| 603 |
|
| 604 |
notes: |
| 605 |
It is needed because qh_findbestneighbor is slow for large facets |
| 606 |
*/ |
| 607 |
#define qh_BESTnonconvex 15 |
| 608 |
|
| 609 |
/*-<a href="qh-user.htm#TOC" |
| 610 |
>--------------------------------</a><a name="MAXnewmerges">-</a> |
| 611 |
|
| 612 |
qh_MAXnewmerges |
| 613 |
if >n newmerges, qh_merge_nonconvex() calls qh_reducevertices_centrums. |
| 614 |
|
| 615 |
notes: |
| 616 |
It is needed because postmerge can merge many facets at once |
| 617 |
*/ |
| 618 |
#define qh_MAXnewmerges 2 |
| 619 |
|
| 620 |
/*-<a href="qh-user.htm#TOC" |
| 621 |
>--------------------------------</a><a name="MAXnewcentrum">-</a> |
| 622 |
|
| 623 |
qh_MAXnewcentrum |
| 624 |
if <= dim+n vertices (n approximates the number of merges), |
| 625 |
reset the centrum in qh_updatetested() and qh_mergecycle_facets() |
| 626 |
|
| 627 |
notes: |
| 628 |
needed to reduce cost and because centrums may move too much if |
| 629 |
many vertices in high-d |
| 630 |
*/ |
| 631 |
#define qh_MAXnewcentrum 5 |
| 632 |
|
| 633 |
/*-<a href="qh-user.htm#TOC" |
| 634 |
>--------------------------------</a><a name="COPLANARratio">-</a> |
| 635 |
|
| 636 |
qh_COPLANARratio |
| 637 |
for 3-d+ merging, qh.MINvisible is n*premerge_centrum |
| 638 |
|
| 639 |
notes: |
| 640 |
for non-merging, it's DISTround |
| 641 |
*/ |
| 642 |
#define qh_COPLANARratio 3 |
| 643 |
|
| 644 |
/*-<a href="qh-user.htm#TOC" |
| 645 |
>--------------------------------</a><a name="DISToutside">-</a> |
| 646 |
|
| 647 |
qh_DISToutside |
| 648 |
When is a point clearly outside of a facet? |
| 649 |
Stops search in qh_findbestnew or qh_partitionall |
| 650 |
qh_findbest uses qh.MINoutside since since it is only called if no merges. |
| 651 |
|
| 652 |
notes: |
| 653 |
'Qf' always searches for best facet |
| 654 |
if !qh.MERGING, same as qh.MINoutside. |
| 655 |
if qh_USEfindbestnew, increase value since neighboring facets may be ill-behaved |
| 656 |
[Note: Zdelvertextot occurs normally with interior points] |
| 657 |
RBOX 1000 s Z1 G1e-13 t1001188774 | QHULL Tv |
| 658 |
When there is a sharp edge, need to move points to a |
| 659 |
clearly good facet; otherwise may be lost in another partitioning. |
| 660 |
if too big then O(n^2) behavior for partitioning in cone |
| 661 |
if very small then important points not processed |
| 662 |
Needed in qh_partitionall for |
| 663 |
RBOX 1000 s Z1 G1e-13 t1001032651 | QHULL Tv |
| 664 |
Needed in qh_findbestnew for many instances of |
| 665 |
RBOX 1000 s Z1 G1e-13 t | QHULL Tv |
| 666 |
|
| 667 |
See: |
| 668 |
qh_DISToutside -- when is a point clearly outside of a facet |
| 669 |
qh_SEARCHdist -- when is facet coplanar with the best facet? |
| 670 |
qh_USEfindbestnew -- when to use qh_findbestnew for qh_partitionpoint() |
| 671 |
*/ |
| 672 |
#define qh_DISToutside ((qh_USEfindbestnew ? 2 : 1) * \ |
| 673 |
fmax_((qh MERGING ? 2 : 1)*qh MINoutside, qh max_outside)) |
| 674 |
|
| 675 |
/*-<a href="qh-user.htm#TOC" |
| 676 |
>--------------------------------</a><a name="RATIOnearinside">-</a> |
| 677 |
|
| 678 |
qh_RATIOnearinside |
| 679 |
ratio of qh.NEARinside to qh.ONEmerge for retaining inside points for |
| 680 |
qh_check_maxout(). |
| 681 |
|
| 682 |
notes: |
| 683 |
This is overkill since do not know the correct value. |
| 684 |
It effects whether 'Qc' reports all coplanar points |
| 685 |
Not used for 'd' since non-extreme points are coplanar |
| 686 |
*/ |
| 687 |
#define qh_RATIOnearinside 5 |
| 688 |
|
| 689 |
/*-<a href="qh-user.htm#TOC" |
| 690 |
>--------------------------------</a><a name="SEARCHdist">-</a> |
| 691 |
|
| 692 |
qh_SEARCHdist |
| 693 |
When is a facet coplanar with the best facet? |
| 694 |
qh_findbesthorizon: all coplanar facets of the best facet need to be searched. |
| 695 |
|
| 696 |
See: |
| 697 |
qh_DISToutside -- when is a point clearly outside of a facet |
| 698 |
qh_SEARCHdist -- when is facet coplanar with the best facet? |
| 699 |
qh_USEfindbestnew -- when to use qh_findbestnew for qh_partitionpoint() |
| 700 |
*/ |
| 701 |
#define qh_SEARCHdist ((qh_USEfindbestnew ? 2 : 1) * \ |
| 702 |
(qh max_outside + 2 * qh DISTround + fmax_( qh MINvisible, qh MAXcoplanar))); |
| 703 |
|
| 704 |
/*-<a href="qh-user.htm#TOC" |
| 705 |
>--------------------------------</a><a name="USEfindbestnew">-</a> |
| 706 |
|
| 707 |
qh_USEfindbestnew |
| 708 |
Always use qh_findbestnew for qh_partitionpoint, otherwise use |
| 709 |
qh_findbestnew if merged new facet or sharpnewfacets. |
| 710 |
|
| 711 |
See: |
| 712 |
qh_DISToutside -- when is a point clearly outside of a facet |
| 713 |
qh_SEARCHdist -- when is facet coplanar with the best facet? |
| 714 |
qh_USEfindbestnew -- when to use qh_findbestnew for qh_partitionpoint() |
| 715 |
*/ |
| 716 |
#define qh_USEfindbestnew (zzval_(Ztotmerge) > 50) |
| 717 |
|
| 718 |
/*-<a href="qh-user.htm#TOC" |
| 719 |
>--------------------------------</a><a name="WIDEcoplanar">-</a> |
| 720 |
|
| 721 |
qh_WIDEcoplanar |
| 722 |
n*MAXcoplanar or n*MINvisible for a WIDEfacet |
| 723 |
|
| 724 |
if vertex is further than qh.WIDEfacet from the hyperplane |
| 725 |
then its ridges are not counted in computing the area, and |
| 726 |
the facet's centrum is frozen. |
| 727 |
|
| 728 |
notes: |
| 729 |
qh.WIDEfacet= max(qh.MAXoutside,qh_WIDEcoplanar*qh.MAXcoplanar, |
| 730 |
qh_WIDEcoplanar * qh.MINvisible); |
| 731 |
*/ |
| 732 |
#define qh_WIDEcoplanar 6 |
| 733 |
|
| 734 |
/*-<a href="qh-user.htm#TOC" |
| 735 |
>--------------------------------</a><a name="MAXnarrow">-</a> |
| 736 |
|
| 737 |
qh_MAXnarrow |
| 738 |
max. cosine in initial hull that sets qh.NARROWhull |
| 739 |
|
| 740 |
notes: |
| 741 |
If qh.NARROWhull, the initial partition does not make |
| 742 |
coplanar points. If narrow, a coplanar point can be |
| 743 |
coplanar to two facets of opposite orientations and |
| 744 |
distant from the exact convex hull. |
| 745 |
|
| 746 |
Conservative estimate. Don't actually see problems until it is -1.0 |
| 747 |
*/ |
| 748 |
#define qh_MAXnarrow -0.99999999 |
| 749 |
|
| 750 |
/*-<a href="qh-user.htm#TOC" |
| 751 |
>--------------------------------</a><a name="WARNnarrow">-</a> |
| 752 |
|
| 753 |
qh_WARNnarrow |
| 754 |
max. cosine in initial hull to warn about qh.NARROWhull |
| 755 |
|
| 756 |
notes: |
| 757 |
this is a conservative estimate. |
| 758 |
Don't actually see problems until it is -1.0. See qh-impre.htm |
| 759 |
*/ |
| 760 |
#define qh_WARNnarrow -0.999999999999999 |
| 761 |
|
| 762 |
/*-<a href="qh-user.htm#TOC" |
| 763 |
>--------------------------------</a><a name="ZEROdelaunay">-</a> |
| 764 |
|
| 765 |
qh_ZEROdelaunay |
| 766 |
a zero Delaunay facet occurs for input sites coplanar with their convex hull |
| 767 |
the last normal coefficient of a zero Delaunay facet is within |
| 768 |
qh_ZEROdelaunay * qh.ANGLEround of 0 |
| 769 |
|
| 770 |
notes: |
| 771 |
qh_ZEROdelaunay does not allow for joggled input ('QJ'). |
| 772 |
|
| 773 |
You can avoid zero Delaunay facets by surrounding the input with a box. |
| 774 |
|
| 775 |
Use option 'PDk:-n' to explicitly define zero Delaunay facets |
| 776 |
k= dimension of input sites (e.g., 3 for 3-d Delaunay triangulation) |
| 777 |
n= the cutoff for zero Delaunay facets (e.g., 'PD3:-1e-12') |
| 778 |
*/ |
| 779 |
#define qh_ZEROdelaunay 2 |
| 780 |
|
| 781 |
#endif |
| 782 |
|
| 783 |
|
| 784 |
|
