📄 qhull.txt
字号:
qhull(1) qhull(1)
NAME
qhull - convex hull, Delaunay triangulation, Voronoi dia-
gram, 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-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
- 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
Geometry Center December 30, 1998 1
qhull(1) qhull(1)
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).
INTRODUCTION
Qhull is a general dimension code for computing convex
hulls, Delaunay triangulations, Voronoi diagram, furthest-
site Voronoi diagram, furthest-site Delaunay triangula-
tions, and halfspace intersections about a point. It
implements the Quickhull algorithm for computing the con-
vex 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, trac-
ing, 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.
Geometry Center December 30, 1998 2
qhull(1) qhull(1)
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 pre-
cision 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 han-
dle precision problems by merging facets. Alternatively,
use option 'QJ' to joggle the input.
With 'C-0', Qhull merges non-convex facets while con-
structing the hull. The remaining facets are clearly con-
vex. 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 for-
mats ('F'), Geomview output ('G'), printing ('P'), Qhull
Geometry Center December 30, 1998 3
qhull(1) qhull(1)
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 tri-
angulation. The 'p' option prints the Voronoi ver-
tices. 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 indi-
cates 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 feasi-
ble point when the first number is the dimension,
the second number is "1", and the coordinates com-
plete 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 guar-
antees triangular otuput. You can also use 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
Geometry Center December 30, 1998 4
qhull(1) qhull(1)
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 cor-
responding 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 ver-
tices 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-simpli-
cial facets. Each apex (the first vertex) is a
created point that corresponds to the facet's cen-
trum. Its index is greater than the indices of the
input points. Each base corresponds to a simpli-
cial ridge between two facets. To print the ver-
tices 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
Geometry Center December 30, 1998 5
qhull(1) qhull(1)
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 coor-
dinates 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 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 posi-
tive, 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 con-
structed 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
Geometry Center December 30, 1998 6
qhull(1) qhull(1)
positive, Qhull tests for convexity after con-
structing 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
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -