Up: Home page for Qhull
Up: Qhull manual: Table of Contents
To: Rbox manual
To: Qhull options: Table of contents (please wait while loading)
To: Qhull options: Delaunay and Voronoi
Dn: Synopsis • Main • Output • Formats • Geomview • Print • Qhull • Precision • Trace

Qhull options

These sections describe the options for Qhull. This section lists the main options. It includes the options for convex hulls and halfspace intersections.

For an example of Qhull, the following computes the convex hull of the vertices of a hypercube. It returns the facet normals.

rbox c D4 | qhull n

See Synopsis and examples and Qhull examples for more examples. Execute 'qhull' by itself for a synopsis and list of examples. To get the full list of options, execute 'qhull - | more'. To get a concise list of all options, execute 'qhull .'.

There are many options. The best way to learn an option is to try it with small examples. Use rbox to generate input sets. If you have Unix, use Geomview to view the results. Start with the following input sets:

'rbox c' generates a cube. The facets are non-simplicial.
'rbox d' generates a diamond. The facets are simplicial.
'rbox 6' generates 6 random points.

Brad Barber, Cambridge MA, January 8, 1998

»Qhull options: Table of contents

Synopsis and examples
Input
Main options
- convex hull
- halfspace intersection ('Hn,n')
- Delaunay triangulation ('d')
- Voronoi diagram ('v')
- furthest-site Delaunay triangulation ('d Qu')
- furthest-site Voronoi diagram ('v Qu')
- Joggled input or merged facets ('QJ')
Output formats
Additional input & output formats (F)
Geomview output options (G)
Print options (P)
Qhull control options (Q)
Precision options
Trace options (T)
Qhull functions, macros, and data structures

Single letters are used for output formats and precision constants. The other options are grouped into menus for formats ('F'), Geomview ('G '), printing ('P'), Qhull control ('Q '), and tracing ('T'). The menu options may be listed together (e.g., 'GrD3' for 'Gr' and 'GD3'). Options may be in any order. Capitalized options take a numeric argument (except for 'PG' and 'F' options). Use option 'FO' to print the selected options.

Qhull uses zero-relative indexing. If there are n points, the index of the first point is 0 and the index of the last point is n-1.

The default options are:

convex hull (convex)
summary output ('s')
facet merging ('C-0' in 2-d, 3-d, 4-d; 'Qx' in 5-d and up)

The Unix tcsh and ksh shells make it easy to try out different options. In Windows 95, use a DOS window with doskey and a window scroller (e.g., peruse).

» Synopsis • Main • Output • Formats • Geomview • Print • Qhull • Precision • Trace

Main options

Convex hull: conventions • outputs • controls • graphics • notes

Halfspace intersection about [n,n,0,...] ('Hn,n' or 'H'): input • conventions • outputs • controls • graphics • notes

Delaunay triangulation ('d'): conventions • outputs • controls • graphics • notes

Voronoi diagram ('v'): conventions • outputs • controls • graphics • notes

Furthest-site Delaunay triangulation ('d Qu'): conventions • outputs • controls • graphics • notes

Furthest-site Voronoi diagram ('v Qu'): conventions • outputs • controls • graphics • notes

Joggled input or merged facets

For an alphabetical list of all options, see qhull.txt. Execute 'qhull' by itself for a synopsis of the most important options. To get one line descriptions of all options, execute 'qhull -'. To get a concise list of all options, execute 'qhull .'.

»Convex hull

The convex hull of a set of points is the smallest convex set containing the points. See the detailed introduction by O'Rourke ['94]. See Description of Qhull and How Qhull adds a point.

Example: rbox 10 D3 | qhull s o TO result: Compute the 3-d convex hull of 10 random points. Write a summary to the console and the points and facets to 'result'.

Qhull always computes a convex hull.

The output for 4-d convex hulls may be confusing if the convex hull contains
non-simplicial facets (e.g., a hypercube). See
<a href="http://www.geom.uiuc.edu/~bradb/qh-faq.htm#extra">Why are there extra points in a 4-d or higher convex hull?</a>

»convex hull conventions

The following terminology is used for convex hulls in Qhull. See Qhull's data structures.

point - d coordinates
vertex - extreme point of the input set
ridge - d-1 vertices between two neighboring facets
hyperplane - halfspace defined by a unit normal and offset
coplanar point - a nearly incident point to a hyperplane
centrum - a point on the hyperplane for testing convexity
facet - a facet with vertices, ridges, coplanar points, neighboring facets, and hyperplane
simplicial facet - a facet with d vertices, d ridges, and d neighbors
non-simplicial facet - a facet with more than d vertices
good facet - a facet selected by 'QVn', etc.

»convex hull outputs

These options control the output from Qhull. They may be used individually or together.

: General
FA: compute total area and volume for 's' and 'FS'
s: print summary for the convex hull. Use 'Fs' for the numbers.

: Coordinates
Ft: print triangulation of the facets with added points
o: print coordinates for all points and list vertices in each facet
p: print vertex coordinates
Qc p: print coordinates of vertices and coplanar points

: Point indices
Fx: list extreme points (i.e., vertices)
i: list vertices for each facet
Fv: list vertices for each facet.
Qc Qi FP: print distance to nearest vertex for each non-extreme point

: Facets
Qc Fc: list coplanar points for each facet (one facet per point)
Qi Fc: list interior points for each facet (one facet per point)
Fn: list neighboring facets for each facet
FN: list neighboring facets for each vertex
Fa: print area for each facet

: Hyperplanes
n: print hyperplane for each facet
Fo: print outer plane for each facet

»convex hull controls

These options provide additional control:

QJ: joggle the input to guarantee triangular output
Qc: keep coplanar points
Qi: keep interior points
f: print all fields of all facets
QVn Pg: print facets adjacent to point n
PDk:0: print facets with a negative coordinate for dimension k
TFn: report progress after constructing n facets
Tv: verify result

»convex hull graphics

Display 2-d, 3-d, and 4-d convex hulls with Geomview ('G').

Display 2-d and 3-d convex hulls with Mathematica ('m').

To view 4-d convex hulls in 3-d, use 'Pd0d1d2d3' to select the positive octant and 'GrD2' to drop dimension 2.

»convex hull notes

Qhull always computes a convex hull. As described below, the convex hull may be used for other geometric structures. The general technique is to transform the structure into an equivalent convex hull problem. For example, the Delaunay triangulation is equivalent to the convex hull of the input sites after lifting the points to a paraboloid.

»Halfspace intersection about [n,n,0,...] ('Hn,n' or 'H')

The intersection of a set of halfspaces is a polytope. The polytope may be unbounded. See Preparata & Shamos ['85] for a discussion. In low dimensions, halfspace intersection may be used for linear programming.

Example: rbox c | qhull FV n | qhull H Fp: Print the intersection of the facets of a cube.

Qhull computes a halfspace intersection by the geometric duality between points and halfspaces. See halfspace notes and halfspace examples.

»halfspace input

The input is a set of halfspaces. Each halfspace is defined by d coefficients followed by a signed offset. This defines a linear inequality. The coefficients define a vector that is normal to the halfspace. The vector may have any length. If it has length one, the offset is the distance from the origin to the halfspace's boundary.

This is the same format that is used by options 'n', 'Fo', and 'Fi'. Use option 'Fd' to use cdd format for the halfspaces.

Qhull needs an interior point to compute the halfspace intersection. An interior point is inside all of the halfspaces Hx+b <= 0. Option 'Hn,n' defines the interior point as [n,n,0,...] where 0 is the default coordinate (e.g., 'H0' is the origin).

The input may start with a interior point. If so, use 'H' by itself. The input starts with a interior point when the first number is the dimension, the second number is "1", and the coordinates complete a line. Options 'FV n' produces an interior point and a set of halfspaces.

For example, here is the input for computing the intersection of halfplanes that form a square. Option 'H' is used since the input starts with an interior point.

rbox c | qhull FV n TO data

2 1
     0      0
3
4
     0     -1   -0.5
    -1      0   -0.5
     1      0   -0.5
     0      1   -0.5

qhull < data H Fp

3
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

»halfspace conventions

The following terminology is used for halfspace intersection in Qhull. This is the hardest structure to understand. The underlying structure is a convex hull with one vertex per nonredundant halfspace. See convex hull conventions.

interior point - a point in the intersection of the halfspaces. Qhull needs an interior point to compute the intersection. See halfspace input.
halfspace - d coordinates for the normal and a signed offset. The distance to an interior point is negative.
nonredundant halfspace - a halfspace that defines an output facet
vertex - a dual vertex in the convex hull corresponding to a nonredundant halfspace
coplanar point - the dual point corresponding to a similar halfspace
interior point - the dual point corresponding to a redundant halfspace
intersection point- the intersection of d or more nonredundant halfspaces
facet - a dual facet in the convex hull corresponding to an intersection point
non-simplicial facet - more than d halfspaces intersect at a point
good facet - an intersection point that satisfies restriction 'QVn', etc.

»halfspace outputs

The following options control the output for halfspace intersection. The other output formats display the dual convex hull.

: General
s: print summary for the halfspace intersection. Use 'Fs' for the numbers.
o: print the facets of the dual convex hull

: Intersections
FN: list the intersection points for each nonredundant halfspace
Fn: list the neighboring intersection points for each intersection point
Fp: print the coordinates for each intersection point

: Halfspaces
Fx: list the nonredundant halfspaces by input id.
i: list the nonredundant halfspaces for each intersection point.
Qi Fc: list the redundant halfspaces for each intersection point (one listing per halfspace)
Qc Fc: list the similar halfspaces for each intersection point (one listing per halfspace)

»halfspace controls

These options provide additional control:

QJ: joggle the input to remove singularities
f: print the data structure for each intersection (i.e., facet)
TFn: report summary after constructing n intersections
QVn Pg: select intersection points for halfspace n (marked 'good')
Tv: verify result

»halfspace graphics

To view the results with Geomview, compute the convex hull of the intersection points ('qhull FQ H0 Fp | qhull G'). See Halfspace examples.

»halfspace notes

If you do not know an interior point for the halfspaces, use linear programming to find one. Assume, n halfspaces defined by: aj*x1+bj*x2+cj*x3+dj>=0, j=1..n. Perform the following linear program:

max(x5) aj*x1+bj*x2+cj*x3+dj*x4-x5>=0, j=1..n

Then, if [x1,x2,x3,x4,x5] is an optimal solution with x4,x5>0 we get:

aj*(x1/x4)+bj*(x2/x4)+cj*(x3/x4)+dj>=(x5/x4)>0, j=1..n

and conclude that the point [x1/x4,x2/x4,x3/x4] is in the interior of all the halfspaces. Note that x5 is optimal, so this point is "way in" the interior (good for precision errors).

After finding an interior point, the rest of the intersection algorithm is from Preparata & Shamos ['85, p. 316, "A simple case ..."]. Translate the halfspaces so that the interior point is the origin. Calculate the dual polytope. The dual polytope is the convex hull of the vertices dual to the original faces in regard to the unit sphere (i.e., halfspaces at distance d from the origin are dual to vertices at distance 1/d). Then calculate the resulting polytope, which is the dual of the dual polytope, and translate the origin back to the interior point [S. Spitz and S. Teller].

Up: Home page for Qhull
Up: Qhull manual: Table of Contents
To: Rbox manual
To: Qhull options: Table of contents
To: Qhull options: Delaunay and Voronoi
Dn: Synopsis • Main • Output • Formats • Geomview • Print • Qhull • Precision • Trace

The Geometry Center Home Page

Comments to: qhull@geom.umn.edu
Created: Sept. 25, 1995 --- Last modified: see top