# Tutorial #7: Voronoi diagrams

| 8 Comments | Published on May 4, 2008Sunday is looking a little overcast, a little gloomy, and a lot like a good day to tackle a complicated tutorial: Voronoi diagrams.

I’m sure you’ve seen them before. Given a set of points, a Voronoi diagram defines a series of cells surrounding each point. Each cell contains all points that are closer to its defining point than to any other point in the set. Subsequently, the “borders” of the cells are equidistant between the defining points of adjacent cells. I’ll give you a diagram later.

I haven’t used my Voronoi class in an exciting applet yet, but it has plenty of uses… mostly functional, some aesthetic. Golan Levin did a series of portraits using Voronoi diagrams. More commonly, they’re used in mapping applications.

But first, the moment you’ve all been waiting for: The final result

And how we get there: Voronoi classes

#### More introduction

Say you have a map of your city, and on it you have located a set of points representing every fast food restaurant. Creating a Voronoi diagram from these points would enable you (on your walk through the city) to know which restaurant you’re closest to at any given time. Of course, an application that simple could be solved more efficiently via other methods, but let’s raise the stakes a bit. What if you want to know the percentage of your walk that will be closest to one particular McDonalds. Suddenly, without a Voronoi diagram, this is tricky. With a Voronoi diagram, however, it’s a simple matter of intersecting the line that represents your walk with the cell that surrounds that particular restaurant.

Voronoi diagrams can also be used to *make* maps, not just analyze them. Say you have a set of points that represent air quality sample locations. To quickly generalize the sample points into a local map… bam! Voronoi diagram!

There are other more abstract information processing uses for the diagrams as well, but I’m not going to get into them here.

#### A few more notes

- The most efficient way to create a Voronoi diagram is via Fortune’s sweepline method, which reminds me of how police departments use lines of people to do a walking search of an open area. We’re not going to use that method here. The math is less intuitive.
- The dual graph of the Voronoi diagram for a set of points is called a Delaunay triangulation. It’s a pretty great way of generating a mesh from a set of points, because it allows for an efficient non-uniform distribution of detail.
- All Voronoi cells are convex hulls, assuming that the boundary we are working within is a convex hull. This will be important.

Still alive?

Don’t worry, the code itself is pretty simple. We’ll be relying on our existing Polygon class’ split() and get_convex_hull() methods, which I’ve discussed earlier in the Building Blocks introduction to my classes.

#### Structuring the applet

Our applet will consist of 4 new classes:

- The Voronoi class coordinates the diagram.
- The Cell class holds a defining Point and all Subcells that are associated with that Point.
- The Subcell class holds a Polygon object, formed when a Cell is split into pieces. Subcells are constantly combined into one Subcell per Cell, and are the only objects that will be rendered.
- The Bisector class defines a line perpendicular to the midpoint on the line between two Points, representing all coordinates equidistant to the two Points.

#### The procedure

First, let’s review what exactly a Cell will define. The first image here shows the basics.

Every point within the blue area is closer to Point A than it is to B or C. Likewise for the other two. Points that lie on the segments between the colored areas are equidistant from the Points that define those areas.

We’ll be using a procedural approach to create our Voronoi diagram. One point at a time. The images on the left illustrate how we’d go about creating the previous example.

Start with Point A. Its initial Cell is the entire boundary of the image. Now add Point B and a Bisector between the two Points, which splits Cell A into two pieces (Subcells). We’ll get into how to determine which Subcell belongs to which Point later.

Now we’ll add Point C, along with a Bisector between A and C, and between B and C. If Bisector A-C intersects Cell A, we split Cell A along that line. Likewise for Bisector B-C.

*If the Bisector does not intersect the Cell whose Point defines it, that Cell is not affected by the insertion of the new Point.*

If it *does* intersect and we split it, we’ll now need to associate all of its pieces with either the old Cell’s defining Point, or the Point that we’re inserting.

#### Associating and consolidating Subcells

In the example below, we have a few Cells that have been affected by the addition of the new Point D (shown in grey). The issue now is that we need to match each Cell fragment (Subcell) with a Point. Here’s how we do it.

Start with all of the Subcells that have been created from an old Cell (in the example image, we start with old Cell A). Create a Segment between the centroid of each Subcell and the new Point. Create a Segment between the centroid of each Subcell and the old Cell’s defining Point. Whichever of those two Segments does *not* intersect the Bisector indicates the owner the new Subcell.

Get it? We’re testing which side of the Bisector line each Subcell falls on. We choose the centroid of the Subcell because (since each Subcell is a convex hull) we know that it will fall within the Subcell’s Polygon. The Segment connecting any internal coordinate of the Polygon and the Subcell’s owner Point should not cross the Bisector. Repeat this procedure for each old Cell that has been affected by the inserted Point.

Now we’ve got each new Subcell associated with a Point. Overall, our applet looks like this: Many Subcell fragments, correctly colored. (You can click on the applet to add new Points.)

Each Subcell belongs to the correct Point, but we have so many Polygons on the screen that it’s become a disaster in terms of visual clarity and CPU-usage. We’d rather not have any more Subcells than we need. The number of Subcells should equal the number of Cells, which is equal to the number of input Points. We only want to split one Polygon per Cell operation.

To consolidate the Subcells of a particular Cell, we combine all of the Points of all of its Subcells into an array, create a funny looking Polygon from them, then simplify that Polygon to be a convex hull, effectively removing all internal Points.

Here’s what the colored applet above looks like once we combine things: Consolidated Subcells. Much more efficient, especially with the 100 input Points shown.

Here’s the code for consolidating Subcells:

```
void consolidate(){
if(nsubcells<=1&&consolidated){ return; }
//combine all subcell points into one big array
Point[] temp1 = {};
for(int i=0;i<nsubcells;i++){
//don't forget to cast your object arrays!
Point[] temp2 = (Point[]) subset(subcells[i].boundary.points,0,subcells[i].boundary.npoints);
temp1 = (Point[]) concat(temp1,temp2);
}
//create a weird complex polygon from the points
Polygon pointset = new Polygon(temp1);
//straighten the polygon up and remove all interior points
boundary = pointset.get_convex_hull();
//empty our array of subcells
nsubcells = 0;
subcells = new Subcell[100];
//add just this new combined subcell to the array
subcells[nsubcells] = new Subcell(boundary);
subcells[nsubcells].c = this;
nsubcells++;
consolidated = true;
}
```

Pretty cool, huh?

It’s important to note that the convex hull function is fairly efficient. Much more efficient than leaving all of the Subcells unconsolidated and calculating split() operations for each.

#### My fingers, eyes, and brain are bleeding

This has been a long tutorial. And for that reason, you’ll have to make sense of the bulk of the code yourself. I hope I’ve outlined the concept behind the applet in such a way that the problem is at least approachable now. If you need more details, email me.

There’s obviously a huge need to order your operations correctly: first split the Cells, then associate them, then recombine them. You’ll see in the code that I had to do some redundant looping and temporary Cell storage to get things to work out correctly.

The only other part of the applet that deserves a mention is the hit testing between the cursor location and the diagram. That’s a simple matter of calling our is_coord_inside() method on the Polygon contained within each Subcell. And of course, that type of application is just the tip of the iceberg in terms of uses for a Voronoi diagram. Let me know if you make something exciting out of it!

#### Sunday is over, you can stop reading now

I had to take a few big breaks during the writing of this tutorial, and now that I’ve gotten back to wrapping it up, Sunday is gone. You don’t have to go home, but you can’t stay here.

Until the next drizzly day… enjoy!