path: root/src/qhull/html/qhull.txt

qhull(1)                                                 qhull(1)


NAME
       qhull  - convex hull, Delaunay triangulation, Voronoi dia-
       gram, halfspace intersection about a point, hull volume, facet area

SYNOPSIS
       qhull- compute convex hulls and related structures
           input (stdin): dimension, #points, point coordinates
           first comment (non-numeric) is listed in the summary
           halfspace: use dim plus one with offsets after coefficients

       options (qh-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
           QJ     - Joggle the input to avoid precision problems
           .      - concise list of all options
           -      - one-line description of all options

       Output options (subset):
           FA     - compute total area and volume
           Fx     - extreme points (convex hull vertices)
           G      - Geomview output (2-d, 3-d and 4-d)
           Fp     - halfspace intersection coordinates
           m      - Mathematica output (2-d and 3-d)
           n      - normals with offsets
           o      - OFF file format (if Voronoi, outputs regions)
           TO file- output results to file, may be enclosed in single quotes
           f      - print all fields of all facets
           s      - summary of results (default)
           Tv     - verify result: structure, convexity, and point inclusion
           p      - vertex coordinates
           i      - vertices incident to each facet

       example:
           rbox 1000 s | qhull Tv s FA

        - html manual:    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>
        - 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://www.faqs.org/faqs/graphics/algorithms-faq/>
        - email:          qhull@qhull.org
        - bug reports:    qhull_bug@qhull.org




Geometry Center              2003/12/30                 1





qhull(1)                                                 qhull(1)


       The sections are:
        - INTRODUCTION
        - DESCRIPTION, a description of Qhull
        - IMPRECISION, how Qhull handles imprecision
        - OPTIONS
        -    Input and output options
        -    Additional input/output formats
        -    Precision options
        -    Geomview options
        -    Print options
        -    Qhull options
        -    Trace options
        - BUGS
        - E-MAIL
        - SEE ALSO
        - AUTHORS
        - ACKNOWLEGEMENTS

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



INTRODUCTION
       Qhull  is  a  general  dimension code for computing convex
       hulls, Delaunay triangulations, Voronoi diagram, furthest-
       site  Voronoi  diagram,  furthest-site Delaunay triangula-
       tions, and halfspace  intersections  about  a  point.   It
       implements  the Quickhull algorithm for computing the con-
       vex hull.  Qhull handles round-off  errors  from  floating
       point arithmetic.  It can approximate a convex hull.

       The  program includes options for hull volume, facet area,
       partial hulls, input transformations, randomization, trac-
       ing,  multiple  output  formats, and execution statistics.
       The program can be called from  within  your  application.
       You  can  view  the  results  in  2-d,  3-d  and  4-d with
       Geomview.


DESCRIPTION
       The format of input is the following: first line  contains
       the  dimension,  second  line contains the number of input
       points, and point coordinates follow.  The  dimension  and
       number  of  points  can  be  reversed.   Comments and line
       breaks are ignored.  A comment starts with  a  non-numeric
       character  and  continues  to  the end of line.  The first
       comment is reported in summaries  and  statistics.   Error
       reporting is better if there is one point per line.

       The  default printout option is a short summary. There are
       many other output formats.




Geometry Center              2003/12/30                 2





qhull(1)                                                 qhull(1)


       Qhull implements the Quickhull algorithm for convex  hull.
       This  algorithm  combines the 2-d Quickhull algorithm with
       the n-d beneath-beyond algorithm [c.f., Preparata & Shamos
       '85].   It  is  similar  to  the  randomized algorithms of
       Clarkson and others  [Clarkson  et  al.  '93].   The  main
       advantages  of Quickhull are output sensitive performance,
       reduced space requirements, and automatic handling of pre-
       cision problems.

       The data structure produced by Qhull consists of vertices,
       ridges, and facets.  A vertex is a point of the input set.
       A ridge is a set of d vertices and two neighboring facets.
       For example in 3-d, a ridge is an edge of the  polyhedron.
       A facet is a set of ridges, a set of neighboring facets, a
       set of incident vertices, and a hyperplane equation.   For
       simplicial  facets, the ridges are defined by the vertices
       and neighboring facets.  When Qhull merges two facets,  it
       produces  a  non-simplicial facet.  A non-simplicial facet
       has more than d neighbors and  may  share  more  than  one
       ridge with a neighbor.


IMPRECISION
       Since Qhull uses floating point arithmetic, roundoff error
       may occur for each calculation.  This causes  problems for
       most geometric algorithms.

       Qhull  automatically  sets  option  'C-0' in 2-d, 3-d, and
       4-d, or option 'Qx' in 5-d and higher.  These options han-
       dle  precision problems by merging facets.  Alternatively,
       use option 'QJ' to joggle the input.

       With 'C-0', Qhull  merges  non-convex  facets  while  con-
       structing  the hull. The remaining facets are clearly con-
       vex. With 'Qx',  Qhull  merges  coplanar  horizon  facets,
       flipped  facets, concave facets and duplicated ridges.  It
       merges coplanar facets after constructing the hull.   With
       'Qx',  coplanar points may be missed, but it appears to be
       unlikely.

       To guarantee triangular  output,  joggle  the  input  with
       option 'QJ'.  Facet merging will not occur.

OPTIONS
       To  get  a  list  of  the  most important options, execute
       'qhull' by itself.  To get a  complete  list  of  options,
       execute  'qhull  -'.   To  get a complete, concise list of
       options, execute 'qhull .'.

       Options can be in any order.  Capitalized options take  an
       argument  (except  'PG'  and 'F' options).  Single letters
       are used for output formats and precision constants.   The
       other options are grouped into menus for other output for-
       mats ('F'), Geomview output ('G'), printing  ('P'),  Qhull



Geometry Center              2003/12/30                 3





qhull(1)                                                 qhull(1)


       control ('Q'), and tracing ('T').

       Main options:

       default
              Compute  the  convex  hull  of  the  input  points.
              Report a summary of the result.

       d      Compute the Delaunay triangulation by  lifting  the
              input  points  to  a  paraboloid.   The  'o' option
              prints the  input  points  and  facets.   The  'QJ'
              option  guarantees  triangular  output.   The  'Ft'
              option prints a triangulation.  It adds points (the
              centrums) to non-simplicial facets.

       v      Compute  the Voronoi diagram from the Delaunay tri-
              angulation.  The 'p' option prints the Voronoi ver-
              tices.   The 'o' option prints the Voronoi vertices
              and the vertices in each Voronoi region.  It  lists
              regions  in  site id order.  The 'Fv' option prints
              each ridge of the Voronoi diagram.   The  first  or
              zero'th  vertex indicates the infinity vertex.  Its
              coordinates are qh_INFINITE  (-10.101).   It  indi-
              cates   unbounded  Voronoi  regions  or  degenerate
              Delaunay triangles.

       Hn,n,...
              Compute halfspace intersection  about  [n,n,0,...].
              The  input  is  a  set of halfspaces defined in the
              same format as 'n', 'Fo', and 'Fi'.   Use  'Fp'  to
              print  the  intersection  points.  Use 'Fv' to list
              the intersection points for  each  halfspace.   The
              other  output formats display the dual convex hull.

              The point [n,n,n,...] is a feasible point  for  the
              halfspaces, i.e., a point that is inside all of the
              halfspaces (Hx+b <=  0).   The  default  coordinate
              value is 0.

              The  input may start with a feasible point.  If so,
              use 'H' by itself.  The input starts with a  feasi-
              ble  point  when the first number is the dimension,
              the second number is "1", and the coordinates  com-
              plete  a line.  The 'FV' option produces a feasible
              point for a convex hull.

       d Qu   Compute the  furthest-site  Delaunay  triangulation
              from  the upper convex hull.  The 'o' option prints
              the input points and facets.  The 'QJ' option guar-
              antees triangular otuput.  You can also use facets.

       v Qu   Compute the furthest-site Voronoi diagram.  The 'p'
              option prints the Voronoi vertices.  The 'o' option
              prints the Voronoi vertices  and  the  vertices  in



Geometry Center              2003/12/30                 4





qhull(1)                                                 qhull(1)


              each  Voronoi  region.  The 'Fv' option prints each
              ridge of the Voronoi diagram.  The first or zero'th
              vertex  indicates  the infinity vertex at infinity.
              Its  coordinates  are  qh_INFINITE  (-10.101).   It
              indicates  unbounded Voronoi regions and degenerate
              Delaunay triangles.

       Qt     Triangulated output.


       Input/Output options:

       f      Print out all facets and all fields of each  facet.

       G      Output  the hull in Geomview format.  For imprecise
              hulls, Geomview displays the inner and outer  hull.
              Geomview can also display points, ridges, vertices,
              coplanar  points,  and  facet  intersections.   See
              below for a list of options.

              For  Delaunay triangulations, 'G' displays the cor-
              responding paraboloid.  For halfspace intersection,
              'G' displays the dual polytope.

       i      Output the incident vertices for each facet.  Qhull
              prints the number of facets followed  by  the  ver-
              tices  of  each  facet.   One  facet is printed per
              line.  The numbers are the  0-relative  indices  of
              the  corresponding  input  points.   The facets are
              oriented.

              In 4-d and higher, Qhull  triangulates  non-simpli-
              cial  facets.   Each  apex  (the first vertex) is a
              created point that corresponds to the facet's  cen-
              trum.  Its index is greater than the indices of the
              input points.  Each base corresponds to  a  simpli-
              cial  ridge  between two facets.  To print the ver-
              tices without triangulation, use option 'Fv'.

       m      Output  the  hull  in  Mathematica  format.   Qhull
              writes  a  Mathematica  file for 2-d and 3-d convex
              hulls and for 2-d Delaunay triangulations.    Qhull
              produces a list of objects that you can assign to a
              variable in Mathematica,  for  example:  "list=  <<
              <outputfilename> ". If the object is 2-d, it can be
              visualized  by  "Show[Graphics[list]]  ".  For  3-d
              objects the command is "Show[Graphics3D[list]]".

       n      Output  the  normal equation for each facet.  Qhull
              prints the dimension  (plus  one),  the  number  of
              facets,  and  the  normals  for  each  facet.   The
              facet's offset follows its normal coefficients.

       o      Output the facets in OFF file format.  Qhull prints
              the  dimension, number of points, number of facets,
              and  number  of  ridges.   Then   it   prints   the



Geometry Center              2003/12/30                 5





qhull(1)                                                 qhull(1)


              coordinates  of  the  input points and the vertices
              for each facet.  Each facet is on a separate  line.
              The  first  number  is the number of vertices.  The
              remainder are  the  indices  of  the  corresponding
              points.  The vertices are oriented in 2-d, 3-d, and
              in simplicial facets.

              For 2-d Voronoi diagrams, the vertices  are  sorted
              by adjacency, but not oriented.  In 3-d and higher,
              the Voronoi vertices are sorted by index.  See  the
              'v' option for more information.

       p      Output the coordinates of each vertex point.  Qhull
              prints the dimension, the number of points, and the
              coordinates  for  each  vertex.   With the 'Gc' and
              'Gi' options, it also prints coplanar and  interior
              points.   For Voronoi diagrams, it prints the coor-
              dinates of each Voronoi vertex.

       s      Print a summary to stderr.  If  no  output  options
              are  specified  at  all,  a summary goes to stdout.
              The summary lists the number of input  points,  the
              dimension,  the  number  of  vertices in the convex
              hull, the number of facets in the convex hull,  the
              number of good facets (if 'Pg'), and statistics.

              The  last  two  statistics  (if needed) measure the
              maximum distance from a point or vertex to a facet.
              The number in parenthesis (e.g., 2.1x) is the ratio
              between the maximum  distance  and  the  worst-case
              distance due to merging two simplicial facets.


       Precision options

       An     Maximum  angle  given  as  a  cosine.  If the angle
              between a pair of 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 posi-
              tive, Qhull tests  angles  after  constructing  the
              hull  (post-merging).   Both  pre- and post-merging
              can be defined.

              Option 'C0' or 'C-0' is set  if  the  corresponding
              'Cn' or 'C-n' is not set.  If 'Qx' is set, then 'A-
              n' and 'C-n' are checked after  the  hull  is  con-
              structed and before 'An' and 'Cn' are checked.

       Cn     Centrum  radius.  If a centrum is less than n below
              a  neighboring  facet,  Qhull  merges  one  of  the
              facets.   If  'n'  is negative or '-0', Qhull tests
              and merges facets after adding each  point  to  the
              hull.   This  is  called  "pre-merging".  If 'n' is



Geometry Center              2003/12/30                 6





qhull(1)                                                 qhull(1)


              positive, Qhull  tests  for  convexity  after  con-
              structing the hull ("post-merging").  Both pre- and
              post-merging can be defined.

              For 5-d and higher, 'Qx' should be used instead  of
              'C-n'.  Otherwise, most or all facets may be merged
              together.

       En     Maximum roundoff error for distance computations.

       Rn     Randomly perturb distance computations up to +/-  n
              *  max_coord.  This option perturbs every distance,
              hyperplane, and angle computation.  To use time  as
              the random number seed, use option 'QR-1'.

       Vn     Minimum  distance  for  a  facet  to be visible.  A
              facet is visible if the distance from the point  to
              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  maxco-
              ord*(1-An).


       Additional input/output formats

       Fa     Print area for each facet.  For Delaunay triangula-
              tions, 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.




Geometry Center              2003/12/30                 7





qhull(1)                                                 qhull(1)


       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 num-
              ber  of  indices  and floats.  The first pair lists
              adjacent input sites, the next  d  floats  are  the
              normalized coefficients for the hyperplane, and the



Geometry Center              2003/12/30                 8





qhull(1)                                                 qhull(1)


              last float is the offset.  The hyperplane  is  ori-
              ented  toward  verify that the hyperplanes are per-
              pendicular  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.  See 'm'

       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 num-
              ber of  neighbors  followed  by  the  corresponding
              facet indices (see 'Fn').

       Fo     Print  outer planes for each facet in the same for-
              mat 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 num-
              ber 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 ori-
              ented toward verify that the hyperplanes  are  per-
              pendicular   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



Geometry Center              2003/12/30                 9



qhull(1)                                                 qhull(1)


              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  ("7"), followed by the dimen-
              sion, 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.

              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  con-
              sists  of the number of integers ("0").  The second
              line consists of the number of  reals  ("2"),  fol-
              lowed  by  the total facet area, and the total vol-
              ume.  Later versions of  Qhull  may  produce  addi-
              tional integers or reals.

              The  total volume measures the volume of the inter-
              section 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 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 num-
              ber  of  indices.   The  first  pair lists adjacent



Geometry Center              2003/12/30                10





qhull(1)                                                 qhull(1)


              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 fea-
              sible 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  hyper-
              planes.

       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



Geometry Center              2003/12/30                11





qhull(1)                                                 qhull(1)


              outer  plane.  Its edges are determined by the ver-
              tices.

       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 automati-
              cally 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 automat-
              ically set.




Geometry Center              2003/12/30                12





qhull(1)                                                 qhull(1)


       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-dimen-
              sional 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, scal-
              ing 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.



Geometry Center              2003/12/30                13





qhull(1)                                                 qhull(1)


       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.  Out-
              put 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  visi-
              ble  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.  Out-
              put 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 triangula-
              tions, 'QJn' sets 'Qbb' to scale the  last  coordi-
              nate (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  random-
              ized  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 tri-
              angulations ('d' and 'v'), rotate  about  the  last
              axis.




Geometry Center              2003/12/30                14





qhull(1)                                                 qhull(1)


       Qs     Search all points for the initial simplex.

       Qt     Triangulated output.  Triangulate non-simplicial
              facets. 'Qt' is deprecated for Voronoi diagrams.
              See also 'QJn'

       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 merg-
              ing  flipped  facets.   Coplanar  merges  and angle
              coplanar merges ('A-n') are not performed.  Concav-
              ity 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  ver-
              tices.

       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.




Geometry Center              2003/12/30                15





qhull(1)                                                 qhull(1)


       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 out-
              side sets at each iteration.

       Q10    With 'Q10', Qhull does not use special processing
              for narrow distributions.

       Q11    With 'Q11', Qhull copies normals and recomputes
              centrums for tricoplanar facets.

       Q12    With 'Q12', Qhull does not report a very wide merge due 
              to a duplicated ridge with nearly coincident 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 topologi-
              cal  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  topologi-
              cal  structure,  facet  convexity, and point inclu-
              sion.  If precision problems occurred,  facet  con-
              vexity  is  tested whether or not 'Tv' is selected.
              Option 'Tv'  does  not  check  point  inclusion  if



Geometry Center              2003/12/30                16





qhull(1)                                                 qhull(1)


              forcing output with 'Po', or if 'Q5' is set.

              For  point  inclusion  testing, Qhull verifies that
              all points are below all outer planes  (facet->max-
              outside).  Point inclusion is exhaustive if merging
              or if the facet-point product is small enough; oth-
              erwise  Qhull  verifies  each point with a directed
              search (qh_findbest).

              Point inclusion testing occurs after producing out-
              put.   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  align-
       ment.   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.



Geometry Center              2003/12/30                17





qhull(1)                                                 qhull(1)


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.graph-
       ics.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 Math-
       ematical 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



ACKNOWLEDGEMENTS
       A special thanks to Albert Marden, Victor Milenkovic,  the
       Geometry Center, Harvard University, and Endocardial Solu-
       tions, 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



Geometry Center              2003/12/30                18





qhull(1)                                                 qhull(1)


       guided the original work at Princeton University.  If you find it
       useful, please let us know.

       The Geometry Center was 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













































Geometry Center              2003/12/30                19