+ + +
Up: Home page for Qhull
-Up:Home page for Qhull (local)
+Up: News about Qhull
-Up: FAQ about Qhull
-To: Qhull manual: Table of Contents
-(please wait while loading)
+Up: Qhull Wiki and
+FAQ (local)
+To: Qhull manual: contents
To: Programs
• Options
• Output
@@ -30,7 +30,7 @@
• Qhull
• Precision
• Trace
-• Functions
+• Functions (local)
Brad Barber, Arlington, MA
-Copyright © 1995-2015 C.B. Barber
+Copyright © 1995-2020 C.B. Barber
@@ -157,7 +158,7 @@
-
@@ -183,12 +183,11 @@ comp.graphics.algorithms
For convex hulls and halfspace intersections, Qhull may be used -for 2-d upto 8-d. For Voronoi diagrams and Delaunay triangulations, Qhull may be -used for 2-d upto 7-d. In higher dimensions, the size of the output +for 2-d up to 8-d. For Voronoi diagrams and Delaunay triangulations, Qhull may be +used for 2-d up to 7-d. In higher dimensions, the size of the output grows rapidly and Qhull does not work well with virtual memory. If n is the size of the input and d is the dimension (d>=3), the size of the output @@ -223,24 +222,26 @@ not try to build a 16-d convex hull of 1000 points. It will have on the order of 1,000,000,000,000,000,000,000,000 facets. -
On a 600 MHz Pentium 3, Qhull computes the 2-d convex hull of -300,000 cocircular points in 11 seconds. It computes the -2-d Delaunay triangulation and 3-d convex hull of 120,000 points -in 12 seconds. It computes the -3-d Delaunay triangulation and 4-d convex hull of 40,000 points -in 18 seconds. It computes the -4-d Delaunay triangulation and 5-d convex hull of 6,000 points -in 12 seconds. It computes the -5-d Delaunay triangulation and 6-d convex hull of 1,000 points -in 12 seconds. It computes the -6-d Delaunay triangulation and 7-d convex hull of 300 points -in 15 seconds. It computes the -7-d Delaunay triangulation and 8-d convex hull of 120 points -in 15 seconds. It computes the -8-d Delaunay triangulation and 9-d convex hull of 70 points -in 15 seconds. It computes the -9-d Delaunay triangulation and 10-d convex hull of 50 points -in 17 seconds. The 10-d convex hull of 50 points has about 90,000 facets. +
On a 1.7 GHz i7, Qhull computes the 2-d convex hull of +3,000,000 evenly spaced, cocircular points in 4.7 seconds. +It computes the +2-d Delaunay triangulation and 3-d convex hull of 600,000 points +in 5.9 seconds. It computes the +3-d Delaunay triangulation and 4-d convex hull of 120,000 points +in 4.6 seconds. It computes the +4-d Delaunay triangulation and 5-d convex hull of 30,000 points +in 5.1 seconds. It computes the +5-d Delaunay triangulation and 6-d convex hull of 6,000 points +in 7.8 seconds. It computes the +6-d Delaunay triangulation and 7-d convex hull of 1,000 points +in 7.6 seconds. It computes the +7-d Delaunay triangulation and 8-d convex hull of 300 points +in 8.6 seconds. It computes the +8-d Delaunay triangulation and 9-d convex hull of 120 points +in 5.7 seconds. It computes the +9-d Delaunay triangulation and 10-d convex hull of 70 points +in 4.8 seconds. +The 10-d convex hull of 70 cospherical points has about 375,000 facets.
Qhull does not support constrained Delaunay @@ -248,12 +249,23 @@ generation of non-convex objects, or medium-sized inputs in 9-D and higher.
-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 +
This is a big package with many options. For 32-bit code, it is one of the +fastest available. It is the only 3-d and higher code that handles precision problems due to floating point arithmetic. For example, it implements the identity function for extreme points (see Imprecision in Qhull).
+Qhull does not handle all precision problems (Limitations of merged facets). +For example, errors may occur for the 4-D Delaunay triangulation of nearly adjacent points in the unit cube. If every +input site has a nearly adjacent point within a 10^-13 ball, precision errors and topological errors are likely to +occur. A bounding box may alleviate these errors. Nearly adjacent points within substantially smaller or larger balls +are OK.
+ +Joggled input, option 'QJn', is an alternative to merged facets (Merged facets or joggled input). +It randomly perturbs the input. If precision problems occur, Qhull restarts with a larger, random perturbation. Joggled input +is a simple solution without the limitations of merged facets. For example, Qhull constructs a convex hull even if all of the input points +are identical.
+If you need a short code for convex hull, Delaunay triangulation, or Voronoi volumes consider Clarkson's hull @@ -262,20 +274,22 @@ program. It is much faster than Qhull and it allows constraints. Both programs use exact arithmetic. They are in http://www.netlib.org/voronoi/. -Qhull version -1.0 may also meet your needs. It detects precision problems, -but does not handle them.
+ +If your input is in general position (i.e., no coplanar or colinear points), +Tomilov's quickhull.hpp (documentation-ru), +or Qhull version 1.0 may meet your needs. Both programs detect precision problems, +but do not handle them.
CGAL is a library of efficient and reliable -geometric algoriths. It uses C++ templates and the Boost library to produce dimension-specific +geometric algorithms. It uses C++ templates and the Boost library to produce dimension-specific code. This allows more efficient use of memory than Qhull's general-dimension -code. CGAL simulates arbitrary precision while Qhull handles round-off error -with thick facets (Robustness Issues in CGAL, -Imprecision in Qhull). - +code. For 64-bit code, CGAL uses significantly less memory than Qhull and runs faster. +CGAL simulates arbitrary precision while Qhull handles round-off error +with thick facets. Compare the two approaches with Robustness Issues in CGAL, +and Imprecision in Qhull. -
Leda is a +
Leda is a library for writing computational geometry programs and other combinatorial algorithms. It includes routines for computing 3-d convex @@ -312,8 +326,7 @@ objects. Use qdelaunay to subdivide a convex object.
-»definition
@@ -405,9 +418,9 @@Single letters are used for output formats and precision constants. The other options are grouped into menus for formats ('F'), Geomview ('G '), printing ('G'), printing ('P'), Qhull control ('Q '), and tracing ('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 'A coordinate is a real number in floating point format.
For examples, use option 'f'. See polyhedron operations for further +href="http://www.qhull.org/src/libqhull_r/qh-poly_r.htm">polyhedron operations (local) for further design documentation.
@@ -556,13 +569,13 @@--See Options.
+See Qhull options.
-See Internals.
+See Qhull code.
If using Xforms (e.g., for Geomview's External Modules), install the 'libXpm-devel' package from cygwin and move the xforms directory into your geomview directory, e.g.,
mv xforms-1.2.4 geomview-1.9.5/xforms
-
Geomview's ndview provides multiple views into 4-d and higher objects. +
Geomview's ndview provides multiple views into 4-d and higher objects. This module is out-of-date (geomview-users: 4dview). Download NDview-sgi.tar.Z at newpieces and 4dview at Geomview/modules. @@ -712,13 +725,12 @@ -
-. Please report if Qhull crashes. Please report if Qhull +Please report bugs to qhull_bug@qhull.org -
Please report bugs to qhull_bug@qhull.org. +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 @@ -747,7 +759,13 @@ facet is convex with its neighbors. It checks the topology of the convex hull.
-Qhull should work on all inputs. It may report precision +
Qhull resolves most precision issues. It reports +a precision error for lower dimensional inputs. It may report a precision +error for non-simplicial facets with multiple merges or nearly +adjacent vertices. See Limitations of merged facets for +more information. + +
Qhull reports precision errors if you turn off merged facets with option 'Q0'. This can get as bad as facets with flipped orientation or two facets with the same vertices. You'll @@ -808,7 +826,7 @@
A special thanks to Endocardial Solutions, Inc. of St. Paul, Minnesota for their support of the -internal documentation (src/libqhull/index.htm). They use Qhull to build 3-d models of +code documentation (src/libqhull_r/index.htm, local). They use Qhull to build 3-d models of heart chambers.
Qhull 1.0 and 2.0 were developed under National Science Foundation @@ -828,7 +846,8 @@ -- A survey of a fundamental geometric data structure," ACM Computing Surveys, 1991, 23:345-405.
-Barber, C. B., D.P. Dobkin, and H.T. +
+Barber, C. B., D.P. Dobkin, and H.T. Huhdanpaa, "The Quickhull Algorithm for Convex Hulls," ACM Transactions on Mathematical Software, 22(4):469-483, Dec 1996, www.qhull.org [Edelsbrunner, H, Geometry and Topology for Mesh Generation, Cambridge University Press, 2001. -
Gartner, B., "Fast and robust smallest enclosing balls", Algorithms - ESA '99, LNCS 1643. +
Gartner, B., "Fast and robust smallest enclosing balls", Algorithms - ESA '99, LNCS 1643. -
Golub, G.H. and van Loan, C.F., Matric Computations, Baltimore, Maryland, USA: John Hopkins Press, 1983 +
Golub, G.H. and van Loan, C.F., Matric Computations, Baltimore, Maryland, USA: John Hopkins Press, 1983
Fortune, S., "Computational
geometry," in R. Martin, editor, Directions in Geometric
@@ -893,11 +912,12 @@
Up: Home page for Qhull
+href="http://www.qhull.org">Home page for Qhull (local)
Up:News about Qhull
-Up: FAQ about Qhull
-To: Qhull manual: Table of Contents
+Up: Qhull Wiki and
+FAQ (local)
+To: Qhull manual: contents
To: Programs
• Options
• Output
@@ -907,12 +927,10 @@
• Qhull
• Precision
• Trace
-• Functions
+• Functions (local)
Dn: Imprecision in Qhull
Dn: Description of Qhull examples
-Dn: Qhull internals
-Dn: Qhull functions, macros, and data
-structures
+Dn: Qhull code
Comments to: qhull@qhull.org
-
+
Created: Sept. 25, 1995 --- Last modified: see top