Voronoi Diagram / Delaunay Triangulation

You should see an interactive Voronoi Diagram / Delaunay Triangulation here.

Mouse: Click the mouse in the drawing region to add new sites to the Voronoi Diagram or Delaunay Triangulation.
Voronoi Diagram and Delaunay Triangulation radio buttons: These toggle between the Voronoi Diagram and the Delaunay Triangulation. Your current set of sites remains the same for both diagrams.
Clear button: Press this to begin a new diagram with no sites.
More Colorful checkbox: When it's checked each Voronoi region and each Delaunay triangle has a randomly chosen color. This doesn't provide any additional insight, but it looks nice.
The Show... regions: If you move the mouse over one of these regions then the corresponding information will be shown on the screen. For instance, if you move the mouse over Show Empty Circles then the empty circles for the current diagram will be displayed.

[If the applet used to work for you and has now quit working, you may want to try one of the older versions of the applet: Java 1.1 version; Java 5 version]

What is it?

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.

The Delaunay Triangulation is the geometric dual of the Voronoi Diagram. Alternately, it can be defined as a triangulation of the sites with the property that for each triangle of the triangulation, the circumcircle of that triangle is empty of all other sites.

These closely related data structures have been found to be among the most useful data structures of the field of Computational Geometry.

Additional Information

The actual data structure here is a Delaunay Triangulation. The Voronoi Diagram is built on-the-fly from the Delaunay Triangulation.

The Delaunay Triangulation is built within a large triangle whose vertices are well off-screen. That's why in the Delaunay Triangulation there are lines heading off-screen. This technique makes the code simpler since otherwise additional code would be needed to handle new sites that are outside the convex hull of the previous sites.

The algorithm: To insert a new site, we walk across the triangulation, starting from the most recently created triangle, until we find the triangle that contains the new site. This triangle and any adjacent triangles that contain this new site in their circumcircle are eliminated and the resulting empty spot is re-triangulated. The site-insertion part of this technique is commonly called the Bowyer-Watson Algorithm. The expected time to insert a new site is roughly O(n^1/2) where n is the current number of sites.

Source Code

The source code is free, but if you find the code useful I would appreciate hearing about how you are using it.

Author: Paul Chew, chew@cs.cornell.edu

Revised: March 1997 (added the Show... regions).
Revised: August 2005 (updated the code and made the source code available)
Revised: December 2007 (cleaned up code, added ability to access to each Voronoi cell, added More Colorful button)