A more engineered example of a space-filling curve layout (see also this random fractal map), using the Gosper curve to displace the leaves of a tree (or a sequence) in a compact, 2D representation. Siblings are placed near to each other, so leaves that are “near” according to the hierarchy are also near to each other in this representation. Please note that internal nodes (non-leaf ones) cannot be represented with this technique. Only the sequence of leaves is shown. Therefore, this layout is particularly suited for datasets in which leaves are “more important” than internal nodes.
Visually, the layout is reminiscent of geographical maps. The color of the hexagonal cells indicates the depth of the corresponding leaf, like a sort of elevation map. As it’s common for digital maps, you can zoom and pan the view.
This example is different from the previous ones about fractal maps: the layout step (i.e. decide where to place each leaf) has been given its own Javascript module. Subsequent process (such as creating a fractal map, a.k.a. jigsaw treemap) can be performed using the coordinates given by this layout module. It is also more easy to modify the layout to use a different space-filling curve (e.g. Hilbert).
The example shows the flare software package: each hexagonal cell represents a class within the package. Classes are displaced according to their position in the pacakage hierarchy (not shown). Class size is also not represented.
We assume the package hierarchy to be an unordered tree. As such, a canonical sorting is performed before feeding the tree into the layout.
Merging of hexagonal regions (to obtain the land boundary) is performed by the powerful clipper.js library (documentation).
(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 defs, depth_color, hierarchy, leaves, nodes, scale, 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);
/* VISUALIZATION
*/
/* compute the space-filling curve layout
*/
scale = 26;
sfc_layout.displace(leaves, sfc_layout.GOSPER, scale, -Math.PI / 6);
/* compute also the position of internal nodes
*/
sfc_layout.displace_tree(tree);
/* define a bundle layout
*/
/* define a color scale for leaf depth
*/
depth_color = d3.scale.linear().domain([
1, d3.max(leaves, function(d) {
return d.depth;
})
]).range(['#FFF7DB', '#F0A848']).interpolate(d3.interpolateHcl);
/* define a thickness scale for region depth
*/
/* translate size to cell scale
*/
/* translate depth to label font size
*/
/* compute all the internal nodes regions
*/
jigsaw.treemap(tree, scale, jigsaw.HEX_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 cells
*/
map.selectAll('.cell').data(leaves).enter().append('path').attr('class', 'cell').attr('d', jigsaw.hex_generate_svg_path(scale)).attr('transform', function(d) {
return "translate(" + d.x + "," + d.y + ")";
}).attr('fill', function(d) {
return depth_color(d.depth);
}).attr('stroke', 'white');
/* draw the level one region boundaries
*/
/* draw the land border (above cells)
*/
map.append('use').attr('class', 'land-fill').attr('xlink:href', '#land');
/* draw the graph links
*/
/* draw the level one labels
*/
/* draw the leaf labels
*/
return map.selectAll('.label').data(leaves).enter().append('text').attr('class', 'label').attr('font-size', '4px').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>Space-filling curve layout</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);
/* 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
*/
(function() {
var paths2string;
paths2string = 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;
};
window.hex_utils = {
svg_hex: function(a) {
var r;
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";
},
hex_region: function(points, a) {
var cpr, hexes, p, r, region, scale;
r = a / Math.sin(Math.PI / 3);
hexes = (function() {
var _i, _len, _results;
_results = [];
for (_i = 0, _len = points.length; _i < _len; _i++) {
p = points[_i];
_results.push([
{
X: p.x + r,
Y: p.y
}, {
X: p.x + r / 2,
Y: p.y + a
}, {
X: p.x - r / 2,
Y: p.y + a
}, {
X: p.x - r,
Y: p.y
}, {
X: p.x - r / 2,
Y: p.y - a
}, {
X: p.x + r / 2,
Y: p.y - a
}
]);
}
return _results;
})();
scale = 100;
ClipperLib.JS.ScaleUpPaths(hexes, scale);
cpr = new ClipperLib.Clipper();
cpr.AddPaths(hexes, ClipperLib.PolyType.ptSubject, true);
region = new ClipperLib.Paths();
cpr.Execute(ClipperLib.ClipType.ctUnion, region, ClipperLib.PolyFillType.pftNonZero, ClipperLib.PolyFillType.pftNonZero);
return paths2string(region, scale);
}
};
}).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)
### VISUALIZATION ###
### compute the space-filling curve layout ###
scale = 26
sfc_layout.displace(leaves, sfc_layout.GOSPER, scale, -Math.PI/6)
### 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 depth ###
# depth_thickness = d3.scale.sqrt()
# .domain([0, d3.max(leaves,(d)->d.depth)-1])
# .range([4, 0.1])
### translate size to cell scale ###
# size2cellscale = d3.scale.sqrt()
# .domain([0, d3.max(nodes,(d)->d.size)])
# .range([0,scale])
### translate depth to label font size ###
# depth2fontsize = d3.scale.sqrt()
# .domain([0, d3.max(nodes,(d)->d.depth)])
# .range([40,4])
### compute all the internal nodes regions ###
jigsaw.treemap(tree, scale, jigsaw.HEX_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 cells ###
map.selectAll('.cell')
.data(leaves)
.enter().append('path')
.attr('class', 'cell')
# .attr('d', (d) -> jigsaw.hex_generate_svg_path size2cellscale(d.size) )
.attr('d', jigsaw.hex_generate_svg_path scale )
.attr('transform', (d) -> "translate(#{d.x},#{d.y})")
.attr('fill', (d) -> depth_color(d.depth))
# .attr('stroke', (d) -> depth_color(d.depth))
.attr('stroke', 'white')
### draw the level one region 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) -> depth_thickness(d.depth))
# .attr('stroke-width', '2px')
### draw the land border (above cells) ###
map.append('use')
.attr('class', 'land-fill')
.attr('xlink:href', '#land')
### draw the graph links ###
# map.selectAll('.graph_link')
# .data(bundles)
# .enter().append('path')
# .attr('class', 'graph_link')
# .attr('d', link_generator)
### draw the level one labels ###
# map.selectAll('.label')
# .data(nodes.filter((d)->d.depth is 1))
# .enter().append('text')
# .attr('class', 'label')
# .attr('font-size', (d) -> depth2fontsize(d.depth))
# .attr('dy', '0.35em')
# .attr('transform', (d) -> "translate(#{d.x},#{d.y})")
# .text((d) -> d.name.split('.').reverse()[0])
### draw the leaf labels ###
map.selectAll('.label')
.data(leaves)
.enter().append('text')
.attr('class', 'label')
.attr('font-size', '4px')
.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: none;
stroke: #444444;
stroke-width: 1px;
}
.cell {
stroke-width: 1px;
}
.region {
fill: none;
stroke: #444444;
}
@font-face {
font-family: "Lacuna";
src: url("lacuna.ttf");
}
.label {
fill: #333333;
text-anchor: middle;
pointer-events: none;
font-family: "Lacuna";
}
.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: none
stroke: #444
stroke-width: 1px
.cell
stroke-width: 1px
.region
fill: none
stroke: #444
@font-face
font-family: "Lacuna"
src: url("lacuna.ttf")
.label
fill: #333
text-anchor: middle
pointer-events: none
font-family: "Lacuna"
.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"
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
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";
},
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;
},
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 ###
displace_tree: (node) ->
if not node.children?
return [node]
### an internal node's position is the centroid of its leaf descendants ###
leaf_descendants = (sfc_layout.displace_tree(c) for c in node.children).reduce((a, d) -> a.concat(d))
node.x = d3.mean(leaf_descendants, (d)->d.x)
node.y = d3.mean(leaf_descendants, (d)->d.y)
### pass descendants up to the hierarchy ###
return 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
*/
displace_tree: function(node) {
var c, leaf_descendants;
if (!(node.children != null)) return [node];
/* an internal node's position is the centroid of its leaf descendants
*/
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(leaf_descendants, function(d) {
return d.x;
});
node.y = d3.mean(leaf_descendants, function(d) {
return d.y;
});
/* pass descendants up to the hierarchy
*/
return 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
}(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;
}
};
}).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);