NAME
qhull - convex hull, Delaunay triangulation, Voronoi diagram, halfspace
intersection about a point, hull volume, facet area
SYNOPSIS
qhull- compute convex hulls and related structures
input (stdin): dimension, #points, point coordinates
first comment (non-numeric) is listed in the summary
halfspace: use dim plus one with offsets after coefficients
options (qh-quick.htm):
d - Delaunay triangulation by lifting points to a paraboloid
v - Voronoi diagram via the Delaunay triangulation
H1,1 - Halfspace intersection about [1,1,0,...]
d Qu - Furthest-site Delaunay triangulation (upper convex hull)
v Qu - Furthest-site Voronoi diagram
Qt - triangulated output
QJ - Joggle the input to avoid precision problems
. - concise list of all options
- - one-line description of all options
Output options (subset):
FA - compute total area and volume
Fx - extreme points (convex hull vertices)
G - Geomview output (2-d, 3-d and 4-d)
Fp - halfspace intersection coordinates
m - Mathematica output (2-d and 3-d)
n - normals with offsets
o - OFF file format (if Voronoi, outputs regions)
TO file- output results to file, may be enclosed in single quotes
f - print all fields of all facets
s - summary of results (default)
Tv - verify result: structure, convexity, and point inclusion
p - vertex coordinates (centers for Voronoi)
i - vertices incident to each facet
example:
rbox 1000 s | qhull Tv s FA
- html manual: index.htm
- installation: README.txt
- see also: COPYING.txt, REGISTER.txt, Changes.txt
- WWW: <http://www.qhull.org>
- CVS: <http://savannah.nongnu.org/projects/qhull/>
- mirror:
<http://www6.uniovi.es/ftp/pub/mirrors/geom.umn.edu/software/ghindex.html>
- news: <http://www.qhull.org/news>
- Geomview: <http://www.geomview.org>
- news group: <news:comp.graphics.algorithms>
- FAQ: <http://exaflop.org/docs/cgafaq/cg.html>
- email: qhull@qhull.org
- bug reports: qhull_bug@qhull.org
The sections are:
- INTRODUCTION
- DESCRIPTION, a description of Qhull
- IMPRECISION, how Qhull handles imprecision
- OPTIONS
- Input and output options
- Additional input/output formats
- Precision options
- Geomview options
- Print options
- Qhull options
- Trace options
- BUGS
- E-MAIL
- SEE ALSO
- AUTHORS
- ACKNOWLEGEMENTS
This man page briefly describes all Qhull options. Please report any
mismatches with Qhull’s html manual (index.htm).
INTRODUCTION
Qhull is a general dimension code for computing convex hulls, Delaunay
triangulations, Voronoi diagram, furthest‐site Voronoi diagram,
furthest‐site Delaunay triangulations, and halfspace intersections
about a point. It implements the Quickhull algorithm for computing the
convex hull. Qhull handles round‐off errors from floating point
arithmetic. It can approximate a convex hull.
The program includes options for hull volume, facet area, partial
hulls, input transformations, randomization, tracing, multiple output
formats, and execution statistics. The program can be called from
within your application. You can view the results in 2‐d, 3‐d and 4‐d
with Geomview.
DESCRIPTION
The format of input is the following: first line contains the
dimension, second line contains the number of input points, and point
coordinates follow. The dimension and number of points can be
reversed. Comments and line breaks are ignored. A comment starts with
a non‐numeric character and continues to the end of line. The first
comment is reported in summaries and statistics. Error reporting is
better if there is one point per line.
The default printout option is a short summary. There are many other
output formats.
Qhull implements the Quickhull algorithm for convex hull. This
algorithm combines the 2‐d Quickhull algorithm with the n‐d
beneath‐beyond algorithm [c.f., Preparata & Shamos ’85]. It is similar
to the randomized algorithms of Clarkson and others [Clarkson et al.
’93]. The main advantages of Quickhull are output sensitive
performance, reduced space requirements, and automatic handling of
precision problems.
The data structure produced by Qhull consists of vertices, ridges, and
facets. A vertex is a point of the input set. A ridge is a set of d
vertices and two neighboring facets. For example in 3‐d, a ridge is an
edge of the polyhedron. A facet is a set of ridges, a set of
neighboring facets, a set of incident vertices, and a hyperplane
equation. For simplicial facets, the ridges are defined by the
vertices and neighboring facets. When Qhull merges two facets, it
produces a non‐simplicial facet. A non‐simplicial facet has more than
d neighbors and may share more than one ridge with a neighbor.
IMPRECISION
Since Qhull uses floating point arithmetic, roundoff error may occur
for each calculation. This causes problems for most geometric
algorithms.
Qhull automatically sets option ’C-0’ in 2‐d, 3‐d, and 4‐d, or option
’Qx’ in 5‐d and higher. These options handle precision problems by
merging facets. Alternatively, use option ’QJ’ to joggle the input.
With ’C-0’, Qhull merges non‐convex facets while constructing the hull.
The remaining facets are clearly convex. With ’Qx’, Qhull merges
coplanar horizon facets, flipped facets, concave facets and duplicated
ridges. It merges coplanar facets after constructing the hull. With
’Qx’, coplanar points may be missed, but it appears to be unlikely.
To guarantee triangular output, joggle the input with option ’QJ’.
Facet merging will not occur.
OPTIONS
To get a list of the most important options, execute ’qhull’ by itself.
To get a complete list of options, execute ’qhull -’. To get a
complete, concise list of options, execute ’qhull .’.
Options can be in any order. Capitalized options take an argument
(except ’PG’ and ’F’ options). Single letters are used for output
formats and precision constants. The other options are grouped into
menus for other output formats (’F’), Geomview output (’G’), printing
(’P’), Qhull control (’Q’), and tracing (’T’).
Main options:
default
Compute the convex hull of the input points. Report a summary
of the result.
d Compute the Delaunay triangulation by lifting the input points
to a paraboloid. The ’o’ option prints the input points and
facets. The ’QJ’ option guarantees triangular output. The ’Ft’
option prints a triangulation. It adds points (the centrums) to
non‐simplicial facets.
v Compute the Voronoi diagram from the Delaunay triangulation.
The ’p’ option prints the Voronoi vertices. The ’o’ option
prints the Voronoi vertices and the vertices in each Voronoi
region. It lists regions in site ID order. The ’Fv’ option
prints each ridge of the Voronoi diagram. The first or zero’th
vertex indicates the infinity vertex. Its coordinates are
qh_INFINITE (-10.101). It indicates unbounded Voronoi regions
or degenerate Delaunay triangles.
Hn,n,...
Compute halfspace intersection about [n,n,0,...]. The input is
a set of halfspaces defined in the same format as ’n’, ’Fo’, and
’Fi’. Use ’Fp’ to print the intersection points. Use ’Fv’ to
list the intersection points for each halfspace. The other
output formats display the dual convex hull.
The point [n,n,n,...] is a feasible point for the halfspaces,
i.e., a point that is inside all of the halfspaces (Hx+b <= 0).
The default coordinate value is 0.
The input may start with a feasible point. If so, use ’H’ by
itself. The input starts with a feasible point when the first
number is the dimension, the second number is "1", and the
coordinates complete a line. The ’FV’ option produces a
feasible point for a convex hull.
d Qu Compute the furthest‐site Delaunay triangulation from the upper
convex hull. The ’o’ option prints the input points and facets.
The ’QJ’ option guarantees triangular otuput. You can also use
’Ft’ to triangulate via the centrums of non‐simplicial facets.
v Qu Compute the furthest‐site Voronoi diagram. The ’p’ option
prints the Voronoi vertices. The ’o’ option prints the Voronoi
vertices and the vertices in each Voronoi region. The ’Fv’
option prints each ridge of the Voronoi diagram. The first or
zero’th vertex indicates the infinity vertex at infinity. Its
coordinates are qh_INFINITE (-10.101). It indicates unbounded
Voronoi regions and degenerate Delaunay triangles.
Input/Output options:
f Print out all facets and all fields of each facet.
G Output the hull in Geomview format. For imprecise hulls,
Geomview displays the inner and outer hull. Geomview can also
display points, ridges, vertices, coplanar points, and facet
intersections. See below for a list of options.
For Delaunay triangulations, ’G’ displays the corresponding
paraboloid. For halfspace intersection, ’G’ displays the dual
polytope.
i Output the incident vertices for each facet. Qhull prints the
number of facets followed by the vertices of each facet. One
facet is printed per line. The numbers are the 0‐relative
indices of the corresponding input points. The facets are
oriented.
In 4d and higher, Qhull triangulates non‐simplicial facets.
Each apex (the first vertex) is a created point that corresponds
to the facet’s centrum. Its index is greater than the indices
of the input points. Each base corresponds to a simplicial
ridge between two facets. To print the vertices without
triangulation, use option ’Fv’.
m Output the hull in Mathematica format. Qhull writes a
Mathematica file for 2‐d and 3‐d convex hulls and for 2‐d
Delaunay triangulations. Qhull produces a list of objects that
you can assign to a variable in Mathematica, for example: "list=
<< <outputfilename> ". If the object is 2‐d, it can be
visualized by "Show[Graphics[list]] ". For 3‐d objects the
command is "Show[Graphics3D[list]]".
n Output the normal equation for each facet. Qhull prints the
dimension (plus one), the number of facets, and the normals for
each facet. The facet’s offset follows its normal coefficients.
o Output the facets in OFF file format. Qhull prints the
dimension, number of points, number of facets, and number of
ridges. Then it prints the coordinates of the input points and
the vertices for each facet. Each facet is on a separate line.
The first number is the number of vertices. The remainder are
the indices of the corresponding points. The vertices are
oriented in 2‐d, 3‐d, and in simplicial facets.
For 2‐d Voronoi diagrams, the vertices are sorted by adjacency,
but not oriented. In 3‐d and higher, the Voronoi vertices are
sorted by index. See the ’v’ option for more information.
p Output the coordinates of each vertex point. Qhull prints the
dimension, the number of points, and the coordinates for each
vertex. With the ’Gc’ and ’Gi’ options, it also prints coplanar
and interior points. For Voronoi diagrams, it prints the
coordinates of each Voronoi vertex.
s Print a summary to stderr. If no output options are specified
at all, a summary goes to stdout. The summary lists the number
of input points, the dimension, the number of vertices in the
convex hull, the number of facets in the convex hull, the number
of good facets (if ’Pg’), and statistics.
The last two statistics (if needed) measure the maximum distance
from a point or vertex to a facet. The number in parenthesis
(e.g., 2.1x) is the ratio between the maximum distance and the
worst‐case distance due to merging two simplicial facets.
Precision options
An Maximum angle given as a cosine. If the angle between a pair of
facet normals is greater than n, Qhull merges one of the facets
into a neighbor. If ’n’ is negative, Qhull tests angles after
adding each point to the hull (pre‐merging). If ’n’ is
positive, Qhull tests angles after constructing the hull
(post‐merging). Both pre‐ and post‐merging can be defined.
Option ’C0’ or ’C-0’ is set if the corresponding ’Cn’ or ’C-n’
is not set. If ’Qx’ is set, then ’A-n’ and ’C-n’ are checked
after the hull is constructed and before ’An’ and ’Cn’ are
checked.
Cn Centrum radius. If a centrum is less than n below a neighboring
facet, Qhull merges one of the facets. If ’n’ is negative or
’-0’, Qhull tests and merges facets after adding each point to
the hull. This is called "pre‐merging". If ’n’ is positive,
Qhull tests for convexity after constructing the hull
("post‐merging"). Both pre‐ and post‐merging can be defined.
For 5‐d and higher, ’Qx’ should be used instead of ’C-n’.
Otherwise, most or all facets may be merged together.
En Maximum roundoff error for distance computations.
Rn Randomly perturb distance computations up to +/- n * max_coord.
This option perturbs every distance, hyperplane, and angle
computation. To use time as the random number seed, use option
’QR-1’.
Vn Minimum distance for a facet to be visible. 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 round‐off
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 (’Wn’), the
maximum, default value for ’Vn’ is ’Wn’.
Un Maximum distance below a facet for a point to be coplanar to the
facet. The default value is ’Vn’.
Wn Minimum outside width of the hull. 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’. The normal value for ’Wn’ is ’En’. If the
user specifies pre‐merging and does not set ’Wn’, than ’Wn’ is
set to the premerge ’Cn’ and maxcoord*(1-An).
Additional input/output formats
Fa Print area for each facet. For Delaunay triangulations, the
area is the area of the triangle. For Voronoi diagrams, the
area is the area of the dual facet. Use ’PAn’ for printing the
n largest facets, and option ’PFn’ for printing facets larger
than ’n’.
The area for non‐simplicial facets is the sum of the areas for
each ridge to the centrum. Vertices far below the facet’s
hyperplane are ignored. The reported area may be significantly
less than the actual area.
FA Compute the total area and volume for option ’s’. It is an
approximation for non‐simplicial facets (see ’Fa’).
Fc Print coplanar points for each facet. The output starts with
the number of facets. Then each facet is printed one per line.
Each line is the number of coplanar points followed by the point
ids. Option ’Qi’ includes the interior points. Each coplanar
point (interior point) is assigned to the facet it is furthest
above (resp., least below).
FC Print centrums for each facet. The output starts with the
dimension followed by the number of facets. Then each facet
centrum is printed, one per line.
Fd Read input in cdd format with homogeneous points. The input
starts with comments. The first comment is reported in the
summary. Data starts after a "begin" line. The next line is
the number of points followed by the dimension+1 and "real" or
"integer". Then the points are listed with a leading "1" or
"1.0". The data ends with an "end" line.
For halfspaces (’Fd Hn,n,...’), the input format is the same.
Each halfspace starts with its offset. The sign of the offset
is the opposite of Qhull’s convention.
FD Print normals (’n’, ’Fo’, ’Fi’) or points (’p’) in cdd format.
The first line is the command line that invoked Qhull. Data
starts with a "begin" line. The next line is the number of
normals or points followed by the dimension+1 and "real". Then
the normals or points are listed with the offset before the
coefficients. The offset for points is 1.0. The offset for
normals has the opposite sign. The data ends with an "end"
line.
FF Print facets (as in ’f’) without printing the ridges.
Fi Print inner planes for each facet. The inner plane is below all
vertices.
Fi Print separating hyperplanes for bounded, inner regions of the
Voronoi diagram. The first line is the number of ridges. Then
each hyperplane is printed, one per line. A line starts with
the number of indices and floats. The first pair lists adjacent
input sites, the next d floats are the normalized coefficients
for the hyperplane, and the last float is the offset. The
hyperplane is oriented toward ’QVn’ (if defined), or the first
input site of the pair. Use ’Tv’ to verify that the hyperplanes
are perpendicular bisectors. Use ’Fo’ for unbounded regions,
and ’Fv’ for the corresponding Voronoi vertices.
FI Print facet identifiers.
Fm Print number of merges for each facet. At most 511 merges are
reported for a facet. See ’PMn’ for printing the facets with
the most merges.
FM Output the hull in Maple format. Qhull writes a Maple file for
2‐d and 3‐d convex hulls and for 2‐d Delaunay triangulations.
Qhull produces a ’.mpl’ file for displaying with display3d().
Fn Print neighbors for each facet. The output starts with the
number of facets. Then each facet is printed one per line.
Each line is the number of neighbors followed by an index for
each neighbor. The indices match the other facet output
formats.
A negative index indicates an unprinted facet due to printing
only good facets (’Pg’). It is the negation of the facet’s ID
(option ’FI’). For example, negative indices are used for
facets "at infinity" in the Delaunay triangulation.
FN Print vertex neighbors or coplanar facet for each point. The
first line is the number of points. Then each point is printed,
one per line. If the point is coplanar, the line is "1"
followed by the facet’s ID. If the point is not a selected
vertex, the line is "0". Otherwise, each line is the number of
neighbors followed by the corresponding facet indices (see
’Fn’).
Fo Print outer planes for each facet in the same format as ’n’.
The outer plane is above all points.
Fo Print separating hyperplanes for unbounded, outer regions of the
Voronoi diagram. The first line is the number of ridges. Then
each hyperplane is printed, one per line. A line starts with
the number of indices and floats. The first pair lists adjacent
input sites, the next d floats are the normalized coefficients
for the hyperplane, and the last float is the offset. The
hyperplane is oriented toward ’QVn’ (if defined), or the first
input site of the pair. Use ’Tv’ to verify that the hyperplanes
are perpendicular bisectors. Use ’Fi’ for bounded regions, and
’Fv’ for the corresponding Voronoi vertices.
FO List all options to stderr, including the default values.
Additional ’FO’s are printed to stdout.
Fp Print points for halfspace intersections (option ’Hn,n,...’).
Each intersection corresponds to a facet of the dual polytope.
The "infinity" point [-10.101,-10.101,...] indicates an
unbounded intersection.
FP For each coplanar point (’Qc’) print the point ID of the nearest
vertex, the point ID, the facet ID, and the distance.
FQ Print command used for qhull and input.
Fs Print a summary. The first line consists of the number of
integers ("8"), followed by the dimension, the number of points,
the number of vertices, the number of facets, the number of
vertices selected for output, the number of facets selected for
output, the number of coplanar points selected for output,
number of simplicial, unmerged facets in output
The second line consists of the number of reals ("2"), followed
by the maxmimum offset to an outer plane and and minimum offset
to an inner plane. Roundoff is included. Later versions of
Qhull may produce additional integers or reals.
FS Print the size of the hull. The first line consists of the
number of integers ("0"). The second line consists of the
number of reals ("2"), followed by the total facet area, and the
total volume. Later versions of Qhull may produce additional
integers or reals.
The total volume measures the volume of the intersection of the
halfspaces defined by each facet. Both area and volume are
approximations for non‐simplicial facets. See option ’Fa’.
Ft Print a triangulation with added points for non‐simplicial
facets. The first line is the dimension and the second line is
the number of points and the number of facets. The points
follow, one per line, then the facets follow as a list of point
indices. With option ’Qz’, the points include the
point‐at‐infinity.
Fv Print vertices for each facet. The first line is the number of
facets. Then each facet is printed, one per line. Each line is
the number of vertices followed by the corresponding point ids.
Vertices are listed in the order they were added to the hull
(the last one is first).
Fv Print all ridges of a Voronoi diagram. The first line is the
number of ridges. Then each ridge is printed, one per line. A
line starts with the number of indices. The first pair lists
adjacent input sites, the remaining indices list Voronoi
vertices. Vertex ’0’ indicates the vertex‐at‐infinity (i.e., an
unbounded ray). In 3‐d, the vertices are listed in order. See
’Fi’ and ’Fo’ for separating hyperplanes.
FV Print average vertex. The average vertex is a feasible point
for halfspace intersection.
Fx List extreme points (vertices) of the convex hull. The first
line is the number of points. The other lines give the indices
of the corresponding points. The first point is ’0’. In 2‐d,
the points occur in counter‐clockwise order; otherwise they
occur in input order. For Delaunay triangulations, ’Fx’ lists
the extreme points of the input sites. The points are
unordered.
Geomview options
G Produce a file for viewing with Geomview. Without other
options, Qhull displays edges in 2‐d, outer planes in 3‐d, and
ridges in 4‐d. A ridge can be explicit or implicit. An
explicit ridge is a dim-1 dimensional simplex between two
facets. In 4‐d, the explicit ridges are triangles. When
displaying a ridge in 4‐d, Qhull projects the ridge’s vertices
to one of its facets’ hyperplanes. Use ’Gh’ to project ridges
to the intersection of both hyperplanes.
Ga Display all input points as dots.
Gc Display the centrum for each facet in 3‐d. The centrum is
defined by a green radius sitting on a blue plane. The plane
corresponds to the facet’s hyperplane. The radius is defined by
’C-n’ or ’Cn’.
GDn Drop dimension n in 3‐d or 4‐d. The result is a 2‐d or 3‐d
object.
Gh Display hyperplane intersections in 3‐d and 4‐d. In 3‐d, the
intersection is a black line. It lies on two neighboring
hyperplanes (c.f., the blue squares associated with centrums
(’Gc’)). In 4‐d, the ridges are projected to the intersection
of both hyperplanes.
Gi Display inner planes in 2‐d and 3‐d. The inner plane of a facet
is below all of its vertices. It is parallel to the facet’s
hyperplane. The inner plane’s color is the opposite
(1-r,1-g,1-b) of the outer plane. Its edges are determined by
the vertices.
Gn Do not display inner or outer planes. By default, Geomview
displays the precise plane (no merging) or both inner and output
planes (merging). Under merging, Geomview does not display the
inner plane if the the difference between inner and outer is too
small.
Go Display outer planes in 2‐d and 3‐d. The outer plane of a facet
is above all input points. It is parallel to the facet’s
hyperplane. Its color is determined by the facet’s normal, and
its edges are determined by the vertices.
Gp Display coplanar points and vertices as radii. A radius defines
a ball which corresponds to the imprecision of the point. The
imprecision is the maximum of the roundoff error, the centrum
radius, and maxcoord * (1-An). It is at least 1/20’th of the
maximum coordinate, and ignores post‐merging if pre‐merging is
done.
Gr Display ridges in 3‐d. A ridge connects the two vertices that
are shared by neighboring facets. Ridges are always displayed
in 4‐d.
Gt A 3‐d Delaunay triangulation looks like a convex hull with
interior facets. Option ’Gt’ removes the outside ridges to
reveal the outermost facets. It automatically sets options ’Gr’
and ’GDn’.
Gv Display vertices as spheres. The radius of the sphere
corresponds to the imprecision of the data. See ’Gp’ for
determining the radius.
Print options
PAn Only the n largest facets are marked good for printing. Unless
’PG’ is set, ’Pg’ is automatically set.
Pdk:n Drop facet from output if normal[k] <= n. The option ’Pdk’ uses
the default value of 0 for n.
PDk:n Drop facet from output if normal[k] >= n. The option ’PDk’ uses
the default value of 0 for n.
PFn Only facets with area at least ’n’ are marked good for printing.
Unless ’PG’ is set, ’Pg’ is automatically set.
Pg Print only good facets. A good facet is either visible from a
point (the ’QGn’ option) or includes a point (the ’QVn’ option).
It also meets the requirements of ’Pdk’ and ’PDk’ options.
Option ’Pg’ is automatically set for options ’PAn’ and ’PFn’.
PG Print neighbors of good facets.
PMn Only the n facets with the most merges are marked good for
printing. Unless ’PG’ is set, ’Pg’ is automatically set.
Po Force output despite precision problems. Verify (’Tv’) does not
check coplanar points. Flipped facets are reported and concave
facets are counted. If ’Po’ is used, points are not partitioned
into flipped facets and a flipped facet is always visible to a
point. Also, if an error occurs before the completion of Qhull
and tracing is not active, ’Po’ outputs a neighborhood of the
erroneous facets (if any).
Pp Do not report precision problems.
Qhull control options
Qbk:0Bk:0
Drop dimension k from the input points. This allows the user to
take convex hulls of sub‐dimensional objects. It happens before
the Delaunay and Voronoi transformation.
QbB Scale the input points to fit the unit cube. After scaling, the
lower bound will be -0.5 and the upper bound +0.5 in all
dimensions. 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.
Qbb Scale the last coordinate to [0, m] where m is the maximum
absolute value of the other coordinates. For Delaunay and
Voronoi diagrams, scaling happens after projection to the
paraboloid. It reduces roundoff error for inputs with integer
coordinates. Under precise arithmetic, scaling does not change
the topology of the convex hull.
Qbk:n Scale the k’th coordinate of the input points. After scaling,
the lower bound of the input points will be n. ’Qbk’ scales to
-0.5.
QBk:n Scale the k’th coordinate of the input points. After scaling,
the upper bound will be n. ’QBk’ scales to +0.5.
Qc Keep coplanar points with the nearest facet. Output formats
’p’, ’f’, ’Gp’, ’Fc’, ’FN’, and ’FP’ will print the points.
Qf Partition points to the furthest outside facet.
Qg Only build good facets. With the ’Qg’ option, Qhull will only
build those facets that it needs to determine the good facets in
the output. See ’QGn’, ’QVn’, and ’PdD’ for defining good
facets, and ’Pg’ and ’PG’ for printing good facets and their
neighbors.
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).
Qi Keep interior points with the nearest facet. Output formats
’p’, ’f’, ’Gp’, ’FN’, ’FP’, and ’Fc’ will print the points.
QJn Joggle each input coordinate by adding a random number in
[-n,n]. If a precision error occurs, then qhull increases n and
tries again. It does not increase n beyond a certain value, and
it stops after a certain number of attempts [see user.h].
Option ’QJ’ selects a default value for n. The output will be
simplicial. For Delaunay triangulations, ’QJn’ sets ’Qbb’ to
scale the last coordinate (not if ’Qbk:n’ or ’QBk:n’ is set).
See also ’Qt’.
Qm Only process points that would otherwise increase max_outside.
Other points are treated as coplanar or interior points.
Qr Process random outside points instead of furthest ones. This
makes Qhull equivalent to the randomized incremental algorithms.
CPU time is not reported since the randomization is inefficient.
QRn Randomly rotate the input points. 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.
For Delaunay triangulations (’d’ and ’v’), rotate about the last
axis.
Qs Search all points for the initial simplex.
Qt Triangulated output. Triangulate all non‐simplicial facets.
See also ’QJ’.
Qv Test vertex neighbors for convexity after post‐merging. To use
the ’Qv’ option, you also need to set a merge option (e.g., ’Qx’
or ’C-0’).
QVn A good facet (see ’Qg’ and ’Pg’) includes point n. If n<0, then
a good facet does not include point n. The point is either in
the initial simplex or it is the first point added to the hull.
Option ’QVn’ may not be used with merging.
Qx Perform exact merges while building the hull. 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’).
Qz Add a point "at infinity" that is above the paraboloid for
Delaunay triangulations and Voronoi diagrams. This reduces
precision problems and allows the triangulation of cospherical
points.
Qhull experiments and speedups
Q0 Turn off pre‐merging as a default option. With ’Q0’/’Qx’ and
without explicit 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.
Q1 With ’Q1’, Qhull sorts merges by type (coplanar, angle coplanar,
concave) instead of by angle.
Q2 With ’Q2’, Qhull merges all facets at once instead of using
independent sets of merges and then retesting.
Q3 With ’Q3’, Qhull does not remove redundant vertices.
Q4 With ’Q4’, Qhull avoids merges of an old facet into a new facet.
Q5 With ’Q5’, Qhull does not correct outer planes at the end. The
maximum outer plane is used instead.
Q6 With ’Q6’, Qhull does not pre‐merge concave or coplanar facets.
Q7 With ’Q7’, Qhull processes facets in depth‐first order instead
of breadth‐first order.
Q8 With ’Q8’ and merging, Qhull does not retain near‐interior
points for adjusting outer planes. ’Qc’ will probably retain
all points that adjust outer planes.
Q9 With ’Q9’, Qhull processes the furthest of all outside sets at
each iteration.
Q10 With ’Q10’, Qhull does not use special processing for narrow
distributions.
Q11 With ’Q11’, Qhull copies normals and recompute centrums for
tricoplanar facets.
Trace options
Tn Trace at level n. Qhull includes full execution tracing. ’T-1’
traces events. ’T1’ traces the overall execution of the
program. ’T2’ and ’T3’ trace overall execution and geometric
and topological events. ’T4’ traces the algorithm. ’T5’
includes information about memory allocation and Gaussian
elimination.
Tc Check frequently during execution. This will catch most
inconsistency errors.
TCn Stop Qhull after building the cone of new facets for point n.
The output for ’f’ includes the cone and the old hull. See also
’TVn’.
TFn Report progress whenever more than n facets are created During
post‐merging, ’TFn’ reports progress after more than n/2 merges.
TI file
Input data from ’file’. The filename may not include spaces or
quotes.
TO file
Output results to ’file’. The name may be enclosed in single
quotes.
TPn Turn on tracing when point n is added to the hull. Trace
partitions of point n. If used with TWn, turn off tracing after
adding point n to the hull.
TRn Rerun qhull n times. Usually used with ’QJn’ to determine the
probability that a given joggle will fail.
Ts Collect statistics and print to stderr at the end of execution.
Tv Verify the convex hull. This checks the topological structure,
facet convexity, and point inclusion. If precision problems
occurred, facet convexity is tested whether or not ’Tv’ is
selected. Option ’Tv’ does not check point inclusion if forcing
output with ’Po’, or if ’Q5’ is set.
For point inclusion testing, Qhull verifies that all points are
below all outer planes (facet->maxoutside). Point inclusion is
exhaustive if merging or if the facet‐point product is small
enough; otherwise Qhull verifies each point with a directed
search (qh_findbest).
Point inclusion testing occurs after producing output. It
prints a message to stderr unless option ’Pp’ is used. This
allows the user to interrupt Qhull without changing the output.
TVn Stop Qhull after adding point n. If n < 0, stop Qhull before
adding point n. Output shows the hull at this time. See also
’TCn’
TMn Turn on tracing at n’th merge.
TWn Trace merge facets when the width is greater than n.
Tz Redirect stderr to stdout.
BUGS
Please report bugs to Brad Barber at qhull_bug@qhull.org.
If Qhull does not compile, it is due to an incompatibility between your
system and ours. The first thing to check is that your compiler is
ANSI standard. If it is, check the man page for the best options, or
find someone to help you. If you locate the cause of your problem,
please send email since it might help others.
If Qhull compiles but crashes on the test case (rbox D4), there’s still
incompatibility between your system and ours. Typically it’s been due
to mem.c and memory alignment. You can use qh_NOmem in mem.h to turn
off memory management. Please let us know if you figure out how to fix
these problems.
If you do find a problem, try to simplify it before reporting the
error. Try different size inputs to locate the smallest one that
causes an error. You’re welcome to hunt through the code using the
execution trace as a guide. This is especially true if you’re
incorporating Qhull into your own program.
When you do report an error, please attach a data set to the end of
your message. This allows us to see the error for ourselves. Qhull is
maintained part‐time.
E‐MAIL
Please send correspondence to qhull@qhull.org and report bugs to
qhull_bug@qhull.org. Let us know how you use Qhull. If you mention it
in a paper, please send the reference and an abstract.
If you would like to get Qhull announcements (e.g., a new version) and
news (any bugs that get fixed, etc.), let us know and we will add you
to our mailing list. If you would like to communicate with other Qhull
users, we will add you to the qhull_users alias. For Internet news
about geometric algorithms and convex hulls, look at
comp.graphics.algorithms and sci.math.num-analysis
SEE ALSO
rbox(1)
Barber, C. B., D.P. Dobkin, and H.T. Huhdanpaa, "The Quickhull
Algorithm for Convex Hulls," ACM Trans. on Mathematical Software,
22(4):469–483, Dec. 1996.
http://www.acm.org/pubs/citations/journals/toms/1996-22-4/p469-barber/
http://citeseer.nj.nec.com.html
Clarkson, K.L., K. Mehlhorn, and R. Seidel, "Four results on randomized
incremental construction," Computational Geometry: Theory and
Applications, vol. 3, p. 185–211, 1993.
Preparata, F. and M. Shamos, Computational Geometry, Springer‐Verlag,
New York, 1985.
AUTHORS
C. Bradford Barber Hannu Huhdanpaa
bradb@qhull.org hannu@qhull.org
c/o The Geometry Center
University of Minnesota
400 Lind Hall
207 Church Street S.E.
Minneapolis, MN 55455
ACKNOWLEDGEMENTS
A special thanks to Albert Marden, Victor Milenkovic, the Geometry
Center, Harvard University, and Endocardial Solutions, Inc. for
supporting this work.
Qhull 1.0 and 2.0 were developed under National Science Foundation
grants NSF/DMS‐8920161 and NSF‐CCR‐91‐15793 750‐7504. David Dobkin
guided the original work at Princeton University. If you find it
useful, please let us know.
The Geometry Center is supported by grant DMS‐8920161 from the National
Science Foundation, by grant DOE/DE‐FG02‐92ER25137 from the Department
of Energy, by the University of Minnesota, and by Minnesota Technology,
Inc.
Qhull is available from http://www.qhull.org