Computational Geometry
Interactive Software

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 Java-capable browser is required to run these demos, and source code is not available.

Delaunay Triangulations and Voronoi Diagrams

Enough already!!

• Delaunay triangulations and farthest point Delaunay triangulations using 3d convex hulls by Daniel Mark Abrahams-Gessel, 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.

• 2-Site 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 (non-Java) 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 applet-enhanced tutorial by Eric C. Olson

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

• Higher-order 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/Sophia-Antipolis, France. X terminal required instead of Java. Extremely slow, at least on this side of the Atlantic.

Other

• Sweep-line 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 n-gon counter

• An interactive meshing demo from Paul Chew's guaranteed-quality 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, minimum-area boundong box, and minimum-perimeter 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
  • What are convex hulls and how do you compute them?
  • A general program illustrating several sorting algorithms, several convex hull algorithms, Fortune's sweep-line algorithm for Voronoi diagrams, and more!

• Martin Hagerup's Travelling Salesman 2-OPT 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 point-line 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:
  • "Sensitivity Alanysis for the Euclidean Travelling Salesman Problem" includes movies, Java demos (with source code), VMRL files, and a PDF version of the paper.
  • Anima-LP, a 2d linear programming demo

• 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 Java-illustrated 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 Richter-Gebert 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:
  • Yet another convex hull applet by Greg Parent
  • Two (translational) polygon placement algorithms by Cristian Dima and Greg Parent
  • Daniel Scharstein and Matt Dickerson's rotation diagram demo. Unfortunately, the demo doesn't include musical accompaniment.

• 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 Richter-Gebert'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, farthest-point 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 n-1 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 frames-capable browser.

• Alex Wolff's Map Labelling Heuristics page at Freie Universität Berlin has an online demo, using either random points or real-world 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

• Alpha-shape 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.

- Jeff Papows, president of Lotus,
in his opening address at Comdex 1997,
as misquoted by The New York Times Syndicate