This example combines a Hilbert jigsaw treemap with an area encoding: Each cell (a class of the flare software package) is scaled accordingly to its size property. This is different from the standard approach of treemaps, that either uses the leaves’ size to affect the whole map, or chooses not to display size information at all (all leaves have a unit area).
(function() {
var height, map, svg, vis, width, zoom;
width = 960;
height = 500;
/* create the SVG
*/
svg = d3.select('body').append('svg').attr('width', width).attr('height', height);
vis = svg.append('g');
map = vis.append('g').attr('transform', "translate(" + (width / 2) + "," + (height / 2) + ")");
/* define a zoom behavior
*/
zoom = d3.behavior.zoom().scaleExtent([1, 10]).on('zoom', function() {
/* whenever the user zooms,
*/
/* modify translation and scale of the zoom group accordingly
*/ return vis.attr('transform', "translate(" + (zoom.translate()) + ")scale(" + (zoom.scale()) + ")");
});
/* bind the zoom behavior to the main SVG
*/
svg.call(zoom);
/* read flare data
*/
d3.json('flare-imports.json', function(data) {
/* package tree
*/
var cells2fontsize, defs, hierarchy, leaves, nodes, scale, size2cellscale, tree;
tree = flare_reader.tree(data);
hierarchy = d3.layout.hierarchy();
nodes = hierarchy(tree);
/* imports links
*/
/* this tree is unordered, we need a canonical ordering for it
*/
tree_utils.canonical_sort(tree);
/* obtain the sequence of leaves
*/
leaves = tree_utils.get_leaves(tree);
/* compute the subtree height for each node
*/
tree_utils.compute_height(tree);
/* VISUALIZATION
*/
/* compute the space-filling curve layout
*/
scale = 26;
sfc_layout.displace(leaves, sfc_layout.HILBERT, scale, 0);
/* compute also the position of internal nodes
*/
sfc_layout.displace_tree(tree);
/* define a bundle layout
*/
/* define a color scale for leaf depth
*/
/* define a thickness scale for region height
*/
/* translate size to cell scale
*/
size2cellscale = d3.scale.sqrt().domain([
0, d3.max(nodes, function(d) {
return d.size;
})
]).range([0, scale]);
/* translate cells to label font size
*/
cells2fontsize = d3.scale.pow().exponent(0.3).domain([1, leaves.length]).range([4, 80]);
/* compute all the internal nodes regions
*/
jigsaw.treemap(tree, scale, jigsaw.SQUARE_CELL);
/* 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 cells)
*/
map.append('use').attr('class', 'land-fill').attr('xlink:href', '#land');
/* draw labels
*/
map.selectAll('.label').data(nodes.filter(function(d) {
return d.depth === 1;
})).enter().append('text').attr('class', 'label').attr('font-size', function(d) {
return cells2fontsize(d.leaf_descendants.length);
}).attr('dy', '0.35em').attr('transform', function(d) {
return "translate(" + d.x + "," + d.y + ")";
}).text(function(d) {
return d.name.split('.').reverse()[0];
}).attr('opacity', 0.2);
/* draw the cells
*/
map.selectAll('.cell').data(leaves).enter().append('path').attr('class', 'cell').attr('d', function(d) {
return jigsaw.square_generate_svg_path(size2cellscale(d.size));
}).attr('transform', function(d) {
return "translate(" + d.x + "," + d.y + ")";
}).attr('fill', 'orange');
/* draw the level one 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', '0.2px');
/* draw the graph links
*/
/* draw the leaf labels
*/
return map.selectAll('.leaf_label').data(leaves).enter().append('text').attr('class', 'leaf_label').attr('font-size', '2.5').attr('dy', '0.35em').attr('transform', function(d) {
return "translate(" + d.x + "," + d.y + ")";
}).text(function(d) {
return d.name.split('.').reverse()[0];
});
});
}).call(this);
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Hilbert treemap (area encoding)</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="zip.js"></script>
<script src="flare_reader.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>### read flare-imports data and provide it in form of tree (for the package hierarchy) and links (for the imports) ###
### code adapted from http://bl.ocks.org/mbostock/4341134 ###
`
window.flare_reader = {
// Lazily construct the package hierarchy from class names.
tree: function(classes) {
var map = {};
function find(name, data) {
var node = map[name], i;
if (!node) {
node = map[name] = data || {name: name, children: []};
if (name.length) {
node.parent = find(name.substring(0, i = name.lastIndexOf(".")));
node.parent.children.push(node);
node.key = name.substring(i + 1);
}
}
return node;
}
classes.forEach(function(d) {
find(d.name, d);
});
var flare = map['flare'];
delete flare.parent; // CHANGED root node is not ""
return flare;
},
// Return a list of imports for the given array of nodes.
imports: function(nodes) {
var map = {},
imports = [];
// Compute a map from name to node.
nodes.forEach(function(d) {
map[d.name] = d;
});
// For each import, construct a link from the source to target node.
nodes.forEach(function(d) {
if (d.imports) d.imports.forEach(function(i) {
imports.push({source: map[d.name], target: map[i]});
});
});
return imports;
}
};
`
/* read flare-imports data and provide it in form of tree (for the package hierarchy) and links (for the imports)
*/
/* code adapted from http://bl.ocks.org/mbostock/4341134
*/
(function() {
window.flare_reader = {
// Lazily construct the package hierarchy from class names.
tree: function(classes) {
var map = {};
function find(name, data) {
var node = map[name], i;
if (!node) {
node = map[name] = data || {name: name, children: []};
if (name.length) {
node.parent = find(name.substring(0, i = name.lastIndexOf(".")));
node.parent.children.push(node);
node.key = name.substring(i + 1);
}
}
return node;
}
classes.forEach(function(d) {
find(d.name, d);
});
var flare = map['flare'];
delete flare.parent; // CHANGED root node is not ""
return flare;
},
// Return a list of imports for the given array of nodes.
imports: function(nodes) {
var map = {},
imports = [];
// Compute a map from name to node.
nodes.forEach(function(d) {
map[d.name] = d;
});
// For each import, construct a link from the source to target node.
nodes.forEach(function(d) {
if (d.imports) d.imports.forEach(function(i) {
imports.push({source: map[d.name], target: map[i]});
});
});
return imports;
}
};
;
}).call(this);
width = 960
height = 500
### create the SVG ###
svg = d3.select('body').append('svg')
.attr('width', width)
.attr('height', height)
vis = svg.append('g')
map = vis.append('g')
.attr('transform', "translate(#{width/2},#{height/2})")
### define a zoom behavior ###
zoom = d3.behavior.zoom()
.scaleExtent([1,10]) # min-max zoom
.on 'zoom', () ->
### whenever the user zooms, ###
### modify translation and scale of the zoom group accordingly ###
vis.attr('transform', "translate(#{zoom.translate()})scale(#{zoom.scale()})")
### bind the zoom behavior to the main SVG ###
svg.call(zoom)
### read flare data ###
d3.json 'flare-imports.json', (data) ->
### package tree ###
tree = flare_reader.tree(data)
hierarchy = d3.layout.hierarchy()
nodes = hierarchy(tree)
### imports links ###
# graph_links = flare_reader.imports(nodes)
### this tree is unordered, we need a canonical ordering for it ###
tree_utils.canonical_sort(tree)
### obtain the sequence of leaves ###
leaves = tree_utils.get_leaves(tree)
### compute the subtree height for each node ###
tree_utils.compute_height(tree)
### VISUALIZATION ###
### compute the space-filling curve layout ###
scale = 26
sfc_layout.displace(leaves, sfc_layout.HILBERT, scale, 0)
### compute also the position of internal nodes ###
sfc_layout.displace_tree(tree)
### define a bundle layout ###
# bundle = d3.layout.bundle()
# bundles = bundle(graph_links)
# link_generator = d3.svg.line()
# .interpolate('bundle')
# .tension(0.99)
# .x((d) -> d.x)
# .y((d) -> d.y)
### define a color scale for leaf depth ###
# depth_color = d3.scale.linear()
# .domain([1, d3.max(leaves,(d)->d.depth)])
# .range(['#FFF7DB', '#F0A848'])
# .interpolate(d3.interpolateHcl)
### define a thickness scale for region height ###
# height2thickness = d3.scale.linear()
# .domain([1, tree.height])
# .range([0.001, 1])
### translate size to cell scale ###
size2cellscale = d3.scale.sqrt()
.domain([0, d3.max(nodes,(d)->d.size)])
.range([0,scale])
### translate cells to label font size ###
cells2fontsize = d3.scale.pow()
.exponent(0.3)
.domain([1, leaves.length])
.range([4,80])
### compute all the internal nodes regions ###
jigsaw.treemap(tree, scale, jigsaw.SQUARE_CELL)
### 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 cells) ###
map.append('use')
.attr('class', 'land-fill')
.attr('xlink:href', '#land')
### draw labels ###
map.selectAll('.label')
.data(nodes.filter((d)->d.depth is 1))
.enter().append('text')
.attr('class', '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.name.split('.').reverse()[0])
.attr('opacity', 0.2)
### draw the cells ###
map.selectAll('.cell')
.data(leaves)
.enter().append('path')
.attr('class', 'cell')
.attr('d', (d) -> jigsaw.square_generate_svg_path size2cellscale(d.size) )
# .attr('d', jigsaw.square_generate_svg_path scale )
.attr('transform', (d) -> "translate(#{d.x},#{d.y})")
# .attr('fill', (d) -> depth_color(d.depth))
.attr('fill', 'orange')
# .attr('stroke', (d) -> depth_color(d.depth))
# .attr('stroke', 'white')
### draw the level one boundaries ###
map.selectAll('.region')
.data(nodes.filter((d)->d.depth is 1))
.enter().append('path')
.attr('class', 'region')
.attr('d', (d) -> jigsaw.get_svg_path d.region)
# .attr('stroke-width', (d) -> height2thickness(d.height))
.attr('stroke-width', '0.2px')
### draw the graph links ###
# map.selectAll('.graph_link')
# .data(bundles)
# .enter().append('path')
# .attr('class', 'graph_link')
# .attr('d', link_generator)
### draw the leaf labels ###
map.selectAll('.leaf_label')
.data(leaves)
.enter().append('text')
.attr('class', 'leaf_label')
.attr('font-size', '2.5')
.attr('dy', '0.35em')
.attr('transform', (d) -> "translate(#{d.x},#{d.y})")
.text((d) -> d.name.split('.').reverse()[0])
.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: 0.5px;
}
.cell {
stroke-width: 1px;
}
.region {
fill: none;
stroke: #444444;
}
@font-face {
font-family: "Lacuna";
src: url("lacuna.ttf");
}
.label, .leaf_label {
fill: #333333;
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;
}
.graph_link {
stroke: teal;
stroke-width: 0.05;
fill: none;
pointer-events: none;
}
.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: 0.5px
.cell
stroke-width: 1px
.region
fill: none
stroke: #444
@font-face
font-family: "Lacuna"
src: url("lacuna.ttf")
.label, .leaf_label
fill: #333
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
.graph_link
stroke: teal
stroke-width: 0.05
fill: none
pointer-events: none
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"
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
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 = 100
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
}(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";
},
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;
},
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 = 100;
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;
}
};
}).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, 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 * Math.cos(orientation),
y: last_point.y + scale * Math.sin(orientation)
}
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: {
base: 7
angle: Math.PI/3
axiom: 'A'
rules:
A: 'A+BF++BF-FA--FAFA-BF+'
B: '-FA+BFBF++BF+FA--FA-B'
}
HILBERT: {
base: 4
angle: Math.PI/2
axiom: 'A'
rules:
A: '-BF+AFA+FB-'
B: '+AF-BFB-FA+'
}
displace: (seq, curve_cfg, scale, orientation) ->
scale = if scale? then scale 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, 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
### 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;
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, 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 * Math.cos(orientation),
y: last_point.y + scale * Math.sin(orientation)
});
}
}
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: {
base: 7,
angle: Math.PI / 3,
axiom: 'A',
rules: {
A: 'A+BF++BF-FA--FAFA-BF+',
B: '-FA+BFBF++BF+FA--FA-B'
}
},
HILBERT: {
base: 4,
angle: Math.PI / 2,
axiom: 'A',
rules: {
A: '-BF+AFA+FB-',
B: '+AF-BFB-FA+'
}
},
displace: function(seq, curve_cfg, scale, orientation) {
var curve, curve_string, d, max_x, max_y, min_x, min_y, point, steps, _i, _j, _len, _len2, _ref, _ref2, _results;
scale = scale != null ? scale : 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, 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;
});
_results = [];
for (_j = 0, _len2 = seq.length; _j < _len2; _j++) {
d = seq[_j];
d.x -= (max_x + min_x) / 2;
_results.push(d.y -= (max_y + min_y) / 2);
}
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)
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
}(function() {
var rsort, 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);
};
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;
}
};
}).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);