Monday, February 23, 2009

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 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 [NEW!] have been recently added or modified.

Robust low-level primitives

Avoid roundoff and precision errors! Use this code instead of naïve floating point or integer arithmetic.

Combinatorics and discrete math

Geometric optimization

Convex hulls and convex polyhedra

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
Measure properties
Boolean operations on polyhedra
Interesting and/or pathological polytope data

Voronoi diagrams and Delaunay triangulations

See also the implementation page from Christopher Gold's site
Relevant pages from DCGS:
Voronoi diagrams and Delaunay triangulations of points
Many convex hull programs can also compute Voronoi diagrams and 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

Operations on polygons

Relevant pages from DCGS:
Point location
Boolean operations
Triangulation and quadrangulation
See also the sections on Voronoi diagrams and Delaunay triangulations and mesh generation and manipulation.

Mesh generation and manipulation

See also the sections on Delaunay triangulations and geometric modeling.

Geometric modeling

See also the section on mesh generation and manipulation.
Relevant pages from DCGS:
Binary space partition trees
Collision detection

Visibility computation

Visualization tools

You should also look for the thing being visualized! See also my list of programs that can be run over the web.



No comments:

Post a Comment