Up: Home page for Qhull
Up: Qhull manual
To:
Rbox manual
To: Table of contents (please wait while loading)
To: Delaunay and Voronoi options
Dn: SynopsisMainOutputFormatsGeomviewPrintQhullPrecisionTrace


[delaunay] Qhull convex hull and halfspace intersection options

These sections describe the options for Qhull. This section lists the main options. It includes a discussion of convex hulls and half-space intersections.

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

rbox c D4 | qhull n

See the Examples section for more examples. Execute 'qhull' by itself for a synopsis of the most important options. To get the full list of options, execute 'qhull -'. 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 can, use Geomview to view the results. Start with the following input sets:

Brad Barber, Cambridge MA, March 28, 1997

Copyright © 1995, 1997 The Geometry Center, Minneapolis MN


»Qhull options: Table of contents

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:

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).


SynopsisMainOutputFormatsGeomviewPrintQhullPrecisionTrace

»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 vertices and regions ('v')
conventions • outputs • controls • graphics • notes
 
Furthest-site Delaunay triangulation ('d Qu')
conventions • outputs • controls • graphics • notes
 
Furthest-site Voronoi vertices and regions ('v Qu')
conventions • outputs • controls • graphics • notes

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.

Qhull always computes a convex hull.

»convex hull conventions

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

»convex hull outputs

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

»convex hull controls

These options provide additional control:

»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 'Pd0d1d2' 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. See Precision issues for the use of halfspace intersection in Qhull's identity function.

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 coordinates and a signed offset. This is the same format that is used by options 'n', 'Fo', and 'Fi'. With option 'Fd', the halfspaces are in cdd format.

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 feasible point. If so, use 'H' by itself. The input starts with a feasible point when the first number is the dimension, the second number is "1", and the coordinates complete a line. Options 'FV n' produces a feasible point and a set of halfspaces.

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

»halfspace outputs

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

»halfspace controls

These options provide additional control:

»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 a feasible point for the half-spaces, 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 a feasible point, the rest of the intersection algorithm is from Preparata & Shamos ['85, p. 316, "A simple case ..."]. Translate the halfspaces so that the feasible 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 feasible point [S. Spitz and S. Teller].


Up: Home page for Qhull
Up: Qhull manual
To:
Rbox manual
To: Table of contents
To: Delaunay and Voronoi options
Dn: SynopsisMainOutputFormatsGeomviewPrintQhullPrecisionTrace


The Geometry Center Home Page

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