![[delaunay]](qh--dt.gif)
Qhull control options (Q)Up: Home page for Qhull
Up: Qhull manual: Table of Contents
To: Programs
• Options
• Output
• Formats
• Geomview
• Print
• Qhull
• Precision
• Trace
• Functions
Qhull control options (Q)This section lists the control options for Qhull. These options are indicated by 'Q' followed by a letter.
Copyright © 1995-2015 C.B. Barber
» Programs • Options • Output • Formats • Geomview • Print • Qhull • Precision • Trace • Functions
After scaling with option 'Qbb', the lower bound of the last coordinate will be 0 and the upper bound will be the maximum width of the other coordinates. Scaling happens after projecting the points to a paraboloid and scaling other coordinates.
Option 'Qbb' is automatically set for qdelaunay and qvoronoi. Option 'Qbb' is automatically set for joggled input 'QJ'.
Option 'Qbb' should be used for Delaunay triangulations with integer coordinates. Since the last coordinate is the sum of squares, it may be much larger than the other coordinates. For example, rbox 10000 D2 B1e8 | qhull d has precision problems while rbox 10000 D2 B1e8 | qhull d Qbb is OK.
After scaling with option 'QbB', the lower bound will be -0.5 and the upper bound +0.5 in all dimensions. For different bounds change qh_DEFAULTbox in user.h (0.5 is best for Geomview).
For Delaunay and Voronoi diagrams, scaling happens after projection to the paraboloid. Under precise arithmetic, scaling does not change the topology of the convex hull. Scaling may reduce precision errors if coordinate values vary widely.
After scaling, the lower bound for dimension k of the input points will be n. 'Qbk' scales coord[k] to -0.5.
After scaling, the upper bound for dimension k of the input points will be n. 'QBk' scales coord[k] to 0.5.
Drop dimension k from the input points. For example, 'Qb1:0B1:0' deletes the y-coordinate from all input points. This allows the user to take convex hulls of sub-dimensional objects. It happens before the Delaunay and Voronoi transformation. It happens after the halfspace transformation for both the data and the feasible point.
During construction of the hull, a point is coplanar if it is between 'Wn' above and 'Un' below a facet's hyperplane. A different definition is used for output from Qhull.
For output, a coplanar point is above the minimum vertex (i.e., above the inner plane). With joggle ('QJ'), a coplanar point includes points within one joggle of the inner plane.
With option 'Qc', output formats 'p ', 'f', 'Gp', 'Fc', 'FN', and 'FP' will print the coplanar points. With options 'Qc Qi' these outputs include the interior points.
For Delaunay triangulations (qdelaunay or qvoronoi), a coplanar point is a point that is nearly incident to a vertex. All input points are either vertices of the triangulation or coplanar.
Qhull stores coplanar points with a facet. While constructing the hull, it retains all points within qh_RATIOnearInside (user.h) of a facet. In qh_check_maxout(), it uses these points to determine the outer plane for each facet. With option 'Qc', qh_check_maxout() retains points above the minimum vertex for the hull. Other points are removed. If qh_RATIOnearInside is wrong or if options 'Q5 Q8' are set, a coplanar point may be missed in the output (see Qhull limitations).
After adding a new point to the convex hull, Qhull partitions the outside points and coplanar points of the old, visible facets. Without the 'f ' option and merging, it assigns a point to the first facet that it is outside ('Wn'). When merging, it assigns a point to the first facet that is more than several times outside (see qh_DISToutside in user.h).
If option 'Qf' is selected, Qhull performs a directed search (no merging) or an exhaustive search (merging) of new facets. Option 'Qf' may reduce precision errors if pre-merging does not occur.
Option 'Q9' processes the furthest of all furthest points.
Qhull has several options for defining and printing good facets. With the 'Qg' option, Qhull will only build those facets that it needs to determine the good facets in the output. This may speed up Qhull in 2-d and 3-d. It is useful for furthest-site Delaunay triangulations (qdelaunay Qu, invoke with 'qhull d Qbb Qu Qg'). It is not effective in higher dimensions because many facets see a given point and contain a given vertex. It is not guaranteed to work for all combinations.
See 'QGn', 'QVn', and 'Pdk' for defining good facets, and 'Pg' and 'PG' for printing good facets and their neighbors. If pre-merging ('C-n') is not used and there are coplanar facets, then 'Qg Pg' may produce a different result than 'Pg'.
With option 'QGn', a facet is good (see 'Qg' and 'Pg') if it is visible from point n. If n < 0, a facet is good if it is not visible from point n. Point n is not added to the hull (unless 'TCn' or 'TPn').
With rbox, use the 'Pn,m,r' option to define your point; it will be point 0 ('QG0').
Normally Qhull ignores points that are clearly interior to the convex hull. With option 'Qi', Qhull treats interior points the same as coplanar points. Option 'Qi' does not retain coplanar points. You will probably want 'Qc ' as well.
Option 'Qi' is automatically set for 'qdelaunay Qc' and 'qvoronoi Qc'. If you use 'qdelaunay Qi' or 'qvoronoi Qi', option 's' reports all nearly incident points while option 'Fs' reports the number of interior points (should always be zero).
With option 'Qi', output formats 'p', 'f','Gp', 'Fc', 'FN', and 'FP' include interior points.
Option 'QJ' or 'QJn' joggles each input coordinate by adding a random number in the range [-n,n]. If a precision error occurs, It tries again. If precision errors still occur, Qhull increases n ten-fold and tries again. The maximum value for increasing n is 0.01 times the maximum width of the input. Option 'QJ' selects a default value for n. User.h defines these parameters and a maximum number of retries. See Merged facets or joggled input.
Users of joggled input should consider converting to triangulated output ('Qt'). Triangulated output is approximately 1000 times more accurate than joggled input.
Option 'QJ' also sets 'Qbb' for Delaunay triangulations and Voronoi diagrams. It does not set 'Qbb' if 'Qbk:n' or 'QBk:n' are set.
If 'QJn' is set, Qhull does not merge facets unless requested to. All facets are simplicial (triangular in 2-d). This may be important for your application. You may also use triangulated output ('Qt') or Option 'Ft'.
Qhull adjusts the outer and inner planes for 'QJn' ('Fs'). They are increased by sqrt(d)*n to account for the maximum distance between a joggled point and the corresponding input point. Coplanar points ('Qc') require an additional sqrt(d)*n since vertices and coplanar points may be joggled in opposite directions.
For Delaunay triangulations (qdelaunay), joggle happens before lifting the input sites to a paraboloid. Instead of 'QJ', you may use triangulated output ('Qt')
This option is deprecated for Voronoi diagrams (qvoronoi). It triangulates cospherical points, leading to duplicated Voronoi vertices.
By default, 'QJn' uses a fixed random number seed. To use time as the random number seed, select 'QR-1'. The summary ('s') will show the selected seed as 'QR-n'.
With 'QJn', Qhull does not error on degenerate hyperplane computations. Except for Delaunay and Voronoi computations, Qhull does not error on coplanar points.
Use option 'FO' to display the selected options. Option 'FO' displays the joggle and the joggle seed. If Qhull restarts, it will redisplay the options.
Use option 'TRn' to estimate the probability that Qhull will fail for a given 'QJn'.
Qhull reports the maximum outer plane in its summary ('s'). With option 'Qm', Qhull does not process points that are below the current, maximum outer plane. This is equivalent to always adjusting 'Wn ' to the maximum distance of a coplanar point to a facet. It is ignored for points above the upper convex hull of a Delaunay triangulation. Option 'Qm' is no longer important for merging.
Normally, Qhull processes the furthest point of a facet's outside points. Option 'Qr' instead selects a random outside point for processing. This makes Qhull equivalent to the randomized incremental algorithms.
The original randomization algorithm by Clarkson and Shor ['89] used a conflict list which is equivalent to Qhull's outside set. Later randomized algorithms retained the previously constructed facets.
To compare Qhull to the randomized algorithms with option 'Qr', compare "hyperplanes constructed" and "distance tests". Qhull does not report CPU time because the randomization is inefficient.
Option 'QRn' randomly rotates the input. For Delaunay triangulations (qdelaunay or qvoronoi), it rotates the lifted points about the last axis.
If n=0, use time as the random number seed. If n>0, use n as the random number seed. If n=-1, don't rotate but use time as the random number seed. If n<-1, don't rotate but use n as the random number seed.
Qhull constructs an initial simplex from d+1 points. It selects points with the maximum and minimum coordinates and non-zero determinants. If this fails, it searches all other points. In 8-d and higher, Qhull selects points with the minimum x or maximum coordinate (see qh_initialvertices in poly2.c ). It rejects points with nearly zero determinants. This should work for almost all input sets.
If Qhull can not construct an initial simplex, it reports a descriptive message. Usually, the point set is degenerate and one or more dimensions should be removed ('Qbk:0Bk:0'). If not, use option 'Qs'. It performs an exhaustive search for the best initial simplex. This is expensive is high dimensions.
By default, qhull merges facets to handle precision errors. This produces non-simplicial facets (e.g., the convex hull of a cube has 6 square facets). Each facet is non-simplicial because it has four vertices.
Use option 'Qt' to triangulate all non-simplicial facets before generating results. Alternatively, use joggled input ('QJ') to prevent non-simplical facets. Unless 'Pp' is set, qhull produces a warning if 'QJ' and 'Qt' are used together.
For Delaunay triangulations (qdelaunay), triangulation occurs after lifting the input sites to a paraboloid and computing the convex hull.
Option 'Qt' is deprecated for Voronoi diagrams (qvoronoi). It triangulates cospherical points, leading to duplicated Voronoi vertices.
Option 'Qt' may produce degenerate facets with zero area.
Facet area and hull volumes may differ with and without 'Qt'. The triangulations are different and different triangles may be ignored due to precision errors.
With sufficient merging, the ridges of a non-simplicial facet may share more than two neighboring facets. If so, their triangulation ('Qt') will fail since two facets have the same vertex set.
When computing a Delaunay triangulation (qdelaunay or qvoronoi), Qhull computes both the the convex hull of points on a paraboloid. It normally prints facets of the lower hull. These correspond to the Delaunay triangulation. With option 'Qu', Qhull prints facets of the upper hull. These correspond to the furthest-site Delaunay triangulation and the furthest-site Voronoi diagram.
Option 'qhull d Qbb Qu Qg' may improve the speed of option 'Qu'. If you use the Qhull library, a faster method is 1) use Qhull to compute the convex hull of the input sites; 2) take the extreme points (vertices) of the convex hull; 3) add one interior point (e.g., 'FV', the average of d extreme points); 4) run 'qhull d Qbb Qu' or 'qhull v Qbb Qu' on these points.
Normally, Qhull tests all facet neighbors for convexity. Non-neighboring facets which share a vertex may not satisfy the convexity constraint. This occurs when a facet undercuts the centrum of another facet. They should still be convex. Option 'Qv' extends Qhull's convexity testing to all neighboring facets of each vertex. The extra testing occurs after the hull is constructed..
With option 'QVn', a facet is good ('Qg', 'Pg') if one of its vertices is point n. If n<0, a good facet does not include point n.
If options 'PG' and 'Qg' are not set, option 'Pg' (print only good) is automatically set.
Option 'QVn' behaves oddly with options 'Fx' and 'qvoronoi Fv'.
If used with option 'Qg' (only process good facets), point n is either in the initial simplex or it is the first point added to the hull. Options 'QVn Qg' require either 'QJ' or 'Q0' (no merging).
Option 'Qx' performs exact merges while building the hull. Option 'Qx' is set by default in 5-d and higher. Use option 'Q0' to not use 'Qx' by default. Unless otherwise specified, option 'Qx' sets option 'C-0'.
The "exact" merges are merging a point into a coplanar facet (defined by 'Vn ', 'Un', and 'C-n'), merging concave facets, merging duplicate ridges, and merging flipped facets. Coplanar merges and angle coplanar merges ('A-n') are not performed. Concavity testing is delayed until a merge occurs.
After the hull is built, all coplanar merges are performed (defined by 'C-n' and 'A-n'), then post-merges are performed (defined by 'Cn' and 'An'). If facet progress is logged ('TFn'), Qhull reports each phase and prints intermediate summaries and statistics ('Ts').
Without 'Qx' in 5-d and higher, options 'C-n' and 'A-n' may merge too many facets. Since redundant vertices are not removed effectively, facets become increasingly wide.
Option 'Qx' may report a wide facet. With 'Qx', coplanar facets are not merged. This can produce a "dent" in an intermediate hull. If a point is partitioned into a dent and it is below the surrounding facets but above other facets, one or more wide facets will occur. In practice, this is unlikely. To observe this effect, run Qhull with option 'Q6' which doesn't pre-merge concave facets. A concave facet makes a large dent in the intermediate hull.
Option 'Qx' may set an outer plane below one of the input points. A coplanar point may be assigned to the wrong facet because of a "dent" in an intermediate hull. After constructing the hull, Qhull double checks all outer planes with qh_check_maxout in poly2.c . If a coplanar point is assigned to the wrong facet, qh_check_maxout may reach a local maximum instead of locating all coplanar facets. This appears to be unlikely.
Option 'Qz' adds a point above the paraboloid of lifted sites for a Delaunay triangulation. It allows the Delaunay triangulation of cospherical sites. It reduces precision errors for nearly cospherical sites.
Turn off default merge options 'C-0' and 'Qx'.
With 'Q0' and without other pre-merge options, Qhull ignores precision issues while constructing the convex hull. This may lead to precision errors. If so, a descriptive warning is generated. See Precision issues.
Qhull sorts the coplanar facets before picking a subset of the facets to merge. It merges concave and flipped facets first. Then it merges facets that meet at a steep angle. With 'Q1', Qhull sorts merges by type (coplanar, angle coplanar, concave) instead of by angle. This may make the facets wider.
With 'Q2', Qhull merges all facets at once instead of performing merges in independent sets. This may make the facets wider.
With 'Q3', Qhull does not remove redundant vertices. In 6-d and higher, Qhull never removes redundant vertices (since vertices are highly interconnected). Option 'Q3' may be faster, but it may result in wider facets. Its effect is easiest to see in 3-d and 4-d.
With 'Q4', Qhull avoids merges of an old facet into a new facet. This sometimes improves facet width and sometimes makes it worse.
When merging facets or approximating a hull, Qhull tests coplanar points and outer planes after constructing the hull. It does this by performing a directed search (qh_findbest in geom.c). It includes points that are just inside the hull.
With options 'Q5' or 'Po', Qhull does not test outer planes. The maximum outer plane is used instead. Coplanar points ('Qc') are defined by 'Un'. An input point may be outside of the maximum outer plane (this appears to be unlikely). An interior point may be above 'Un' from a hyperplane.
Option 'Q5' may be used if outer planes are not needed. Outer planes are needed for options 's', 'G', 'Go ', 'Fs', 'Fo', 'FF', and 'f'.
With 'Q6', Qhull does not pre-merge concave or coplanar facets. This demonstrates the effect of "dents" when using 'Qx'.
With 'Q7', Qhull processes facets in depth-first order instead of breadth-first order. This may increase the locality of reference in low dimensions. If so, Qhull may be able to use virtual memory effectively.
In 5-d and higher, many facets are visible from each unprocessed point. So each iteration may access a large proportion of allocated memory. This makes virtual memory ineffectual. Once real memory is used up, Qhull will spend most of its time waiting for I/O.
Under 'Q7', Qhull runs slower and the facets may be wider.
With 'Q8' and merging, Qhull does not process interior points that are near to a facet (as defined by qh_RATIOnearInside in user.h). This avoids partitioning steps. It may miss a coplanar point when adjusting outer hulls in qh_check_maxout(). The best value for qh_RATIOnearInside is not known. Options 'Q8 Qc' may be sufficient.
With 'Q9', Qhull processes the furthest point of all outside sets. This may reduce precision problems. The furthest point of all outside sets is not necessarily the furthest point from the convex hull.
With 'Q10', Qhull does not special-case narrow distributions. See Limitations of merged facets for more information.
Use 'Q11' if you use the Qhull library to add points incrementally and call qh_triangulate() after each point. Otherwise, Qhull will report an error when it tries to merge and replace a tricoplanar facet.
With sufficient merging and new points, option 'Q11' may lead to precision problems such as duplicate ridges and concave facets. For example, if qh_triangulate() is added to qh_addpoint(), RBOX 1000 s W1e-12 t1001813667 P0 | QHULL d Q11 Tv, reports an error due to a duplicate ridge.
In 3-d and higher Delaunay Triangulations or 4-d and higher convex hulls, multiple, nearly coincident points may lead to very wide facets. An error is reported if a merge across a duplicate ridge would increase the facet width by 100x or more.
Use option 'Q12' to log a warning instead of throwing an error.
For Delaunay triangulations, a bounding box may alleviate this error (e.g., rbox 500 C1,1E-13 t c G1 | qhull d). This avoids the ill-defined edge between upper and lower convex hulls. The problem will be fixed in a future release of Qhull.
To demonstrate the problem, use rbox option 'Cn,r,m' to generate nearly coincident points.
For more information, see "Nearly coincident points on an edge"
in Home page for Qhull
Up: Qhull manual: Table of Contents
To: Programs
• Options
• Output
• Formats
• Geomview
• Print
• Qhull
• Precision
• Trace
• Functions
The Geometry Center
Home Page
Comments to: qhull@qhull.org
Created: Sept. 25, 1995 --- Last modified: see top