Don Havey

Well isn’t today just the most amazing day of self-motivation ever. This is project #3 that I’ve uploaded. It must be this new Vimeo account… I’m addicted to sharing video now. Here’s the video clip: Voronoi plateau from Don Havey on Vimeo.

This quick sketch used my Voronoi diagram class to create a landscape of plateau-like structures derived from an image. The image is “chiseled” into a Voronoi diagram, then extruded according to each cell’s brightness. The diagramming process is interesting, the result is… meh. It makes high-intensity images a little more intense… but that’s about it.

On a related note, I discovered that when overlaying a number of iterations of Voronoi-diagrammed images in Photoshop with an exclusion filter, the results approach the original image in terms of resolution. Here’s an example:

Notice that the red image is washed out a bit, but is much more resolved than the others… interesting.

Anyways, here’s the source code (get your own images this time) and a demo. Click to give the applet focus, then use the arrow keys to navigate once the diagram is finished. Enjoy.

Sunday 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?

Read more…