Up: Home page for Qhull (local)
Up: Qhull manual: contents
To: Programs • Options • Output • Formats • Geomview • Print • Qhull • Precision • Trace • Functions (local)
To: Qhull imprecision: contents

Imprecision in Qhull

This section of the Qhull manual discusses the problems caused by coplanar points and why Qhull uses the default options 'C-0' or 'Qx'. If you ignore precision issues with option 'Q0', the output from Qhull can be arbitrarily bad. Qhull avoids most precision problems if you merge facets (the default) or joggle the input ('QJ').

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.

»Precision problems

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.

There are several kinds of precision errors:

Representation error occurs when there are not enough digits to represent a number, e.g., 1/3.
Measurement error occurs when the input coordinates are from measurements.
Roundoff error occurs when a calculation is rounded to a fixed number of digits, e.g., a floating point calculation.
Approximation error occurs when the user wants an approximate result because the exact result contains too much detail.
Topological error occurs when the topology of mathematical convex hulls is broken by facet merging or vertex merging.

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 may be corrected by using option 'C-0', but then the output may contain wide facets.

Qhull 2.5 and later provides option 'QJ' 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.

Joggled input avoids merged facets and the topological issues that may arise. If your application is sensitive to errors, consider joggled input and the corresponding flag, qh_NOmerge.

Qhull 3.1 and later provides option 'Qt' for triangulated output. Non-simplicial facets are triangulated. The facets may have zero area. Triangulated output is particularly useful for Delaunay triangulations.

Qhull 2019.1 includes an experimental option ('Q14') to merge nearly adjacent vertices due to duplicated ridges. If reports a topological error if merging fails to resolve the issue. Further work is needed.

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):

qconvex FV n | qhalf Fp

Bernd Gartner published his Miniball algorithm ["Fast and robust smallest enclosing balls", Algorithms - ESA '99, 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.

»Merged facets or joggled input

This section discusses the choice between merged facets and joggled input. By default, Qhull uses merged facets to handle precision problems. With option 'QJ', the input is joggled. See examples of joggled input and triangulated output.

Use merged facets (the default) when you want non-simplicial output (e.g., the faces of a cube).
Use joggled input ('QJ') when you need clearly-convex, simplicial output.
Use joggled input if your code is sensitive to errors. Joggled input handles all inputs, even highly degenerate inputs such as 100 identical points. If you compile with qh_NOmerge, Qhull does not contain code for merging facets. It uses joggled input instead.
Otherwise, use merged facets and triangulated output ('Qt') when you want simplicial output and coplanar facets (e.g., triangles for a Delaunay triangulation).

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. Although less precise, joggled input is more reliable than merged facets. A future version of Qhull will provide per vertex joggle.

Use merged facets (the default, 'C-0') or triangulated output ('Qt') if

Your application supports non-simplicial facets, or it allows degenerate, simplicial facets (option 'Qt').
You do not want the input modified.
Your input coordinates start with the same five or more digits (i.e., it is shifted relative to the origin). This reduces the available precision.
You use single precision arithmetic (realT).
You want to set additional options for approximating the hull.

Use joggled input ('QJ') if

Your application needs clearly convex, simplicial output
Your application supports perturbed input points and narrow triangles.
Seven significant digits is sufficient accuracy.
Your application is sensitive to errors.

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 poi