![[4-d cube]](qh--4d.gif)
Imprecision in QhullUp: Home
page for Qhull
Up: Qhull manual: Table of
Contents
To: Qhull imprecision: Table of Contents
(please wait while loading)
Imprecision in QhullThis section of the Qhull manual discusses the problems caused by coplanar points and why Qhull uses options 'C-0' or 'Qx' by default. If you ignore precision issues with option 'Q0', the output from Qhull can be arbitrarily bad. If you joggle the input with option 'QJ', Qhull avoids precision problems.
Use option 'Tv' 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.
Qhull automatically tests for convexity if it detects precision errors while constructing the hull.
Brad Barber, Cambridge MA, January 8, 1998
Copyright © 1995-1998 The Geometry Center, Minneapolis MN
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.
There are several kinds of precision errors:
Under imprecision, calculations may return erroneous results. For example, roundoff error can turn a small, positive number into a small, negative number. See Milenkovic ['93] for a discussion of strict robust geometry. Qhull does not meet Milenkovic's criterion for accuracy. Qhull's error bound is empirical instead of theoretical.
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.
Qhull 2.4 and later automatically handles errors due to machine round-off. Option 'C-0' or 'Qx' 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 'C-0', but then the output may contain wide facets.
Qhull 2.5 and later provides option 'QJ' 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.
By handling round-off errors, Qhull can provide a variety of output formats. For example, it can return the halfspace that defines each facet ('n'). 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.
The following pipe implements the identity function for extreme points (with roundoff):
This section discusses the choice between joggled input and merged facets. By default, Qhull uses merged facets to handle precision problems. With option 'QJ', 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).
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.
Merged facets ('C-0') 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.
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.
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.
Convex hull of unit cube
joggle error prob. 1.0e-15 0.983 2.0e-15 0.830 4.0e-15 0.561 8.0e-15 0.325 1.6e-14 0.185 3.2e-14 0.099 6.4e-14 0.051 1.3e-13 0.025 2.6e-13 0.010 5.1e-13 0.004 1.0e-12 0.002 2.0e-12 0.001
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.
Convex hull of 1000 points on unit cube
joggle error prob. 1.0e-12 0.870 2.0e-12 0.700 4.0e-12 0.450 8.0e-12 0.250 1.6e-11 0.110 3.2e-11 0.065 6.4e-11 0.030 1.3e-10 0.010 2.6e-10 0.008 5.1e-09 0.003
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.
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.
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.
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.
Use joggled input ('QJ') if
Use merged facets ('C-0', the default) if
You may use both techniques or combine joggle with post-merging ('Cn').
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.
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 'QbB' to scale points to the unit cube. For Delaunay triangulations and Voronoi diagrams, you may use option 'Qbb' to scale the last coordinate to [0,m] where m is the maximum width of the other coordinates. Option 'Qbb' is recommended for Delaunay triangulations of integer coordinates and Delaunay triangulations ('d') of nearly cocircular points.
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 'C-n'.
In 5-d and higher, option 'Qx' (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 'Qx' for further discussion.
Option 'Qc' 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 user.h. 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 'Qc Qi') or make qh_RATIOnearInside sufficiently large.
In 3-d, a narrow distribution may result in a poor approximation. For example, rbox s 5000 W1e-13 D2 | qhull d Qu 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 'Qbb' (it scales the last coordinate).
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 user.h or by setting option 'Pp'.
Qhull reports an error if there are d+1 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 'C-n'.
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 'Qx' option, it does a good job in higher dimensions. In 5-d and higher, Qhull does poorly at detecting redundant vertices.
In the summary ('s'), 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.
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.
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 d points.
Clarkson's hull program and Shewchuk's triangle program are practical implementations of exact arithmetic.
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.
Programs that use Delaunay triangulations traditionally assume a triangulated input. If you want triangulated output from Qhull use the joggle option 'QJ' with option 'd'. If you want merged facets for cocircular or cospherical points then use option 'd' alone.
Option 'Ft' 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.
Try option 'Qbb' with Delaunay triangulations. It scales the last coordinate and may reduce roundoff error. It is automatically set for option 'QJ'
Qhull computes the distance from a point to a hyperplane and the hyperplane through d+1 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.
Qhull handles precision problems by merging non-convex facets. The result of merging two facets is a thick facet defined by an inner plane and an outer plane. 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.
Qhull tests for convexity by computing a point for each facet. This point is called the facet's centrum. It is the arithmetic center of the facet's vertices projected to the facet's hyperplane. For simplicial facets with d vertices, the centrum is equivalent to the centroid or center of gravity.
Two neighboring facets are convex if each centrum is clearly below the other hyperplane. The 'Cn' or 'C-n' options sets the centrum's radius to n . 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.
With the 'C-n' or 'A-n ' options, Qhull merges non-convex facets while constructing the hull. The remaining facets are clearly convex. With the 'Qx ' 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 'Qx', coplanar points may be missed, but it appears to be unlikely.
If the user sets the 'An' or 'A-n' option, then all neighboring facets are clearly convex and the maximum (exact) cosine of an angle is n.
If 'C-0' or 'Qx' is used without other precision options (default), Qhull tests vertices instead of centrums for adjacent simplicies. In 3-d, if simplex abc is adjacent to simplex bcd, Qhull tests that vertex a is clearly below simplex bcd , and vertex d is clearly below simplex abc. When building the hull, Qhull tests vertices if the horizon is simplicial and no merges occur.
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.
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.
Merging two simplicial facets creates a non-simplicial facet of d+1 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).
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 'Qx C-n' to merge facets as the hull is being constructed. Then use 'Cn' and/or 'An' to merge small facets during post-processing. You can print the n largest facets with option 'PAn'. You can print facets whose area is at least n with option 'PFn'. You can output the outer planes and an interior point with 'FV Fo' and then compute their intersection with 'qhull Hn Qx'.
To approximate a convex hull in 6-d and higher, use post-merging with 'Wn' (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 'QbB' may help to spread out the data.
You will need to experiment to determine a satisfactory set of options. Use rbox to generate test sets quickly and Geomview 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.
Up: Home
page for Qhull
Up: Qhull manual: Table of
Contents
To: Qhull imprecision: Table of Contents
The Geometry Center
Home Page
Comments to: qhull@geom.umn.edu
Created: Sept. 25, 1995 --- Last modified: see top