http://sam.tregar.com/voronoi.cgi

I'm using this at my day job to make overlays for Google maps. So far it's been pretty great - producing very natural looking maps. (If that link is slow or broken try again in a bit - it's a CGI on a shared server with fairly low limits.)

Want to help me make it better? I tried (and failed) to write code to join polygons when mapping multiple points in a set. In a Voronoi diagram each point generates a polygon. If I color all the polygons from a set the same color I get a map that looks right, but the code would run a lot faster if I could draw just a few bigger polygons instead of hundreds of little ones.

The code I wrote (which I never released because it didn't work) walked through the set of polygons looking for common edges, combining polygons along each edge. That worked fine in early rounds, joining big polygons with small ones. The problem is that after a while you'll reach a case where a polygon needs to be joined with itself - that is, it has an internal edge. I couldn't find a way to reliably remove the internal edges (which may be long strings of multiple edges) without sometimes botching the job and killing the polygon.

Another useful note - the input polygons produced by voronoi mapping are convex, but the output usually won't be. So just computing the convex hull won't work.

Mathmonks, I call on you! The first one to turn in a working implementation gets to be a co-maintainer of the module on CPAN. Think of the glory! And the recriminations when the code doesn't compile on an ancient AIX machine! Forget that last one!

-sam