Home > Java > Computational geometry

Computational geometry

Related Categories

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 plain-sweep 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, 18--21 (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 anti-crust 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 20-sided 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 x-coordinates. 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 sensitive---running 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: Output-sensitive construction of 4-d polytopes and 3-d {Voronoi} diagrams," Discrete Comput. Geom., 18, 1997, p. 433--454.
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 Nine-Point 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 Nine-Point 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



  Privacy - Trademarks - Feedback - Terms of Use Copyright The MathWorks, Inc.