| 1 |
|
| 2 |
Qhull 2003.1 2003/12/30 |
| 3 |
|
| 4 |
http://www.qhull.org |
| 5 |
http://savannah.nongnu.org/projects/qhull/ |
| 6 |
http://www6.uniovi.es/ftp/pub/mirrors/geom.umn.edu/software/ghindex.html |
| 7 |
http://www.geomview.org |
| 8 |
http://www.geom.uiuc.edu |
| 9 |
|
| 10 |
Qhull computes convex hulls, Delaunay triangulations, Voronoi diagrams, |
| 11 |
furthest-site Voronoi diagrams, and halfspace intersections about a point. |
| 12 |
It runs in 2-d, 3-d, 4-d, or higher. It implements the Quickhull algorithm |
| 13 |
for computing convex hulls. Qhull handles round-off errors from floating |
| 14 |
point arithmetic. It can approximate a convex hull. |
| 15 |
|
| 16 |
The program includes options for hull volume, facet area, partial hulls, |
| 17 |
input transformations, randomization, tracing, multiple output formats, and |
| 18 |
execution statistics. The program can be called from within your application. |
| 19 |
You can view the results in 2-d, 3-d and 4-d with Geomview. |
| 20 |
|
| 21 |
To download Qhull: |
| 22 |
http://www.qhull.org/download |
| 23 |
http://savannah.nongnu.org/files/?group=qhull |
| 24 |
|
| 25 |
Download qhull-96.ps for: |
| 26 |
|
| 27 |
Barber, C. B., D.P. Dobkin, and H.T. Huhdanpaa, "The |
| 28 |
Quickhull Algorithm for Convex Hulls," ACM Trans. on |
| 29 |
Mathematical Software, 22(4):469-483, Dec. 1996. |
| 30 |
http://www.acm.org/pubs/citations/journals/toms/1996-22-4/p469-barber/ |
| 31 |
http://citeseer.nj.nec.com/83502.html |
| 32 |
|
| 33 |
Abstract: |
| 34 |
|
| 35 |
The convex hull of a set of points is the smallest convex set that contains |
| 36 |
the points. This article presents a practical convex hull algorithm that |
| 37 |
combines the two-dimensional Quickhull Algorithm with the general dimension |
| 38 |
Beneath-Beyond Algorithm. It is similar to the randomized, incremental |
| 39 |
algorithms for convex hull and Delaunay triangulation. We provide empirical |
| 40 |
evidence that the algorithm runs faster when the input contains non-extreme |
| 41 |
points, and that it uses less memory. |
| 42 |
|
| 43 |
Computational geometry algorithms have traditionally assumed that input sets |
| 44 |
are well behaved. When an algorithm is implemented with floating point |
| 45 |
arithmetic, this assumption can lead to serious errors. We briefly describe |
| 46 |
a solution to this problem when computing the convex hull in two, three, or |
| 47 |
four dimensions. The output is a set of "thick" facets that contain all |
| 48 |
possible exact convex hulls of the input. A variation is effective in five |
| 49 |
or more dimensions. |
| 50 |
|
