Voronoi diagrams are fascinating geometric object with numerous applications. However, the process for their generation may be slow and complex. Fortunately, there are elegant solutions to efficiently construct these diagrams. Here is my JavaScript implementation of the Fortune’s Algorithm.

Click on the canvas to add a site

Execution time:

Intro

The Voronoi diagram1 is an important geometric object that finds applications in nearest neighbour queries, mesh generation, travelling salesman problems and many more.

Given a set of sites (points) on a plane, a Voronoi diagram is a geometric object that partitions the plane into regions around each site. Each region contains the points closer to that site than to any other. The Voronoi Edges represent the segments that are equidistant to two sites. These edges intersect at points called Voronoi vertices that are equidistant to three or more sites.

The generation of a Voronoi diagram is a nearly impossible task when using a brute-force approach but can be efficiently solved thanks to elegant algorithms.

A brilliant approach to this problem came from Steven Fortune. The so-called Fortune’s Algorithm2 uses a sweepline that moves across the plane updating the geometry only at certain specific points generating the diagram with a complexity \(O(n \log(n))\).

It’s an elegant solution to a complex problem and I will try to illustrate the main aspects below.

The algorithm

The algorithm key concept is built around the definition of parabola. Given a line named directrix and a point called focus, a parabola is the locus of points in a plane that are equidistant from both the directrix and the focus.

This chart shows a parabola and its focus in red. The horizontal line below is the directrix

From the definition follows that if two parabolas have the same directrix their intersection point is equidistant to the two focuses.

As the directrix moves across the plane the intersection points divide the plane into two regions that respectively contains all the points closer to the region’s focus.

Given two parabolas \(A\) and \(B\), defined by the focii \(f_A\) and \(f_B\) and a common directrix \(d\), the \(x\) coordinates of their intersections are given by:

\[\frac{x_{f_B}(y_{f_A}-d)-x_{f_A}(y_{f_B}-d)\pm \sqrt{(y_{f_A}-d)(y_{f_B}-d)[(x_{f_A}-x_{f_B})^2+(y_{f_A}-y_{f_B})^2]}}{y_{f_A}-y_{f_B}}\]

This chart illustrate how two intersecting parabola sharing the same directrix define a Voronoi edge. You can click on the chart to insert a new site and see how the algorithm work. Note: the new points must have decreasing y-coordinate. To reset the points press the clear button.

The Fortune’s algorithm uses a sweepline representing a directrix that moves across the plane and a complex curve called beachline composed by consecutive parabolic arcs.

The beachline evolves while the sweepline moves: when crosses a new site a new arc is added to the beachline. When an arc is squeezed between two others, it disappears and is removed from the beachline. At this point two Voronoi edges intersect in a point called Voronoi vertex.

While moving the sweepline across the plane, the algorithm only update the geometry at certain points called events. There are two types of events:

  • Point Event: represented by the focuses, is when a new parabola is added in the beachline
  • Vertex Event: the point where two edges intersect and an arc is deleted.

I will assume the sweepline moves vertically across the plane.

The events are kept in a queue and sorted by their \(y\) coordinate. At each step, the first event in the queue is extracted and executed.

The algorithm starts with an empty beach line and the list of sites The main logic is quite simple:

event _queue = list of sites sorted by y coordinate
while(event_queue is not empty)
	e <- extract smaller event from the queue
	if (e == point event) execute point event
	else execute vertex event

To understand it better is necessary to look in more detail a few elements: The beach line data structure Handling of a point event Handling of a vertex event

the BeachLine

The beachline is the structure that contains the parabolic arcs. It needs to support the operations of search, addition and deletion.
I structured it as a linked list. Each node of the list is an arc and is simply identified by the parabola focus. Each node also has a pointer to the right and left neighbour arcs and left and right edges.

Searching

The search operation is aimed at finding which arc projection on the x-axis contains a certain \(x\) coordinate. To navigate the list just start from the root that will be the leftmost arc and move right until you find the desired arc:

let p = new site
let n = beachline root;
while (n.right != null && find_parabola_intersection(n, n.right) < p.x )
{
	n = n.right;
}

The search will stop when the intersection point between the parabola \(n\) and \(n+1\) (on the right side of \(n\)) is greater than the \(x\) coordinate.

Adding an arc

Unless the beachline is empty, in which case the root is assigned, the arc \(p\) to be inserted must fall on another arc \(q\). In the insertion process, \(q\) will be split into two arcs with the same focus: \(q_l\) on the left of \(p\) and \(q_r\) on the right. It is important to carefully update the relevant left and right neighbours as well as their edges.

Deleting an arc

To delete an arc just update its left and right neighbour’s links accordingly.

Point event

A point event is handled when the sweep line reaches a new site. Here, a new parabola is inserted into the beach line. These are the steps execute on a point event:

  1. Create a new arc \(p\) with the new site as a focus;
  2. Find where this arc should be located in the beach line. This is given by the \(x\) coordinate of the site identifying an arc \(q\) as described above;
  3. Add \(p\) to the beach line as described above splitting the parabola \(q\) in \(q_l\) and \(q_r\);
  4. Delete any vertex event related to the arc \(q\);
  5. Add vertex events for \(q_l\) and \(q_r\) (described later);
  6. Create a new Voronoi edge.

Vertex Event

A vertex event take place when an arc is squeezed between two other arcs. Here, two edges intersect on a Voronoi vertex. This is sometimes called a circle event as the Voronoi vertex is the centre of a circle that passes through the focus of the shrinking arc and its left and right neighbours.

This chart illustrates the concept of "Vertex or Circle event". Note the bottom of the circle is tangent to the sweepline. This position of the sweepline is the position of the event.

The operations to handle a circle event are the following:

  1. Delete the shrinking arc p from the beachline
  2. Create a new Voronoi vertex where the two edges intersect
  3. Add a new Voronoi edge starting from vertex just added
  4. Add vertex events for the arc p.left
  5. Add vertex events for the arc p.right

Adding a vertex event

As mentioned above, a vertex event takes place where two edges intersect and an arc disappears. This point is equidistant to the three focuses of the arcs involved. From the parabola definition, this is also equal to the distance between the Voronoi vertex and the directrix (or sweepline).

If we assume the Voronoi vertex to be the centre of a circle the bottommost point of the circle is tangent to the sweepline.

These considerations suggest that the position of a Vertex event can be found adding the circle radius to the \(y\) coordinate of the intersection of the edges.

However, not every triplet of arcs generates a Vertex event. To insert a new Vertex event in the queue the event must be below the current sweepline position and the angle identified by the three focuses must be less than 180 degrees (otherwise the edges are not converging)

Other considerations

Completing the edges

Once the last event has been executed, the product of the algorithm is a collection of edges and vertices. However, some edges may not be complete. The ones still attached to the beachline will not have an endpoint but just a starting point. Other edges will have a starting point outside the drawing canvas and some other will be completely outside.

To complete the Voronoi diagram some cleanup is needed. This process depends on the structure of data used and the information produced during the execution. Based on my experience this is the trickiest part of the whole algorithm as you need to identify and manage several cases in distinct ways.

Graphics

Drawing the diagram depends on the platform and language used. I wrote the program in JavaScript and built the graphics elements in SVG. The basic SVG tags (line, circle and path) are very convenient for rendering geometric objects.

Full code

The full JavaScript code and details about the usage can be found on the github page.

Notes

  1. The Wikipedia pages about Voronoi diagram and Fortune’s Algorithm ↩

  2. Steven Fortunes paper ↩