

 
qhull(1) 
FreeBSD General Commands Manual 
qhull(1) 
qhull  convex hull, Delaunay triangulation, Voronoi diagram, halfspace
intersection about a point, hull volume, facet area
qhull compute convex hulls and related structures
input (stdin): dimension, #points, point coordinates
first comment (nonnumeric) is listed in the summary
halfspace: use dim plus one with offsets after coefficients
options (qhquick.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  Furthestsite Delaunay triangulation (upper convex hull)
v Qu  Furthestsite Voronoi diagram
Qt  triangulated output
QJ  Joggle the input to avoid precision problems
.  concise list of all options
  oneline description of all options
Output options (subset):
FA  compute total area and volume
Fx  extreme points (convex hull vertices)
G  Geomview output (2d, 3d and 4d)
Fp  halfspace intersection coordinates
m  Mathematica output (2d and 3d)
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/cga6.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
 EMAIL
 SEE ALSO
 AUTHORS
 ACKNOWLEGEMENTS
This man page briefly describes all Qhull options. Please report any mismatches
with Qhull's html manual (index.htm).
Qhull is a general dimension code for computing convex hulls, Delaunay
triangulations, Voronoi diagram, furthestsite Voronoi diagram, furthestsite
Delaunay triangulations, and halfspace intersections about a point. It
implements the Quickhull algorithm for computing the convex hull. Qhull
handles roundoff 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 2d, 3d and 4d with Geomview.
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 nonnumeric 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 2d Quickhull algorithm with the nd beneathbeyond 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 3d, 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 nonsimplicial facet. A nonsimplicial facet has more than d
neighbors and may share more than one ridge with a neighbor.
Since Qhull uses floating point arithmetic, roundoff error may occur for each
calculation. This causes problems for most geometric algorithms.
Qhull automatically sets option 'C0' in 2d, 3d, and 4d, or option 'Qx' in
5d and higher. These options handle precision problems by merging facets.
Alternatively, use option 'QJ' to joggle the input.
With 'C0', Qhull merges nonconvex 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.
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 nonsimplicial
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 furthestsite 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 facets.
 v Qu
 Compute the furthestsite 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 0relative indices of the corresponding input
points. The facets are oriented.
In 4d and higher, Qhull triangulates nonsimplicial 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
2d and 3d convex hulls and for 2d 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 2d, it can be visualized by
"Show[Graphics[list]] ". For 3d 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 2d, 3d, and in simplicial facets.
For 2d Voronoi diagrams, the vertices are sorted by adjacency, but not
oriented. In 3d 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 worstcase 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
(premerging). If 'n' is positive, Qhull tests angles after constructing
the hull (postmerging). Both pre and postmerging can be defined.
Option 'C0' or 'C0' is set if the corresponding 'Cn' or 'Cn' is not set.
If 'Qx' is set, then 'An' and 'Cn' 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
"premerging". If 'n' is positive, Qhull tests for convexity
after constructing the hull ("postmerging"). Both pre and
postmerging can be defined.
For 5d and higher, 'Qx' should be used instead of 'Cn'. 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 'QR1'.
 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 roundoff error ('En').
With merging, the default value is the premerge centrum ('Cn') in 2d or
3d, 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 premerging and does not set 'Wn',
than 'Wn' is set to the premerge 'Cn' and maxcoord*(1An).
 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 nonsimplicial 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 nonsimplicial 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 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 2d and 3d
convex hulls and for 2d 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 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
nonsimplicial facets. See option 'Fa'.
 Ft
 Print a triangulation with added points for nonsimplicial 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 points include the
pointatinfinity.
 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
vertexatinfinity (i.e., an unbounded ray). In 3d, 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 2d, the points occur in
counterclockwise 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 2d, outer planes in 3d, and ridges in 4d. A ridge can
be explicit or implicit. An explicit ridge is a dim1 dimensional simplex
between two facets. In 4d, the explicit ridges are triangles. When
displaying a ridge in 4d, 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 3d. 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 'Cn' or 'Cn'.
 GDn
 Drop dimension n in 3d or 4d. The result is a 2d or 3d object.
 Gh
 Display hyperplane intersections in 3d and 4d. In 3d, the intersection
is a black line. It lies on two neighboring hyperplanes (c.f., the blue
squares associated with centrums ('Gc')). In 4d, the ridges are projected
to the intersection of both hyperplanes.
 Gi
 Display inner planes in 2d and 3d. 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 (1r,1g,1b) 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 2d and 3d. 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 * (1An).
It is at least 1/20'th of the maximum coordinate, and ignores postmerging
if premerging is done.
 Gr
 Display ridges in 3d. A ridge connects the two vertices that are shared
by neighboring facets. Ridges are always displayed in 4d.
 Gt
 A 3d 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 subdimensional 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 nonsimplicial facets. See also
'QJ'.
 Qv
 Test vertex neighbors for convexity after postmerging. To use the 'Qv'
option, you also need to set a merge option (e.g., 'Qx' or 'C0').
 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
'Cn'), merging concave facets, merging duplicate ridges, and merging
flipped facets. Coplanar merges and angle coplanar merges ('An') are not
performed. Concavity testing is delayed until a merge occurs.
After the hull is built, all coplanar merges are performed (defined by 'Cn'
and 'An'), then postmerges 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 premerging as a default option. With 'Q0'/'Qx' and without
explicit premerge 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 premerge concave or coplanar facets.
 Q7
 With 'Q7', Qhull processes facets in depthfirst order instead of
breadthfirst order.
 Q8
 With 'Q8' and merging, Qhull does not retain nearinterior 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. 'T1' 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
postmerging, '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 facetpoint 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.
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
parttime.
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.numanalysis
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):469483,
Dec. 1996.
http://www.acm.org/pubs/citations/journals/toms/1996224/p469barber/
http://citeseer.nj.nec.com/83502.html
Clarkson, K.L., K. Mehlhorn, and R. Seidel, "Four results on randomized
incremental construction," Computational Geometry: Theory and
Applications, vol. 3, p. 185211, 1993.
Preparata, F. and M. Shamos, Computational Geometry, SpringerVerlag, New York,
1985.
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
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/DMS8920161 and NSFCCR9115793 7507504. 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 DMS8920161 from the National Science
Foundation, by grant DOE/DEFG0292ER25137 from the Department of Energy, by
the University of Minnesota, and by Minnesota Technology, Inc.
Qhull is available from http://www.qhull.org
Visit the GSP FreeBSD Man Page Interface. Output converted with ManDoc. 