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
It's strange how differently Firefox (based on Gecko) and midori (based on WebKit).
(It's also annoying how all links here are followed by their hostnames, since it's completely hosed my short, hyperlinked comment.)
Re:display of canvas
samtregar on 2008-06-23T15:01:13
Huh, what does it look like? Just different or bad different? I didn't test with anything but Firefox so far. There's some extra magic to get canvas working with IE I think...-sam
Re:display of canvas
slanning on 2008-06-24T10:14:42
Click the links for firefox and midori in my previous post, those are screenshots of your demo in firefox and midori. Basically, firefox puts thin black lines between the colored regions, whereas midori (and so, I'd assume, safari) doesn't.
