./" 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
./"
.TH qhull 1 "May 15 1993" "Geometry Center"
.SH NAME
qhull \- convex hull and Delaunay triangulation in general dimension
.SH SYNOPSIS
qhull [An] [b] [c] [d] [f] [g] [i] [Tn]
.SH DESCRIPTION
.PP
qhull is a general dimension convex hull program that reads a set of points
from stdin, and outputs the smallest convex set that contains the points to
stdout according to printout options.
.PP
The format of input should be the following: first line contains the dimension,
second line contains the number of input points. After that the input contains
one point per line. Points are represented by their coordinate values. For
dimension d the algorithm requires d+1 input points.
.PP
The default printout option is a short summary. There are two other possible
formats. First, an output format that can be used as an input to geomview is available for dimensions 2 - 4 (see section GEOMVIEW below). Second, the user can print the facets of convex hull, each identified by which vertices it contains.
.PP
The convex hull of a set of points is the smallest convex set that contains
the points. The convex hull is a fundamental construction for mathematics and
computational geometry. Other problems can be reduced to convex hull, e.g.,
Delaunay triangulation, Voronoi diagram, half space intersection, and linear
programming.
.PP
qhull implements the Quick_hull algorithm for convex hull. Its performance
characteristics are similar to the randomized algorithms of Clarkson, and others [Clarkson et al. 92; Fortune 93]. These algorithms add randomly selected points and retain previously constructed hulls. qhull adds furthest points and records the points that are outside of each facet. The two main advantages of qhull are output sensitive performance and early termination with approximate convex hull. Output sensitivity is important because the size of the output can be much smaller than the maximum possible output size. With the 'An' option, qhull produces an approximate convex hull with no point more than 'n' from the hull. See [Barber, Dobkin, and Huhdanpaa 93] for details.
.PP
qhull assumes general position inputs. It reports nearly coplanar points and singular facets, and optionally tests that all the input points are inside the convex hull ('c' option). Nearly singular facets are not detected.
If the input is highly degenerate (e.g., rbox 1000 s Z1e-6), qhull reports
facets with flipped orientations.
A later release of qhull will handle singularities.
.PP
.SH OPTIONS
.TP
An
approximate convex hull with delta value n. Points within distance n from a facet are considered to be in the hull already. Turns on option 'b' unless 'f' is set.
.TP
d
Delaunay triangulation by lifting the points to a paraboloid. Use 'i' to
print the triangulation. The 'g' option prints the paraboloid for 2-d
and the lower envelope of the paraboloid for 3-d sites. To view the 2-d
triangulation, turn on edges in geomview and view along the Z axis.
To view the 3-d triangulation, use geomview's
4dview. The default projection shows the triangulation without its convex
hull.
.TP
g
output can be viewed with geomview, available for dimensions 2 - 4. Produces a VECT-file for 2d, OFF-file for 3d, and 4OFF-file for 4d. 4OFF-file can be viewed using 4d-viewer. For higher dimensions, gives the full data structure.
.TP
i
prints the number of facets followed by the vertices in each facet.
.TP
Performance and tracing options:
.TP
c
check structure. Checks that all the input points are inside the
convex hull, and checks that the resulting structure is consistent
and correct. If there are 10,000 points and 10,000 facets,
the 'c' option will take longer than qhull.
.TP
f
in partitioning, the point is assigned to the new facet it is
furthest above instead of any facet it is above. Even though most
processed points are extreme, this slows down qhull.
.TP
b
the points above the horizon facets are also partitioned.
This automatically sets 'f' option, and guarantees that only
extreme points are processed. This is slower than 'f' alone.
.TP
Tn
tracing on at level n. T-1 gives detailed error messages.
.SH GEOMVIEW
Geomview is an interactive geometry viewing program for SGI
workstations and NeXT workstations. It is available via anonymous ftp
from geom.umn.edu (pub/geomview-only.tar.Z for SGI and
pub/geomview/geomview-next.tar,Z for NeXT). It includes a 4d-viewer.
.SH ENHANCEMENTS
Potential enhancements for future releases:
- merge nearly coplanar facets
- Mathematica output
- add bucketing to speed up 2-d Delaunay triangulation
- goal directed partitioning of points for 'f' option
- allow singularities, imprecise inputs and arithmetic
- conversion from Delaunay triangulation to Voronoi diagram
- optimize for virtual memory
- improved hyperplanes via minimum spanning trees and
Householder orthogonalization
Please notify us about your applications, improvements,
and desired enhancements.
.SH BUGS
Report bugs to qhull_bugs@geom.umn.edu, other correspondence to qhull@geom.umn.edu.
.SH SEE ALSO
rbox(1); Barber, C. B., and Dobkin, D. P., and Huhdanpaa, H.T., "The Quickhull Algorithm for Convex Hull", Technical Report GCG53; K.L. Clarkson, K. Mehlhorn, and R. Seidel, "Four results on randomized incremental construction", \fISymposium on Theoretical Aspects of Computer Science\fP, 1992; S. Fortune, "Computational geometry", in R. Martin, editor, \fIDirections in Geometric Computation\fP, Information Geometers, 1993
.SH AUTHORS
.nf
C. Bradford Barber Hannu Huhdanpaa
The Geometry Center The Geometry Center
University of Minnesota University of Minnesota
Suite 500 Suite 500
1300 South Second Street, 1300 South Second Street,
Minneapolis, MN 55454 Minneapolis, MN 55454
.fi