Implementation of Fortune's Algorithm in Processing
Branch: master
Clone or download
Latest commit f8ffe86 Mar 29, 2017
Type Name Latest commit message Commit time
Failed to load latest commit information.
FortuneAlgorithm Initial Commit Mar 29, 2017
LICENSE Initial commit Mar 29, 2017 Update Mar 29, 2017


This is an implementation of Fortune's sweep line algorithm in Processing. Fortune's Algorithm is used to generate the Voronoi Diagram of a set of points in the 2D plane. The Voronoi Diagram is partioning the plane into regions based on the distance between the input points. The lines of the Voronoi Diagram correspond to the bisectors between two points and each point on the line has the same distance to these both points. The Voronoi Diagram is highly useful for a number of applications, such as the Nearest Neighbor Search, finding the maximum empty circle within a set of points, Vector Quantization and additionally the Voronoi Diagram is dual to the Delaunay Triangulation.

The animation illustrates the steps involved in the algorithm. The implementation is based on the explanation of Ivan Kuckir which was very helpful for the understanding and implementation of the algorithm. This implementation does not deal with many degenerate cases, which can cause problems for large set of input points.