use Perl

I've been working with generating overlays for google maps lately at my day job. Without going into too much detail, the data set I need to display is a set of points, each assigned to a given set. In the real world these sets form contiguous regions which I need to translate into shapes to draw over the map. The rub is that these regions come in really complex shapes - drawing convex hulls isn't an option.

My first attempt at the problem once I realized I couldn't draw a hull was to divide the world into a grid and color each box according to what I found inside, subdividing until each box contained only a single set's point(s). The results were blocky (duh) and not all that appealing. But as long as the data was dense enough (i.e. urban areas) it did a decent job of expressing the shapes. Unfortunately in rural areas where points are more spread out it looked terrible.

For my second attempt I decided to actually learn some computational geometry - I read a book and quite a few sites around the web. This lead me to Voronoi diagrams. There's a wide variety of Voronoi diagram producing code out there on the web - everything from highly-templated C++ monsters to Java to some excellent 20-year old C code. I chose the latter of course (Perl and old-school C go together like chocolate and peanut butter), and after some serious debugging I give you Math::Geometry::Voronoi.

You can see a demo of it in action here: http://sam.tregar.com/voronoi.cgi. This is essentially what I'm doing with Google maps, except that I'm coloring multiple regions the same color and drawing a line around the border rather than each cell.

The speed of the diagramming code is really good. Don't let the demo fool you - that code is running in CGI mode on a shared server. Put it on a fast mod_perl server and it's definitely not going to be the bottleneck in a mapping application. That prize goes to Google Maps. Sweet app, but it sure is slow!

-sam