Provided by: qhull-bin_2012.1-4_amd64 bug

NAME

       qhull - convex hull, Delaunay triangulation, Voronoi diagram, 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-quick.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
           Qt     - triangulated output
           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 (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>
        - GIT:            <git@gitorious.org:qhull/qhull.git>
        -                                                                                 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
        - E-MAIL
        - SEE ALSO
        - AUTHORS
        - ACKNOWLEGEMENTS

       This  man  page  briefly  describes  all Qhull options.  Please report any mismatches with
       Qhull's html manual (index.htm).

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.

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.

       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.

       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 handle precision problems by merging  facets.   Alternatively,  use
       option 'QJ' to joggle the input.

       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.

       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  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 non‐simplicial 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 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.

       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.

       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 0‐relative indices of the corresponding input points.  The facets
              are oriented.

              In 4d 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'.

       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 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 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 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 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 (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.

       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 positive,  Qhull  tests  for  convexity  after  constructing  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 the facet is greater than 'Vn'.

              Without  merging,  the  default value for 'Vn' is the round‐off error ('En').  With
              merging, the default value is the pre‐merge centrum ('C-n') in 2‐d or 3‐d, 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 pre‐merging and does not set 'Wn', than 'Wn' is set to the premerge  'Cn'
              and maxcoord*(1-An).

       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 non‐simplicial 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  non‐
              simplicial 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
              'QVn' (if defined), or the first input site of the pair.  Use 'Tv' to  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 2‐d and 3‐d convex
              hulls and for 2‐d 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
              'QVn'  (if  defined), or the first input site of the pair.  Use 'Tv' to 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 non‐simplicial facets.
              See option 'Fa'.

       Ft     Print a triangulation with added points for non‐simplicial 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 'Qz', the points include the point‐at‐infinity.

       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 vertex‐at‐infinity (i.e., an unbounded
              ray).  In 3‐d, 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 2‐d, the points occur in counter‐clockwise 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  2‐d, outer planes in 3‐d, and ridges in 4‐d.  A ridge can be explicit or
              implicit.  An explicit ridge is a dim-1 dimensional simplex between two facets.  In
              4‐d,  the  explicit  ridges  are  triangles.  When displaying a ridge in 4‐d, 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 3‐d.  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 'C-n' or 'Cn'.

       GDn    Drop dimension n in 3‐d or 4‐d.  The result is a 2‐d or 3‐d object.

       Gh     Display  hyperplane  intersections  in 3‐d and 4‐d.   In 3‐d, the intersection is a
              black line.  It lies  on  two  neighboring  hyperplanes  (c.f.,  the  blue  squares
              associated  with  centrums  ('Gc')).   In  4‐d,  the  ridges  are  projected to the
              intersection of both hyperplanes.

       Gi     Display inner planes in 2‐d and 3‐d.  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 (1-r,1-g,1-b) 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 2‐d and 3‐d.  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 * (1-An).  It is at least  1/20'th
              of the maximum coordinate, and ignores post‐merging if pre‐merging is done.

       Gr     Display  ridges  in  3‐d.   A  ridge  connects  the two vertices that are shared by
              neighboring facets.  Ridges are always displayed in 4‐d.

       Gt     A 3‐d 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   sub‐dimensional   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).  ´QJn'  is  deprecated  for  Voronoi
              diagrams.  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 non‐simplicial facets.  ´Qt' is deprecated
              for Voronoi diagrams.  See also 'Qt'.

       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').

       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  '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').

       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 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.

       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 pre‐merge concave or coplanar facets.

       Q7     With  'Q7',  Qhull  processes  facets in depth‐first order instead of breadth‐first
              order.

       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.

       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.  '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.

       Ta     Annotate output with codes that identify the corresponding qh_fprintf() statement.

       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 post‐merging, '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
              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.

       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.

BUGS

       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 part‐time.

E‐MAIL

       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.num-analysis

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,    22(4):469–483,    Dec.    1996.
       http://portal.acm.org/citation.cfm?doid=235815.235821
       http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.405

       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.

AUTHORS

         C. Bradford Barber                    Hannu Huhdanpaa
         bradb@shore.net                       hannu@qhull.org

        .fi

ACKNOWLEDGEMENTS

       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/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 from http://www.qhull.org