Hilbert Map

.block

license: mit

README.md

This example is an attempt to generate a treemap based on the Hilbert curve. We use an approach based on the generation of quads from numbers in base 4. Each color represents a class. On the top left, the legend shows the amount of instances each class contains.

The fractal structure of the resulting map can be seen by zooming the tiny tails of each region. REFRESH the page in order to get a new map (Both number of classes and class amounts are randomly generated).

forked from fabiovalse's block: Hilbert Map

index.coffee

replace_char = (s, index, new_char) ->
  s.substr(0, index) + new_char + s.substr(index + 1)

get_quad_code = (offset, N, n) ->
  b4 = offset.toString(4)
  b4 = Array(N-b4.length+1).join('0') + b4
  b4 = b4[0...N-n]
  return b4

get_quads = (cls) ->
  quads = []

  # START to Z range
  if cls.start isnt cls.z
    offset = cls.start
    start_to_z = (cls.z - cls.start).toString(4).split('').reverse().join('')

    for d,i in start_to_z
      for j in [0...parseInt(d)]
        digits = start_to_z.length - (start_to_z.length - i)

        quad = get_quad_code offset, order, digits
        quads.push quad

        offset += parseInt('1' + Array(digits + 1).join('0'), 4)

  # Z to END range
  offset = cls.z
  z_to_end = (cls.end - cls.z).toString(4)

  for d,i in z_to_end
    for j in [0...parseInt(d)]
      digits = z_to_end.length - i - 1

      quad = get_quad_code offset, order, digits
      quads.push quad

      offset += parseInt('1' + Array(z_to_end.length - i).join('0'), 4)

  return quads

get_z = (d) ->
  start_4 = (d.start).toString(4)
  end_4 = (d.end).toString(4)

  if start_4 is '0'
    return parseInt(start_4, 4)

  i = start_4.length - 1
  initial_i = start_4.length - 1
  while start_4.length <= end_4.length
    # zero the i-th digit
    new_start_4 = replace_char start_4, i, '0'
    # plus one the (i-1)th digit
    new_start_4 = (parseInt('1' + Array(new_start_4.length - i + 1).join('0'), 4)+parseInt(new_start_4, 4)).toString(4)

    if parseInt(new_start_4, 4) < d.end
      start_4 = new_start_4
    else
      break

    if initial_i is start_4.length
      i -= 1
    else
      initial_i += 1

  return parseInt(start_4, 4)

### Initialization
###
start = 0

# Random data construction
n_class = Array(Math.ceil(Math.random()*10)).fill()
data = n_class.map (d,i) -> {name: "class#{i+1}", size: Math.ceil(Math.random()*10000000000)}

order = Math.ceil(Math.log(d3.sum(data, (d) -> d.size)) / Math.log(4))

data.forEach (cls) ->
  # START, END offset calculation
  cls.start = start
  cls.end = start + cls.size
  start += cls.size

  cls.z = get_z cls
  cls.quads = get_quads cls

### Visualization
###
scale = 480
precision_multiplier = 10000

svg = d3.select 'svg'

width = svg.node().getBoundingClientRect().width
height = svg.node().getBoundingClientRect().height

svg
  .attr
    width: width
    height: height

zoomable_layer = svg.append('g')
zoom = d3.behavior.zoom()
  .scaleExtent([-Infinity, Infinity])
  .on 'zoom', () ->
    zoomable_layer
      .attr
        transform: "translate(#{zoom.translate()})scale(#{zoom.scale()})"
svg.call(zoom)

vis = zoomable_layer.append 'g'
  .attr
    transform: "translate(#{(width-scale)/2}, #{(height-scale)/2}) scale(#{1/precision_multiplier})"
legend = svg.append 'g'

color = d3.scale.category10()

quads = []
data.forEach (d) ->
  q = d.quads.map quad_layout(hquad, scale*precision_multiplier)
  q.forEach (i) ->
    i.name = d.name
  quads = quads.concat q

# Quads
rects = vis.selectAll 'rect'
  .data quads

rects.enter().append 'g'

rects.append 'rect'
  .attr
    x: (d) -> d.x
    y: (d) -> d.y
    width: (d) -> d.dx
    height: (d) -> d.dy
    fill: (d) -> color d.name
  .append 'title'
    .text (d) -> "x: #{d.x}\ny: #{d.y}\nw/h: #{d.dx}"

rects.append 'text'
  .attr
    x: (d) -> d.x + (d.dx / 2)
    y: (d) -> d.y + (d.dy / 2)
    'text-anchor': 'middle'
    dy: '0.35em'
    'font-size': (d) -> d.dx/8
  .text (d) -> d.digits

# Legend
legend_items = legend.selectAll '.legend_item'
  .data data

legend_items.enter().append 'g'
  .attr
    class: 'legend_item'

legend_items.append 'rect'
  .attr
    x: 10
    y: (d,i) -> 10 + i*15
    width: (d) -> 10
    height: (d) -> 10
    fill: (d) -> color d.name

legend_items.append 'text'
  .attr
    x: 30
    y: (d,i) -> 15 + i*15
    dy: '0.35em'
  .text (d) -> d3.format(',d')(d.size)

index.css

html, body {
  padding: 0;
  margin: 0;
  height: 100%;
  overflow: hidden;
  font-family: sans-serif;
}

svg {
  width: 100%;
  height: 100%;
}

rect {
  stroke: #fff;
  stroke-width: 0.5px;
  vector-effect: non-scaling-stroke;
}

text {
  pointer-events: none;
}

.legend_item {
  font-size: 12px;
}

index.html

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <script src="quad_utils.js"></script>
  <script src="http://d3js.org/d3.v3.min.js"></script>
  <link rel="stylesheet" href="index.css">
  <title></title>
</head>
<body>
  <svg></svg>
  <script src="index.js"></script>
</body>
</html>

index.js

// Generated by CoffeeScript 1.10.0
(function() {
  var color, data, float_multiplier, get_quad_code, get_quads, get_z, height, legend, legend_items, n_class, order, quads, rects, replace_char, scale, start, svg, vis, width, zoom, zoomable_layer;

  replace_char = function(s, index, new_char) {
    return s.substr(0, index) + new_char + s.substr(index + 1);
  };

  get_quad_code = function(offset, N, n) {
    var b4;
    b4 = offset.toString(4);
    b4 = Array(N - b4.length + 1).join('0') + b4;
    b4 = b4.slice(0, N - n);
    return b4;
  };

  get_quads = function(cls) {
    var d, digits, i, j, k, l, len, len1, m, o, offset, quad, quads, ref, ref1, start_to_z, z_to_end;
    quads = [];
    if (cls.start !== cls.z) {
      offset = cls.start;
      start_to_z = (cls.z - cls.start).toString(4).split('').reverse().join('');
      for (i = k = 0, len = start_to_z.length; k < len; i = ++k) {
        d = start_to_z[i];
        for (j = l = 0, ref = parseInt(d); 0 <= ref ? l < ref : l > ref; j = 0 <= ref ? ++l : --l) {
          digits = start_to_z.length - (start_to_z.length - i);
          quad = get_quad_code(offset, order, digits);
          quads.push(quad);
          offset += parseInt('1' + Array(digits + 1).join('0'), 4);
        }
      }
    }
    offset = cls.z;
    z_to_end = (cls.end - cls.z).toString(4);
    for (i = m = 0, len1 = z_to_end.length; m < len1; i = ++m) {
      d = z_to_end[i];
      for (j = o = 0, ref1 = parseInt(d); 0 <= ref1 ? o < ref1 : o > ref1; j = 0 <= ref1 ? ++o : --o) {
        digits = z_to_end.length - i - 1;
        quad = get_quad_code(offset, order, digits);
        quads.push(quad);
        offset += parseInt('1' + Array(z_to_end.length - i).join('0'), 4);
      }
    }
    return quads;
  };

  get_z = function(d) {
    var end_4, i, initial_i, new_start_4, start_4;
    start_4 = d.start.toString(4);
    end_4 = d.end.toString(4);
    if (start_4 === '0') {
      return parseInt(start_4, 4);
    }
    i = start_4.length - 1;
    initial_i = start_4.length - 1;
    while (start_4.length <= end_4.length) {
      new_start_4 = replace_char(start_4, i, '0');
      new_start_4 = (parseInt('1' + Array(new_start_4.length - i + 1).join('0'), 4) + parseInt(new_start_4, 4)).toString(4);
      if (parseInt(new_start_4, 4) < d.end) {
        start_4 = new_start_4;
      } else {
        break;
      }
      if (initial_i === start_4.length) {
        i -= 1;
      } else {
        initial_i += 1;
      }
    }
    return parseInt(start_4, 4);
  };


  /* Initialization
   */

  start = 0;

  n_class = Array(Math.ceil(Math.random() * 10)).fill();

  data = n_class.map(function(d, i) {
    return {
      name: "class" + (i + 1),
      size: Math.ceil(Math.random() * 10000000000)
    };
  });

  order = Math.ceil(Math.log(d3.sum(data, function(d) {
    return d.size;
  })) / Math.log(4));

  data.forEach(function(cls) {
    cls.start = start;
    cls.end = start + cls.size;
    start += cls.size;
    cls.z = get_z(cls);
    return cls.quads = get_quads(cls);
  });


  /* Visualization
   */

  scale = 480;

  float_multiplier = 10000;

  svg = d3.select('svg');

  width = svg.node().getBoundingClientRect().width;

  height = svg.node().getBoundingClientRect().height;

  svg.attr({
    width: width,
    height: height
  });

  zoomable_layer = svg.append('g');

  zoom = d3.behavior.zoom().scaleExtent([-Infinity, Infinity]).on('zoom', function() {
    return zoomable_layer.attr({
      transform: "translate(" + (zoom.translate()) + ")scale(" + (zoom.scale()) + ")"
    });
  });

  svg.call(zoom);

  vis = zoomable_layer.append('g').attr({
    transform: "translate(" + ((width - scale) / 2) + ", " + ((height - scale) / 2) + ") scale(" + (1 / float_multiplier) + ")"
  });

  legend = svg.append('g');

  color = d3.scale.category10();

  quads = [];

  data.forEach(function(d) {
    var q;
    q = d.quads.map(quad_layout(hquad, scale * float_multiplier));
    q.forEach(function(i) {
      return i.name = d.name;
    });
    return quads = quads.concat(q);
  });

  rects = vis.selectAll('rect').data(quads);

  rects.enter().append('g');

  rects.append('rect').attr({
    x: function(d) {
      return d.x;
    },
    y: function(d) {
      return d.y;
    },
    width: function(d) {
      return d.dx;
    },
    height: function(d) {
      return d.dy;
    },
    fill: function(d) {
      return color(d.name);
    }
  }).append('title').text(function(d) {
    return "x: " + d.x + "\ny: " + d.y + "\nw/h: " + d.dx;
  });

  rects.append('text').attr({
    x: function(d) {
      return d.x + (d.dx / 2);
    },
    y: function(d) {
      return d.y + (d.dy / 2);
    },
    'text-anchor': 'middle',
    dy: '0.35em',
    'font-size': function(d) {
      return d.dx / 8;
    }
  }).text(function(d) {
    return d.digits;
  });

  legend_items = legend.selectAll('.legend_item').data(data);

  legend_items.enter().append('g').attr({
    "class": 'legend_item'
  });

  legend_items.append('rect').attr({
    x: 10,
    y: function(d, i) {
      return 10 + i * 15;
    },
    width: function(d) {
      return 10;
    },
    height: function(d) {
      return 10;
    },
    fill: function(d) {
      return color(d.name);
    }
  });

  legend_items.append('text').attr({
    x: 30,
    y: function(d, i) {
      return 15 + i * 15;
    },
    dy: '0.35em'
  }).text(function(d) {
    return d3.format(',d')(d.size);
  });

}).call(this);

quad_utils.coffee

window.sizeify = (n) ->
  #if typeof n is 'string'
  if !n.children?
    n.n = 0
    n.size = 1
    return 1
  else
    n.size = 0
    n.children.forEach (c) ->
      n.size += sizeify(c)

    # expand to fill a square
    n.n = Math.ceil(Math.log(n.size)/Math.log(4))
    n.size = Math.pow(4,n.n)

    return n.size

window.quad_layout = (mapping, size) ->

  return (digits) ->
    m = mapping digits

    return {
      x: m.j/Math.pow(2,m.n)*size,
      y: m.i/Math.pow(2,m.n)*size,
      dx: 1/Math.pow(2,m.n)*size,
      dy: 1/Math.pow(2,m.n)*size,
      digits: m.digits
    }

window.hquad = (digits) ->
  n = digits.length
  l = 1
  i = 0
  j = 0

  for d in digits by -1
    switch d
      when '0'
        i_temp = i
        i = j
        j = i_temp
      when '1'
        i += l
      when '2'
        i += l
        j += l
      when '3'
        i_temp = i
        i = l - j - 1
        j = 2*l - i_temp - 1

    l = 2*l

  return {
    j: j,
    i: i,
    n: n,
    digits: digits
  }

window.quad = (digits) ->
  n = digits.length
  l = 1
  i = 0
  j = 0

  for d in digits by -1
    switch d
      when '1'
        j += l
      when '2'
        i += l
      when '3'
        i += l
        j += l

    l = 2*l

  return {
    j: j,
    i: i,
    n: n,
    digits: digits
  }

quad_utils.js

// Generated by CoffeeScript 1.10.0
(function() {
  window.sizeify = function(n) {
    if (n.children == null) {
      n.n = 0;
      n.size = 1;
      return 1;
    } else {
      n.size = 0;
      n.children.forEach(function(c) {
        return n.size += sizeify(c);
      });
      n.n = Math.ceil(Math.log(n.size) / Math.log(4));
      n.size = Math.pow(4, n.n);
      return n.size;
    }
  };

  window.quad_layout = function(mapping, size) {
    return function(digits) {
      var m;
      m = mapping(digits);
      return {
        x: m.j / Math.pow(2, m.n) * size,
        y: m.i / Math.pow(2, m.n) * size,
        dx: 1 / Math.pow(2, m.n) * size,
        dy: 1 / Math.pow(2, m.n) * size,
        digits: m.digits
      };
    };
  };

  window.hquad = function(digits) {
    var d, i, i_temp, j, k, l, n;
    n = digits.length;
    l = 1;
    i = 0;
    j = 0;
    for (k = digits.length - 1; k >= 0; k += -1) {
      d = digits[k];
      switch (d) {
        case '0':
          i_temp = i;
          i = j;
          j = i_temp;
          break;
        case '1':
          i += l;
          break;
        case '2':
          i += l;
          j += l;
          break;
        case '3':
          i_temp = i;
          i = l - j - 1;
          j = 2 * l - i_temp - 1;
      }
      l = 2 * l;
    }
    return {
      j: j,
      i: i,
      n: n,
      digits: digits
    };
  };

  window.quad = function(digits) {
    var d, i, j, k, l, n;
    n = digits.length;
    l = 1;
    i = 0;
    j = 0;
    for (k = digits.length - 1; k >= 0; k += -1) {
      d = digits[k];
      switch (d) {
        case '1':
          j += l;
          break;
        case '2':
          i += l;
          break;
        case '3':
          i += l;
          j += l;
      }
      l = 2 * l;
    }
    return {
      j: j,
      i: i,
      n: n,
      digits: digits
    };
  };

}).call(this);