A label placement algorithm for Hilbert treemaps. For each region, a label that do not overlap the boundaries is drawn. The label is placed inside the largest area rectangle that can be found within the region. Use the mouse to zoom and pan, and click the map to display the largest rectangle of each region.
The algorithm works in integer coordinates, and proceeds as follows: First, the X axis is scanned to find contiguous sequences of cells along the Y axis (tall boxes). Each box is then enlarged along X until it finds a boundary (even if a one-cell-wide hole is found). Then the process is repeated scanning the Y axis, producing wide boxes then enlarging them along Y.
The largest box is then chosed as the largest area rectangle (shown in yellow if you click on the map), that is used to fit the text’s bounding box.
The implementation is very simplistic and unoptimized, and works only for polygonal regions composed of contiguous cells of a square tiling (as is the case for Hilbert regions). More general and rigorous approaches to the problem of finding the Largest Rectangle within a polygon can be found in Daniels 1997 (found in this StackOverflow post).
Using a web font (such in this case) can slightly alter the placement. It seems that if the font is not already loaded when the original text’s bounding box is computed, a different font is used for the computation, resulting in a different bounding box.
/* 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.HILBERT, 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 hilbert 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 Hilbert 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.HILBERT, 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 hilbert 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+'
}
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+'
}
},
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);