allegiance/qhull/qhull.txt

qhull(1)						 qhull(1)


NAME
       qhull  -	convex hull, Delaunay triangulation, Voronoi ver-
       tices, halfspace	intersection, hull volume, facet area

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

       options (qh-opt.htm):
	   d	  - Delaunay triangulation by lifting points to	a paraboloid
	   v	  - Voronoi vertices and regions via Delaunay triangulation
	   H1,1	  - Halfspace intersection about [1,1,0,...]
	   d Qu	  - Furthest-site Delaunay triangulation (upper	convex hull)
	   v Qu	  - Furthest-site Voronoi vertices and regions
	   .	  - concise list of all	options
	   -	  - one-line description of all	options

       Output options (subset):
	   s	  - (default) summary to stderr
	   Ft	  - triangulated output	with centrums
	   o	  - OFF	file format (if	Voronoi, outputs regions)
	   i	  - vertices incident to each facet
	   n	  - normals with offsets
	   p	  - vertex coordinates (centers	for Voronoi)
	   Fp	  - halfspace intersection coordinates
	   FA	  - compute total area and volume
	   G	  - Geomview output (2-d, 3-d and 4-d)
	   m	  - Mathematica	output (2-d and	3-d)
	   Tv	  - verify result: structure, convexity, and point inclusion
	   f	  - print all fields of	all facets

       example:
	   rbox	1000 s | qhull Tv s FA

	- html manual:	  qh-man.htm
	- installation:	  README.txt
	- see also:	  COPYING.txt, REGISTER.txt, Changes.txt
	- WWW:	<http://www.geom.umn.edu/locate/qhull>
	- news:	<http://www.geom.umn.edu/~bradb/qhull-news.html>
	- ftp:	<ftp://geom.umn.edu/pub/software/qhull.tar.Z>
	-	<ftp://geom.umn.edu/pub/software/qhull-1.0.tar.Z>
	- Geomview:  <http://www.geom.umn.edu/locate/geomview>
	-	     <ftp://geom.umn.edu/pub/software/geomview/>
	- news group:	  <news:comp.graphics.algorithms>
	- email:	  qhull@geom.umn.edu
	- bug reports:	  qhull_bug@geom.umn.edu

       The sections are:
	- INTRODUCTION
	- DESCRIPTION, a description of	Qhull
	- IMPRECISION, how Qhull handles imprecision
	- OPTIONS



Geometry Center		  April	2, 1997				1





qhull(1)						 qhull(1)


	-    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  vertices   and
       regions,	 furthest-site	Voronoi	 vertices,  furthest-site
       Delaunay	triangulations,	and halfspace intersections.   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 should be 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



Geometry Center		  April	2, 1997				2





qhull(1)						 qhull(1)


       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.

       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.


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
       control ('Q'), and tracing ('T').

       Main options:

       default
	      Compute the convex hull of the input points.

       d      Compute  the  Delaunay triangulation by lifting the



Geometry Center		  April	2, 1997				3





qhull(1)						 qhull(1)


	      input points  to	a  paraboloid.	 The  'o'  option
	      prints  the  input  points  and  facets.	 The 'Ft'
	      option prints a triangulation.  It adds points (the
	      centrums)	to non-simplicial facets.

       v      Compute  the Voronoi vertices via	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.	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 half-spaces 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
	      half-spaces,  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  'Ft'  option
	      prints  a	 triangulation.	 It adds points	(the cen-
	      trums) to	non-simplicial facets.

       v Qu   Compute  the  furthest-site  Voronoi  vertices  and
	      regions.	 The  'p'  option prints the Voronoi ver-
	      tices.  The 'o' option prints the	Voronoi	 vertices
	      and the vertices in each Voronoi region.	The first
	      or zero'th vertex	indicates the infinity vertex  at
	      infinity.	    Its	  coordinates	are   qh_INFINITE
	      (-10.101).  It indicates unbounded Voronoi  regions
	      and degenerate Delaunay triangles.


       Input/Output options:

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




Geometry Center		  April	2, 1997				4





qhull(1)						 qhull(1)


       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-
	      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 sim-
	      plicial ridge between two	 facets.   To  print  the
	      vertices without triangulation, use option 'Fv'.

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

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

       o      Output the facets	in OFF file format.  Qhull prints
	      the dimension, number of points, number of  facets,
	      and  number  of ridges.  Then it prints the coordi-
	      nates 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.




Geometry Center		  April	2, 1997				5





qhull(1)						 qhull(1)


       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 vertices, it	prints the  coor-
	      dinates of each Voronoi vertex.

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

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


       Precision options

       An     Maximum angle given as  a	 cosine.   If  the  angle
	      between  a  pair of facets is greater than n, Qhull
	      merges one of the	facets into a neighbor.	  If  'n'
	      is  negative,  Qhull tests angles	after adding each
	      point to the hull	(pre-merging).	If 'n'	is  posi-
	      tive,  Qhull  tests  angles  after constructing the
	      hull (post-merging).  Both  pre-	and  post-merging
	      can be defined.

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

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



Geometry Center		  April	2, 1997				6





qhull(1)						 qhull(1)


	      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 vertices,	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).




Geometry Center		  April	2, 1997				7





qhull(1)						 qhull(1)


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

       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



Geometry Center		  April	2, 1997				8





qhull(1)						 qhull(1)


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



Geometry Center		  April	2, 1997				9





qhull(1)						 qhull(1)


	      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 average vertex.  The average vertex	is a fea-
	      sible point for half-space intersection.


       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
	      outer  plane.  Its edges are determined by the ver-
	      tices.




Geometry Center		  April	2, 1997			       10





qhull(1)						 qhull(1)


       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.

       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



Geometry Center		  April	2, 1997			       11





qhull(1)						 qhull(1)


	      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.	The maxi-
	      mum   outside   distance	  is	not    determined
	      (qh_check_maxout).   Verify  ('Tv')  does	not check
	      coplanar points.	Flipped	facets are  reported  and
	      concave  facets  are  counted.   If  'Po'	 is used,
	      points are not partitioned into flipped facets  and
	      a	 flipped  facet	 is  always  visible  to a point.
	      Also, if an error	occurs before the  completion  of
	      Qhull  and  tracing  is  not active, 'Po'	outputs	a
	      neighborhood of the erroneous facets (if any).

       Pp     Do not report precision problems.


       Qhull control options

       Qbk:0Bk:0
	      Drop dimension  k	 from  the  input  points.   This
	      allows  the  user	 to  take  convex  hulls  of sub-
	      dimensional objects.  It happens before the  Delau-
	      nay 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.

       QBk:n  Scale  the  k'th	coordinate  of	the input points.
	      After scaling, the upper bound will  be  n.   'QBk'



Geometry Center		  April	2, 1997			       12





qhull(1)						 qhull(1)


	      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.

       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.

       Qs     Search all points	for the	initial	simplex.

       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.




Geometry Center		  April	2, 1997			       13





qhull(1)						 qhull(1)


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

       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



Geometry Center		  April	2, 1997			       14





qhull(1)						 qhull(1)


	      outside sets at each iteration.


       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.

       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.

       TPn    Turn  on tracing when point n is added to	the hull.

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




Geometry Center		  April	2, 1997			       15





qhull(1)						 qhull(1)


       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@geom.umn.edu.

       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.


E-MAIL
       Please	send  correspondence  to  qhull@geom.umn.edu  and
       report bugs to qhull_bug@geom.umn.edu.  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)




Geometry Center		  April	2, 1997			       16





qhull(1)						 qhull(1)


       Barber, C. B.,  D.P.  Dobkin,  and  H.T.	 Huhdanpaa,  "The
       Quickhull Algorithm for Convex Hulls," ACM Trans. on Math-
       ematical		 Software,	     Dec.	    1996.
       http://www.acm.org/pubs/toc/Abstracts/toms/235821.html

       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@geom.umn.edu		       hannu@geom.umn.edu

			   c/o The Geometry Center
			   University of Minnesota
			   1300	South Second Street, Suite 500
			   Minneapolis,	MN 55454



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

       The  software was developed under National Science Founda-
       tion grants NSF/DMS-8920161 and NSF-CCR-91-15793	750-7504.
       David Dobkin quided the original	work at	Princeton Univer-
       sity.  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  Uni-
       versity of Minnesota, and by Minnesota Technology, Inc.

       Qhull is	available by anonymous ftp from	geom.umn.edu.  To
       retrieve	a copy:	ftp  geom.umn.edu,  user:  anonymous,  cd
       pub/software,	get    qhull.tar.Z,    quit,   uncompress
       qhull.tar.Z, tar	xf qhull.tar, cd qhull,	make












Geometry Center		  April	2, 1997			       17