Up: Home page for Qhull
Up: FAQ about Qhull
To: Qhull manual: Table of Contents (please wait while loading)
To: Synopsis and examples of Qhull (please wait while loading)
Dn: Description of Qhull examples
Dn: Imprecision in Qhull
Dn: Options for using Qhull
Dn: Qhull internals
Dn: Rbox, Qhull's input generator

# Qhull manual

Qhull is a general dimension code for computing convex hulls, Delaunay triangulations, halfspace intersections about a point, Voronoi diagrams, furthest-site Delaunay triangulations, and furthest-site Voronoi diagrams. These structures have applications in science, engineering, statistics, and mathematics. See Fukuda's introduction to convex hulls, Delaunay triangulations, Voronoi diagrams, and linear programming. For a detailed introduction, see O'Rourke ['94], Computational Geometry in C.

Qhull implements the Quickhull algorithm for computing the convex hull. Qhull handles roundoff errors from floating point arithmetic. It can approximate a convex hull. It includes options for hull volume, facet area, multiple output formats, and graphical output.

Brad Barber, Cambridge MA, January 8, 1998

Copyright © 1995-1998 The Geometry Center, Minneapolis MN

## »Qhull manual: Table of Contents

- When to use Qhull
- Synopsis and examples of Qhull
- Description of Qhull
  - definition • input • output • algorithm • data structure
- Imprecision in Qhull
- Rbox, Qhull's input generator
- Geomview, Qhull's graphical viewer
- Examples of Qhull
- Options for using Qhull
  - Main options
    - Convex hull
    - Halfspace intersection
    - Delaunay triangulation
    - Voronoi diagram
    - Furthest-site Delaunay triangulation
    - Furthest-site Voronoi diagram
    - Joggled input or merged facets
  - Output formats
  - Additional I/O formats
  - Geomview output options
  - Print options
  - Qhull control options
  - Precision options
  - Trace options
- Qhull internals
  - Performance of Qhull
  - Calling Qhull from your program
  - Enhancements to Qhull
  - Qhull functions, macros, and data structures
- What to do if something goes wrong
- Email
- Authors
- References
- Acknowledgments

## »When to use Qhull

Qhull constructs convex hulls, Delaunay triangulations, halfspace intersections about a point, Voronoi diagrams, furthest-site Delaunay triangulations, and furthest-site Voronoi diagrams.

Qhull may be used for 2-d, 3-d, 4-d, and higher dimensions. For example, a Pentium 166 computes the Delaunay triangulation of 1000 points in 3-d in one CPU second. It computes the convex hull of the 7-d hypercube in two CPU seconds.

This is a big package with many options. It is one of the fastest available. It is the only 3-d code that handles precision problems due to floating point arithmetic. For example, it implements the identity function for extreme points (see Imprecision in Qhull).

If you need a short code for convex hull, Delaunay triangulation, or Voronoi volumes consider Clarkson's hull program. If you need 2-d Delaunay triangulations consider Shewchuk's triangle program. It is much faster than Qhull and it allows constraints. Both programs use exact arithmetic. They are in ftp://netlib.bell-labs.com/netlib/voronoi. Qhull version 1.0 may also meet your needs. It is 1/5 the size of Version 2.1.

If your problem is in high dimensions with a few, non-simplicial facets, try Fukuda's cdd. It is much faster than Qhull for these distributions.

Custom software for 2-d and 3-d convex hulls may be faster than Qhull. Qhull uses general-dimension data structures and code.

Qhull is not suitable for mesh generation or triangulation of arbitrary surfaces. You may use Qhull if the surface is convex or completely visible from an interior point (e.g., a star-shaped polyhedron). First, project each site to a sphere that is centered at the interior point. Then, compute the convex hull of the projected sites. The facets of the convex hull correspond to a triangulation of the surface. For mesh generation of arbitrary surfaces, see Schneiders' Finite Element Mesh Generation.

Qhull is not suitable for constrained Delaunay triangulations. With a lot of work, you can write a program that uses Qhull to add constraints by adding additional points to the triangulation.

Qhull is not suitable for the subdivision of arbitrary objects. To subdivide a convex object into tetrahedrons with Qhull, use options 'd QJ' on the object's vertices.

For other implementations and related software see

- Amenta's Directory of Computational Geometry Software
- Bronnimann's Computational Geometry Tribune, WWW sites
- Erickson's Computational Geometry Software
- the Stony Brook Algorithm Repository on computational geometry.

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

## »Synopsis and examples of Qhull

Note: This manual is included with Download Qhull.

Qhull computes convex hulls, Delaunay triangulations, Voronoi diagrams, and halfspace intersections about a point.
  When to use Qhull
  www.geom.umn.edu - home page for Qhull
  qhull-news.html - news about Qhull
  README.txt - installation instructions
  COPYING.txt - copyright notice
  REGISTER.txt - registration
  Changes.txt - change history
  qhull.txt - Unix manual page
input format, e.g., 'rbox 4', 'rbox 10 | qhull', or 'qhull <data'
  dimension
  number of points
  coordinates for each point
  Comments start with a non-numeric character
  For halfspaces, each halfspace ends with an offset
main options
  default
    convex hull
  d
    Delaunay triangulation
  v
    Voronoi diagram
  H1,1 Fp
    Halfspace intersection about [1,1,0,...]
  d Qu
    Furthest-site Delaunay triangulation
  v Qu
    Furthest-site Voronoi diagram
  QJ
    Joggle input or merge facets
  .
    concise list of all options
  -
    one line descriptions of all options
output options (subset)
  FA
    compute total area and volume for summary
  Fx
    extreme points (i.e., convex hull vertices)
  G
    Geomview output (2-d, 3-d, and 4-d)
  Fp
    halfspace intersections
  m
    Mathematica output (2-d and 3-d)
  n
    normals with offsets
  o
    OFF file format for facets or Voronoi vertices and 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
examples
  rbox c d D2 | qhull Qc s f Fx | more
    Print all fields of all facets for a square and a diamond. Also print a summary and a list of vertices. Note the coplanar points. Use output and format options to select individual fields.
  rbox 1000 s | qhull Tv s FA
    Compute the convex hull of 1000 cospherical points. Verify the results and print a summary with the total area and volume.
  rbox 10 D2 | qhull d QJ s i TO result
    Compute the 2-d Delaunay triangulation of 10 random points. Joggle the input to prevent singularities. Write the triangles to 'result' and a summary to the console.
  rbox 10 D2 | qhull v QJ o
    Print the Voronoi vertices and regions for the previous example.
  rbox 10 D2 | qhull v QJ Fv
    Print the edges of the Voronoi diagram for the previous example.
  rbox 10 D2 | qhull d Qu QJ m
    Print the furthest-site Delaunay triangulation in Mathematica format.
  rbox 10 D2 | qhull v Qu QJ o
    Print the furthest-site Voronoi vertices and regions. The first point represents 'infinity'. All regions are unbounded.
  rbox c | qhull n
    Print the normals for each facet of a cube.
  rbox c | qhull FV n | qhull H Fp
    Print the intersection of the facets of a cube.
  rbox d D12 | qhull QR0 FA
    Compute the convex hull of a 12-d diamond. Randomly rotate the input. Note the large number of facets and the small volume.
  rbox c D7 | qhull FA TF1000
    Compute the convex hull of the 7-d hypercube. Report on progress every 1000 facets. Computing the convex hull of the 9-d hypercube takes too much time and space.
  rbox y 500 W0 | qhull
    Compute the convex hull of a simplex and 500 points on the surface.
  rbox 10 | qhull v QJ o Fv
    Compute the Voronoi diagram of 10 3-d points. Print Voronoi vertices, regions, and ridges. The first point represents 'infinity'. Each ridge is listed with the corresponding pair of input sites.

## »Description of Qhull

### »definition

The convex hull of a point set P is the smallest convex set that contains P. If P is finite, the convex hull defines a matrix A and a vector b such that for all x in P, Ax+b <= [0,...].

Qhull computes the convex hull in 2-d, 3-d, 4-d, and higher dimensions. Qhull represents a convex hull as a list of facets. Each facet has a set of vertices, a set of neighboring facets, and a halfspace. A halfspace is defined by a unit normal and an offset (i.e., a row of A and an element of b).

Qhull accounts for round-off error. It returns "thick" facets defined by two parallel hyperplanes. The outer planes contain all input points. The inner planes exclude all output vertices. See Imprecise convex hulls.

Qhull may be used for the Delaunay triangulation or the Voronoi diagram of a set of points. It may be used for the intersection of halfspaces.

### »input format

The input data on `stdin` consists of:

- first line contains the dimension
- second line contains the number of input points
- remaining lines contain point coordinates

For example:

        3  #sample 3-d input
        5
        0.4 -0.5 1.0
        1000 -1e-5 -100
        0.3 0.2 0.1
        1.0 1.0 1.0
        0 0 0

Input may be entered by hand. End the input with a control-D (^D) character.

A comment starts with a non-numeric character and continues to the end of line. The first comment is reported in summaries and statistics. With multiple `qhull` commands, use option 'FQ' to place a comment in the output.

The dimension and number of points can be reversed. Comments and line breaks are ignored. Error reporting is better if there is one point per line.

### »output format

To write the results to a file, use I/O redirection or 'TO file'. Windows 95 users should use 'TO file' or the console.

The default output option is a short summary ('s') to `stdout`. There are many others (see output and formats). You can list vertex incidences, vertices and facets, vertex coordinates, or facet normals. You can view Qhull objects with Geomview or Mathematica. You can print the internal data structures. You can call Qhull from your application (see Qhull library).

For example, 'qhull o' lists the vertices and facets of the convex hull.

Error messages and additional summaries ('s') go to `stderr`. Unless redirected, `stderr` is the console.

### »algorithm

Qhull implements the Quickhull algorithm for convex hull [Barber et al. '96]. 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 & Shor '89; Clarkson et al. '93; Mulmuley '94]. For a demonstration, see How Qhull adds a point. The main advantages of Quickhull are output sensitive performance (in terms of the number of extreme points), reduced space requirements, and floating-point error handling.

### »data structures

Qhull produces the following data structures for dimension d:

- A coordinate is a real number in floating point format.
- A point is an array of d coordinates. With option 'QJ', the coordinates are joggled by a small amount.
- A vertex is an input point.
- A hyperplane is d normal coefficients and an offset. The length of the normal is one. The hyperplane defines a halfspace. If V is a normal, b is an offset, and x is a point inside the convex hull, then Vx+b <0.
- An outer plane is a positive offset from a hyperplane. When Qhull is done, all points will be below all outer planes.
- An inner plane is a negative offset from a hyperplane. When Qhull is done, all vertices will be above the corresponding inner planes.
- An orientation is either 'top' or 'bottom'. It is the topological equivalent of a hyperplane's geometric orientation.
- A simplicial facet is a set of d neighboring facets, a set of d vertices, a hyperplane equation, an inner plane, an outer plane, and an orientation. For example in 3-d, a simplicial facet is a triangle.
- A centrum is a point on a facet's hyperplane. A centrum is the average of a facet's vertices. Neighboring facets are convex if each centrum is below the neighbor facet's hyperplane.
- A ridge is a set of d-1 vertices, two neighboring facets, and an orientation. For example in 3-d, a ridge is a line segment.
- A non-simplicial facet is a set of ridges, a hyperplane equation, a centrum, an outer plane, and an inner plane. The ridges determine a set of neighboring facets, a set of vertices, and an orientation. Qhull produces a non-simplicial facet when it merges two facets together. For example, a cube has six non-simplicial facets.

For examples, use option 'f'. See polyhedron operations for further design documentation.

## »Imprecision in Qhull

See Imprecision in Qhull.

## »Rbox, Qhull's input generator

See Rbox.

## »Geomview, Qhull's graphical viewer

Geomview is an interactive geometry viewing program for SGI workstations, Sun workstations, NeXT workstations, Linux, and X-windows. It is available via anonymous ftp from geom.umn.edu. Besides a 3-d viewer, it includes a 4-d viewer, an n-d viewer and many features for viewing mathematical objects. You may need to ftp `ndview` from the `newpieces` directory.

## »Description of Qhull examples

See Examples. Some of the examples have pictures .

## »Options for using Qhull

See Options.

## »Qhull internals

See Internals.

## »What to do if something goes wrong

Please report bugs to qhull_bug@geom.umn.edu . Please report if Qhull crashes. Please report if Qhull generates an "internal error". Please report if Qhull produces a poor approximate hull in 2-d, 3-d or 4-d. Please report documentation errors. Please report missing or incorrect links.

If you do not understand something, try a small example. The rbox program is an easy way to generate test cases. The Geomview program helps to visualize the output from Qhull.

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. Qhull produces a compiler error if __STDC__ is not defined. You may need to set a flag (e.g., '-A' or '-ansi').

If Qhull compiles but crashes on the test case (rbox D4), there's still incompatibility between your system and ours. Sometimes it is due to memory management. This can be turned off with qh_NOmem in mem.h. Please let us know if you figure out how to fix these problems.

If you doubt the output from Qhull, add option 'Tv'. It checks that every point is inside the outer planes of the convex hull. It checks that every facet is convex with its neighbors. It checks the topology of the convex hull.

Qhull should work on all inputs. It may report precision errors if you turn off facet merging with option 'Q0'. This can get as bad as facets with flipped orientation or two facets with the same vertices. You'll get a long help message if you run into such a case. They are easy to generate with `rbox`.

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 ('T4') as a guide. This is especially true if you're incorporating Qhull into your own program.

When you report an error, please attach a data set to the end of your message. Include the options that you used with Qhull, the results of option 'FO', and any messages generated by Qhull. This allows me to see the error for myself. Qhull is maintained part-time.

## »Email

Please send correspondence to Brad Barber at qhull@geom.umn.edu and report bugs to qhull_bug@geom.umn.edu . Let me know how you use Qhull. If you mention it in a paper, please send a reference and 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, I will add you to the qhull_users alias. For Internet news about geometric algorithms and convex hulls, look at comp.graphics.algorithms and sci.math.num-analysis. For Qhull news look at qhull-news.html.

## »Authors

      C. Bradford Barber                    Hannu Huhdanpaa
      bradb@geom.umn.edu                    hannu@geom.umn.edu

                        c/o The Geometry Center
                        University of Minnesota
                        400 Lind Hall
                        207 Church Street S.E.
                        Minneapolis, MN 55455

## »Acknowledgments

A special thanks to David Dobkin for his guidance. A special thanks to Albert Marden, Victor Milenkovic, the Geometry Center, Harvard University, and Endocardial Solutions, Inc. for supporting this work.

The software was developed under National Science Foundation grants NSF/DMS-8920161 and NSF-CCR-91-15793 750-7504. If you find it useful, please let us know.

The Geometry Center is 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.

## »References

Aurenhammer, F., "Voronoi diagrams -- A survey of a fundamental geometric data structure," ACM Computing Surveys, 1991, 23:345-405.

Barber, C. B., D.P. Dobkin, and H.T. Huhdanpaa, "The Quickhull Algorithm for Convex Hulls," ACM Transactions on Mathematical Software, Vol. 22, No. 4 (Dec. 1996), p. 469-483 [http://www.acm.org; ftp://geom.umn.edu].

Clarkson, K.L. and P.W. Shor, "Applications of random sampling in computational geometry, II", Discrete Computational Geometry, 4:387-421, 1989

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.

Dobkin, D.P. and D.G. Kirkpatrick, "Determining the separation of preprocessed polyhedra--a unified approach," in Proc. 17th Inter. Colloq. Automata Lang. Program., in Lecture Notes in Computer Science, Springer-Verlag, 443:400-413, 1990.

Fortune, S., "Computational geometry," in R. Martin, editor, Directions in Geometric Computation, Information Geometers, 47 Stockers Avenue, Winchester, SO22 5LB, UK, ISBN 1-874728-02-X, 1993.

Milenkovic, V., "Robust polygon modeling," Computer-Aided Design, vol. 25, p. 546-566, September 1993.

Mucke, E.P., I. Saias, B. Zhu, Fast randomized point location without preprocessing in Two- and Three-dimensional Delaunay Triangulations, ACM Symposium on Computational Geometry, p. 274-283, 1996 [GeomDir].

Mulmuley, K., Computational Geometry, An Introduction Through Randomized Algorithms, Prentice-Hall, NJ, 1994.

O'Rourke, J., Computational Geometry in C, Cambridge University Press, 1994.

Preparata, F. and M. Shamos, Computational Geometry, Springer-Verlag, New York, 1985.

Qhull is available by anonymous ftp from geom.umn.edu. To retrieve a copy visit Download Qhull or, in Unix, ftp geom.umn.edu, user: anonymous, cd pub/software, get qhull.tar.Z, quit, uncompress qhull.tar.Z, tar xf qhull.tar, cd qhull, make

Up: Home page for Qhull
Up: FAQ about Qhull
To: Qhull manual: Table of Contents
To: Synopsis and examples of Qhull
Dn: Options for using Qhull
Dn: Rbox, Qhull's input generator
Dn: Imprecision in Qhull
Dn: Description of Qhull examples
Dn: Qhull internals

The Geometry Center Home Page

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