Fractal treemap (random, Gosper)

Full source, including python code, here.

A more complete example of a fractal treemap (also known as jigsaw treemap) made of Gosper regions, this time representing a hierarchy. Zoom in by using the mouse wheel.

A random tree is generated with this script, obtaining a tree with 48,207 leaves (tree_48207.csv). The file contains the prefixes of all the leaf nodes, sorted in lexicographic order.

Usage (ipython):

run gosper_regions.py
gosperify('tree_48207.csv', 'hexes.wkt.csv', 'regions') # input tree, input tiling, output directory

By running the python script, the sequence of leaves is paired with the sequence of hexagons (generated by this script) that follows the Gosper space-filling curve. Because of the lexicographic order, sibling nodes are placed near to each other, similarly to classes (colors) in this other example. Different tilings can be used in theory, but that was not tested.

In order to have a representation for internal nodes, leaf nodes are recursively merged into regions representing subtrees, until the root, yielding the entire tree, is reached. This is not what the code does, actually. The same result is obtained by using each hexagon prefix (leaf prefix) to merge it to one or more regions, each one representing an internal node at a certain depth. This creates one layer for each tree level, each one having a region representing an internal node. For an in-depth explanation of this layout, see also this example, Auber et al. 2011 and Wattenberg 2005.

The layers are saved into the requested folder, each one as a separate GeoJSON file. The example tree generates eight layers. All the layers are combined into a single TopoJSON file (as in this example):

topojson --cartesian --no-quantization -p prefix -o regions.topo.json regions/0.json regions/1.json regions/2.json regions/3.json regions/4.json regions/5.json regions/6.json regions/7.json

The obtained file is finally rendered with d3.js, using a style similar to the one found in this U.S. map (land glow has been replaced with a faux shadow due to performance reasons). The labels show each region’s prefix. A zoom behavior (see this other example) is introduced to help navigating the map. To avoid cluttering the map, only the first three levels are shown. This is an issue that has to be addressed, perhaps using the zoom behavior to load fine-grained regions on demand. Also, labels are placed using the region’s centroid, giving a bad label placement in many cases.

The python script uses the shapely library for merging regions, and the Fiona library for storing the results as GeoJSON, so you have to install them if you want to run this script. The Fiona package requires GDAL 1.8+, and it was a bit tricky to install that on my Ubuntu 10:

gdal-config --version # this can be used to see if you really need to update gdal

sudo apt-add-repository ppa:ubuntugis/ubuntugis-unstable
sudo apt-get update
sudo apt-get install python-gdal
sudo apt-get install libgdal1-dev
sudo apt-get install gdal-bin
pip install Fiona

This guide covers shapely & Fiona usage.

Reading a tuple serialization was also an unexpectedly difficult task, because apparently there’s no way to do it by using the tuple constructor. The solution was, as always, using regular expressions!