1qhull(1)                    General Commands Manual                   qhull(1)
2
3
4

NAME

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

SYNOPSIS

10       qhull- compute convex hulls and related structures
11           input (stdin): dimension, #points, point coordinates
12           first comment (non-numeric) is listed in the summary
13           halfspace: use dim plus one with offsets after coefficients
14
15       options (qh-quick.htm):
16           d      - Delaunay triangulation by lifting points to a paraboloid
17           v      - Voronoi diagram via the Delaunay triangulation
18           H1,1   - Halfspace intersection about [1,1,0,...]
19           d Qu   - Furthest-site Delaunay triangulation (upper convex hull)
20           v Qu   - Furthest-site Voronoi diagram
21           Qt     - triangulated output
22           QJ     - Joggle the input to avoid precision problems
23           .      - concise list of all options
24           -      - one-line description of all options
25
26       Output options (subset):
27           FA     - compute total area and volume
28           Fx     - extreme points (convex hull vertices)
29           G      - Geomview output (2-d, 3-d and 4-d)
30           Fp     - halfspace intersection coordinates
31           m      - Mathematica output (2-d and 3-d)
32           n      - normals with offsets
33           o      - OFF file format (if Voronoi, outputs regions)
34           TO file- output results to file, may be enclosed in single quotes
35           f      - print all fields of all facets
36           s      - summary of results (default)
37           Tv     - verify result: structure, convexity, and point inclusion
38           p      - vertex coordinates (centers for Voronoi)
39           i      - vertices incident to each facet
40
41       example:
42           rbox 1000 s | qhull Tv s FA
43
44        - html manual:    index.htm
45        - installation:   README.txt
46        - see also:       COPYING.txt, REGISTER.txt, Changes.txt
47        - WWW:            <http://www.qhull.org>
48        - GIT:            <git@github.com:qhull/qhull.git>
49        -         mirror:                  <http://www6.uniovi.es/ftp/pub/mir
50       rors/geom.umn.edu/software/ghindex.html>
51        - news:           <http://www.qhull.org/news>
52        - Geomview:       <http://www.geomview.org>
53        - news group:     <news:comp.graphics.algorithms>
54        - FAQ:            <http://www.faqs.org/faqs/graphics/algorithms-faq/>
55        - email:          qhull@qhull.org
56        - bug reports:    qhull_bug@qhull.org
57
58       The sections are:
59        - INTRODUCTION
60        - DESCRIPTION, a description of Qhull
61        - IMPRECISION, how Qhull handles imprecision
62        - OPTIONS
63        -    Input and output options
64        -    Additional input/output formats
65        -    Precision options
66        -    Geomview options
67        -    Print options
68        -    Qhull options
69        -    Trace options
70        - BUGS
71        - E-MAIL
72        - SEE ALSO
73        - AUTHORS
74        - ACKNOWLEGEMENTS
75
76       This  man  page briefly describes all Qhull options.  Please report any
77       mismatches with Qhull's html manual (index.htm).
78
79

INTRODUCTION

81       Qhull is a general dimension code for computing convex hulls,  Delaunay
82       triangulations,  Voronoi  diagram,  furthest‐site Voronoi diagram, fur‐
83       thest‐site Delaunay triangulations, and halfspace intersections about a
84       point.   It implements the Quickhull algorithm for computing the convex
85       hull.  Qhull handles round‐off errors from floating  point  arithmetic.
86       It can approximate a convex hull.
87
88       The  program  includes  options  for  hull  volume, facet area, partial
89       hulls, input transformations, randomization, tracing,  multiple  output
90       formats,  and  execution  statistics.   The  program can be called from
91       within your application.  You can view the results in 2‐d, 3‐d and  4‐d
92       with Geomview.
93

DESCRIPTION

95       The  format  of  input is the following: first line contains the dimen‐
96       sion, second line contains the number of input points, and point  coor‐
97       dinates  follow.   The  dimension and number of points can be reversed.
98       Comments and line breaks are ignored.  A comment  starts  with  a  non‐
99       numeric  character and continues to the end of line.  The first comment
100       is reported in summaries and statistics.  Error reporting is better  if
101       there is one point per line.
102
103       The  default  printout  option is a short summary. There are many other
104       output formats.
105
106       Qhull implements the Quickhull algorithm for convex  hull.  This  algo‐
107       rithm  combines the 2‐d Quickhull algorithm with the n‐d beneath‐beyond
108       algorithm [c.f., Preparata & Shamos '85].  It is similar to the random‐
109       ized algorithms of Clarkson and others [Clarkson et al. '93].  The main
110       advantages of Quickhull are output sensitive performance, reduced space
111       requirements, and automatic handling of precision problems.
112
113       The  data structure produced by Qhull consists of vertices, ridges, and
114       facets.  A vertex is a point of the input set.  A ridge is a set  of  d
115       vertices and two neighboring facets.  For example in 3‐d, a ridge is an
116       edge of the polyhedron.  A facet is a set of ridges, a set of neighbor‐
117       ing facets, a set of incident vertices, and a hyperplane equation.  For
118       simplicial facets, the ridges are defined by the vertices and neighbor‐
119       ing facets.  When Qhull merges two facets, it produces a non‐simplicial
120       facet.  A non‐simplicial facet has more than d neighbors and may  share
121       more than one ridge with a neighbor.
122

IMPRECISION

124       Since  Qhull  uses  floating point arithmetic, roundoff error may occur
125       for each calculation.  This causes  problems for most  geometric  algo‐
126       rithms.
127
128       Qhull  automatically  sets option 'C-0' in 2‐d, 3‐d, and 4‐d, or option
129       'Qx' in 5‐d and higher.  These options  handle  precision  problems  by
130       merging facets.  Alternatively, use option 'QJ' to joggle the input.
131
132       With 'C-0', Qhull merges non‐convex facets while constructing the hull.
133       The remaining facets are clearly convex. With 'Qx', Qhull merges copla‐
134       nar  horizon  facets,  flipped  facets,  concave  facets and duplicated
135       ridges.  It merges coplanar facets after constructing the  hull.   With
136       'Qx', coplanar points may be missed, but it appears to be unlikely.
137
138       To  guarantee  triangular  output,  joggle  the input with option 'QJ'.
139       Facet merging will not occur.
140

OPTIONS

142       To get a list of the most important options, execute 'qhull' by itself.
143       To  get  a  complete list of options, execute 'qhull -'.  To get a com‐
144       plete, concise list of options, execute 'qhull .'.
145
146       Options can be in any order.   Capitalized  options  take  an  argument
147       (except 'PG' and 'F' options).  Single letters are used for output for‐
148       mats and precision constants.  The other options are grouped into menus
149       for  other output formats ('F'), Geomview output ('G'), printing ('P'),
150       Qhull control ('Q'), and tracing ('T').
151
152       Main options:
153
154       default
155              Compute the convex hull of the input points.  Report  a  summary
156              of the result.
157
158       d      Compute  the  Delaunay triangulation by lifting the input points
159              to a paraboloid.  The 'o' option prints  the  input  points  and
160              facets.  The 'QJ' option guarantees triangular output.  The 'Ft'
161              option prints a triangulation.  It adds points (the centrums) to
162              non‐simplicial facets.
163
164       v      Compute  the  Voronoi  diagram  from the Delaunay triangulation.
165              The 'p' option prints the  Voronoi  vertices.   The  'o'  option
166              prints  the  Voronoi  vertices  and the vertices in each Voronoi
167              region.  It lists regions in site ID  order.   The  'Fv'  option
168              prints  each ridge of the Voronoi diagram.  The first or zero'th
169              vertex indicates  the  infinity  vertex.   Its  coordinates  are
170              qh_INFINITE  (-10.101).   It indicates unbounded Voronoi regions
171              or degenerate Delaunay triangles.
172
173       Hn,n,...
174              Compute halfspace intersection about [n,n,0,...].  The input  is
175              a set of halfspaces defined in the same format as 'n', 'Fo', and
176              'Fi'.  Use 'Fp' to print the intersection points.  Use  'Fv'  to
177              list the intersection points for each halfspace.  The other out‐
178              put formats display the dual convex hull.
179
180              The point [n,n,n,...] is a feasible point  for  the  halfspaces,
181              i.e.,  a point that is inside all of the halfspaces (Hx+b <= 0).
182              The default coordinate value is 0.
183
184              The input may start with a feasible point.  If so,  use  'H'  by
185              itself.   The  input starts with a feasible point when the first
186              number is the dimension, the second number is "1", and the coor‐
187              dinates  complete  a  line.  The 'FV' option produces a feasible
188              point for a convex hull.
189
190       d Qu   Compute the furthest‐site Delaunay triangulation from the  upper
191              convex hull.  The 'o' option prints the input points and facets.
192              The 'QJ' option guarantees triangular otuput.  You can also  use
193              'Ft' to triangulate via the centrums of non‐simplicial facets.
194
195       v Qu   Compute  the  furthest‐site  Voronoi  diagram.   The  'p' option
196              prints the Voronoi vertices.  The 'o' option prints the  Voronoi
197              vertices  and  the  vertices  in  each Voronoi region.  The 'Fv'
198              option prints each ridge of the Voronoi diagram.  The  first  or
199              zero'th  vertex  indicates the infinity vertex at infinity.  Its
200              coordinates are qh_INFINITE (-10.101).  It  indicates  unbounded
201              Voronoi regions and degenerate Delaunay triangles.
202
203       Input/Output options:
204
205       f      Print out all facets and all fields of each facet.
206
207       G      Output  the  hull  in  Geomview  format.   For  imprecise hulls,
208              Geomview displays the inner and outer hull.  Geomview  can  also
209              display  points,  ridges,  vertices,  coplanar points, and facet
210              intersections.  See below for a list of options.
211
212              For Delaunay triangulations, 'G' displays the corresponding  pa‐
213              raboloid.   For  halfspace  intersection,  'G' displays the dual
214              polytope.
215
216       i      Output the incident vertices for each facet.  Qhull  prints  the
217              number  of  facets  followed by the vertices of each facet.  One
218              facet is printed per  line.   The  numbers  are  the  0‐relative
219              indices  of the corresponding input points.  The facets are ori‐
220              ented.
221
222              In 4d and  higher,  Qhull  triangulates  non‐simplicial  facets.
223              Each apex (the first vertex) is a created point that corresponds
224              to the facet's centrum.  Its index is greater than  the  indices
225              of  the  input  points.   Each  base corresponds to a simplicial
226              ridge between two facets.  To print the vertices without  trian‐
227              gulation, use option 'Fv'.
228
229       m      Output the hull in Mathematica format.  Qhull writes a Mathemat‐
230              ica file for 2‐d and 3‐d convex hulls and for 2‐d Delaunay  tri‐
231              angulations.    Qhull  produces  a  list of objects that you can
232              assign to a variable in  Mathematica,  for  example:  "list=  <<
233              <outputfilename>  ".  If the object is 2‐d, it can be visualized
234              by "Show[Graphics[list]] ".  For  3‐d  objects  the  command  is
235              "Show[Graphics3D[list]]".
236
237       n      Output  the  normal  equation  for each facet.  Qhull prints the
238              dimension (plus one), the number of facets, and the normals  for
239              each facet.  The facet's offset follows its normal coefficients.
240
241       o      Output  the  facets in OFF file format.  Qhull prints the dimen‐
242              sion, number of points, number of facets, and number of  ridges.
243              Then  it prints the coordinates of the input points and the ver‐
244              tices for each facet.  Each facet is on a  separate  line.   The
245              first  number  is the number of vertices.  The remainder are the
246              indices of the corresponding points.  The vertices are  oriented
247              in 2‐d, 3‐d, and in simplicial facets.
248
249              For  2‐d Voronoi diagrams, the vertices are sorted by adjacency,
250              but not oriented.  In 3‐d and higher, the Voronoi  vertices  are
251              sorted by index.  See the 'v' option for more information.
252
253       p      Output  the  coordinates of each vertex point.  Qhull prints the
254              dimension, the number of points, and the  coordinates  for  each
255              vertex.  With the 'Gc' and 'Gi' options, it also prints coplanar
256              and interior points.  For Voronoi diagrams, it prints the  coor‐
257              dinates of each Voronoi vertex.
258
259       s      Print  a  summary to stderr.  If no output options are specified
260              at all, a summary goes to stdout.  The summary lists the  number
261              of  input  points,  the dimension, the number of vertices in the
262              convex hull, the number of facets in the convex hull, the number
263              of good facets (if 'Pg'), and statistics.
264
265              The last two statistics (if needed) measure the maximum distance
266              from a point or vertex to a facet.  The  number  in  parenthesis
267              (e.g.,  2.1x)  is the ratio between the maximum distance and the
268              worst‐case distance due to merging two simplicial facets.
269
270       Precision options
271
272       An     Maximum angle given as a cosine.  If the angle between a pair of
273              facet  normals is greater than n, Qhull merges one of the facets
274              into a neighbor.  If 'n' is negative, Qhull tests  angles  after
275              adding  each  point  to the hull (pre‐merging).  If 'n' is posi‐
276              tive, Qhull tests angles after constructing the hull (post‐merg‐
277              ing).  Both pre‐ and post‐merging can be defined.
278
279              Option  'C0'  or 'C-0' is set if the corresponding 'Cn' or 'C-n'
280              is not set.  If 'Qx' is set, then 'A-n' and  'C-n'  are  checked
281              after  the  hull  is  constructed  and  before 'An' and 'Cn' are
282              checked.
283
284       Cn     Centrum radius.  If a centrum is less than n below a neighboring
285              facet,  Qhull  merges  one of the facets.  If 'n' is negative or
286              '-0', Qhull tests and merges facets after adding each  point  to
287              the  hull.   This  is called "pre‐merging".  If 'n' is positive,
288              Qhull tests for convexity after constructing  the  hull  ("post‐
289              merging").  Both pre‐ and post‐merging can be defined.
290
291              For  5‐d and higher, 'Qx' should be used instead of 'C-n'.  Oth‐
292              erwise, most or all facets may be merged together.
293
294       En     Maximum roundoff error for distance computations.
295
296       Rn     Randomly perturb distance computations up to +/- n *  max_coord.
297              This  option perturbs every distance, hyperplane, and angle com‐
298              putation.  To use time as the random  number  seed,  use  option
299              'QR-1'.
300
301       Vn     Minimum  distance for a facet to be visible.  A facet is visible
302              if the distance from the point to  the  facet  is  greater  than
303              'Vn'.
304
305              Without  merging,  the  default  value for 'Vn' is the round‐off
306              error ('En').  With merging, the default value is the  pre‐merge
307              centrum  ('C-n')  in  2‐d  or  3‐d, or three times that in other
308              dimensions.  If the outside width is specified ('Wn'), the maxi‐
309              mum, default value for 'Vn' is 'Wn'.
310
311       Un     Maximum distance below a facet for a point to be coplanar to the
312              facet.  The default value is 'Vn'.
313
314       Wn     Minimum outside width of the hull.  Points are added to the con‐
315              vex  hull  only if they are clearly outside of a facet.  A point
316              is outside of a facet if its distance to the  facet  is  greater
317              than  'Wn'.   The  normal  value  for 'Wn' is 'En'.  If the user
318              specifies pre‐merging and does not set 'Wn', than 'Wn' is set to
319              the premerge 'Cn' and maxcoord*(1-An).
320
321       Additional input/output formats
322
323       Fa     Print  area  for  each  facet.  For Delaunay triangulations, the
324              area is the area of the triangle.   For  Voronoi  diagrams,  the
325              area  is the area of the dual facet.  Use 'PAn' for printing the
326              n largest facets, and option 'PFn' for  printing  facets  larger
327              than 'n'.
328
329              The  area  for non‐simplicial facets is the sum of the areas for
330              each ridge to the centrum.    Vertices  far  below  the  facet's
331              hyperplane  are ignored.  The reported area may be significantly
332              less than the actual area.
333
334       FA     Compute the total area and volume for  option  's'.   It  is  an
335              approximation for non‐simplicial facets (see 'Fa').
336
337       Fc     Print  coplanar  points  for each facet.  The output starts with
338              the number of facets.  Then each facet is printed one per  line.
339              Each line is the number of coplanar points followed by the point
340              ids.  Option 'Qi' includes the interior points.   Each  coplanar
341              point  (interior  point) is assigned to the facet it is furthest
342              above (resp., least below).
343
344       FC     Print centrums for each  facet.   The  output  starts  with  the
345              dimension  followed  by  the  number of facets.  Then each facet
346              centrum is printed, one per line.
347
348       Fd     Read input in cdd format with  homogeneous  points.   The  input
349              starts with comments.  The first comment is reported in the sum‐
350              mary.  Data starts after a "begin" line.  The next line  is  the
351              number  of  points  followed  by  the  dimension+1 and "real" or
352              "integer".  Then the points are listed  with a  leading  "1"  or
353              "1.0".  The data ends with an "end" line.
354
355              For  halfspaces  ('Fd  Hn,n,...'), the input format is the same.
356              Each halfspace starts with its offset.  The sign of  the  offset
357              is the opposite of Qhull's convention.
358
359       FD     Print  normals  ('n', 'Fo', 'Fi') or points ('p') in cdd format.
360              The first line is the command line  that  invoked  Qhull.   Data
361              starts with a "begin" line.  The next line is the number of nor‐
362              mals or points followed by the dimension+1 and "real".  Then the
363              normals or points are listed  with the offset before the coeffi‐
364              cients.  The offset for points is 1.0.  The offset  for  normals
365              has the opposite sign.  The data ends with an "end" line.
366
367       FF     Print facets (as in 'f') without printing the ridges.
368
369       Fi     Print inner planes for each facet.  The inner plane is below all
370              vertices.
371
372       Fi     Print separating hyperplanes for bounded, inner regions  of  the
373              Voronoi  diagram.  The first line is the number of ridges.  Then
374              each hyperplane is printed, one per line.  A  line  starts  with
375              the number of indices and floats.  The first pair lists adjacent
376              input sites, the next d floats are the  normalized  coefficients
377              for  the  hyperplane,  and  the  last  float is the offset.  The
378              hyperplane is oriented toward 'QVn' (if defined), or  the  first
379              input site of the pair.  Use 'Tv' to verify that the hyperplanes
380              are perpendicular bisectors.  Use 'Fo'  for  unbounded  regions,
381              and 'Fv' for the corresponding Voronoi vertices.
382
383       FI     Print facet identifiers.
384
385       Fm     Print  number  of merges for each facet.  At most 511 merges are
386              reported for a facet.  See 'PMn' for printing  the  facets  with
387              the most merges.
388
389       FM     Output  the hull in Maple format.  Qhull writes a Maple file for
390              2‐d and 3‐d convex hulls and for  2‐d  Delaunay  triangulations.
391              Qhull produces a '.mpl' file for displaying with display3d().
392
393       Fn     Print neighbors for each facet.  The output starts with the num‐
394              ber of facets.  Then each facet is printed one per  line.   Each
395              line  is  the  number of neighbors followed by an index for each
396              neighbor.  The indices match the other facet output formats.
397
398              A negative index indicates an unprinted facet  due  to  printing
399              only  good  facets ('Pg').  It is the negation of the facet's ID
400              (option 'FI').  For  example,  negative  indices  are  used  for
401              facets "at infinity" in the Delaunay triangulation.
402
403       FN     Print  vertex  neighbors  or coplanar facet for each point.  The
404              first line is the number of points.  Then each point is printed,
405              one  per  line.   If the point is coplanar, the line is "1" fol‐
406              lowed by the facet's ID.  If the point is not a selected vertex,
407              the  line  is "0".  Otherwise, each line is the number of neigh‐
408              bors followed by the corresponding facet indices (see 'Fn').
409
410       Fo     Print outer planes for each facet in the  same  format  as  'n'.
411              The outer plane is above all points.
412
413       Fo     Print separating hyperplanes for unbounded, outer regions of the
414              Voronoi diagram.  The first line is the number of ridges.   Then
415              each  hyperplane  is  printed, one per line.  A line starts with
416              the number of indices and floats.  The first pair lists adjacent
417              input  sites,  the next d floats are the normalized coefficients
418              for the hyperplane, and the  last  float  is  the  offset.   The
419              hyperplane  is  oriented toward 'QVn' (if defined), or the first
420              input site of the pair.  Use 'Tv' to verify that the hyperplanes
421              are  perpendicular bisectors.  Use 'Fi' for bounded regions, and
422              'Fv' for the corresponding Voronoi vertices.
423
424       FO     List all options to stderr, including the default values.  Addi‐
425              tional 'FO's are printed to stdout.
426
427       Fp     Print  points  for  halfspace intersections (option 'Hn,n,...').
428              Each intersection corresponds to a facet of the  dual  polytope.
429              The   "infinity"   point   [-10.101,-10.101,...]   indicates  an
430              unbounded intersection.
431
432       FP     For each coplanar point ('Qc') print the point ID of the nearest
433              vertex, the point ID, the facet ID, and the distance.
434
435       FQ     Print command used for qhull and input.
436
437       Fs     Print a summary.  The first line consists of the number of inte‐
438              gers ("8"), followed by the dimension, the number of points, the
439              number of vertices, the number of facets, the number of vertices
440              selected for output, the number of facets selected  for  output,
441              the  number  of  coplanar  points selected for output, number of
442              simplicial, unmerged facets in output
443
444              The second line consists of the number of reals ("2"),  followed
445              by  the maxmimum offset to an outer plane and and minimum offset
446              to an inner plane.  Roundoff is  included.   Later  versions  of
447              Qhull may produce additional integers or reals.
448
449       FS     Print the size of the hull.  The first line consists of the num‐
450              ber of integers ("0").  The second line consists of  the  number
451              of  reals ("2"), followed by the total facet area, and the total
452              volume.  Later versions of Qhull may produce additional integers
453              or reals.
454
455              The  total volume measures the volume of the intersection of the
456              halfspaces defined by each facet.   Both  area  and  volume  are
457              approximations for non‐simplicial facets.  See option 'Fa'.
458
459       Ft     Print  a  triangulation  with  added  points  for non‐simplicial
460              facets.  The first line is the dimension and the second line  is
461              the  number of points and the number of facets.  The points fol‐
462              low, one per line, then the facets follow as  a  list  of  point
463              indices.   With  option  'Qz',  the points include the point‐at‐
464              infinity.
465
466       Fv     Print vertices for each facet.  The first line is the number  of
467              facets.  Then each facet is printed, one per line.  Each line is
468              the number of vertices followed by the corresponding point  ids.
469              Vertices  are  listed  in  the order they were added to the hull
470              (the last one is first).
471
472       Fv     Print all ridges of a Voronoi diagram.  The first  line  is  the
473              number  of ridges.  Then each ridge is printed, one per line.  A
474              line starts with the number of indices.  The  first  pair  lists
475              adjacent  input  sites,  the remaining indices list Voronoi ver‐
476              tices.  Vertex '0' indicates the  vertex‐at‐infinity  (i.e.,  an
477              unbounded  ray).  In 3‐d, the vertices are listed in order.  See
478              'Fi' and 'Fo' for separating hyperplanes.
479
480       FV     Print average vertex.  The average vertex is  a  feasible  point
481              for halfspace intersection.
482
483       Fx     List  extreme  points  (vertices) of the convex hull.  The first
484              line is the number of points.  The other lines give the  indices
485              of  the  corresponding points.  The first point is '0'.  In 2‐d,
486              the points occur  in  counter‐clockwise  order;  otherwise  they
487              occur  in  input order.  For Delaunay triangulations, 'Fx' lists
488              the  extreme  points  of  the  input  sites.   The  points   are
489              unordered.
490
491       Geomview options
492
493       G      Produce  a  file  for  viewing  with  Geomview.   Without  other
494              options, Qhull displays edges in 2‐d, outer planes in  3‐d,  and
495              ridges  in  4‐d.   A  ridge  can  be  explicit  or implicit.  An
496              explicit ridge  is  a  dim-1  dimensional  simplex  between  two
497              facets.   In  4‐d, the explicit ridges are triangles.  When dis‐
498              playing a ridge in 4‐d, Qhull projects the ridge's  vertices  to
499              one  of  its facets' hyperplanes.  Use 'Gh' to project ridges to
500              the intersection of both hyperplanes.
501
502       Ga     Display all input points as dots.
503
504       Gc     Display the centrum for each  facet  in  3‐d.   The  centrum  is
505              defined  by  a  green radius sitting on a blue plane.  The plane
506              corresponds to the facet's hyperplane.  The radius is defined by
507              'C-n' or 'Cn'.
508
509       GDn    Drop  dimension  n  in  3‐d  or 4‐d.  The result is a 2‐d or 3‐d
510              object.
511
512       Gh     Display hyperplane intersections in 3‐d and 4‐d.   In  3‐d,  the
513              intersection is a black line.  It lies on two neighboring hyper‐
514              planes (c.f., the blue squares associated with centrums ('Gc')).
515              In  4‐d,  the  ridges  are projected to the intersection of both
516              hyperplanes.
517
518       Gi     Display inner planes in 2‐d and 3‐d.  The inner plane of a facet
519              is  below  all  of  its vertices.  It is parallel to the facet's
520              hyperplane.   The  inner   plane's   color   is   the   opposite
521              (1-r,1-g,1-b)  of  the outer plane.  Its edges are determined by
522              the vertices.
523
524       Gn     Do not display inner or outer planes.  By default, Geomview dis‐
525              plays  the  precise  plane (no merging) or both inner and output
526              planes (merging).  Under merging, Geomview does not display  the
527              inner plane if the the difference between inner and outer is too
528              small.
529
530       Go     Display outer planes in 2‐d and 3‐d.  The outer plane of a facet
531              is above all input points.  It is parallel to the facet's hyper‐
532              plane.  Its color is determined by the facet's normal,  and  its
533              edges are determined by the vertices.
534
535       Gp     Display coplanar points and vertices as radii.  A radius defines
536              a ball which corresponds to the imprecision of the  point.   The
537              imprecision  is  the  maximum of the roundoff error, the centrum
538              radius, and maxcoord * (1-An).  It is at least  1/20'th  of  the
539              maximum  coordinate,  and ignores post‐merging if pre‐merging is
540              done.
541
542       Gr     Display ridges in 3‐d.  A ridge connects the two  vertices  that
543              are  shared  by neighboring facets.  Ridges are always displayed
544              in 4‐d.
545
546       Gt     A 3‐d Delaunay triangulation looks like a convex hull with inte‐
547              rior  facets.   Option 'Gt' removes the outside ridges to reveal
548              the outermost facets.  It automatically sets  options  'Gr'  and
549              'GDn'.
550
551       Gv     Display  vertices  as  spheres.  The radius of the sphere corre‐
552              sponds to the imprecision of the data.  See 'Gp' for determining
553              the radius.
554
555       Print options
556
557       PAn    Only  the n largest facets are marked good for printing.  Unless
558              'PG' is set, 'Pg' is automatically set.
559
560       Pdk:n  Drop facet from output if normal[k] <= n.  The option 'Pdk' uses
561              the default value of 0 for n.
562
563       PDk:n  Drop facet from output if normal[k] >= n.  The option 'PDk' uses
564              the default value of 0 for n.
565
566       PFn    Only facets with area at least 'n' are marked good for printing.
567              Unless 'PG' is set, 'Pg' is automatically set.
568
569       Pg     Print  only  good facets.  A good facet is either visible from a
570              point (the 'QGn' option) or includes a point (the 'QVn' option).
571              It  also  meets  the  requirements  of  'Pdk' and 'PDk' options.
572              Option 'Pg' is automatically set for options 'PAn' and 'PFn'.
573
574       PG     Print neighbors of good facets.
575
576       PMn    Only the n facets with the  most  merges  are  marked  good  for
577              printing.  Unless 'PG' is set, 'Pg' is automatically set.
578
579       Po     Force output despite precision problems.  Verify ('Tv') does not
580              check coplanar points.  Flipped facets are reported and  concave
581              facets are counted.  If 'Po' is used, points are not partitioned
582              into flipped facets and a flipped facet is always visible  to  a
583              point.   Also, if an error occurs before the completion of Qhull
584              and tracing is not active, 'Po' outputs a  neighborhood  of  the
585              erroneous facets (if any).
586
587       Pp     Do not report precision problems.
588
589       Qhull control options
590
591       Qbk:0Bk:0
592              Drop dimension k from the input points.  This allows the user to
593              take convex hulls of sub‐dimensional objects.  It happens before
594              the Delaunay and Voronoi transformation.
595
596       QbB    Scale the input points to fit the unit cube.  After scaling, the
597              lower bound will be -0.5 and the upper bound +0.5 in all  dimen‐
598              sions.  For Delaunay and Voronoi diagrams, scaling happens after
599              projection to the paraboloid.  Under precise arithmetic, scaling
600              does not change the topology of the convex hull.
601
602       Qbb    Scale the last coordinate to [0, m] where m is the maximum abso‐
603              lute value of the other coordinates.  For Delaunay  and  Voronoi
604              diagrams,  scaling  happens  after projection to the paraboloid.
605              It reduces roundoff error for inputs with  integer  coordinates.
606              Under  precise  arithmetic, scaling does not change the topology
607              of the convex hull.
608
609       Qbk:n  Scale the k'th coordinate of the input points.   After  scaling,
610              the  lower bound of the input points will be n.  'Qbk' scales to
611              -0.5.
612
613       QBk:n  Scale the k'th coordinate of the input points.   After  scaling,
614              the upper bound will be n.  'QBk' scales to +0.5.
615
616       Qc     Keep  coplanar  points  with  the nearest facet.  Output formats
617              'p', 'f', 'Gp', 'Fc', 'FN', and 'FP' will print the points.
618
619       Qf     Partition points to the furthest outside facet.
620
621       Qg     Only build good facets.  With the 'Qg' option, Qhull  will  only
622              build those facets that it needs to determine the good facets in
623              the output.  See 'QGn',  'QVn',  and  'PdD'  for  defining  good
624              facets,  and  'Pg'  and  'PG' for printing good facets and their
625              neighbors.
626
627       QGn    A facet is good (see 'Qg' and 'Pg') if it is visible from  point
628              n.  If n < 0, a facet is good if it is not visible from point n.
629              Point n is not added to the hull (unless 'TCn' or 'TPn').   With
630              rbox,  use  the 'Pn,m,r' option to define your point; it will be
631              point 0 (QG0).
632
633       Qi     Keep interior points with the  nearest  facet.   Output  formats
634              'p', 'f', 'Gp', 'FN', 'FP', and 'Fc' will print the points.
635
636       QJn    Joggle  each  input  coordinate  by  adding  a  random number in
637              [-n,n].  If a precision error occurs, then qhull increases n and
638              tries again.  It does not increase n beyond a certain value, and
639              it stops after  a  certain  number  of  attempts  [see  user.h].
640              Option  'QJ'  selects a default value for n.  The output will be
641              simplicial.  For Delaunay triangulations, 'QJn'  sets  'Qbb'  to
642              scale  the  last  coordinate (not if 'Qbk:n' or 'QBk:n' is set).
643              ´QJn' is deprecated for Voronoi diagrams.  See also 'Qt'.
644
645       Qm     Only process points that would otherwise  increase  max_outside.
646              Other points are treated as coplanar or interior points.
647
648       Qr     Process  random  outside  points instead of furthest ones.  This
649              makes Qhull equivalent to the randomized incremental algorithms.
650              CPU time is not reported since the randomization is inefficient.
651
652       QRn    Randomly  rotate the input points.  If n=0, use time as the ran‐
653              dom number seed.  If n>0, use n as the random number  seed.   If
654              n=-1,  don't rotate but use time as the random number seed.  For
655              Delaunay triangulations ('d' and 'v'),  rotate  about  the  last
656              axis.
657
658       Qs     Search all points for the initial simplex.
659
660       Qt     Triangulated  output.   Triangulate  all  non‐simplicial facets.
661              ´Qt' is deprecated for Voronoi diagrams.  See also 'Qt'.
662
663       Qv     Test vertex neighbors for convexity after post‐merging.  To  use
664              the 'Qv' option, you also need to set a merge option (e.g., 'Qx'
665              or 'C-0').
666
667       QVn    A good facet (see 'Qg' and 'Pg') includes point n.  If n<0, then
668              a  good  facet does not include point n.  The point is either in
669              the initial simplex or it is the first point added to the  hull.
670              Option 'QVn' may not be used with merging.
671
672       Qx     Perform  exact  merges  while  building  the  hull.  The "exact"
673              merges are merging a point into a  coplanar  facet  (defined  by
674              'Vn',  'Un',  and 'C-n'), merging concave facets, merging dupli‐
675              cate ridges, and merging flipped facets.   Coplanar  merges  and
676              angle  coplanar  merges  ('A-n')  are  not performed.  Concavity
677              testing is delayed until a merge occurs.
678
679              After the hull is  built,  all  coplanar  merges  are  performed
680              (defined  by  'C-n'  and  'A-n'), then post‐merges are performed
681              (defined by 'Cn' and 'An').
682
683       Qz     Add a point "at infinity"  that  is  above  the  paraboloid  for
684              Delaunay triangulations and Voronoi diagrams.  This reduces pre‐
685              cision problems and  allows  the  triangulation  of  cospherical
686              points.
687
688       Qhull experiments and speedups
689
690       Q0     Turn  off  pre‐merging  as a default option.  With 'Q0'/'Qx' and
691              without explicit  pre‐merge  options,  Qhull  ignores  precision
692              issues  while  constructing  the  convex hull.  This may lead to
693              precision errors.  If so, a descriptive warning is generated.
694
695       Q1     With 'Q1', Qhull sorts merges by type (coplanar, angle coplanar,
696              concave) instead of by angle.
697
698       Q2     With  'Q2',  Qhull  merges  all  facets at once instead of using
699              independent sets of merges and then retesting.
700
701       Q3     With 'Q3', Qhull does not remove redundant vertices.
702
703       Q4     With 'Q4', Qhull avoids merges of an old facet into a new facet.
704
705       Q5     With 'Q5', Qhull does not correct outer planes at the end.   The
706              maximum outer plane is used instead.
707
708       Q6     With 'Q6', Qhull does not pre‐merge concave or coplanar facets.
709
710       Q7     With  'Q7',  Qhull processes facets in depth‐first order instead
711              of breadth‐first order.
712
713       Q8     With 'Q8' and  merging,  Qhull  does  not  retain  near‐interior
714              points  for  adjusting  outer planes.  'Qc' will probably retain
715              all points that adjust outer planes.
716
717       Q9     With 'Q9', Qhull processes the furthest of all outside  sets  at
718              each iteration.
719
720       Q10    With  'Q10',  Qhull  does  not use special processing for narrow
721              distributions.
722
723       Q11    With 'Q11', Qhull copies normals and recompute centrums for tri‐
724              coplanar facets.
725
726       Q12    With  'Q12',  Qhull  does  not report a very wide merge due to a
727              duplicated ridge with nearly coincident vertices
728
729       Trace options
730
731       Tn     Trace at level n.  Qhull includes full execution tracing.  'T-1'
732              traces  events.   'T1'  traces the overall execution of the pro‐
733              gram.  'T2' and 'T3' trace overall execution and  geometric  and
734              topological  events.   'T4' traces the algorithm.  'T5' includes
735              information about memory allocation and Gaussian elimination.
736
737       Ta     Annotate output  with  codes  that  identify  the  corresponding
738              qh_fprintf() statement.
739
740       Tc     Check  frequently during execution.  This will catch most incon‐
741              sistency errors.
742
743       TCn    Stop Qhull after building the cone of new facets  for  point  n.
744              The output for 'f' includes the cone and the old hull.  See also
745              'TVn'.
746
747       TFn    Report progress whenever more than n facets are  created  During
748              post‐merging, 'TFn' reports progress after more than n/2 merges.
749
750       TI file
751              Input  data from 'file'.  The filename may not include spaces or
752              quotes.
753
754       TO file
755              Output results to 'file'.  The name may be  enclosed  in  single
756              quotes.
757
758       TPn    Turn on tracing when point n is added to the hull.  Trace parti‐
759              tions of point n.  If used with  TWn,  turn  off  tracing  after
760              adding point n to the hull.
761
762       TRn    Rerun  qhull  n times.  Usually used with 'QJn' to determine the
763              probability that a given joggle will fail.
764
765       Ts     Collect statistics and print to stderr at the end of execution.
766
767       Tv     Verify the convex hull.  This checks the topological  structure,
768              facet  convexity,  and  point  inclusion.  If precision problems
769              occurred, facet convexity is  tested  whether  or  not  'Tv'  is
770              selected.  Option 'Tv' does not check point inclusion if forcing
771              output with 'Po', or if 'Q5' is set.
772
773              For point inclusion testing, Qhull verifies that all points  are
774              below  all outer planes (facet->maxoutside).  Point inclusion is
775              exhaustive if merging or if the  facet‐point  product  is  small
776              enough;  otherwise  Qhull  verifies  each  point with a directed
777              search (qh_findbest).
778
779              Point inclusion  testing  occurs  after  producing  output.   It
780              prints  a  message  to  stderr unless option 'Pp' is used.  This
781              allows the user to interrupt Qhull without changing the output.
782
783       TVn    Stop Qhull after adding point n.  If n < 0,  stop  Qhull  before
784              adding  point  n.  Output shows the hull at this time.  See also
785              'TCn'
786
787       TMn    Turn on tracing at n'th merge.
788
789       TWn    Trace merge facets when the width is greater than n.
790
791       Tz     Redirect stderr to stdout.
792

BUGS

794       Please report bugs to Brad Barber at qhull_bug@qhull.org.
795
796       If Qhull does not compile, it is due to an incompatibility between your
797       system  and  ours.   The  first thing to check is that your compiler is
798       ANSI standard.  If it is, check the man page for the best  options,  or
799       find  someone  to  help  you.  If you locate the cause of your problem,
800       please send email since it might help others.
801
802       If Qhull compiles but crashes on the test case (rbox D4), there's still
803       incompatibility  between your system and ours.  Typically it's been due
804       to mem.c and memory alignment.  You can use qh_NOmem in mem.h  to  turn
805       off memory management.  Please let us know if you figure out how to fix
806       these problems.
807
808       If you do find a problem, try  to  simplify  it  before  reporting  the
809       error.   Try  different  size  inputs  to  locate the smallest one that
810       causes an error.  You're welcome to hunt through  the  code  using  the
811       execution trace as a guide.  This is especially true if you're incorpo‐
812       rating Qhull into your own program.
813
814       When you do report an error, please attach a data set  to  the  end  of
815       your message.  This allows us to see the error for ourselves.  Qhull is
816       maintained part‐time.
817

E‐MAIL

819       Please send  correspondence  to  qhull@qhull.org  and  report  bugs  to
820       qhull_bug@qhull.org.  Let us know how you use Qhull.  If you mention it
821       in a paper, please send the reference and an abstract.
822
823       If you would like to get Qhull announcements (e.g., a new version)  and
824       news  (any  bugs that get fixed, etc.), let us know and we will add you
825       to our mailing list.  If you would like to communicate with other Qhull
826       users,  we  will  add  you to the qhull_users alias.  For Internet news
827       about geometric  algorithms  and  convex  hulls,  look  at  comp.graph‐
828       ics.algorithms and sci.math.num-analysis
829
830

SEE ALSO

832       rbox(1)
833
834       Barber,  C.  B.,  D.P. Dobkin, and H.T. Huhdanpaa, "The Quickhull Algo‐
835       rithm  for  Convex  Hulls,"  ACM  Trans.  on   Mathematical   Software,
836       22(4):469–483,       Dec.       1996.       http://portal.acm.org/cita
837       tion.cfm?doid=235815.235821   http://citeseerx.ist.psu.edu/viewdoc/sum
838       mary?doi=10.1.1.117.405
839
840       Clarkson, K.L., K. Mehlhorn, and R. Seidel, "Four results on randomized
841       incremental construction," Computational Geometry: Theory and  Applica‐
842       tions, vol. 3, p. 185–211, 1993.
843
844       Preparata,  F.  and M. Shamos, Computational Geometry, Springer‐Verlag,
845       New York, 1985.
846
847

AUTHORS

849         C. Bradford Barber                    Hannu Huhdanpaa
850         bradb@shore.net                       hannu@qhull.org
851
852        .fi
853
854

ACKNOWLEDGEMENTS

856       A special thanks to Albert Marden, Victor Milenkovic, the Geometry Cen‐
857       ter, Harvard University, and Endocardial Solutions, Inc. for supporting
858       this work.
859
860       Qhull 1.0 and 2.0 were  developed  under  National  Science  Foundation
861       grants  NSF/DMS‐8920161  and  NSF‐CCR‐91‐15793  750‐7504.  David Dobkin
862       guided the original work at Princeton University.  If you find it  use‐
863       ful, please let us know.
864
865       The Geometry Center is supported by grant DMS‐8920161 from the National
866       Science Foundation, by grant DOE/DE‐FG02‐92ER25137 from the  Department
867       of Energy, by the University of Minnesota, and by Minnesota Technology,
868       Inc.
869
870       Qhull is available from http://www.qhull.org
871
872
873
874Geometry Center                   2003/12/30                          qhull(1)
Impressum