Computational Geometry Applet 

This applet illustrates several pieces of code from Computational Geometry in C (Second Edition) by Joseph O'Rourke . The C code in the book has been translated as directly as possible into Java. Submitted: Dec 16, 1999

Delaunay triangulation 

This algorithm maintains the Delaunay triangulation of points added incrementally. Submitted: Dec 16, 1999

Slow Convex Hull and Fast Convex Hull (Wismath) 

There are many solutions to the convex hull problem. Here, two of them are implemented. The purpose is to compare the speed and techniques of each algorithm in finding the hull. Submitted: Dec 14, 1999

A visual implementation of Fortune's Voronoi algorithm 

This page briefly describes what a Voronoi diagram is and provides an interactive demonstration of how these can be created using Fortune's plainsweep algorithm. Submitted: Jun 02, 2001

Voronoi Diagram /Delaunay triangulation demo (Chew) 

The Voronoi diagram has the property that for each site (clicked with the mouse) every point in the region around that site is closer to that site than to any of the other sites. This applet illustrates it. Submitted: Dec 14, 1999

Minimal Enclosing Circle 

The minimal enclosing circle problem (also known as the smallest enclosing circle or mininum spanning circle problem) is this: given a set of points on the plane, find the smallest circle which encloses all of them. This applet allows you to experiment with the minimal enclosing circle algorithm. Submitted: Dec 16, 1999

Jarvis convex hull demo 

The Jarvis march is one of the nicest to animate since it proceeds by wrapping a string around the point set. Running time is O(nh) if the input size is n and output size is h. See R. A. Jarvis, "On the identification of the convex hull of a finite set of points in the plane" Inform. Process. Lett., 2, 1973, 1821 (Graham & Yao's algorithm is faster, and easy if you have a sort routine). Submitted: Dec 16, 1999

Delaunay triangulation 

This applet shows the crust and the anticrust that can be obtained from the Voronoi diagram/Delaunay triangulation of a set of points. Submitted: Dec 16, 1999

GrahamScan Convex Hull (Zupancic) 

Here's a demonstration of Graham's scan. It finds the convex hull of 30 points randomly positioned on the plane. Submitted: Dec 14, 1999

The Geometry Applet 

"This geometry applet is being used to illustrate Euclid's Elements. Above you see an icosahedron, that is, a regular 20sided solid, constructed according to Euclid's construction in proposition XIII.16. Another example using this Geometry Applet illustrates the Euler line of a triangle. Here's how you can manipulate the figure that appears above. If you click on a point in the figure, you can usually move it in some way. A free point *, usually colored red, can be freely dragged about, and as they move, the rest of the diagram (except the other free points) will adjust appropriately..." Source files are available on the page. Submitted: Dec 16, 1999

Quickhull convex hull demo 

This applet illustrates the divide & conquer algorithm, that is the analogue of Quicksort for sorting. Submitted: Dec 16, 1999

Terrain Reconstruction Demo 

This applet shows a TIN terrain model in Java. Submitted: Dec 16, 1999

GrahamYao convex hull demo 

Graham and Yao's algorithm maintains the convex hull incrementally in two stacks (or a double ended queue) as points are added in order of sorted xcoordinates. In this version we use Quicksort to sort coordinates. You can compare with another version using insertion sort (Or go on to compare with Quickhull). Submitted: Dec 16, 1999

Visibility polygon test 

This is an algorithm for computing the visibility polygon from a point. Submitted: Dec 16, 1999

ChanDC convex hull demo 

Chan's divide, prune, & conquer algorithm is like Quickhull, but an extra pruning step makes it optimal and output sensitiverunning in O(n log h) in the worst case. See T. M. Chan and J. Snoeyink and C. K. Yap, "Primal dividing and dual pruning: Outputsensitive construction of 4d polytopes and 3d {Voronoi} diagrams," Discrete Comput. Geom., 18, 1997, p. 433454. Submitted: Dec 16, 1999

MWT Demo 

In this demo, you enter a vertices of a SIMPLE polygon in CCW order and click update to compute a minimum weight triangulation. Submitted: Dec 16, 1999

LineTesting convex hull demo 

This algorithm simply tests whether each oriented line defined by a pair of points has all the other points to one side. Submitted: Dec 16, 1999

The NinePoint Circle 

For any triangle, a circle can be constructed passing through nine special points: the midpoints of the three sides (yellow) the feet of the altitudes (purple) the midpoints of each segment from a vertex to the orthocenter (orange) (An altitude extends from a vertex to the opposite side, and is perpendicular to that side. It intersects the opposite side at its foot. The orthocenter is the intersection of the altitudes.) The following illustration shows the NinePoint circle. Try dragging the triangle's vertices (if your mouse has more than one button, use the left one). Source code is available on the page. Submitted: Dec 16, 1999

Minimum Convex Decomposition Demo 

In this demo, you enter the vertices of a SIMPLE polygon in CCW order and after clicking Update, a decomposition by diagonals into a minimum number of convex pieces is shown. Submitted: Dec 16, 1999

Euler's Line 

This illustration shows Euler's theorem. Euler's line appears red. Try dragging the triangle's vertices with the mouse (if your mouse has more than one button, use the left one). As the three points move, they remain colinear. Submitted: Dec 16, 1999

Tripod Demo 

This demo in progress shows a data structure for triangulations that was suggested by Martin Heller, ETH Zurich. It stores exactly 3 edges per point and 2 pointers per edge, yet supports all the standard operations. Submitted: Dec 16, 1999

Morley's Theorem 

The following illustration shows Morley's triangle in green. Try dragging the large triangle's red vertices with the mouse. Submitted: Dec 16, 1999

Polyominoids counter 

The polyominoids are figures made from the faces of cubes. They are generalizations of polyominoes, or figures made from squares. This applet counts polyominoids and show them. Java sources included. Submitted: Nov 11, 2001

MaxRDepth Demo 

This applet, by Bettina Speckmann, implements a binary search algorithm that runs in O(n log^2 n) to compute the point of maximum depth. Submitted: Dec 16, 1999

