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 sub-categories. (Eventually, each category will get its own separate web page.) Each program is listed only once, but I've provided cross-links 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:
Low-dimensional convex hulls
Arbitrary-dimensional 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
- Primal-dual methods for vertex and facet enumeration by David Bremner, Komei Fukuda, and Ambros Marzetta
- Hull: Arbitrary-dimensional 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 vertex-facet 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:31-50 (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 Jean-Daniel Boissonnat, Olivier Devillers, Stefan Meiser, and Monique Teillaud, from the PRISME project at INRIA Sophia-Antipolis.
- 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 Sophia-Antipolis. (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 divide-and-conquer 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 3-space or periodic Voronoi diagrams in the 3-torus.
- 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 two-dimensional point sets.
- Software on the Web, from the CNR-Pisa 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 "snap-rounded" 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 self-intersecting, possibly multiply-connected 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 linear-size nonobtuse triangulations of polygons, using the circle-packing 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 guaranteed-quality meshes.
- QMG: mesh generation and related software by Steven Vavasis
- The Chopper, a semi-automatic 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 "hand-drawing" mathematical objects, by Nina Amenta, Danek Duvall, and Tim Rowley
- Javier Elices's GeomView module for visualizing the Dobkin-Kirkpatrick 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 high-dimensional polytopes through their cross-sections 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 Richter-Gebert, 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 high-dimensional 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 CNR-Pisa Visual Computing Group, includes code for volume visualization.
- ZEUS, an algorithm animation system developed at DEC SRC (Modula-3)
<!--------------------------------------------------------------------------------------->
- Algorithms for partitioning multi-dimensional 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)