Skip to content

Instantly share code, notes, and snippets.

@fabiovalse

fabiovalse/README.md

Last active November 8, 2019 07:19
Show Gist options
  • Save fabiovalse/c25191e52406903b4cd9aede7d51ab5e to your computer and use it in GitHub Desktop.
Save fabiovalse/c25191e52406903b4cd9aede7d51ab5e to your computer and use it in GitHub Desktop.
Download ZIP
Hilbert Map
Raw
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).

Raw
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)
Raw
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;
}
Raw
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>
Raw
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);
Raw
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
}
Raw
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);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment