Fortune's Algorithm for Voronoi Diagrams
Fortune's Algorithm for Voronoi Diagrams
Given a finite set of points (called sites) in a plane, a Voronoi diagram divides the plane into regions around each site that are closer to that site than to any of the others. This Demonstration shows Fortune's algorithm for drawing Voronoi diagrams[1].
Two auxiliary curves are involved in the procedure:
1. The sweep line (green) can move up or down; only sites above it are active.
2. The beach line (red) is a sequence of parabolic arcs. Each parabola has an active site for its locus and the sweep line as directrix.
The intersections of two parabolic arcs (the breakpoints on the beach line) have equal distance to two sites (the foci of the two parabolas) and to the sweep line. Thus, as the sweep line moves down, these intersection points determine the rest of the diagram.
References
References
[1] S. Fortune, "A Sweepline Algorithm for Voronoi Diagrams," Algorithmica, 2, 1987 pp. 153–174. www.wias-berlin.de/people/si/course/files/Fortune87-SweepLine-Voronoi.pdf.
External Links
External Links
Permanent Citation
Permanent Citation
Erik Mahieu
"Fortune's Algorithm for Voronoi Diagrams"
http://demonstrations.wolfram.com/FortunesAlgorithmForVoronoiDiagrams/
Wolfram Demonstrations Project
Published: July 19, 2016