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.
// 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);
<!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="//d3js.org/d3.v3.min.js"></script>
</head>
<body>
<svg></svg>
<script src="index.js"></script>
</body>
</html>
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
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;
}