To: ProgramsOptionsOutputFormatsGeomviewPrintQhullPrecisionTrace
To: synopsis • input • outputs • controls • options

# qhull -- convex hull and related structures

The convex hull of a set of points is the smallest convex set containing the points. The Delaunay triangulation and furthest-site Delaunay triangulation are equivalent to a convex hull in one higher dimension. Halfspace intersection about a point is equivalent to a convex hull by polar duality.

The qhull program provides options to build these structures and to experiment with the process. Use the qconvex, qdelaunay, qhalf, and qvoronoi programs to build specific structures. You may use qhull instead. It takes the same options and uses the same code.

Example: rbox 1000 D3 | qhull C-1e-4 FO Ts
Compute the 3-d convex hull of 1000 random points. Centrums must be 10^-4 below neighboring hyperplanes. Print the options and precision constants. When done, print statistics. These options may be used with any of the Qhull programs.

Example: rbox 1000 D3 | qhull d R1e-4 Q0
Compute the 3-d Delaunay triangulation of 1000 random points. Randomly perturb all calculations by [0.9999,1.0001]. Do not correct precision problems. This leads to serious precision errors.

Use the following equivalences when calling qhull in 2-d to 4-d (a 3-d Delaunay triangulation is a 4-d convex hull):

Use the following equivalences when calling qhull in 5-d and higher (a 4-d Delaunay triangulation is a 5-d convex hull):

If you use 'Qt' (triangulated output), all furthest-site Delaunay regions will be simplicial (e.g., triangles in 2-d). Some regions may be degenerate and have zero area. Qhull can identify coincident points. With facet merging, cocircular and cospherical extreme points will lead to non-simplicial output (e.g., a square).

If you use 'QJ' (joggle), all furthest-site Delaunay regions will be simplicial (e.g., triangles in 2-d). Duplicate points will create small regions since the points are joggled apart. See Joggled input or merged facets.

The output for 4-d convex hulls may be confusing if the convex hull contains non-simplicial facets (e.g., a hypercube). See Why are there extra points in a 4-d or higher convex hull?

### »qhull synopsis

```qhull- compute convex hulls and related structures.
input (stdin): dimension, n, point coordinates
halfspace: use dim+1 and put offsets after coefficients

options (qh-quick.htm):
d    - Delaunay triangulation by lifting points to a paraboloid
d Qu - furthest-site Delaunay triangulation (upper convex hull)
v    - Voronoi diagram as the dual of the Delaunay triangulation
v Qu - furthest-site Voronoi diagram
H1,1 - Halfspace intersection about [1,1,0,...] via polar duality
Qt   - triangulated output
QJ   - joggle input instead of merging facets
Tv   - verify result: structure, convexity, and point inclusion
.    - concise list of all options
-    - one-line description of all options

Output options (subset):
s    - summary of results (default)
i    - vertices incident to each facet
n    - normals with offsets
p    - vertex coordinates (if 'Qc', includes coplanar points)
if 'v', Voronoi vertices
Fp   - halfspace intersections
Fx   - extreme points (convex hull vertices)
FA   - compute total area and volume
o    - OFF format (if 'v', outputs Voronoi regions)
G    - Geomview output (2-d, 3-d and 4-d)
m    - Mathematica output (2-d and 3-d)
QVn  - print facets that include point n, -n if not
TO file- output results to file, may be enclosed in single quotes

examples:
rbox c d D2 | qhull Qc s f Fx | more      rbox 1000 s | qhull Tv s FA
rbox 10 D2 | qhull d QJ s i TO result     rbox 10 D2 | qhull v Qt p
rbox 10 D2 | qhull d Qu QJ m              rbox 10 D2 | qhull v Qu QJ o
rbox c | qhull n                          rbox c | qhull FV n | qhull H Fp
rbox d D12 | qhull QR0 FA                 rbox c D7 | qhull FA TF1000
rbox y 1000 W0 | qhull                    rbox 10 | qhull v QJ o Fv
```

### »qhull input

The input data on stdin consists of:

• dimension
• number of points
• point coordinates

Use I/O redirection (e.g., qhull < data.txt), a pipe (e.g., rbox 10 | qhull), or the 'TI' option (e.g., qhull TI data.txt).

Comments start with a non-numeric character. Error reporting is simpler if there is one point per line. Dimension and number of points may be reversed. For halfspace intersection, an interior point may be prepended (see qhalf input).

Here is the input for computing the convex hull of the unit cube. The output is the normals, one per facet.

rbox c > data

```3 RBOX c
8
-0.5   -0.5   -0.5
-0.5   -0.5    0.5
-0.5    0.5   -0.5
-0.5    0.5    0.5
0.5   -0.5   -0.5
0.5   -0.5    0.5
0.5    0.5   -0.5
0.5    0.5    0.5
```

qhull s n < data

```
Convex hull of 8 points in 3-d:

Number of vertices: 8
Number of facets: 6
Number of non-simplicial facets: 6

Statistics for: RBOX c | QHULL s n

Number of points processed: 8
Number of hyperplanes created: 11
Number of distance tests for qhull: 35
Number of merged facets: 6
Number of distance tests for merging: 84
CPU seconds to compute hull (after input): 0.081

4
6
0      0     -1   -0.5
0     -1      0   -0.5
1      0      0   -0.5
-1      0      0   -0.5
0      1      0   -0.5
0      0      1   -0.5
```

### »qhull outputs

These options control the output of qhull. They may be used individually or together.

General
qhull d
compute the Delaunay triangulation by lifting the points to a paraboloid. See qdelaunay.
qhull v
compute the Voronoi diagram by computing the Delaunay triangulation. See qvoronoi.
qhull H
compute the halfspace intersection about a point via polar duality. See qhalf.

For a full list of output options see

### »qhull controls

For a full list of control options see

### »qhull options

```qhull- compute convex hulls and related structures.
http://www.geom.umn.edu/software/qhull

input (stdin):
first lines: dimension and number of points (or vice-versa).
other lines: point coordinates, best if one point per line
halfspaces:  use dim plus one and put offset after coefficients.
May be preceded by a single interior point ('H').

options:
d    - Delaunay triangulation by lifting points to a paraboloid
d Qu - furthest-site Delaunay triangulation (upper convex hull)
v    - Voronoi diagram (dual of the Delaunay triangulation)
v Qu - furthest-site Voronoi diagram
Hn,n,... - halfspace intersection about point [n,n,0,...]
Qt   - triangulated output
QJ   - joggle input instead of merging facets
Qc   - keep coplanar points with nearest facet
Qi   - keep interior points with nearest facet

Qhull control options:
Qbk:n   - scale coord k so that low bound is n
QBk:n - scale coord k so that upper bound is n (QBk is 0.5)
QbB  - scale input to unit cube centered at the origin
Qbb  - scale last coordinate to [0,m] for Delaunay triangulations
Qbk:0Bk:0 - remove k-th coordinate from input
QJn  - randomly joggle input in range [-n,n]
QRn  - random rotation (n=seed, n=0 time, n=-1 time/no rotate)
Qf   - partition point to furthest outside facet
Qg   - only build good facets (needs 'QGn', 'QVn', or 'PdD')
Qm   - only process points that would increase max_outside
Qr   - process random outside points instead of furthest ones
Qs   - search all points for the initial simplex
Qu   - for 'd' or 'v', compute upper hull without point at-infinity
returns furthest-site Delaunay triangulation
Qv   - test vertex neighbors for convexity
Qx   - exact pre-merges (skips coplanar and anglomaniacs facets)
Qz   - add point-at-infinity to Delaunay triangulation
QGn  - good facet if visible from point n, -n for not visible
QVn  - good facet if it includes point n, -n if not
Q0   - turn off default p remerge with 'C-0'/'Qx'
Q1	   - sort merges by type instead of angle
Q2   - merge all non-convex at once instead of independent sets
Q3   - do not merge redundant vertices
Q4   - avoid old>new merges
Q5   - do not correct outer planes at end of qhull
Q6   - do not pre-merge concave or coplanar facets
Q8   - do not process near-inside points
Q9   - process furthest of furthest points
Q10  - no special processing for narrow distributions
Q11  - copy normals and recompute centrums for tricoplanar facets

Towpaths Trace options:
T4   - trace at level n, 4=all, 5=mem/gauss, -1= events
Tc   - check frequently during execution
Ts   - print statistics
Tv   - verify result: structure, convexity, and point inclusion
Tz   - send all output to stdout
TFn  - report summary when n or more facets created
TI file - input data from file, no spaces or single quotes
TO file - output results to file, may be enclosed in single quotes
TPn  - turn on tracing when point n added to hull
TMn - turn on tracing at merge n
TWn - trace merge facets when width > n
TRn  - rerun qhull n times.  Use with 'QJn'
TVn  - stop qhull after adding point n, -n for before (see TCn)
TCn - stop qhull after building cone for point n (see TVn)

Precision options:
An  - cosine of maximum angle.  Merge facets if cosine > n or non-convex
C-0 roundoff, A-0.99/C-0.01 pre-merge, A0.99/C0.01 post-merge
En   - max roundoff error for distance computation
Rn   - randomly perturb computations by a factor of [1-n,1+n]
Vn   - min distance above plane for a visible facet (default 3C-n or En)
Un   - max distance below plane for a new, coplanar point (default Vn)
Wn   - min facet width for outside point (before roundoff, default 2Vn)

Output formats (may be combined; if none, produces a summary to stdout):
f    - facet dump
G    - Geomview output (see below)
i    - vertices incident to each facet
m    - Mathematica output (2-d and 3-d)
o    - OFF format (dim, points and facets; Voronoi regions)
n    - normals with offsets
p    - vertex coordinates or Voronoi vertices (coplanar points if 'Qc')
s    - summary (stderr)

More formats:
Fa   - area for each facet
FA   - compute total area and volume for option 's'
Fc   - count plus coplanar points for each facet
use 'Qc' (default) for coplanar and 'Qi' for interior
FC   - centrum or Voronoi center for each facet
Fd   - use cdd format for input (homogeneous with offset first)
FD   - use cdd format for numeric output (offset first)
FF   - facet dump without ridges
Fi   - inner plane for each facet
for 'v', separating hyperplanes for bounded Voronoi regions
FI   - ID of each facet
Fm   - merge count for each facet (511 max)
Fn   - count plus neighboring facets for each facet
FN   - count plus neighboring facets for each point
Fo   - outer plane (or max_outside) for each facet
for 'v', separating hyperplanes for unbounded Voronoi regions
FO   - options and precision constants
Fp   - dim, count, and intersection coordinates (halfspace only)
FP   - nearest vertex and distance for each coplanar point
FQ   - command used for qhull
Fs   - summary: #int (8), dimension, #points, tot vertices, tot facets,
output: #vertices, #facets, #coplanars, #nonsimplicial
#real (2), max outer plane, min vertex
FS   - sizes:   #int (0)
#real(2) tot area, tot volume
Ft   - triangulation with centrums for non-simplicial facets (OFF format)
Fv   - count plus vertices for each facet
for 'v', Voronoi diagram as Voronoi vertices for pairs of sites
FV   - average of vertices (a feasible point for 'H')
Fx   - extreme points (in order for 2-d)

Geomview options (2-d, 3-d, and 4-d; 2-d Voronoi)
Ga   - all points as dots
Gp  -  coplanar points and vertices as radii
Gv  -  vertices as spheres
Gi   - inner planes only
Gn  -  no planes
Go  -  outer planes only
Gc   - centrums
Gh   - hyperplane intersections
Gr   - ridges
GDn  - drop dimension n in 3-d and 4-d output
Gt   - for 3-d 'd', transparent outer ridges

Print options:
PAn  - keep n largest facets by area
Pdk:n - drop facet if normal[k] <= n (default 0.0)
PDk:n - drop facet if normal[k] >= n
Pg   - print good facets (needs 'QGn' or 'QVn')
PFn  - keep facets whose area is at least n
PG   - print neighbors of good facets
PMn  - keep n facets with most merges
Po   - force output.  If error, output neighborhood of facet
Pp   - do not report precision problems

.    - list of all options
-    - one line descriptions of all options
```

To: ProgramsOptionsOutputFormatsGeomviewPrintQhullPrecisionTrace
To: synopsis • input • outputs • controls • options