Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

home | help
qhull(1)		    General Commands Manual		      qhull(1)

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

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

       options (qh-quick.htm):
	   d	  - Delaunay triangulation by lifting points to	a paraboloid
	   v	  - Voronoi diagram via	the Delaunay triangulation
	   H1,1	  - Halfspace intersection about [1,1,0,...]
	   d Qu	  - Furthest-site Delaunay triangulation (upper	convex hull)
	   v Qu	  - Furthest-site Voronoi diagram
	   Qt	  - triangulated output
	   QJ	  - Joggle the input to	avoid precision	problems
	   .	  - concise list of all	options
	   -	  - one-line description of all	options

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

       example:
	   rbox	1000 s | qhull Tv s FA

	- html manual:	  index.htm
	- installation:	  README.txt
	- see also:	  COPYING.txt, REGISTER.txt, Changes.txt
	- WWW:		  <http://www.qhull.org>
	- GIT:		  <git@github.com:qhull/qhull.git>
	-	  mirror:		   <http://www6.uniovi.es/ftp/pub/mir-
       rors/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

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

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

INTRODUCTION
       Qhull is	a general dimension code for computing convex hulls,  Delaunay
       triangulations,	Voronoi	 diagram,  furthest-site Voronoi diagram, fur-
       thest-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	dimen-
       sion, second line contains the number of	input points, and point	 coor-
       dinates	follow.	  The  dimension and number of points can be reversed.
       Comments	and line breaks	are ignored.  A	comment	starts with a  non-nu-
       meric 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	 algo-
       rithm  combines the 2-d Quickhull algorithm with	the n-d	beneath-beyond
       algorithm [c.f.,	Preparata & Shamos '85].  It is	similar	to the random-
       ized 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 neighbor-
       ing facets, a set of incident vertices, and a hyperplane	equation.  For
       simplicial facets, the ridges are defined by the	vertices and neighbor-
       ing 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	 algo-
       rithms.

       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	copla-
       nar  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 com-
       plete, concise list of options, execute 'qhull .'.

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

       Main options:

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

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

       v      Compute  the  Voronoi  diagram  from the Delaunay	triangulation.
	      The 'p' option prints the	 Voronoi  vertices.   The  'o'	option
	      prints the Voronoi vertices and the vertices in each Voronoi re-
	      gion.  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 out-
	      put 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 coor-
	      dinates  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' op-
	      tion prints each ridge of	the Voronoi  diagram.	The  first  or
	      zero'th  vertex  indicates the infinity vertex at	infinity.  Its
	      coordinates are qh_INFINITE (-10.101).  It  indicates  unbounded
	      Voronoi regions and degenerate Delaunay triangles.

       Input/Output options:

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

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

	      For Delaunay triangulations, 'G' displays	the corresponding  pa-
	      raboloid.	  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  in-
	      dices  of	 the  corresponding input points.  The facets are ori-
	      ented.

	      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	trian-
	      gulation,	use option 'Fv'.

       m      Output the hull in Mathematica format.  Qhull writes a Mathemat-
	      ica file for 2-d and 3-d convex hulls and	for 2-d	Delaunay  tri-
	      angulations.   Qhull produces a list of objects that you can as-
	      sign to a	variable in Mathematica, for example: "list= <<	 <out-
	      putfilename>  ".	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 di-
	      mension (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	dimen-
	      sion, number of points, number of	facets,	and number of  ridges.
	      Then  it prints the coordinates of the input points and the ver-
	      tices 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-merg-
	      ing).  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'.  Oth-
	      erwise, 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 com-
	      putation.	 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 er-
	      ror ('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 di-
	      mensions.	 If the	outside	width is specified ('Wn'),  the	 maxi-
	      mum, 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 con-
	      vex  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  hy-
	      perplane	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  ap-
	      proximation 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  di-
	      mension  followed	by the number of facets.  Then each facet cen-
	      trum 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 sum-
	      mary.  Data starts after a "begin" line.	The next line  is  the
	      number  of points	followed by the	dimension+1 and	"real" or "in-
	      teger".  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 nor-
	      mals or points followed by the dimension+1 and "real".  Then the
	      normals or points	are listed  with the offset before the coeffi-
	      cients.  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 hy-
	      perplane is oriented toward 'QVn'	(if defined), or the first in-
	      put  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 num-
	      ber 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" fol-
	      lowed by the facet's ID.	If the point is	not a selected vertex,
	      the  line	 is "0".  Otherwise, each line is the number of	neigh-
	      bors 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  hy-
	      perplane is oriented toward 'QVn'	(if defined), or the first in-
	      put 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.	 Addi-
	      tional '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 un-
	      bounded 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 inte-
	      gers ("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 num-
	      ber 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  ap-
	      proximations 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 fol-
	      low, one per line, then the facets follow	as a list of point in-
	      dices.  With option 'Qz',	the points include the point-at-infin-
	      ity.

       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 ver-
	      tices.  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  oc-
	      cur 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  op-
	      tions,  Qhull  displays  edges  in 2-d, outer planes in 3-d, and
	      ridges in	4-d.  A	ridge can be explicit  or  implicit.   An  ex-
	      plicit  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	inter-
	      section of both hyperplanes.

       Ga     Display all input	points as dots.

       Gc     Display  the  centrum for	each facet in 3-d.  The	centrum	is de-
	      fined by a green radius sitting on a blue	plane.	The plane cor-
	      responds	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  ob-
	      ject.

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

       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 hy-
	      perplane.	 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 dis-
	      plays  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	hyper-
	      plane.  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 inte-
	      rior  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	corre-
	      sponds 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.  Op-
	      tion 'Pg'	is automatically set for options 'PAn' and 'PFn'.

       PG     Print neighbors of good facets.

       PMn    Only the n facets	with the  most	merges	are  marked  good  for
	      printing.	 Unless	'PG' is	set, 'Pg' is automatically set.

       Po     Force output despite precision problems.	Verify ('Tv') does not
	      check coplanar points.  Flipped facets are reported and  concave
	      facets are counted.  If 'Po' is used, points are not partitioned
	      into flipped facets and a	flipped	facet is always	visible	 to  a
	      point.   Also, if	an error occurs	before the completion of Qhull
	      and tracing is not active, 'Po' outputs a	 neighborhood  of  the
	      erroneous	facets (if any).

       Pp     Do not report precision problems.

       Qhull control options

       Qbk:0Bk:0
	      Drop dimension k from the	input points.  This allows the user to
	      take convex hulls	of sub-dimensional objects.  It	happens	before
	      the Delaunay and Voronoi transformation.

       QbB    Scale the	input points to	fit the	unit cube.  After scaling, the
	      lower bound will be -0.5 and the upper bound +0.5	in all	dimen-
	      sions.  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 abso-
	      lute 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].   Op-
	      tion  '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 ran-
	      dom number seed.	If n>0,	use n as the random number  seed.   If
	      n=-1,  don't rotate but use time as the random number seed.  For
	      Delaunay triangulations ('d' and 'v'),  rotate  about  the  last
	      axis.

       Qs     Search all points	for the	initial	simplex.

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

       Qv     Test vertex neighbors for	convexity after	post-merging.  To  use
	      the 'Qv' option, you also	need to	set a merge option (e.g., 'Qx'
	      or 'C-0').

       QVn    A	good facet (see	'Qg' and 'Pg') includes	point n.  If n<0, then
	      a	 good  facet does not include point n.	The point is either in
	      the initial simplex or it	is the first point added to the	 hull.
	      Option 'QVn' may not be used with	merging.

       Qx     Perform  exact  merges  while  building  the  hull.  The "exact"
	      merges are merging a point into a	 coplanar  facet  (defined  by
	      'Vn',  'Un',  and	'C-n'),	merging	concave	facets,	merging	dupli-
	      cate 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  (de-
	      fined  by	 'C-n' and 'A-n'), then	post-merges are	performed (de-
	      fined by 'Cn' and	'An').

       Qz     Add a point "at infinity"	that is	above the paraboloid  for  De-
	      launay triangulations and	Voronoi	diagrams.  This	reduces	preci-
	      sion  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  is-
	      sues  while constructing the convex hull.	 This may lead to pre-
	      cision 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 in-
	      dependent	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 tri-
	      coplanar facets.

       Q12    With 'Q12', Qhull	does not report	a very wide merge due to a du-
	      plicated 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 pro-
	      gram.  'T2' and 'T3' trace overall execution and	geometric  and
	      topological  events.   'T4' traces the algorithm.	 'T5' includes
	      information about	memory allocation and Gaussian elimination.

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

       Tc     Check  frequently	during execution.  This	will catch most	incon-
	      sistency 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	parti-
	      tions of point n.	 If used with  TWn,  turn  off	tracing	 after
	      adding point n to	the hull.

       TRn    Rerun  qhull  n times.  Usually used with	'QJn' to determine the
	      probability that a given joggle will fail.

       Ts     Collect statistics and print to stderr at	the end	of execution.

       Tv     Verify the convex	hull.  This checks the topological  structure,
	      facet convexity, and point inclusion.  If	precision problems oc-
	      curred, facet convexity is tested	whether	or  not	 'Tv'  is  se-
	      lected.	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 al-
	      lows the user to interrupt Qhull without changing	the output.

       TVn    Stop Qhull after adding point n.	If n < 0,  stop	 Qhull	before
	      adding  point  n.	 Output	shows the hull at this time.  See also
	      'TCn'

       TMn    Turn on tracing at n'th merge.

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

       Tz     Redirect stderr to stdout.

BUGS
       Please report bugs to Brad Barber at qhull_bug@qhull.org.

       If Qhull	does not compile, it is	due to an incompatibility between your
       system  and  ours.   The	 first thing to	check is that your compiler is
       ANSI standard.  If it is, check the man page for	the best  options,  or
       find  someone  to  help	you.  If you locate the	cause of your problem,
       please send email since it might	help others.

       If Qhull	compiles but crashes on	the test case (rbox D4), there's still
       incompatibility	between	your system and	ours.  Typically it's been due
       to mem.c	and memory alignment.  You can use qh_NOmem in mem.h  to  turn
       off memory management.  Please let us know if you figure	out how	to fix
       these problems.

       If you do find a	problem, try to	simplify it before reporting  the  er-
       ror.   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.al-
       gorithms	and sci.math.num-analysis

SEE ALSO
       rbox(1)

       Barber,	C.  B.,	 D.P. Dobkin, and H.T. Huhdanpaa, "The Quickhull Algo-
       rithm  for  Convex  Hulls,"  ACM	 Trans.	 on   Mathematical   Software,
       22(4):469-483,	    Dec.       1996.	   http://portal.acm.org/cita-
       tion.cfm?doid=235815.235821   http://citeseerx.ist.psu.edu/viewdoc/sum-
       mary?doi=10.1.1.117.405

       Clarkson, K.L., K. Mehlhorn, and	R. Seidel, "Four results on randomized
       incremental construction," Computational	Geometry: Theory and  Applica-
       tions, 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 Cen-
       ter, 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  use-
       ful, 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

Geometry Center			  2003/12/30			      qhull(1)

NAME | SYNOPSIS | INTRODUCTION | DESCRIPTION | IMPRECISION | OPTIONS | BUGS | E-MAIL | SEE ALSO | AUTHORS | ACKNOWLEDGEMENTS

Want to link to this manual page? Use this URL:
<https://www.freebsd.org/cgi/man.cgi?query=qhull&sektion=1&manpath=FreeBSD+13.0-RELEASE+and+Ports>

home | help