How can I make voronoi treemaps?

Answer 1

Math::Geometry::Voronoi

Answer 2

James Tauber is writing a tutorial that uses JavaScript and Fortune's algorithm to draw a Voronoi diagram in a canvas element: Voronoi Canvas Tutorial

It's not complete yet (he's at part 3 of 4) but there's enough there to complete it I think.

Answer 3

Nice demos and graphics for Python: http://home.scarlet.be/zoetrope/voronoi/

Answer 4

Just found this page. I've been working on a Voronoi demo applet using Javascript/canvas, after translating into Javascript a C# version of Steven Fortune's algorithm by Benjamin Dittes (available at Code Project, see "Fortune's Voronoi algorithm implemented in C#"). Here is the page which include Fortune's Voronoi algorithm in Javascript: http://www.raymondhill.net/voronoi/voronoi.php This is a first iteration, I plan to adapt it further to be better suited to Javascript. Hope this helps.

Answer 5

the other Python answer seems to point at a raster only solution. I am also interested in solving this problem (in Python) and I think the following script could form a usable starting point:

http://www.oxfish.com/python/voronoi.py

Answer 6

First of all, the lines are not strange: it's the result of the fact that this is not a normal Voronoi tessellation, but an area-weighted Voronoi (AWT) tessellation, possibly even a centroidal Voronoi tessellation (CVT). That being said, in order to have Voronoi regions (polygons) with significantly differing areas (which would reflect some attribute of the data), you need AWTs (preferably implemented as CVTs to retain nice aspect ratios for the polygons); a normal Voronoi algorithm (as suggested by some people above) will not be able to help you. There is probably no direct solution for this available, especially not for scripted languages, since the computational complexity due to iterative updating steps for AWTs is quite high. You should look up the work on "Voronoi Treemaps" and "Dynamic Voronoi Treemaps" by Balzer et al. and Sud et al. to get an idea of the algorithm and then implement it on your own (everything that you need is in their papers).