Portal: Algorithm Visualization in Computational Geometry

with QuickTime® Movies

This page serves as a portal to the results of nearly five years of development of QuickTime® Movies to illustrate algorithms from computational geometry.

The suite of algorithms illustrated in this way now includes nearly 1.6 Gb and over 150 QuickTime movies.  You are free to play the movies and to download them one-at-a-time and save them (with attribution, and not-for-profit, please).  The movies will download into the QuickTime player, and you may select "Save as ..." from the File menu.  

QuickTime version 6 or better is required.  You can download that free from Apple.

You may also write for a CD or DVD containing all the movies (for the cost of the media plus postage).

Use

Please be aware that some movies are quite large, and download times may be long, especially over slower internet connections.  

Each movie is marked with its size in Mb.  Movies that are marked "with questions" pause at important steps in the algorithm to pose a question to the student or viewer. The viewer may then press the "play" button on the QuickTime player to resume the movie.  

There is more than one movie for most algorithms. Usually the movies show the algorithm running against a randomly chosen dataset of some number of elements. Movies with the same number of elements (but differently placed) should run in about the same time; counts of important information (for example, how many comparisons) are shown in the text track.  Movies with different numbers of elements should give the viewer a good idea of the order of the algorithm. If, for example, the number of operations quadruples when the number of elements doubles, one could conclude that the algorithm is quadratic order O (N²)).

The usual disclaimers apply:  I don't guarantee that the movie is a correct animation of the algorithm, or that it will play, or that it will be useful to you for your purposes.

Sample Code: Lorenz attractor

Sample code is available at this site also: the sample makes movies of the Lorenz attractor.  During the course of this project, programs developed in C, C++, Java, and Objective-C have been used to generate movies.  The latest implementation (Objective-C, Xcode, OpenGL, QuickTime) is available for download.  The same disclaimers apply:  I don't guarantee that the code is a correct implementation of an algorithm, or that it will compile and execute correctly, or that it will be suitable to your purposes, or that I will be able to help you modify it for your purposes.  The sample code can be downloaded freely; we ask that you acknowledge F&M as well as Apple Computer if you use this code for your own purposes.

Some movies of the Lorenz attractor are also available on the sample code page.

 

Computational Geometry

This website is not intended to be a tutorial in computational geometry.  The subject matter can be found in two excellent texts:  Computational Geometry: Algorithms and Applications by deBerg et al. (Springer, 2002), and Computational Geometry in C by O'Rourke (Cambridge, 1994).  I have found or adopted all of my algorithms from these sources.  This website and the QuickTime movies found here are intended to be used in conjunction with these or other textbooks, and not to substitute for either.

 

The Suite:  Problems and Algorithms

• Convex Hull

  • extreme point algorithm
  • extreme edge algorithm
  • gift wrap algorithm
  • "QuickHull" algorithm
  • an incremental algorithm
• Convex Hull in three dimensions
  • an incremental algorithm

•  Delaunay Triangulation

  • from the Voronoi diagram

  • an incremental algorithm

• Line Intersection

  • a brute force algorithm

  • a sweepline algorithm

• Motion Planning:  Any path, shortest path.

• Point in Polygon

  • plumbline algorithm

  • trapezoidal map algorithm

  • winding number algorithm

• Polygon Triangulation

  • recursive algorithm:  the "art gallery" problem

  • recursive algorithm, without the "art gallery"

  • triangulation of a monotone polygon

  • decomposing a polygon into monotone polygons

• Range Tree and Searching

  • constructing and searching in a one-dimensional range tree

  • constructing a two-dimensional range tree

  • constructing a two-dimensional search tree (kd-tree)

• Voronoi diagram

  • half-plane algorithm

  • Fortune's algorithm

  • A quadtree algorithm

• Space-partitioning algorithms

  • A quadtree algorithm for the Voronoi diagram

  • The painter's algorithm

  • Binary space partitioning tree