./"  This is the Unix manual page for qhull, written in nroff, the standard
./"  manual formatter for Unix systems.  To format it, type
./"
./"  nroff -man qhull.man
./"
./"  This will print a formatted copy to standard output.  If you want
./"  to ensure that the output is plain ASCII, free of any control
./"  characters that nroff uses for underlining etc, pipe the output
./"  through "col -b":
./"
./"  nroff -man qhull.man | col -b
./"
./"  Warning: a leading quote "'" or dot "." will not format correctly
./"
.TH qhull 1 "December 30, 1998" "Geometry Center"
.SH NAME
qhull \- convex hull, Delaunay triangulation, Voronoi diagram, 
halfspace intersection about a point, hull volume, facet area
.SH SYNOPSIS
.nf
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-opt.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
    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
    i      - vertices incident to each facet
    
example:
    rbox 1000 s | qhull Tv s FA
.fi

 - html manual:    qh-man.htm
 - installation:   README.txt
 - see also:       COPYING.txt, REGISTER.txt, Changes.txt
 - WWW:  <http://www.geom.umn.edu/locate/qhull>
 - news: <http://www.geom.umn.edu/~bradb/qhull-news.html>
 - ftp:  <ftp://geom.umn.edu/pub/software/qhull.tar.Z>
 -       <ftp://geom.umn.edu/pub/software/qhull.zip>
 -       <ftp://geom.umn.edu/pub/software/qhull-96.ps.Z>
 -       <ftp://geom.umn.edu/pub/software/qhull-1.0.tar.Z>
 - Geomview:  <http://www.geom.umn.edu/locate/geomview>
 -            <ftp://geom.umn.edu/pub/software/geomview/>
 - news group:     <news:comp.graphics.algorithms>
 - FAQ:       <http://exaflop.org/docs/cgafaq/cga6.html>
 - email:          qhull@geom.umn.edu
 - bug reports:    qhull_bug@geom.umn.edu
 
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 (qh-man.htm).

.PP
.SH 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.
.PP
.SH DESCRIPTION
.PP
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.
.PP
The default printout option is a short summary. There are many
other output formats.
.PP
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.
.PP
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.
.PP
.SH IMPRECISION 
.PP
Since Qhull uses floating point arithmetic, roundoff error may occur for each
calculation.  This causes  problems
for most geometric algorithms.
.PP
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.
.PP
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.
.PP
To guarantee triangular output, joggle the input with option 'QJ'.  Facet
merging will not occur. 
.SH OPTIONS
.PP
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').
.TP
Main options:
.TP
default
Compute the convex hull of the input points.  Report a summary of
the result.
.TP
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.  
.TP
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.
.TP
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.
.TP
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.  
.TP
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.
.PP
.TP
Input/Output options:
.TP
f
Print out all facets and all fields of each facet.
.TP
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.
.TP
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 4-d 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'.
.TP
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]]".
.TP
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.
.TP
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.
.TP
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.  
.TP
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.
.PP
.TP
Precision options
.TP
An
Maximum angle given as a cosine.  If the angle between a pair of facets
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.
.TP
Cn