Voronoï Diagrams: Part 2— A Plane Sweep Algorithm
Now that we know a bit more about what Voronoï Diagrams are and about their specificities, let’s dive into a better way of computing them, which is a plane sweep algorithm, inspired by the work of Steven Fortune.
Plane Sweep Algorithm
A plane line sweep is a type of algorithm widely used in computational geometry. The idea behind it is to have a line that swipes the plan in one direction — vertically or horizontally— and performs an operation whenever the line encounters a point.
Applied to our Voronoi problem, we would be tempted to say something in the line of “when the line encounters a seed, we create its Voronoi region”. The issue is that when we are on a particular seed, we still have no way to know where its region starts and ends. We need to ruse a little.
Parabolas
One solution to this issue is to use parabolas. Why parabolas?
Well, parabolas are often known by their equations in the form y = ax² + bx + c, a being a constant and non-null.
But there is another way to define them. A parabola can be constructed by using a single point, named focus, and a line, named directrix. When using those two elements, the parabola consists of all the points that are equidistant from the focus and from the closest point on the directrix.
The important part here is the word “equidistant”, it will be very useful to create our Voronoï edges.
Beachline
Knowing that we can now change our approach to the sweep line algorithm. Whenever we encounter a seed, we will create a new parabola. Its focus will be the seed, and its directrix the sweep line itself. We’ll maintain in memory a list of all existing arcs, which we call the beach line.
Visually, the beachline consists in a series of adjacent parabolas, of different size, that reminds the lines drawn by the water on the beach, hence the name.
Edges construction
When you add a new parabola to the beach line, it will at first be a vertical line that will intersect with another parabola at a single point — considering that the beach line is not empty. This point is the start of a Voronoi Edge. When the sweep line continues, a parabola will be created, and grow. That parabola will intersect with another parabola. By definition, the intersection point is now equidistant from the focus points of both parabolas. The point is part of the Voronoi edge between the two focus points. As the sweep line continues and the parabolas grow, the intersection points will move, and following those points is what constructs the edges.
Finishing an edge / Closing a region
Visually, when the line moves over, we can see that at some points multiple edges will meet into one point, and one or more of the parabolic arcs will disappear completely. From that converging point, the remaining parabolic arcs will meet and start a new edge.
Potential candidates for vertex
Whenever we add a new arc, we can look for possible vertex candidates. We just have to look for the circumcenter of the newly added site and its two previous arcs, and then the circumcentre of the newly added and the two next arcs. If they exist of course. We don’t need to check the case where the newly added point is in the middle, because the created edges will be divergent.
And that is the trick. For each potential vertex, we verify if the created arcs are convergent. If it’s not the case, it means the vertex is above the beachline and already passed — considering the plane is swept from top to bottom.
Algorithm description
Now we have everything we need to describe the algorithm simply:
- Create a priority queue containing all the sites. The plane is swept from top to bottom so we want the queue to be sorted by descending y coordinates.
- While the queue is not empty
- Take the first element
- If the element is a site, add a new parabola with a focus on that point to the beach line. Then check for possible vertex, and add them to the priority queue. Create the half edges of the intersections.
- If the element is a vertex, it means an arc is disappearing. Remove it from the beach line, finish the edges relative to it, and create the new one(s) starting from it. Then check for possible vertex between the newly neighbouring arcs and add the ones to the event queue.
- When the event queue is empty, it’s done. If you need to display the graph, you’ll have to bound the diagram to be able to display the ‘infinite’ edges — the ones from the unbounded regions.
That’s it for the global idea. In a later article, we’ll discuss how to actually implement it. It is not as easy as it seems and I’m still in the process of finishing it so that article might take a bit of time before it lands, but it will come for sure.
References used to write this article:
Computational Geometry: Algorithms and Applications, by Marc van Kreveld, Mark de Berg, Mark Overmars
https://www.desmos.com/calculator For creating the images
