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.
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.
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; | |
} |
<!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> |
// 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); |