9
9
<!-- Navigation links -->
10
<p><a name="TOP"><b>Up:</b></a> <a href="http://www.geom.umn.edu/locate/qhull">Home
10
<p><a name="TOP"><b>Up:</b></a> <a href="http://www.qhull.org">Home
11
11
page</a> for Qhull <br>
12
12
<b>Up:</b> <a href="index.htm#TOC">Qhull manual</a>: Table of
27
27
<!-- Main text of document -->
29
href="http://www.geom.umn.edu/graphics/pix/Special_Topics/Computational_Geometry/4dcube.html"><img
29
href="http://www.geom.uiuc.edu/graphics/pix/Special_Topics/Computational_Geometry/4dcube.html"><img
30
30
src="qh--4d.gif" alt="[4-d cube]" align="middle" width="100"
31
31
height="100"></a> Imprecision in Qhull</h1>
46
46
<p>Qhull automatically tests for convexity if it detects
47
47
precision errors while constructing the hull. </p>
49
<p><b>Copyright © 1995-2001 The Geometry Center, Minneapolis MN</b></p>
49
<p><b>Copyright © 1995-2003 The Geometry Center, Minneapolis MN</b></p>
57
57
<li><a href="#prec">Precision problems</a></li>
58
<li><a href="#joggle">Joggled input or merged facets</a></li>
58
<li><a href="#joggle">Merged facets or joggled input</a></li>
59
59
<li><a href="#delaunay">Delaunay triangulations</a></li>
60
60
<li><a href="#imprecise">Merged facets</a></li>
61
61
<li><a href="#how">How Qhull merges facets</a></li>
137
137
point, but this appears to be unlikely.</p>
139
139
<p>The following pipe implements the identity function for
140
extreme points (with roundoff):</p>
140
extreme points (with roundoff):
143
<p>qconvex <a href="qh-optf.htm#FV">FV</a> <a
144
href="qh-opto.htm#n">n</a> | qhalf <a href="qh-optf.htm#Fp">Fp</a></p>
142
qconvex <a href="qh-optf.htm#FV">FV</a> <a
143
href="qh-opto.htm#n">n</a> | qhalf <a href="qh-optf.htm#Fp">Fp</a>
147
<h2><a href="#TOC">�</a><a name="joggle">Joggled input or merged
150
<p>This section discusses the choice between joggled input and
151
merged facets. By default, Qhull uses merged facets to handle
146
<p>Bernd Gartner published his
147
<a href=http://www.inf.ethz.ch/personal/gaertner/miniball.html>Miniball</a>
148
algorithm ["Fast and robust smallest enclosing balls", <i>Algorithms - ESA '99</i>, LNCS 1643].
149
It uses floating point arithmetic and a carefully designed primitive operation.
150
It is practical to 20-D or higher, and identifies at least two points on the
151
convex hull of the input set. Like Qhull, it is an incremental algorithm that
152
processes points furthest from the intermediate result and ignores
153
points that are close to the intermediate result.
155
<h2><a href="#TOC">�</a><a name="joggle">Merged facets or joggled input</a></h2>
157
<p>This section discusses the choice between merged facets and joggled input.
158
By default, Qhull uses merged facets to handle
152
159
precision problems. With option '<a href="qh-optq.htm#QJn">QJ</a>',
153
160
the input is joggled. See <a href="qh-eg.htm#joggle">examples</a>
154
161
of joggled input and triangulated output.
158
165
<li>Use merged facets and triangulated output ('<a href="qh-optq.htm#Qt">Qt</a>') when
159
166
you want simplicial output and coplanar facets (e.g., triangles for a Delaunay triangulation).
160
167
<li>Use joggled input ('<a href="qh-optq.htm#QJn">QJ</a>') when you need clearly-convex,
162
(e.g., triangles for a Delaunay triangulation).
165
<p>The choice between joggled input and merged facets depends on
171
<p>The choice between merged facets and joggled input depends on
166
172
the application. Both run about the same speed. Joggled input may
167
173
be faster if the initial joggle is sufficiently large to avoid
168
precision errors. Most applications should used merged facets
169
with triangulated output.</p>
176
<p>Most applications should used merged facets
177
with triangulated output. </p>
171
179
<p>Use merged facets (the
172
180
default, '<a href="qh-optc.htm#C0">C-0</a>')
188
196
<li>Your application needs clearly convex, simplicial output</li>
189
197
<li>Your application supports perturbed input points and narrow triangles.</li>
190
<li>Seven significant digits is sufficient accuracy. </li>
198
<li>Seven significant digits is sufficient accuracy.</li>
193
201
<p>You may use both techniques or combine joggle with
232
240
<a href=qvoronoi.htm>qvoronoi</a>, and option '<a
233
241
href="qh-optq.htm#QJn">QJ</a>'.</p>
243
<p>Edelsbrunner, H, <i>Geometry and Topology for Mesh Generation</i>, Cambridge University Press, 2001.
244
Good mathematical treatise on Delaunay triangulation and mesh generation for 2-d
245
and 3-d surfaces. The chapter on surface simplification is
246
particularly interesting. It is similar to facet merging in Qhull.
248
<p>Veron and Leon published an algorithm for shape preserving polyhedral
249
simplification with bounded error [<i>Computers and Graphics</i>, 22.5:565-585, 1998].
250
It remove nodes using front propagation and multiple remeshing.
235
252
<h2><a href="#TOC">�</a><a name="imprecise">Merged facets </a></h2>
237
254
<p>Qhull detects precision
728
745
the results. You will probably want to write your own driver for
729
746
Qhull using the Qhull library. For example, you could select the
730
747
largest facet in each quadrant.</p>
731
749
<!-- Navigation links -->
734
<p><b>Up:</b> <a href="http://www.geom.umn.edu/locate/qhull">Home
752
<p><b>Up:</b> <a href="http://www.qhull.org">Home
735
753
page</a> for Qhull <br>
736
754
<b>Up:</b> <a href="index.htm#TOC">Qhull manual</a>: Table of
749
767
<!-- GC common information -->
752
<p><a href="http://www.geom.umn.edu/"><img src="qh--geom.gif"
770
<p><a href="http://www.geom.uiuc.edu/"><img src="qh--geom.gif"
753
771
align="middle" width="40" height="40"></a><i>The Geometry Center
754
772
Home Page </i></p>
757
href="http://www.geom.umn.edu/software/qhull/qhull-mail.html">qhull@geom.umn.edu
774
<p>Comments to: <a href=mailto:qhull@qhull.org>qhull@qhull.org</a>
759
776
Created: Sept. 25, 1995 --- <!-- hhmts start --> Last modified: see top <!-- hhmts end --> </p>
added
removed
html/qh-impre.htm
