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>
	- CVS:	<http://savannah.nongnu.org/projects/qhull/>
	-  mirror:   <http://www6.uniovi.es/ftp/pub/mirrors/geom.umn.edu/soft-
       ware/ghindex.html>
	- news:	<http://www.qhull.org/news>
	- Geomview:  <http://www.geomview.org>
	- news group:	  <news:comp.graphics.algorithms>
	- FAQ:	     <http://exaflop.org/docs/cgafaq/cga6.html>
	- email:	  qhull@qhull.org
	- bug reports:	  qhull_bug@qhull.org

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

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

INTRODUCTION
       Qhull is	a general dimension code for computing convex hulls,  Delaunay
       triangulations,	Voronoi	 diagram,  furthest-site Voronoi diagram, 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
	      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 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 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 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.	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 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.	 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 points include the point-at-infinity.

       Fv     Print  vertices for each facet.  The first line is the number of
	      facets.  Then each facet is printed, one per line.  Each line is
	      the  number of vertices followed by the corresponding point ids.
	      Vertices are listed in the order they were  added	 to  the  hull
	      (the last	one is first).

       Fv     Print  all  ridges  of a Voronoi diagram.	 The first line	is the
	      number of	ridges.	 Then each ridge is printed, one per line.   A
	      line  starts  with  the number of	indices.  The first pair lists
	      adjacent input sites, the	remaining indices  list	 Voronoi  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).
	      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.
	      See also 'QJ'.

       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.

       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.

       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://www.acm.org/pubs/citations/jour-
       nals/toms/1996-22-4/p469-barber/	http://citeseer.nj.nec.com/83502.html

       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@qhull.org		    hannu@qhull.org

			   c/o The Geometry Center
			   University of Minnesota
			   400 Lind Hall
			   207 Church Street S.E.
			   Minneapolis,	MN 55455

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