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 - 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 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 'Ft' to triangulate via the centrums of non‐simplicial 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 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 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 '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 FI Print facet identifiers.
384 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 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 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 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 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 Fo Print outer planes for each facet in the same format as 'n'.
411 The outer plane is above all points.
412 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 FO List all options to stderr, including the default values. Addi‐
425 tional 'FO's are printed to stdout.
426 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 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 FQ Print command used for qhull and input.
436 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 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 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 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 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 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 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 FV Print average vertex. The average vertex is a feasible point
481 for halfspace intersection.
482 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 Geomview options
492 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 Ga Display all input points as dots.
503 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 GDn Drop dimension n in 3‐d or 4‐d. The result is a 2‐d or 3‐d
510 object.
511 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 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 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 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 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 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 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 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 Print options
556 PAn Only the n largest facets are marked good for printing. Unless
558 'PG' is set, 'Pg' is automatically set.
559 Pdk:n Drop facet from output if normal[k] <= n. The option 'Pdk' uses
561 the default value of 0 for n.
562 PDk:n Drop facet from output if normal[k] >= n. The option 'PDk' uses
564 the default value of 0 for n.
565 PFn Only facets with area at least 'n' are marked good for printing.
567 Unless 'PG' is set, 'Pg' is automatically set.
568 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 PG Print neighbors of good facets.
575 PMn Only the n facets with the most merges are marked good for
577 printing. Unless 'PG' is set, 'Pg' is automatically set.
578 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 Pp Do not report precision problems.
588 Qhull control options
590 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 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 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 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 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 Qc Keep coplanar points with the nearest facet. Output formats
617 'p', 'f', 'Gp', 'Fc', 'FN', and 'FP' will print the points.
618 Qf Partition points to the furthest outside facet.
620 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 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 Qi Keep interior points with the nearest facet. Output formats
634 'p', 'f', 'Gp', 'FN', 'FP', and 'Fc' will print the points.
635 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 Qm Only process points that would otherwise increase max_outside.
646 Other points are treated as coplanar or interior points.
647 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 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 Qs Search all points for the initial simplex.
659 Qt Triangulated output. Triangulate all non‐simplicial facets.
661 ´Qt' is deprecated for Voronoi diagrams. See also 'Qt'.
662 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 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 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 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 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 Qhull experiments and speedups
689 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 Q1 With 'Q1', Qhull sorts merges by type (coplanar, angle coplanar,
696 concave) instead of by angle.
697 Q2 With 'Q2', Qhull merges all facets at once instead of using
699 independent sets of merges and then retesting.
700 Q3 With 'Q3', Qhull does not remove redundant vertices.
702 Q4 With 'Q4', Qhull avoids merges of an old facet into a new facet.
704 Q5 With 'Q5', Qhull does not correct outer planes at the end. The
706 maximum outer plane is used instead.
707 Q6 With 'Q6', Qhull does not pre‐merge concave or coplanar facets.
709 Q7 With 'Q7', Qhull processes facets in depth‐first order instead
711 of breadth‐first order.
712 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 Q9 With 'Q9', Qhull processes the furthest of all outside sets at
718 each iteration.
719 Q10 With 'Q10', Qhull does not use special processing for narrow
721 distributions.
722 Q11 With 'Q11', Qhull copies normals and recompute centrums for tri‐
724 coplanar facets.
725 Q12 With 'Q12', Qhull does not report a very wide merge due to a
727 duplicated ridge with nearly coincident vertices
728 Trace options
730 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 Ta Annotate output with codes that identify the corresponding
738 qh_fprintf() statement.
739 Tc Check frequently during execution. This will catch most incon‐
741 sistency errors.
742 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 TFn Report progress whenever more than n facets are created During
748 post‐merging, 'TFn' reports progress after more than n/2 merges.
749 TI file
751 Input data from 'file'. The filename may not include spaces or
752 quotes.
753 TO file
755 Output results to 'file'. The name may be enclosed in single
756 quotes.
757 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 TRn Rerun qhull n times. Usually used with 'QJn' to determine the
763 probability that a given joggle will fail.
764 Ts Collect statistics and print to stderr at the end of execution.
766 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 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 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 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 TMn Turn on tracing at n'th merge.
788 TWn Trace merge facets when the width is greater than n.
790 Tz Redirect stderr to stdout.
792
794 Please report bugs to Brad Barber at qhull_bug@qhull.org.
795 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 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 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 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
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 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
832 rbox(1)
833 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 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 Preparata, F. and M. Shamos, Computational Geometry, Springer‐Verlag,
845 New York, 1985.
846
849 C. Bradford Barber Hannu Huhdanpaa
850 bradb@shore.net hannu@qhull.org
851 .fi
853
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 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 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 Qhull is available from http://www.qhull.org
871Geometry Center 2003/12/30 qhull(1)