Computational Geometry
Code
This page lists "small" pieces of geometric software available on the Internet. Most of
the software is available free of charge. Unless otherwise specified, C or
C++ source code is available for all programs.
Software libraries and collections and
programs that can be run interactively over the web are listed
on separate web pages.
Caveat Surfor! I can't make any claims about the
usefulness or quality of the programs listed here. I don't have the time or equipment to
try them all. If you have experience with any of these programs, either positive or
negative, please tell me about it.
The programs on this page are divided into several categories, some of which are
divided into further subcategories. (Eventually, each category will get its own separate
web page.) Each program is listed only once, but I've provided crosslinks between
overlapping categories, and I've tried to arrange similar categories near each other.
Each category also includes links to relevant pages in
Nina Amenta's comprehensive
Directory of Computational Geometry
Software, which I strongly encourage you to visit!
Items marked have been recently added
or modified.
Avoid roundoff and precision errors! Use this code instead of naïve floating point
or integer arithmetic.
Most convex hull programs will also compute Voronoi diagrams and
Delaunay triangulations. (Actually, all of them do, if you look at them the
right way.)
Relevant pages from DCGS:
Lowdimensional convex hulls
Arbitrarydimensional convex hulls
 lrs 3.1: the first "official"
distribution of David Avis' implementation of Avis
and Fukuda's reverse search algorithm for vertex/facet enumeration. (This is an
updated version of an
earlier preliminary implementation.) An extensive
user's guide
is included.
 Qhull by Brad Barber,
David Dobkin, and Hannu Huhdanpaa
 Primaldual methods for vertex
and facet enumeration by
David Bremner,
Komei Fukuda,
and Ambros Marzetta
 Hull:
Arbitrarydimensional convex hulls, Voronoi diagrams, Delaunay
triangulations, and alpha shapes, by
Ken Clarkson

PORTA, a collection of tools for analyzing polytopes and polyhedra, by
Thomas Christof and
Andreas Loebel,
featured in Günter Ziegler's Lectures on Polytopes.
 Computational
geometry software by
Ioannis Emiris: perturbed convex hulls in arbitrary dimensions, exact convex
hulls in two and three dimensions, mixed volume in arbitrary dimensions, and mixed
subdivisions in the plane.
 Polytope software by
Komei Fukuda
 Kurt Mehlhorn's
programs for generating higher dimensional convex hulls and Delaunay
triangulations and checking geometric structures.
(C++WEB output only)
Measure properties
 Vinci
(also here):
a program for computing volumes of convex polytopes, presented as either the
convex hull of a set of points, the intersection of a set of halfspaces, or both
(with the vertexfacet incidence graph). Extensive
online documentation and
sample polytope
files are available. Written by
Benno
Büeler, Andreas
Enge, and
Komei Fukuda.
 Ehrhart, a
program to count integer points in convex polyhedra and compute
Ehrhart
polynomials, by Philippe
Claus, Vincent
Loechner, and Doran Wilde.

Fast and accurate computation of polyhedral mass properties by
Brian Mirtich,
published in
journal of graphics tools 1.2:3150 (1996)
Boolean operations on polyhedra
Interesting and/or pathological polytope data
Miscellaneous
See also the implementation page
from Christopher Gold's site www.Voronoi.com.
Relevant pages from DCGS:
Voronoi diagrams and Delaunay triangulations of points
Many convex hull programs can also compute Voronoi diagrams and
Delaunay triangulations.
 2d and 3d
Delaunay triangulations by JeanDaniel Boissonnat, Olivier Devillers, Stefan
Meiser, and Monique Teillaud, from the
PRISME project at INRIA
SophiaAntipolis.
 The Delaunay
hieararchy, a data structure for 2d Delaunay triangulations that supports
dynamic insertions (and deletions, but those aren't implemented), by Olivier
Devillers, from the
PRISME project at INRIA
SophiaAntipolis. (Solaris and SGI executables only)
 Graphics utilities
by David Eberly:
 GAMBINI: a program for
constructing multiplicatively weighted Voronoi diagrams for points in the plane,
by Barry Boots.
(Windows 3.1/95/NT executable only)
 Ernst Mücke's
Detri, from his
GeomDir, robustly computes 3D Delaunay triangulations.

A simple divideandconquer Delaunay triangulation algorithm from Jorge
Stolfi's
software collection. Requires Stolfi's
quad edge
data structure library.
 Software by John Sullivan
includes code to compute either standard Voronoi diagrams in Euclidean 3space or
periodic Voronoi diagrams in the 3torus.
 Dave Watson's incremental
convex hull/Delaunay triangulation program
nnsort.c
and
a description of
the algorithm
 Roman Waupotitsch's MinMaxer
generates Delaunay, regular, and various other triangulations of twodimensional
point sets.
 Software on the Web, from
the CNRPisa Visual Computing
Group, includes code for
3D Delaunay
triangulations
Constrained Delaunay triangulations
See also mesh generation and manipulation.
 Super Delaunay, a
commercial fully dynamic constrained Delaunay triangulation package from
David Kornmann (description only).
Interactive demo versions for Sun
Solaris and Linux are available here
(binaries and data only). Demo versions for other architectures
are available from the author.
 Dani Lischinski's
incremental constrained Delaunay triangulation program
CDT.
 Robert J. Renka's TRIPACK,
Collected Algorithms of the
ACM #751, computes constrained Delaunay triangulations, convex hulls,
polygon areas, nearest neighbors, and shortest paths. (FORTRAN)
Medial axes and Voronoi diagrams of line segments
Miscellaneous
Relevant pages from DCGS:
Point location
Boolean operations
 Constructive Planar
Geometry by David Eberly:
standard boolean operations on generalized polygons (only intersection is actually
implemented)
 Boolean operations on
polygons by Matej Gombosi.
 Boolean operations on sets of
2d polygons, by Klaas Holwerda,
includes interactive visualization software (Sun and Windows only) and a
complete
description of the algorithms and data structures used. Results are
"snaprounded" to the integer grid.
 Polypack,
a package of routines to manipulate polygons, by David J. Kennison
(FORTRAN, description only)
 Alan Murta's
generic
polygon clipping library computes intersections, unions, and differences
between possibly selfintersecting, possibly multiplyconnected polygons,
possibly with holes.
 Klammer Schutte's
clippoly
computes intersections and differences of nonconvex polygons. (Warning: The
source contains over 10,000 lines of C++ code!)
Triangulation and quadrangulation
See also the sections on Voronoi diagrams and Delaunay
triangulations and mesh generation and manipulation.
Miscellaneous
See also the sections on Delaunay triangulations and
geometric modeling.
 Relevant pages from DCGS:
 Other collections:
 Barry Joe's
GEOMPACK
(FORTRAN)

Scott Mitchell's triangulation results includes code to generate
linearsize nonobtuse triangulations of polygons, using the
circlepacking algorithm of Bern, Mitchell, and Ruppert.
(MATLAB and C++)
 EasyMesh
by Bojan Niceno builds constrained and
conforming Delaunay triangulations (and their dual Voronoi diagrams) and performs
local mesh coarsening, refining, relaxation, and smoothing. Written by an applied
physicist using
algorithms developed by other applied physicists.
 Triangle, a comprehensive
package by Jonathan Shewchuk for generating Delaunay triangulations and
guaranteedquality meshes.

QMG: mesh generation and related software by
Steven
Vavasis
 The Chopper, a
semiautomatic hexahedral mesh generator, by the
Finite Element Modelling Group, Queen's University of Belfast
(descriptions only)
 STRIPE
breaks a polygonal model into few triangle strips.
See also the section on mesh generation and manipulation.
Relevant pages from DCGS:
Binary space partition trees
Collision detection
Reconstruction
Simplification
You should also look for the thing being visualized! See also my list of
programs that can be run over the web.
 Relevant pages from DCGS:
 UNREAL, a GeomView
module for "handdrawing" mathematical objects, by
Nina Amenta,
Danek Duvall, and
Tim Rowley
 Javier Elices's GeomView module
for visualizing the DobkinKirkpatrick
hierarchy
 Graphviz, tools for
viewing and interacting with graph diagrams, by
John Ellson,
Eleftherios Koutsofios, and
TopoVista: fly over
USGS Digital Elevation Models, using
right triangular
irregular networks to maintain variable levels of detail, courtesy of
Will Evans and
Gregg Townsend.
Requires OpenGL and Glut.

DUST, a program for visualizing Voronoi diagrams, Delaunay triangulations,
minimum spanning trees, and matchings in various metrics. From
Michael
Jünger's research group at Universität zu Köln.
 Peek by
Gordon Kindlmann, a program
for visualizing highdimensional polytopes through their crosssections and
projections (or as Amenta and Ziegler would have it, their
shadows and
slices).
 Cinderellas Café, a "dynamic
geometry" Java program written by Ulrich Kortenkamp and Jürgen
RichterGebert, dynamically maintains sets of geometric objects (points, lines,
circles, and conics) as the user moves their defining points around, provides
primal and polar views of the same objects, supports spherical and hyperbolic
geometry, and even includes some automatic theorem proving!
A demo version
is available. Information
is currently available in German only.

Geomview, the Geometry Center's 3d geometric visualization program, written
by Stuart Levy, Tamara Munzner, Mark Phillips, and a cast of thousands. Also
available from a
mirror site in Berlin.
 JGV, a successor to GeomView
written in Java, also from the Geometry Center. (Java, source not
available)
 Bob Lewis's
homogeneous coordinates and duality visualization program
VideHoc (SGI executable only)
 Michael Murphy's
Ranger, a program for visualizing highdimensional nearest neighbor and
orthogonal range searching data structures. From
Steve Skiena's
Practical Algorithm
Reference
 The GeoPrO distributed
visualization enviornment,
by Pedro J. de Rezende,
Guilherme Albuquerque Pinto,
Alexandre Volpim, and
Frederico Guth. (description
only so far)
 Otfried Schwarzkopf's extendible
drawing editor
Ipe

Toposcope: Automatic visualization of the topology of 2D cell complexes by
Jorge Stolfi,
Rober Marcone Rosi,
C. F. Xavier de Mendonça,
and L. P. Lozada
 Shastra, a
geometric modeling and visualization system being developed at Purdue University
(descriptions only)
 Software on the Web, from
the CNRPisa Visual Computing
Group, includes code for volume
visualization.
 ZEUS, an algorithm
animation system developed at DEC SRC (Modula3)
 Algorithms for
partitioning multidimensional data sets, collected by
Charles Alpert
 DemoKin, a
demonstration of kinetic data structures for convex hulls, closest pairs, Voronoi
diagrams, and minimum spanning trees, by
Julien Basch,
Leo Guibas,
Craig Silverstein,
and Li Zhang.
Requires LEDA,
XForms, and
OpenGL to compile;
an SGI executable is available.
 MAXRAD:
software to find the maximum radius sphere touching each point (atom) in a set
(molecule) using inversion and convex hulls, by
Todd Yeates.
(FORTRAN)