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

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

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

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.

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,

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.

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

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

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://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/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-

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>