Within computational geometry, the Voronoi diagram is a relatively simple concept with a wide-range of applications. Everything from physics research to the “snap-to” feature in GUI-design uses Voronoi diagrams as a simple underlying data structure to decompose space. I have been working with Voronoi diagrams for the past few months, as my research has focused on interpolation, specifically scalable natural neighbor interpolation. Because the interpolation I have been doing (and the demo I have created) focuses on Voronoi diagrams in a plane, I will only discuss the Voronoi diagrams in 2D space. However, the mathematical concepts can be extended to higher dimensions.
If you already know all about Voronoi diagrams or simply don’t care about the math and just want to play, jump to here or go straight to my Voronoi diagram generator application.
The Voronoi Diagram
I would first like to briefly describe what precisely the Voronoi diagram is, along with how nearest neighbor and natural neighbor interpolation make use of this data structure. The Voronoi diagram is the division of plane into discrete Voronoi cells. Given a set of input points S, we would like to divide the plane such that for any given position in the plane, we know the nearest input point. This is the nearest neighbor problem. A Voronoi cell Vor(p,S) represents the region of the plane for which the given point p is the closest input point from the set of input points S. Mathematically the Voronoi cell Vor(p,S) is defined as
In the Voronoi diagram below, we color each Voronoi cell with a unique color. For the entire region covered by each cell, the input point within the cell is the closest point from the set of input points. You can also easily observe that the boundaries between neighboring cells is the set of points equidistant between two nearby input points.
Interpolation with the Voronoi Diagram
Given this understanding of the Voronoi diagram, we can easily answer a nearest neighbor query. Given a point q at position (x,y) we need only check which Voronoi cell it is within to see which input point is closest to it. Thus, if each input point also has some height z we could roughly interpolate the height of q by taking the height of its nearest neighbor.
A more complex interpolation scheme, known as natural neighbor interpolation, is to take a weighted average of all of the nearby input points. This is done by inserting the query point into the Voronoi diagram and observing how much area the Voronoi cell of the query point steals from the neighboring Voronoi cells in the original Voronoi diagram. Specifically, the fractional weight assigned to each natural neighbor is the area stolen from that nearest neighbor’s original Voronoi cell divided by the total area of the Voronoi cell of the query point. Mathematically this interpolation can be defined as:
While more complicated than nearest neighbor interpolation, natural neighbor interpolation offers a higher quality interpolation and produces smooth results.
Approximating the Voronoi Diagram in OpenGL
As explained briefly in the OpenGL Red Book, we can compute the Voronoi diagram easily in OpenGL by rendering cones at each input point and using the depth buffer to figure out the boundaries between Voronoi cells. Specifically, if we place a right angle cone with the apex at a point, the height of the cone at a given position is equal to the distance form the point in the x,y plane. As such, if we place all the cones in the plane and look at them from below, we will only see the lowest cone at any given point and thus only the cone for which the point it represents is closest. This is known as taking the lower envelope. (For more information, you can read Hoff et. al.’s paper on how this works.)
Therefore, by merely drawing the cones and placing the viewpoint appropriately within OpenGL, the framebuffer will store the Voronoi diagram. Naturally, when doing computations with OpenGL, the diagram will be discretized into pixels. Additionally, OpenGL can not draw cones, only triangles. Therefore, we approximate a cone with a f-sided pyramid. With a reasonably large value for f, we will not notice the effect of the discretization, but making f a small value like 4-10 can be interesting. Both of these discretizations of course create some deviation from the previously defined Voronoi diagram.
I have used this method, implemented in WebGL, the Javascript API to OpenGL, to create the following interactive Voronoi diagram generator.
Enough Math
While math is necessary to precisely describe these concepts, it is not always the best way to convey some of the nuances of the geometric behavior. As a result, one night, both to play with WebGL and to better understand Voronoi diagrams, I implemented some of these concepts in the browser. Below is a short screencast of me playing with the tool, which may be useful if either you don’t have a WebGL-enabled browser or you want to learn some of the features of tool; or just play with it for yourself.
On Code
Not much to say here. To make this small application, I used two canvases overlaid, one with WebGL and one with just the 2D-context. This allowed me to draw over the Voronoi diagram (such as the points). Following the learningwebgl.com tutorials, I used the Sylvester library for Matrix math as well as the glUtils library from the tutorials.
WebGL is still a little buggy and memory management can be an issue, among other things. But overall, it samples a good portion of OpenGL. Unfortunately, getting started can take a little effort. For example, unlike OpenGL in C++, you must write your own shader programs; I suggest using samples from learningwebgl.com at least to get started. However, once you have a functioning WebGL canvas, it is easy to pick up speed. I also went slightly overboard on the movement functions, but it was a good chance to play with Javascript closures.
Some cool Voronoi diagrams
And finally, here are some Voronoi diagrams I have generated that I find interesting, cool, or merely pretty.
Similar kinetic Voronoi diagram but with only 6-sided pyramids used.
Below, the same set of input points are plotted with two different types of cones. The first uses a 50-sided pyramid. The second only uses 6-sided pyramids, creating the jagged effect between neigboring Voronoi cells.
The following two Voronoi diagrams show the Voronoi cells and area stolen for a natural neighbor query.
