Skip to content

Instantly share code, notes, and snippets.

@1wheel

1wheel/.gitignore

Last active Sep 13, 2019
Embed
What would you like to do?
d3-module-faces
node_modules

To visualize the d3 modules being used, I made a log scaled scatter plot of forced directed Chernoff faces. By transforming many different attributes of our dataset into friendly glyphs, Chernoff faces allow us to understand multidimensional datasets. The encoding scheme is probably self explanatory, but I've included it below just in case:

'face':  ƒ('dependentsCount')
'hair':  ƒ('description', 'length')
'mouth': ƒ('downloads')
'nosew': ƒ('githubContributers')
'noseh': ƒ('githubIssues')
'eyew':  ƒ('githubStars')
'eyeh':  d => Math.random()
'brow':  ƒ('repoSize')

I used the following modules:

Data is from nprms.io - see download-data.js to your generate your own listing of modules with different data points.

var ƒ = d3.f
var width = 960
var height = 500
var faceRadius = 20
d3.loadData(['dense-modules.json', 'annotations.json'], function(err, res){
d3.select('body').html('').selectAppend('div.tooltip')
modules = res[0]
annotations = res[1]
c = d3.conventions({
totalWidth: width,
totalHeight: height,
margin: {left: 40, top: 5, bottom: 20, right: 11}
})
c.svg.append('text')
.text('NPM downloads v. Github stars')
.translate([10, 10])
.st({fontWeight: 600, fontFamily: 'monospace'})
chernoff = d3.chernoff()
d3.entries({
'face': ƒ('dependentsCount'),
'hair': ƒ('description', 'length'),
'mouth': ƒ('downloads'),
'nosew': ƒ('githubContributers'),
'noseh': ƒ('githubIssues'),
'eyew': ƒ('githubStars'),
'eyeh': d => Math.random(),
'brow': ƒ('repoSize'),
}).forEach(function(d){
var scale = d3.scaleLog().domain(d3.extent(modules, ƒ(d.value, addOne)))
chernoff[d.key](ƒ(d.value, addOne, scale))
})
c.x = d3.scaleLog()
.domain(d3.extent(modules, ƒ('downloads', addOne)))
.range(c.x.range())
c.y = d3.scaleLog()
.domain(d3.extent(modules, ƒ('githubStars', addOne)))
.range(c.y.range())
c.xAxis.scale(c.x)
c.yAxis.scale(c.y)
c.drawAxis()
var simulation = d3.forceSimulation(modules)
.force('x', d3.forceX(ƒ('downloads', addOne, c.x)).strength(.1))
.force('y', d3.forceY(ƒ('githubStars', addOne, c.y)).strength(.1))
.force('collide', d3.forceCollide(faceRadius))
.force('container', d3.forceContainer([
[faceRadius, faceRadius],
[width - faceRadius*3, height - faceRadius*2.6] ]))
for (var i = 0; i < 400; ++i) simulation.tick()
var color = d3.scaleOrdinal(d3.schemeCategory10)
var moduleSel = c.svg.appendMany(modules, 'g')
.at({
fill: ƒ('author', color),
stroke: ƒ('author', color)
})
.translate(d => [d.x, d.y])
.on('click', d => window.open(d.link, '_blank'))
.st({cursor: 'pointer'})
modules.forEach(function(d){
delete d.x
delete d.y
delete d.vx
delete d.vy
delete d.index
})
moduleSel.call(d3.attachTooltip)
moduleSel.append('circle').at({r: faceRadius})
moduleSel.append('g.face')
.call(chernoff)
.at({transform: function(d){
var s = 80/faceRadius
return ['scale(', 1/s , ') ', 'translate(', -faceRadius*3.5, -faceRadius*4, ')'].join(' ')
} })
var swoopy = d3.swoopyDrag()
.x(d => 0)
.y(d => 0)
.draggable(0)
.annotations(annotations)
var swoopySel = c.svg.append('g.swoopy').call(swoopy)
swoopySel.selectAll('path').attr('marker-end', 'url(#arrow)')
c.svg.append('marker')
.attr('id', 'arrow')
.attr('viewBox', '-10 -10 20 20')
.attr('markerWidth', 20)
.attr('markerHeight', 20)
.attr('orient', 'auto')
.append('path')
.attr('d', 'M-6.75,-6.75 L 0,0 L -6.75,6.75')
swoopySel.selectAll('text')
.each(function(d){
d3.select(this)
.text('')
.tspans(d3.wordwrap(d.text, 22))
})
})
function addOne(d){ return d + 1 }
[
{
"path": "M 764,400 A 37.76 37.76 0 0 1 759,330",
"text": "Modules Mike included in the default d3 build have the most stars and downloads",
"textOffset": [
773,
414
]
},
{
"path": "M 811,39 A 48.376 48.376 0 0 0 907,50",
"text": "The most downloaded, d3-queue, predates d3v4",
"textOffset": [
696,
10
]
},
{
"path": "M 455,75 A 60.466 60.466 0 0 0 547,87",
"text": "Susie's legend generator is the most popular module not in the default build",
"textOffset": [
369,
35
]
},
{
"path": "M 432,358 A 35.487 35.487 0 0 1 394,314",
"text": "All three of Peter's modules have about the same number of downloads",
"textOffset": [
445,
359
]
},
{
"path": "M 133,277 A 99.156 99.156 0 0 0 56,194",
"text": "I just put swoopy-drag and force-container on npm",
"textOffset": [
38,
310
]
},
{
"path": "M 134,339 A 82.601 82.601 0 0 1 49,432",
"text": "",
"textOffset": [
38,
310
]
}
]
function sign(num) {
if(num > 0) {
return 1;
} else if(num < 0) {
return -1;
} else {
return 0;
}
}
function d3_chernoff() {
var facef = 0.5, // 0 - 1
hairf = 0, // -1 - 1
mouthf = 0, // -1 - 1
nosehf = 0.5, // 0 - 1
nosewf = 0.5, // 0 - 1
eyehf = 0.5, // 0 - 1
eyewf = 0.5, // 0 - 1
browf = 0, // -1 - 1
line = d3.line()
.curve(d3.curveCardinalClosed)
.x(function(d) { return d.x; })
.y(function(d) { return d.y; }),
bline = d3.line()
.curve(d3.curveBasisClosed)
.x(function(d) { return d.x; })
.y(function(d) { return d.y; });
function chernoff(a) {
if(true || a instanceof Array) {
a.each(__chernoff);
} else {
d3.select(this).each(__chernoff);
}
}
function __chernoff(d) {
var ele = d3.select(this),
facevar = (typeof(facef) === "function" ? facef(d) : facef) * 30,
hairvar = (typeof(hairf) === "function" ? hairf(d) : hairf) * 80,
mouthvar = (typeof(mouthf) === "function" ? mouthf(d) : mouthf) * 7,
nosehvar = (typeof(nosehf) === "function" ? nosehf(d) : nosehf) * 10,
nosewvar = (typeof(nosewf) === "function" ? nosewf(d) : nosewf) * 10,
eyehvar = (typeof(eyehf) === "function" ? eyehf(d) : eyehf) * 10,
eyewvar = (typeof(eyewf) === "function" ? eyewf(d) : eyewf) * 10,
browvar = (typeof(browf) === "function" ? browf(d) : browf) * 3;
var face = [{x: 70, y: 60}, {x: 120, y: 80},
{x: 120-facevar, y: 110}, {x: 120-facevar, y: 160},
{x: 20+facevar, y: 160}, {x: 20+facevar, y: 110},
{x: 20, y: 80}];
ele.selectAll("path.face").data([face]).enter()
.append("svg:path")
.attr("class", "face")
.attr("d", bline);
var hair = [{x: 70, y: 60}, {x: 120, y: 80},
{x: 140, y: 45-hairvar}, {x: 120, y: 45},
{x: 70, y: 30}, {x: 20, y: 45},
{x: 0, y: 45-hairvar}, {x: 20, y: 80}];
ele.selectAll("path.hair").data([hair]).enter()
.append("svg:path")
.attr("class", "hair")
.attr("d", bline);
var mouth = [{x: 70, y: 130+mouthvar},
{x: 110-facevar, y: 135-mouthvar},
{x: 70, y: 140+mouthvar},
{x: 30+facevar, y: 135-mouthvar}];
ele.selectAll("path.mouth").data([mouth]).enter()
.append("svg:path")
.attr("class", "mouth")
.attr("d", line);
var nose = [{x: 70, y: 110-nosehvar},
{x: 70+nosewvar, y: 110+nosehvar},
{x: 70-nosewvar, y: 110+nosehvar}];
ele.selectAll("path.nose").data([nose]).enter()
.append("svg:path")
.attr("class", "nose")
.attr("d", line);
var leye = [{x: 55, y: 90-eyehvar}, {x: 55+eyewvar, y: 90},
{x: 55, y: 90+eyehvar}, {x: 55-eyewvar, y: 90}];
var reye = [{x: 85, y: 90-eyehvar}, {x: 85+eyewvar, y: 90},
{x: 85, y: 90+eyehvar}, {x: 85-eyewvar, y: 90}];
ele.selectAll("path.leye").data([leye]).enter()
.append("svg:path")
.attr("class", "leye")
.attr("d", bline);
ele.selectAll("path.reye").data([reye]).enter()
.append("svg:path")
.attr("class", "reye")
.attr("d", bline);
ele.append("svg:path")
.attr("class", "lbrow")
.attr("d", "M" + (55-eyewvar/1.7-sign(browvar)) + "," +
(87-eyehvar+browvar) + " " +
(55+eyewvar/1.7-sign(browvar)) + "," +
(87-eyehvar-browvar));
ele.append("svg:path")
.attr("class", "rbrow")
.attr("d", "M" + (85-eyewvar/1.7+sign(browvar)) + "," +
(87-eyehvar-browvar) + " " +
(85+eyewvar/1.7+sign(browvar)) + "," +
(87-eyehvar+browvar));
}
chernoff.face = function(x) {
if(!arguments.length) return facef;
facef = x;
return chernoff;
};
chernoff.hair = function(x) {
if(!arguments.length) return hairf;
hairf = x;
return chernoff;
};
chernoff.mouth = function(x) {
if(!arguments.length) return mouthf;
mouthf = x;
return chernoff;
};
chernoff.noseh = function(x) {
if(!arguments.length) return nosehf;
nosehf = x;
return chernoff;
};
chernoff.nosew = function(x) {
if(!arguments.length) return nosewf;
nosewf = x;
return chernoff;
};
chernoff.eyeh = function(x) {
if(!arguments.length) return eyehf;
eyehf = x;
return chernoff;
};
chernoff.eyew = function(x) {
if(!arguments.length) return eyewf;
eyewf = x;
return chernoff;
};
chernoff.brow = function(x) {
if(!arguments.length) return browf;
browf = x;
return chernoff;
};
return chernoff;
}
d3.chernoff = function() {
return d3_chernoff(Object);
};
(function (global, factory) {
typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) :
typeof define === 'function' && define.amd ? define(['exports'], factory) :
(factory((global.d3 = global.d3 || {})));
}(this, function (exports) { 'use strict';
function forceContainer (bbox){
var nodes, strength = 1;;
if (!bbox || bbox.length < 2) bbox = [[0, 0], [100, 100]]
function force(alpha) {
var i,
n = nodes.length,
node,
x = 0,
y = 0;
for (i = 0; i < n; ++i) {
node = nodes[i], x = node.x, y = node.y;
if (x < bbox[0][0]) node.vx += (bbox[0][0] - x)*alpha
if (y < bbox[0][1]) node.vy += (bbox[0][1] - y)*alpha
if (x > bbox[1][0]) node.vx += (bbox[1][0] - x)*alpha
if (y > bbox[1][1]) node.vy += (bbox[1][1] - y)*alpha
}
}
force.initialize = function(_){
nodes = _;
};
force.bbox = function(_){
return arguments.length ? (bbox = +_, force) : bbox;
};
force.strength = function(_){
return arguments.length ? (strength = +_, force) : strength;
}
return force;
}
exports.forceContainer = forceContainer;
Object.defineProperty(exports, '__esModule', { value: true });
}));
(function (global, factory) {
typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) :
typeof define === 'function' && define.amd ? define(['exports'], factory) :
(factory((global.d3 = global.d3 || {})));
}(this, function (exports) { 'use strict';
function ascending(a, b) {
return a < b ? -1 : a > b ? 1 : a >= b ? 0 : NaN;
}
function bisector(compare) {
if (compare.length === 1) compare = ascendingComparator(compare);
return {
left: function(a, x, lo, hi) {
if (lo == null) lo = 0;
if (hi == null) hi = a.length;
while (lo < hi) {
var mid = lo + hi >>> 1;
if (compare(a[mid], x) < 0) lo = mid + 1;
else hi = mid;
}
return lo;
},
right: function(a, x, lo, hi) {
if (lo == null) lo = 0;
if (hi == null) hi = a.length;
while (lo < hi) {
var mid = lo + hi >>> 1;
if (compare(a[mid], x) > 0) hi = mid;
else lo = mid + 1;
}
return lo;
}
};
}
function ascendingComparator(f) {
return function(d, x) {
return ascending(f(d), x);
};
}
var ascendingBisect = bisector(ascending);
var bisectRight = ascendingBisect.right;
var bisectLeft = ascendingBisect.left;
function descending(a, b) {
return b < a ? -1 : b > a ? 1 : b >= a ? 0 : NaN;
}
function number(x) {
return x === null ? NaN : +x;
}
function variance(array, f) {
var n = array.length,
m = 0,
a,
d,
s = 0,
i = -1,
j = 0;
if (f == null) {
while (++i < n) {
if (!isNaN(a = number(array[i]))) {
d = a - m;
m += d / ++j;
s += d * (a - m);
}
}
}
else {
while (++i < n) {
if (!isNaN(a = number(f(array[i], i, array)))) {
d = a - m;
m += d / ++j;
s += d * (a - m);
}
}
}
if (j > 1) return s / (j - 1);
}
function deviation(array, f) {
var v = variance(array, f);
return v ? Math.sqrt(v) : v;
}
function extent(array, f) {
var i = -1,
n = array.length,
a,
b,
c;
if (f == null) {
while (++i < n) if ((b = array[i]) != null && b >= b) { a = c = b; break; }
while (++i < n) if ((b = array[i]) != null) {
if (a > b) a = b;
if (c < b) c = b;
}
}
else {
while (++i < n) if ((b = f(array[i], i, array)) != null && b >= b) { a = c = b; break; }
while (++i < n) if ((b = f(array[i], i, array)) != null) {
if (a > b) a = b;
if (c < b) c = b;
}
}
return [a, c];
}
var array = Array.prototype;
var slice = array.slice;
var map = array.map;
function constant(x) {
return function() {
return x;
};
}
function identity(x) {
return x;
}
function range(start, stop, step) {
start = +start, stop = +stop, step = (n = arguments.length) < 2 ? (stop = start, start = 0, 1) : n < 3 ? 1 : +step;
var i = -1,
n = Math.max(0, Math.ceil((stop - start) / step)) | 0,
range = new Array(n);
while (++i < n) {
range[i] = start + i * step;
}
return range;
}
var e10 = Math.sqrt(50);
var e5 = Math.sqrt(10);
var e2 = Math.sqrt(2);
function ticks(start, stop, count) {
var step = tickStep(start, stop, count);
return range(
Math.ceil(start / step) * step,
Math.floor(stop / step) * step + step / 2, // inclusive
step
);
}
function tickStep(start, stop, count) {
var step0 = Math.abs(stop - start) / Math.max(0, count),
step1 = Math.pow(10, Math.floor(Math.log(step0) / Math.LN10)),
error = step0 / step1;
if (error >= e10) step1 *= 10;
else if (error >= e5) step1 *= 5;
else if (error >= e2) step1 *= 2;
return stop < start ? -step1 : step1;
}
function sturges(values) {
return Math.ceil(Math.log(values.length) / Math.LN2) + 1;
}
function histogram() {
var value = identity,
domain = extent,
threshold = sturges;
function histogram(data) {
var i,
n = data.length,
x,
values = new Array(n);
for (i = 0; i < n; ++i) {
values[i] = value(data[i], i, data);
}
var xz = domain(values),
x0 = xz[0],
x1 = xz[1],
tz = threshold(values, x0, x1);
// Convert number of thresholds into uniform thresholds.
if (!Array.isArray(tz)) tz = ticks(x0, x1, tz);
// Remove any thresholds outside the domain.
var m = tz.length;
while (tz[0] <= x0) tz.shift(), --m;
while (tz[m - 1] >= x1) tz.pop(), --m;
var bins = new Array(m + 1),
bin;
// Initialize bins.
for (i = 0; i <= m; ++i) {
bin = bins[i] = [];
bin.x0 = i > 0 ? tz[i - 1] : x0;
bin.x1 = i < m ? tz[i] : x1;
}
// Assign data to bins by value, ignoring any outside the domain.
for (i = 0; i < n; ++i) {
x = values[i];
if (x0 <= x && x <= x1) {
bins[bisectRight(tz, x, 0, m)].push(data[i]);
}
}
return bins;
}
histogram.value = function(_) {
return arguments.length ? (value = typeof _ === "function" ? _ : constant(_), histogram) : value;
};
histogram.domain = function(_) {
return arguments.length ? (domain = typeof _ === "function" ? _ : constant([_[0], _[1]]), histogram) : domain;
};
histogram.thresholds = function(_) {
return arguments.length ? (threshold = typeof _ === "function" ? _ : Array.isArray(_) ? constant(slice.call(_)) : constant(_), histogram) : threshold;
};
return histogram;
}
function threshold(array, p, f) {
if (f == null) f = number;
if (!(n = array.length)) return;
if ((p = +p) <= 0 || n < 2) return +f(array[0], 0, array);
if (p >= 1) return +f(array[n - 1], n - 1, array);
var n,
h = (n - 1) * p,
i = Math.floor(h),
a = +f(array[i], i, array),
b = +f(array[i + 1], i + 1, array);
return a + (b - a) * (h - i);
}
function freedmanDiaconis(values, min, max) {
values = map.call(values, number).sort(ascending);
return Math.ceil((max - min) / (2 * (threshold(values, 0.75) - threshold(values, 0.25)) * Math.pow(values.length, -1 / 3)));
}
function scott(values, min, max) {
return Math.ceil((max - min) / (3.5 * deviation(values) * Math.pow(values.length, -1 / 3)));
}
function max(array, f) {
var i = -1,
n = array.length,
a,
b;
if (f == null) {
while (++i < n) if ((b = array[i]) != null && b >= b) { a = b; break; }
while (++i < n) if ((b = array[i]) != null && b > a) a = b;
}
else {
while (++i < n) if ((b = f(array[i], i, array)) != null && b >= b) { a = b; break; }
while (++i < n) if ((b = f(array[i], i, array)) != null && b > a) a = b;
}
return a;
}
function mean(array, f) {
var s = 0,
n = array.length,
a,
i = -1,
j = n;
if (f == null) {
while (++i < n) if (!isNaN(a = number(array[i]))) s += a; else --j;
}
else {
while (++i < n) if (!isNaN(a = number(f(array[i], i, array)))) s += a; else --j;
}
if (j) return s / j;
}
function median(array, f) {
var numbers = [],
n = array.length,
a,
i = -1;
if (f == null) {
while (++i < n) if (!isNaN(a = number(array[i]))) numbers.push(a);
}
else {
while (++i < n) if (!isNaN(a = number(f(array[i], i, array)))) numbers.push(a);
}
return threshold(numbers.sort(ascending), 0.5);
}
function merge(arrays) {
var n = arrays.length,
m,
i = -1,
j = 0,
merged,
array;
while (++i < n) j += arrays[i].length;
merged = new Array(j);
while (--n >= 0) {
array = arrays[n];
m = array.length;
while (--m >= 0) {
merged[--j] = array[m];
}
}
return merged;
}
function min(array, f) {
var i = -1,
n = array.length,
a,
b;
if (f == null) {
while (++i < n) if ((b = array[i]) != null && b >= b) { a = b; break; }
while (++i < n) if ((b = array[i]) != null && a > b) a = b;
}
else {
while (++i < n) if ((b = f(array[i], i, array)) != null && b >= b) { a = b; break; }
while (++i < n) if ((b = f(array[i], i, array)) != null && a > b) a = b;
}
return a;
}
function pairs(array) {
var i = 0, n = array.length - 1, p = array[0], pairs = new Array(n < 0 ? 0 : n);
while (i < n) pairs[i] = [p, p = array[++i]];
return pairs;
}
function permute(array, indexes) {
var i = indexes.length, permutes = new Array(i);
while (i--) permutes[i] = array[indexes[i]];
return permutes;
}
function scan(array, compare) {
if (!(n = array.length)) return;
var i = 0,
n,
j = 0,
xi,
xj = array[j];
if (!compare) compare = ascending;
while (++i < n) if (compare(xi = array[i], xj) < 0 || compare(xj, xj) !== 0) xj = xi, j = i;
if (compare(xj, xj) === 0) return j;
}
function shuffle(array, i0, i1) {
var m = (i1 == null ? array.length : i1) - (i0 = i0 == null ? 0 : +i0),
t,
i;
while (m) {
i = Math.random() * m-- | 0;
t = array[m + i0];
array[m + i0] = array[i + i0];
array[i + i0] = t;
}
return array;
}
function sum(array, f) {
var s = 0,
n = array.length,
a,
i = -1;
if (f == null) {
while (++i < n) if (a = +array[i]) s += a; // Note: zero and null are equivalent.
}
else {
while (++i < n) if (a = +f(array[i], i, array)) s += a;
}
return s;
}
function transpose(matrix) {
if (!(n = matrix.length)) return [];
for (var i = -1, m = min(matrix, length), transpose = new Array(m); ++i < m;) {
for (var j = -1, n, row = transpose[i] = new Array(n); ++j < n;) {
row[j] = matrix[j][i];
}
}
return transpose;
}
function length(d) {
return d.length;
}
function zip() {
return transpose(arguments);
}
var prefix = "$";
function Map() {}
Map.prototype = map$1.prototype = {
constructor: Map,
has: function(key) {
return (prefix + key) in this;
},
get: function(key) {
return this[prefix + key];
},
set: function(key, value) {
this[prefix + key] = value;
return this;
},
remove: function(key) {
var property = prefix + key;
return property in this && delete this[property];
},
clear: function() {
for (var property in this) if (property[0] === prefix) delete this[property];
},
keys: function() {
var keys = [];
for (var property in this) if (property[0] === prefix) keys.push(property.slice(1));
return keys;
},
values: function() {
var values = [];
for (var property in this) if (property[0] === prefix) values.push(this[property]);
return values;
},
entries: function() {
var entries = [];
for (var property in this) if (property[0] === prefix) entries.push({key: property.slice(1), value: this[property]});
return entries;
},
size: function() {
var size = 0;
for (var property in this) if (property[0] === prefix) ++size;
return size;
},
empty: function() {
for (var property in this) if (property[0] === prefix) return false;
return true;
},
each: function(f) {
for (var property in this) if (property[0] === prefix) f(this[property], property.slice(1), this);
}
};
function map$1(object, f) {
var map = new Map;
// Copy constructor.
if (object instanceof Map) object.each(function(value, key) { map.set(key, value); });
// Index array by numeric index or specified key function.
else if (Array.isArray(object)) {
var i = -1,
n = object.length,
o;
if (f == null) while (++i < n) map.set(i, object[i]);
else while (++i < n) map.set(f(o = object[i], i, object), o);
}
// Convert object to map.
else if (object) for (var key in object) map.set(key, object[key]);
return map;
}
function nest() {
var keys = [],
sortKeys = [],
sortValues,
rollup,
nest;
function apply(array, depth, createResult, setResult) {
if (depth >= keys.length) return rollup != null
? rollup(array) : (sortValues != null
? array.sort(sortValues)
: array);
var i = -1,
n = array.length,
key = keys[depth++],
keyValue,
value,
valuesByKey = map$1(),
values,
result = createResult();
while (++i < n) {
if (values = valuesByKey.get(keyValue = key(value = array[i]) + "")) {
values.push(value);
} else {
valuesByKey.set(keyValue, [value]);
}
}
valuesByKey.each(function(values, key) {
setResult(result, key, apply(values, depth, createResult, setResult));
});
return result;
}
function entries(map, depth) {
if (++depth > keys.length) return map;
var array, sortKey = sortKeys[depth - 1];
if (rollup != null && depth >= keys.length) array = map.entries();
else array = [], map.each(function(v, k) { array.push({key: k, values: entries(v, depth)}); });
return sortKey != null ? array.sort(function(a, b) { return sortKey(a.key, b.key); }) : array;
}
return nest = {
object: function(array) { return apply(array, 0, createObject, setObject); },
map: function(array) { return apply(array, 0, createMap, setMap); },
entries: function(array) { return entries(apply(array, 0, createMap, setMap), 0); },
key: function(d) { keys.push(d); return nest; },
sortKeys: function(order) { sortKeys[keys.length - 1] = order; return nest; },
sortValues: function(order) { sortValues = order; return nest; },
rollup: function(f) { rollup = f; return nest; }
};
}
function createObject() {
return {};
}
function setObject(object, key, value) {
object[key] = value;
}
function createMap() {
return map$1();
}
function setMap(map, key, value) {
map.set(key, value);
}
function Set() {}
var proto = map$1.prototype;
Set.prototype = set.prototype = {
constructor: Set,
has: proto.has,
add: function(value) {
value += "";
this[prefix + value] = value;
return this;
},
remove: proto.remove,
clear: proto.clear,
values: proto.keys,
size: proto.size,
empty: proto.empty,
each: proto.each
};
function set(object, f) {
var set = new Set;
// Copy constructor.
if (object instanceof Set) object.each(function(value) { set.add(value); });
// Otherwise, assume it’s an array.
else if (object) {
var i = -1, n = object.length;
if (f == null) while (++i < n) set.add(object[i]);
else while (++i < n) set.add(f(object[i], i, object));
}
return set;
}
function d3keys(map) {
var keys = [];
for (var key in map) keys.push(key);
return keys;
}
function values(map) {
var values = [];
for (var key in map) values.push(map[key]);
return values;
}
function entries(map) {
var entries = [];
for (var key in map) entries.push({key: key, value: map[key]});
return entries;
}
function uniform(min, max) {
min = min == null ? 0 : +min;
max = max == null ? 1 : +max;
if (arguments.length === 1) max = min, min = 0;
else max -= min;
return function() {
return Math.random() * max + min;
};
}
function normal(mu, sigma) {
var x, r;
mu = mu == null ? 0 : +mu;
sigma = sigma == null ? 1 : +sigma;
return function() {
var y;
// If available, use the second previously-generated uniform random.
if (x != null) y = x, x = null;
// Otherwise, generate a new x and y.
else do {
x = Math.random() * 2 - 1;
y = Math.random() * 2 - 1;
r = x * x + y * y;
} while (!r || r > 1);
return mu + sigma * y * Math.sqrt(-2 * Math.log(r) / r);
};
}
function logNormal() {
var randomNormal = normal.apply(this, arguments);
return function() {
return Math.exp(randomNormal());
};
}
function irwinHall(n) {
return function() {
for (var sum = 0, i = 0; i < n; ++i) sum += Math.random();
return sum;
};
}
function bates(n) {
var randomIrwinHall = irwinHall(n);
return function() {
return randomIrwinHall() / n;
};
}
function exponential(lambda) {
return function() {
return -Math.log(1 - Math.random()) / lambda;
};
}
function linear(t) {
return +t;
}
function quadIn(t) {
return t * t;
}
function quadOut(t) {
return t * (2 - t);
}
function quadInOut(t) {
return ((t *= 2) <= 1 ? t * t : --t * (2 - t) + 1) / 2;
}
function cubicIn(t) {
return t * t * t;
}
function cubicOut(t) {
return --t * t * t + 1;
}
function easeCubicInOut(t) {
return ((t *= 2) <= 1 ? t * t * t : (t -= 2) * t * t + 2) / 2;
}
var exponent = 3;
var polyIn = (function custom(e) {
e = +e;
function polyIn(t) {
return Math.pow(t, e);
}
polyIn.exponent = custom;
return polyIn;
})(exponent);
var polyOut = (function custom(e) {
e = +e;
function polyOut(t) {
return 1 - Math.pow(1 - t, e);
}
polyOut.exponent = custom;
return polyOut;
})(exponent);
var polyInOut = (function custom(e) {
e = +e;
function polyInOut(t) {
return ((t *= 2) <= 1 ? Math.pow(t, e) : 2 - Math.pow(2 - t, e)) / 2;
}
polyInOut.exponent = custom;
return polyInOut;
})(exponent);
var pi = Math.PI;
var halfPi = pi / 2;
function sinIn(t) {
return 1 - Math.cos(t * halfPi);
}
function sinOut(t) {
return Math.sin(t * halfPi);
}
function sinInOut(t) {
return (1 - Math.cos(pi * t)) / 2;
}
function expIn(t) {
return Math.pow(2, 10 * t - 10);
}
function expOut(t) {
return 1 - Math.pow(2, -10 * t);
}
function expInOut(t) {
return ((t *= 2) <= 1 ? Math.pow(2, 10 * t - 10) : 2 - Math.pow(2, 10 - 10 * t)) / 2;
}
function circleIn(t) {
return 1 - Math.sqrt(1 - t * t);
}
function circleOut(t) {
return Math.sqrt(1 - --t * t);
}
function circleInOut(t) {
return ((t *= 2) <= 1 ? 1 - Math.sqrt(1 - t * t) : Math.sqrt(1 - (t -= 2) * t) + 1) / 2;
}
var b1 = 4 / 11;
var b2 = 6 / 11;
var b3 = 8 / 11;
var b4 = 3 / 4;
var b5 = 9 / 11;
var b6 = 10 / 11;
var b7 = 15 / 16;
var b8 = 21 / 22;
var b9 = 63 / 64;
var b0 = 1 / b1 / b1;
function bounceIn(t) {
return 1 - bounceOut(1 - t);
}
function bounceOut(t) {
return (t = +t) < b1 ? b0 * t * t : t < b3 ? b0 * (t -= b2) * t + b4 : t < b6 ? b0 * (t -= b5) * t + b7 : b0 * (t -= b8) * t + b9;
}
function bounceInOut(t) {
return ((t *= 2) <= 1 ? 1 - bounceOut(1 - t) : bounceOut(t - 1) + 1) / 2;
}
var overshoot = 1.70158;
var backIn = (function custom(s) {
s = +s;
function backIn(t) {
return t * t * ((s + 1) * t - s);
}
backIn.overshoot = custom;
return backIn;
})(overshoot);
var backOut = (function custom(s) {
s = +s;
function backOut(t) {
return --t * t * ((s + 1) * t + s) + 1;
}
backOut.overshoot = custom;
return backOut;
})(overshoot);
var backInOut = (function custom(s) {
s = +s;
function backInOut(t) {
return ((t *= 2) < 1 ? t * t * ((s + 1) * t - s) : (t -= 2) * t * ((s + 1) * t + s) + 2) / 2;
}
backInOut.overshoot = custom;
return backInOut;
})(overshoot);
var tau = 2 * Math.PI;
var amplitude = 1;
var period = 0.3;
var elasticIn = (function custom(a, p) {
var s = Math.asin(1 / (a = Math.max(1, a))) * (p /= tau);
function elasticIn(t) {
return a * Math.pow(2, 10 * --t) * Math.sin((s - t) / p);
}
elasticIn.amplitude = function(a) { return custom(a, p * tau); };
elasticIn.period = function(p) { return custom(a, p); };
return elasticIn;
})(amplitude, period);
var elasticOut = (function custom(a, p) {
var s = Math.asin(1 / (a = Math.max(1, a))) * (p /= tau);
function elasticOut(t) {
return 1 - a * Math.pow(2, -10 * (t = +t)) * Math.sin((t + s) / p);
}
elasticOut.amplitude = function(a) { return custom(a, p * tau); };
elasticOut.period = function(p) { return custom(a, p); };
return elasticOut;
})(amplitude, period);
var elasticInOut = (function custom(a, p) {
var s = Math.asin(1 / (a = Math.max(1, a))) * (p /= tau);
function elasticInOut(t) {
return ((t = t * 2 - 1) < 0
? a * Math.pow(2, 10 * t) * Math.sin((s - t) / p)
: 2 - a * Math.pow(2, -10 * t) * Math.sin((s + t) / p)) / 2;
}
elasticInOut.amplitude = function(a) { return custom(a, p * tau); };
elasticInOut.period = function(p) { return custom(a, p); };
return elasticInOut;
})(amplitude, period);
function area(polygon) {
var i = -1,
n = polygon.length,
a,
b = polygon[n - 1],
area = 0;
while (++i < n) {
a = b;
b = polygon[i];
area += a[1] * b[0] - a[0] * b[1];
}
return area / 2;
}
function centroid(polygon) {
var i = -1,
n = polygon.length,
x = 0,
y = 0,
a,
b = polygon[n - 1],
c,
k = 0;
while (++i < n) {
a = b;
b = polygon[i];
k += c = a[0] * b[1] - b[0] * a[1];
x += (a[0] + b[0]) * c;
y += (a[1] + b[1]) * c;
}
return k *= 3, [x / k, y / k];
}
// Returns the 2D cross product of AB and AC vectors, i.e., the z-component of
// the 3D cross product in a quadrant I Cartesian coordinate system (+x is
// right, +y is up). Returns a positive value if ABC is counter-clockwise,
// negative if clockwise, and zero if the points are collinear.
function cross(a, b, c) {
return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]);
}
function lexicographicOrder(a, b) {
return a[0] - b[0] || a[1] - b[1];
}
// Computes the upper convex hull per the monotone chain algorithm.
// Assumes points.length >= 3, is sorted by x, unique in y.
// Returns an array of indices into points in left-to-right order.
function computeUpperHullIndexes(points) {
var n = points.length,
indexes = [0, 1],
size = 2;
for (var i = 2; i < n; ++i) {
while (size > 1 && cross(points[indexes[size - 2]], points[indexes[size - 1]], points[i]) <= 0) --size;
indexes[size++] = i;
}
return indexes.slice(0, size); // remove popped points
}
function hull(points) {
if ((n = points.length) < 3) return null;
var i,
n,
sortedPoints = new Array(n),
flippedPoints = new Array(n);
for (i = 0; i < n; ++i) sortedPoints[i] = [+points[i][0], +points[i][1], i];
sortedPoints.sort(lexicographicOrder);
for (i = 0; i < n; ++i) flippedPoints[i] = [sortedPoints[i][0], -sortedPoints[i][1]];
var upperIndexes = computeUpperHullIndexes(sortedPoints),
lowerIndexes = computeUpperHullIndexes(flippedPoints);
// Construct the hull polygon, removing possible duplicate endpoints.
var skipLeft = lowerIndexes[0] === upperIndexes[0],
skipRight = lowerIndexes[lowerIndexes.length - 1] === upperIndexes[upperIndexes.length - 1],
hull = [];
// Add upper hull in right-to-l order.
// Then add lower hull in left-to-right order.
for (i = upperIndexes.length - 1; i >= 0; --i) hull.push(points[sortedPoints[upperIndexes[i]][2]]);
for (i = +skipLeft; i < lowerIndexes.length - skipRight; ++i) hull.push(points[sortedPoints[lowerIndexes[i]][2]]);
return hull;
}
function contains(polygon, point) {
var n = polygon.length,
p = polygon[n - 1],
x = point[0], y = point[1],
x0 = p[0], y0 = p[1],
x1, y1,
inside = false;
for (var i = 0; i < n; ++i) {
p = polygon[i], x1 = p[0], y1 = p[1];
if (((y1 > y) !== (y0 > y)) && (x < (x0 - x1) * (y - y1) / (y0 - y1) + x1)) inside = !inside;
x0 = x1, y0 = y1;
}
return inside;
}
function length$1(polygon) {
var i = -1,
n = polygon.length,
b = polygon[n - 1],
xa,
ya,
xb = b[0],
yb = b[1],
perimeter = 0;
while (++i < n) {
xa = xb;
ya = yb;
b = polygon[i];
xb = b[0];
yb = b[1];
xa -= xb;
ya -= yb;
perimeter += Math.sqrt(xa * xa + ya * ya);
}
return perimeter;
}
var pi$1 = Math.PI;
var tau$1 = 2 * pi$1;
var epsilon = 1e-6;
var tauEpsilon = tau$1 - epsilon;
function Path() {
this._x0 = this._y0 = // start of current subpath
this._x1 = this._y1 = null; // end of current subpath
this._ = [];
}
function path() {
return new Path;
}
Path.prototype = path.prototype = {
constructor: Path,
moveTo: function(x, y) {
this._.push("M", this._x0 = this._x1 = +x, ",", this._y0 = this._y1 = +y);
},
closePath: function() {
if (this._x1 !== null) {
this._x1 = this._x0, this._y1 = this._y0;
this._.push("Z");
}
},
lineTo: function(x, y) {
this._.push("L", this._x1 = +x, ",", this._y1 = +y);
},
quadraticCurveTo: function(x1, y1, x, y) {
this._.push("Q", +x1, ",", +y1, ",", this._x1 = +x, ",", this._y1 = +y);
},
bezierCurveTo: function(x1, y1, x2, y2, x, y) {
this._.push("C", +x1, ",", +y1, ",", +x2, ",", +y2, ",", this._x1 = +x, ",", this._y1 = +y);
},
arcTo: function(x1, y1, x2, y2, r) {
x1 = +x1, y1 = +y1, x2 = +x2, y2 = +y2, r = +r;
var x0 = this._x1,
y0 = this._y1,
x21 = x2 - x1,
y21 = y2 - y1,
x01 = x0 - x1,
y01 = y0 - y1,
l01_2 = x01 * x01 + y01 * y01;
// Is the radius negative? Error.
if (r < 0) throw new Error("negative radius: " + r);
// Is this path empty? Move to (x1,y1).
if (this._x1 === null) {
this._.push(
"M", this._x1 = x1, ",", this._y1 = y1
);
}
// Or, is (x1,y1) coincident with (x0,y0)? Do nothing.
else if (!(l01_2 > epsilon));
// Or, are (x0,y0), (x1,y1) and (x2,y2) collinear?
// Equivalently, is (x1,y1) coincident with (x2,y2)?
// Or, is the radius zero? Line to (x1,y1).
else if (!(Math.abs(y01 * x21 - y21 * x01) > epsilon) || !r) {
this._.push(
"L", this._x1 = x1, ",", this._y1 = y1
);
}
// Otherwise, draw an arc!
else {
var x20 = x2 - x0,
y20 = y2 - y0,
l21_2 = x21 * x21 + y21 * y21,
l20_2 = x20 * x20 + y20 * y20,
l21 = Math.sqrt(l21_2),
l01 = Math.sqrt(l01_2),
l = r * Math.tan((pi$1 - Math.acos((l21_2 + l01_2 - l20_2) / (2 * l21 * l01))) / 2),
t01 = l / l01,
t21 = l / l21;
// If the start tangent is not coincident with (x0,y0), line to.
if (Math.abs(t01 - 1) > epsilon) {
this._.push(
"L", x1 + t01 * x01, ",", y1 + t01 * y01
);
}
this._.push(
"A", r, ",", r, ",0,0,", +(y01 * x20 > x01 * y20), ",", this._x1 = x1 + t21 * x21, ",", this._y1 = y1 + t21 * y21
);
}
},
arc: function(x, y, r, a0, a1, ccw) {
x = +x, y = +y, r = +r;
var dx = r * Math.cos(a0),
dy = r * Math.sin(a0),
x0 = x + dx,
y0 = y + dy,
cw = 1 ^ ccw,
da = ccw ? a0 - a1 : a1 - a0;
// Is the radius negative? Error.
if (r < 0) throw new Error("negative radius: " + r);
// Is this path empty? Move to (x0,y0).
if (this._x1 === null) {
this._.push(
"M", x0, ",", y0
);
}
// Or, is (x0,y0) not coincident with the previous point? Line to (x0,y0).
else if (Math.abs(this._x1 - x0) > epsilon || Math.abs(this._y1 - y0) > epsilon) {
this._.push(
"L", x0, ",", y0
);
}
// Is this arc empty? We’re done.
if (!r) return;
// Is this a complete circle? Draw two arcs to complete the circle.
if (da > tauEpsilon) {
this._.push(
"A", r, ",", r, ",0,1,", cw, ",", x - dx, ",", y - dy,
"A", r, ",", r, ",0,1,", cw, ",", this._x1 = x0, ",", this._y1 = y0
);
}
// Otherwise, draw an arc!
else {
if (da < 0) da = da % tau$1 + tau$1;
this._.push(
"A", r, ",", r, ",0,", +(da >= pi$1), ",", cw, ",", this._x1 = x + r * Math.cos(a1), ",", this._y1 = y + r * Math.sin(a1)
);
}
},
rect: function(x, y, w, h) {
this._.push("M", this._x0 = this._x1 = +x, ",", this._y0 = this._y1 = +y, "h", +w, "v", +h, "h", -w, "Z");
},
toString: function() {
return this._.join("");
}
};
function tree_add(d) {
var x = +this._x.call(null, d),
y = +this._y.call(null, d);
return add(this.cover(x, y), x, y, d);
}
function add(tree, x, y, d) {
if (isNaN(x) || isNaN(y)) return tree; // ignore invalid points
var parent,
node = tree._root,
leaf = {data: d},
x0 = tree._x0,
y0 = tree._y0,
x1 = tree._x1,
y1 = tree._y1,
xm,
ym,
xp,
yp,
right,
bottom,
i,
j;
// If the tree is empty, initialize the root as a leaf.
if (!node) return tree._root = leaf, tree;
// Find the existing leaf for the new point, or add it.
while (node.length) {
if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm;
if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym;
if (parent = node, !(node = node[i = bottom << 1 | right])) return parent[i] = leaf, tree;
}
// Is the new point is exactly coincident with the existing point?
xp = +tree._x.call(null, node.data);
yp = +tree._y.call(null, node.data);
if (x === xp && y === yp) return leaf.next = node, parent ? parent[i] = leaf : tree._root = leaf, tree;
// Otherwise, split the leaf node until the old and new point are separated.
do {
parent = parent ? parent[i] = new Array(4) : tree._root = new Array(4);
if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm;
if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym;
} while ((i = bottom << 1 | right) === (j = (yp >= ym) << 1 | (xp >= xm)));
return parent[j] = node, parent[i] = leaf, tree;
}
function addAll(data) {
var d, i, n = data.length,
x,
y,
xz = new Array(n),
yz = new Array(n),
x0 = Infinity,
y0 = Infinity,
x1 = -Infinity,
y1 = -Infinity;
// Compute the points and their extent.
for (i = 0; i < n; ++i) {
if (isNaN(x = +this._x.call(null, d = data[i])) || isNaN(y = +this._y.call(null, d))) continue;
xz[i] = x;
yz[i] = y;
if (x < x0) x0 = x;
if (x > x1) x1 = x;
if (y < y0) y0 = y;
if (y > y1) y1 = y;
}
// If there were no (valid) points, inherit the existing extent.
if (x1 < x0) x0 = this._x0, x1 = this._x1;
if (y1 < y0) y0 = this._y0, y1 = this._y1;
// Expand the tree to cover the new points.
this.cover(x0, y0).cover(x1, y1);
// Add the new points.
for (i = 0; i < n; ++i) {
add(this, xz[i], yz[i], data[i]);
}
return this;
}
function tree_cover(x, y) {
if (isNaN(x = +x) || isNaN(y = +y)) return this; // ignore invalid points
var x0 = this._x0,
y0 = this._y0,
x1 = this._x1,
y1 = this._y1;
// If the quadtree has no extent, initialize them.
// Integer extent are necessary so that if we later double the extent,
// the existing quadrant boundaries don’t change due to floating point error!
if (isNaN(x0)) {
x1 = (x0 = Math.floor(x)) + 1;
y1 = (y0 = Math.floor(y)) + 1;
}
// Otherwise, double repeatedly to cover.
else if (x0 > x || x > x1 || y0 > y || y > y1) {
var z = x1 - x0,
node = this._root,
parent,
i;
switch (i = (y < (y0 + y1) / 2) << 1 | (x < (x0 + x1) / 2)) {
case 0: {
do parent = new Array(4), parent[i] = node, node = parent;
while (z *= 2, x1 = x0 + z, y1 = y0 + z, x > x1 || y > y1);
break;
}
case 1: {
do parent = new Array(4), parent[i] = node, node = parent;
while (z *= 2, x0 = x1 - z, y1 = y0 + z, x0 > x || y > y1);
break;
}
case 2: {
do parent = new Array(4), parent[i] = node, node = parent;
while (z *= 2, x1 = x0 + z, y0 = y1 - z, x > x1 || y0 > y);
break;
}
case 3: {
do parent = new Array(4), parent[i] = node, node = parent;
while (z *= 2, x0 = x1 - z, y0 = y1 - z, x0 > x || y0 > y);
break;
}
}
if (this._root && this._root.length) this._root = node;
}
// If the quadtree covers the point already, just return.
else return this;
this._x0 = x0;
this._y0 = y0;
this._x1 = x1;
this._y1 = y1;
return this;
}
function tree_data() {
var data = [];
this.visit(function(node) {
if (!node.length) do data.push(node.data); while (node = node.next)
});
return data;
}
function tree_extent(_) {
return arguments.length
? this.cover(+_[0][0], +_[0][1]).cover(+_[1][0], +_[1][1])
: isNaN(this._x0) ? undefined : [[this._x0, this._y0], [this._x1, this._y1]];
}
function Quad(node, x0, y0, x1, y1) {
this.node = node;
this.x0 = x0;
this.y0 = y0;
this.x1 = x1;
this.y1 = y1;
}
function tree_find(x, y, radius) {
var data,
x0 = this._x0,
y0 = this._y0,
x1,
y1,
x2,
y2,
x3 = this._x1,
y3 = this._y1,
quads = [],
node = this._root,
q,
i;
if (node) quads.push(new Quad(node, x0, y0, x3, y3));
if (radius == null) radius = Infinity;
else {
x0 = x - radius, y0 = y - radius;
x3 = x + radius, y3 = y + radius;
radius *= radius;
}
while (q = quads.pop()) {
// Stop searching if this quadrant can’t contain a closer node.
if (!(node = q.node)
|| (x1 = q.x0) > x3
|| (y1 = q.y0) > y3
|| (x2 = q.x1) < x0
|| (y2 = q.y1) < y0) continue;
// Bisect the current quadrant.
if (node.length) {
var xm = (x1 + x2) / 2,
ym = (y1 + y2) / 2;
quads.push(
new Quad(node[3], xm, ym, x2, y2),
new Quad(node[2], x1, ym, xm, y2),
new Quad(node[1], xm, y1, x2, ym),
new Quad(node[0], x1, y1, xm, ym)
);
// Visit the closest quadrant first.
if (i = (y >= ym) << 1 | (x >= xm)) {
q = quads[quads.length - 1];
quads[quads.length - 1] = quads[quads.length - 1 - i];
quads[quads.length - 1 - i] = q;
}
}
// Visit this point. (Visiting coincident points isn’t necessary!)
else {
var dx = x - +this._x.call(null, node.data),
dy = y - +this._y.call(null, node.data),
d2 = dx * dx + dy * dy;
if (d2 < radius) {
var d = Math.sqrt(radius = d2);
x0 = x - d, y0 = y - d;
x3 = x + d, y3 = y + d;
data = node.data;
}
}
}
return data;
}
function tree_remove(d) {
if (isNaN(x = +this._x.call(null, d)) || isNaN(y = +this._y.call(null, d))) return this; // ignore invalid points
var parent,
node = this._root,
retainer,
previous,
next,
x0 = this._x0,
y0 = this._y0,
x1 = this._x1,
y1 = this._y1,
x,
y,
xm,
ym,
right,
bottom,
i,
j;
// If the tree is empty, initialize the root as a leaf.
if (!node) return this;
// Find the leaf node for the point.
// While descending, also retain the deepest parent with a non-removed sibling.
if (node.length) while (true) {
if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm;
if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym;
if (!(parent = node, node = node[i = bottom << 1 | right])) return this;
if (!node.length) break;
if (parent[(i + 1) & 3] || parent[(i + 2) & 3] || parent[(i + 3) & 3]) retainer = parent, j = i;
}
// Find the point to remove.
while (node.data !== d) if (!(previous = node, node = node.next)) return this;
if (next = node.next) delete node.next;
// If there are multiple coincident points, remove just the point.
if (previous) return (next ? previous.next = next : delete previous.next), this;
// If this is the root point, remove it.
if (!parent) return this._root = next, this;
// Remove this leaf.
next ? parent[i] = next : delete parent[i];
// If the parent now contains exactly one leaf, collapse superfluous parents.
if ((node = parent[0] || parent[1] || parent[2] || parent[3])
&& node === (parent[3] || parent[2] || parent[1] || parent[0])
&& !node.length) {
if (retainer) retainer[j] = node;
else this._root = node;
}
return this;
}
function removeAll(data) {
for (var i = 0, n = data.length; i < n; ++i) this.remove(data[i]);
return this;
}
function tree_root() {
return this._root;
}
function tree_size() {
var size = 0;
this.visit(function(node) {
if (!node.length) do ++size; while (node = node.next)
});
return size;
}
function tree_visit(callback) {
var quads = [], q, node = this._root, child, x0, y0, x1, y1;
if (node) quads.push(new Quad(node, this._x0, this._y0, this._x1, this._y1));
while (q = quads.pop()) {
if (!callback(node = q.node, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1) && node.length) {
var xm = (x0 + x1) / 2, ym = (y0 + y1) / 2;
if (child = node[3]) quads.push(new Quad(child, xm, ym, x1, y1));
if (child = node[2]) quads.push(new Quad(child, x0, ym, xm, y1));
if (child = node[1]) quads.push(new Quad(child, xm, y0, x1, ym));
if (child = node[0]) quads.push(new Quad(child, x0, y0, xm, ym));
}
}
return this;
}
function tree_visitAfter(callback) {
var quads = [], next = [], q;
if (this._root) quads.push(new Quad(this._root, this._x0, this._y0, this._x1, this._y1));
while (q = quads.pop()) {
var node = q.node;
if (node.length) {
var child, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1, xm = (x0 + x1) / 2, ym = (y0 + y1) / 2;
if (child = node[0]) quads.push(new Quad(child, x0, y0, xm, ym));
if (child = node[1]) quads.push(new Quad(child, xm, y0, x1, ym));
if (child = node[2]) quads.push(new Quad(child, x0, ym, xm, y1));
if (child = node[3]) quads.push(new Quad(child, xm, ym, x1, y1));
}
next.push(q);
}
while (q = next.pop()) {
callback(q.node, q.x0, q.y0, q.x1, q.y1);
}
return this;
}
function defaultX(d) {
return d[0];
}
function tree_x(_) {
return arguments.length ? (this._x = _, this) : this._x;
}
function defaultY(d) {
return d[1];
}
function tree_y(_) {
return arguments.length ? (this._y = _, this) : this._y;
}
function quadtree(nodes, x, y) {
var tree = new Quadtree(x == null ? defaultX : x, y == null ? defaultY : y, NaN, NaN, NaN, NaN);
return nodes == null ? tree : tree.addAll(nodes);
}
function Quadtree(x, y, x0, y0, x1, y1) {
this._x = x;
this._y = y;
this._x0 = x0;
this._y0 = y0;
this._x1 = x1;
this._y1 = y1;
this._root = undefined;
}
function leaf_copy(leaf) {
var copy = {data: leaf.data}, next = copy;
while (leaf = leaf.next) next = next.next = {data: leaf.data};
return copy;
}
var treeProto = quadtree.prototype = Quadtree.prototype;
treeProto.copy = function() {
var copy = new Quadtree(this._x, this._y, this._x0, this._y0, this._x1, this._y1),
node = this._root,
nodes,
child;
if (!node) return copy;
if (!node.length) return copy._root = leaf_copy(node), copy;
nodes = [{source: node, target: copy._root = new Array(4)}];
while (node = nodes.pop()) {
for (var i = 0; i < 4; ++i) {
if (child = node.source[i]) {
if (child.length) nodes.push({source: child, target: node.target[i] = new Array(4)});
else node.target[i] = leaf_copy(child);
}
}
}
return copy;
};
treeProto.add = tree_add;
treeProto.addAll = addAll;
treeProto.cover = tree_cover;
treeProto.data = tree_data;
treeProto.extent = tree_extent;
treeProto.find = tree_find;
treeProto.remove = tree_remove;
treeProto.removeAll = removeAll;
treeProto.root = tree_root;
treeProto.size = tree_size;
treeProto.visit = tree_visit;
treeProto.visitAfter = tree_visitAfter;
treeProto.x = tree_x;
treeProto.y = tree_y;
var slice$1 = [].slice;
var noabort = {};
function Queue(size) {
if (!(size >= 1)) throw new Error;
this._size = size;
this._call =
this._error = null;
this._tasks = [];
this._data = [];
this._waiting =
this._active =
this._ended =
this._start = 0; // inside a synchronous task callback?
}
Queue.prototype = queue.prototype = {
constructor: Queue,
defer: function(callback) {
if (typeof callback !== "function" || this._call) throw new Error;
if (this._error != null) return this;
var t = slice$1.call(arguments, 1);
t.push(callback);
++this._waiting, this._tasks.push(t);
poke(this);
return this;
},
abort: function() {
if (this._error == null) abort(this, new Error("abort"));
return this;
},
await: function(callback) {
if (typeof callback !== "function" || this._call) throw new Error;
this._call = function(error, results) { callback.apply(null, [error].concat(results)); };
maybeNotify(this);
return this;
},
awaitAll: function(callback) {
if (typeof callback !== "function" || this._call) throw new Error;
this._call = callback;
maybeNotify(this);
return this;
}
};
function poke(q) {
if (!q._start) {
try { start(q); } // let the current task complete
catch (e) {
if (q._tasks[q._ended + q._active - 1]) abort(q, e); // task errored synchronously
else if (!q._data) throw e; // await callback errored synchronously
}
}
}
function start(q) {
while (q._start = q._waiting && q._active < q._size) {
var i = q._ended + q._active,
t = q._tasks[i],
j = t.length - 1,
c = t[j];
t[j] = end(q, i);
--q._waiting, ++q._active;
t = c.apply(null, t);
if (!q._tasks[i]) continue; // task finished synchronously
q._tasks[i] = t || noabort;
}
}
function end(q, i) {
return function(e, r) {
if (!q._tasks[i]) return; // ignore multiple callbacks
--q._active, ++q._ended;
q._tasks[i] = null;
if (q._error != null) return; // ignore secondary errors
if (e != null) {
abort(q, e);
} else {
q._data[i] = r;
if (q._waiting) poke(q);
else maybeNotify(q);
}
};
}
function abort(q, e) {
var i = q._tasks.length, t;
q._error = e; // ignore active callbacks
q._data = undefined; // allow gc
q._waiting = NaN; // prevent starting
while (--i >= 0) {
if (t = q._tasks[i]) {
q._tasks[i] = null;
if (t.abort) {
try { t.abort(); }
catch (e) { /* ignore */ }
}
}
}
q._active = NaN; // allow notification
maybeNotify(q);
}
function maybeNotify(q) {
if (!q._active && q._call) {
var d = q._data;
q._data = undefined; // allow gc
q._call(q._error, d);
}
}
function queue(concurrency) {
return new Queue(arguments.length ? +concurrency : Infinity);
}
function constant$1(x) {
return function constant() {
return x;
};
}
var epsilon$1 = 1e-12;
var pi$2 = Math.PI;
var halfPi$1 = pi$2 / 2;
var tau$2 = 2 * pi$2;
function arcInnerRadius(d) {
return d.innerRadius;
}
function arcOuterRadius(d) {
return d.outerRadius;
}
function arcStartAngle(d) {
return d.startAngle;
}
function arcEndAngle(d) {
return d.endAngle;
}
function arcPadAngle(d) {
return d && d.padAngle; // Note: optional!
}
function asin(x) {
return x >= 1 ? halfPi$1 : x <= -1 ? -halfPi$1 : Math.asin(x);
}
function intersect(x0, y0, x1, y1, x2, y2, x3, y3) {
var x10 = x1 - x0, y10 = y1 - y0,
x32 = x3 - x2, y32 = y3 - y2,
t = (x32 * (y0 - y2) - y32 * (x0 - x2)) / (y32 * x10 - x32 * y10);
return [x0 + t * x10, y0 + t * y10];
}
// Compute perpendicular offset line of length rc.
// http://mathworld.wolfram.com/Circle-LineIntersection.html
function cornerTangents(x0, y0, x1, y1, r1, rc, cw) {
var x01 = x0 - x1,
y01 = y0 - y1,
lo = (cw ? rc : -rc) / Math.sqrt(x01 * x01 + y01 * y01),
ox = lo * y01,
oy = -lo * x01,
x11 = x0 + ox,
y11 = y0 + oy,
x10 = x1 + ox,
y10 = y1 + oy,
x00 = (x11 + x10) / 2,
y00 = (y11 + y10) / 2,
dx = x10 - x11,
dy = y10 - y11,
d2 = dx * dx + dy * dy,
r = r1 - rc,
D = x11 * y10 - x10 * y11,
d = (dy < 0 ? -1 : 1) * Math.sqrt(Math.max(0, r * r * d2 - D * D)),
cx0 = (D * dy - dx * d) / d2,
cy0 = (-D * dx - dy * d) / d2,
cx1 = (D * dy + dx * d) / d2,
cy1 = (-D * dx + dy * d) / d2,
dx0 = cx0 - x00,
dy0 = cy0 - y00,
dx1 = cx1 - x00,
dy1 = cy1 - y00;
// Pick the closer of the two intersection points.
// TODO Is there a faster way to determine which intersection to use?
if (dx0 * dx0 + dy0 * dy0 > dx1 * dx1 + dy1 * dy1) cx0 = cx1, cy0 = cy1;
return {
cx: cx0,
cy: cy0,
x01: -ox,
y01: -oy,
x11: cx0 * (r1 / r - 1),
y11: cy0 * (r1 / r - 1)
};
}
function arc() {
var innerRadius = arcInnerRadius,
outerRadius = arcOuterRadius,
cornerRadius = constant$1(0),
padRadius = null,
startAngle = arcStartAngle,
endAngle = arcEndAngle,
padAngle = arcPadAngle,
context = null;
function arc() {
var buffer,
r,
r0 = +innerRadius.apply(this, arguments),
r1 = +outerRadius.apply(this, arguments),
a0 = startAngle.apply(this, arguments) - halfPi$1,
a1 = endAngle.apply(this, arguments) - halfPi$1,
da = Math.abs(a1 - a0),
cw = a1 > a0;
if (!context) context = buffer = path();
// Ensure that the outer radius is always larger than the inner radius.
if (r1 < r0) r = r1, r1 = r0, r0 = r;
// Is it a point?
if (!(r1 > epsilon$1)) context.moveTo(0, 0);
// Or is it a circle or annulus?
else if (da > tau$2 - epsilon$1) {
context.moveTo(r1 * Math.cos(a0), r1 * Math.sin(a0));
context.arc(0, 0, r1, a0, a1, !cw);
if (r0 > epsilon$1) {
context.moveTo(r0 * Math.cos(a1), r0 * Math.sin(a1));
context.arc(0, 0, r0, a1, a0, cw);
}
}
// Or is it a circular or annular sector?
else {
var a01 = a0,
a11 = a1,
a00 = a0,
a10 = a1,
da0 = da,
da1 = da,
ap = padAngle.apply(this, arguments) / 2,
rp = (ap > epsilon$1) && (padRadius ? +padRadius.apply(this, arguments) : Math.sqrt(r0 * r0 + r1 * r1)),
rc = Math.min(Math.abs(r1 - r0) / 2, +cornerRadius.apply(this, arguments)),
rc0 = rc,
rc1 = rc,
t0,
t1;
// Apply padding? Note that since r1 ≥ r0, da1 ≥ da0.
if (rp > epsilon$1) {
var p0 = asin(rp / r0 * Math.sin(ap)),
p1 = asin(rp / r1 * Math.sin(ap));
if ((da0 -= p0 * 2) > epsilon$1) p0 *= (cw ? 1 : -1), a00 += p0, a10 -= p0;
else da0 = 0, a00 = a10 = (a0 + a1) / 2;
if ((da1 -= p1 * 2) > epsilon$1) p1 *= (cw ? 1 : -1), a01 += p1, a11 -= p1;
else da1 = 0, a01 = a11 = (a0 + a1) / 2;
}
var x01 = r1 * Math.cos(a01),
y01 = r1 * Math.sin(a01),
x10 = r0 * Math.cos(a10),
y10 = r0 * Math.sin(a10);
// Apply rounded corners?
if (rc > epsilon$1) {
var x11 = r1 * Math.cos(a11),
y11 = r1 * Math.sin(a11),
x00 = r0 * Math.cos(a00),
y00 = r0 * Math.sin(a00);
// Restrict the corner radius according to the sector angle.
if (da < pi$2) {
var oc = da0 > epsilon$1 ? intersect(x01, y01, x00, y00, x11, y11, x10, y10) : [x10, y10],
ax = x01 - oc[0],
ay = y01 - oc[1],
bx = x11 - oc[0],
by = y11 - oc[1],
kc = 1 / Math.sin(Math.acos((ax * bx + ay * by) / (Math.sqrt(ax * ax + ay * ay) * Math.sqrt(bx * bx + by * by))) / 2),
lc = Math.sqrt(oc[0] * oc[0] + oc[1] * oc[1]);
rc0 = Math.min(rc, (r0 - lc) / (kc - 1));
rc1 = Math.min(rc, (r1 - lc) / (kc + 1));
}
}
// Is the sector collapsed to a line?
if (!(da1 > epsilon$1)) context.moveTo(x01, y01);
// Does the sector’s outer ring have rounded corners?
else if (rc1 > epsilon$1) {
t0 = cornerTangents(x00, y00, x01, y01, r1, rc1, cw);
t1 = cornerTangents(x11, y11, x10, y10, r1, rc1, cw);
context.moveTo(t0.cx + t0.x01, t0.cy + t0.y01);
// Have the corners merged?
if (rc1 < rc) context.arc(t0.cx, t0.cy, rc1, Math.atan2(t0.y01, t0.x01), Math.atan2(t1.y01, t1.x01), !cw);
// Otherwise, draw the two corners and the ring.
else {
context.arc(t0.cx, t0.cy, rc1, Math.atan2(t0.y01, t0.x01), Math.atan2(t0.y11, t0.x11), !cw);
context.arc(0, 0, r1, Math.atan2(t0.cy + t0.y11, t0.cx + t0.x11), Math.atan2(t1.cy + t1.y11, t1.cx + t1.x11), !cw);
context.arc(t1.cx, t1.cy, rc1, Math.atan2(t1.y11, t1.x11), Math.atan2(t1.y01, t1.x01), !cw);
}
}
// Or is the outer ring just a circular arc?
else context.moveTo(x01, y01), context.arc(0, 0, r1, a01, a11, !cw);
// Is there no inner ring, and it’s a circular sector?
// Or perhaps it’s an annular sector collapsed due to padding?
if (!(r0 > epsilon$1) || !(da0 > epsilon$1)) context.lineTo(x10, y10);
// Does the sector’s inner ring (or point) have rounded corners?
else if (rc0 > epsilon$1) {
t0 = cornerTangents(x10, y10, x11, y11, r0, -rc0, cw);
t1 = cornerTangents(x01, y01, x00, y00, r0, -rc0, cw);
context.lineTo(t0.cx + t0.x01, t0.cy + t0.y01);
// Have the corners merged?
if (rc0 < rc) context.arc(t0.cx, t0.cy, rc0, Math.atan2(t0.y01, t0.x01), Math.atan2(t1.y01, t1.x01), !cw);
// Otherwise, draw the two corners and the ring.
else {
context.arc(t0.cx, t0.cy, rc0, Math.atan2(t0.y01, t0.x01), Math.atan2(t0.y11, t0.x11), !cw);
context.arc(0, 0, r0, Math.atan2(t0.cy + t0.y11, t0.cx + t0.x11), Math.atan2(t1.cy + t1.y11, t1.cx + t1.x11), cw);
context.arc(t1.cx, t1.cy, rc0, Math.atan2(t1.y11, t1.x11), Math.atan2(t1.y01, t1.x01), !cw);
}
}
// Or is the inner ring just a circular arc?
else context.arc(0, 0, r0, a10, a00, cw);
}
context.closePath();
if (buffer) return context = null, buffer + "" || null;
}
arc.centroid = function() {
var r = (+innerRadius.apply(this, arguments) + +outerRadius.apply(this, arguments)) / 2,
a = (+startAngle.apply(this, arguments) + +endAngle.apply(this, arguments)) / 2 - pi$2 / 2;
return [Math.cos(a) * r, Math.sin(a) * r];
};
arc.innerRadius = function(_) {
return arguments.length ? (innerRadius = typeof _ === "function" ? _ : constant$1(+_), arc) : innerRadius;
};
arc.outerRadius = function(_) {
return arguments.length ? (outerRadius = typeof _ === "function" ? _ : constant$1(+_), arc) : outerRadius;
};
arc.cornerRadius = function(_) {
return arguments.length ? (cornerRadius = typeof _ === "function" ? _ : constant$1(+_), arc) : cornerRadius;
};
arc.padRadius = function(_) {
return arguments.length ? (padRadius = _ == null ? null : typeof _ === "function" ? _ : constant$1(+_), arc) : padRadius;
};
arc.startAngle = function(_) {
return arguments.length ? (startAngle = typeof _ === "function" ? _ : constant$1(+_), arc) : startAngle;
};
arc.endAngle = function(_) {
return arguments.length ? (endAngle = typeof _ === "function" ? _ : constant$1(+_), arc) : endAngle;
};
arc.padAngle = function(_) {
return arguments.length ? (padAngle = typeof _ === "function" ? _ : constant$1(+_), arc) : padAngle;
};
arc.context = function(_) {
return arguments.