Algorithm Description
The following section describes how to implement Fortune's linear sweep algorithm for computing Voronoi diagrams
Data Structures
- Arcs
- Keep a dynamic Binary Search Tree to store partial arcs. Each arc or partial arc inserted has a unique key.
- Each arc is determined by a site and a time, which is the y-value of the sweep line
- PriorityQueue
- Store site events and circle events in a priority queue
- Highest priority event has the maximum y-coordinate
- Continue sweep until queue is empty
Description
To start, add all sites to a priority queue which is sorted by maximum y-value. While the priority queue is not empty, pop an element and process it.
If it is a site event, it creates an arc to add to the wavefront. To add the arc, generate an infinitely narrow parabola. Next, update each existing parabolic arc in the wavefront using the new value of the sweep line (the y-value of the event) to compute the range of each arc. The new arc intersects an existing arc if their ranges intersect.
If the parabola for the new site intersects one of the arcs, specifically arcA, in the wavefront, start by splitting arcA into two pieces. To do this, a copy of arcA is created with a distinct key and is inserted into the BST maintaining the wavefronts. After arcA has been split, insert the arc created by the new site. Update the ranges of each of the affected arcs to reflect the newly inserted arc. Lastly, delete the circle event for the affected arcA and its neighboring arcs from the priority queue and insert the two new circle events into the priority queue. Note that circle events can only occur when three distinct sites have adjacent arcs in the wavefront.
Finding arcA to intersect
Splitting arcA into two pieces
Splicing new arc into wavefront
Original circle for arcA and its neighbors to delete from the priority queue
First new circle to add to the priority queue
Second new circle to add to the priority queue
If the event was instead a circle event, the middle arc must be deleted from the wavefront. Start by updating each arc in the wavefront according to the sweep line position. The middle arc will have a range of 0 width and the two other arcs will intersect at that same point. This is recorded as a voronoi vertex.
The first circle event is hit by the sweep line at y = -0.20. The left arc for site (5,0) is removed from the wavefront list and a Voronoi vertex is recorded at the circle center
The second circle event is hit by the sweep line at y = -0.23. The right arc for site (5, 0) is removed from the wavefront list and a Voronoi vertex is recorded at the circle center
The sweep line value is updated as each event is popped off of the priority queue. Note that the sweep line value may stay the same if multiple events occur at that y-value. The algorithm finishes when all events have been processed from the priority queue.
In Steven Fortune's code the parabolic arcs and sweep line are not actually calculated or stored. Instead at each y-value of events that are popped off of the priority queue, an edge is inserted into the edge list. This edge list contains all of the perpendicular bisectors between adjacent sites. Centers of circles, which are Voronoi vertices, define the endpoints of the line segments for the three sites that determine the circle. The set of line segments, lines, and vertices which create the Voronoi diagram are output.