Up: Home
page for Qhull
Up: Qhull manual
To: Table of Contents
(please wait while loading)
This 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.
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, March 26, 1997
Copyright © 1995, 1997 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 theoritical.
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.
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. If exact arithmetic was used to intersect the halfspaces, nearly incident points may be returned for one of the 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 is the identity function for Qhull:
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 regions, you may use option 'Qbb' to scale the last coordinate to [0,m] where m is the maximum absolute value of the other coordinates. Option 'Qbb' is recommended for Delaunay triangulations of integer coordinates and for the furthest-site Delaunay triangulation ('d Qu') 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.
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. Since Qhull handles imprecision by merging facets, its output is not triangulated. Instead it produces a single facet for cocircular points. See option 'd'.
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.
If you must triangulate the original point set, try options 'Q0 Po'. They will force a triangulated output if possible. Qhull checks the output for convexity and reports any problems. A better solution is to use exact arithmetic -- see above for Clarkson's or Shewchuk's programs.
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 while the outer plane is clearly above all input points. Any exact convex hull must lie between the inner and outer plane.
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 a feasible 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.
Up: Home
page for Qhull
Up: Qhull manual
To: Table of Contents
Comments to: qhull@geom.umn.edu
Created: Sept. 25, 1995 --- Last modified: see top