A visual implementation of Fortune's Voronoi algorithm

by Allan Odgaard & Benny Kjær Nielsen

"I found the animation very entertaining"
- Steven Fortune

Introduction

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.

A starting point might be Voronoi.com, which features a lot of Voronoi related stuff.

The applet located on this page was created in context with the course "Computational Geometry" held by Pawel Winter during the spring of 2000 at the department of computer science at the university of Copenhagen (DIKU).

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.

Implementation details

Our implementation is based on the explanation given in the book entitled Computational Geometry: Algorithms and Applications.

An online explanation of the details in Fortune's algorithm is carefully described by Èuk Roman and can be found at his page.

It should be emphasized that our implementation does not run in O(n log n). We only wanted to visualize the algorithm and all structures have been made as simple as possible to avoid unneccessary complexity. A non-visual implementation, done in C, can be found at this page.

The source

The source is available at GitHub. Unfortunately we managed to delete the source, but thanks to Jad (a JAVA decompiler) we were able to get it back, but all comments and local variable names were lost. Furthermore this has resulted in a not 100% strict coding style, since most of it was produced by Jad. This is also our first program made in Java.

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.

ButtonsCheckboxes
Suspend
Halt the incremental movement of the sweep-line.
Resume
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
Clear the canvas.
Restart
Move the sweep-line to the extreme left and restart tracing of the Voronoi diagram.
Circles
Enable/disable drawing of circle event points.
Beachline
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.



Other applets



Webmaster - Created: May 2, 2000