The label placement algorithm introduced here can be also used in treemaps built by using a Peano space-filling curve.
Peano regions always have a landscape (or square) orientation, yielding more horizontal labels than Hilbert treemaps.
/* GLOBAL SETTINGS, SVG and panels
*/
/* define a fixed random seed, to avoid to have a different layout on each page reload. change the string to randomize
*/
(function() {
var LABEL_SCALE, defs, height, hierarchy, i, j, leaves, map, nodes, randint, randlen, randname, randsy, region_labels, scale, svg, svg_bbox, syllables, tree, vis, width, zoom;
width = 960;
height = 500;
svg = d3.select('body').append('svg').attr('width', width).attr('height', height);
svg_bbox = svg[0][0].getBoundingClientRect();
/* main visualization (map view from the top)
*/
vis = svg.append('g');
map = vis.append('g').attr('transform', "translate(" + (width / 2) + "," + (height / 2) + ")").on('click', function() {
if (d3.event.defaultPrevented) return;
return d3.select(this).classed('selected', !d3.select(this).classed('selected'));
});
/* ZUI
*/
/* define a zoom behavior
*/
zoom = d3.behavior.zoom().scaleExtent([0.1, 10]).on('zoom', function() {
/* whenever the user zooms,
*/
/* modify translation and scale of the zoom group accordingly
*/
var scale, translation;
translation = zoom.translate();
scale = zoom.scale();
return vis.attr('transform', "translate(" + translation + ")scale(" + scale + ")");
});
/* bind the zoom behavior to the main SVG
*/
svg.call(zoom);
/* DATA
*/
console.debug('Generating random data...');
syllables = ['bi', 'bo', 'bu', 'ta', 'se', 'tri', 'su', 'ke', 'ka', 'flo', 'ko', 'pi', 'pe', 'no', 'go', 'zo', 'fu', 'fo', 'si', 'pa', 'ar', 'es', 'i', 'kya', 'kyu', 'fle', 'o', 'ne', 'na', 'le', 'lu', 'ma', 'an'];
randlen = function() {
return 2 + Math.floor(Math.random() * 4);
};
randsy = function() {
return syllables[Math.floor(Math.random() * syllables.length)];
};
randname = function() {
var i;
return ((function() {
var _ref, _results;
_results = [];
for (i = 0, _ref = randlen(); 0 <= _ref ? i < _ref : i > _ref; 0 <= _ref ? i++ : i--) {
_results.push(randsy());
}
return _results;
})()).join('');
};
randint = function(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
};
tree = {
children: (function() {
var _ref, _results;
_results = [];
for (j = 0, _ref = randint(8, 32); 0 <= _ref ? j < _ref : j > _ref; 0 <= _ref ? j++ : j--) {
_results.push({
label: randname(),
children: (function() {
var _ref2, _results2;
_results2 = [];
for (i = 0, _ref2 = randint(128, 1280); 0 <= _ref2 ? i < _ref2 : i > _ref2; 0 <= _ref2 ? i++ : i--) {
_results2.push({});
}
return _results2;
})()
});
}
return _results;
})()
};
console.debug('Computing d3 hierarchy layout...');
hierarchy = d3.layout.hierarchy();
nodes = hierarchy(tree);
/* this tree is unordered, we need a canonical ordering for it
*/
console.debug('Computing canonical sort...');
tree_utils.canonical_sort(tree);
/* obtain the sequence of leaves
*/
leaves = tree_utils.get_leaves(tree);
/* VISUALIZATION
*/
/* compute the space-filling curve layout
*/
console.debug('Computing the Space-Filling Curve layout...');
scale = 3;
sfc_layout.displace(leaves, sfc_layout.PEANO, scale, scale, 0);
/* compute also the position of internal nodes
*/
console.debug('Computing the position of internal nodes...');
sfc_layout.displace_tree(tree);
console.debug('Computing the jigsaw treemap...');
/* compute all the internal nodes regions
*/
jigsaw.treemap(tree, scale, jigsaw.SQUARE_CELL);
console.debug('Computing label placement...');
jigsaw.hilbert_labels(tree, scale);
console.debug('Drawing...');
/* define the level zero region (the land)
*/
defs = svg.append('defs');
defs.append('path').attr('id', 'land').attr('d', jigsaw.get_svg_path(tree.region));
/* faux land glow (using filters takes too much resources)
*/
map.append('use').attr('class', 'land-glow-outer').attr('xlink:href', '#land');
map.append('use').attr('class', 'land-glow-inner').attr('xlink:href', '#land');
/* draw the land border (behind boundaries)
*/
map.append('use').attr('class', 'land-fill').attr('xlink:href', '#land');
/* draw label bboxes
*/
map.selectAll('.bbox').data(nodes.filter(function(d) {
return d.depth === 1;
})).enter().append('rect').attr('class', 'bbox').attr('x', function(d) {
return d.label_bbox.x;
}).attr('y', function(d) {
return d.label_bbox.y;
}).attr('width', function(d) {
return d.label_bbox.width;
}).attr('height', function(d) {
return d.label_bbox.height;
});
/* draw boundaries
*/
map.selectAll('.region').data(nodes.filter(function(d) {
return d.depth === 1;
})).enter().append('path').attr('class', 'region').attr('d', function(d) {
return jigsaw.get_svg_path(d.region);
}).attr('stroke-width', '1px').attr('stroke', 'white');
/* draw region labels
*/
LABEL_SCALE = 0.8;
region_labels = map.selectAll('.region_label').data(nodes.filter(function(d) {
return d.depth === 1;
})).enter().append('text').attr('class', 'region_label').attr('dy', '0.35em').text(function(d) {
return d.label;
}).attr('transform', function(d) {
var bbox, bbox_aspect, h_ratio, lbbox, lbbox_aspect, lbbox_height, lbbox_width, ratio, rotate, w_ratio;
bbox = this.getBBox();
bbox_aspect = bbox.width / bbox.height;
lbbox = d.label_bbox;
lbbox_aspect = lbbox.width / lbbox.height;
rotate = bbox_aspect >= 1 && lbbox_aspect < 1 || bbox_aspect < 1 && lbbox_aspect >= 1;
if (rotate) {
lbbox_width = lbbox.height;
lbbox_height = lbbox.width;
} else {
lbbox_width = lbbox.width;
lbbox_height = lbbox.height;
}
w_ratio = lbbox_width / bbox.width;
h_ratio = lbbox_height / bbox.height;
ratio = Math.min(w_ratio, h_ratio) * LABEL_SCALE;
return "translate(" + (d.label_bbox.x + d.label_bbox.width / 2) + "," + (d.label_bbox.y + d.label_bbox.height / 2) + "),scale(" + ratio + "),rotate(" + (rotate ? -90 : 0) + ")";
});
}).call(this);
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Label placement for Peano treemaps</title>
<link type="text/css" href="index.css" rel="stylesheet"/>
<script src="//d3js.org/d3.v3.min.js"></script>
<script src="//jsclipper.sourceforge.net/6.1.3.1/clipper.js"></script>
<script src="//davidbau.com/encode/seedrandom-min.js"></script>
<script src="zip.js"></script>
<script src="tree_utils.js"></script>
<script src="sfc_layout.js"></script>
<script src="jigsaw.js"></script>
</head>
<body>
</body>
<script src="index.js"></script>
</html>### GLOBAL SETTINGS, SVG and panels ###
### define a fixed random seed, to avoid to have a different layout on each page reload. change the string to randomize ###
# Math.seedrandom('42')
width = 960
height = 500
svg = d3.select('body').append('svg')
.attr('width', width)
.attr('height', height)
svg_bbox = svg[0][0].getBoundingClientRect()
### main visualization (map view from the top) ###
vis = svg.append('g')
map = vis.append('g')
.attr('transform', "translate(#{width/2},#{height/2})")
.on('click', () ->
return if (d3.event.defaultPrevented)
d3.select(this).classed('selected', not d3.select(this).classed('selected'))
)
### ZUI ###
### define a zoom behavior ###
zoom = d3.behavior.zoom()
.scaleExtent([0.1,10]) # min-max zoom
.on 'zoom', () ->
### whenever the user zooms, ###
### modify translation and scale of the zoom group accordingly ###
translation = zoom.translate()
scale = zoom.scale()
vis.attr('transform', "translate(#{translation})scale(#{scale})")
### bind the zoom behavior to the main SVG ###
svg.call(zoom)
### DATA ###
console.debug 'Generating random data...'
syllables = ['bi','bo','bu','ta','se','tri','su','ke','ka','flo','ko','pi','pe','no','go','zo','fu','fo','si','pa','ar','es','i','kya','kyu','fle','o','ne','na','le','lu','ma','an']
randlen = () -> 2+Math.floor(Math.random()*4)
randsy = () -> syllables[Math.floor(Math.random()*syllables.length)]
randname = () -> (randsy() for i in [0...randlen()]).join('')
randint = (min, max) -> Math.floor(Math.random()*(max-min+1)) + min
tree = {
children: ({label: randname(), children: ({} for i in [0...randint(128,1280)])} for j in [0...randint(8,32)])
}
console.debug 'Computing d3 hierarchy layout...'
hierarchy = d3.layout.hierarchy()
nodes = hierarchy(tree)
### this tree is unordered, we need a canonical ordering for it ###
console.debug 'Computing canonical sort...'
tree_utils.canonical_sort(tree)
### obtain the sequence of leaves ###
leaves = tree_utils.get_leaves(tree)
### VISUALIZATION ###
### compute the space-filling curve layout ###
console.debug 'Computing the Space-Filling Curve layout...'
scale = 3
sfc_layout.displace(leaves, sfc_layout.PEANO, scale, scale, 0)
### compute also the position of internal nodes ###
console.debug 'Computing the position of internal nodes...'
sfc_layout.displace_tree(tree)
console.debug 'Computing the jigsaw treemap...'
### compute all the internal nodes regions ###
jigsaw.treemap(tree, scale, jigsaw.SQUARE_CELL)
console.debug 'Computing label placement...'
jigsaw.hilbert_labels(tree, scale)
console.debug 'Drawing...'
### define the level zero region (the land) ###
defs = svg.append('defs')
defs.append('path')
.attr('id', 'land')
.attr('d', jigsaw.get_svg_path tree.region)
### faux land glow (using filters takes too much resources) ###
map.append('use')
.attr('class', 'land-glow-outer')
.attr('xlink:href', '#land')
map.append('use')
.attr('class', 'land-glow-inner')
.attr('xlink:href', '#land')
### draw the land border (behind boundaries) ###
map.append('use')
.attr('class', 'land-fill')
.attr('xlink:href', '#land')
### draw label bboxes ###
map.selectAll('.bbox')
.data(nodes.filter((d)->d.depth == 1))
.enter().append('rect')
.attr('class', 'bbox')
.attr('x', (d)->d.label_bbox.x)
.attr('y', (d)->d.label_bbox.y)
.attr('width', (d)->d.label_bbox.width)
.attr('height', (d)->d.label_bbox.height)
### draw boundaries ###
map.selectAll('.region')
.data(nodes.filter((d)->d.depth == 1))
.enter().append('path')
.attr('class', 'region')
.attr('d', (d) -> jigsaw.get_svg_path d.region)
.attr('stroke-width', '1px')
.attr('stroke', 'white')
### draw region labels ###
# cells2fontsize = d3.scale.pow()
# .exponent(0.4)
# .domain([1, leaves.length])
# .range([2,42])
LABEL_SCALE = 0.8
region_labels = map.selectAll('.region_label')
.data(nodes.filter((d)->d.depth == 1))
.enter().append('text')
.attr('class', 'region_label')
##.attr('font-size', (d) -> cells2fontsize(d.leaf_descendants.length))
.attr('dy', '0.35em')
# .attr('transform', (d) -> "translate(#{d.x},#{d.y})")
.text((d) -> d.label)
.attr('transform', (d) ->
bbox = this.getBBox()
bbox_aspect = bbox.width / bbox.height
lbbox = d.label_bbox
lbbox_aspect = lbbox.width / lbbox.height
rotate = bbox_aspect >= 1 and lbbox_aspect < 1 or bbox_aspect < 1 and lbbox_aspect >= 1
if rotate
lbbox_width = lbbox.height
lbbox_height = lbbox.width
else
lbbox_width = lbbox.width
lbbox_height = lbbox.height
w_ratio = lbbox_width / bbox.width
h_ratio = lbbox_height / bbox.height
ratio = Math.min(w_ratio, h_ratio)*LABEL_SCALE
return "translate(#{d.label_bbox.x+d.label_bbox.width/2},#{d.label_bbox.y+d.label_bbox.height/2}),scale(#{ratio}),rotate(#{if rotate then -90 else 0})"
)
#land {
vector-effect: non-scaling-stroke;
shape-rendering: crispEdges;
}
.land-glow-outer {
fill: none;
stroke: #eeeeee;
stroke-width: 16px;
}
.land-glow-inner {
fill: none;
stroke: #dddddd;
stroke-width: 8px;
}
.land-fill {
fill: white;
stroke: #444444;
stroke-width: 2px;
}
.region {
fill: none;
stroke: #444444;
stroke-width: 1px;
vector-effect: non-scaling-stroke;
shape-rendering: crispEdges;
}
.bbox {
fill: #fff373;
fill-opacity: 0.5;
shape-rendering: crispEdges;
display: none;
}
.selected:hover .bbox {
display: inline;
}
@font-face {
font-family: "Lacuna";
src: url("lacuna.ttf");
}
.region_label {
fill: #444444;
text-anchor: middle;
pointer-events: none;
font-family: "Lacuna";
-webkit-touch-callout: none;
-webkit-user-select: none;
-khtml-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
text-transform: capitalize;
font-size: 20px;
}
#land
vector-effect: non-scaling-stroke
shape-rendering: crispEdges
.land-glow-outer
fill: none
stroke: #EEE
stroke-width: 16px
.land-glow-inner
fill: none
stroke: #DDD
stroke-width: 8px
.land-fill
fill: white
stroke: #444
stroke-width: 2px
.region
fill: none
stroke: #444
stroke-width: 1px
vector-effect: non-scaling-stroke
shape-rendering: crispEdges
.bbox
fill: #FFF373
fill-opacity: 0.5
shape-rendering: crispEdges
display: none
.selected:hover .bbox
display: inline
@font-face
font-family: "Lacuna"
src: url("lacuna.ttf")
.region_label
fill: #444
text-anchor: middle
pointer-events: none
font-family: "Lacuna"
-webkit-touch-callout: none
-webkit-user-select: none
-khtml-user-select: none
-moz-user-select: none
-ms-user-select: none
user-select: none
text-transform: capitalize
font-size: 20px
window.jigsaw = {
hex_generate_svg_path: (scale) ->
a = scale/2
r = a / Math.sin(Math.PI/3)
return "M#{r} 0 L#{r/2} #{a} L#{-r/2} #{a} L#{-r} 0 L#{-r/2} #{-a} L#{r/2} #{-a} Z"
square_generate_svg_path: (scale) ->
a = scale/2
return "M#{-a} #{-a} L#{-a} #{a} L#{a} #{a} L#{a} #{-a} Z"
iso_generate_svg_path: (scale) ->
rx = scale*Math.sqrt(2)/2
ry = scale*Math.sqrt(2)/(2*Math.sqrt(3))
return "M#{0} #{-ry} L#{rx} #{0} L#{0} #{ry} L#{-rx} #{0} Z"
HEX_CELL: (node, scale) ->
a = scale/2
r = a / Math.sin(Math.PI/3)
region = [[{X:node.x+r, Y:node.y}, {X:node.x+r/2, Y:node.y+a}, {X:node.x-r/2, Y:node.y+a}, {X:node.x-r, Y:node.y}, {X:node.x-r/2, Y:node.y-a}, {X:node.x+r/2, Y:node.y-a}]]
return region
SQUARE_CELL: (node, scale) ->
a = scale/2
region = [[{X:node.x-a, Y:node.y-a}, {X:node.x-a, Y:node.y+a}, {X:node.x+a, Y:node.y+a}, {X:node.x+a, Y:node.y-a}]]
return region
ISO_CELL: (node, scale) ->
rx = scale*Math.sqrt(2)/2
ry = scale*Math.sqrt(2)/(2*Math.sqrt(3))
region = [[{X:node.x, Y:node.y-ry}, {X:node.x+rx, Y:node.y}, {X:node.x, Y:node.y+ry}, {X:node.x-rx, Y:node.y}]]
treemap: (node, scale, base) ->
if not node.children?
node.region = base(node, scale)
return node.region
children_paths = (jigsaw.treemap(child, scale, base) for child in node.children).reduce((a, d) -> a.concat(d))
upscale = 1000
ClipperLib.JS.ScaleUpPaths(children_paths, upscale)
cpr = new ClipperLib.Clipper()
cpr.AddPaths(children_paths, ClipperLib.PolyType.ptSubject, true)
node.region = new ClipperLib.Paths()
cpr.Execute(ClipperLib.ClipType.ctUnion, node.region, ClipperLib.PolyFillType.pftNonZero, ClipperLib.PolyFillType.pftNonZero)
ClipperLib.JS.ScaleDownPaths(children_paths, upscale)
ClipperLib.JS.ScaleDownPaths(node.region, upscale)
return node.region
### Converts Paths to SVG path string ###
### and scales down the coordinates ###
### from http://jsclipper.sourceforge.net/6.1.3.1/index.html?p=starter_boolean.html ###
get_svg_path: (paths, scale) ->
svgpath = ''
if not scale?
scale = 1
for path in paths
for p, i in path
if i is 0
svgpath += 'M'
else
svgpath += 'L'
svgpath += p.X/scale + ", " + p.Y/scale
svgpath += 'Z'
if svgpath is ''
svgpath = 'M0,0'
return svgpath
hilbert_labels: (node, scale) ->
### create a sort of bitmap of this node's cells ###
matrix = {}
for cell in node.leaf_descendants
if cell.ix not of matrix
matrix[cell.ix] = {}
matrix[cell.ix][cell.iy] = cell
### compute the matrix boundaries ###
min_ix = d3.min(node.leaf_descendants, (d)->d.ix)
max_ix = d3.max(node.leaf_descendants, (d)->d.ix)
min_iy = d3.min(node.leaf_descendants, (d)->d.iy)
max_iy = d3.max(node.leaf_descendants, (d)->d.iy)
### scan X to create tall boxes ###
x_boxes = []
for ix in [min_ix..max_ix]
x_boxes.push {}
for iy in [min_iy..max_iy]
last_box = x_boxes[x_boxes.length-1]
if ix of matrix and iy of matrix[ix]
if 'topleft' not of last_box
last_box.bottomright = last_box.topleft = matrix[ix][iy]
last_box.area = 1
else
last_box.bottomright = matrix[ix][iy]
last_box.area += 1
else if 'topleft' of last_box # this checks if last_box is not empty
x_boxes.push {}
### scan Y to create wide boxes ###
y_boxes = []
for iy in [min_iy..max_iy]
y_boxes.push {}
for ix in [min_ix..max_ix]
last_box = y_boxes[y_boxes.length-1]
if ix of matrix and iy of matrix[ix]
if 'topleft' not of last_box
last_box.topleft = matrix[ix][iy]
last_box.bottomright = matrix[ix][iy]
last_box.area = 1
else
last_box.bottomright = matrix[ix][iy]
last_box.area += 1
else if 'topleft' of last_box # this checks if last_box is not empty
y_boxes.push {}
# y_boxes = []
# for iy in [min_iy..max_iy]
# y_boxes.push []
# for ix in [min_ix..max_ix]
# if ix of matrix and iy of matrix[ix]
# y_boxes[y_boxes.length-1].push matrix[ix][iy]
# else if y_boxes[y_boxes.length-1].length > 0
# y_boxes.push []
### grow boxes along X ###
for box in x_boxes
if not box.topleft? # FIXME there are some holes into the structure
continue
grow = true
original_area = box.area
while grow
ixg = box.bottomright.ix+1
for iyg in [box.topleft.iy..box.bottomright.iy]
grow = ixg of matrix and iyg of matrix[ixg]
if not grow
break
if grow
box.bottomright = matrix[ixg][box.bottomright.iy]
box.area += original_area
### grow boxes along Y ###
for box in y_boxes
if not box.topleft? # FIXME there are some holes into the structure
continue
grow = true
original_area = box.area
while grow
iyg = box.bottomright.iy+1
for ixg in [box.topleft.ix..box.bottomright.ix]
grow = ixg of matrix and iyg of matrix[ixg]
if not grow
break
if grow
box.bottomright = matrix[box.bottomright.ix][iyg]
box.area += original_area
### select the biggest box ###
boxes = x_boxes.concat(y_boxes)
max_area = d3.max(boxes,(b)->b.area)
box = boxes.filter((d)->d.area == max_area)[0]
### convert into x,y coordinates ###
min_x = box.topleft.x-scale/2
max_x = box.bottomright.x+scale/2
min_y = box.topleft.y-scale/2
max_y = box.bottomright.y+scale/2
node.label_bbox = {
x: min_x,
y: min_y,
width: max_x-min_x,
height: max_y-min_y
}
if node.children?
for child in node.children
jigsaw.hilbert_labels(child, scale)
}(function() {
window.jigsaw = {
hex_generate_svg_path: function(scale) {
var a, r;
a = scale / 2;
r = a / Math.sin(Math.PI / 3);
return "M" + r + " 0 L" + (r / 2) + " " + a + " L" + (-r / 2) + " " + a + " L" + (-r) + " 0 L" + (-r / 2) + " " + (-a) + " L" + (r / 2) + " " + (-a) + " Z";
},
square_generate_svg_path: function(scale) {
var a;
a = scale / 2;
return "M" + (-a) + " " + (-a) + " L" + (-a) + " " + a + " L" + a + " " + a + " L" + a + " " + (-a) + " Z";
},
iso_generate_svg_path: function(scale) {
var rx, ry;
rx = scale * Math.sqrt(2) / 2;
ry = scale * Math.sqrt(2) / (2 * Math.sqrt(3));
return "M" + 0 + " " + (-ry) + " L" + rx + " " + 0 + " L" + 0 + " " + ry + " L" + (-rx) + " " + 0 + " Z";
},
HEX_CELL: function(node, scale) {
var a, r, region;
a = scale / 2;
r = a / Math.sin(Math.PI / 3);
region = [
[
{
X: node.x + r,
Y: node.y
}, {
X: node.x + r / 2,
Y: node.y + a
}, {
X: node.x - r / 2,
Y: node.y + a
}, {
X: node.x - r,
Y: node.y
}, {
X: node.x - r / 2,
Y: node.y - a
}, {
X: node.x + r / 2,
Y: node.y - a
}
]
];
return region;
},
SQUARE_CELL: function(node, scale) {
var a, region;
a = scale / 2;
region = [
[
{
X: node.x - a,
Y: node.y - a
}, {
X: node.x - a,
Y: node.y + a
}, {
X: node.x + a,
Y: node.y + a
}, {
X: node.x + a,
Y: node.y - a
}
]
];
return region;
},
ISO_CELL: function(node, scale) {
var region, rx, ry;
rx = scale * Math.sqrt(2) / 2;
ry = scale * Math.sqrt(2) / (2 * Math.sqrt(3));
return region = [
[
{
X: node.x,
Y: node.y - ry
}, {
X: node.x + rx,
Y: node.y
}, {
X: node.x,
Y: node.y + ry
}, {
X: node.x - rx,
Y: node.y
}
]
];
},
treemap: function(node, scale, base) {
var child, children_paths, cpr, upscale;
if (!(node.children != null)) {
node.region = base(node, scale);
return node.region;
}
children_paths = ((function() {
var _i, _len, _ref, _results;
_ref = node.children;
_results = [];
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
child = _ref[_i];
_results.push(jigsaw.treemap(child, scale, base));
}
return _results;
})()).reduce(function(a, d) {
return a.concat(d);
});
upscale = 1000;
ClipperLib.JS.ScaleUpPaths(children_paths, upscale);
cpr = new ClipperLib.Clipper();
cpr.AddPaths(children_paths, ClipperLib.PolyType.ptSubject, true);
node.region = new ClipperLib.Paths();
cpr.Execute(ClipperLib.ClipType.ctUnion, node.region, ClipperLib.PolyFillType.pftNonZero, ClipperLib.PolyFillType.pftNonZero);
ClipperLib.JS.ScaleDownPaths(children_paths, upscale);
ClipperLib.JS.ScaleDownPaths(node.region, upscale);
return node.region;
},
/* Converts Paths to SVG path string
*/
/* and scales down the coordinates
*/
/* from http://jsclipper.sourceforge.net/6.1.3.1/index.html?p=starter_boolean.html
*/
get_svg_path: function(paths, scale) {
var i, p, path, svgpath, _i, _len, _len2;
svgpath = '';
if (!(scale != null)) scale = 1;
for (_i = 0, _len = paths.length; _i < _len; _i++) {
path = paths[_i];
for (i = 0, _len2 = path.length; i < _len2; i++) {
p = path[i];
if (i === 0) {
svgpath += 'M';
} else {
svgpath += 'L';
}
svgpath += p.X / scale + ", " + p.Y / scale;
}
svgpath += 'Z';
}
if (svgpath === '') svgpath = 'M0,0';
return svgpath;
},
hilbert_labels: function(node, scale) {
/* create a sort of bitmap of this node's cells
*/
var box, boxes, cell, child, grow, ix, ixg, iy, iyg, last_box, matrix, max_area, max_ix, max_iy, max_x, max_y, min_ix, min_iy, min_x, min_y, original_area, x_boxes, y_boxes, _i, _j, _k, _l, _len, _len2, _len3, _len4, _ref, _ref2, _ref3, _ref4, _ref5, _ref6, _results;
matrix = {};
_ref = node.leaf_descendants;
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
cell = _ref[_i];
if (!(cell.ix in matrix)) matrix[cell.ix] = {};
matrix[cell.ix][cell.iy] = cell;
}
/* compute the matrix boundaries
*/
min_ix = d3.min(node.leaf_descendants, function(d) {
return d.ix;
});
max_ix = d3.max(node.leaf_descendants, function(d) {
return d.ix;
});
min_iy = d3.min(node.leaf_descendants, function(d) {
return d.iy;
});
max_iy = d3.max(node.leaf_descendants, function(d) {
return d.iy;
});
/* scan X to create tall boxes
*/
x_boxes = [];
for (ix = min_ix; min_ix <= max_ix ? ix <= max_ix : ix >= max_ix; min_ix <= max_ix ? ix++ : ix--) {
x_boxes.push({});
for (iy = min_iy; min_iy <= max_iy ? iy <= max_iy : iy >= max_iy; min_iy <= max_iy ? iy++ : iy--) {
last_box = x_boxes[x_boxes.length - 1];
if (ix in matrix && iy in matrix[ix]) {
if (!('topleft' in last_box)) {
last_box.bottomright = last_box.topleft = matrix[ix][iy];
last_box.area = 1;
} else {
last_box.bottomright = matrix[ix][iy];
last_box.area += 1;
}
} else if ('topleft' in last_box) {
x_boxes.push({});
}
}
}
/* scan Y to create wide boxes
*/
y_boxes = [];
for (iy = min_iy; min_iy <= max_iy ? iy <= max_iy : iy >= max_iy; min_iy <= max_iy ? iy++ : iy--) {
y_boxes.push({});
for (ix = min_ix; min_ix <= max_ix ? ix <= max_ix : ix >= max_ix; min_ix <= max_ix ? ix++ : ix--) {
last_box = y_boxes[y_boxes.length - 1];
if (ix in matrix && iy in matrix[ix]) {
if (!('topleft' in last_box)) {
last_box.topleft = matrix[ix][iy];
last_box.bottomright = matrix[ix][iy];
last_box.area = 1;
} else {
last_box.bottomright = matrix[ix][iy];
last_box.area += 1;
}
} else if ('topleft' in last_box) {
y_boxes.push({});
}
}
}
/* grow boxes along X
*/
for (_j = 0, _len2 = x_boxes.length; _j < _len2; _j++) {
box = x_boxes[_j];
if (!(box.topleft != null)) continue;
grow = true;
original_area = box.area;
while (grow) {
ixg = box.bottomright.ix + 1;
for (iyg = _ref2 = box.topleft.iy, _ref3 = box.bottomright.iy; _ref2 <= _ref3 ? iyg <= _ref3 : iyg >= _ref3; _ref2 <= _ref3 ? iyg++ : iyg--) {
grow = ixg in matrix && iyg in matrix[ixg];
if (!grow) break;
}
if (grow) {
box.bottomright = matrix[ixg][box.bottomright.iy];
box.area += original_area;
}
}
}
/* grow boxes along Y
*/
for (_k = 0, _len3 = y_boxes.length; _k < _len3; _k++) {
box = y_boxes[_k];
if (!(box.topleft != null)) continue;
grow = true;
original_area = box.area;
while (grow) {
iyg = box.bottomright.iy + 1;
for (ixg = _ref4 = box.topleft.ix, _ref5 = box.bottomright.ix; _ref4 <= _ref5 ? ixg <= _ref5 : ixg >= _ref5; _ref4 <= _ref5 ? ixg++ : ixg--) {
grow = ixg in matrix && iyg in matrix[ixg];
if (!grow) break;
}
if (grow) {
box.bottomright = matrix[box.bottomright.ix][iyg];
box.area += original_area;
}
}
}
/* select the biggest box
*/
boxes = x_boxes.concat(y_boxes);
max_area = d3.max(boxes, function(b) {
return b.area;
});
box = boxes.filter(function(d) {
return d.area === max_area;
})[0];
/* convert into x,y coordinates
*/
min_x = box.topleft.x - scale / 2;
max_x = box.bottomright.x + scale / 2;
min_y = box.topleft.y - scale / 2;
max_y = box.bottomright.y + scale / 2;
node.label_bbox = {
x: min_x,
y: min_y,
width: max_x - min_x,
height: max_y - min_y
};
if (node.children != null) {
_ref6 = node.children;
_results = [];
for (_l = 0, _len4 = _ref6.length; _l < _len4; _l++) {
child = _ref6[_l];
_results.push(jigsaw.hilbert_labels(child, scale));
}
return _results;
}
}
};
}).call(this);
### FIXME update this code to the optimized version ###
### compute a Lindenmayer system given an axiom, a number of steps and rules ###
fractalize = (config) ->
input = config.axiom
for i in [0...config.steps]
output = ''
for char in input
if char of config.rules
output += config.rules[char]
else
output += char
input = output
return output
### execute a curve string and return all the generated points ###
execute = (curve_string, angle, scale_x, scale_y, orientation) ->
points = [{x: 0, y: 0}]
for char in curve_string
if char == '+'
orientation += angle
else if char == '-'
orientation -= angle
else if char == 'F'
last_point = points[points.length-1]
points.push {
x: last_point.x + scale_x * Math.cos(orientation),
y: last_point.y + scale_y * Math.sin(orientation)
}
return points
### execute a curve string and return all the generated points ###
### returns integer coordinates (works only for 0-oriented, clockwise square tilings) ###
int_execute = (curve_string) ->
points = [{ix: 0, iy: 0}]
dirs = [
[+1,0],
[0,+1],
[-1,0],
[0,-1]
]
dir_i = 0
for char in curve_string
if char == '+'
dir_i = (dir_i+1) % dirs.length
else if char == '-'
dir_i = if dir_i is 0 then dirs.length-1 else dir_i-1
else if char == 'F'
last_point = points[points.length-1]
points.push {
ix: last_point.ix + dirs[dir_i][0],
iy: last_point.iy + dirs[dir_i][1]
}
return points
### custom base for logarithm (see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/log) ###
base_log = (x, base) -> Math.log(x) / Math.log(base)
window.sfc_layout = {
GOSPER: {
tiling: 'hex'
base: 7
angle: Math.PI/3
axiom: 'A'
rules:
A: 'A+BF++BF-FA--FAFA-BF+'
B: '-FA+BFBF++BF+FA--FA-B'
}
HILBERT: {
tiling: 'square'
base: 4
angle: Math.PI/2
axiom: 'A'
rules:
A: '-BF+AFA+FB-'
B: '+AF-BFB-FA+'
}
PEANO: {
tiling: 'square'
base: 9
angle: Math.PI/2
axiom: 'L'
rules:
L: 'LFRFL-F-RFLFR+F+LFRFL'
R: 'RFLFR+F+LFRFL-F-RFLFR'
}
displace: (seq, curve_cfg, scale_x, scale_y, orientation) ->
scale_x = if scale_x? then scale_x else 10
scale_y = if scale_y? then scale_y else 10
orientation = if orientation? then orientation else 0
### create the minimal curve that can accommodate the whole sequence ###
steps = Math.ceil(base_log(seq.length, curve_cfg.base))
### generate the Lindenmayer system string for the requested curve ###
curve_string = fractalize
steps: steps
axiom: curve_cfg.axiom
rules: curve_cfg.rules
### execute the string, producing the actual points of the curve ###
curve = execute(curve_string, curve_cfg.angle, scale_x, scale_y, orientation)
### stores the coordinates in the given sequence ###
for [d,point] in zip(seq, curve)
d.x = point.x
d.y = point.y
### center the layout coordinates in the center of its bounding box ###
max_x = d3.max(seq, (d)->d.x)
max_y = d3.max(seq, (d)->d.y)
min_x = d3.min(seq, (d)->d.x)
min_y = d3.min(seq, (d)->d.y)
for d in seq
d.x -= (max_x+min_x)/2
d.y -= (max_y+min_y)/2
### if the curve uses a square tiling, also compute integer coordinates ###
if curve_cfg.tiling is 'square'
int_curve = int_execute(curve_string)
for [d,point] in zip(seq, int_curve)
d.ix = point.ix
d.iy = point.iy
### recursively assign positions to internal nodes too. also compute leaf descendants ###
displace_tree: (node) ->
if not node.children?
### this is a leaf ###
node.leaf_descendants = [node]
return node.leaf_descendants
### an internal node's position is the centroid of its leaf descendants ###
node.leaf_descendants = (sfc_layout.displace_tree(c) for c in node.children).reduce((a, d) -> a.concat(d))
node.x = d3.mean(node.leaf_descendants, (d)->d.x)
node.y = d3.mean(node.leaf_descendants, (d)->d.y)
### pass descendants up to the hierarchy ###
return node.leaf_descendants
}/* FIXME update this code to the optimized version
*/
/* compute a Lindenmayer system given an axiom, a number of steps and rules
*/
(function() {
var base_log, execute, fractalize, int_execute;
fractalize = function(config) {
var char, i, input, output, _i, _len, _ref;
input = config.axiom;
for (i = 0, _ref = config.steps; 0 <= _ref ? i < _ref : i > _ref; 0 <= _ref ? i++ : i--) {
output = '';
for (_i = 0, _len = input.length; _i < _len; _i++) {
char = input[_i];
if (char in config.rules) {
output += config.rules[char];
} else {
output += char;
}
}
input = output;
}
return output;
};
/* execute a curve string and return all the generated points
*/
execute = function(curve_string, angle, scale_x, scale_y, orientation) {
var char, last_point, points, _i, _len;
points = [
{
x: 0,
y: 0
}
];
for (_i = 0, _len = curve_string.length; _i < _len; _i++) {
char = curve_string[_i];
if (char === '+') {
orientation += angle;
} else if (char === '-') {
orientation -= angle;
} else if (char === 'F') {
last_point = points[points.length - 1];
points.push({
x: last_point.x + scale_x * Math.cos(orientation),
y: last_point.y + scale_y * Math.sin(orientation)
});
}
}
return points;
};
/* execute a curve string and return all the generated points
*/
/* returns integer coordinates (works only for 0-oriented, clockwise square tilings)
*/
int_execute = function(curve_string) {
var char, dir_i, dirs, last_point, points, _i, _len;
points = [
{
ix: 0,
iy: 0
}
];
dirs = [[+1, 0], [0, +1], [-1, 0], [0, -1]];
dir_i = 0;
for (_i = 0, _len = curve_string.length; _i < _len; _i++) {
char = curve_string[_i];
if (char === '+') {
dir_i = (dir_i + 1) % dirs.length;
} else if (char === '-') {
dir_i = dir_i === 0 ? dirs.length - 1 : dir_i - 1;
} else if (char === 'F') {
last_point = points[points.length - 1];
points.push({
ix: last_point.ix + dirs[dir_i][0],
iy: last_point.iy + dirs[dir_i][1]
});
}
}
return points;
};
/* custom base for logarithm (see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/log)
*/
base_log = function(x, base) {
return Math.log(x) / Math.log(base);
};
window.sfc_layout = {
GOSPER: {
tiling: 'hex',
base: 7,
angle: Math.PI / 3,
axiom: 'A',
rules: {
A: 'A+BF++BF-FA--FAFA-BF+',
B: '-FA+BFBF++BF+FA--FA-B'
}
},
HILBERT: {
tiling: 'square',
base: 4,
angle: Math.PI / 2,
axiom: 'A',
rules: {
A: '-BF+AFA+FB-',
B: '+AF-BFB-FA+'
}
},
PEANO: {
tiling: 'square',
base: 9,
angle: Math.PI / 2,
axiom: 'L',
rules: {
L: 'LFRFL-F-RFLFR+F+LFRFL',
R: 'RFLFR+F+LFRFL-F-RFLFR'
}
},
displace: function(seq, curve_cfg, scale_x, scale_y, orientation) {
var curve, curve_string, d, int_curve, max_x, max_y, min_x, min_y, point, steps, _i, _j, _k, _len, _len2, _len3, _ref, _ref2, _ref3, _ref4, _results;
scale_x = scale_x != null ? scale_x : 10;
scale_y = scale_y != null ? scale_y : 10;
orientation = orientation != null ? orientation : 0;
/* create the minimal curve that can accommodate the whole sequence
*/
steps = Math.ceil(base_log(seq.length, curve_cfg.base));
/* generate the Lindenmayer system string for the requested curve
*/
curve_string = fractalize({
steps: steps,
axiom: curve_cfg.axiom,
rules: curve_cfg.rules
});
/* execute the string, producing the actual points of the curve
*/
curve = execute(curve_string, curve_cfg.angle, scale_x, scale_y, orientation);
/* stores the coordinates in the given sequence
*/
_ref = zip(seq, curve);
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
_ref2 = _ref[_i], d = _ref2[0], point = _ref2[1];
d.x = point.x;
d.y = point.y;
}
/* center the layout coordinates in the center of its bounding box
*/
max_x = d3.max(seq, function(d) {
return d.x;
});
max_y = d3.max(seq, function(d) {
return d.y;
});
min_x = d3.min(seq, function(d) {
return d.x;
});
min_y = d3.min(seq, function(d) {
return d.y;
});
for (_j = 0, _len2 = seq.length; _j < _len2; _j++) {
d = seq[_j];
d.x -= (max_x + min_x) / 2;
d.y -= (max_y + min_y) / 2;
}
/* if the curve uses a square tiling, also compute integer coordinates
*/
if (curve_cfg.tiling === 'square') {
int_curve = int_execute(curve_string);
_ref3 = zip(seq, int_curve);
_results = [];
for (_k = 0, _len3 = _ref3.length; _k < _len3; _k++) {
_ref4 = _ref3[_k], d = _ref4[0], point = _ref4[1];
d.ix = point.ix;
_results.push(d.iy = point.iy);
}
return _results;
}
},
/* recursively assign positions to internal nodes too. also compute leaf descendants
*/
displace_tree: function(node) {
var c;
if (!(node.children != null)) {
/* this is a leaf
*/
node.leaf_descendants = [node];
return node.leaf_descendants;
}
/* an internal node's position is the centroid of its leaf descendants
*/
node.leaf_descendants = ((function() {
var _i, _len, _ref, _results;
_ref = node.children;
_results = [];
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
c = _ref[_i];
_results.push(sfc_layout.displace_tree(c));
}
return _results;
})()).reduce(function(a, d) {
return a.concat(d);
});
node.x = d3.mean(node.leaf_descendants, function(d) {
return d.x;
});
node.y = d3.mean(node.leaf_descendants, function(d) {
return d.y;
});
/* pass descendants up to the hierarchy
*/
return node.leaf_descendants;
}
};
}).call(this);
tcmp = (a,b) ->
children_a = (if a.children? then a.children else [])
children_b = (if b.children? then b.children else [])
for [ai, bi] in zip(children_a,children_b)
ci = tcmp(ai,bi)
if ci isnt 0
return ci
return children_b.length-children_a.length
rsort = (t) ->
children = (if t.children? then t.children else [])
for c in children
rsort(c)
children.sort(tcmp)
### random name generation ###
syllables = ['bi','bo','bu','ta','se','tri','su','ke','ka','flo','ko','pi','pe','no','go','zo','fu','fo','si','pa','ar','es','i','kya','kyu','fle','o','ne','na','le','lu','ma','an']
randlen = () -> 2+Math.floor(Math.random()*4)
randsy = () -> syllables[Math.floor(Math.random()*syllables.length)]
namegen = () -> (randsy() for j in [0...randlen()]).join('')
window.tree_utils = {
### sort the given unordered tree using a canonical ordering ###
### see Constant time generation of free trees - Wright et al. 1986 ###
canonical_sort: (tree) ->
rsort(tree)
### return the ordered sequence of leaves of a given tree ###
get_leaves: (tree) ->
seq = []
parse_leaves = (node) ->
if not node.children?
seq.push node
else
for c in node.children
parse_leaves(c)
parse_leaves(tree)
return seq
### compute the height of each node ###
compute_height: (node) ->
if not node.children?
node.height = 1
else
node.height = d3.max((tree_utils.compute_height(c) for c in node.children)) + 1
return node.height
### generate a random tree ###
random_tree: (d, MAX_D, MAX_N) ->
### return a tree with maximum depth MAX_D that branches with probability p at most N times for each internal node. p starts from 1 and decreases linearly with d, reaching zero at MAX_D ###
### this still seems to be necessary to avoid infinte recursion (floating point precision?) ###
return {name: namegen()} if d is MAX_D
p = (MAX_D-d)/MAX_D
### if the tree branches, at least one branch is made ###
n = Math.floor(Math.random()*MAX_N)+1
children = []
for i in [0...n]
if p >= Math.random()
children.push tree_utils.random_tree(d+1, MAX_D, MAX_N)
else
children.push {name: namegen()}
return {
children: children,
name: namegen()
}
}(function() {
var namegen, randlen, randsy, rsort, syllables, tcmp;
tcmp = function(a, b) {
var ai, bi, children_a, children_b, ci, _i, _len, _ref, _ref2;
children_a = (a.children != null ? a.children : []);
children_b = (b.children != null ? b.children : []);
_ref = zip(children_a, children_b);
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
_ref2 = _ref[_i], ai = _ref2[0], bi = _ref2[1];
ci = tcmp(ai, bi);
if (ci !== 0) return ci;
}
return children_b.length - children_a.length;
};
rsort = function(t) {
var c, children, _i, _len;
children = (t.children != null ? t.children : []);
for (_i = 0, _len = children.length; _i < _len; _i++) {
c = children[_i];
rsort(c);
}
return children.sort(tcmp);
};
/* random name generation
*/
syllables = ['bi', 'bo', 'bu', 'ta', 'se', 'tri', 'su', 'ke', 'ka', 'flo', 'ko', 'pi', 'pe', 'no', 'go', 'zo', 'fu', 'fo', 'si', 'pa', 'ar', 'es', 'i', 'kya', 'kyu', 'fle', 'o', 'ne', 'na', 'le', 'lu', 'ma', 'an'];
randlen = function() {
return 2 + Math.floor(Math.random() * 4);
};
randsy = function() {
return syllables[Math.floor(Math.random() * syllables.length)];
};
namegen = function() {
var j;
return ((function() {
var _ref, _results;
_results = [];
for (j = 0, _ref = randlen(); 0 <= _ref ? j < _ref : j > _ref; 0 <= _ref ? j++ : j--) {
_results.push(randsy());
}
return _results;
})()).join('');
};
window.tree_utils = {
/* sort the given unordered tree using a canonical ordering
*/
/* see Constant time generation of free trees - Wright et al. 1986
*/
canonical_sort: function(tree) {
return rsort(tree);
},
/* return the ordered sequence of leaves of a given tree
*/
get_leaves: function(tree) {
var parse_leaves, seq;
seq = [];
parse_leaves = function(node) {
var c, _i, _len, _ref, _results;
if (!(node.children != null)) {
return seq.push(node);
} else {
_ref = node.children;
_results = [];
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
c = _ref[_i];
_results.push(parse_leaves(c));
}
return _results;
}
};
parse_leaves(tree);
return seq;
},
/* compute the height of each node
*/
compute_height: function(node) {
var c;
if (!(node.children != null)) {
node.height = 1;
} else {
node.height = d3.max((function() {
var _i, _len, _ref, _results;
_ref = node.children;
_results = [];
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
c = _ref[_i];
_results.push(tree_utils.compute_height(c));
}
return _results;
})()) + 1;
}
return node.height;
},
/* generate a random tree
*/
random_tree: function(d, MAX_D, MAX_N) {
/* return a tree with maximum depth MAX_D that branches with probability p at most N times for each internal node. p starts from 1 and decreases linearly with d, reaching zero at MAX_D
*/
/* this still seems to be necessary to avoid infinte recursion (floating point precision?)
*/
var children, i, n, p;
if (d === MAX_D) {
return {
name: namegen()
};
}
p = (MAX_D - d) / MAX_D;
/* if the tree branches, at least one branch is made
*/
n = Math.floor(Math.random() * MAX_N) + 1;
children = [];
for (i = 0; 0 <= n ? i < n : i > n; 0 <= n ? i++ : i--) {
if (p >= Math.random()) {
children.push(tree_utils.random_tree(d + 1, MAX_D, MAX_N));
} else {
children.push({
name: namegen()
});
}
}
return {
children: children,
name: namegen()
};
}
};
}).call(this);
### python-like zip ###
window.zip = () ->
args = [].slice.call(arguments)
shortest = if args.length == 0 then [] else args.reduce(((a,b) ->
if a.length < b.length then a else b
))
return shortest.map(((_,i) ->
args.map((array) -> array[i])
))/* python-like zip
*/
(function() {
window.zip = function() {
var args, shortest;
args = [].slice.call(arguments);
shortest = args.length === 0 ? [] : args.reduce((function(a, b) {
if (a.length < b.length) {
return a;
} else {
return b;
}
}));
return shortest.map((function(_, i) {
return args.map(function(array) {
return array[i];
});
}));
};
}).call(this);