Up: Directory of Computational Software
Planar libraries and environments
XYZGeobench
Library of 2-D algorithms with animation, in
ObjectPascal for the MAC. Algorithms include:
- Convex hull of a simple polyline (linear time algorithm)
- Tangents common to two convex polygons
- Contour of a set of rectangles
- Closest pair of line segments (sweep line)
- Euclidean minimum spanning tree (EMST)
- Traveling salesman heuristics (nearest neighbor, EMST, convex hull,
tour optimizer)
- Exact solution to the traveling salesman problem
- Quad-tree operations (creation, boolean operations)
- Test whether an arbitrary polygon is convex
- On line closest pair
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.
geolab
A library of 2-D geometric algorithms and data
structures, with a visualization environment. In C++
for SUN/OS (dynamic linking requires the SUN C++
compiler for the whole package,
but you might be able to hack out and adapt the code for a particular problem).
Over 40 algorithms, including all the computational geometry classics
plus some other interesting things like:
- Farthest point Voronoi diagram
- Nearest neighbors
- Ray shooting
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.
Workbench for computational geometry
An implementation and visualization environment, in Smalltalk
for the Macintosh. Includes implementations of many planar algorithms.
The manual is in Microsoft Word.
By Peter Epstein, J. Kavanagh, A. Knight, J. May, T. Nguyen,
and Jörg-Rüdiger Sack.
You can take a look at the Info file in the
ftp directory.
Center for Digital Algorithms
This commercial endeavor has developed a library of about
a hundred subroutines for planar computational geometry,
and a data structure library.
Includes demos and a workbench for Windows 95.
They're asking for alpha test sites, so it's free for now.
They also have a graph theory library and workbench.
For a list of functions and some screen shots of the demos,
see the CDA homepage.
Up: Directory of Computational Software
![[HOME]](/pix/home.gif)
The Geometry Center Home Page
Comments to: nina@geom.umn.edu