Up: Home page for Qhull
To: Table of Contents (please wait
while loading)
To: Synopsis of Qhull (please wait
while loading)
Dn: Options for using Qhull
Dn: Rbox, Qhull's input generator
Dn: Imprecision in Qhull
Dn: Description of Qhull examples
Dn: Qhull internals
Qhull is a general dimension code for computing convex hulls, Delaunay triangulations, halfspace intersections, Voronoi regions and vertices, furthest-site Delaunay triangulations, and furthest-site Voronoi regions and vertices. These structures have applications in science, engineering, statistics, and mathematics. For a detailed introduction, see O'Rourke ['94].
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 (Geomview).
Brad Barber, Cambridge MA, April 14, 1997
Copyright © 1995, 1997 The Geometry Center, Minneapolis MN
Synopsis Main Output Formats Geomview Print Qhull Precision Trace
Note: This manual is included with Download Qhull.
Qhull constructs convex hulls, Delaunay triangulations, halfspace intersections, Voronoi regions and vertices, furthest-site Delaunay triangulations, and furthest-site Voronoi regions and vertices.
Qhull may be used for 2-d, 3-d, 4-d, and higher dimensions. For example, a Pentium 166 computes the Delauny triangulation of 1000 points in 3-d in one CPU second. It computes the convex hull of 25 cospherical points in 20-d in four CPU seconds. Memory and time requirements increase rapidly with increasing dimension.
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. 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 you need exact arithmetic or simplicial Delaunay triangulations try Clarkson's hull program or Shewchuk's triangle program. The later includes 2-d constrained triangulations.
If your problem is in high dimensions with non-simplicial facets, try Fukuda's cdd program in ftp://ifor13.ethz.ch/pub/fukuda/cdd/ . It is much faster than Qhull for these distributions. For other implementations and related software see Amenta's Directory of Computational Geometry Software , Erickson's Computational Geometry Pages, and the Stony Brook Algorithm Repository on computational geometry.
For Voronoi diagrams, Qhull produces the Voronoi vertices of each Voronoi region. In 2-d, it produces the Voronoi diagram. In higher dimensions, adjacency information can be derived from Qhull's data structures. Qhull computes furthest-site Voronoi vertices and furthest-site Delaunay triangulations. Except for spheres, Qhull is not suitable for the Delaunay triangulation of a surface.
Qhull uses a general dimension data structure based on a list of facets. If your problem is in 2-d or 3-d, a specialized data structure may be faster. If you need 2-d Delaunay triangulations, a bucketing approach may be faster. If you do not need the ridges of a high-dimensional hull, halfspace intersection with bit vectors may be much faster (see cdd above).
With floating point arithmetic, precision problems can be severe. Qhull handles precision problems by merging non-convex facets. Qhull produces a convex hull that clearly contains all of the input points. The output is clearly convex, but in higher dimensions (5-d and up with 'Qx'), a point could be outside of the hull.
Qhull is not suitable for mesh generation of arbitrary surfaces. You may use Qhull if the surface is 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.
As is, Qhull is not suitable for constrained Delaunay triangulations. With a fair amount of work, you can write a program that uses Qhull to add constraints by adding additional points to the triangulation.
Qhull is a convex hull program for 2-d, 3-d, 4-d, and higher dimensions. It reads points from stdin, and outputs the smallest convex set that contains the points to stdout according to printout options. If A is the matrix of facet normals and b is the vector of facet offsets, the convex hull of a set of points satisfies Ax+b<=0.
Qhull accounts for round-off error. It returns "thick" facets defined by parallel hyperplanes. The outer planes contain all input points (2-d, 3-d, or 4-d). The inner planes exclude all output vertices. See Imprecise convex hulls.
Qhull may be used for the Delaunay triangulation or the Voronoi vertices of a set of points. It may be used for the intersection of halfspaces.
The input data on stdin consists of:
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.
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 default printout option is a short summary ('s') to stdout. There are many other output 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).
Error messages and additional summaries ('s') go to stderr.
See Options.
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.
The data structure produced by Qhull consists of vertices, ridges, and facets. A vertex is a point of the input set. A ridge is a set of d vertices and two neighboring facets. For example in 3-d, a ridge is an edge of the polyhedron. A facet is a set of ridges, a set of neighboring facets, a set of incident vertices, and a hyperplane equation. For simplicial facets, the ridges are defined by the vertices and neighboring facets. When Qhull merges two facets, it produces a non-simplicial facet. A non-simplicial facet has more than d neighbors and may share more than one ridge with a neighbor.
A facet has a geometric and topological orientation. A facet's hyperplane equation determines its geometric orientation. The facet is oriented correctly if the distance from an interior point (qh interior_point) to the facet is negative. A facet is flipped if the distance is positive.
For a simplicial facet, a facet's vertices and toporient flag determines its topological orientation. The vertices are sorted by decreasing id. Each neighbor is opposite the corresponding vertex. Except for axis-parallel facets in 5-d and higher, the topological orientation determines the geometric orientation.
Ridges determine the topological orientation of a non-simplicial facet. Each ridge has two facets. If you exchange the facets, you reverse the orientation.
See Imprecision in Qhull.
See Rbox.
Geomview is an interactive geometry viewing program for SGI workstations, NeXT workstations, 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.
See Examples. Some of the examples have pictures .
See Options.
See Internals.
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.
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.
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 the reference and an 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.
C. Bradford Barber Hannu Huhdanpaa bradb@geom.umn.edu hannu@geom.umn.edu c/o The Geometry Center University of Minnesota 1300 South Second Street, Suite 500 Minneapolis, MN 55454
A special thanks to David Dobkin for his guidance. A special thanks to Albert Marden, Victor Milenkovic, the Geometry Center, and Harvard University 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.
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; included with Qhull].
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 modelling," Computer-Aided Design, vol. 25, p. 546-566, September 1993.
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: 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
To: Table of Contents
To: Synopsis 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
Comments to: qhull@geom.umn.edu
Created: Sept. 25, 1995 --- Last modified: see top