1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
|
qhull(1) qhull(1)
NAME
qhull - convex hull, Delaunay triangulation, Voronoi dia-
gram, halfspace intersection about a point, hull volume, facet area
SYNOPSIS
qhull- compute convex hulls and related structures
input (stdin): dimension, #points, point coordinates
first comment (non-numeric) is listed in the summary
halfspace: use dim plus one with offsets after coefficients
options (qh-quick.htm):
d - Delaunay triangulation by lifting points to a paraboloid
v - Voronoi diagram via the Delaunay triangulation
H1,1 - Halfspace intersection about [1,1,0,...]
d Qu - Furthest-site Delaunay triangulation (upper convex hull)
v Qu - Furthest-site Voronoi diagram
QJ - Joggle the input to avoid precision problems
. - concise list of all options
- - one-line description of all options
Output options (subset):
FA - compute total area and volume
Fx - extreme points (convex hull vertices)
G - Geomview output (2-d, 3-d and 4-d)
Fp - halfspace intersection coordinates
m - Mathematica output (2-d and 3-d)
n - normals with offsets
o - OFF file format (if Voronoi, outputs regions)
TO file- output results to file, may be enclosed in single quotes
f - print all fields of all facets
s - summary of results (default)
Tv - verify result: structure, convexity, and point inclusion
p - vertex coordinates
i - vertices incident to each facet
example:
rbox 1000 s | qhull Tv s FA
- html manual: index.htm
- installation: README.txt
- see also: COPYING.txt, REGISTER.txt, Changes.txt
- WWW: <http://www.qhull.org>
- GIT: <git@github.com:qhull/qhull.git>
- mirror: <http://www6.uniovi.es/ftp/pub/mirrors/geom.umn.edu/software/ghindex.html>
- news: <http://www.qhull.org/news>
- Geomview: <http://www.geomview.org>
- news group: <news:comp.graphics.algorithms>
- FAQ: <http://www.faqs.org/faqs/graphics/algorithms-faq/>
- email: qhull@qhull.org
- bug reports: qhull_bug@qhull.org
Geometry Center 2003/12/30 1
qhull(1) qhull(1)
The sections are:
- INTRODUCTION
- DESCRIPTION, a description of Qhull
- IMPRECISION, how Qhull handles imprecision
- OPTIONS
- Input and output options
- Additional input/output formats
- Precision options
- Geomview options
- Print options
- Qhull options
- Trace options
- BUGS
- E-MAIL
- SEE ALSO
- AUTHORS
- ACKNOWLEGEMENTS
This man page briefly describes all Qhull options. Please
report any mismatches with Qhull's html manual (qh-
man.htm).
INTRODUCTION
Qhull is a general dimension code for computing convex
hulls, Delaunay triangulations, Voronoi diagram, furthest-
site Voronoi diagram, furthest-site Delaunay triangula-
tions, and halfspace intersections about a point. It
implements the Quickhull algorithm for computing the con-
vex hull. Qhull handles round-off errors from floating
point arithmetic. It can approximate a convex hull.
The program includes options for hull volume, facet area,
partial hulls, input transformations, randomization, trac-
ing, multiple output formats, and execution statistics.
The program can be called from within your application.
You can view the results in 2-d, 3-d and 4-d with
Geomview.
DESCRIPTION
The format of input is the following: first line contains
the dimension, second line contains the number of input
points, and point coordinates follow. The dimension and
number of points can be reversed. Comments and line
breaks are ignored. A comment starts with a non-numeric
character and continues to the end of line. The first
comment is reported in summaries and statistics. Error
reporting is better if there is one point per line.
The default printout option is a short summary. There are
many other output formats.
Geometry Center 2003/12/30 2
qhull(1) qhull(1)
Qhull implements the Quickhull algorithm for convex hull.
This algorithm combines the 2-d Quickhull algorithm with
the n-d beneath-beyond algorithm [c.f., Preparata & Shamos
'85]. It is similar to the randomized algorithms of
Clarkson and others [Clarkson et al. '93]. The main
advantages of Quickhull are output sensitive performance,
reduced space requirements, and automatic handling of pre-
cision problems.
The data structure produced by Qhull consists of vertices,
ridges, and facets. A vertex is a point of the input set.
A ridge is a set of d vertices and two neighboring facets.
For example in 3-d, a ridge is an edge of the polyhedron.
A facet is a set of ridges, a set of neighboring facets, a
set of incident vertices, and a hyperplane equation. For
simplicial facets, the ridges are defined by the vertices
and neighboring facets. When Qhull merges two facets, it
produces a non-simplicial facet. A non-simplicial facet
has more than d neighbors and may share more than one
ridge with a neighbor.
IMPRECISION
Since Qhull uses floating point arithmetic, roundoff error
may occur for each calculation. This causes problems for
most geometric algorithms.
Qhull automatically sets option 'C-0' in 2-d, 3-d, and
4-d, or option 'Qx' in 5-d and higher. These options han-
dle precision problems by merging facets. Alternatively,
use option 'QJ' to joggle the input.
With 'C-0', Qhull merges non-convex facets while con-
structing the hull. The remaining facets are clearly con-
vex. With 'Qx', Qhull merges coplanar horizon facets,
flipped facets, concave facets and duplicated ridges. It
merges coplanar facets after constructing the hull. With
'Qx', coplanar points may be missed, but it appears to be
unlikely.
To guarantee triangular output, joggle the input with
option 'QJ'. Facet merging will not occur.
OPTIONS
To get a list of the most important options, execute
'qhull' by itself. To get a complete list of options,
execute 'qhull -'. To get a complete, concise list of
options, execute 'qhull .'.
Options can be in any order. Capitalized options take an
argument (except 'PG' and 'F' options). Single letters
are used for output formats and precision constants. The
other options are grouped into menus for other output for-
mats ('F'), Geomview output ('G'), printing ('P'), Qhull
Geometry Center 2003/12/30 3
qhull(1) qhull(1)
control ('Q'), and tracing ('T').
Main options:
default
Compute the convex hull of the input points.
Report a summary of the result.
d Compute the Delaunay triangulation by lifting the
input points to a paraboloid. The 'o' option
prints the input points and facets. The 'QJ'
option guarantees triangular output. The 'Ft'
option prints a triangulation. It adds points (the
centrums) to non-simplicial facets.
v Compute the Voronoi diagram from the Delaunay tri-
angulation. The 'p' option prints the Voronoi ver-
tices. The 'o' option prints the Voronoi vertices
and the vertices in each Voronoi region. It lists
regions in site id order. The 'Fv' option prints
each ridge of the Voronoi diagram. The first or
zero'th vertex indicates the infinity vertex. Its
coordinates are qh_INFINITE (-10.101). It indi-
cates unbounded Voronoi regions or degenerate
Delaunay triangles.
Hn,n,...
Compute halfspace intersection about [n,n,0,...].
The input is a set of halfspaces defined in the
same format as 'n', 'Fo', and 'Fi'. Use 'Fp' to
print the intersection points. Use 'Fv' to list
the intersection points for each halfspace. The
other output formats display the dual convex hull.
The point [n,n,n,...] is a feasible point for the
halfspaces, i.e., a point that is inside all of the
halfspaces (Hx+b <= 0). The default coordinate
value is 0.
The input may start with a feasible point. If so,
use 'H' by itself. The input starts with a feasi-
ble point when the first number is the dimension,
the second number is "1", and the coordinates com-
plete a line. The 'FV' option produces a feasible
point for a convex hull.
d Qu Compute the furthest-site Delaunay triangulation
from the upper convex hull. The 'o' option prints
the input points and facets. The 'QJ' option guar-
antees triangular otuput. You can also use facets.
v Qu Compute the furthest-site Voronoi diagram. The 'p'
option prints the Voronoi vertices. The 'o' option
prints the Voronoi vertices and the vertices in
Geometry Center 2003/12/30 4
qhull(1) qhull(1)
each Voronoi region. The 'Fv' option prints each
ridge of the Voronoi diagram. The first or zero'th
vertex indicates the infinity vertex at infinity.
Its coordinates are qh_INFINITE (-10.101). It
indicates unbounded Voronoi regions and degenerate
Delaunay triangles.
Qt Triangulated output.
Input/Output options:
f Print out all facets and all fields of each facet.
G Output the hull in Geomview format. For imprecise
hulls, Geomview displays the inner and outer hull.
Geomview can also display points, ridges, vertices,
coplanar points, and facet intersections. See
below for a list of options.
For Delaunay triangulations, 'G' displays the cor-
responding paraboloid. For halfspace intersection,
'G' displays the dual polytope.
i Output the incident vertices for each facet. Qhull
prints the number of facets followed by the ver-
tices of each facet. One facet is printed per
line. The numbers are the 0-relative indices of
the corresponding input points. The facets are
oriented.
In 4-d and higher, Qhull triangulates non-simpli-
cial facets. Each apex (the first vertex) is a
created point that corresponds to the facet's cen-
trum. Its index is greater than the indices of the
input points. Each base corresponds to a simpli-
cial ridge between two facets. To print the ver-
tices without triangulation, use option 'Fv'.
m Output the hull in Mathematica format. Qhull
writes a Mathematica file for 2-d and 3-d convex
hulls and for 2-d Delaunay triangulations. Qhull
produces a list of objects that you can assign to a
variable in Mathematica, for example: "list= <<
<outputfilename> ". If the object is 2-d, it can be
visualized by "Show[Graphics[list]] ". For 3-d
objects the command is "Show[Graphics3D[list]]".
n Output the normal equation for each facet. Qhull
prints the dimension (plus one), the number of
facets, and the normals for each facet. The
facet's offset follows its normal coefficients.
o Output the facets in OFF file format. Qhull prints
the dimension, number of points, number of facets,
and number of ridges. Then it prints the
Geometry Center 2003/12/30 5
qhull(1) qhull(1)
coordinates of the input points and the vertices
for each facet. Each facet is on a separate line.
The first number is the number of vertices. The
remainder are the indices of the corresponding
points. The vertices are oriented in 2-d, 3-d, and
in simplicial facets.
For 2-d Voronoi diagrams, the vertices are sorted
by adjacency, but not oriented. In 3-d and higher,
the Voronoi vertices are sorted by index. See the
'v' option for more information.
p Output the coordinates of each vertex point. Qhull
prints the dimension, the number of points, and the
coordinates for each vertex. With the 'Gc' and
'Gi' options, it also prints coplanar and interior
points. For Voronoi diagrams, it prints the coor-
dinates of each Voronoi vertex.
s Print a summary to stderr. If no output options
are specified at all, a summary goes to stdout.
The summary lists the number of input points, the
dimension, the number of vertices in the convex
hull, the number of facets in the convex hull, the
number of good facets (if 'Pg'), and statistics.
The last two statistics (if needed) measure the
maximum distance from a point or vertex to a facet.
The number in parenthesis (e.g., 2.1x) is the ratio
between the maximum distance and the worst-case
distance due to merging two simplicial facets.
Precision options
An Maximum angle given as a cosine. If the angle
between a pair of facet normals is greater than n, Qhull
merges one of the facets into a neighbor. If 'n'
is negative, Qhull tests angles after adding each
point to the hull (pre-merging). If 'n' is posi-
tive, Qhull tests angles after constructing the
hull (post-merging). Both pre- and post-merging
can be defined.
Option 'C0' or 'C-0' is set if the corresponding
'Cn' or 'C-n' is not set. If 'Qx' is set, then 'A-
n' and 'C-n' are checked after the hull is con-
structed and before 'An' and 'Cn' are checked.
Cn Centrum radius. If a centrum is less than n below
a neighboring facet, Qhull merges one of the
facets. If 'n' is negative or '-0', Qhull tests
and merges facets after adding each point to the
hull. This is called "pre-merging". If 'n' is
Geometry Center 2003/12/30 6
qhull(1) qhull(1)
positive, Qhull tests for convexity after con-
structing the hull ("post-merging"). Both pre- and
post-merging can be defined.
For 5-d and higher, 'Qx' should be used instead of
'C-n'. Otherwise, most or all facets may be merged
together.
En Maximum roundoff error for distance computations.
Rn Randomly perturb distance computations up to +/- n
* max_coord. This option perturbs every distance,
hyperplane, and angle computation. To use time as
the random number seed, use option 'QR-1'.
Vn Minimum distance for a facet to be visible. A
facet is visible if the distance from the point to
the facet is greater than 'Vn'.
Without merging, the default value for 'Vn' is the
round-off error ('En'). With merging, the default
value is the pre-merge centrum ('C-n') in 2-d or
3--d, or three times that in other dimensions. If
the outside width is specified ('Wn'), the maximum,
default value for 'Vn' is 'Wn'.
Un Maximum distance below a facet for a point to be
coplanar to the facet. The default value is 'Vn'.
Wn Minimum outside width of the hull. Points are
added to the convex hull only if they are clearly
outside of a facet. A point is outside of a facet
if its distance to the facet is greater than 'Wn'.
The normal value for 'Wn' is 'En'. If the user
specifies pre-merging and does not set 'Wn', than
'Wn' is set to the premerge 'Cn' and maxco-
ord*(1-An).
Additional input/output formats
Fa Print area for each facet. For Delaunay triangula-
tions, the area is the area of the triangle. For
Voronoi diagrams, the area is the area of the dual
facet. Use 'PAn' for printing the n largest
facets, and option 'PFn' for printing facets larger
than 'n'.
The area for non-simplicial facets is the sum of
the areas for each ridge to the centrum. Vertices
far below the facet's hyperplane are ignored. The
reported area may be significantly less than the
actual area.
Geometry Center 2003/12/30 7
qhull(1) qhull(1)
FA Compute the total area and volume for option 's'.
It is an approximation for non-simplicial facets
(see 'Fa').
Fc Print coplanar points for each facet. The output
starts with the number of facets. Then each facet
is printed one per line. Each line is the number
of coplanar points followed by the point ids.
Option 'Qi' includes the interior points. Each
coplanar point (interior point) is assigned to the
facet it is furthest above (resp., least below).
FC Print centrums for each facet. The output starts
with the dimension followed by the number of
facets. Then each facet centrum is printed, one
per line.
Fd Read input in cdd format with homogeneous points.
The input starts with comments. The first comment
is reported in the summary. Data starts after a
"begin" line. The next line is the number of
points followed by the dimension+1 and "real" or
"integer". Then the points are listed with a
leading "1" or "1.0". The data ends with an "end"
line.
For halfspaces ('Fd Hn,n,...'), the input format is
the same. Each halfspace starts with its offset.
The sign of the offset is the opposite of Qhull's
convention.
FD Print normals ('n', 'Fo', 'Fi') or points ('p') in
cdd format. The first line is the command line
that invoked Qhull. Data starts with a "begin"
line. The next line is the number of normals or
points followed by the dimension+1 and "real".
Then the normals or points are listed with the
offset before the coefficients. The offset for
points is 1.0. The offset for normals has the
opposite sign. The data ends with an "end" line.
FF Print facets (as in 'f') without printing the
ridges.
Fi Print inner planes for each facet. The inner plane
is below all vertices.
Fi Print separating hyperplanes for bounded, inner
regions of the Voronoi diagram. The first line is
the number of ridges. Then each hyperplane is
printed, one per line. A line starts with the num-
ber of indices and floats. The first pair lists
adjacent input sites, the next d floats are the
normalized coefficients for the hyperplane, and the
Geometry Center 2003/12/30 8
qhull(1) qhull(1)
last float is the offset. The hyperplane is ori-
ented toward verify that the hyperplanes are per-
pendicular bisectors. Use 'Fo' for unbounded
regions, and 'Fv' for the corresponding Voronoi
vertices.
FI Print facet identifiers.
Fm Print number of merges for each facet. At most 511
merges are reported for a facet. See 'PMn' for
printing the facets with the most merges.
FM Output the hull in Maple format. See 'm'
Fn Print neighbors for each facet. The output starts
with the number of facets. Then each facet is
printed one per line. Each line is the number of
neighbors followed by an index for each neighbor.
The indices match the other facet output formats.
A negative index indicates an unprinted facet due
to printing only good facets ('Pg'). It is the
negation of the facet's id (option 'FI'). For
example, negative indices are used for facets "at
infinity" in the Delaunay triangulation.
FN Print vertex neighbors or coplanar facet for each
point. The first line is the number of points.
Then each point is printed, one per line. If the
point is coplanar, the line is "1" followed by the
facet's id. If the point is not a selected vertex,
the line is "0". Otherwise, each line is the num-
ber of neighbors followed by the corresponding
facet indices (see 'Fn').
Fo Print outer planes for each facet in the same for-
mat as 'n'. The outer plane is above all points.
Fo Print separating hyperplanes for unbounded, outer
regions of the Voronoi diagram. The first line is
the number of ridges. Then each hyperplane is
printed, one per line. A line starts with the num-
ber of indices and floats. The first pair lists
adjacent input sites, the next d floats are the
normalized coefficients for the hyperplane, and the
last float is the offset. The hyperplane is ori-
ented toward verify that the hyperplanes are per-
pendicular bisectors. Use 'Fi' for bounded
regions, and 'Fv' for the corresponding Voronoi
vertices.
FO List all options to stderr, including the default
values. Additional 'FO's are printed to stdout.
Fp Print points for halfspace intersections (option
'Hn,n,...'). Each intersection corresponds to a
Geometry Center 2003/12/30 9
qhull(1) qhull(1)
facet of the dual polytope. The "infinity" point
[-10.101,-10.101,...] indicates an unbounded
intersection.
FP For each coplanar point ('Qc') print the point id
of the nearest vertex, the point id, the facet id,
and the distance.
FQ Print command used for qhull and input.
Fs Print a summary. The first line consists of the
number of integers ("7"), followed by the dimen-
sion, the number of points, the number of vertices,
the number of facets, the number of vertices
selected for output, the number of facets selected
for output, the number of coplanar points selected
for output.
The second line consists of the number of reals
("2"), followed by the maxmimum offset to an outer
plane and and minimum offset to an inner plane.
Roundoff is included. Later versions of Qhull may
produce additional integers or reals.
FS Print the size of the hull. The first line con-
sists of the number of integers ("0"). The second
line consists of the number of reals ("2"), fol-
lowed by the total facet area, and the total vol-
ume. Later versions of Qhull may produce addi-
tional integers or reals.
The total volume measures the volume of the inter-
section of the halfspaces defined by each facet.
Both area and volume are approximations for non-
simplicial facets. See option 'Fa'.
Ft Print a triangulation with added points for non-
simplicial facets. The first line is the dimension
and the second line is the number of points and the
number of facets. The points follow, one per line,
then the facets follow as a list of point indices.
With option points include the point-at-infinity.
Fv Print vertices for each facet. The first line is
the number of facets. Then each facet is printed,
one per line. Each line is the number of vertices
followed by the corresponding point ids. Vertices
are listed in the order they were added to the hull
(the last one is first).
Fv Print all ridges of a Voronoi diagram. The first
line is the number of ridges. Then each ridge is
printed, one per line. A line starts with the num-
ber of indices. The first pair lists adjacent
Geometry Center 2003/12/30 10
qhull(1) qhull(1)
input sites, the remaining indices list Voronoi
vertices. Vertex '0' indicates the vertex-at-
infinity (i.e., an unbounded ray). In 3-d, the
vertices are listed in order. See 'Fi' and 'Fo'
for separating hyperplanes.
FV Print average vertex. The average vertex is a fea-
sible point for halfspace intersection.
Fx List extreme points (vertices) of the convex hull.
The first line is the number of points. The other
lines give the indices of the corresponding points.
The first point is '0'. In 2-d, the points occur
in counter-clockwise order; otherwise they occur in
input order. For Delaunay triangulations, 'Fx'
lists the extreme points of the input sites. The
points are unordered.
Geomview options
G Produce a file for viewing with Geomview. Without
other options, Qhull displays edges in 2-d, outer
planes in 3-d, and ridges in 4-d. A ridge can be
explicit or implicit. An explicit ridge is a dim-1
dimensional simplex between two facets. In 4-d,
the explicit ridges are triangles. When displaying
a ridge in 4-d, Qhull projects the ridge's vertices
to one of its facets' hyperplanes. Use 'Gh' to
project ridges to the intersection of both hyper-
planes.
Ga Display all input points as dots.
Gc Display the centrum for each facet in 3-d. The
centrum is defined by a green radius sitting on a
blue plane. The plane corresponds to the facet's
hyperplane. The radius is defined by 'C-n' or
'Cn'.
GDn Drop dimension n in 3-d or 4-d. The result is a
2-d or 3-d object.
Gh Display hyperplane intersections in 3-d and 4-d.
In 3-d, the intersection is a black line. It lies
on two neighboring hyperplanes (c.f., the blue
squares associated with centrums ('Gc')). In 4-d,
the ridges are projected to the intersection of
both hyperplanes.
Gi Display inner planes in 2-d and 3-d. The inner
plane of a facet is below all of its vertices. It
is parallel to the facet's hyperplane. The inner
plane's color is the opposite (1-r,1-g,1-b) of the
Geometry Center 2003/12/30 11
qhull(1) qhull(1)
outer plane. Its edges are determined by the ver-
tices.
Gn Do not display inner or outer planes. By default,
Geomview displays the precise plane (no merging) or
both inner and output planes (merging). Under
merging, Geomview does not display the inner plane
if the the difference between inner and outer is
too small.
Go Display outer planes in 2-d and 3-d. The outer
plane of a facet is above all input points. It is
parallel to the facet's hyperplane. Its color is
determined by the facet's normal, and its edges are
determined by the vertices.
Gp Display coplanar points and vertices as radii. A
radius defines a ball which corresponds to the
imprecision of the point. The imprecision is the
maximum of the roundoff error, the centrum radius,
and maxcoord * (1-An). It is at least 1/20'th of
the maximum coordinate, and ignores post-merging if
pre-merging is done.
Gr Display ridges in 3-d. A ridge connects the two
vertices that are shared by neighboring facets.
Ridges are always displayed in 4-d.
Gt A 3-d Delaunay triangulation looks like a convex
hull with interior facets. Option 'Gt' removes the
outside ridges to reveal the outermost facets. It
automatically sets options 'Gr' and 'GDn'.
Gv Display vertices as spheres. The radius of the
sphere corresponds to the imprecision of the data.
See 'Gp' for determining the radius.
Print options
PAn Only the n largest facets are marked good for
printing. Unless 'PG' is set, 'Pg' is automati-
cally set.
Pdk:n Drop facet from output if normal[k] <= n. The
option 'Pdk' uses the default value of 0 for n.
PDk:n Drop facet from output if normal[k] >= n. The
option 'PDk' uses the default value of 0 for n.
PFn Only facets with area at least 'n' are marked good
for printing. Unless 'PG' is set, 'Pg' is automat-
ically set.
Geometry Center 2003/12/30 12
qhull(1) qhull(1)
Pg Print only good facets. A good facet is either
visible from a point (the 'QGn' option) or includes
a point (the 'QVn' option). It also meets the
requirements of 'Pdk' and 'PDk' options. Option
'Pg' is automatically set for options 'PAn' and
'PFn'.
PG Print neighbors of good facets.
PMn Only the n facets with the most merges are marked
good for printing. Unless 'PG' is set, 'Pg' is
automatically set.
Po Force output despite precision problems. Verify ('Tv') does not check
coplanar points. Flipped facets are reported and
concave facets are counted. If 'Po' is used,
points are not partitioned into flipped facets and
a flipped facet is always visible to a point.
Also, if an error occurs before the completion of
Qhull and tracing is not active, 'Po' outputs a
neighborhood of the erroneous facets (if any).
Pp Do not report precision problems.
Qhull control options
Qbk:0Bk:0
Drop dimension k from the input points. This
allows the user to take convex hulls of sub-dimen-
sional objects. It happens before the Delaunay and
Voronoi transformation.
QbB Scale the input points to fit the unit cube. After
scaling, the lower bound will be -0.5 and the upper
bound +0.5 in all dimensions. For Delaunay and
Voronoi diagrams, scaling happens after projection
to the paraboloid. Under precise arithmetic, scal-
ing does not change the topology of the convex
hull.
Qbb Scale the last coordinate to [0, m] where m is the
maximum absolute value of the other coordinates.
For Delaunay and Voronoi diagrams, scaling happens
after projection to the paraboloid. It reduces
roundoff error for inputs with integer coordinates.
Under precise arithmetic, scaling does not change
the topology of the convex hull.
Qbk:n Scale the k'th coordinate of the input points.
After scaling, the lower bound of the input points
will be n. 'Qbk' scales to -0.5.
Geometry Center 2003/12/30 13
qhull(1) qhull(1)
QBk:n Scale the k'th coordinate of the input points.
After scaling, the upper bound will be n. 'QBk'
scales to +0.5.
Qc Keep coplanar points with the nearest facet. Out-
put formats 'p', 'f', 'Gp', 'Fc', 'FN', and 'FP'
will print the points.
Qf Partition points to the furthest outside facet.
Qg Only build good facets. With the 'Qg' option,
Qhull will only build those facets that it needs to
determine the good facets in the output. See
'QGn', 'QVn', and 'PdD' for defining good facets,
and 'Pg' and 'PG' for printing good facets and
their neighbors.
QGn A facet is good (see 'Qg' and 'Pg') if it is visi-
ble from point n. If n < 0, a facet is good if it
is not visible from point n. Point n is not added
to the hull (unless 'TCn' or 'TPn'). With rbox,
use the 'Pn,m,r' option to define your point; it
will be point 0 (QG0).
Qi Keep interior points with the nearest facet. Out-
put formats 'p', 'f', 'Gp', 'FN', 'FP', and 'Fc'
will print the points.
QJn Joggle each input coordinate by adding a random
number in [-n,n]. If a precision error occurs,
then qhull increases n and tries again. It does
not increase n beyond a certain value, and it stops
after a certain number of attempts [see user.h].
Option 'QJ' selects a default value for n. The
output will be simplicial. For Delaunay triangula-
tions, 'QJn' sets 'Qbb' to scale the last coordi-
nate (not if 'Qbk:n' or 'QBk:n' is set). 'QJn' is
deprecated for Voronoi diagrams. See also 'Qt'.
Qm Only process points that would otherwise increase
max_outside. Other points are treated as coplanar
or interior points.
Qr Process random outside points instead of furthest
ones. This makes Qhull equivalent to the random-
ized incremental algorithms. CPU time is not
reported since the randomization is inefficient.
QRn Randomly rotate the input points. If n=0, use time
as the random number seed. If n>0, use n as the
random number seed. If n=-1, don't rotate but use
time as the random number seed. For Delaunay tri-
angulations ('d' and 'v'), rotate about the last
axis.
Geometry Center 2003/12/30 14
qhull(1) qhull(1)
Qs Search all points for the initial simplex.
Qt Triangulated output. Triangulate non-simplicial
facets. 'Qt' is deprecated for Voronoi diagrams.
See also 'QJn'
Qv Test vertex neighbors for convexity after post-
merging. To use the 'Qv' option, you also need to
set a merge option (e.g., 'Qx' or 'C-0').
QVn A good facet (see 'Qg' and 'Pg') includes point n.
If n<0, then a good facet does not include point n.
The point is either in the initial simplex or it is
the first point added to the hull. Option 'QVn'
may not be used with merging.
Qx Perform exact merges while building the hull. The
"exact" merges are merging a point into a coplanar
facet (defined by 'Vn', 'Un', and 'C-n'), merging
concave facets, merging duplicate ridges, and merg-
ing flipped facets. Coplanar merges and angle
coplanar merges ('A-n') are not performed. Concav-
ity testing is delayed until a merge occurs.
After the hull is built, all coplanar merges are
performed (defined by 'C-n' and 'A-n'), then post-
merges are performed (defined by 'Cn' and 'An').
Qz Add a point "at infinity" that is above the
paraboloid for Delaunay triangulations and Voronoi
diagrams. This reduces precision problems and
allows the triangulation of cospherical points.
Qhull experiments and speedups
Q0 Turn off pre-merging as a default option. With
'Q0'/'Qx' and without explicit pre-merge options,
Qhull ignores precision issues while constructing
the convex hull. This may lead to precision
errors. If so, a descriptive warning is generated.
Q1 With 'Q1', Qhull sorts merges by type (coplanar,
angle coplanar, concave) instead of by angle.
Q2 With 'Q2', Qhull merges all facets at once instead
of using independent sets of merges and then
retesting.
Q3 With 'Q3', Qhull does not remove redundant ver-
tices.
Q4 With 'Q4', Qhull avoids merges of an old facet into
a new facet.
Q5 With 'Q5', Qhull does not correct outer planes at
the end. The maximum outer plane is used instead.
Geometry Center 2003/12/30 15
qhull(1) qhull(1)
Q6 With 'Q6', Qhull does not pre-merge concave or
coplanar facets.
Q7 With 'Q7', Qhull processes facets in depth-first
order instead of breadth-first order.
Q8 With 'Q8' and merging, Qhull does not retain near-
interior points for adjusting outer planes. 'Qc'
will probably retain all points that adjust outer
planes.
Q9 With 'Q9', Qhull processes the furthest of all out-
side sets at each iteration.
Q10 With 'Q10', Qhull does not use special processing
for narrow distributions.
Q11 With 'Q11', Qhull copies normals and recomputes
centrums for tricoplanar facets.
Q12 With 'Q12', Qhull does not report a very wide merge due
to a duplicated ridge with nearly coincident vertices
Trace options
Tn Trace at level n. Qhull includes full execution
tracing. 'T-1' traces events. 'T1' traces the
overall execution of the program. 'T2' and 'T3'
trace overall execution and geometric and topologi-
cal events. 'T4' traces the algorithm. 'T5'
includes information about memory allocation and
Gaussian elimination.
Ta Annotate output with codes that identify the
corresponding qh_fprintf() statement.
Tc Check frequently during execution. This will catch
most inconsistency errors.
TCn Stop Qhull after building the cone of new facets
for point n. The output for 'f' includes the cone
and the old hull. See also 'TVn'.
TFn Report progress whenever more than n facets are
created During post-merging, 'TFn' reports progress
after more than n/2 merges.
TI file
Input data from 'file'. The filename may not include
spaces or quotes.
TO file
Output results to 'file'. The name may be enclosed
in single quotes.
TPn Turn on tracing when point n is added to the hull.
Trace partitions of point n. If used with TWn, turn off
tracing after adding point n to the hull.
TRn Rerun qhull n times. Usually used with 'QJn' to
determine the probability that a given joggle will
fail.
Ts Collect statistics and print to stderr at the end
of execution.
Tv Verify the convex hull. This checks the topologi-
cal structure, facet convexity, and point inclu-
sion. If precision problems occurred, facet con-
vexity is tested whether or not 'Tv' is selected.
Option 'Tv' does not check point inclusion if
Geometry Center 2003/12/30 16
qhull(1) qhull(1)
forcing output with 'Po', or if 'Q5' is set.
For point inclusion testing, Qhull verifies that
all points are below all outer planes (facet->max-
outside). Point inclusion is exhaustive if merging
or if the facet-point product is small enough; oth-
erwise Qhull verifies each point with a directed
search (qh_findbest).
Point inclusion testing occurs after producing out-
put. It prints a message to stderr unless option
'Pp' is used. This allows the user to interrupt
Qhull without changing the output.
TVn Stop Qhull after adding point n. If n < 0, stop
Qhull before adding point n. Output shows the hull
at this time. See also 'TCn'
TMn Turn on tracing at n'th merge.
TWn Trace merge facets when the width is greater than
n.
Tz Redirect stderr to stdout.
BUGS
Please report bugs to Brad Barber at
qhull_bug@qhull.org.
If Qhull does not compile, it is due to an incompatibility
between your system and ours. The first thing to check is
that your compiler is ANSI standard. If it is, check the
man page for the best options, or find someone to help
you. If you locate the cause of your problem, please send
email since it might help others.
If Qhull compiles but crashes on the test case (rbox D4),
there's still incompatibility between your system and
ours. Typically it's been due to mem.c and memory align-
ment. You can use qh_NOmem in mem.h to turn off memory
management. Please let us know if you figure out how to
fix these problems.
If you do find a problem, try to simplify it before
reporting the error. Try different size inputs to locate
the smallest one that causes an error. You're welcome to
hunt through the code using the execution trace as a
guide. This is especially true if you're incorporating
Qhull into your own program.
When you do report an error, please attach a data set to
the end of your message. This allows us to see the error
for ourselves. Qhull is maintained part-time.
Geometry Center 2003/12/30 17
qhull(1) qhull(1)
E-MAIL
Please send correspondence to qhull@qhull.org and
report bugs to qhull_bug@qhull.org. Let us know how
you use Qhull. If you mention it in a paper, please send
the reference and an abstract.
If you would like to get Qhull announcements (e.g., a new
version) and news (any bugs that get fixed, etc.), let us
know and we will add you to our mailing list. If you
would like to communicate with other Qhull users, we will
add you to the qhull_users alias. For Internet news about
geometric algorithms and convex hulls, look at comp.graph-
ics.algorithms and sci.math.num-analysis
SEE ALSO
rbox(1)
Barber, C. B., D.P. Dobkin, and H.T. Huhdanpaa, "The
Quickhull Algorithm for Convex Hulls," ACM Trans. on Math-
ematical Software, 22(4):469-483, Dec. 1996.
http://portal.acm.org/citation.cfm?doid=235815.235821
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.405
Clarkson, K.L., K. Mehlhorn, and R. Seidel, "Four results
on randomized incremental construction," Computational
Geometry: Theory and Applications, vol. 3, p. 185-211,
1993.
Preparata, F. and M. Shamos, Computational Geometry,
Springer-Verlag, New York, 1985.
AUTHORS
C. Bradford Barber Hannu Huhdanpaa
bradb@shore.net hannu@qhull.org
ACKNOWLEDGEMENTS
A special thanks to Albert Marden, Victor Milenkovic, the
Geometry Center, Harvard University, and Endocardial Solu-
tions, Inc. for supporting this work.
Qhull 1.0 and 2.0 were developed under National Science Foundation
grants NSF/DMS-8920161 and NSF-CCR-91-15793 750-7504. David Dobkin
Geometry Center 2003/12/30 18
qhull(1) qhull(1)
guided the original work at Princeton University. If you find it
useful, please let us know.
The Geometry Center was supported by grant DMS-8920161 from the National
Science Foundation, by grant DOE/DE-FG02-92ER25137 from the Department
of Energy, by the University of Minnesota, and by Minnesota Technology, Inc.
Qhull is available from http://www.qhull.org
Geometry Center 2003/12/30 19
|