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

Copyright © 1995-1998 The Geometry Center, Minneapolis MN

## »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.umn.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