1qhull(1) General Commands Manual qhull(1)
2
6 qhull - convex hull, Delaunay triangulation, Voronoi diagram, halfspace
7 intersection about a point, hull volume, facet area
8
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 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 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 example:
42 rbox 1000 s | qhull Tv s FA
43 - html manual: index.htm
45 - installation: README.txt
46 - see also: COPYING.txt, REGISTER.txt, Changes.txt
47 - WWW: <http://www.qhull.org>
48 - CVS: <http://savannah.nongnu.org/projects/qhull/>
49 - mirror: <http://www6.uniovi.es/ftp/pub/mirrors/geom.umn.edu/soft‐
50 ware/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://exaflop.org/docs/cgafaq/cga6.html>
55 - email: qhull@qhull.org
56 - bug reports: qhull_bug@qhull.org
57 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 This man page briefly describes all Qhull options. Please report any
77 mismatches with Qhull's html manual (index.htm).
78
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 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
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 The default printout option is a short summary. There are many other
104 output formats.
105 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 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
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 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 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 To guarantee triangular output, joggle the input with option 'QJ'.
139 Facet merging will not occur.
140
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 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 Main options:
153 default
155 Compute the convex hull of the input points. Report a summary
156 of the result.
157 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 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 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 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 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 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 facets.
194 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 Input/Output options:
204 f Print out all facets and all fields of each facet.
206 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 For Delaunay triangulations, 'G' displays the corresponding pa‐
213 raboloid. For halfspace intersection, 'G' displays the dual
214 polytope.
215 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 In 4-d 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 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 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 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 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 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 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 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 Precision options
271 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 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 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 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 En Maximum roundoff error for distance computations.
295 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 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 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 Un Maximum distance below a facet for a point to be coplanar to the
312 facet. The default value is 'Vn'.
313 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 Additional input/output formats
322 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 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 FA Compute the total area and volume for option 's'. It is an
335 approximation for non-simplicial facets (see 'Fa').
336 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 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 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 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 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 FF Print facets (as in 'f') without printing the ridges.
368 Fi Print inner planes for each facet. The inner plane is below all
370 vertices.
371 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 verify that the hyperplanes are
379 perpendicular bisectors. Use 'Fo' for unbounded regions, and
380 'Fv' for the corresponding Voronoi vertices.
381 FI Print facet identifiers.
383 Fm Print number of merges for each facet. At most 511 merges are
385 reported for a facet. See 'PMn' for printing the facets with
386 the most merges.
387 FM Output the hull in Maple format. Qhull writes a Maple file for
389 2-d and 3-d convex hulls and for 2-d Delaunay triangulations.
390 Qhull produces a '.mpl' file for displaying with display3d().
391 Fn Print neighbors for each facet. The output starts with the num‐
393 ber of facets. Then each facet is printed one per line. Each
394 line is the number of neighbors followed by an index for each
395 neighbor. The indices match the other facet output formats.
396 A negative index indicates an unprinted facet due to printing
398 only good facets ('Pg'). It is the negation of the facet's ID
399 (option 'FI'). For example, negative indices are used for
400 facets "at infinity" in the Delaunay triangulation.
401 FN Print vertex neighbors or coplanar facet for each point. The
403 first line is the number of points. Then each point is printed,
404 one per line. If the point is coplanar, the line is "1" fol‐
405 lowed by the facet's ID. If the point is not a selected vertex,
406 the line is "0". Otherwise, each line is the number of neigh‐
407 bors followed by the corresponding facet indices (see 'Fn').
408 Fo Print outer planes for each facet in the same format as 'n'.
410 The outer plane is above all points.
411 Fo Print separating hyperplanes for unbounded, outer regions of the
413 Voronoi diagram. The first line is the number of ridges. Then
414 each hyperplane is printed, one per line. A line starts with
415 the number of indices and floats. The first pair lists adjacent
416 input sites, the next d floats are the normalized coefficients
417 for the hyperplane, and the last float is the offset. The
418 hyperplane is oriented toward verify that the hyperplanes are
419 perpendicular bisectors. Use 'Fi' for bounded regions, and 'Fv'
420 for the corresponding Voronoi vertices.
421 FO List all options to stderr, including the default values. Addi‐
423 tional 'FO's are printed to stdout.
424 Fp Print points for halfspace intersections (option 'Hn,n,...').
426 Each intersection corresponds to a facet of the dual polytope.
427 The "infinity" point [-10.101,-10.101,...] indicates an
428 unbounded intersection.
429 FP For each coplanar point ('Qc') print the point ID of the nearest
431 vertex, the point ID, the facet ID, and the distance.
432 FQ Print command used for qhull and input.
434 Fs Print a summary. The first line consists of the number of inte‐
436 gers ("8"), followed by the dimension, the number of points, the
437 number of vertices, the number of facets, the number of vertices
438 selected for output, the number of facets selected for output,
439 the number of coplanar points selected for output, number of
440 simplicial, unmerged facets in output
441 The second line consists of the number of reals ("2"), followed
443 by the maxmimum offset to an outer plane and and minimum offset
444 to an inner plane. Roundoff is included. Later versions of
445 Qhull may produce additional integers or reals.
446 FS Print the size of the hull. The first line consists of the num‐
448 ber of integers ("0"). The second line consists of the number
449 of reals ("2"), followed by the total facet area, and the total
450 volume. Later versions of Qhull may produce additional integers
451 or reals.
452 The total volume measures the volume of the intersection of the
454 halfspaces defined by each facet. Both area and volume are
455 approximations for non-simplicial facets. See option 'Fa'.
456 Ft Print a triangulation with added points for non-simplicial
458 facets. The first line is the dimension and the second line is
459 the number of points and the number of facets. The points fol‐
460 low, one per line, then the facets follow as a list of point
461 indices. With option points include the point-at-infinity.
462 Fv Print vertices for each facet. The first line is the number of
464 facets. Then each facet is printed, one per line. Each line is
465 the number of vertices followed by the corresponding point ids.
466 Vertices are listed in the order they were added to the hull
467 (the last one is first).
468 Fv Print all ridges of a Voronoi diagram. The first line is the
470 number of ridges. Then each ridge is printed, one per line. A
471 line starts with the number of indices. The first pair lists
472 adjacent input sites, the remaining indices list Voronoi ver‐
473 tices. Vertex '0' indicates the vertex-at-infinity (i.e., an
474 unbounded ray). In 3-d, the vertices are listed in order. See
475 'Fi' and 'Fo' for separating hyperplanes.
476 FV Print average vertex. The average vertex is a feasible point
478 for halfspace intersection.
479 Fx List extreme points (vertices) of the convex hull. The first
481 line is the number of points. The other lines give the indices
482 of the corresponding points. The first point is '0'. In 2-d,
483 the points occur in counter-clockwise order; otherwise they
484 occur in input order. For Delaunay triangulations, 'Fx' lists
485 the extreme points of the input sites. The points are
486 unordered.
487 Geomview options
489 G Produce a file for viewing with Geomview. Without other
491 options, Qhull displays edges in 2-d, outer planes in 3-d, and
492 ridges in 4-d. A ridge can be explicit or implicit. An
493 explicit ridge is a dim-1 dimensional simplex between two
494 facets. In 4-d, the explicit ridges are triangles. When dis‐
495 playing a ridge in 4-d, Qhull projects the ridge's vertices to
496 one of its facets' hyperplanes. Use 'Gh' to project ridges to
497 the intersection of both hyperplanes.
498 Ga Display all input points as dots.
500 Gc Display the centrum for each facet in 3-d. The centrum is
502 defined by a green radius sitting on a blue plane. The plane
503 corresponds to the facet's hyperplane. The radius is defined by
504 'C-n' or 'Cn'.
505 GDn Drop dimension n in 3-d or 4-d. The result is a 2-d or 3-d
507 object.
508 Gh Display hyperplane intersections in 3-d and 4-d. In 3-d, the
510 intersection is a black line. It lies on two neighboring hyper‐
511 planes (c.f., the blue squares associated with centrums ('Gc')).
512 In 4-d, the ridges are projected to the intersection of both
513 hyperplanes.
514 Gi Display inner planes in 2-d and 3-d. The inner plane of a facet
516 is below all of its vertices. It is parallel to the facet's
517 hyperplane. The inner plane's color is the opposite
518 (1-r,1-g,1-b) of the outer plane. Its edges are determined by
519 the vertices.
520 Gn Do not display inner or outer planes. By default, Geomview dis‐
522 plays the precise plane (no merging) or both inner and output
523 planes (merging). Under merging, Geomview does not display the
524 inner plane if the the difference between inner and outer is too
525 small.
526 Go Display outer planes in 2-d and 3-d. The outer plane of a facet
528 is above all input points. It is parallel to the facet's hyper‐
529 plane. Its color is determined by the facet's normal, and its
530 edges are determined by the vertices.
531 Gp Display coplanar points and vertices as radii. A radius defines
533 a ball which corresponds to the imprecision of the point. The
534 imprecision is the maximum of the roundoff error, the centrum
535 radius, and maxcoord * (1-An). It is at least 1/20'th of the
536 maximum coordinate, and ignores post-merging if pre-merging is
537 done.
538 Gr Display ridges in 3-d. A ridge connects the two vertices that
540 are shared by neighboring facets. Ridges are always displayed
541 in 4-d.
542 Gt A 3-d Delaunay triangulation looks like a convex hull with inte‐
544 rior facets. Option 'Gt' removes the outside ridges to reveal
545 the outermost facets. It automatically sets options 'Gr' and
546 'GDn'.
547 Gv Display vertices as spheres. The radius of the sphere corre‐
549 sponds to the imprecision of the data. See 'Gp' for determining
550 the radius.
551 Print options
553 PAn Only the n largest facets are marked good for printing. Unless
555 'PG' is set, 'Pg' is automatically set.
556 Pdk:n Drop facet from output if normal[k] <= n. The option 'Pdk' uses
558 the default value of 0 for n.
559 PDk:n Drop facet from output if normal[k] >= n. The option 'PDk' uses
561 the default value of 0 for n.
562 PFn Only facets with area at least 'n' are marked good for printing.
564 Unless 'PG' is set, 'Pg' is automatically set.
565 Pg Print only good facets. A good facet is either visible from a
567 point (the 'QGn' option) or includes a point (the 'QVn' option).
568 It also meets the requirements of 'Pdk' and 'PDk' options.
569 Option 'Pg' is automatically set for options 'PAn' and 'PFn'.
570 PG Print neighbors of good facets.
572 PMn Only the n facets with the most merges are marked good for
574 printing. Unless 'PG' is set, 'Pg' is automatically set.
575 Po Force output despite precision problems. Verify ('Tv') does not
577 check coplanar points. Flipped facets are reported and concave
578 facets are counted. If 'Po' is used, points are not partitioned
579 into flipped facets and a flipped facet is always visible to a
580 point. Also, if an error occurs before the completion of Qhull
581 and tracing is not active, 'Po' outputs a neighborhood of the
582 erroneous facets (if any).
583 Pp Do not report precision problems.
585 Qhull control options
587 Qbk:0Bk:0
589 Drop dimension k from the input points. This allows the user to
590 take convex hulls of sub-dimensional objects. It happens before
591 the Delaunay and Voronoi transformation.
592 QbB Scale the input points to fit the unit cube. After scaling, the
594 lower bound will be -0.5 and the upper bound +0.5 in all dimen‐
595 sions. For Delaunay and Voronoi diagrams, scaling happens after
596 projection to the paraboloid. Under precise arithmetic, scaling
597 does not change the topology of the convex hull.
598 Qbb Scale the last coordinate to [0, m] where m is the maximum abso‐
600 lute value of the other coordinates. For Delaunay and Voronoi
601 diagrams, scaling happens after projection to the paraboloid.
602 It reduces roundoff error for inputs with integer coordinates.
603 Under precise arithmetic, scaling does not change the topology
604 of the convex hull.
605 Qbk:n Scale the k'th coordinate of the input points. After scaling,
607 the lower bound of the input points will be n. 'Qbk' scales to
608 -0.5.
609 QBk:n Scale the k'th coordinate of the input points. After scaling,
611 the upper bound will be n. 'QBk' scales to +0.5.
612 Qc Keep coplanar points with the nearest facet. Output formats
614 'p', 'f', 'Gp', 'Fc', 'FN', and 'FP' will print the points.
615 Qf Partition points to the furthest outside facet.
617 Qg Only build good facets. With the 'Qg' option, Qhull will only
619 build those facets that it needs to determine the good facets in
620 the output. See 'QGn', 'QVn', and 'PdD' for defining good
621 facets, and 'Pg' and 'PG' for printing good facets and their
622 neighbors.
623 QGn A facet is good (see 'Qg' and 'Pg') if it is visible from point
625 n. If n < 0, a facet is good if it is not visible from point n.
626 Point n is not added to the hull (unless 'TCn' or 'TPn'). With
627 rbox, use the 'Pn,m,r' option to define your point; it will be
628 point 0 (QG0).
629 Qi Keep interior points with the nearest facet. Output formats
631 'p', 'f', 'Gp', 'FN', 'FP', and 'Fc' will print the points.
632 QJn Joggle each input coordinate by adding a random number in
634 [-n,n]. If a precision error occurs, then qhull increases n and
635 tries again. It does not increase n beyond a certain value, and
636 it stops after a certain number of attempts [see user.h].
637 Option 'QJ' selects a default value for n. The output will be
638 simplicial. For Delaunay triangulations, 'QJn' sets 'Qbb' to
639 scale the last coordinate (not if 'Qbk:n' or 'QBk:n' is set).
640 See also 'Qt'.
641 Qm Only process points that would otherwise increase max_outside.
643 Other points are treated as coplanar or interior points.
644 Qr Process random outside points instead of furthest ones. This
646 makes Qhull equivalent to the randomized incremental algorithms.
647 CPU time is not reported since the randomization is inefficient.
648 QRn Randomly rotate the input points. If n=0, use time as the ran‐
650 dom number seed. If n>0, use n as the random number seed. If
651 n=-1, don't rotate but use time as the random number seed. For
652 Delaunay triangulations ('d' and 'v'), rotate about the last
653 axis.
654 Qs Search all points for the initial simplex.
656 Qt Triangulated output. Triangulate all non-simplicial facets.
658 See also 'QJ'.
659 Qv Test vertex neighbors for convexity after post-merging. To use
661 the 'Qv' option, you also need to set a merge option (e.g., 'Qx'
662 or 'C-0').
663 QVn A good facet (see 'Qg' and 'Pg') includes point n. If n<0, then
665 a good facet does not include point n. The point is either in
666 the initial simplex or it is the first point added to the hull.
667 Option 'QVn' may not be used with merging.
668 Qx Perform exact merges while building the hull. The "exact"
670 merges are merging a point into a coplanar facet (defined by
671 'Vn', 'Un', and 'C-n'), merging concave facets, merging dupli‐
672 cate ridges, and merging flipped facets. Coplanar merges and
673 angle coplanar merges ('A-n') are not performed. Concavity
674 testing is delayed until a merge occurs.
675 After the hull is built, all coplanar merges are performed
677 (defined by 'C-n' and 'A-n'), then post-merges are performed
678 (defined by 'Cn' and 'An').
679 Qz Add a point "at infinity" that is above the paraboloid for
681 Delaunay triangulations and Voronoi diagrams. This reduces pre‐
682 cision problems and allows the triangulation of cospherical
683 points.
684 Qhull experiments and speedups
686 Q0 Turn off pre-merging as a default option. With 'Q0'/'Qx' and
688 without explicit pre-merge options, Qhull ignores precision
689 issues while constructing the convex hull. This may lead to
690 precision errors. If so, a descriptive warning is generated.
691 Q1 With 'Q1', Qhull sorts merges by type (coplanar, angle coplanar,
693 concave) instead of by angle.
694 Q2 With 'Q2', Qhull merges all facets at once instead of using
696 independent sets of merges and then retesting.
697 Q3 With 'Q3', Qhull does not remove redundant vertices.
699 Q4 With 'Q4', Qhull avoids merges of an old facet into a new facet.
701 Q5 With 'Q5', Qhull does not correct outer planes at the end. The
703 maximum outer plane is used instead.
704 Q6 With 'Q6', Qhull does not pre-merge concave or coplanar facets.
706 Q7 With 'Q7', Qhull processes facets in depth-first order instead
708 of breadth-first order.
709 Q8 With 'Q8' and merging, Qhull does not retain near-interior
711 points for adjusting outer planes. 'Qc' will probably retain
712 all points that adjust outer planes.
713 Q9 With 'Q9', Qhull processes the furthest of all outside sets at
715 each iteration.
716 Q10 With 'Q10', Qhull does not use special processing for narrow
718 distributions.
719 Q11 With 'Q11', Qhull copies normals and recompute centrums for tri‐
721 coplanar facets.
722 Trace options
724 Tn Trace at level n. Qhull includes full execution tracing. 'T-1'
726 traces events. 'T1' traces the overall execution of the pro‐
727 gram. 'T2' and 'T3' trace overall execution and geometric and
728 topological events. 'T4' traces the algorithm. 'T5' includes
729 information about memory allocation and Gaussian elimination.
730 Tc Check frequently during execution. This will catch most incon‐
732 sistency errors.
733 TCn Stop Qhull after building the cone of new facets for point n.
735 The output for 'f' includes the cone and the old hull. See also
736 'TVn'.
737 TFn Report progress whenever more than n facets are created During
739 post-merging, 'TFn' reports progress after more than n/2 merges.
740 TI file
742 Input data from 'file'. The filename may not include spaces or
743 quotes.
744 TO file
746 Output results to 'file'. The name may be enclosed in single
747 quotes.
748 TPn Turn on tracing when point n is added to the hull. Trace parti‐
750 tions of point n. If used with TWn, turn off tracing after
751 adding point n to the hull.
752 TRn Rerun qhull n times. Usually used with 'QJn' to determine the
754 probability that a given joggle will fail.
755 Ts Collect statistics and print to stderr at the end of execution.
757 Tv Verify the convex hull. This checks the topological structure,
759 facet convexity, and point inclusion. If precision problems
760 occurred, facet convexity is tested whether or not 'Tv' is
761 selected. Option 'Tv' does not check point inclusion if forcing
762 output with 'Po', or if 'Q5' is set.
763 For point inclusion testing, Qhull verifies that all points are
765 below all outer planes (facet->maxoutside). Point inclusion is
766 exhaustive if merging or if the facet-point product is small
767 enough; otherwise Qhull verifies each point with a directed
768 search (qh_findbest).
769 Point inclusion testing occurs after producing output. It
771 prints a message to stderr unless option 'Pp' is used. This
772 allows the user to interrupt Qhull without changing the output.
773 TVn Stop Qhull after adding point n. If n < 0, stop Qhull before
775 adding point n. Output shows the hull at this time. See also
776 'TCn'
777 TMn Turn on tracing at n'th merge.
779 TWn Trace merge facets when the width is greater than n.
781 Tz Redirect stderr to stdout.
783
785 Please report bugs to Brad Barber at qhull_bug@qhull.org.
786 If Qhull does not compile, it is due to an incompatibility between your
788 system and ours. The first thing to check is that your compiler is
789 ANSI standard. If it is, check the man page for the best options, or
790 find someone to help you. If you locate the cause of your problem,
791 please send email since it might help others.
792 If Qhull compiles but crashes on the test case (rbox D4), there's still
794 incompatibility between your system and ours. Typically it's been due
795 to mem.c and memory alignment. You can use qh_NOmem in mem.h to turn
796 off memory management. Please let us know if you figure out how to fix
797 these problems.
798 If you do find a problem, try to simplify it before reporting the
800 error. Try different size inputs to locate the smallest one that
801 causes an error. You're welcome to hunt through the code using the
802 execution trace as a guide. This is especially true if you're incorpo‐
803 rating Qhull into your own program.
804 When you do report an error, please attach a data set to the end of
806 your message. This allows us to see the error for ourselves. Qhull is
807 maintained part-time.
808
810 Please send correspondence to qhull@qhull.org and report bugs to
811 qhull_bug@qhull.org. Let us know how you use Qhull. If you mention it
812 in a paper, please send the reference and an abstract.
813 If you would like to get Qhull announcements (e.g., a new version) and
815 news (any bugs that get fixed, etc.), let us know and we will add you
816 to our mailing list. If you would like to communicate with other Qhull
817 users, we will add you to the qhull_users alias. For Internet news
818 about geometric algorithms and convex hulls, look at comp.graph‐
819 ics.algorithms and sci.math.num-analysis
820
823 rbox(1)
824 Barber, C. B., D.P. Dobkin, and H.T. Huhdanpaa, "The Quickhull Algo‐
826 rithm for Convex Hulls," ACM Trans. on Mathematical Software,
827 22(4):469-483, Dec. 1996. http://www.acm.org/pubs/citations/jour‐
828 nals/toms/1996-22-4/p469-barber/ http://citeseer.nj.nec.com/83502.html
829 Clarkson, K.L., K. Mehlhorn, and R. Seidel, "Four results on randomized
831 incremental construction," Computational Geometry: Theory and Applica‐
832 tions, vol. 3, p. 185-211, 1993.
833 Preparata, F. and M. Shamos, Computational Geometry, Springer-Verlag,
835 New York, 1985.
836
839 C. Bradford Barber Hannu Huhdanpaa
840 bradb@qhull.org hannu@qhull.org
841 c/o The Geometry Center
843 University of Minnesota
844 400 Lind Hall
845 207 Church Street S.E.
846 Minneapolis, MN 55455
847
851 A special thanks to Albert Marden, Victor Milenkovic, the Geometry Cen‐
852 ter, Harvard University, and Endocardial Solutions, Inc. for supporting
853 this work.
854 Qhull 1.0 and 2.0 were developed under National Science Foundation
856 grants NSF/DMS-8920161 and NSF-CCR-91-15793 750-7504. David Dobkin
857 guided the original work at Princeton University. If you find it use‐
858 ful, please let us know.
859 The Geometry Center is supported by grant DMS-8920161 from the National
861 Science Foundation, by grant DOE/DE-FG02-92ER25137 from the Department
862 of Energy, by the University of Minnesota, and by Minnesota Technology,
863 Inc.
864 Qhull is available from http://www.qhull.org
866Geometry Center 2003/12/30 qhull(1)