827 lines
36 KiB
HTML
827 lines
36 KiB
HTML
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
|
|
<html>
|
|
|
|
<head>
|
|
<title>Imprecision in Qhull</title>
|
|
</head>
|
|
|
|
<body>
|
|
<!-- Navigation links -->
|
|
<p><a name="TOP"><b>Up:</b></a> <a href="http://www.qhull.org">Home
|
|
page</a> for Qhull <br>
|
|
<b>Up:</b> <a href="index.htm#TOC">Qhull manual</a>: Table of
|
|
Contents<br>
|
|
<b>To:</b> <a href="qh-quick.htm#programs">Programs</a>
|
|
• <a href="qh-quick.htm#options">Options</a>
|
|
• <a href="qh-opto.htm#output">Output</a>
|
|
• <a href="qh-optf.htm#format">Formats</a>
|
|
• <a href="qh-optg.htm#geomview">Geomview</a>
|
|
• <a href="qh-optp.htm#print">Print</a>
|
|
• <a href="qh-optq.htm#qhull">Qhull</a>
|
|
• <a href="qh-optc.htm#prec">Precision</a>
|
|
• <a href="qh-optt.htm#trace">Trace</a>
|
|
• <a href="../src/libqhull_r/index.htm">Functions</a><br>
|
|
<b>To: </b><a href="#TOC">Qhull imprecision</a>: Table of Contents
|
|
(please wait while loading)
|
|
|
|
<hr>
|
|
<!-- Main text of document -->
|
|
<h1><a
|
|
href="http://www.geom.uiuc.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. Qhull avoids precision problems if you merge facets (the default) or joggle
|
|
the input ('<a
|
|
href="qh-optq.htm#QJn">QJ</a>'). </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><b>Copyright © 1995-2015 C.B. Barber</b></p>
|
|
|
|
<hr>
|
|
|
|
<h2><a href="#TOP">»</a><a name="TOC">Qhull
|
|
imprecision: Table of Contents </a></h2>
|
|
|
|
<ul>
|
|
<li><a href="#prec">Precision problems</a></li>
|
|
<li><a href="#joggle">Merged facets or joggled input</a></li>
|
|
<li><a href="#delaunay">Delaunay triangulations</a></li>
|
|
<li><a href="#halfspace">Halfspace intersection/a></li>
|
|
<li><a href="#imprecise">Merged facets</a></li>
|
|
<li><a href="#how">How Qhull merges facets</a></li>
|
|
<li><a href="#limit">Limitations of merged facets</a></li>
|
|
<li><a href="#injoggle">Joggled input</a></li>
|
|
<li><a href="#exact">Exact arithmetic</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
|
|
geometric algorithms. Other floating point codes for convex
|
|
hulls, Delaunay triangulations, and Voronoi diagrams also suffer
|
|
from these problems. Qhull handles most of them.</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="index.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 may be 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 joggled 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>Qhull 3.1 and later provides option '<a href="qh-optq.htm#Qt">Qt</a>'
|
|
for triangulated output. This removes the need for
|
|
joggled input ('<a href="qh-optq.htm#QJn">QJ</a>').
|
|
Non-simplicial facets are triangulated.
|
|
The facets may have zero area.
|
|
Triangulated output is particularly useful for Delaunay triangulations.</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):
|
|
<blockquote>
|
|
qconvex <a href="qh-optf.htm#FV">FV</a> <a
|
|
href="qh-opto.htm#n">n</a> | qhalf <a href="qh-optf.htm#Fp">Fp</a>
|
|
</blockquote>
|
|
|
|
<p>Bernd Gartner published his
|
|
<a href=http://www.inf.ethz.ch/personal/gaertner/miniball.html>Miniball</a>
|
|
algorithm ["Fast and robust smallest enclosing balls", <i>Algorithms - ESA '99</i>, LNCS 1643].
|
|
It uses floating point arithmetic and a carefully designed primitive operation.
|
|
It is practical to 20-D or higher, and identifies at least two points on the
|
|
convex hull of the input set. Like Qhull, it is an incremental algorithm that
|
|
processes points furthest from the intermediate result and ignores
|
|
points that are close to the intermediate result.
|
|
|
|
<h2><a href="#TOC">»</a><a name="joggle">Merged facets or joggled input</a></h2>
|
|
|
|
<p>This section discusses the choice between merged facets and joggled input.
|
|
By default, Qhull uses merged facets to handle
|
|
precision problems. With option '<a href="qh-optq.htm#QJn">QJ</a>',
|
|
the input is joggled. See <a href="qh-eg.htm#joggle">examples</a>
|
|
of joggled input and triangulated output.
|
|
<ul>
|
|
<li>Use merged facets (the default)
|
|
when you want non-simplicial output (e.g., the faces of a cube).
|
|
<li>Use merged facets and triangulated output ('<a href="qh-optq.htm#Qt">Qt</a>') when
|
|
you want simplicial output and coplanar facets (e.g., triangles for a Delaunay triangulation).
|
|
<li>Use joggled input ('<a href="qh-optq.htm#QJn">QJ</a>') when you need clearly-convex,
|
|
simplicial output.
|
|
</ul>
|
|
|
|
<p>The choice between merged facets and joggled input 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>Most applications should used merged facets
|
|
with triangulated output. </p>
|
|
|
|
<p>Use merged facets (the
|
|
default, '<a href="qh-optc.htm#C0">C-0</a>')
|
|
or triangulated output ('<a href="qh-optq.htm#Qt">Qt</a>') if </p>
|
|
|
|
<ul>
|
|
<li>Your application supports non-simplicial facets, or
|
|
it allows degenerate, simplicial facets (option '<a href="qh-optq.htm#Qt">Qt</a>'). </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 arithmetic (<a href="../src/libqhull/user.h#realT">realT</a>).
|
|
</li>
|
|
</ul>
|
|
|
|
<p>Use joggled input ('<a href="qh-optq.htm#QJn">QJ</a>') if </p>
|
|
|
|
<ul>
|
|
<li>Your application needs clearly convex, simplicial output</li>
|
|
<li>Your application supports perturbed input points and narrow triangles.</li>
|
|
<li>Seven significant digits is sufficient accuracy.</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>
|
|
|
|
<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 fix the problem or attempt to merge the
|
|
last remaining facets. </p>
|
|
|
|
<h2><a href="#TOC">»</a><a name="delaunay">Delaunay
|
|
triangulations </a></h2>
|
|
|
|
<p>Programs that use Delaunay triangulations traditionally assume
|
|
a triangulated input. By default, <a href=qdelaun.htm>qdelaunay</a>
|
|
merges regions with cocircular or cospherical input sites.
|
|
If you want a simplicial triangulation
|
|
use triangulated output ('<a href="qh-optq.htm#Qt">Qt</a>') or joggled
|
|
input ('<a href="qh-optq.htm#QJn">QJ</a>').
|
|
|
|
<p>For Delaunay triangulations, triangulated
|
|
output should produce good results. All points are within roundoff error of
|
|
a paraboloid. If two points are nearly incident, one will be a
|
|
coplanar point. So all points are clearly separated and convex.
|
|
If qhull reports deleted vertices, the triangulation
|
|
may contain serious precision faults. Deleted vertices are reported
|
|
in the summary ('<a href="qh-opto.htm#s">s</a>', '<a href="qh-optf.htm#Fs">Fs</a>'</p>
|
|
|
|
<p>You should use 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 <a href=qdelaun.htm>qdelaunay</a>,
|
|
<a href=qvoronoi.htm>qvoronoi</a>, and option '<a
|
|
href="qh-optq.htm#QJn">QJ</a>'.</p>
|
|
|
|
<p>Edelsbrunner, H, <i>Geometry and Topology for Mesh Generation</i>, Cambridge University Press, 2001.
|
|
Good mathematical treatise on Delaunay triangulation and mesh generation for 2-d
|
|
and 3-d surfaces. The chapter on surface simplification is
|
|
particularly interesting. It is similar to facet merging in Qhull.
|
|
|
|
<p>Veron and Leon published an algorithm for shape preserving polyhedral
|
|
simplification with bounded error [<i>Computers and Graphics</i>, 22.5:565-585, 1998].
|
|
It remove nodes using front propagation and multiple remeshing.
|
|
|
|
<h2><a href="#TOC">»</a><a name="halfspace">Halfspace intersection</a></h2>
|
|
|
|
<p>
|
|
The identity pipe for Qhull reveals some precision questions for
|
|
halfspace intersections. The identity pipe creates the convex hull of
|
|
a set of points and intersects the facets' hyperplanes. It should return the input
|
|
points, but narrow distributions may drop points while offset distributions may add
|
|
points. It may be better to normalize the input set about the origin.
|
|
For example, compare the first results with the later two results: [T. Abraham]
|
|
<blockquote>
|
|
rbox 100 s t | tee r | qconvex FV n | qhalf Fp | cat - r | /bin/sort -n | tail
|
|
<br>
|
|
rbox 100 L1e5 t | tee r | qconvex FV n | qhalf Fp | cat - r | /bin/sort -n | tail
|
|
<br>
|
|
rbox 100 s O10 t | tee r | qconvex FV n | qhalf Fp | cat - r | /bin/sort -n | tail
|
|
</blockquote>
|
|
|
|
|
|
<h2><a href="#TOC">»</a><a name="imprecise">Merged facets </a></h2>
|
|
|
|
<p>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 if it
|
|
were exact.</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 simplices. 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 <i>d</i> 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="limit">Limitations of merged
|
|
facets</a></h2>
|
|
|
|
<ul>
|
|
<li><b>Uneven dimensions</b> --
|
|
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, <a href=qdelaun.htm>qdelaunay</a>
|
|
and <a href=qvoronoi.htm>qvoronoi</a> always set
|
|
option '<a href="qh-optq.htm#Qbb">Qbb</a>'. It scales 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
|
|
needed for Delaunay triangulations of integer coordinates
|
|
and nearly cocircular points.
|
|
|
|
<p>For example, compare
|
|
<pre>
|
|
rbox 1000 W0 t | qconvex Qb2:-1e-14B2:1e-14
|
|
</pre>
|
|
with
|
|
<pre>
|
|
rbox 1000 W0 t | qconvex
|
|
</pre>
|
|
The distributions are the same but the first is compressed to a 2e-14 slab.
|
|
<p>
|
|
<li><b>Post-merging of coplanar facets</b> -- 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>This is difficult to produce in 5-d and higher. Option '<a href="qh-optq.htm#Q6">Q6</a>' turns off merging of concave
|
|
facets. This is similar to 'Qx'. It may lead to serious precision errors,
|
|
for example,
|
|
<pre>
|
|
rbox 10000 W1e-13 | qhull Q6 Tv
|
|
</pre>
|
|
|
|
<p>
|
|
<li><b>Maximum facet width</b> --
|
|
Qhull reports the maximum outer plane and inner planes (if
|
|
more than roundoff error apart). There is no 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 may indicate an
|
|
implementation error. Narrow distributions (see following) may
|
|
produce wide facets.
|
|
|
|
<p>For example, if special processing for narrow distributions is
|
|
turned off ('<a href="qh-optq.htm#Q10">Q10</a>'), qhull may produce
|
|
a wide facet:</p>
|
|
<pre>
|
|
rbox 1000 L100000 s G1e-16 t1002074964 | qhull Tv Q10
|
|
</pre>
|
|
|
|
<p>
|
|
<li><b>Narrow distribution</b> -- In 3-d, a narrow distribution may result in a poor
|
|
approximation. For example, if you do not use qdelaunay nor option
|
|
'<a href="qh-optq.htm#Qbb">Qbb</a>', the furthest-site
|
|
Delaunay triangulation of nearly cocircular points may produce a poor
|
|
approximation:
|
|
<pre>
|
|
rbox s 5000 W1e-13 D2 t1002151341 | qhull d Qt
|
|
rbox 1000 s W1e-13 t1002231672 | qhull d Tv
|
|
</pre>
|
|
|
|
<p>During
|
|
construction of the hull, a point may be above two
|
|
facets with opposite orientations that span the input
|
|
set. Even though the point may be nearly coplanar with both
|
|
facets, and can be distant from the precise convex
|
|
hull of the input sites. Additional facets leave the point distant from
|
|
a facet. To fix this problem, add option '<a href="qh-optq.htm#Qbb">Qbb</a>'
|
|
(it scales the last coordinate). Option '<a href="qh-optq.htm#Qbb">Qbb</a>'
|
|
is automatically set for <a href=qdelaun.htm>qdelaunay</a> and <a href=qvoronoi.htm>qvoronoi</a>.
|
|
|
|
<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.
|
|
Use option '<a href="qh-optq.htm#Q10">Q10</a>' to try Qhull without
|
|
special processing for narrow distributions.
|
|
For example, special processing is needed for:
|
|
<pre>
|
|
rbox 1000 L100000 s G1e-16 t1002074964 | qhull Tv Q10
|
|
</pre>
|
|
|
|
<p>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>Similar problems occur for distributions with a large flat facet surrounded
|
|
with many small facet at a sharp angle to the large facet.
|
|
Qhull 3.1 fixes most of these problems, but a poor approximation can occur.
|
|
A point may be left outside of the convex hull ('<a href="qh-optt.htm#Tv">Tv</a>').
|
|
Examples include
|
|
the furthest-site Delaunay triangulation of nearly cocircular points plus the origin, and the convex hull of a cone of nearly cocircular points. The width of the band is 10^-13.
|
|
<pre>
|
|
rbox s 1000 W1e-13 P0 D2 t996799242 | qhull d Tv
|
|
rbox 1000 s Z1 G1e-13 t1002152123 | qhull Tv
|
|
rbox 1000 s Z1 G1e-13 t1002231668 | qhull Tv
|
|
</pre>
|
|
|
|
<p>
|
|
<li><b>Quadratic running time</b> -- If the output contains large, non-simplicial
|
|
facets, the running time for Qhull may be quadratic in the size of the triangulated
|
|
output. For example, <tt>rbox 1000 s W1e-13 c G2 | qhull d</tt> is 4 times
|
|
faster for 500 points. The convex hull contains two large nearly spherical facets and
|
|
many nearly coplanar facets. Each new point retriangulates the spherical facet and repartitions the remaining points into all of the nearly coplanar facets.
|
|
In this case, quadratic running time is avoided if you use qdelaunay,
|
|
add option '<a href="qh-optq.htm#Qbb">Qbb</a>',
|
|
or add the origin ('P0') to the input.
|
|
<p>
|
|
<li><b>Nearly coincident points within 1e-13</b> --
|
|
Multiple, nearly coincident points within a 1e-13 ball of points in the unit cube
|
|
may lead to wide facets or quadratic running time.
|
|
For example, the convex hull a 1000 coincident, cospherical points in 4-D,
|
|
or the 3-D Delaunay triangulation of nearly coincident points, may lead to very
|
|
wide facets (e.g., 2267021951.3x).
|
|
|
|
<p>For Delaunay triangulations, the problem typically occurs for extreme points of the input
|
|
set (i.e., on the edge between the upper and lower convex hull). After multiple facet merges, four
|
|
facets may share the same, duplicate ridge and must be merged.
|
|
Some of these facets may be long and narrow, leading to a very wide merged facet.
|
|
If so, error QH6271 is reported. It may be overriden with option '<a href="qh-optq.htm#Q12">Q12</a>'.
|
|
|
|
<p>Duplicate ridges occur when the horizon facets for a new point is "pinched".
|
|
In a duplicate ridge, a subridge (e.g., a line segment in 3-d) is shared by two horizon facets.
|
|
At least two of its vertices are nearly coincident. It is easy to generate coincident points with
|
|
option 'Cn,r,m' of rbox. It generates n points within an r ball for each of m input sites. For example,
|
|
every point of the following distributions has a nearly coincident point within a 1e-13 ball.
|
|
Substantially smaller or larger balls do not lead to pinched horizons.
|
|
<pre>
|
|
rbox 1000 C1,1e-13 D4 s t | qhull
|
|
rbox 75 C1,1e-13 t | qhull d
|
|
</pre>
|
|
For Delaunay triangulations, a bounding box may alleviate this error (e.g., <tt>rbox 500 C1,1E-13 t c G1 | qhull d</tt>).
|
|
A later release of qhull will avoid pinched horizons by merging duplicate subridges. A subridge is
|
|
merged by merging adjacent vertices.
|
|
<p>
|
|
<li><b>Facet with zero-area</b> --
|
|
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>
|
|
|
|
<p>
|
|
<li><b>No more facets</b> -- 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>
|
|
<li><b>Deleted cone</b> -- Lots of merging can end up deleting all
|
|
of the new facets for a point. This is a rare event that has
|
|
only been seen while debugging the code.
|
|
|
|
<p>
|
|
<li><b>Triangulated output leads to precision problems</b> -- With sufficient
|
|
merging, the ridges of a non-simplicial facet may have serious topological
|
|
and geometric problems. A ridge may be between more than two
|
|
neighboring facets. If so, their triangulation ('<a href="qh-optq.htm#Qt">Qt</a>')
|
|
will fail since two facets have the same vertex set. Furthermore,
|
|
a triangulated facet may have flipped orientation compared to its
|
|
neighbors.</li>
|
|
|
|
<p>The triangulation process detects degenerate facets with
|
|
only two neighbors. These are marked degenerate. They have
|
|
zero area.
|
|
|
|
<p>
|
|
<li><b>Coplanar points</b> --
|
|
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>
|
|
<li><b>Maximum roundoff error</b> -- 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>
|
|
<li><b>All flipped or upper Delaunay</b> -- When a lot of merging occurs for
|
|
Delaunay triangulations, a new point may lead to no good facets. For example,
|
|
try a strong convexity constraint:
|
|
<pre>
|
|
rbox 1000 s t993602376 | qdelaunay C-1e-3
|
|
</pre>
|
|
|
|
</ul>
|
|
|
|
<h2><a href="#TOC">»</a><a name="injoggle">Joggled input</a></h2>
|
|
|
|
<p>Joggled input is a simple work-around for precision problems
|
|
in computational geometry ["joggle: to shake or jar
|
|
slightly," Amer. Heritage Dictionary]. Other names are
|
|
<i>jostled input</i> or <i>random perturbation</i>.
|
|
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>Neither joggle nor merged facets 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 ('<a href="qh-optt.htm#TRn">TRn</a>') . 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>
|
|
|
|
<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.</p>
|
|
|
|
<p>Clarkson's <a
|
|
href="http://www.netlib.org/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="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 'qhalf'. </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="rbox.htm">rbox</a> to generate test sets
|
|
quickly and <a href="index.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.qhull.org">Home
|
|
page</a> for Qhull <br>
|
|
<b>Up:</b> <a href="index.htm#TOC">Qhull manual</a>: Table of
|
|
Contents<br>
|
|
<b>To:</b> <a href="qh-quick.htm#programs">Programs</a>
|
|
• <a href="qh-quick.htm#options">Options</a>
|
|
• <a href="qh-opto.htm#output">Output</a>
|
|
• <a href="qh-optf.htm#format">Formats</a>
|
|
• <a href="qh-optg.htm#geomview">Geomview</a>
|
|
• <a href="qh-optp.htm#print">Print</a>
|
|
• <a href="qh-optq.htm#qhull">Qhull</a>
|
|
• <a href="qh-optc.htm#prec">Precision</a>
|
|
• <a href="qh-optt.htm#trace">Trace</a>
|
|
• <a href="../src/libqhull_r/index.htm">Functions</a><br>
|
|
<b>To:</b> <a href="#TOC">Qhull imprecision: Table of Contents</a>
|
|
|
|
<!-- GC common information -->
|
|
<hr>
|
|
|
|
<p><a href="http://www.geom.uiuc.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=mailto:qhull@qhull.org>qhull@qhull.org</a>
|
|
</a><br>
|
|
Created: Sept. 25, 1995 --- <!-- hhmts start --> Last modified: see top <!-- hhmts end --> </p>
|
|
</body>
|
|
</html>
|