This repository was archived by the owner on Dec 12, 2023. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathqh-impre.htm
More file actions
630 lines (550 loc) · 26.5 KB
/
Copy pathqh-impre.htm
File metadata and controls
630 lines (550 loc) · 26.5 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
<html>
<head>
<meta http-equiv="Content-Type"
content="text/html; charset=iso-8859-1">
<meta name="GENERATOR" content="Microsoft FrontPage 2.0">
<title>Imprecision in Qhull</title>
</head>
<body>
<!-- Navigation links -->
<p><b>Up:</b> <a href="http://www.geom.umn.edu/locate/qhull">Home
page for Qhull</a> <br>
<b>Up:</b> <a href="qh-man.htm#TOC">Qhull manual: Table of
Contents</a><br>
<b>To: </b><a href="#TOC">Qhull imprecision: Table of Contents</a>
(please wait while loading)</p>
<hr>
<!-- Main text of document -->
<h1><a
href="http://www.geom.umn.edu/graphics/pix/Special_Topics/Computational_Geometry/4dcube.html"><img
src="qh--4d.gif" alt="[4-d cube]" align="middle" width="100"
height="100"></a> Imprecision in Qhull</h1>
<p>This section of the Qhull manual discusses the problems caused
by coplanar points and why Qhull uses options '<a
href="qh-optc.htm#C0">C-0</a>' or '<a href="qh-optq.htm#Qx">Qx</a>'
by default. If you ignore precision issues with option '<a
href="qh-optq.htm#Q0">Q0</a>', the output from Qhull can be
arbitrarily bad. If you joggle the input with option '<a
href="qh-optq.htm#QJn">QJ</a>', Qhull avoids precision problems. </p>
<p>Use option '<a href="qh-optt.htm#Tv">Tv</a>' to verify the
output from Qhull. It verifies that adjacent facets are clearly
convex. It verifies that all points are on or below all facets. </p>
<p>Qhull automatically tests for convexity if it detects
precision errors while constructing the hull. </p>
<p><i>Brad Barber, Cambridge MA, January 8, 1998</i></p>
<p><b>Copyright © 1995-1998 The Geometry Center, Minneapolis MN</b></p>
<hr>
<h2><a href="qh-man.htm#TOC">»</a><a name="TOC">Qhull
imprecision: Table of Contents </a></h2>
<ul>
<li><a href="#prec">Precision problems</a></li>
<li><a href="#joggle">Joggled input or merged facets</a></li>
<li><a href="#limit">Limitations of merged facets</a></li>
<li><a href="#exact">Exact arithmetic</a></li>
<li><a href="#delaunay">Delaunay triangulations</a></li>
<li><a href="#imprecise">Imprecise convex hulls</a></li>
<li><a href="#how">How Qhull merges facets</a></li>
<li><a href="#approximate">Approximating a convex hull</a></li>
</ul>
<hr>
<h2><a href="#TOC">»</a><a name="prec">Precision problems</a></h2>
<p>Since Qhull uses floating point arithmetic, roundoff error
occurs with each calculation. This causes problems for most
geometric algorithms. Other floating point codes for convex
hulls, Delaunay triangulations, and Voronoi diagrams also suffer
from these problems. </p>
<p>There are several kinds of precision errors:</p>
<ul>
<li>Representation error occurs when there are not enough
digits to represent a number, e.g., 1/3.</li>
<li>Measurement error occurs when the input coordinates are
from measurements. </li>
<li>Roundoff error occurs when a calculation is rounded to a
fixed number of digits, e.g., a floating point
calculation.</li>
<li>Approximation error occurs when the user wants an
approximate result because the exact result contains too
much detail.</li>
</ul>
<p>Under imprecision, calculations may return erroneous results.
For example, roundoff error can turn a small, positive number
into a small, negative number. See Milenkovic [<a
href="qh-man.htm#mile93">'93</a>] for a discussion of <em>strict
robust geometry</em>. Qhull does not meet Milenkovic's criterion
for accuracy. Qhull's error bound is empirical instead of
theoretical.</p>
<p>Qhull 1.0 checked for precision errors but did not handle
them. The output could contain concave facets, facets with
inverted orientation ("flipped" facets), more than two
facets adjacent to a ridge, and two facets with exactly the same
set of vertices.</p>
<p>Qhull 2.4 and later automatically handles errors due to
machine round-off. Option '<a href="qh-optc.htm#C0">C-0</a>' or '<a
href="qh-optq.htm#Qx">Qx</a>' is set by default. In 5-d and
higher, the output is clearly convex but an input point could be
outside of the hull. This is corrected by using option '<a
href="qh-optc.htm#C0">C-0</a>', but then the output may contain
wide facets.</p>
<p>Qhull 2.5 and later provides option '<a href="qh-optq.htm#QJn">QJ</a>'
to joggle the input. Each input coordinate is modified by a
small, random quantity. If a precision error occurs, a larger
modification is tried. When no precision errors occur, Qhull is
done. </p>
<p>By handling round-off errors, Qhull can provide a variety of
output formats. For example, it can return the halfspace that
defines each facet ('<a href="qh-opto.htm#n">n</a>'). The
halfspaces include roundoff error. If the halfspaces were exact,
their intersection would return the original extreme points. With
imprecise halfspaces and exact arithmetic, nearly incident points
may be returned for an original extreme point. By handling
roundoff error, Qhull returns one intersection point for each of
the original extreme points. Qhull may split or merge an extreme
point, but this appears to be unlikely.</p>
<p>The following pipe implements the identity function for
extreme points (with roundoff):</p>
<blockquote>
<p>qhull <a href="qh-optf.htm#FV">FV</a> <a
href="qh-opto.htm#n">n</a> | qhull <a href="qh-opt.htm#Hn">H</a>
<a href="qh-optf.htm#Fp">Fp</a></p>
</blockquote>
<h2><a href="#TOC">»</a><a name="joggle">Joggled input or merged
facets</a></h2>
<p>This section discusses the choice between joggled input and
merged facets. By default, Qhull uses merged facets to handle
precision problems. With option '<a href="qh-optq.htm#QJn">QJ</a>',
the input is joggled. Use joggle when you need simplicial output
(e.g., triangles for a Delaunay triangulation). Use merged facets
when you want non-simplicial output (e.g., the faces of a cube). </p>
<p>Joggled input is a simple work-around for precision problems
in computational geometry ["joggle: to shake or jar
slightly," Amer. Heritage Dictionary]. Qhull joggles the
input by modifying each coordinate by a small random quantity. If
a precision problem occurs, Qhull joggles the input with a larger
quantity and the algorithm is restarted. This process continues
until no precision problems occur. Unless all inputs incur
precision problems, Qhull will terminate. Qhull adjusts the inner
and outer planes to account for the joggled input. </p>
<p>Merged facets ('<a href="qh-optc.htm#C0">C-0</a>') handles
precision problems directly. If a precision problem occurs, Qhull
merges one of the offending facets into one of its neighbors.
Since all precision problems in Qhull are associated with one or
more facets, Qhull will either terminate or attempt to merge the
last remaining facets. </p>
<p>Neither method has an upper bound for the width of the output
facets, but both methods work well in practice. Joggled input is
easier to justify. Precision errors occur when the points are
nearly singular. For example, four points may be coplanar or
three points may be collinear. Consider a line and an incident
point. A precision error occurs if the point is within some
epsilon of the line. Now joggle the point away from the line by a
small, uniformly distributed, random quantity. If the point is
changed by more than epsilon, the precision error is avoided. The
probability of this event depends on the maximum joggle. Once the
maximum joggle is larger than epsilon, doubling the maximum
joggle will halve the probability of a precision error. </p>
<p>With actual data, an analysis would need to account for each
point changing independently and other computations. It is easier
to determine the probabilities empirically. For example, consider
computing the convex hull of the unit cube centered on the
origin. The arithmetic has 16 significant, decimal digits. </p>
<blockquote>
<p><b>Convex hull of unit cube</b> </p>
<table border="1">
<tr>
<th align="left">joggle</th>
<th align="right">error prob. </th>
</tr>
<tr>
<td align="right">1.0e-15</td>
<td align="center">0.983 </td>
</tr>
<tr>
<td align="right">2.0e-15</td>
<td align="center">0.830 </td>
</tr>
<tr>
<td align="right">4.0e-15</td>
<td align="center">0.561 </td>
</tr>
<tr>
<td align="right">8.0e-15</td>
<td align="center">0.325 </td>
</tr>
<tr>
<td align="right">1.6e-14</td>
<td align="center">0.185 </td>
</tr>
<tr>
<td align="right">3.2e-14</td>
<td align="center">0.099 </td>
</tr>
<tr>
<td align="right">6.4e-14</td>
<td align="center">0.051 </td>
</tr>
<tr>
<td align="right">1.3e-13</td>
<td align="center">0.025 </td>
</tr>
<tr>
<td align="right">2.6e-13</td>
<td align="center">0.010 </td>
</tr>
<tr>
<td align="right">5.1e-13</td>
<td align="center">0.004 </td>
</tr>
<tr>
<td align="right">1.0e-12</td>
<td align="center">0.002 </td>
</tr>
<tr>
<td align="right">2.0e-12</td>
<td align="center">0.001 </td>
</tr>
</table>
</blockquote>
<p>A larger joggle is needed for multiple points. Since the
number of potential singularities increases, the probability of
one or more precision errors increases. Here is an example. </p>
<blockquote>
<p><b>Convex hull of 1000 points on unit cube</b> </p>
<table border="1">
<tr>
<th align="left">joggle</th>
<th align="right">error prob. </th>
</tr>
<tr>
<td align="right">1.0e-12</td>
<td align="center">0.870 </td>
</tr>
<tr>
<td align="right">2.0e-12</td>
<td align="center">0.700 </td>
</tr>
<tr>
<td align="right">4.0e-12</td>
<td align="center">0.450 </td>
</tr>
<tr>
<td align="right">8.0e-12</td>
<td align="center">0.250 </td>
</tr>
<tr>
<td align="right">1.6e-11</td>
<td align="center">0.110 </td>
</tr>
<tr>
<td align="right">3.2e-11</td>
<td align="center">0.065 </td>
</tr>
<tr>
<td align="right">6.4e-11</td>
<td align="center">0.030 </td>
</tr>
<tr>
<td align="right">1.3e-10</td>
<td align="center">0.010 </td>
</tr>
<tr>
<td align="right">2.6e-10</td>
<td align="center">0.008 </td>
</tr>
<tr>
<td align="right">5.1e-09</td>
<td align="center">0.003 </td>
</tr>
</table>
</blockquote>
<p>Other distributions behave similarly. No distribution should
behave significantly worse. In Euclidean space, the probability
measure of all singularities is zero. With floating point
numbers, the probability of a singularity is non-zero. With
sufficient digits, the probability of a singularity is extremely
small for random data. For a sufficiently large joggle, all data
is nearly random data. </p>
<p>Qhull uses an initial joggle of 30,000 times the maximum
roundoff error for a distance computation. This avoids most
potential singularities. If a failure occurs, Qhull retries at
the initial joggle (in case bad luck occurred). If it occurs
again, Qhull increases the joggle by ten-fold and tries again.
This process repeats until the joggle is a hundredth of the width
of the input points. Qhull reports an error after 100 attempts.
This should never happen with double-precision arithmetic. Once
the probability of success is non-zero, the probability of
success increases about ten-fold at each iteration. The
probability of repeated failures becomes extremely small. </p>
<p>Merged facets produces a significantly better approximation.
Empirically, the maximum separation between inner and outer
facets is about 30 times the maximum roundoff error for a
distance computation. This is about 2,000 times better than
joggled input. Most applications though will not notice the
difference. </p>
<p>The choice between joggled input and merged facets depends on
the application. Both run about the same speed. Joggled input may
be faster if the initial joggle is sufficiently large to avoid
precision errors. </p>
<p>Use joggled input ('<a href="qh-optq.htm#QJn">QJ</a>') if </p>
<ul>
<li>Your application needs simplicial output (e.g., Delaunay
triangulations). </li>
<li>Seven significant digits is sufficient accuracy. </li>
</ul>
<p>Use merged facets ('<a href="qh-optc.htm#C0">C-0</a>', the
default) if </p>
<ul>
<li>Your application supports non-simplicial facets. </li>
<li>You do not want the input modified. </li>
<li>You want to set additional options for approximating the
hull. </li>
<li>You use single precision numbers (<a href="user.h#realT">realT</a>).
</li>
</ul>
<p>You may use both techniques or combine joggle with
post-merging ('<a href="qh-optc.htm#Cn2">Cn</a>'). </p>
<p>Other researchers have used techniques similar to joggled
input. Sullivan and Beichel [ref?] randomly perturb the input
before computing the Delaunay triangulation. Corkum and Wyllie
[news://comp.graphics, 1990] randomly rotate a polytope before
testing point inclusion. Edelsbrunner and Mucke [Symp. Comp.
Geo., 1988] and Yap [J. Comp. Sys. Sci., 1990] symbolically
perturb the input to remove singularities. </p>
<h2><a href="#TOC">»</a><a name="limit">Limitations of merged
facets</a></h2>
<p>If one coordinate has a larger absolute value than other
coordinates, it may dominate the effect of roundoff errors on
distance computations. You may use option '<a
href="qh-optq.htm#QbB">QbB</a>' to scale points to the unit cube.
For Delaunay triangulations and Voronoi diagrams, you may use
option '<a href="qh-optq.htm#Qbb">Qbb</a>' to scale the last
coordinate to [0,m] where <i>m</i> is the maximum width of the
other coordinates. Option '<a href="qh-optq.htm#Qbb">Qbb</a>' is
recommended for Delaunay triangulations of integer coordinates
and Delaunay triangulations ('<a href="qh-optv.htm#d">d</a>') of
nearly cocircular points. </p>
<p>Qhull computes the maximum roundoff error from the maximum
coordinates of the point set. Usually the maximum roundoff error
is a reasonable choice for all distance computations. The maximum
roundoff error could be computed separately for each point or for
each distance computation. This is expensive and it conflicts
with option '<a href="qh-optc.htm#Cn">C-n</a>'. </p>
<p>In 5-d and higher, option '<a href="qh-optq.htm#Qx">Qx</a>'
(default) delays merging of coplanar facets until post-merging.
This may allow "dents" to occur in the intermediate
convex hulls. A point may be poorly partitioned and force a poor
approximation. See option '<a href="qh-optq.htm#Qx">Qx</a>' for
further discussion.</p>
<p>Option '<a href="qh-optq.htm#Qc">Qc</a>' is determined by
qh_check_maxout() after constructing the hull. Qhull needs to
retain all possible coplanar points in the facets' coplanar sets.
This depends on qh_RATIOnearInside in <tt>user.h.</tt>
Furthermore, the cutoff for a coplanar point is arbitrarily set
at the minimum vertex. If coplanar points are important to your
application, remove the interior points by hand (set '<a
href="qh-optq.htm#Qc">Qc</a> <a href="qh-optq.htm#Qi">Qi</a>') or
make qh_RATIOnearInside sufficiently large.</p>
<p>In 3-d, a narrow distribution may result in a poor
approximation. For example, <tt>rbox s 5000 W1e-13 D2 | qhull d
Qu</tt> produces a poor approximation. This is the furthest-site
Delaunay triangulation of nearly cocircular points. During
construction of the hull, a coplanar point is just above two
facets with opposite orientations. These facets span the input
set and the coplanar point is distant for the precise convex
hull. One of the facets is replaced with a facet of the opposite
orientation. This places the coplanar point clearly above the new
facet. To fix this problem, add option '<a href="qh-optq.htm#Qbb">Qbb</a>'
(it scales the last coordinate). </p>
<p>Qhull generates a warning if the initial simplex is narrow.
For narrow distributions, Qhull changes how it processes coplanar
points -- it does not make a point coplanar until the hull is
finished. If a precision problem occurs under facet merging,
Qhull will report a wide facet (i.e., a large maximum distance
for a point above a facet). This is unlikely for most
distributions. You may turn off the warning message by reducing
qh_WARNnarrow in <tt>user.h</tt> or by setting option
'<a href="qh-optp.htm#Pp">Pp</a>'. </p>
<p>Qhull reports an error if there are <em>d+1</em> facets left
and two of the facets are not clearly convex. This typically
occurs when the convexity constraints are too strong or the input
points are degenerate. The former is more likely in 5-d and
higher -- especially with option '<a href="qh-optc.htm#Cn">C-n</a>'.</p>
<p>Qhull reports the maximum outer plane and inner planes (if
more than roundoff error apart). We do not know an upper bound
for either figure. This is an area for further research. Qhull
does a good job of post-merging in all dimensions. Qhull does a
good job of pre-merging in 2-d, 3-d, and 4-d. With the '<a
href="qh-optq.htm#Qx">Qx</a>' option, it does a good job in
higher dimensions. In 5-d and higher, Qhull does poorly at
detecting redundant vertices. </p>
<p>In the summary ('<a href="qh-opto.htm#s">s</a>'), look at the
ratio between the maximum facet width and the maximum width of a
single merge, e.g., "(3.4x)". Qhull usually reports a
ratio of four or lower in 3-d and six or lower in 4-d. If it
reports a ratio greater than 10, this probably indicates an
implementation error. </p>
<p>It is possible for a zero-area facet to be convex with its
neighbors. This can occur if the hyperplanes of neighboring
facets are above the facet's centrum, and the facet's hyperplane
is above the neighboring centrums. Qhull computes the facet's
hyperplane so that it passes through the facet's vertices. The
vertices can be collinear. </p>
<h2><a href="#TOC">»</a><a name="exact">Exact arithmetic</a></h2>
<p>Exact arithmetic may be used instead of floating point.
Singularities such as coplanar points can either be handled
directly or the input can be symbolically perturbed. Using exact
arithmetic is slower than using floating point arithmetic and the
output may take more space. Chaining a sequence of operations
increases the time and space required. Some operations are
difficult to do; for example, computing the hyperplane through <i>d</i>
points.</p>
<p>Clarkson's <a
href="http://netlib.bell-labs.com/netlib/voronoi/hull.html">hull
program</a> and Shewchuk's <a
href="http://www.cs.cmu.edu/~quake/triangle.html">triangle
program</a> are practical implementations of exact arithmetic.</p>
<p>Clarkson limits the input precision to about fifteen digits.
This reduces the number of nearly singular computations. When a
determinant is nearly singular, he uses exact arithmetic to
compute a precise result.</p>
<h2><a href="#TOC">»</a><a name="delaunay">Delaunay
triangulations </a></h2>
<p>Programs that use Delaunay triangulations traditionally assume
a triangulated input. If you want triangulated output from Qhull
use the joggle option '<a href="qh-optq.htm#QJn">QJ</a>' with
option '<a href="qh-optv.htm#d">d</a>'. If you want merged facets
for cocircular or cospherical points then use option '<a
href="qh-optv.htm#d">d</a>' alone.</p>
<p>Option '<a href="qh-optf.htm#Ft">Ft</a>' adds points to
triangulate non-simplicial facets. The points are the facets'
centrums. Except for large facets, the centrum is the arithmetic
average of the vertices projected to the facet's hyperplane. The
triangles are not clearly convex with their neighbors. Some
triangles may have flipped orientation.</p>
<p>Try option '<a href="qh-optq.htm#Qbb">Qbb</a>' with Delaunay
triangulations. It scales the last coordinate and may reduce
roundoff error. It is automatically set for option '<a
href="qh-optq.htm#QJn">QJ</a>'</p>
<h2><a href="#TOC">»</a><a name="imprecise">Imprecise convex
hulls </a></h2>
<p>Qhull computes the distance from a point to a hyperplane and
the hyperplane through <i>d+1</i> points. Qhull detects precision
problems when computing distances. A precision problem occurs if
the distance computation is less than the maximum roundoff error.
Qhull treats the result of a hyperplane computation as an exact
result and allows the corresponding points to be near the
hyperplane. Precision problems do not occur for hyperplane
computations. </p>
<p>Qhull handles precision problems by merging non-convex facets.
The result of merging two facets is a thick facet defined by an <i>inner
plane</i> and an <i>outer plane</i>. The inner and outer planes
are offsets from the facet's hyperplane. The inner plane is
clearly below the facet's vertices. At the end of Qhull, the
outer planes are clearly above all input points. Any exact convex
hull must lie between the inner and outer planes.</p>
<p>Qhull tests for convexity by computing a point for each facet.
This point is called the facet's <i>centrum</i>. It is the
arithmetic center of the facet's vertices projected to the
facet's hyperplane. For simplicial facets with <em>d</em>
vertices, the centrum is equivalent to the centroid or center of
gravity. </p>
<p>Two neighboring facets are convex if each centrum is clearly
below the other hyperplane. The '<a href="qh-optc.htm#Cn2">Cn</a>'
or '<a href="qh-optc.htm#Cn">C-n</a>' options sets the centrum's
radius to <i>n </i>. A centrum is clearly below a hyperplane if
the computed distance from the centrum to the hyperplane is
greater than the centrum's radius plus two maximum roundoff
errors. Two are required because the centrum can be the maximum
roundoff error above its hyperplane and the distance computation
can be high by the maximum roundoff error.</p>
<p>With the '<a href="qh-optc.htm#Cn">C-n</a>' or '<a
href="qh-optc.htm#An">A-n </a>' options, Qhull merges non-convex
facets while constructing the hull. The remaining facets are
clearly convex. With the '<a href="qh-optq.htm#Qx">Qx </a>'
option, Qhull merges coplanar facets after constructing the hull.
While constructing the hull, it merges coplanar horizon facets,
flipped facets, concave facets and duplicated ridges. With '<a
href="qh-optq.htm#Qx">Qx</a>', coplanar points may be missed, but
it appears to be unlikely.</p>
<p>If the user sets the '<a href="qh-optc.htm#An2">An</a>' or '<a
href="qh-optc.htm#An">A-n</a>' option, then all neighboring
facets are clearly convex and the maximum (exact) cosine of an
angle is <i>n</i>.</p>
<p>If '<a href="qh-optc.htm#C0">C-0</a>' or '<a
href="qh-optq.htm#Qx">Qx</a>' is used without other precision
options (default), Qhull tests vertices instead of centrums for
adjacent simplicies. In 3-d, if simplex <i>abc</i> is adjacent to
simplex <i>bcd</i>, Qhull tests that vertex <i>a</i> is clearly
below simplex <i>bcd </i>, and vertex <i>d</i> is clearly below
simplex <i>abc</i>. When building the hull, Qhull tests vertices
if the horizon is simplicial and no merges occur. </p>
<h2><a href="#TOC">»</a><a name="how">How Qhull merges facets</a></h2>
<p>If two facets are not clearly convex, then Qhull removes one
or the other facet by merging the facet into a neighbor. It
selects the merge which minimizes the distance from the
neighboring hyperplane to the facet's vertices. Qhull also
performs merges when a facet has fewer than d neighbors (called a
degenerate facet), when a facet's vertices are included in a
neighboring facet's vertices (called a redundant facet), when a
facet's orientation is flipped, or when a ridge occurs between
more than two facets.</p>
<p>Qhull performs merges in a series of passes sorted by merge
angle. Each pass merges those facets which haven't already been
merged in that pass. After a pass, Qhull checks for redundant
vertices. For example, if a vertex has only two neighbors in 3-d,
the vertex is redundant and Qhull merges it into an adjacent
vertex.</p>
<p>Merging two simplicial facets creates a non-simplicial facet
of <em>d+1</em> vertices. Additional merges create larger facets.
When merging facet A into facet B, Qhull retains facet B's
hyperplane. It merges the vertices, neighbors, and ridges of both
facets. It recomputes the centrum if a wide merge has not
occurred (qh_WIDEcoplanar) and the number of extra vertices is
smaller than a constant (qh_MAXnewcentrum).</p>
<h2><a href="#TOC">»</a><a name="approximate">Approximating a
convex hull</a></h2>
<p>Qhull may be used for approximating a convex hull. This is
particularly valuable in 5-d and higher where hulls can be
immense. You can use '<a href="qh-optq.htm#Qx">Qx</a> <a
href="qh-optc.htm#Cn">C-n</a>' to merge facets as the hull is
being constructed. Then use '<a href="qh-optc.htm#Cn2">Cn</a>'
and/or '<a href="qh-optc.htm#An2">An</a>' to merge small facets
during post-processing. You can print the <i>n</i> largest facets
with option '<a href="qh-optp.htm#PAn">PAn</a>'. You can print
facets whose area is at least <i>n</i> with option '<a
href="qh-optp.htm#PFn">PFn</a>'. You can output the outer planes
and an interior point with '<a href="qh-optf.htm#FV">FV</a> <a
href="qh-optf.htm#Fo">Fo</a>' and then compute their intersection
with 'qhull <a href="qh-opt.htm#Hn">Hn</a> <a
href="qh-optq.htm#Qx">Qx</a>'. </p>
<p>To approximate a convex hull in 6-d and higher, use
post-merging with '<a href="qh-optc.htm#Wn">Wn</a>' (e.g., qhull
W1e-1 C1e-2 TF2000). Pre-merging with a convexity constraint
(e.g., qhull Qx C-1e-2) often produces a poor approximation or
terminates with a simplex. Option '<a href="qh-optq.htm#QbB">QbB</a>'
may help to spread out the data.</p>
<p>You will need to experiment to determine a satisfactory set of
options. Use <a href="qh-rbox.htm">rbox</a> to generate test sets
quickly and <a href="qh-man.htm#geomview">Geomview</a> to view
the results. You will probably want to write your own driver for
Qhull using the Qhull library. For example, you could select the
largest facet in each quadrant.</p>
<!-- Navigation links -->
<hr>
<p><b>Up:</b> <a href="http://www.geom.umn.edu/locate/qhull">Home
page for Qhull</a> <br>
<b>Up:</b> <a href="qh-man.htm#TOC">Qhull manual: Table of
Contents</a><br>
<b>To:</b> <a href="#TOC">Qhull imprecision: Table of Contents</a>
</p>
<!-- GC common information -->
<hr>
<p><a href="http://www.geom.umn.edu/"><img src="qh--geom.gif"
align="middle" width="40" height="40"></a><i>The Geometry Center
Home Page </i></p>
<p>Comments to: <a
href="http://www.geom.umn.edu/software/qhull/qhull-mail.html">qhull@geom.umn.edu
</a><br>
Created: Sept. 25, 1995 --- <!-- hhmts start --> Last modified: see top <!-- hhmts end --> </p>
</body>
</html>