## Qhull |
Qhull computes the convex hull, Delaunay triangulation, Voronoi diagram,
halfspace intersection about a point, furthest-site Delaunay
triangulation, and furthest-site Voronoi diagram. The source code runs in
2-d, 3-d, 4-d, and higher dimensions. Qhull implements the Quickhull
algorithm for computing the convex hull. It handles roundoff
errors from floating point arithmetic. It computes volumes,
surface areas, and approximations to the convex hull.
Qhull does If you call Qhull from your program, please use reentrant Qhull (libqhull_r) or static Qhull (libqhull). If you use Qhull 2003.1, please upgrade or apply poly.c-qh_gethash.patch. |

**Introduction**

- Gregorius' talk on implementing Quickhull, Lloyd's QuickHull3D in Java, and Newbold's Waterman polyhedra
- Fukuda's introduction to convex hulls, Delaunay triangulations, Voronoi diagrams, and linear programming
- LEDA Guide to geometry algorithms
- MathWorld's Computational Geometry from Wolfram Research
- Skiena's Computational Geometry from his
*Algorithm Design Manual*. - Stony Brook Algorithm Repository, computational geometry

**Qhull Documentation and Support**

- Manual for Qhull and rbox
- Description of Qhull
- Imprecision in Qhull
- Programs and Options quick reference
- qconvex -- convex hull
- qdelaunay -- Delaunay triangulation
- qvoronoi -- Voronoi diagram
- qhalf -- halfspace intersection about a point
- rbox -- generate point distributions

- FAQ - frequently asked questions about Qhull
- Geomview for visualizing Qhull
- COPYING.txt - copyright notice

- REGISTER.txt - registration

- README.txt - installation
instructions

- Changes.txt - change history

- Qhull code
- Function index to Qhull

- Send e-mail to qhull@qhull.org
- Report bugs to qhull_bug@qhull.org

**Related URLs**

- Amenta's directory of computational geometry software
- BGL Boost Graph Library provides C++ classes for graph data structures and algorithms,
- CGAL and Leda libraries for writing computational geometry programs and other combinatorial algorithms
- Clarkson's hull program with exact arithmetic for convex hulls, Delaunay triangulations, Voronoi volumes, and alpha shapes.
- Erickson's Computational Geometry Pages and Software
- Fukuda's cdd program for halfspace intersection and convex hulls (Polco/Java)
- Gartner's Miniball for fast and robust smallest enclosing balls (up to 20-d)
- Mathtools.net of scientific and engineering software
- Owen's International Meshing Roundtable
- Schneiders' Finite Element Mesh Generation page
- Shewchuk's triangle program for 2-d Delaunay
- Voronoi Web Site for all things Voronoi
- Young's Internet Finite Element Resources
- Zolotykh's Skeleton generates all extreme rays of a polyhedral cone using the Double Description Method
- Tomilov's quickhull.hpp (doc-ru) implements the Quickhull algorithm for points in general position.

**FAQs and Newsgroups**

- FAQ for computer graphics algorithms
- FAQ for linear programming
- Newsgroup: comp.graphics.algorithms
- Newsgroup: comp.soft-sys.matlab
- Newsgroup: sci.math.num-analysis
- Newsgroup: sci.op-research

The program includes options for input transformations, randomization, tracing, multiple output formats, and execution statistics. The program can be called from within your application.

You can view the results in 2-d, 3-d and 4-d with Geomview. An alternative is VTK.

For an article about Qhull, download from ACM or CiteSeer:

Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T., "The Quickhull algorithm for convex hulls,"

ACM Trans. on Mathematical Software, 22(4):469-483, Dec 1996, http://www.qhull.org

Abstract:

The convex hull of a set of points is the smallest convex set that contains the points. This article presents a practical convex hull algorithm that combines the two-dimensional Quickhull Algorithm with the general dimension Beneath-Beyond Algorithm. It is similar to the randomized, incremental algorithms for convex hull and Delaunay triangulation. We provide empirical evidence that the algorithm runs faster when the input contains non-extreme points, and that it uses less memory.

Computational geometry algorithms have traditionally assumed that input sets are well behaved. When an algorithm is implemented with floating point arithmetic, this assumption can lead to serious errors. We briefly describe a solution to this problem when computing the convex hull in two, three, or four dimensions. The output is a set of "thick" facets that contain all possible exact convex hulls of the input. A variation is effective in five or more dimensions.

**Up:** *Past Software
Projects of the Geometry Center*

**URL:** http://www.qhull.org
**To:**
News
• Download
• Scholar
• Images
• Manual
• FAQ
• Programs
• Options
• Functions

Comments to: qhull@qhull.org

Created: May 17 1995 ---