|
// https://d3js.org Version 4.0.0. Copyright 2016 Mike Bostock. |
|
(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'; |
|
|
|
var version = "4.0.0"; |
|
|
|
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 keys(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 |
|
} |
|
|
|
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) q._call(q._error, q._data); |
|
} |
|
|
|
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.length ? ((context = _ == null ? null : _), arc) : context; |
|
}; |
|
|
|
return arc; |
|
} |
|
|
|
function Linear(context) { |
|
this._context = context; |
|
} |
|
|
|
Linear.prototype = { |
|
areaStart: function() { |
|
this._line = 0; |
|
}, |
|
areaEnd: function() { |
|
this._line = NaN; |
|
}, |
|
lineStart: function() { |
|
this._point = 0; |
|
}, |
|
lineEnd: function() { |
|
if (this._line || (this._line !== 0 && this._point === 1)) this._context.closePath(); |
|
this._line = 1 - this._line; |
|
}, |
|
point: function(x, y) { |
|
x = +x, y = +y; |
|
switch (this._point) { |
|
case 0: this._point = 1; this._line ? this._context.lineTo(x, y) : this._context.moveTo(x, y); break; |
|
case 1: this._point = 2; // proceed |
|
default: this._context.lineTo(x, y); break; |
|
} |
|
} |
|
}; |
|
|
|
function curveLinear(context) { |
|
return new Linear(context); |
|
} |
|
|
|
function x(p) { |
|
return p[0]; |
|
} |
|
|
|
function y(p) { |
|
return p[1]; |
|
} |
|
|
|
function line() { |
|
var x$$ = x, |
|
y$$ = y, |
|
defined = constant$1(true), |
|
context = null, |
|
curve = curveLinear, |
|
output = null; |
|
|
|
function line(data) { |
|
var i, |
|
n = data.length, |
|
d, |
|
defined0 = false, |
|
buffer; |
|
|
|
if (context == null) output = curve(buffer = path()); |
|
|
|
for (i = 0; i <= n; ++i) { |
|
if (!(i < n && defined(d = data[i], i, data)) === defined0) { |
|
if (defined0 = !defined0) output.lineStart(); |
|
else output.lineEnd(); |
|
} |
|
if (defined0) output.point(+x$$(d, i, data), +y$$(d, i, data)); |
|
} |
|
|
|
if (buffer) return output = null, buffer + "" || null; |
|
} |
|
|
|
line.x = function(_) { |
|
return arguments.length ? (x$$ = typeof _ === "function" ? _ : constant$1(+_), line) : x$$; |
|
}; |
|
|
|
line.y = function(_) { |
|
return arguments.length ? (y$$ = typeof _ === "function" ? _ : constant$1(+_), line) : y$$; |
|
}; |
|
|
|
line.defined = function(_) { |
|
return arguments.length ? (defined = typeof _ === "function" ? _ : constant$1(!!_), line) : defined; |
|
}; |
|
|
|
line.curve = function(_) { |
|
return arguments.length ? (curve = _, context != null && (output = curve(context)), line) : curve; |
|
}; |
|
|
|
line.context = function(_) { |
|
return arguments.length ? (_ == null ? context = output = null : output = curve(context = _), line) : context; |
|
}; |
|
|
|
return line; |
|
} |
|
|
|
function area$1() { |
|
var x0 = x, |
|
x1 = null, |
|
y0 = constant$1(0), |
|
y1 = y, |
|
defined = constant$1(true), |
|
context = null, |
|
curve = curveLinear, |
|
output = null; |
|
|
|
function area(data) { |
|
var i, |
|
j, |
|
k, |
|
n = data.length, |
|
d, |
|
defined0 = false, |
|
buffer, |
|
x0z = new Array(n), |
|
y0z = new Array(n); |
|
|
|
if (context == null) output = curve(buffer = path()); |
|
|
|
for (i = 0; i <= n; ++i) { |
|
if (!(i < n && defined(d = data[i], i, data)) === defined0) { |
|
if (defined0 = !defined0) { |
|
j = i; |
|
output.areaStart(); |
|
output.lineStart(); |
|
} else { |
|
output.lineEnd(); |
|
output.lineStart(); |
|
for (k = i - 1; k >= j; --k) { |
|
output.point(x0z[k], y0z[k]); |
|
} |
|
output.lineEnd(); |
|
output.areaEnd(); |
|
} |
|
} |
|
if (defined0) { |
|
x0z[i] = +x0(d, i, data), y0z[i] = +y0(d, i, data); |
|
output.point(x1 ? +x1(d, i, data) : x0z[i], y1 ? +y1(d, i, data) : y0z[i]); |
|
} |
|
} |
|
|
|
if (buffer) return output = null, buffer + "" || null; |
|
} |
|
|
|
function arealine() { |
|
return line().defined(defined).curve(curve).context(context); |
|
} |
|
|
|
area.x = function(_) { |
|
return arguments.length ? (x0 = typeof _ === "function" ? _ : constant$1(+_), x1 = null, area) : x0; |
|
}; |
|
|
|
area.x0 = function(_) { |
|
return arguments.length ? (x0 = typeof _ === "function" ? _ : constant$1(+_), area) : x0; |
|
}; |
|
|
|
area.x1 = function(_) { |
|
return arguments.length ? (x1 = _ == null ? null : typeof _ === "function" ? _ : constant$1(+_), area) : x1; |
|
}; |
|
|
|
area.y = function(_) { |
|
return arguments.length ? (y0 = typeof _ === "function" ? _ : constant$1(+_), y1 = null, area) : y0; |
|
}; |
|
|
|
area.y0 = function(_) { |
|
return arguments.length ? (y0 = typeof _ === "function" ? _ : constant$1(+_), area) : y0; |
|
}; |
|
|
|
area.y1 = function(_) { |
|
return arguments.length ? (y1 = _ == null ? null : typeof _ === "function" ? _ : constant$1(+_), area) : y1; |
|
}; |
|
|
|
area.lineX0 = |
|
area.lineY0 = function() { |
|
return arealine().x(x0).y(y0); |
|
}; |
|
|
|
area.lineY1 = function() { |
|
return arealine().x(x0).y(y1); |
|
}; |
|
|
|
area.lineX1 = function() { |
|
return arealine().x(x1).y(y0); |
|
}; |
|
|
|
area.defined = function(_) { |
|
return arguments.length ? (defined = typeof _ === "function" ? _ : constant$1(!!_), area) : defined; |
|
}; |
|
|
|
area.curve = function(_) { |
|
return arguments.length ? (curve = _, context != null && (output = curve(context)), area) : curve; |
|
}; |
|
|
|
area.context = function(_) { |
|
return arguments.length ? (_ == null ? context = output = null : output = curve(context = _), area) : context; |
|
}; |
|
|
|
return area; |
|
} |
|
|
|
function descending$1(a, b) { |
|
return b < a ? -1 : b > a ? 1 : b >= a ? 0 : NaN; |
|
} |
|
|
|
function identity$1(d) { |
|
return d; |
|
} |
|
|
|
function pie() { |
|
var value = identity$1, |
|
sortValues = descending$1, |
|
sort = null, |
|
startAngle = constant$1(0), |
|
endAngle = constant$1(tau$2), |
|
padAngle = constant$1(0); |
|
|
|
function pie(data) { |
|
var i, |
|
n = data.length, |
|
j, |
|
k, |
|
sum = 0, |
|
index = new Array(n), |
|
arcs = new Array(n), |
|
a0 = +startAngle.apply(this, arguments), |
|
da = Math.min(tau$2, Math.max(-tau$2, endAngle.apply(this, arguments) - a0)), |
|
a1, |
|
p = Math.min(Math.abs(da) / n, padAngle.apply(this, arguments)), |
|
pa = p * (da < 0 ? -1 : 1), |
|
v; |
|
|
|
for (i = 0; i < n; ++i) { |
|
if ((v = arcs[index[i] = i] = +value(data[i], i, data)) > 0) { |
|
sum += v; |
|
} |
|
} |
|
|
|
// Optionally sort the arcs by previously-computed values or by data. |
|
if (sortValues != null) index.sort(function(i, j) { return sortValues(arcs[i], arcs[j]); }); |
|
else if (sort != null) index.sort(function(i, j) { return sort(data[i], data[j]); }); |
|
|
|
// Compute the arcs! They are stored in the original data's order. |
|
for (i = 0, k = sum ? (da - n * pa) / sum : 0; i < n; ++i, a0 = a1) { |
|
j = index[i], v = arcs[j], a1 = a0 + (v > 0 ? v * k : 0) + pa, arcs[j] = { |
|
data: data[j], |
|
index: i, |
|
value: v, |
|
startAngle: a0, |
|
endAngle: a1, |
|
padAngle: p |
|
}; |
|
} |
|
|
|
return arcs; |
|
} |
|
|
|
pie.value = function(_) { |
|
return arguments.length ? (value = typeof _ === "function" ? _ : constant$1(+_), pie) : value; |
|
}; |
|
|
|
pie.sortValues = function(_) { |
|
return arguments.length ? (sortValues = _, sort = null, pie) : sortValues; |
|
}; |
|
|
|
pie.sort = function(_) { |
|
return arguments.length ? (sort = _, sortValues = null, pie) : sort; |
|
}; |
|
|
|
pie.startAngle = function(_) { |
|
return arguments.length ? (startAngle = typeof _ === "function" ? _ : constant$1(+_), pie) : startAngle; |
|
}; |
|
|
|
pie.endAngle = function(_) { |
|
return arguments.length ? (endAngle = typeof _ === "function" ? _ : constant$1(+_), pie) : endAngle; |
|
}; |
|
|
|
pie.padAngle = function(_) { |
|
return arguments.length ? (padAngle = typeof _ === "function" ? _ : constant$1(+_), pie) : padAngle; |
|
}; |
|
|
|
return pie; |
|
} |
|
|
|
var curveRadialLinear = curveRadial(curveLinear); |
|
|
|
function Radial(curve) { |
|
this._curve = curve; |
|
} |
|
|
|
Radial.prototype = { |
|
areaStart: function() { |
|
this._curve.areaStart(); |
|
}, |
|
areaEnd: function() { |
|
this._curve.areaEnd(); |
|
}, |
|
lineStart: function() { |
|
this._curve.lineStart(); |
|
}, |
|
lineEnd: function() { |
|
this._curve.lineEnd(); |
|
}, |
|
point: function(a, r) { |
|
this._curve.point(r * Math.sin(a), r * -Math.cos(a)); |
|
} |
|
}; |
|
|
|
function curveRadial(curve) { |
|
|
|
function radial(context) { |
|
return new Radial(curve(context)); |
|
} |
|
|
|
radial._curve = curve; |
|
|
|
return radial; |
|
} |
|
|
|
function radialLine(l) { |
|
var c = l.curve; |
|
|
|
l.angle = l.x, delete l.x; |
|
l.radius = l.y, delete l.y; |
|
|
|
l.curve = function(_) { |
|
return arguments.length ? c(curveRadial(_)) : c()._curve; |
|
}; |
|
|
|
return l; |
|
} |
|
|
|
function radialLine$1() { |
|
return radialLine(line().curve(curveRadialLinear)); |
|
} |
|
|
|
function radialArea() { |
|
var a = area$1().curve(curveRadialLinear), |
|
c = a.curve, |
|
x0 = a.lineX0, |
|
x1 = a.lineX1, |
|
y0 = a.lineY0, |
|
y1 = a.lineY1; |
|
|
|
a.angle = a.x, delete a.x; |
|
a.startAngle = a.x0, delete a.x0; |
|
a.endAngle = a.x1, delete a.x1; |
|
a.radius = a.y, delete a.y; |
|
a.innerRadius = a.y0, delete a.y0; |
|
a.outerRadius = a.y1, delete a.y1; |
|
a.lineStartAngle = function() { return radialLine(x0()); }, delete a.lineX0; |
|
a.lineEndAngle = function() { return radialLine(x1()); }, delete a.lineX1; |
|
a.lineInnerRadius = function() { return radialLine(y0()); }, delete a.lineY0; |
|
a.lineOuterRadius = function() { return radialLine(y1()); }, delete a.lineY1; |
|
|
|
a.curve = function(_) { |
|
return arguments.length ? c(curveRadial(_)) : c()._curve; |
|
}; |
|
|
|
return a; |
|
} |
|
|
|
var circle = { |
|
draw: function(context, size) { |
|
var r = Math.sqrt(size / pi$2); |
|
context.moveTo(r, 0); |
|
context.arc(0, 0, r, 0, tau$2); |
|
} |
|
}; |
|
|
|
var cross$1 = { |
|
draw: function(context, size) { |
|
var r = Math.sqrt(size / 5) / 2; |
|
context.moveTo(-3 * r, -r); |
|
context.lineTo(-r, -r); |
|
context.lineTo(-r, -3 * r); |
|
context.lineTo(r, -3 * r); |
|
context.lineTo(r, -r); |
|
context.lineTo(3 * r, -r); |
|
context.lineTo(3 * r, r); |
|
context.lineTo(r, r); |
|
context.lineTo(r, 3 * r); |
|
context.lineTo(-r, 3 * r); |
|
context.lineTo(-r, r); |
|
context.lineTo(-3 * r, r); |
|
context.closePath(); |
|
} |
|
}; |
|
|
|
var tan30 = Math.sqrt(1 / 3); |
|
var tan30_2 = tan30 * 2; |
|
var diamond = { |
|
draw: function(context, size) { |
|
var y = Math.sqrt(size / tan30_2), |
|
x = y * tan30; |
|
context.moveTo(0, -y); |
|
context.lineTo(x, 0); |
|
context.lineTo(0, y); |
|
context.lineTo(-x, 0); |
|
context.closePath(); |
|
} |
|
}; |
|
|
|
var ka = 0.89081309152928522810; |
|
var kr = Math.sin(pi$2 / 10) / Math.sin(7 * pi$2 / 10); |
|
var kx = Math.sin(tau$2 / 10) * kr |