Skip to content

Instantly share code, notes, and snippets.

@Fil
Last active Jan 30, 2017
Embed
What would you like to do?
Hilbert paths
license: mit
<!DOCTYPE html>
<head>
<meta charset="utf-8">
<script src="https://d3js.org/d3.v4.min.js"></script>
<style>
body { margin:0;position:fixed;top:0;right:0;bottom:0;left:0; }
</style>
</head>
<body>
<script>
// Feel free to change or delete any of the code you see in this editor!
var svg = d3.select("body").append("svg")
.attr("width", 960)
.attr("height", 530)
.append('g')
.attr('transform', 'translate(10,10)')
var scale = 8,
max = Math.pow(2, Math.floor(Math.log2(512/scale)));
var color = d3.scaleOrdinal(d3.schemeCategory20b);
var n=0, m=0, segments = [];
while (n < max*max){
m = 3 + Math.floor(100 * Math.random() * Math.random());
segments.push([n, n += m]);
}
segments[segments.length-1][1] = max*max;
svg.append('g')
.selectAll('path')
.data(segments)
.enter()
.append('path')
.attr('fill', 'transparent')
.attr('stroke', (d,i) => color(i))
.attr('stroke-width', '8')
.attr('stroke-linecap',"square")
.attr('d', d =>
'M'
+ d3.range(d[0], d[1])
.map(e => [(xy = d2xy(e), scale * xy.x), scale * xy.y])
.join('L')
);
svg.append('path')
.attr('fill', 'transparent')
.attr('stroke', '#fff')
.attr('stroke-width', '1')
.attr('d', 'M' + d3.range(max*max).map(d2xy).map(d => [scale * d.x, scale * d.y]).join('L'))
t = svg.append('text')
.attr("y", 100)
.attr("x", 512)
.attr("font-size", 36)
.style("font-family", "monospace");
var c = d3.range(7)
.map(i =>
svg.append('circle')
.attr("r", 5)
.attr('fill', 'white')
);
d3.interval(e => {
var xy = d2xy((e/10) % (max*max));
c[Math.floor(Math.random()*c.length)]
.transition()
.duration(10)
.attr('cx', scale * xy.x)
.attr('cy', scale * xy.y)
t.text(JSON.stringify(xy));
},10);
// https://github.com/ryan-williams/hilbert/blob/master/hilbert2d.js
var horseshoe2d = [0, 1, 3, 2];
function d2xy(d) {
d = Math.floor(d);
var curPos = {
x: 0,
y: 0
};
var s = 1;
var iter = 0;
while (d > 0) {
var ry = 1 & (d/2);
var rx = 1 & (ry ^ d);
// Rotate, if need be
if (rx == 0) {
if (ry == 1) {
curPos = {
x: s - 1 - curPos.x,
y: s - 1 - curPos.y
};
}
curPos = {
x: curPos.y,
y: curPos.x
};
}
curPos = {
x: curPos.x + s*rx,
y: curPos.y + s*ry
};
s *= 2;
d = Math.floor(d/4);
iter = (iter + 1) % 2;
}
if (iter == 0) {
curPos = {
x: curPos.y,
y: curPos.x
};
}
return curPos;
};
xy2d = function(x, y) {
x = Math.floor(x);
y = Math.floor(y);
var s = 1;
var max = Math.max(x,y);
var level = 0;
for (; 2*s <= max; s*=2) {
level = (level + 1) % 2;
}
if (level % 2 == 1) {
var t = x;
x = y;
y = t;
}
var d = 0;
while(s > 0) {
var rx = x&s && 1;
var ry = y&s && 1;
d *= 4;
d += horseshoe2d[2*ry + rx];
log("s: " + s + " d: " + d + " r:("+rx+','+ry+')');
if (rx == 0) {
if (ry == 1) {
x = s-1 - x;
y = s-1 - y;
}
var t = x;
x = y;
y = t;
}
x %= s;
y %= s;
s = Math.floor(s / 2);
}
return d;
};
</script>
</body>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment