block by nitaku 8272715

Fractal treemap of Konanopii (1,724 leaves)

Full Screen

See this gist for the full code.

An example of an unambiguous fractal treemap. See this example discussing the unambiguous representation of unordered trees, and also this other example from which the random tree Konanopii (1,724 leaves) has been taken from.

ipython
run gosper_regions_depth.py
gosperify('konanopii_1724.json','/data/_workspace/hexes.wkt.csv','regions','depth.json')
Ctrl+D

topojson --cartesian --no-quantization -p depth -p label -o regions_depth.topo.json depth.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

gosper_regions_depth.py produces both the treemap’s regions and depth levels as GeoJSON (then converted into TopoJSON as usual). A python generator is used to enumerate the leaves without creating a copy of them (similar to the code found in this StackOverflow question).

Only the first two levels are shown, to avoid cluttering. Labels are naively placed at the centroid of the corresponding region, leading to unoptimal placement in many cases (e.g. “Sebo”).

The color scale, supporting trees with a maximum of ten levels, is adapted from Gretchen N. Peterson’s Cartographer’s Toolkit (page 40 - the scale have been reversed and blended with white). The font is Lacuna, by Peter Hoffmann, and was chosen because of its good readability at small sizes.

The halo around labels is implemented with a SASS mixin that defines multiple text-shadows. White blending leverages the possibility of leaving the hue of white undefined in d3’s HCL representation, producing a correct HCL interpolation (see this discussion for more info).

index.js

(function() {
  var concat;

  concat = function(a) {
    return a.reduce((function(a, o) {
      return a.concat(o);
    }), []);
  };

  window.main = function() {
    /* "globals"
    */
    var categories, colorify, container, dx, dy, height, legend, path_generator, radius, scale, svg, vis, whiten, whiteness, width, _i, _ref, _ref2, _results;
    vis = null;
    width = 960;
    height = 500;
    svg = d3.select('body').append('svg').attr('width', width).attr('height', height);
    /* ZOOM and PAN
    */
    /* create container elements
    */
    container = svg.append('g').attr('transform', 'translate(560, 54)');
    container.call(d3.behavior.zoom().scaleExtent([1, 49]).on('zoom', (function() {
      return vis.attr('transform', "translate(" + d3.event.translate + ")scale(" + d3.event.scale + ")");
    })));
    vis = container.append('g');
    /* create a rectangular overlay to catch events
    */
    /* WARNING rect size is huge but not infinite. this is a dirty hack
    */
    vis.append('rect').attr('class', 'overlay').attr('x', -500000).attr('y', -500000).attr('width', 1000000).attr('height', 1000000);
    /* END ZOOM and PAN
    */
    /* custom projection to make hexagons appear regular (y axis is also flipped)
    */
    radius = 6;
    dx = radius * 2 * Math.sin(Math.PI / 3);
    dy = radius * 1.5;
    path_generator = d3.geo.path().projection(d3.geo.transform({
      point: function(x, y) {
        return this.stream.point(x * dx / 2, -(y - (2 - (y & 1)) / 3) * dy / 2);
      }
    }));
    /* depth scale
    */
    whiteness = 0.6;
    whiten = function(color) {
      return d3.interpolateHcl(color, d3.hcl(void 0, 0, 100))(whiteness);
    };
    colorify = d3.scale.quantize().domain([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]).range(['#396353', '#0DB14B', '#6DC067', '#ABD69B', '#DAEAC1', '#DFCCE4', '#C7B2D6', '#9474B4', '#754098', '#504971'].map(whiten));
    /* legend
    */
    legend = svg.append('g').attr('id', 'legend').attr('transform', 'translate(30,20)');
    scale = (function() {
      _results = [];
      for (var _i = _ref = colorify.domain()[0], _ref2 = colorify.domain()[1]; _ref <= _ref2 ? _i <= _ref2 : _i >= _ref2; _ref <= _ref2 ? _i++ : _i--){ _results.push(_i); }
      return _results;
    }).apply(this);
    categories = legend.selectAll('.category').data(scale).enter().append('g').attr('class', 'category').attr('transform', function(d, i) {
      return "translate(0," + (i * 22) + ")";
    });
    categories.append('rect').attr('x', 0).attr('y', 0).attr('width', 22).attr('height', 22).attr('fill', function(d) {
      return colorify(d);
    });
    categories.append('text').attr('y', 11).attr('dx', -4).attr('dy', '0.35em').text(function(d) {
      return d;
    });
    /* load topoJSON data
    */
    return d3.json('regions_depth.topo.json', function(error, data) {
      /* write the name of the land
      */
      var defs, depth, title;
      title = svg.append('text').attr('class', 'title').text(topojson.feature(data, data.objects['0']).features[0].properties.label).attr('transform', 'translate(80,40)');
      /* define the level zero region (the land)
      */
      defs = svg.append('defs');
      defs.append('path').datum(topojson.feature(data, data.objects['0']).features[0]).attr('id', 'land').attr('d', path_generator);
      /* faux land glow (using filters takes too much resources)
      */
      vis.append('use').attr('class', 'land-glow-outer').attr('xlink:href', '#land');
      vis.append('use').attr('class', 'land-glow-inner').attr('xlink:href', '#land');
      /* draw the depth levels
      */
      vis.selectAll('.contour').data(topojson.feature(data, data.objects.depth).features).enter().append('path').attr('class', 'contour').attr('d', path_generator).attr('fill', function(d) {
        return colorify(d.properties.depth);
      });
      /* draw the political boundaries
      */
      for (depth = 1; depth <= 2; depth++) {
        vis.append('path').datum(topojson.mesh(data, data.objects[depth], (function(a, b) {
          return a !== b;
        }))).attr('d', path_generator).attr('class', 'boundary').style('stroke-width', "" + (1.8 / depth) + "px");
      }
      /* draw the land border
      */
      vis.append('use').attr('class', 'land-fill').attr('xlink:href', '#land');
      /* draw the other labels
      */
      return vis.selectAll('.label').data(concat((function() {
        var _results2;
        _results2 = [];
        for (depth = 2; depth >= 1; depth--) {
          _results2.push(topojson.feature(data, data.objects[depth]).features.map(function(d) {
            return {
              feature: d,
              depth: depth
            };
          }));
        }
        return _results2;
      })())).enter().append('text').attr('class', 'label').attr('dy', '0.35em').attr('transform', (function(d) {
        var area, centroid;
        centroid = path_generator.centroid(d.feature);
        area = path_generator.area(d.feature);
        return "translate(" + centroid[0] + "," + centroid[1] + ") scale(" + (10 / d.depth) + ")";
      })).text(function(d) {
        return d.feature.properties.label;
      });
    });
  };

}).call(this);

index.html

<!DOCTYPE html>
<html>
    <head>
        <meta charset="utf-8">
        <title>Fractal treemap - Konanopii (1,724)</title>
        <link type="text/css" href="index.css" rel="stylesheet"/>
        <script src="//d3js.org/d3.v3.min.js"></script>
        <script src="//d3js.org/topojson.v1.min.js"></script>
        <script src="index.js"></script>
    </head>
    <body onload="main()">
    </body>
</html>

gosper_regions_depth.py

from __future__ import print_function
from itertools import izip
import csv
import json
from shapely.geometry.polygon import Polygon
import shapely.wkt
from fiona import collection
from shapely.geometry import mapping
import re
import os

# yield the leaves of the tree, also computing each leaf path
def leafify(node, path=()):
    if 'c' not in node:
        node['path'] = path + (node,)
        yield node
    else:
        for c in node['c']:
            for l in leafify(c, path + (node,)):
                yield l 
                
def gosperify(tree_path, hexes_path, output_regions_dir_path, depth_filename):
    leaves_done = 0
    layers = {}
    depth_levels = {}
    
    print('Reading the tree...')
    
    with open(tree_path, 'rb') as tree_file:
        tree = json.loads(tree_file.read())
        
    print('Reading hexes...')
    
    # iterate over the hexes taken from the file
    with open(hexes_path, 'rb') as hexes_file:
        hexes_reader = csv.reader(hexes_file, delimiter=';', quotechar='#')
        
        for leaf, hexes_row in izip(leafify(tree), hexes_reader):
            path = leaf['path']
            hex = shapely.wkt.loads(hexes_row[0])
            
            for depth in xrange(len(path)):
                # add the hex to its political regions
                ancestor_or_self = path[depth]
                
                if depth not in layers:
                    layers[depth] = {}
                    
                if id(ancestor_or_self) not in layers[depth]:
                    layers[depth][id(ancestor_or_self)] = {
                        'geometry': hex,
                        'node': ancestor_or_self
                    }
                else:
                    layers[depth][id(ancestor_or_self)]['geometry'] = layers[depth][id(ancestor_or_self)]['geometry'].union(hex)
                    
                # add the hex to all the depth levels with d <= depth
                if depth not in depth_levels:
                    depth_levels[depth] = hex
                else:
                    depth_levels[depth] = depth_levels[depth].union(hex)
                    
            # logging
            leaves_done += 1
            print('%d leaves done' % leaves_done, end='\r')
    
    print('Writing political regions...')
    
    schema = {'geometry': 'Polygon', 'properties': {'label': 'str'}}
    
    if not os.path.exists(output_regions_dir_path):
        os.makedirs(output_regions_dir_path)
        
    for depth, regions in layers.items():
        with collection(output_regions_dir_path+'/'+str(depth)+'.json', 'w', 'GeoJSON', schema) as output:
            for _, region_obj in regions.items():
                output.write({
                    'properties': {
                        'label': region_obj['node']['l']
                    },
                    'geometry': mapping(region_obj['geometry'])
                })
            
    print('Writing depth_levels...')
    
    schema = {'geometry': 'Polygon', 'properties': {'depth': 'int'}}
    
    with collection(depth_filename, 'w', 'GeoJSON', schema) as output:
        for depth, region in depth_levels.items():
            output.write({
                'properties': {
                    'depth': depth
                },
                'geometry': mapping(region)
            })

index.coffee

concat = (a) -> a.reduce ((a,o) -> a.concat(o)), []

window.main = () ->
    ### "globals" ###
    vis = null
    
    width = 960
    height = 500
    
    svg = d3.select('body').append('svg')
        .attr('width', width)
        .attr('height', height)
        
    ### ZOOM and PAN ###
    ### create container elements ###
    container = svg.append('g')
        .attr('transform','translate(560, 54)')
        
    container.call(d3.behavior.zoom().scaleExtent([1, 49]).on('zoom', (() -> vis.attr('transform', "translate(#{d3.event.translate})scale(#{d3.event.scale})"))))
    
    vis = container.append('g')
    
    ### create a rectangular overlay to catch events ###
    ### WARNING rect size is huge but not infinite. this is a dirty hack ###
    vis.append('rect')
        .attr('class', 'overlay')
        .attr('x', -500000)
        .attr('y', -500000)
        .attr('width', 1000000)
        .attr('height', 1000000)
        
    ### END ZOOM and PAN ###
    
    ### custom projection to make hexagons appear regular (y axis is also flipped) ###
    radius = 6
    dx = radius * 2 * Math.sin(Math.PI / 3)
    dy = radius * 1.5
    
    path_generator = d3.geo.path()
        .projection d3.geo.transform({
            point: (x,y) ->
                this.stream.point(x * dx / 2, -(y - (2 - (y & 1)) / 3) * dy / 2)
        })
        
    ### depth scale ###
    whiteness = 0.6
    whiten = (color) -> d3.interpolateHcl(color, d3.hcl(undefined,0,100))(whiteness)
    colorify = d3.scale.quantize()
        .domain([0..9])
        .range(['#396353','#0DB14B','#6DC067','#ABD69B','#DAEAC1','#DFCCE4','#C7B2D6','#9474B4','#754098','#504971'].map(whiten))
        # .range(['#59A80F','#9ED54C','#C4ED68','#E2FF9E','#F0F2DD','#F8CA8C','#E9A189','#D47384','#AC437B','#8C286E'])
        # .range(['#FFFCF6','#FFF7DB','#FFF4C2','#FEECAE','#F8CA8C','#F0A848','#C07860','#A86060','#784860','#604860'])
        
    ### legend ###
    legend = svg.append('g')
        .attr('id','legend')
        .attr('transform', 'translate(30,20)')
        
    scale = [colorify.domain()[0]..colorify.domain()[1]]
    categories = legend.selectAll('.category')
        .data(scale)
      .enter().append('g')
        .attr('class', 'category')
        .attr('transform', (d,i) -> "translate(0,#{i*22})")
        
    categories.append('rect')
        .attr('x', 0).attr('y', 0)
        .attr('width', 22).attr('height', 22)
        .attr('fill', (d) -> colorify(d))
        
    categories.append('text')
        .attr('y', 11)
        .attr('dx', -4)
        .attr('dy', '0.35em')
        .text((d) -> d)
        
    ### load topoJSON data ###
    d3.json 'regions_depth.topo.json', (error, data) ->
        ### write the name of the land ###
        title = svg.append('text')
            .attr('class', 'title')
            .text(topojson.feature(data, data.objects['0']).features[0].properties.label)
            .attr('transform', 'translate(80,40)')
            
        ### define the level zero region (the land) ###
        defs = svg.append('defs')
        
        defs.append('path')
            .datum(topojson.feature(data, data.objects['0']).features[0])
            .attr('id', 'land')
            .attr('d', path_generator)
            
        ### faux land glow (using filters takes too much resources) ###
        vis.append('use')
            .attr('class', 'land-glow-outer')
            .attr('xlink:href', '#land')
            
        vis.append('use')
            .attr('class', 'land-glow-inner')
            .attr('xlink:href', '#land')
            
        ### draw the depth levels ###
        vis.selectAll('.contour')
            .data(topojson.feature(data, data.objects.depth).features)
          .enter().append('path')
            .attr('class', 'contour')
            .attr('d', path_generator)
            .attr('fill', (d) -> colorify(d.properties.depth))
            
        ### draw the political boundaries ###
        for depth in [1..2]
            vis.append('path')
                .datum(topojson.mesh(data, data.objects[depth], ((a,b) -> a isnt b)))
                .attr('d', path_generator)
                .attr('class', 'boundary')
                .style('stroke-width', "#{1.8/depth}px")
                
        ### draw the land border ###
        vis.append('use')
            .attr('class', 'land-fill')
            .attr('xlink:href', '#land')
            
        ### draw the other labels ###
        vis.selectAll('.label')
            .data(concat((topojson.feature(data, data.objects[depth]).features.map((d) -> {feature: d, depth: depth}) for depth in [2..1])))
          .enter().append('text')
            .attr('class', 'label')
            .attr('dy','0.35em')
            .attr('transform', ((d) ->
                centroid = path_generator.centroid(d.feature)
                area = path_generator.area(d.feature)
                return "translate(#{centroid[0]},#{centroid[1]}) scale(#{10/d.depth})"
            ))
            .text((d) -> d.feature.properties.label)

index.css

#land {
  fill: none;
}

.land-glow-outer {
  stroke: #eeeeee;
  stroke-width: 16px;
}

.land-glow-inner {
  stroke: #dddddd;
  stroke-width: 8px;
}

.land-fill {
  stroke: #444444;
  stroke-width: 2px;
}

.contour {
  stroke: none;
}

.category text {
  text-anchor: end;
  fill: #444444;
  font-family: sans-serif;
  font-weight: bold;
  font-size: 14px;
  pointer-events: none;
  text-shadow: -1px 0 white, 0 1px white, 1px 0 white, 0 -1px white;
}

.boundary {
  stroke: #444444;
  fill: none;
  pointer-events: none;
}

@font-face {
  font-family: "Lacuna";
  src: url("lacuna.ttf");
}

.label {
  text-transform: capitalize;
  text-anchor: middle;
  font-size: 2.5px;
  fill: #444444;
  pointer-events: none;
  font-family: "Lacuna";
  text-shadow: -2px 0 white, 0 2px white, 2px 0 white, 0 -2px white, -1px -1px white, 1px -1px white, 1px 1px white, -1px 1px white;
}

.title {
  text-transform: capitalize;
  text-anchor: start;
  font-size: 24pt;
  fill: #444444;
  pointer-events: none;
  font-family: "Lacuna";
  text-shadow: -1px 0 white, 0 1px white, 1px 0 white, 0 -1px white;
}

.overlay {
  fill: transparent;
}

index.sass

@mixin halo($color)
    text-shadow: -1px 0 $color, 0 1px $color, 1px 0 $color, 0 -1px $color
    
@mixin halo_double($color)
    text-shadow: -2px 0 $color, 0 2px $color, 2px 0 $color, 0 -2px $color, -1px -1px $color, 1px -1px $color, 1px 1px $color, -1px 1px $color
    
#land
    fill: none
    
.land-glow-outer
    stroke: #EEE
    stroke-width: 16px
    
.land-glow-inner
    stroke: #DDD
    stroke-width: 8px
    
.land-fill
    stroke: #444
    stroke-width: 2px
    
.contour
    stroke: none
    
.category text
    text-anchor: end
    fill: #444
    font-family: sans-serif
    font-weight: bold
    font-size: 14px
    pointer-events: none
    @include halo(white)
    
.boundary
    stroke: #444
    fill: none
    
    // avoid blinking when hovering regions
    pointer-events: none
    
@font-face
    font-family: 'Lacuna'
    src: url('lacuna.ttf')
    
.label
    text-transform: capitalize
    text-anchor: middle
    font-size: 2.5px
    fill: #444
    pointer-events: none
    font-family: 'Lacuna'
    @include halo_double(white)
    
.title
    text-transform: capitalize
    text-anchor: start
    font-size: 24pt
    fill: #444
    pointer-events: none
    font-family: 'Lacuna'
    @include halo(white)
    
// zoom and pan
.overlay
    fill: transparent