Prof. Dr. Jay Martin Anderson
Professor Emeritus of Computer Science, Franklin & Marshall College
  • home
  • Development
    • Gallery
    • Stop and Pray
    • Stations at St. Thomas
    • PricePer
    • What's It Cost?
    • my own
    • at F&M
    • for clients
  • Small Gallery
  • LVC
  • Visualization
    • Algorithm Visualization >
      • Binary Space Partition
      • Convex Hull >
        • Extreme Point algorithm
        • Extreme Edge algorithm
        • "Gift Wrap" algorithm
        • Incremental algorithm
        • Incremental algorithm in three dimensions
        • "QuickHull" algorithm
      • Delaunay triangulation >
        • Incremental algorithm
        • from the Voronoi diagram
      • Line intersection >
        • a "brute force" algorithm
        • Sweepline algorithm
      • Motion planning
      • Point-in-Polygon >
        • Plumbline algorithm
        • Trapezoidal Map
        • Winding Number
      • Polygon triangulation >
        • "Art Gallery" Problem
        • Recursive algorithm
        • Make Monotone Polygons
        • Triangulate a Monotone Polygon
      • Voronoi diagram >
        • Fortune's algorithm
        • Intersection of Half-Planes
        • Quadtree algorithm
    • Data Visualization
  • OpenGL
    • OpenGL for Apple Software Developers
  • iBooks
  • about me
    • contact
Delaunay Triangulation:  an Incremental Algorithm
Picture
The Delaunay triangulation of a set of points in the plane divides the plane into a number of triangles, plus one open figure.  The set of triangles is the "best" in the sense that:

  • one couldn't add another triangle without going out of the plane

  • the triangles maximize their smallest angle; that is, the triangles avoid being long and skinny.

The Delaunay triangulation leaves on open figure, which is the inverse of the convex hull.  That is, the outermost edges of the triangles form the convex hull of the points.

The Delaunay triangulation is also the dual of the Voronoi diagram of these points.  An edge of the triangulation maps to an edge of the diagram; a triangle maps to a Voronoi vertex; a vertex of the triangulation maps to a Voronoi cell. 

The incremental algorithm begins by surrounding the point set by one huge triangle.  One by one (aribtrarily), a point is connected to the triangle which surrounds it.  Once a point is connected to its surrounding triangle, the triangles are adjusted to be "not skinny," or "legal."  Once all points have been connected, the lines which connect the points to the original huge triangle are removed; the figure that remains is the Delaunay triangulation.

Two kinds of movies are available.  In the first kind of movie, you will briefly see the huge surrounding triangle, and then zoom in on the pointset and the triangulation.  At the end of this kind of movie, you will briefly see the huge surrounding triangle removed.  In the second kind of movie, you will see two images in parallel:  the image zoomed in on the point set and triangulation, and the image zoomed out to see the huge surrounding triangle.

Click on the Download button at the right to download a zipped file of the first kind of movies (described above).
download
The second kind of movie, in which one sees both the enclosing triangle and the incremental triangulation side by side, is shown at the left.

Click on the Download button at the right to download a zipped file of movies of the second kind.
download
Proudly powered by Weebly