# FreeBSD Manual Pages

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

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

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

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

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

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