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.
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 ### | |
# 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; | |
} |
<!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="http://d3js.org/d3.v3.min.js"></script> | |
<script src="http://jsclipper.sourceforge.net/6.1.3.1/clipper.js"></script> | |
<script src="http://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 | |
*/ | |
(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); |
#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); |