Announce: Qhull 3.0 for convex hull, Delaunay, Voronoi,
Halfspace
Brad Barber
bradb at shore.net
Sat Mar 24 10:48:29 PST 2001
I am pleased to announce Qhull 3.0 for computing
convex hulls, Delaunay triangulations, Voronoi diagrams, and
halfspace intersection about a point. It includes programs
for each of these structures.
Qhull uses floating point arithmetic to compute an approximation
to the convex hull. Each facet is defined by an outer plane that
is clearly above all points and an inner plane that is clearly below
the vertices. It provides two methods to handle precision errors:
facet merging -- If a ridge is not clearly convex, Qhull merges
a facet into a neighboring facet.
joggled input -- Qhull randomly perturbs the input. If a precision
error occurs, Qhull restarts with a larger joggle.
For example,
rbox 1000 W0 | qconvex QR0 R1e-3
computes the convex hull of 1000 points on the surface of a rotated
unit cube. To test Qhull, each computation is randomly perturbed
by up to 0.001. Qhull merged 92 facets to handle precision errors.
Convex hull of 1000 points in 3-d:
Number of vertices: 52
Number of facets: 39
Number of non-simplicial facets: 12
Statistics for: RBOX 1000 W0 | QCONVEX QR0 R1e-3 QR985448492
Number of points processed: 62
Number of hyperplanes created: 178
Number of distance tests for qhull: 18629
Number of merged facets: 92
Number of distance tests for merging: 2801
CPU seconds to compute hull (after input): 0.11
Maximum distance of point above facet: 0.0038 (0.6x)
Maximum distance of vertex below facet: -0.0074 (1.2x)
Home page:
http://www.geom.umn.edu/locate/qhull
Convex hull:
http://www.geom.umn.edu/software/qhull/html/qconvex.htm
Delaunay triangulation:
http://www.geom.umn.edu/software/qhull/html/qdelaun.htm
Voronoi diagram:
http://www.geom.umn.edu/software/qhull/html/qvoronoi.htm
Halfspace intersection about a point:
http://www.geom.umn.edu/software/qhull/html/qhalf.htm
N-dimensional point distributions:
http://www.geom.umn.edu/software/qhull/html/rbox.htm
--Brad
-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.
More information about the Compgeom-announce
mailing list