diff options
Diffstat (limited to 'src/qhull/html/qh-impre.htm')
| -rw-r--r-- | src/qhull/html/qh-impre.htm | 826 |
1 files changed, 826 insertions, 0 deletions
diff --git a/src/qhull/html/qh-impre.htm b/src/qhull/html/qh-impre.htm new file mode 100644 index 000000000..cfbe0acb8 --- /dev/null +++ b/src/qhull/html/qh-impre.htm @@ -0,0 +1,826 @@ +<!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> |