Computational Geometry
Interactive Software
This page lists geometric programs that can be run intractively over the Internet,
primarily (but not exclusively) Java applets.
Alon Efrat maintains a similar page of
Javaanimated algorithm demos.
If you're looking for downloadable software, see Nina Amenta's
Directory of Computational Geometry
Software at the Geometry Center or my own pages of software
libraries and individual programs.
Items marked are recommended.
Items marked have been recently added or
modified.
Unless otherwise specified, a Javacapable browser is required to run these demos, and
source code is not available.
See also the implementation page
from Christopher Gold's site www.Voronoi.com.
Enough already!!

Delaunay
triangulations and farthest point Delaunay triangulations using 3d convex
hulls by Daniel Mark
AbrahamsGessel, fortunately stolen by
Anirudh Modi before the original
page was taken off the Web. This is the best one!
 Convex hulls,
Delaunay triangulations, Voronoi diagrams, and proximity graphs
by James E. Baker, Isabel F. Cruz, Luis D. Lejter, Giuseppe Liotta, and
Roberto Tamassia.
Source
code is available.

Incremental Delaunay triangulations and Voronoi diagrams
by Frank Bossen

Voronoi Diagram/Delaunay Triangulation by
Paul
Chew uses a randomized incremental algorithm with "brute force" point
location.

2Site Voronoi diagrams by
Matt Dickerson, from the
Middlebury College
Undergraduate Research Project in Computational Geometry

The convex
hull/Voronoi diagram applet from
the GeomNet project
provides a secure Java wrapper for existing (nonJava) code.
The applet calls qhull to
build its convex hulls and
Steve Fortune's
sweep2 to
build its Voronoi diagrams.
A forms interface to
the same programs is also available.

VoroGlide, by Christian
Icking, Rolf Klein, Peter Köllner, and Lihong Ma. Smoothly maintains the
convex hull, Voronoi diagram, and Delaunay triangulation as points are moved,
illustrates incremental construction of the Delaunay triangulation, and includes a
recorded demo. Now on a faster server!

Delaunay triangulations by Geoff Leach compares several (very)
naïve algorithms.
Source code is available.

Bisectors and
Voronoi diagrams under
convex
(polygonal) distance functions by
Lihong Ma.
The diagram is updated on the fly while sites or vertices of the unit ball
are inserted, deleted, or dragged around. Very cool!
 Delaunay
triangulations and Dirichlet tesselations and a short appletenhanced
tutorial by Eric C. Olson

The Voronoi Game by Dennis Shasha. Try to place points to maximize the area
of your Voronoi regions.

Higherorder Voronoi diagrams by
Barry Schaudt
 Tessy, yet
another interactive Voronoi/Delaunay demo from
Keith Voegele. Java
not required.

ModeMap, by David
Watson, draws Voronoi diagrams, Delaunay triangulations, natural neighbor circles
(circumcircles of Delaunay triangles), and (for the very patient) radial density
contours on the sphere. Don't give it more than 80 points.

Delaunay Triangulation from
Zhiyuan
Zhao's
JAVA Gallery of Geometric Algorithms

Delaunay Triangulation Demo at ESSI, Université de
Nice/SophiaAntipolis, France. X terminal required instead of Java.
Extremely slow, at least on this side of the Atlantic.
Maybe it's time to break this up.
 Sweepline
algorithm to count line segment intersections by K. C. Baltz, with
source
code
 Steven F. Bellenot shows us
how to cut a log. (This
was the first "geometric" applet I saw.)

Interactive point set quadrangulation by
Martin Blais, from his class
project
"Characterizing and Efficiently Computing Quadrangulations of
Planar Point Sets"
 Paul Burchard's
Geometry Toolbox
 Heidi Burgiel and Michele Raymond's
simple ngon counter
 An interactive
meshing demo from
Paul Chew's
guaranteedquality mesh generation page. Access is sporadic. Java not
required.
 Pat "SeeHandSki" Cichanski's implementation of the
Graham's scan
2d convex hull algorithm. (Disable Java and JavaScript before visiting
his home page!)

Nir Efrat demonstrates
five applications of rotating calipers: diameter, "weak diameters", width,
minimumarea boundong box, and minimumperimeter bounding box.
Source code is available.

Motorcycle graphs by
David Eppstein
 Joe Ganley's
Euclidean minimum
spanning tree applet, with
source code.
 Sorting
algorithms demo by James Gosling, Jason Harrison, and Jim Boritz

Algorithm
animations by Alejo Hausner
 Martin Hagerup's
Travelling Salesman 2OPT Heuristic for Dummies.
Source
code is available.
 Nicole Heckenkemper's
STIP: Search Target in Polygon, a simulation of a robot searching for an
unknown target in an unknown polygonal environment. (May require the JDK 1.1
appletviewer.)
 Fred Henle's
pointline duality demo illustrates three different duality maps.

2d convex hulls and
3d
clustering by Dorit
Hochbaum, from the
RIOT project at Berkeley.
 A demonstraction of
the piano
mover's problem by Lei Jin
 Interactive demos by
Chris Jones:

David Joyce's
Geometry
applet lets you set up simple geometric objects (points, lines, polygons, and
circles) and constraints (such as incidence, colinearity, cocircularity, and
parallelism), and then observe the effects as you move the objects around. Used
in his Javaillustrated version of
Euclid's Elements.
Now in 3d!
 Demo version
of Cinderellas Café, a "dynamic
geometry" Java program written by Ulrich Kortenkamp and Jürgen
RichterGebert that 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! Information is
currently available in German only.

Demonstration of several old and new
settlement selection algorithms by
Marc van Kreveld,
René van Oostrum,
and Jack Snoeyink.

Realizing a Delaunay
Triangulation by Tim
Lambert is the exact opposite of a Delaunay triangulator. The user inputs a
triangulation of a convex polygon, and it finds a set of points whose Delaunay
triangulation is combinatorially equivalent to the given one!

Paton Lewis's excellent
BSP tree demo
 Erez Lirov's applet for generating not quite optimal
travelling salesman
tours
 More applets from the
Middlebury College
Undergraduate Research Project in Computational Geometry:
 Pat Morin's
sorting algorithm demo.
Source code is available. Not for use in hazardous environments.
 Connie Peng's implementation of
Graham's scan (the first 2d convex hull algorithm), with
source code. Don't give it duplicate points!
 Michael J. Radwin's
Java projects, including a
demonstration of
priority search trees
 Jürgen RichterGebert's
homepage illustrates an
interesting
oriented matroid using David Joyce's
Geometry
applet. Check out the document source!
 Tim Rowley's applet to compute
the minimum enclosing
circle, convex hull, farthestpoint Voronoi diagram, and diameter of a set of
points in the plane.
 «Une exercise de
géométrie algorithmique», un programme qui
calcule l'envelloppe inferieure d'un liste de segments, avec
les sources par
Olivier Seguin (en français)

Several cool Java demos
by Jack Snoeyink.
 Jeff So's
2d convex hull applet
compares quickhull to brute force.
Source code is
available.
 Clustering by use of minimum
spanning trees by Mike Soss
 A cluster of
stars by Ileana Strienu
 John Sullivan's
stereographic projection demo
 J. Suwanparisut's applet for
determining an inducing path of length n1 in an arrangement of n
lines, based on an algorithm of
Jit Bose, Hazel Everett, and Steven
Wismath

Student projects from Godfreid Toussaint's Fall 1997 computational geometry
class. There's lots of really cool stuff here! Source is available
for most projects; a few projects require a framescapable browser.

Alex Wolff's
Map Labelling Heuristics page at Freie Universität Berlin has an online
demo, using either random points or
realworld data, and
pointers to several
relevant papers. Java not required.
 Zhiyuan Zhao's
JAVA Gallery of Geometric Algorithms
 The Geometry Center's Java Gallery of
Interactive Geometry

Alphashape demo from
NCSA. Requires VRML.
Source code is available.
Java is our last and best hope of making software you write once and runs anywhere.
If we screw this up, we are all enormous losers.