Up: Home page for Qhull (local)
Up: Qhull manual: contents
To: ProgramsOptionsOutputFormatsGeomviewPrintQhullPrecisionTraceFunctions (local)


[delaunay] Qhull precision options

This section lists the precision options for Qhull. These options are indicated by an upper-case letter followed by a number.

Copyright © 1995-2020 C.B. Barber


» Programs OptionsOutputFormatsGeomviewPrintQhullPrecisionTraceFunctions (local)

Precision options

Most users will not need to set these options. They are best used for approximating a convex hull. They may also be used for testing Qhull's handling of precision errors.

Qhull uses the default option 'C-0' for 2-d, 3-d and 4-d, and 'Qx' for 5-d and higher. These options use facet merging to handle precision errors. You may also use joggled input 'QJ' to avoid precision problems. For more information see Imprecision in Qhull.

 
General
Cn
centrum radius for post-merging
C-n
centrum radius for pre-merging
An
cosine of maximum angle for post-merging
A-n
cosine of maximum angle for pre-merging
Qx
exact pre-merges (allows coplanar facets)
C-0
handle all precision errors
Wn
min distance above plane for outside points
 
Experimental
Un
max distance below plane for a new, coplanar point
En
max roundoff error for distance computation
Vn
min distance above plane for a visible facet
Rn
randomly perturb computations by a factor of [1-n,1+n]

»A-n - cosine of maximum angle for pre-merging.

Pre-merging occurs while Qhull constructs the hull. It is indicated by 'C-n', 'A-n', or 'Qx'.

If the angle between a pair of facet normals is greater than n, Qhull merges one of the facets into a neighbor. It selects the facet that is closest to a neighboring facet.

For example, option 'A-0.99' merges facets during the construction of the hull. If the cosine of the angle between facets is greater than 0.99, one or the other facet is merged. Qhull accounts for the maximum roundoff error.

If 'A-n' is set without 'C-n', then 'C-0' is automatically set.

In 5-d and higher, you should set 'Qx' along with 'A-n'. It skips merges of coplanar facets until after the hull is constructed and before 'An' and 'Cn' are checked.

»An - cosine of maximum angle for post-merging.

Post merging occurs after the hull is constructed. For example, option 'A0.99' merges a facet if the cosine of the angle between facets is greater than 0.99. Qhull accounts for the maximum roundoff error.

If 'An' is set without 'Cn', then 'C0' is automatically set.

»C-0 - handle all precision errors

Qhull handles precision errors by merging facets. The default option 'C-0' handles all precision errors in 2-d, 3-d, and 4-d. It may be used in higher dimensions, but sometimes the facet width grows rapidly. In 5-d and higher, the default option is 'Qx'. Use 'QJ' to joggle the input instead of merging facets. Use 'Q0' to turn both options off.

Qhull optimizes 'C-0' ("_zero-centrum") by testing vertices instead of centrums for adjacent simplices. This may be slower in higher dimensions if merges decrease the number of processed points. The optimization may be turned off by setting a small value such as 'C-1e-30'. See How Qhull handles imprecision.

»C-n - centrum radius for pre-merging

Pre-merging occurs while Qhull constructs the hull. It is indicated by 'C-n', 'A-n', or 'Qx'.

The centrum of a facet is a point on the facet for testing facet convexity. It is the average of the vertices projected to the facet's hyperplane. Two adjacent facets are convex if each centrum is clearly below the other facet.

If adjacent facets are non-convex, one of the facets is merged into a neighboring facet. Qhull merges the facet that is closest to a neighboring facet.

For option 'C-n', n is the centrum radius. For example, 'C-0.001' merges facets whenever the centrum is less than 0.001 from a neighboring hyperplane. Qhull accounts for roundoff error when testing the centrum.

In 5-d and higher, you should set 'Qx' along with 'C-n'. It skips merges of coplanar facets until after the hull is constructed and before 'An' and 'Cn' are checked.

»Cn - centrum radius for post-merging

Post-merging occurs after Qhull constructs the hull. It is indicated by 'Cn' or 'An'.

For option 'Cn', n is the centrum radius. For example, 'C0.001' merges facets when the centrum is less than 0.001 from a neighboring hyperplane. Qhull accounts for roundoff error when testing the centrum.

Both pre-merging and post-merging may be defined. If only post-merging is used ('Q0' with 'Cn'), Qhull may fail to produce a hull due to precision errors during the hull's construction.

»En - max roundoff error for distance computations

This allows the user to change the maximum roundoff error computed by Qhull. The value computed by Qhull may be overly pessimistic. If 'En' is set too small, then the output may not be convex. The statistic "max. distance of a new vertex to a facet" (from option 'Ts') is a reasonable upper bound for the actual roundoff error.

»Rn - randomly perturb computations

This option perturbs every distance, hyperplane, and angle computation by up to (+/- n * max_coord). It simulates the effect of roundoff errors. Unless 'En' is explicitly set, it is adjusted for 'Rn'. The command 'qhull Rn' will generate a convex hull despite the perturbations. See the Examples section for an example.

Options 'Rn C-n' have the effect of 'W2n' and 'C-2n'. To use time as the random number seed, use option 'QR-1'.

»Un - max distance for a new, coplanar point

This allows the user to set coplanarity. When pre-merging ('C-n', 'A-n' or 'Qx'), Qhull merges a new point into any coplanar facets. The default value for 'Un' is 'Vn'.

»Vn - min distance for a visible facet

This allows the user to set facet visibility. When adding a point to the convex hull, Qhull determines all facets that are visible from the point. A facet is visible if the distance from the point to the facet is greater than 'Vn'.

Without merging, the default value for 'Vn' is the roundoff error ('En'). With merging, the default value is the pre-merge centrum ('C-n') in 2-d or 3-d, or three times that in other dimensions. If the outside width is specified with option 'Wn', the maximum, default value for 'Vn' is 'Wn'.

Qhull warns if 'Vn' is greater than 'Wn' and furthest outside ('Qf') is not selected; this combination usually results in flipped facets (i.e., reversed normals).

»Wn - min distance above plane for outside points

Points are added to the convex hull only if they are clearly outside of a facet. A point is outside of a facet if its distance to the facet is greater than 'Wn'. Without pre-merging, the default value for 'Wn' is 'En'. If the user specifies pre-merging and does not set 'Wn', than 'Wn' is set to the maximum of 'C-n' and maxcoord*(1 - A-n).

This option is good for approximating a convex hull.

Options 'Qc' and 'Qi' use the minimum vertex to distinguish coplanar points from interior points.


Up: Home page for Qhull (local)
Up: Qhull manual: contents
To: ProgramsOptionsOutputFormatsGeomviewPrintQhullPrecisionTraceFunctions (local)


The Geometry Center Home Page

Comments to: qhull@qhull.org
Created: Sept. 25, 1995 --- Last modified: see top