README.md

## README.md

      
          Raw
        
        
              README.md
            
          
    This example uses strings of quaternary digits to generate squares in a quadtree. The string acts as a unique identifier for squares of different size and position.

Click here to compare with a Hilbert displacement.

  
## index.coffee
scale = 480

svg = d3.select 'svg'
vis = svg.append 'g'
  .attr
    transform: "translate(#{scale/2}, 10)"

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

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
    }

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
  }

###  Visualization
###
indices = ["0","10","11","12","13","200","201","202","203","210","211","212","213","220","221","222","223","230","231","232","233","230","231","232","233","3000","3001","3002","301","302","303","31","32"]

quads = indices.map quad_layout(quad, scale)

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
  .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/5
  .text (d) -> d.digits

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

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

rect {
  fill: steelblue;
  stroke: #fff;
  stroke-width: 0.5px;
}

text {
  pointer-events: none;
}

## index.html
<!doctype html>
<html>
  <head>
    <meta charset="utf-8">
    <title>Quaternary numbers for indexing a quadtree</title>
    <link type="text/css" rel="stylesheet" href="index.css"/>
    <script src="http://d3js.org/d3.v3.min.js"></script>
  </head>
  <body>
    <svg></svg>
    <script src="index.js"></script>
  </body>
</html>

## index.js
// Generated by CoffeeScript 1.10.0
(function() {
  var height, indices, quad, quad_layout, quads, rects, scale, svg, vis, width;

  scale = 480;

  svg = d3.select('svg');

  vis = svg.append('g').attr({
    transform: "translate(" + (scale / 2) + ", 10)"
  });

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

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

  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
      };
    };
  };

  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
    };
  };


  /*  Visualization
   */

  indices = ["0", "10", "11", "12", "13", "200", "201", "202", "203", "210", "211", "212", "213", "220", "221", "222", "223", "230", "231", "232", "233", "230", "231", "232", "233", "3000", "3001", "3002", "301", "302", "303", "31", "32"];

  quads = indices.map(quad_layout(quad, scale));

  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;
    }
  }).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 / 5;
    }
  }).text(function(d) {
    return d.digits;
  });

}).call(this);

## thumbnail.png

      
          Raw
        
        
              thumbnail.png