Provided by: qhull-bin_2020.2-6_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
           d Qu - furthest-site Delaunay triangulation (upper convex hull)
           v    - Voronoi diagram as the dual of the Delaunay triangulation
           v Qu - furthest-site Voronoi diagram
           H1,1 - Halfspace intersection about [1,1,0,...] via polar duality
           Qt   - triangulated output
           QJ   - joggled input instead of merged facets
           Tv   - verify result: structure, convexity, and point inclusion
           .    - concise list of all options
           -    - one-line description of each option
           -?   - this message
           -V   - version

       Output options (subset):
           s    - summary of results (default)
           i    - vertices incident to each facet
           n    - normals with offsets
           p    - vertex coordinates (if 'Qc', includes coplanar points)
                  if 'v', Voronoi vertices
           FA   - report total area and volume
           Fp   - halfspace intersections
           FS   - total area and volume
           Fx   - extreme points (convex hull vertices)
           G    - Geomview output (2-d, 3-d and 4-d)
           m    - Mathematica output (2-d and 3-d)
           o    - OFF format (if 'v', outputs Voronoi regions)
           QVn  - print facets that include point n, -n if not
           TI file - input file, may be enclosed in single quotes
           TO file - output file, may be enclosed in single quotes

       examples:
           rbox D4 | qhull Tv                        rbox 1000 s | qhull Tv s FA
           rbox 10 D2 | qhull d QJ s i TO result     rbox 10 D2 | qhull v Qbb Qt p
           rbox 10 D2 | qhull d Qu QJ m              rbox 10 D2 | qhull v Qu QJ o
           rbox c d D2 | qhull Qc s f Fx | more      rbox c | qhull FV n | qhull H Fp
           rbox d D12 | qhull QR0 FA                 rbox c D7 | qhull FA TF1000
           rbox y 1000 W0 | qhull Qc                 rbox c | qhull n

        - html manual:    html/index.htm
        - installation:   README.txt
        - see also:       COPYING.txt, REGISTER.txt, Changes.txt
        - WWW:            <http://www.qhull.org>
        - GIT:            <git@github.com:qhull/qhull.git>
        - news:           <http://www.qhull.org/news>
        - Geomview:       <http://www.geomview.org>
        - news group:     <news:comp.graphics.algorithms>
        - FAQ:            <http://www.faqs.org/faqs/graphics/algorithms-faq/>
        - 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 (html/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 -?'.  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:  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 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'.  To print the centrum coordinates, use option 'Ft'.  The centrum
              indices for option 'i' are one more than the centrum indices for option 'Ft'.

       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, 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 'd', 'PAn',
              'PFn', and 'PMn'.

       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

       Qa     Allow input with fewer or more points than coordinates

       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.

       Qw     Allow option warnings. Otherwise Qhull returns an error after most option warnings

       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 merges by mergetype/angle instead of mergetype/distance.

       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.

       Q12    With 'Q12', Qhull allows wide facets and wide dupridge.

       Q14    With 'Q14', Qhull merges pinched vertices that create a dupridge.

       Q15    With 'Q15', Qhull checks for duplicate ridges with the same vertices.

       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.

       TAn    Stop Qhull after adding n vertices.

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

       Tf     Flush output after each qh_fprintf.  Use 'Tf' for debugging  segfaults.   See  'Tz'
              for redirecting stderr.

       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.

       TMn    Turn on tracing at n'th merge.

       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.

       TP-1   Turn on tracing after qh_buildhull and qh_postmerge.

       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'

       TWn    Trace merge facets when the width is greater than n.

       Tz     Redirect stderr to stdout.  See 'Tf' for flushing writes.

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