![[random-fixed]](qh--rand.gif)
Qhull manual 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 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
• Synopsis • Main • Output • Formats • Geomview • Print • Qhull • Precision • Trace •
Note: This manual is included with Download Qhull.
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.
The input data on stdin consists of:
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.
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.
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.
Qhull produces the following data structures for dimension d:
For examples, use option 'f'. See polyhedron operations for further design documentation.
See Imprecision in Qhull.
See Rbox.
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.
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. 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.
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.
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
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.
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