-A A +A

A visual implementation of Fortune's Voronoi algorithm

Primary tabs

Collection:   AlgoViz
Source: http://algoviz.org/node/1928
Format:   application/x-java-vm

Animation of Fortune's beach front algorithm to compute the Voronoi map of a collection of points. The controls allow a user to toggle the display of circle events, the beach front, the edges in the Voronoi map, and the dual Delaunay triangulation. User can suspend, resume, play at full speed, play to next event, or step at the pixel level as the sweep line progresses. The applet defaults to a set of points on which to run the algorithm, but the user can easily clear the screen and place new points to test the behavior of the algorithm. The implementation is based on the explanation given in 'Computational Geometry: Algorithms and Applications' by de Berg, et al. (see reference link below). Excellent tool to help the user understand the nuances of what otherwise is a difficult algorithm to motivate for students. The applet page contains pointers to some material discussing the problem and the algorithm, but no formal tutorial of the material is presented. So a student using this applet would want to use another source to first familiarize themselves with the problem the algorithm solves and the essential terminology and steps of the algorithm. While the controls allow for easy control of the algorithm's progress, the user cannot 'back up'. Excellent portrayal of the beach front as a stitched-together collection of parbolic arcs that ebb and flow as a sweep line progresses from left-to-right, dragging the beach front of arcs behind it. As two arcs encompass another arc sandwiched between them, the edges in the Voronoi map are traced out.

Creator: Benny Kj'r Nielsen  Allan Odgaard  
Publisher: University of Copenhagen  
Subject:   Computational geometry  Voronoi Diagram  Delaunay Triangulation  
Language: english  
Rights: Source code in the public domain
ACM CCS 2012:
Theory of computation Human-centered computing Randomness, geometry and discrete structures Visualization Computational geometry

ylchen's picture
Submitted by ylchen on Wed, 01/05/2011 - 02:53