qhull.man

关于网格剖分的

.TP
PMn
Only the n facets with the most merges are marked good for printing.
Unless 'PG' is set, 'Pg' is automatically set. 
.TP
Po
Force output despite precision problems.  The maximum outside distance
is not determined (qh_check_maxout).
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).
.TP
Pp
Do not report precision problems.
.PP
.TP
Qhull control options
.TP
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.
.TP
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.  
.TP
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.  
.TP
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.  
.TP
QBk:n
Scale the k'th coordinate of the input points.  After scaling, the upper
bound will be n.  'QBk' scales to +0.5.
.TP
Qc
Keep coplanar points with the nearest facet.  Output 
formats 'p', 'f', 'Gp', 'Fc', 'FN', and 'FP' will print the points.  
.TP
Qf
Partition points to the furthest outside facet.
.TP
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.
.TP
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).  
.TP
Qi
Keep interior points with the nearest facet.  
Output formats 'p', 'f', 'Gp', 'FN', 'FP', and 'Fc' will print the points.
.TP
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).
.TP
Qm
Only process points that would otherwise increase max_outside.  Other
points are treated as coplanar or interior points.
.TP
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.
.TP
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.
.TP
Qs
Search all points for the initial simplex.
.TP
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').
.TP
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.
.TP
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').
.TP
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.
.PP
.TP 
Qhull experiments and speedups
.TP
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.  
.TP
Q1
With 'Q1', Qhull sorts merges by type (coplanar, angle coplanar, concave)
instead of by angle.
.TP
Q2
With 'Q2', Qhull merges all facets at once instead of using
independent sets of merges and then retesting.
.TP
Q3
With 'Q3', Qhull does not remove redundant vertices.
.TP
Q4
With 'Q4', Qhull avoids merges of an old facet into a new facet.
.TP
Q5
With 'Q5', Qhull does not correct outer planes at the end.  The
maximum outer plane is used instead.
.TP
Q6
With 'Q6', Qhull does not pre-merge concave or coplanar facets.
.TP
Q7
With 'Q7', Qhull processes facets in depth-first order instead of
breadth-first order.
.TP
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.
.TP
Q9
With 'Q9', Qhull processes the furthest of all outside sets at each iteration.
.PP
.TP
Trace options
.TP
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.
.TP
Tc
Check frequently during execution.  This will catch most inconsistency
errors.
.TP
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'.
.TP
TFn
Report progress whenever more than n facets are created
During post-merging, 'TFn' 
reports progress after more than n/2 merges.
.TP
TO file
Output results to 'file'.  The name may be enclosed in single
quotes.
.TP
TPn
Turn on tracing when point n is added to the hull. 
.TP
TRn
Rerun qhull n times.  Usually used with 'QJn' to determine the
probability that a given joggle will fail.
.TP
Ts
Collect statistics and print to stderr at the end of execution.
.TP
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.
.TP
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'
.TP
TMn
Turn on tracing at n'th merge.
.TP
TWn
Trace merge facets when the width is greater than n.
.TP
Tz
Redirect stderr to stdout.
.PP
.SH BUGS
Please report bugs to Brad Barber at [e-mail].  

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.
.PP
.SH E-MAIL
Please send correspondence to [e-mail] and report bugs to
[e-mail].  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

.SH 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, Dec. 1996.
http://www.acm.org/pubs/citations/journals/toms/1996-22-4/p469-barber/
ftp://geom.umn.edu/pub/software/qhull-96.ps.Z

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.

.PP
.SH AUTHORS
.nf
  C. Bradford Barber                    Hannu Huhdanpaa
  [e-mail]                    [e-mail]
  
                    c/o The Geometry Center
                    University of Minnesota
                    400 Lind Hall
                    207 Church Street S.E.
                    Minneapolis, MN 55455

.fi

.SH ACKNOWLEDGEMENTS

A special thanks to Albert Marden, Victor Milenkovic, the Geometry Center,
Harvard University, and Endocardial Solutions, Inc. for supporting this work.

The software was 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 by anonymous ftp from geom.umn.edu.  To retrieve
a copy go to www.geom.umn.edu/locate/qhull or ftp: geom.umn.edu, 
user: anonymous, cd pub/software, get qhull.tar.Z, quit, 
uncompress qhull.tar.Z, tar xf qhull.tar, cd qhull, make