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.

The goal of the page is to give you an intuitive understanding of how Fortune's algorithm works and how Voronoi diagrams look, so if you have never heard of these diagrams we suggest that you follow some of the links given to get a better understanding of the theoretical aspects of Voronoi diagrams.

What is a Voronoi diagram?

Example of a Voronoi diagramImagine you have a map over a city with n cell phone masts. A cell phone always connects to the closest mast, so you'd like to split up the city in zones, where each zone has exactly one cell phone mast and each location inside such a zone is closest to the cell phone mast found in the same zone.

The result of such a partitioning is often referred to as a Voronoi diagram and can be created in O(n log n) time by various algorithms. This is also a lower limit.

Using a Voronoi diagram

In the above example we have transformed the problem of finding the closest mast to the problem of finding the zone in which we are located (also known as the point location problem). This can be determined in logarithmic time instead of the linear time, which would be required for finding the nearest mast if no preprocessing was done. Naturally you'll need to query the Voronoi diagram more than once to make up for this preprocessing time.

Though given a Voronoi diagram we can solve a lot of other geometrical problems such as convex hull and Delaunay triangulation.

The source

The source is available as a gzip'ed tar archive (5.5 Kb).

The applet

How to use it

You control the program with your mouse. At any time you can click on the right side of the sweep-line to add a point. Below follows an explanation of the various buttons and checkboxes.

Halt the incremental movement of the sweep-line.
Continue the incremental movement.
Next event
Move the sweep-line to the next event point, including circle event points.
Next pixel
Move sweep-line a single pixel.
Clear the canvas.
Move the sweep-line to the extreme left and restart tracing of the Voronoi diagram.
Enable/disable drawing of circle event points.
Enable/disable the beachline.
Voronoi diagram
Enable/disable tracing of the Voronoi diagram.
Delaunay triangulation
Enable/disable Delaunay triangulation.

Interesting point configurations

If you draw a perfect circle of points all the zones should meet in the center of this circle. Now try to spoil this feature by adding a point in the middle of the circle. Even if you didn't succeed in making the circle perfect then try it anyway.