This page contains a list of free computational geometry programs and packages. If you have, or know of, any others, please send me mail. I'm also interested in tools, like arithmetic or linear algebra packages. Other feedback is also welcome
Nina Amenta, Collector
XYZGeobench
Library of 2-D algorithms with animation, in
ObjectPascal for the MAC. Algorithms include:
For more information, including a full list of algorithms and references, see the abstract . There is also a README file and some papers at the ftp site.
By Peter Schorn and lots of others, at ETH Zurich.
Distributed by ftp from ETH.
You can look at the README for more information.
By Pedro J. de Rezende, Welson R. Jacometti, Cesar N. Gon,
and Laerte F. Morgado, Universidade Estadual de Campinas, Brazil.
Because Brazil is far away, we mirror this system in our
ftp
directory.
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 short abstract , or the long man page .
By Brad Barber, David Dobkin and Hannu Huhdanpaa, The Geometry Center.
To get the code,
go to our ftp directory
and get qhull.tar.Z.
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.
Check out the
README for more information.
By Thomas Christof, Heidelburg University and Andreas Loebel, Konrad-Zuse-Zentrum fur Informatik (ZIB).
There is more information on the
manpage .
By Steve Fortune, Bell Labs.
By Barry Joe, University of Alberta.
There's a short
paper about this program.
By Ernst Muecke, University of Illinois at Urbana-Champaign.
There's more information in the
README file.
By Carol Hazelwood, Southwest Texas State University.
By Mike Hohmeyer, U.C. Berkeley.
See geompack, above.
There is a two-page
paper about arrange.
By Michael Goldwasser, Stanford University.
Details are in the
README file.
By Dimitris Gunopulos, Princeton University.
LEDA is a language, and it has a thick manual,
available at the ftp site. There is a little more info in
this
abstract .
By Stefan Naeher, Max Plank Institute.
There is a short manual included in the distribution.
By Geert-Jan Giezeman, Utrect University.
Take a look at the
abstract for an overview.
There is also documentation and the text of the relevant papers
at the ftp site.
By Ashu Rege, U.C. Berkeley.
Take a look at the alpha README
or the Shape2D README
for a little more information.
There is more documentation and references at
the ftp site.
alpha by Ernst Muecke, Michael Facello, Supervisor: Herbert Edelsbrunner,
Shape2D by Nataraj Akkiraju, Supervisor: Herbert Edelsbrunner,
Web on over to
INRIA for more details.
By Bernhard Geiger, INRIA.
The best documentation is the book!
By Joe O'Rourke, Smith College.
Take a look at the table of contents
and see if they've got what you want.
The programs are available by
ftp from Princeton.
The program comes with a 60 page user manual.
By J.J. Verkuil, Utrect University.
Marc Brown and John Hershberger, DEC SRC.
We have lots more
information available, which will lead you to the ftp address.
By Stuart Levy, Tamara Munzner, Mark Phillips and others, The Geometry Center.
Porta
Arbitrary dimensional convex hull
via Fourier-Motzkin elimination,
using integer arithmatic.
Also does enumeration of integer points inside the convex hull
and tests a new facet to see if it intersects the hull.
Get this program by ftp from
ZIB .
Low dimensional Voronoi diagrams and Delaunay triangulations
voronoi
Voronoi diagram of points in the plane.
Fortune's planesweep algorithm.
Floating-point arithmatic in C.
This program lives in
netlib .
geompack
Delaunay triangulation of point sets in 2-D, 3-D and k-D, where
k is small.
Also contains convex decomposition and triangulation programs for
2D polygons and 3D polyhedra.
Fortran 77 source code.
For more info (including references) go to the
ftp site at Alberta.
Detri
Delaunay tetrahedralization of 3-D point sets.
Incremental flipping algorithm.
Executables for X, SGI and Sun. Graphical interface.
As part of the Alpha-shapes distribution.
Get Detri by
ftp from NCSA.
tess
Delaunay tetrahedralization of 3-D point set using a sort
of gift-wrapping algorithm. In C. Floating point with
careful attention to numerical stability, but not guaranteed
to handle degenerate input.
Get tess from our
ftp directory.
Linear programming and its relatives
linprog
Low-dimensional linear programming using
Seidel's randomized incremental algorithm.
Also handles rational objective functions, so with some cleverness
you can get arbitrary-dimensional smallest enclosing ball,
polytope seperation distance, linear programming on a sphere, ect.
C source code.
Available by ftp from
ICEMCFD, Mike's company.
Triangulation, trapezoidation, point location
arrange
Randomized incremental trapezoidation of
arrangements of polygons in the plane
or on the sphere, with point location.
C source code.
Look in Stanford's
ftp directory
for the code.
trapdec
Linear-time trapezoidation of a simple polygon, in C.
An input flag gives an O(n lg n) time trapezoidation which
is probably faster!
C source code.
Get trapdec from our
ftp directory .
Objects and Data structures
LEDA
LEDA is a collection of
C++ objects and data structures for graph theoretic
and geometric algorithm implementation. Objects include
rational planar points and segments, and
floating-point points, segments, polygons, circles and planar
subdivisions.
Sets, dictionaries, queues, stacks and other useful data structures
are implemented, as are
many graph algorithms.
The LEDA distribution
also includes planar convex hull, Voronoi diagram and
sweepline segment intersection programs.
Get LEDA and it's documentation from the
ftp site at MPI.
PLAGEO/SPAGEO
A collection of geometric C++ objects.
Planar point, line, polygon objects, and
3-D point, line, polygon, sphere, and polyhedron objects.
Rigid motion, intersection and distance functions.
Look for these collections at the
ftp site in Utrecht.
Algebraic Surfaces
toolkit
Toolkit for Algebra and Geometry.
Resultants, sub-resultants and Sturm-Habicht sequences
for multivariate polynomials
over floating-point numbers, integers modulo a prime,
straight-line programs or mixed-arithmatic.
Use to solve systems of polynomial equalities.
Get the toolkit by
ftp
from Berkeley.
Reconstruction
alpha and Shape2D
alpha produces a set of tetrahedra, triangles and edges
determined in a nice mathematically precise way from a set of points
in 3-space. Usually gives a nice picture of the ``shape'' of the
point set.
Shape2D does the same thing for 2-D point sets.
Executables for X, SGI and Sun. Graphical interface.
and Duane Setterdahl, Gilles Bourhis, Jiang Qian, Supervisor: Ping Fu.
and Carlos Varela, Supervisor: Ping Fu.
All at the University of Illinois at Urbana-Chapaign, and NCSA.
The programs and documentation are available by
ftp from NCSA.
Nuages
3-D model reconstruction from 2-D slices.
Binaries for various machines.
Code from books
Code from "Computational Geometry in C"
Get the code by
ftp from Smith.
Code from "Graphics Gems"
Lots of wacky primitives, and some interesting higher-level algorithms,
especially in Graphics Gems IV, eg.
a C++ implementation of an incremental
2-D Delaunay triangulation.
Visualization
idual
Visualization of planar dualities, for
SGI Iris.
Get idualbin1.1.tar.gz from the
ftp site at Utrecht.
ZEUS
Algorithm animation system. Distributed as part of
Modula-3.
Their Web site has more information on
ZEUS.
Geomview
The Geometry Center's own popular
interactive viewer for three and higher dimensional geometry.