Up: Directory of Computational Geometry Software
Arbitrary dimensional convex hull, Voronoi diagram, Delaunay triangulation
qhull
Arbitrary-dimensional convex hull.
Computes approximate hulls.
Floating-point arithmetic with many parameters for tolerancing.
Very fast.
Deterministic incremental algorithm with heuristics.
Does Voronoi diagrams and Delaunay triangulations
and, in low dimensions, Geomview output.
Check out the
qhull home page for more information.
By Brad Barber, David Dobkin and Hannu Huhdanpaa, The Geometry Center.
To get the code,
go to our qhull download page.
chD
Arbitrary-dimensional convex hull.
Computes exact hull of infinitessimally perturbed input.
The symbolic perturbations handle all degenerate cases and
break output faces up into simplices.
Deterministic incremental algorithm.
Does Voronoi diagrams and Delaunay triangulations
and, in low dimensions, Geomview output.
The options are described in the
README file for chD.
By Ioannis Emiris, U.C. Berkeley.
The code, and the relevant papers, are available by ftp from
Berkeley.
Hull
Arbitrary dimensional convex hulls, Delaunay triangulations, alpha shapes,
volumes of Voronoi cells; no non-degeneracy assumptions. ANSI C, about
3K lines.
Exact arithmetic, with moderate speed penalty over floating point.
Incremental algorithm, with performance guarantees if sites are added in
random order. Output formats include postscript in 2D, geomview in 3D.
By Ken Clarkson,
Bell Labs.
More information, references, and the code, is available on
netlib .
Porta
Arbitrary dimensional convex hull
or dual convex hull via Fourier-Motzkin elimination.
Uses integer arithmetic but does not handle degeneracies.
Also does enumeration of integer points inside the convex hull, projection
of halfspace intersection,
and tests a new facet to see if it intersects the hull.
Check out the
README for more information.
By Thomas Christof, Heidelburg University and Andreas Loebel, Konrad-Zuse-Zentrum fur Informatik (ZIB).
Get this program by ftp from
ZIB .
cdd
Dual convex hull - computes the vertices of a polytope defined as
an intersection of halfspaces (nice because it's easier to solve
convex hull given a program for the dual than visa versa).
Handles unbounded intersections of halfspaces.
Also can compute convex hulls of point sets, and unbounded convex
hulls given an unbounded direction.
A post-processing step gives the entire face structure of the polytope,
and an auxiliary program gives projections of the polytope to
lower-dimensional subspaces.
Both C and C++ source code, the latter with an exact arithmetic option
as well as floating point.
Just had a new release!
Look here for more details.
By Komei Fukuda, ETH Zurich, Switzerland and University of Tsukuba, Japan
Get the code from ETH by ftp.
lrs (rs, qrs)
lrs, like earlier versions rs and qrs,
finds all the vertices of a an intersection of
halfspaces, by walking from vertex to vertex.
C source code, with exact rational arithmetic and
optional lexographics symbolic perturbation to handle degenerate polytopes.
You should look at both the
README file,
and the
paper
to understand what's going on.
By David Avis, McGill University
The code is in this
ftp directory.
(Try doing ftp ``by hand'' from mutt.cs.mcgill.ca, /pub/C,
if you have trouble with this).
Up: Directory of Computational Geometry Software
![[HOME]](/pix/home.gif)
The Geometry Center Home Page
Comments to: nina@geom.umn.edu
Created: May 31 1995 ---
Last modified: Wed Jun 14 16:34:27 1995