Skip to content

Instantly share code, notes, and snippets.

@justinvdm

justinvdm/build.diff

Created October 15, 2013 13:45
Show Gist options
  • Save justinvdm/6991795 to your computer and use it in GitHub Desktop.
Save justinvdm/6991795 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
build.diff
diff --git a/diamondash/public/js/vendor.js b/diamondash/public/js/vendor.js
index a8a594c..1c8b944 100644
--- a/diamondash/public/js/vendor.js
+++ b/diamondash/public/js/vendor.js
@@ -13611,7 +13611,7 @@ if ( typeof window === "object" && typeof window.document === "object" ) {
d3 = function() {
var d3 = {
- version: "3.3.3"
+ version: "3.3.8"
};
if (!Date.now) Date.now = function() {
return +new Date();
@@ -13797,8 +13797,19 @@ d3 = function() {
return entries;
};
d3.merge = function(arrays) {
- return Array.prototype.concat.apply([], 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;
};
+ var abs = Math.abs;
d3.range = function(start, stop, step) {
if (arguments.length < 3) {
step = 1;
@@ -13808,7 +13819,7 @@ d3 = function() {
}
}
if ((stop - start) / step === Infinity) throw new Error("infinite range");
- var range = [], k = d3_range_integerScale(Math.abs(step)), i = -1, j;
+ var range = [], k = d3_range_integerScale(abs(step)), i = -1, j;
start *= k, stop *= k, step *= k;
if (step < 0) while ((j = start + step * ++i) > stop) range.push(j / k); else while ((j = start + step * ++i) < stop) range.push(j / k);
return range;
@@ -13884,7 +13895,7 @@ d3 = function() {
}
}
});
- var d3_map_prefix = "\0", d3_map_prefixCode = d3_map_prefix.charCodeAt(0);
+ var d3_map_prefix = "\x00", d3_map_prefixCode = d3_map_prefix.charCodeAt(0);
d3.nest = function() {
var nest = {}, keys = [], sortKeys = [], sortValues, rollup;
function map(mapType, array, depth) {
@@ -14325,16 +14336,16 @@ d3 = function() {
};
function d3_selection_creator(name) {
return typeof name === "function" ? name : (name = d3.ns.qualify(name)).local ? function() {
- return d3_document.createElementNS(name.space, name.local);
+ return this.ownerDocument.createElementNS(name.space, name.local);
} : function() {
- return d3_document.createElementNS(this.namespaceURI, name);
+ return this.ownerDocument.createElementNS(this.namespaceURI, name);
};
}
d3_selectionPrototype.insert = function(name, before) {
name = d3_selection_creator(name);
before = d3_selection_selector(before);
return this.select(function() {
- return this.insertBefore(name.apply(this, arguments), before.apply(this, arguments));
+ return this.insertBefore(name.apply(this, arguments), before.apply(this, arguments) || null);
});
};
d3_selectionPrototype.remove = function() {
@@ -14742,7 +14753,6 @@ d3 = function() {
type: "dragstart"
});
function moved() {
- if (!parent) return ended();
var p = position(parent, eventId), dx = p[0] - origin_[0], dy = p[1] - origin_[1];
dragged |= dx | dy;
origin_ = p;
@@ -14770,7 +14780,7 @@ d3 = function() {
};
return d3.rebind(drag, event, "on");
};
- var π = Math.PI, ε = 1e-6, ε2 = ε * ε, d3_radians = π / 180, d3_degrees = 180 / π;
+ var π = Math.PI, τ = 2 * π, halfπ = π / 2, ε = 1e-6, ε2 = ε * ε, d3_radians = π / 180, d3_degrees = 180 / π;
function d3_sgn(x) {
return x > 0 ? 1 : x < 0 ? -1 : 0;
}
@@ -14778,16 +14788,16 @@ d3 = function() {
return x > 1 ? 0 : x < -1 ? π : Math.acos(x);
}
function d3_asin(x) {
- return x > 1 ? π / 2 : x < -1 ? -π / 2 : Math.asin(x);
+ return x > 1 ? halfπ : x < -1 ? -halfπ : Math.asin(x);
}
function d3_sinh(x) {
- return (Math.exp(x) - Math.exp(-x)) / 2;
+ return ((x = Math.exp(x)) - 1 / x) / 2;
}
function d3_cosh(x) {
- return (Math.exp(x) + Math.exp(-x)) / 2;
+ return ((x = Math.exp(x)) + 1 / x) / 2;
}
function d3_tanh(x) {
- return d3_sinh(x) / d3_cosh(x);
+ return ((x = Math.exp(2 * x)) - 1) / (x + 1);
}
function d3_haversin(x) {
return (x = Math.sin(x / 2)) * x;
@@ -15643,11 +15653,12 @@ d3 = function() {
if (n < 2) delay = 0;
if (n < 3) then = Date.now();
var time = then + delay, timer = {
- callback: callback,
- time: time,
- next: null
+ c: callback,
+ t: time,
+ f: false,
+ n: null
};
- if (d3_timer_queueTail) d3_timer_queueTail.next = timer; else d3_timer_queueHead = timer;
+ if (d3_timer_queueTail) d3_timer_queueTail.n = timer; else d3_timer_queueHead = timer;
d3_timer_queueTail = timer;
if (!d3_timer_interval) {
d3_timer_timeout = clearTimeout(d3_timer_timeout);
@@ -15672,30 +15683,23 @@ d3 = function() {
d3_timer_mark();
d3_timer_sweep();
};
- function d3_timer_replace(callback, delay, then) {
- var n = arguments.length;
- if (n < 2) delay = 0;
- if (n < 3) then = Date.now();
- d3_timer_active.callback = callback;
- d3_timer_active.time = then + delay;
- }
function d3_timer_mark() {
var now = Date.now();
d3_timer_active = d3_timer_queueHead;
while (d3_timer_active) {
- if (now >= d3_timer_active.time) d3_timer_active.flush = d3_timer_active.callback(now - d3_timer_active.time);
- d3_timer_active = d3_timer_active.next;
+ if (now >= d3_timer_active.t) d3_timer_active.f = d3_timer_active.c(now - d3_timer_active.t);
+ d3_timer_active = d3_timer_active.n;
}
return now;
}
function d3_timer_sweep() {
var t0, t1 = d3_timer_queueHead, time = Infinity;
while (t1) {
- if (t1.flush) {
- t1 = t0 ? t0.next = t1.next : d3_timer_queueHead = t1.next;
+ if (t1.f) {
+ t1 = t0 ? t0.n = t1.n : d3_timer_queueHead = t1.n;
} else {
- if (t1.time < time) time = t1.time;
- t1 = (t0 = t1).next;
+ if (t1.t < time) time = t1.t;
+ t1 = (t0 = t1).n;
}
}
d3_timer_queueTail = t0;
@@ -15714,7 +15718,7 @@ d3 = function() {
return d3_formatPrefixes[8 + i / 3];
};
function d3_formatPrefix(d, i) {
- var k = Math.pow(10, Math.abs(8 - i) * 3);
+ var k = Math.pow(10, abs(8 - i) * 3);
return {
scale: i > 8 ? function(d) {
return d / k;
@@ -16000,7 +16004,7 @@ d3 = function() {
return [ Math.atan2(cartesian[1], cartesian[0]), d3_asin(cartesian[2]) ];
}
function d3_geo_sphericalEqual(a, b) {
- return Math.abs(a[0] - b[0]) < ε && Math.abs(a[1] - b[1]) < ε;
+ return abs(a[0] - b[0]) < ε && abs(a[1] - b[1]) < ε;
}
d3.geo.bounds = function() {
var λ0, φ0, λ1, φ1, λ_, λ__, φ__, p0, dλSum, ranges, range;
@@ -16035,7 +16039,7 @@ d3 = function() {
var normal = d3_geo_cartesianCross(p0, p), equatorial = [ normal[1], -normal[0], 0 ], inflection = d3_geo_cartesianCross(equatorial, normal);
d3_geo_cartesianNormalize(inflection);
inflection = d3_geo_spherical(inflection);
- var dλ = λ - λ_, s = dλ > 0 ? 1 : -1, λi = inflection[0] * d3_degrees * s, antimeridian = Math.abs(dλ) > 180;
+ var dλ = λ - λ_, s = dλ > 0 ? 1 : -1, λi = inflection[0] * d3_degrees * s, antimeridian = abs(dλ) > 180;
if (antimeridian ^ (s * λ_ < λi && λi < s * λ)) {
var φi = inflection[1] * d3_degrees;
if (φi > φ1) φ1 = φi;
@@ -16080,7 +16084,7 @@ d3 = function() {
function ringPoint(λ, φ) {
if (p0) {
var dλ = λ - λ_;
- dλSum += Math.abs(dλ) > 180 ? dλ + (dλ > 0 ? 360 : -360) : dλ;
+ dλSum += abs(dλ) > 180 ? dλ + (dλ > 0 ? 360 : -360) : dλ;
} else λ__ = λ, φ__ = φ;
d3_geo_area.point(λ, φ);
linePoint(λ, φ);
@@ -16091,7 +16095,7 @@ d3 = function() {
function ringEnd() {
ringPoint(λ__, φ__);
d3_geo_area.lineEnd();
- if (Math.abs(dλSum) > ε) λ0 = -(λ1 = 180);
+ if (abs(dλSum) > ε) λ0 = -(λ1 = 180);
range[0] = λ0, range[1] = λ1;
p0 = null;
}
@@ -16223,7 +16227,7 @@ d3 = function() {
function d3_true() {
return true;
}
- function d3_geo_clipPolygon(segments, compare, inside, interpolate, listener) {
+ function d3_geo_clipPolygon(segments, compare, clipStartInside, interpolate, listener) {
var subject = [], clip = [];
segments.forEach(function(segment) {
if ((n = segment.length - 1) <= 0) return;
@@ -16234,41 +16238,13 @@ d3 = function() {
listener.lineEnd();
return;
}
- var a = {
- point: p0,
- points: segment,
- other: null,
- visited: false,
- entry: true,
- subject: true
- }, b = {
- point: p0,
- points: [ p0 ],
- other: a,
- visited: false,
- entry: false,
- subject: false
- };
- a.other = b;
+ var a = new d3_geo_clipPolygonIntersection(p0, segment, null, true), b = new d3_geo_clipPolygonIntersection(p0, null, a, false);
+ a.o = b;
subject.push(a);
clip.push(b);
- a = {
- point: p1,
- points: [ p1 ],
- other: null,
- visited: false,
- entry: false,
- subject: true
- };
- b = {
- point: p1,
- points: [ p1 ],
- other: a,
- visited: false,
- entry: true,
- subject: false
- };
- a.other = b;
+ a = new d3_geo_clipPolygonIntersection(p1, segment, null, false);
+ b = new d3_geo_clipPolygonIntersection(p1, null, a, true);
+ a.o = b;
subject.push(a);
clip.push(b);
});
@@ -16276,36 +16252,37 @@ d3 = function() {
d3_geo_clipPolygonLinkCircular(subject);
d3_geo_clipPolygonLinkCircular(clip);
if (!subject.length) return;
- if (inside) for (var i = 1, e = !inside(clip[0].point), n = clip.length; i < n; ++i) {
- clip[i].entry = e = !e;
+ for (var i = 0, entry = clipStartInside, n = clip.length; i < n; ++i) {
+ clip[i].e = entry = !entry;
}
- var start = subject[0], current, points, point;
+ var start = subject[0], points, point;
while (1) {
- current = start;
- while (current.visited) if ((current = current.next) === start) return;
- points = current.points;
+ var current = start, isSubject = true;
+ while (current.v) if ((current = current.n) === start) return;
+ points = current.z;
listener.lineStart();
do {
- current.visited = current.other.visited = true;
- if (current.entry) {
- if (current.subject) {
- for (var i = 0; i < points.length; i++) listener.point((point = points[i])[0], point[1]);
+ current.v = current.o.v = true;
+ if (current.e) {
+ if (isSubject) {
+ for (var i = 0, n = points.length; i < n; ++i) listener.point((point = points[i])[0], point[1]);
} else {
- interpolate(current.point, current.next.point, 1, listener);
+ interpolate(current.x, current.n.x, 1, listener);
}
- current = current.next;
+ current = current.n;
} else {
- if (current.subject) {
- points = current.prev.points;
- for (var i = points.length; --i >= 0; ) listener.point((point = points[i])[0], point[1]);
+ if (isSubject) {
+ points = current.p.z;
+ for (var i = points.length - 1; i >= 0; --i) listener.point((point = points[i])[0], point[1]);
} else {
- interpolate(current.point, current.prev.point, -1, listener);
+ interpolate(current.x, current.p.x, -1, listener);
}
- current = current.prev;
+ current = current.p;
}
- current = current.other;
- points = current.points;
- } while (!current.visited);
+ current = current.o;
+ points = current.z;
+ isSubject = !isSubject;
+ } while (!current.v);
listener.lineEnd();
}
}
@@ -16313,16 +16290,24 @@ d3 = function() {
if (!(n = array.length)) return;
var n, i = 0, a = array[0], b;
while (++i < n) {
- a.next = b = array[i];
- b.prev = a;
+ a.n = b = array[i];
+ b.p = a;
a = b;
}
- a.next = b = array[0];
- b.prev = a;
+ a.n = b = array[0];
+ b.p = a;
}
- function d3_geo_clip(pointVisible, clipLine, interpolate, polygonContains) {
- return function(listener) {
- var line = clipLine(listener);
+ function d3_geo_clipPolygonIntersection(point, points, other, entry) {
+ this.x = point;
+ this.z = points;
+ this.o = other;
+ this.e = entry;
+ this.v = false;
+ this.n = this.p = null;
+ }
+ function d3_geo_clip(pointVisible, clipLine, interpolate, clipStart) {
+ return function(rotate, listener) {
+ var line = clipLine(listener), rotatedClipStart = rotate.invert(clipStart[0], clipStart[1]);
var clip = {
point: point,
lineStart: lineStart,
@@ -16340,9 +16325,10 @@ d3 = function() {
clip.lineStart = lineStart;
clip.lineEnd = lineEnd;
segments = d3.merge(segments);
+ var clipStartInside = d3_geo_pointInPolygon(rotatedClipStart, polygon);
if (segments.length) {
- d3_geo_clipPolygon(segments, d3_geo_clipSort, null, interpolate, listener);
- } else if (polygonContains(polygon)) {
+ d3_geo_clipPolygon(segments, d3_geo_clipSort, clipStartInside, interpolate, listener);
+ } else if (clipStartInside) {
listener.lineStart();
interpolate(null, null, 1, listener);
listener.lineEnd();
@@ -16359,10 +16345,12 @@ d3 = function() {
}
};
function point(λ, φ) {
- if (pointVisible(λ, φ)) listener.point(λ, φ);
+ var point = rotate(λ, φ);
+ if (pointVisible(λ = point[0], φ = point[1])) listener.point(λ, φ);
}
function pointLine(λ, φ) {
- line.point(λ, φ);
+ var point = rotate(λ, φ);
+ line.point(point[0], point[1]);
}
function lineStart() {
clip.point = pointLine;
@@ -16375,8 +16363,9 @@ d3 = function() {
var segments;
var buffer = d3_geo_clipBufferListener(), ringListener = clipLine(buffer), polygon, ring;
function pointRing(λ, φ) {
- ringListener.point(λ, φ);
ring.push([ λ, φ ]);
+ var point = rotate(λ, φ);
+ ringListener.point(point[0], point[1]);
}
function ringStart() {
ringListener.lineStart();
@@ -16429,10 +16418,10 @@ d3 = function() {
};
}
function d3_geo_clipSort(a, b) {
- return ((a = a.point)[0] < 0 ? a[1] - π / 2 - ε : π / 2 - a[1]) - ((b = b.point)[0] < 0 ? b[1] - π / 2 - ε : π / 2 - b[1]);
+ return ((a = a.x)[0] < 0 ? a[1] - halfπ - ε : halfπ - a[1]) - ((b = b.x)[0] < 0 ? b[1] - halfπ - ε : halfπ - b[1]);
}
function d3_geo_pointInPolygon(point, polygon) {
- var meridian = point[0], parallel = point[1], meridianNormal = [ Math.sin(meridian), -Math.cos(meridian), 0 ], polarAngle = 0, polar = false, southPole = false, winding = 0;
+ var meridian = point[0], parallel = point[1], meridianNormal = [ Math.sin(meridian), -Math.cos(meridian), 0 ], polarAngle = 0, winding = 0;
d3_geo_areaRingSum.reset();
for (var i = 0, n = polygon.length; i < n; ++i) {
var ring = polygon[i], m = ring.length;
@@ -16441,28 +16430,26 @@ d3 = function() {
while (true) {
if (j === m) j = 0;
point = ring[j];
- var λ = point[0], φ = point[1] / 2 + π / 4, sinφ = Math.sin(φ), cosφ = Math.cos(φ), dλ = λ - λ0, antimeridian = Math.abs(dλ) > π, k = sinφ0 * sinφ;
+ var λ = point[0], φ = point[1] / 2 + π / 4, sinφ = Math.sin(φ), cosφ = Math.cos(φ), dλ = λ - λ0, antimeridian = abs(dλ) > π, k = sinφ0 * sinφ;
d3_geo_areaRingSum.add(Math.atan2(k * Math.sin(dλ), cosφ0 * cosφ + k * Math.cos(dλ)));
- if (Math.abs(φ) < ε) southPole = true;
- polarAngle += antimeridian ? dλ + (dλ >= 0 ? 2 : -2) * π : dλ;
+ polarAngle += antimeridian ? dλ + (dλ >= 0 ? τ : -τ) : dλ;
if (antimeridian ^ λ0 >= meridian ^ λ >= meridian) {
var arc = d3_geo_cartesianCross(d3_geo_cartesian(point0), d3_geo_cartesian(point));
d3_geo_cartesianNormalize(arc);
var intersection = d3_geo_cartesianCross(meridianNormal, arc);
d3_geo_cartesianNormalize(intersection);
var φarc = (antimeridian ^ dλ >= 0 ? -1 : 1) * d3_asin(intersection[2]);
- if (parallel > φarc) {
+ if (parallel > φarc || parallel === φarc && (arc[0] || arc[1])) {
winding += antimeridian ^ dλ >= 0 ? 1 : -1;
}
}
if (!j++) break;
λ0 = λ, sinφ0 = sinφ, cosφ0 = cosφ, point0 = point;
}
- if (Math.abs(polarAngle) > ε) polar = true;
}
- return (!southPole && !polar && d3_geo_areaRingSum < 0 || polarAngle < -ε) ^ winding & 1;
+ return (polarAngle < -ε || polarAngle < ε && d3_geo_areaRingSum < 0) ^ winding & 1;
}
- var d3_geo_clipAntimeridian = d3_geo_clip(d3_true, d3_geo_clipAntimeridianLine, d3_geo_clipAntimeridianInterpolate, d3_geo_clipAntimeridianPolygonContains);
+ var d3_geo_clipAntimeridian = d3_geo_clip(d3_true, d3_geo_clipAntimeridianLine, d3_geo_clipAntimeridianInterpolate, [ -π, -π / 2 ]);
function d3_geo_clipAntimeridianLine(listener) {
var λ0 = NaN, φ0 = NaN, sλ0 = NaN, clean;
return {
@@ -16471,9 +16458,9 @@ d3 = function() {
clean = 1;
},
point: function(λ1, φ1) {
- var sλ1 = λ1 > 0 ? π : -π, dλ = Math.abs(λ1 - λ0);
- if (Math.abs(dλ - π) < ε) {
- listener.point(λ0, φ0 = (φ0 + φ1) / 2 > 0 ? π / 2 : -π / 2);
+ var sλ1 = λ1 > 0 ? π : -π, dλ = abs(λ1 - λ0);
+ if (abs(dλ - π) < ε) {
+ listener.point(λ0, φ0 = (φ0 + φ1) / 2 > 0 ? halfπ : -halfπ);
listener.point(sλ0, φ0);
listener.lineEnd();
listener.lineStart();
@@ -16481,8 +16468,8 @@ d3 = function() {
listener.point(λ1, φ0);
clean = 0;
} else if (sλ0 !== sλ1 && dλ >= π) {
- if (Math.abs(λ0 - sλ0) < ε) λ0 -= sλ0 * ε;
- if (Math.abs(λ1 - sλ1) < ε) λ1 -= sλ1 * ε;
+ if (abs(λ0 - sλ0) < ε) λ0 -= sλ0 * ε;
+ if (abs(λ1 - sλ1) < ε) λ1 -= sλ1 * ε;
φ0 = d3_geo_clipAntimeridianIntersect(λ0, φ0, λ1, φ1);
listener.point(sλ0, φ0);
listener.lineEnd();
@@ -16504,12 +16491,12 @@ d3 = function() {
}
function d3_geo_clipAntimeridianIntersect(λ0, φ0, λ1, φ1) {
var cosφ0, cosφ1, sinλ0_λ1 = Math.sin(λ0 - λ1);
- return Math.abs(sinλ0_λ1) > ε ? Math.atan((Math.sin(φ0) * (cosφ1 = Math.cos(φ1)) * Math.sin(λ1) - Math.sin(φ1) * (cosφ0 = Math.cos(φ0)) * Math.sin(λ0)) / (cosφ0 * cosφ1 * sinλ0_λ1)) : (φ0 + φ1) / 2;
+ return abs(sinλ0_λ1) > ε ? Math.atan((Math.sin(φ0) * (cosφ1 = Math.cos(φ1)) * Math.sin(λ1) - Math.sin(φ1) * (cosφ0 = Math.cos(φ0)) * Math.sin(λ0)) / (cosφ0 * cosφ1 * sinλ0_λ1)) : (φ0 + φ1) / 2;
}
function d3_geo_clipAntimeridianInterpolate(from, to, direction, listener) {
var φ;
if (from == null) {
- φ = direction * π / 2;
+ φ = direction * halfπ;
listener.point(-π, φ);
listener.point(0, φ);
listener.point(π, φ);
@@ -16519,8 +16506,8 @@ d3 = function() {
listener.point(-π, -φ);
listener.point(-π, 0);
listener.point(-π, φ);
- } else if (Math.abs(from[0] - to[0]) > ε) {
- var s = (from[0] < to[0] ? 1 : -1) * π;
+ } else if (abs(from[0] - to[0]) > ε) {
+ var s = from[0] < to[0] ? π : -π;
φ = direction * s / 2;
listener.point(-s, φ);
listener.point(0, φ);
@@ -16529,13 +16516,9 @@ d3 = function() {
listener.point(to[0], to[1]);
}
}
- var d3_geo_clipAntimeridianPoint = [ -π, 0 ];
- function d3_geo_clipAntimeridianPolygonContains(polygon) {
- return d3_geo_pointInPolygon(d3_geo_clipAntimeridianPoint, polygon);
- }
function d3_geo_clipCircle(radius) {
- var cr = Math.cos(radius), smallRadius = cr > 0, point = [ radius, 0 ], notHemisphere = Math.abs(cr) > ε, interpolate = d3_geo_circleInterpolate(radius, 6 * d3_radians);
- return d3_geo_clip(visible, clipLine, interpolate, polygonContains);
+ var cr = Math.cos(radius), smallRadius = cr > 0, notHemisphere = abs(cr) > ε, interpolate = d3_geo_circleInterpolate(radius, 6 * d3_radians);
+ return d3_geo_clip(visible, clipLine, interpolate, smallRadius ? [ 0, -radius ] : [ -π, radius - π ]);
function visible(λ, φ) {
return Math.cos(λ) * Math.cos(φ) > cr;
}
@@ -16614,9 +16597,9 @@ d3 = function() {
if (!two) return q;
var λ0 = a[0], λ1 = b[0], φ0 = a[1], φ1 = b[1], z;
if (λ1 < λ0) z = λ0, λ0 = λ1, λ1 = z;
- var δλ = λ1 - λ0, polar = Math.abs(δλ - π) < ε, meridian = polar || δλ < ε;
+ var δλ = λ1 - λ0, polar = abs(δλ - π) < ε, meridian = polar || δλ < ε;
if (!polar && φ1 < φ0) z = φ0, φ0 = φ1, φ1 = z;
- if (meridian ? polar ? φ0 + φ1 > 0 ^ q[1] < (Math.abs(q[0] - λ0) < ε ? φ0 : φ1) : φ0 <= q[1] && q[1] <= φ1 : δλ > π ^ (λ0 <= q[0] && q[0] <= λ1)) {
+ if (meridian ? polar ? φ0 + φ1 > 0 ^ q[1] < (abs(q[0] - λ0) < ε ? φ0 : φ1) : φ0 <= q[1] && q[1] <= φ1 : δλ > π ^ (λ0 <= q[0] && q[0] <= λ1)) {
var q1 = d3_geo_cartesianScale(u, (-w + t) / uu);
d3_geo_cartesianAdd(q1, A);
return [ q, d3_geo_spherical(q1) ];
@@ -16628,9 +16611,60 @@ d3 = function() {
if (φ < -r) code |= 4; else if (φ > r) code |= 8;
return code;
}
- function polygonContains(polygon) {
- return d3_geo_pointInPolygon(point, polygon);
- }
+ }
+ function d3_geom_clipLine(x0, y0, x1, y1) {
+ return function(line) {
+ var a = line.a, b = line.b, ax = a.x, ay = a.y, bx = b.x, by = b.y, t0 = 0, t1 = 1, dx = bx - ax, dy = by - ay, r;
+ r = x0 - ax;
+ if (!dx && r > 0) return;
+ r /= dx;
+ if (dx < 0) {
+ if (r < t0) return;
+ if (r < t1) t1 = r;
+ } else if (dx > 0) {
+ if (r > t1) return;
+ if (r > t0) t0 = r;
+ }
+ r = x1 - ax;
+ if (!dx && r < 0) return;
+ r /= dx;
+ if (dx < 0) {
+ if (r > t1) return;
+ if (r > t0) t0 = r;
+ } else if (dx > 0) {
+ if (r < t0) return;
+ if (r < t1) t1 = r;
+ }
+ r = y0 - ay;
+ if (!dy && r > 0) return;
+ r /= dy;
+ if (dy < 0) {
+ if (r < t0) return;
+ if (r < t1) t1 = r;
+ } else if (dy > 0) {
+ if (r > t1) return;
+ if (r > t0) t0 = r;
+ }
+ r = y1 - ay;
+ if (!dy && r < 0) return;
+ r /= dy;
+ if (dy < 0) {
+ if (r > t1) return;
+ if (r > t0) t0 = r;
+ } else if (dy > 0) {
+ if (r < t0) return;
+ if (r < t1) t1 = r;
+ }
+ if (t0 > 0) line.a = {
+ x: ax + t0 * dx,
+ y: ay + t0 * dy
+ };
+ if (t1 < 1) line.b = {
+ x: ax + t1 * dx,
+ y: ay + t1 * dy
+ };
+ return line;
+ };
}
var d3_geo_clipExtentMAX = 1e9;
d3.geo.clipExtent = function() {
@@ -16652,7 +16686,7 @@ d3 = function() {
};
function d3_geo_clipExtent(x0, y0, x1, y1) {
return function(listener) {
- var listener_ = listener, bufferListener = d3_geo_clipBufferListener(), segments, polygon, ring;
+ var listener_ = listener, bufferListener = d3_geo_clipBufferListener(), clipLine = d3_geom_clipLine(x0, y0, x1, y1), segments, polygon, ring;
var clip = {
point: point,
lineStart: lineStart,
@@ -16661,25 +16695,27 @@ d3 = function() {
listener = bufferListener;
segments = [];
polygon = [];
+ clean = true;
},
polygonEnd: function() {
listener = listener_;
- if ((segments = d3.merge(segments)).length) {
+ segments = d3.merge(segments);
+ var clipStartInside = insidePolygon([ x0, y1 ]), inside = clean && clipStartInside, visible = segments.length;
+ if (inside || visible) {
listener.polygonStart();
- d3_geo_clipPolygon(segments, compare, inside, interpolate, listener);
+ if (inside) {
+ listener.lineStart();
+ interpolate(null, null, 1, listener);
+ listener.lineEnd();
+ }
+ if (visible) {
+ d3_geo_clipPolygon(segments, compare, clipStartInside, interpolate, listener);
+ }
listener.polygonEnd();
- } else if (insidePolygon([ x0, y0 ])) {
- listener.polygonStart(), listener.lineStart();
- interpolate(null, null, 1, listener);
- listener.lineEnd(), listener.polygonEnd();
}
segments = polygon = ring = null;
}
};
- function inside(point) {
- var a = corner(point, -1), i = insidePolygon([ a === 0 || a === 3 ? x0 : x1, a > 1 ? y1 : y0 ]);
- return i;
- }
function insidePolygon(p) {
var wn = 0, n = polygon.length, y = p[1];
for (var i = 0; i < n; ++i) {
@@ -16708,13 +16744,13 @@ d3 = function() {
listener.point(to[0], to[1]);
}
}
- function visible(x, y) {
+ function pointVisible(x, y) {
return x0 <= x && x <= x1 && y0 <= y && y <= y1;
}
function point(x, y) {
- if (visible(x, y)) listener.point(x, y);
+ if (pointVisible(x, y)) listener.point(x, y);
}
- var x__, y__, v__, x_, y_, v_, first;
+ var x__, y__, v__, x_, y_, v_, first, clean;
function lineStart() {
clip.point = linePoint;
if (polygon) polygon.push(ring = []);
@@ -16734,7 +16770,7 @@ d3 = function() {
function linePoint(x, y) {
x = Math.max(-d3_geo_clipExtentMAX, Math.min(d3_geo_clipExtentMAX, x));
y = Math.max(-d3_geo_clipExtentMAX, Math.min(d3_geo_clipExtentMAX, y));
- var v = visible(x, y);
+ var v = pointVisible(x, y);
if (polygon) ring.push([ x, y ]);
if (first) {
x__ = x, y__ = y, v__ = v;
@@ -16745,17 +16781,28 @@ d3 = function() {
}
} else {
if (v && v_) listener.point(x, y); else {
- var a = [ x_, y_ ], b = [ x, y ];
- if (clipLine(a, b)) {
+ var l = {
+ a: {
+ x: x_,
+ y: y_
+ },
+ b: {
+ x: x,
+ y: y
+ }
+ };
+ if (clipLine(l)) {
if (!v_) {
listener.lineStart();
- listener.point(a[0], a[1]);
+ listener.point(l.a.x, l.a.y);
}
- listener.point(b[0], b[1]);
+ listener.point(l.b.x, l.b.y);
if (!v) listener.lineEnd();
+ clean = false;
} else if (v) {
listener.lineStart();
listener.point(x, y);
+ clean = false;
}
}
}
@@ -16764,43 +16811,15 @@ d3 = function() {
return clip;
};
function corner(p, direction) {
- return Math.abs(p[0] - x0) < ε ? direction > 0 ? 0 : 3 : Math.abs(p[0] - x1) < ε ? direction > 0 ? 2 : 1 : Math.abs(p[1] - y0) < ε ? direction > 0 ? 1 : 0 : direction > 0 ? 3 : 2;
+ return abs(p[0] - x0) < ε ? direction > 0 ? 0 : 3 : abs(p[0] - x1) < ε ? direction > 0 ? 2 : 1 : abs(p[1] - y0) < ε ? direction > 0 ? 1 : 0 : direction > 0 ? 3 : 2;
}
function compare(a, b) {
- return comparePoints(a.point, b.point);
+ return comparePoints(a.x, b.x);
}
function comparePoints(a, b) {
var ca = corner(a, 1), cb = corner(b, 1);
return ca !== cb ? ca - cb : ca === 0 ? b[1] - a[1] : ca === 1 ? a[0] - b[0] : ca === 2 ? a[1] - b[1] : b[0] - a[0];
}
- function clipLine(a, b) {
- var dx = b[0] - a[0], dy = b[1] - a[1], t = [ 0, 1 ];
- if (Math.abs(dx) < ε && Math.abs(dy) < ε) return x0 <= a[0] && a[0] <= x1 && y0 <= a[1] && a[1] <= y1;
- if (d3_geo_clipExtentT(x0 - a[0], dx, t) && d3_geo_clipExtentT(a[0] - x1, -dx, t) && d3_geo_clipExtentT(y0 - a[1], dy, t) && d3_geo_clipExtentT(a[1] - y1, -dy, t)) {
- if (t[1] < 1) {
- b[0] = a[0] + t[1] * dx;
- b[1] = a[1] + t[1] * dy;
- }
- if (t[0] > 0) {
- a[0] += t[0] * dx;
- a[1] += t[0] * dy;
- }
- return true;
- }
- return false;
- }
- }
- function d3_geo_clipExtentT(num, denominator, t) {
- if (Math.abs(denominator) < ε) return num <= 0;
- var u = num / denominator;
- if (denominator > 0) {
- if (u > t[1]) return false;
- if (u > t[0]) t[0] = u;
- } else {
- if (u < t[0]) return false;
- if (u < t[1]) t[1] = u;
- }
- return true;
}
function d3_geo_compose(a, b) {
function compose(x, y) {
@@ -16925,7 +16944,7 @@ d3 = function() {
},
polygonEnd: function() {
d3_geo_pathArea.lineStart = d3_geo_pathArea.lineEnd = d3_geo_pathArea.point = d3_noop;
- d3_geo_pathAreaSum += Math.abs(d3_geo_pathAreaPolygon / 2);
+ d3_geo_pathAreaSum += abs(d3_geo_pathAreaPolygon / 2);
}
};
function d3_geo_pathAreaRingStart() {
@@ -17083,7 +17102,7 @@ d3 = function() {
};
function point(x, y) {
context.moveTo(x, y);
- context.arc(x, y, pointRadius, 0, 2 * π);
+ context.arc(x, y, pointRadius, 0, τ);
}
function pointLineStart(x, y) {
context.moveTo(x, y);
@@ -17154,8 +17173,8 @@ d3 = function() {
function resampleLineTo(x0, y0, λ0, a0, b0, c0, x1, y1, λ1, a1, b1, c1, depth, stream) {
var dx = x1 - x0, dy = y1 - y0, d2 = dx * dx + dy * dy;
if (d2 > 4 * δ2 && depth--) {
- var a = a0 + a1, b = b0 + b1, c = c0 + c1, m = Math.sqrt(a * a + b * b + c * c), φ2 = Math.asin(c /= m), λ2 = Math.abs(Math.abs(c) - 1) < ε ? (λ0 + λ1) / 2 : Math.atan2(b, a), p = project(λ2, φ2), x2 = p[0], y2 = p[1], dx2 = x2 - x0, dy2 = y2 - y0, dz = dy * dx2 - dx * dy2;
- if (dz * dz / d2 > δ2 || Math.abs((dx * dx2 + dy * dy2) / d2 - .5) > .3 || a0 * a1 + b0 * b1 + c0 * c1 < cosMinDistance) {
+ var a = a0 + a1, b = b0 + b1, c = c0 + c1, m = Math.sqrt(a * a + b * b + c * c), φ2 = Math.asin(c /= m), λ2 = abs(abs(c) - 1) < ε ? (λ0 + λ1) / 2 : Math.atan2(b, a), p = project(λ2, φ2), x2 = p[0], y2 = p[1], dx2 = x2 - x0, dy2 = y2 - y0, dz = dy * dx2 - dx * dy2;
+ if (dz * dz / d2 > δ2 || abs((dx * dx2 + dy * dy2) / d2 - .5) > .3 || a0 * a1 + b0 * b1 + c0 * c1 < cosMinDistance) {
resampleLineTo(x0, y0, λ0, a0, b0, c0, x2, y2, λ2, a /= m, b /= m, c, depth, stream);
stream.point(x2, y2);
resampleLineTo(x2, y2, λ2, a, b, c, x1, y1, λ1, a1, b1, c1, depth, stream);
@@ -17282,7 +17301,7 @@ d3 = function() {
}
projection.stream = function(output) {
if (stream) stream.valid = false;
- stream = d3_geo_projectionRadiansRotate(rotate, preclip(projectResample(postclip(output))));
+ stream = d3_geo_projectionRadians(preclip(rotate, projectResample(postclip(output))));
stream.valid = true;
return stream;
};
@@ -17339,11 +17358,10 @@ d3 = function() {
return reset();
};
}
- function d3_geo_projectionRadiansRotate(rotate, stream) {
+ function d3_geo_projectionRadians(stream) {
var transform = new d3_geo_transform(stream);
- transform.point = function(x, y) {
- y = rotate(x * d3_radians, y * d3_radians), x = y[0];
- stream.point(x > π ? x - 2 * π : x < -π ? x + 2 * π : x, y[1]);
+ transform.point = function(λ, φ) {
+ stream.point(λ * d3_radians, φ * d3_radians);
};
return transform;
}
@@ -17365,12 +17383,16 @@ d3 = function() {
};
return forward;
};
+ function d3_geo_identityRotation(λ, φ) {
+ return [ λ > π ? λ - τ : λ < -π ? λ + τ : λ, φ ];
+ }
+ d3_geo_identityRotation.invert = d3_geo_equirectangular;
function d3_geo_rotation(δλ, δφ, δγ) {
- return δλ ? δφ || δγ ? d3_geo_compose(d3_geo_rotationλ(δλ), d3_geo_rotationφγ(δφ, δγ)) : d3_geo_rotationλ(δλ) : δφ || δγ ? d3_geo_rotationφγ(δφ, δγ) : d3_geo_equirectangular;
+ return δλ ? δφ || δγ ? d3_geo_compose(d3_geo_rotationλ(δλ), d3_geo_rotationφγ(δφ, δγ)) : d3_geo_rotationλ(δλ) : δφ || δγ ? d3_geo_rotationφγ(δφ, δγ) : d3_geo_identityRotation;
}
function d3_geo_forwardRotationλ(δλ) {
return function(λ, φ) {
- return λ += δλ, [ λ > π ? λ - 2 * π : λ < -π ? λ + 2 * π : λ, φ ];
+ return λ += δλ, [ λ > π ? λ - τ : λ < -π ? λ + τ : λ, φ ];
};
}
function d3_geo_rotationλ(δλ) {
@@ -17429,9 +17451,9 @@ d3 = function() {
if (from != null) {
from = d3_geo_circleAngle(cr, from);
to = d3_geo_circleAngle(cr, to);
- if (direction > 0 ? from < to : from > to) from += direction * 2 * π;
+ if (direction > 0 ? from < to : from > to) from += direction * τ;
} else {
- from = radius + direction * 2 * π;
+ from = radius + direction * τ;
to = radius - .5 * step;
}
for (var point, t = from; direction > 0 ? t > to : t < to; t -= step) {
@@ -17460,9 +17482,9 @@ d3 = function() {
}
function lines() {
return d3.range(Math.ceil(X0 / DX) * DX, X1, DX).map(X).concat(d3.range(Math.ceil(Y0 / DY) * DY, Y1, DY).map(Y)).concat(d3.range(Math.ceil(x0 / dx) * dx, x1, dx).filter(function(x) {
- return Math.abs(x % DX) > ε;
+ return abs(x % DX) > ε;
}).map(x)).concat(d3.range(Math.ceil(y0 / dy) * dy, y1, dy).filter(function(y) {
- return Math.abs(y % DY) > ε;
+ return abs(y % DY) > ε;
}).map(y));
}
graticule.lines = function() {
@@ -17610,7 +17632,7 @@ d3 = function() {
d3_geo_length.point = d3_geo_length.lineEnd = d3_noop;
};
function nextPoint(λ, φ) {
- var sinφ = Math.sin(φ *= d3_radians), cosφ = Math.cos(φ), t = Math.abs((λ *= d3_radians) - λ0), cosΔλ = Math.cos(t);
+ var sinφ = Math.sin(φ *= d3_radians), cosφ = Math.cos(φ), t = abs((λ *= d3_radians) - λ0), cosΔλ = Math.cos(t);
d3_geo_lengthSum += Math.atan2(Math.sqrt((t = cosφ * Math.sin(t)) * t + (t = cosφ0 * sinφ - sinφ0 * cosφ * cosΔλ) * t), sinφ0 * sinφ + cosφ0 * cosφ * cosΔλ);
λ0 = λ, sinφ0 = sinφ, cosφ0 = cosφ;
}
@@ -17647,12 +17669,12 @@ d3 = function() {
}, n = φ0 === φ1 ? Math.sin(φ0) : Math.log(cosφ0 / Math.cos(φ1)) / Math.log(t(φ1) / t(φ0)), F = cosφ0 * Math.pow(t(φ0), n) / n;
if (!n) return d3_geo_mercator;
function forward(λ, φ) {
- var ρ = Math.abs(Math.abs(φ) - π / 2) < ε ? 0 : F / Math.pow(t(φ), n);
+ var ρ = abs(abs(φ) - halfπ) < ε ? 0 : F / Math.pow(t(φ), n);
return [ ρ * Math.sin(n * λ), F - ρ * Math.cos(n * λ) ];
}
forward.invert = function(x, y) {
var ρ0_y = F - y, ρ = d3_sgn(n) * Math.sqrt(x * x + ρ0_y * ρ0_y);
- return [ Math.atan2(x, ρ0_y) / n, 2 * Math.atan(Math.pow(F / ρ, 1 / n)) - π / 2 ];
+ return [ Math.atan2(x, ρ0_y) / n, 2 * Math.atan(Math.pow(F / ρ, 1 / n)) - halfπ ];
};
return forward;
}
@@ -17661,7 +17683,7 @@ d3 = function() {
}).raw = d3_geo_conicConformal;
function d3_geo_conicEquidistant(φ0, φ1) {
var cosφ0 = Math.cos(φ0), n = φ0 === φ1 ? Math.sin(φ0) : (cosφ0 - Math.cos(φ1)) / (φ1 - φ0), G = cosφ0 / n + φ0;
- if (Math.abs(n) < ε) return d3_geo_equirectangular;
+ if (abs(n) < ε) return d3_geo_equirectangular;
function forward(λ, φ) {
var ρ = G - φ;
return [ ρ * Math.sin(n * λ), G - ρ * Math.cos(n * λ) ];
@@ -17685,7 +17707,7 @@ d3 = function() {
return [ λ, Math.log(Math.tan(π / 4 + φ / 2)) ];
}
d3_geo_mercator.invert = function(x, y) {
- return [ x, 2 * Math.atan(Math.exp(y)) - π / 2 ];
+ return [ x, 2 * Math.atan(Math.exp(y)) - halfπ ];
};
function d3_geo_mercatorProjection(project) {
var m = d3_geo_projection(project), scale = m.scale, translate = m.translate, clipExtent = m.clipExtent, clipAuto;
@@ -17739,830 +17761,810 @@ d3 = function() {
return d3_geo_mercatorProjection(d3_geo_transverseMercator);
}).raw = d3_geo_transverseMercator;
d3.geom = {};
- d3.svg = {};
- function d3_svg_line(projection) {
- var x = d3_svg_lineX, y = d3_svg_lineY, defined = d3_true, interpolate = d3_svg_lineLinear, interpolateKey = interpolate.key, tension = .7;
- function line(data) {
- var segments = [], points = [], i = -1, n = data.length, d, fx = d3_functor(x), fy = d3_functor(y);
- function segment() {
- segments.push("M", interpolate(projection(points), tension));
+ function d3_geom_pointX(d) {
+ return d[0];
+ }
+ function d3_geom_pointY(d) {
+ return d[1];
+ }
+ d3.geom.hull = function(vertices) {
+ var x = d3_geom_pointX, y = d3_geom_pointY;
+ if (arguments.length) return hull(vertices);
+ function hull(data) {
+ if (data.length < 3) return [];
+ var fx = d3_functor(x), fy = d3_functor(y), n = data.length, vertices, plen = n - 1, points = [], stack = [], d, i, j, h = 0, x1, y1, x2, y2, u, v, a, sp;
+ if (fx === d3_geom_pointX && y === d3_geom_pointY) vertices = data; else for (i = 0,
+ vertices = []; i < n; ++i) {
+ vertices.push([ +fx.call(this, d = data[i], i), +fy.call(this, d, i) ]);
}
- while (++i < n) {
- if (defined.call(this, d = data[i], i)) {
- points.push([ +fx.call(this, d, i), +fy.call(this, d, i) ]);
- } else if (points.length) {
- segment();
- points = [];
+ for (i = 1; i < n; ++i) {
+ if (vertices[i][1] < vertices[h][1] || vertices[i][1] == vertices[h][1] && vertices[i][0] < vertices[h][0]) h = i;
+ }
+ for (i = 0; i < n; ++i) {
+ if (i === h) continue;
+ y1 = vertices[i][1] - vertices[h][1];
+ x1 = vertices[i][0] - vertices[h][0];
+ points.push({
+ angle: Math.atan2(y1, x1),
+ index: i
+ });
+ }
+ points.sort(function(a, b) {
+ return a.angle - b.angle;
+ });
+ a = points[0].angle;
+ v = points[0].index;
+ u = 0;
+ for (i = 1; i < plen; ++i) {
+ j = points[i].index;
+ if (a == points[i].angle) {
+ x1 = vertices[v][0] - vertices[h][0];
+ y1 = vertices[v][1] - vertices[h][1];
+ x2 = vertices[j][0] - vertices[h][0];
+ y2 = vertices[j][1] - vertices[h][1];
+ if (x1 * x1 + y1 * y1 >= x2 * x2 + y2 * y2) {
+ points[i].index = -1;
+ continue;
+ } else {
+ points[u].index = -1;
+ }
}
+ a = points[i].angle;
+ u = i;
+ v = j;
}
- if (points.length) segment();
- return segments.length ? segments.join("") : null;
+ stack.push(h);
+ for (i = 0, j = 0; i < 2; ++j) {
+ if (points[j].index > -1) {
+ stack.push(points[j].index);
+ i++;
+ }
+ }
+ sp = stack.length;
+ for (;j < plen; ++j) {
+ if (points[j].index < 0) continue;
+ while (!d3_geom_hullCCW(stack[sp - 2], stack[sp - 1], points[j].index, vertices)) {
+ --sp;
+ }
+ stack[sp++] = points[j].index;
+ }
+ var poly = [];
+ for (i = sp - 1; i >= 0; --i) poly.push(data[stack[i]]);
+ return poly;
}
- line.x = function(_) {
- if (!arguments.length) return x;
- x = _;
- return line;
- };
- line.y = function(_) {
- if (!arguments.length) return y;
- y = _;
- return line;
- };
- line.defined = function(_) {
- if (!arguments.length) return defined;
- defined = _;
- return line;
- };
- line.interpolate = function(_) {
- if (!arguments.length) return interpolateKey;
- if (typeof _ === "function") interpolateKey = interpolate = _; else interpolateKey = (interpolate = d3_svg_lineInterpolators.get(_) || d3_svg_lineLinear).key;
- return line;
+ hull.x = function(_) {
+ return arguments.length ? (x = _, hull) : x;
};
- line.tension = function(_) {
- if (!arguments.length) return tension;
- tension = _;
- return line;
+ hull.y = function(_) {
+ return arguments.length ? (y = _, hull) : y;
};
- return line;
+ return hull;
+ };
+ function d3_geom_hullCCW(i1, i2, i3, v) {
+ var t, a, b, c, d, e, f;
+ t = v[i1];
+ a = t[0];
+ b = t[1];
+ t = v[i2];
+ c = t[0];
+ d = t[1];
+ t = v[i3];
+ e = t[0];
+ f = t[1];
+ return (f - b) * (c - a) - (d - b) * (e - a) > 0;
}
- d3.svg.line = function() {
- return d3_svg_line(d3_identity);
+ d3.geom.polygon = function(coordinates) {
+ d3_subclass(coordinates, d3_geom_polygonPrototype);
+ return coordinates;
};
- function d3_svg_lineX(d) {
- return d[0];
+ var d3_geom_polygonPrototype = d3.geom.polygon.prototype = [];
+ d3_geom_polygonPrototype.area = function() {
+ var i = -1, n = this.length, a, b = this[n - 1], area = 0;
+ while (++i < n) {
+ a = b;
+ b = this[i];
+ area += a[1] * b[0] - a[0] * b[1];
+ }
+ return area * .5;
+ };
+ d3_geom_polygonPrototype.centroid = function(k) {
+ var i = -1, n = this.length, x = 0, y = 0, a, b = this[n - 1], c;
+ if (!arguments.length) k = -1 / (6 * this.area());
+ while (++i < n) {
+ a = b;
+ b = this[i];
+ c = a[0] * b[1] - b[0] * a[1];
+ x += (a[0] + b[0]) * c;
+ y += (a[1] + b[1]) * c;
+ }
+ return [ x * k, y * k ];
+ };
+ d3_geom_polygonPrototype.clip = function(subject) {
+ var input, closed = d3_geom_polygonClosed(subject), i = -1, n = this.length - d3_geom_polygonClosed(this), j, m, a = this[n - 1], b, c, d;
+ while (++i < n) {
+ input = subject.slice();
+ subject.length = 0;
+ b = this[i];
+ c = input[(m = input.length - closed) - 1];
+ j = -1;
+ while (++j < m) {
+ d = input[j];
+ if (d3_geom_polygonInside(d, a, b)) {
+ if (!d3_geom_polygonInside(c, a, b)) {
+ subject.push(d3_geom_polygonIntersect(c, d, a, b));
+ }
+ subject.push(d);
+ } else if (d3_geom_polygonInside(c, a, b)) {
+ subject.push(d3_geom_polygonIntersect(c, d, a, b));
+ }
+ c = d;
+ }
+ if (closed) subject.push(subject[0]);
+ a = b;
+ }
+ return subject;
+ };
+ function d3_geom_polygonInside(p, a, b) {
+ return (b[0] - a[0]) * (p[1] - a[1]) < (b[1] - a[1]) * (p[0] - a[0]);
}
- function d3_svg_lineY(d) {
- return d[1];
+ function d3_geom_polygonIntersect(c, d, a, b) {
+ var x1 = c[0], x3 = a[0], x21 = d[0] - x1, x43 = b[0] - x3, y1 = c[1], y3 = a[1], y21 = d[1] - y1, y43 = b[1] - y3, ua = (x43 * (y1 - y3) - y43 * (x1 - x3)) / (y43 * x21 - x43 * y21);
+ return [ x1 + ua * x21, y1 + ua * y21 ];
}
- var d3_svg_lineInterpolators = d3.map({
- linear: d3_svg_lineLinear,
- "linear-closed": d3_svg_lineLinearClosed,
- step: d3_svg_lineStep,
- "step-before": d3_svg_lineStepBefore,
- "step-after": d3_svg_lineStepAfter,
- basis: d3_svg_lineBasis,
- "basis-open": d3_svg_lineBasisOpen,
- "basis-closed": d3_svg_lineBasisClosed,
- bundle: d3_svg_lineBundle,
- cardinal: d3_svg_lineCardinal,
- "cardinal-open": d3_svg_lineCardinalOpen,
- "cardinal-closed": d3_svg_lineCardinalClosed,
- monotone: d3_svg_lineMonotone
- });
- d3_svg_lineInterpolators.forEach(function(key, value) {
- value.key = key;
- value.closed = /-closed$/.test(key);
- });
- function d3_svg_lineLinear(points) {
- return points.join("L");
+ function d3_geom_polygonClosed(coordinates) {
+ var a = coordinates[0], b = coordinates[coordinates.length - 1];
+ return !(a[0] - b[0] || a[1] - b[1]);
}
- function d3_svg_lineLinearClosed(points) {
- return d3_svg_lineLinear(points) + "Z";
+ var d3_geom_voronoiEdges, d3_geom_voronoiCells, d3_geom_voronoiBeaches, d3_geom_voronoiBeachPool = [], d3_geom_voronoiFirstCircle, d3_geom_voronoiCircles, d3_geom_voronoiCirclePool = [];
+ function d3_geom_voronoiBeach() {
+ d3_geom_voronoiRedBlackNode(this);
+ this.edge = this.site = this.circle = null;
}
- function d3_svg_lineStep(points) {
- var i = 0, n = points.length, p = points[0], path = [ p[0], ",", p[1] ];
- while (++i < n) path.push("H", (p[0] + (p = points[i])[0]) / 2, "V", p[1]);
- if (n > 1) path.push("H", p[0]);
- return path.join("");
+ function d3_geom_voronoiCreateBeach(site) {
+ var beach = d3_geom_voronoiBeachPool.pop() || new d3_geom_voronoiBeach();
+ beach.site = site;
+ return beach;
}
- function d3_svg_lineStepBefore(points) {
- var i = 0, n = points.length, p = points[0], path = [ p[0], ",", p[1] ];
- while (++i < n) path.push("V", (p = points[i])[1], "H", p[0]);
- return path.join("");
+ function d3_geom_voronoiDetachBeach(beach) {
+ d3_geom_voronoiDetachCircle(beach);
+ d3_geom_voronoiBeaches.remove(beach);
+ d3_geom_voronoiBeachPool.push(beach);
+ d3_geom_voronoiRedBlackNode(beach);
}
- function d3_svg_lineStepAfter(points) {
- var i = 0, n = points.length, p = points[0], path = [ p[0], ",", p[1] ];
- while (++i < n) path.push("H", (p = points[i])[0], "V", p[1]);
- return path.join("");
- }
- function d3_svg_lineCardinalOpen(points, tension) {
- return points.length < 4 ? d3_svg_lineLinear(points) : points[1] + d3_svg_lineHermite(points.slice(1, points.length - 1), d3_svg_lineCardinalTangents(points, tension));
- }
- function d3_svg_lineCardinalClosed(points, tension) {
- return points.length < 3 ? d3_svg_lineLinear(points) : points[0] + d3_svg_lineHermite((points.push(points[0]),
- points), d3_svg_lineCardinalTangents([ points[points.length - 2] ].concat(points, [ points[1] ]), tension));
- }
- function d3_svg_lineCardinal(points, tension) {
- return points.length < 3 ? d3_svg_lineLinear(points) : points[0] + d3_svg_lineHermite(points, d3_svg_lineCardinalTangents(points, tension));
- }
- function d3_svg_lineHermite(points, tangents) {
- if (tangents.length < 1 || points.length != tangents.length && points.length != tangents.length + 2) {
- return d3_svg_lineLinear(points);
- }
- var quad = points.length != tangents.length, path = "", p0 = points[0], p = points[1], t0 = tangents[0], t = t0, pi = 1;
- if (quad) {
- path += "Q" + (p[0] - t0[0] * 2 / 3) + "," + (p[1] - t0[1] * 2 / 3) + "," + p[0] + "," + p[1];
- p0 = points[1];
- pi = 2;
- }
- if (tangents.length > 1) {
- t = tangents[1];
- p = points[pi];
- pi++;
- path += "C" + (p0[0] + t0[0]) + "," + (p0[1] + t0[1]) + "," + (p[0] - t[0]) + "," + (p[1] - t[1]) + "," + p[0] + "," + p[1];
- for (var i = 2; i < tangents.length; i++, pi++) {
- p = points[pi];
- t = tangents[i];
- path += "S" + (p[0] - t[0]) + "," + (p[1] - t[1]) + "," + p[0] + "," + p[1];
+ function d3_geom_voronoiRemoveBeach(beach) {
+ var circle = beach.circle, x = circle.x, y = circle.cy, vertex = {
+ x: x,
+ y: y
+ }, previous = beach.P, next = beach.N, disappearing = [ beach ];
+ d3_geom_voronoiDetachBeach(beach);
+ var lArc = previous;
+ while (lArc.circle && abs(x - lArc.circle.x) < ε && abs(y - lArc.circle.cy) < ε) {
+ previous = lArc.P;
+ disappearing.unshift(lArc);
+ d3_geom_voronoiDetachBeach(lArc);
+ lArc = previous;
+ }
+ disappearing.unshift(lArc);
+ d3_geom_voronoiDetachCircle(lArc);
+ var rArc = next;
+ while (rArc.circle && abs(x - rArc.circle.x) < ε && abs(y - rArc.circle.cy) < ε) {
+ next = rArc.N;
+ disappearing.push(rArc);
+ d3_geom_voronoiDetachBeach(rArc);
+ rArc = next;
+ }
+ disappearing.push(rArc);
+ d3_geom_voronoiDetachCircle(rArc);
+ var nArcs = disappearing.length, iArc;
+ for (iArc = 1; iArc < nArcs; ++iArc) {
+ rArc = disappearing[iArc];
+ lArc = disappearing[iArc - 1];
+ d3_geom_voronoiSetEdgeEnd(rArc.edge, lArc.site, rArc.site, vertex);
+ }
+ lArc = disappearing[0];
+ rArc = disappearing[nArcs - 1];
+ rArc.edge = d3_geom_voronoiCreateEdge(lArc.site, rArc.site, null, vertex);
+ d3_geom_voronoiAttachCircle(lArc);
+ d3_geom_voronoiAttachCircle(rArc);
+ }
+ function d3_geom_voronoiAddBeach(site) {
+ var x = site.x, directrix = site.y, lArc, rArc, dxl, dxr, node = d3_geom_voronoiBeaches._;
+ while (node) {
+ dxl = d3_geom_voronoiLeftBreakPoint(node, directrix) - x;
+ if (dxl > ε) node = node.L; else {
+ dxr = x - d3_geom_voronoiRightBreakPoint(node, directrix);
+ if (dxr > ε) {
+ if (!node.R) {
+ lArc = node;
+ break;
+ }
+ node = node.R;
+ } else {
+ if (dxl > -ε) {
+ lArc = node.P;
+ rArc = node;
+ } else if (dxr > -ε) {
+ lArc = node;
+ rArc = node.N;
+ } else {
+ lArc = rArc = node;
+ }
+ break;
+ }
}
}
- if (quad) {
- var lp = points[pi];
- path += "Q" + (p[0] + t[0] * 2 / 3) + "," + (p[1] + t[1] * 2 / 3) + "," + lp[0] + "," + lp[1];
- }
- return path;
- }
- function d3_svg_lineCardinalTangents(points, tension) {
- var tangents = [], a = (1 - tension) / 2, p0, p1 = points[0], p2 = points[1], i = 1, n = points.length;
- while (++i < n) {
- p0 = p1;
- p1 = p2;
- p2 = points[i];
- tangents.push([ a * (p2[0] - p0[0]), a * (p2[1] - p0[1]) ]);
- }
- return tangents;
- }
- function d3_svg_lineBasis(points) {
- if (points.length < 3) return d3_svg_lineLinear(points);
- var i = 1, n = points.length, pi = points[0], x0 = pi[0], y0 = pi[1], px = [ x0, x0, x0, (pi = points[1])[0] ], py = [ y0, y0, y0, pi[1] ], path = [ x0, ",", y0, "L", d3_svg_lineDot4(d3_svg_lineBasisBezier3, px), ",", d3_svg_lineDot4(d3_svg_lineBasisBezier3, py) ];
- points.push(points[n - 1]);
- while (++i <= n) {
- pi = points[i];
- px.shift();
- px.push(pi[0]);
- py.shift();
- py.push(pi[1]);
- d3_svg_lineBasisBezier(path, px, py);
- }
- points.pop();
- path.push("L", pi);
- return path.join("");
- }
- function d3_svg_lineBasisOpen(points) {
- if (points.length < 4) return d3_svg_lineLinear(points);
- var path = [], i = -1, n = points.length, pi, px = [ 0 ], py = [ 0 ];
- while (++i < 3) {
- pi = points[i];
- px.push(pi[0]);
- py.push(pi[1]);
- }
- path.push(d3_svg_lineDot4(d3_svg_lineBasisBezier3, px) + "," + d3_svg_lineDot4(d3_svg_lineBasisBezier3, py));
- --i;
- while (++i < n) {
- pi = points[i];
- px.shift();
- px.push(pi[0]);
- py.shift();
- py.push(pi[1]);
- d3_svg_lineBasisBezier(path, px, py);
- }
- return path.join("");
- }
- function d3_svg_lineBasisClosed(points) {
- var path, i = -1, n = points.length, m = n + 4, pi, px = [], py = [];
- while (++i < 4) {
- pi = points[i % n];
- px.push(pi[0]);
- py.push(pi[1]);
- }
- path = [ d3_svg_lineDot4(d3_svg_lineBasisBezier3, px), ",", d3_svg_lineDot4(d3_svg_lineBasisBezier3, py) ];
- --i;
- while (++i < m) {
- pi = points[i % n];
- px.shift();
- px.push(pi[0]);
- py.shift();
- py.push(pi[1]);
- d3_svg_lineBasisBezier(path, px, py);
+ var newArc = d3_geom_voronoiCreateBeach(site);
+ d3_geom_voronoiBeaches.insert(lArc, newArc);
+ if (!lArc && !rArc) return;
+ if (lArc === rArc) {
+ d3_geom_voronoiDetachCircle(lArc);
+ rArc = d3_geom_voronoiCreateBeach(lArc.site);
+ d3_geom_voronoiBeaches.insert(newArc, rArc);
+ newArc.edge = rArc.edge = d3_geom_voronoiCreateEdge(lArc.site, newArc.site);
+ d3_geom_voronoiAttachCircle(lArc);
+ d3_geom_voronoiAttachCircle(rArc);
+ return;
+ }
+ if (!rArc) {
+ newArc.edge = d3_geom_voronoiCreateEdge(lArc.site, newArc.site);
+ return;
+ }
+ d3_geom_voronoiDetachCircle(lArc);
+ d3_geom_voronoiDetachCircle(rArc);
+ var lSite = lArc.site, ax = lSite.x, ay = lSite.y, bx = site.x - ax, by = site.y - ay, rSite = rArc.site, cx = rSite.x - ax, cy = rSite.y - ay, d = 2 * (bx * cy - by * cx), hb = bx * bx + by * by, hc = cx * cx + cy * cy, vertex = {
+ x: (cy * hb - by * hc) / d + ax,
+ y: (bx * hc - cx * hb) / d + ay
+ };
+ d3_geom_voronoiSetEdgeEnd(rArc.edge, lSite, rSite, vertex);
+ newArc.edge = d3_geom_voronoiCreateEdge(lSite, site, null, vertex);
+ rArc.edge = d3_geom_voronoiCreateEdge(site, rSite, null, vertex);
+ d3_geom_voronoiAttachCircle(lArc);
+ d3_geom_voronoiAttachCircle(rArc);
+ }
+ function d3_geom_voronoiLeftBreakPoint(arc, directrix) {
+ var site = arc.site, rfocx = site.x, rfocy = site.y, pby2 = rfocy - directrix;
+ if (!pby2) return rfocx;
+ var lArc = arc.P;
+ if (!lArc) return -Infinity;
+ site = lArc.site;
+ var lfocx = site.x, lfocy = site.y, plby2 = lfocy - directrix;
+ if (!plby2) return lfocx;
+ var hl = lfocx - rfocx, aby2 = 1 / pby2 - 1 / plby2, b = hl / plby2;
+ if (aby2) return (-b + Math.sqrt(b * b - 2 * aby2 * (hl * hl / (-2 * plby2) - lfocy + plby2 / 2 + rfocy - pby2 / 2))) / aby2 + rfocx;
+ return (rfocx + lfocx) / 2;
+ }
+ function d3_geom_voronoiRightBreakPoint(arc, directrix) {
+ var rArc = arc.N;
+ if (rArc) return d3_geom_voronoiLeftBreakPoint(rArc, directrix);
+ var site = arc.site;
+ return site.y === directrix ? site.x : Infinity;
+ }
+ function d3_geom_voronoiCell(site) {
+ this.site = site;
+ this.edges = [];
+ }
+ d3_geom_voronoiCell.prototype.prepare = function() {
+ var halfEdges = this.edges, iHalfEdge = halfEdges.length, edge;
+ while (iHalfEdge--) {
+ edge = halfEdges[iHalfEdge].edge;
+ if (!edge.b || !edge.a) halfEdges.splice(iHalfEdge, 1);
+ }
+ halfEdges.sort(d3_geom_voronoiHalfEdgeOrder);
+ return halfEdges.length;
+ };
+ function d3_geom_voronoiCloseCells(extent) {
+ var x0 = extent[0][0], x1 = extent[1][0], y0 = extent[0][1], y1 = extent[1][1], x2, y2, x3, y3, cells = d3_geom_voronoiCells, iCell = cells.length, cell, iHalfEdge, halfEdges, nHalfEdges, start, end;
+ while (iCell--) {
+ cell = cells[iCell];
+ if (!cell || !cell.prepare()) continue;
+ halfEdges = cell.edges;
+ nHalfEdges = halfEdges.length;
+ iHalfEdge = 0;
+ while (iHalfEdge < nHalfEdges) {
+ end = halfEdges[iHalfEdge].end(), x3 = end.x, y3 = end.y;
+ start = halfEdges[++iHalfEdge % nHalfEdges].start(), x2 = start.x, y2 = start.y;
+ if (abs(x3 - x2) > ε || abs(y3 - y2) > ε) {
+ halfEdges.splice(iHalfEdge, 0, new d3_geom_voronoiHalfEdge(d3_geom_voronoiCreateBorderEdge(cell.site, end, abs(x3 - x0) < ε && y1 - y3 > ε ? {
+ x: x0,
+ y: abs(x2 - x0) < ε ? y2 : y1
+ } : abs(y3 - y1) < ε && x1 - x3 > ε ? {
+ x: abs(y2 - y1) < ε ? x2 : x1,
+ y: y1
+ } : abs(x3 - x1) < ε && y3 - y0 > ε ? {
+ x: x1,
+ y: abs(x2 - x1) < ε ? y2 : y0
+ } : abs(y3 - y0) < ε && x3 - x0 > ε ? {
+ x: abs(y2 - y0) < ε ? x2 : x0,
+ y: y0
+ } : null), cell.site, null));
+ ++nHalfEdges;
+ }
+ }
}
- return path.join("");
}
- function d3_svg_lineBundle(points, tension) {
- var n = points.length - 1;
- if (n) {
- var x0 = points[0][0], y0 = points[0][1], dx = points[n][0] - x0, dy = points[n][1] - y0, i = -1, p, t;
- while (++i <= n) {
- p = points[i];
- t = i / n;
- p[0] = tension * p[0] + (1 - tension) * (x0 + t * dx);
- p[1] = tension * p[1] + (1 - tension) * (y0 + t * dy);
+ function d3_geom_voronoiHalfEdgeOrder(a, b) {
+ return b.angle - a.angle;
+ }
+ function d3_geom_voronoiCircle() {
+ d3_geom_voronoiRedBlackNode(this);
+ this.x = this.y = this.arc = this.site = this.cy = null;
+ }
+ function d3_geom_voronoiAttachCircle(arc) {
+ var lArc = arc.P, rArc = arc.N;
+ if (!lArc || !rArc) return;
+ var lSite = lArc.site, cSite = arc.site, rSite = rArc.site;
+ if (lSite === rSite) return;
+ var bx = cSite.x, by = cSite.y, ax = lSite.x - bx, ay = lSite.y - by, cx = rSite.x - bx, cy = rSite.y - by;
+ var d = 2 * (ax * cy - ay * cx);
+ if (d >= -ε2) return;
+ var ha = ax * ax + ay * ay, hc = cx * cx + cy * cy, x = (cy * ha - ay * hc) / d, y = (ax * hc - cx * ha) / d, cy = y + by;
+ var circle = d3_geom_voronoiCirclePool.pop() || new d3_geom_voronoiCircle();
+ circle.arc = arc;
+ circle.site = cSite;
+ circle.x = x + bx;
+ circle.y = cy + Math.sqrt(x * x + y * y);
+ circle.cy = cy;
+ arc.circle = circle;
+ var before = null, node = d3_geom_voronoiCircles._;
+ while (node) {
+ if (circle.y < node.y || circle.y === node.y && circle.x <= node.x) {
+ if (node.L) node = node.L; else {
+ before = node.P;
+ break;
+ }
+ } else {
+ if (node.R) node = node.R; else {
+ before = node;
+ break;
+ }
}
}
- return d3_svg_lineBasis(points);
- }
- function d3_svg_lineDot4(a, b) {
- return a[0] * b[0] + a[1] * b[1] + a[2] * b[2] + a[3] * b[3];
- }
- var d3_svg_lineBasisBezier1 = [ 0, 2 / 3, 1 / 3, 0 ], d3_svg_lineBasisBezier2 = [ 0, 1 / 3, 2 / 3, 0 ], d3_svg_lineBasisBezier3 = [ 0, 1 / 6, 2 / 3, 1 / 6 ];
- function d3_svg_lineBasisBezier(path, x, y) {
- path.push("C", d3_svg_lineDot4(d3_svg_lineBasisBezier1, x), ",", d3_svg_lineDot4(d3_svg_lineBasisBezier1, y), ",", d3_svg_lineDot4(d3_svg_lineBasisBezier2, x), ",", d3_svg_lineDot4(d3_svg_lineBasisBezier2, y), ",", d3_svg_lineDot4(d3_svg_lineBasisBezier3, x), ",", d3_svg_lineDot4(d3_svg_lineBasisBezier3, y));
- }
- function d3_svg_lineSlope(p0, p1) {
- return (p1[1] - p0[1]) / (p1[0] - p0[0]);
- }
- function d3_svg_lineFiniteDifferences(points) {
- var i = 0, j = points.length - 1, m = [], p0 = points[0], p1 = points[1], d = m[0] = d3_svg_lineSlope(p0, p1);
- while (++i < j) {
- m[i] = (d + (d = d3_svg_lineSlope(p0 = p1, p1 = points[i + 1]))) / 2;
+ d3_geom_voronoiCircles.insert(before, circle);
+ if (!before) d3_geom_voronoiFirstCircle = circle;
+ }
+ function d3_geom_voronoiDetachCircle(arc) {
+ var circle = arc.circle;
+ if (circle) {
+ if (!circle.P) d3_geom_voronoiFirstCircle = circle.N;
+ d3_geom_voronoiCircles.remove(circle);
+ d3_geom_voronoiCirclePool.push(circle);
+ d3_geom_voronoiRedBlackNode(circle);
+ arc.circle = null;
+ }
+ }
+ function d3_geom_voronoiClipEdges(extent) {
+ var edges = d3_geom_voronoiEdges, clip = d3_geom_clipLine(extent[0][0], extent[0][1], extent[1][0], extent[1][1]), i = edges.length, e;
+ while (i--) {
+ e = edges[i];
+ if (!d3_geom_voronoiConnectEdge(e, extent) || !clip(e) || abs(e.a.x - e.b.x) < ε && abs(e.a.y - e.b.y) < ε) {
+ e.a = e.b = null;
+ edges.splice(i, 1);
+ }
}
- m[i] = d;
- return m;
}
- function d3_svg_lineMonotoneTangents(points) {
- var tangents = [], d, a, b, s, m = d3_svg_lineFiniteDifferences(points), i = -1, j = points.length - 1;
- while (++i < j) {
- d = d3_svg_lineSlope(points[i], points[i + 1]);
- if (Math.abs(d) < 1e-6) {
- m[i] = m[i + 1] = 0;
+ function d3_geom_voronoiConnectEdge(edge, extent) {
+ var vb = edge.b;
+ if (vb) return true;
+ var va = edge.a, x0 = extent[0][0], x1 = extent[1][0], y0 = extent[0][1], y1 = extent[1][1], lSite = edge.l, rSite = edge.r, lx = lSite.x, ly = lSite.y, rx = rSite.x, ry = rSite.y, fx = (lx + rx) / 2, fy = (ly + ry) / 2, fm, fb;
+ if (ry === ly) {
+ if (fx < x0 || fx >= x1) return;
+ if (lx > rx) {
+ if (!va) va = {
+ x: fx,
+ y: y0
+ }; else if (va.y >= y1) return;
+ vb = {
+ x: fx,
+ y: y1
+ };
} else {
- a = m[i] / d;
- b = m[i + 1] / d;
- s = a * a + b * b;
- if (s > 9) {
- s = d * 3 / Math.sqrt(s);
- m[i] = s * a;
- m[i + 1] = s * b;
+ if (!va) va = {
+ x: fx,
+ y: y1
+ }; else if (va.y < y0) return;
+ vb = {
+ x: fx,
+ y: y0
+ };
+ }
+ } else {
+ fm = (lx - rx) / (ry - ly);
+ fb = fy - fm * fx;
+ if (fm < -1 || fm > 1) {
+ if (lx > rx) {
+ if (!va) va = {
+ x: (y0 - fb) / fm,
+ y: y0
+ }; else if (va.y >= y1) return;
+ vb = {
+ x: (y1 - fb) / fm,
+ y: y1
+ };
+ } else {
+ if (!va) va = {
+ x: (y1 - fb) / fm,
+ y: y1
+ }; else if (va.y < y0) return;
+ vb = {
+ x: (y0 - fb) / fm,
+ y: y0
+ };
+ }
+ } else {
+ if (ly < ry) {
+ if (!va) va = {
+ x: x0,
+ y: fm * x0 + fb
+ }; else if (va.x >= x1) return;
+ vb = {
+ x: x1,
+ y: fm * x1 + fb
+ };
+ } else {
+ if (!va) va = {
+ x: x1,
+ y: fm * x1 + fb
+ }; else if (va.x < x0) return;
+ vb = {
+ x: x0,
+ y: fm * x0 + fb
+ };
}
}
}
- i = -1;
- while (++i <= j) {
- s = (points[Math.min(j, i + 1)][0] - points[Math.max(0, i - 1)][0]) / (6 * (1 + m[i] * m[i]));
- tangents.push([ s || 0, m[i] * s || 0 ]);
+ edge.a = va;
+ edge.b = vb;
+ return true;
+ }
+ function d3_geom_voronoiEdge(lSite, rSite) {
+ this.l = lSite;
+ this.r = rSite;
+ this.a = this.b = null;
+ }
+ function d3_geom_voronoiCreateEdge(lSite, rSite, va, vb) {
+ var edge = new d3_geom_voronoiEdge(lSite, rSite);
+ d3_geom_voronoiEdges.push(edge);
+ if (va) d3_geom_voronoiSetEdgeEnd(edge, lSite, rSite, va);
+ if (vb) d3_geom_voronoiSetEdgeEnd(edge, rSite, lSite, vb);
+ d3_geom_voronoiCells[lSite.i].edges.push(new d3_geom_voronoiHalfEdge(edge, lSite, rSite));
+ d3_geom_voronoiCells[rSite.i].edges.push(new d3_geom_voronoiHalfEdge(edge, rSite, lSite));
+ return edge;
+ }
+ function d3_geom_voronoiCreateBorderEdge(lSite, va, vb) {
+ var edge = new d3_geom_voronoiEdge(lSite, null);
+ edge.a = va;
+ edge.b = vb;
+ d3_geom_voronoiEdges.push(edge);
+ return edge;
+ }
+ function d3_geom_voronoiSetEdgeEnd(edge, lSite, rSite, vertex) {
+ if (!edge.a && !edge.b) {
+ edge.a = vertex;
+ edge.l = lSite;
+ edge.r = rSite;
+ } else if (edge.l === rSite) {
+ edge.b = vertex;
+ } else {
+ edge.a = vertex;
}
- return tangents;
}
- function d3_svg_lineMonotone(points) {
- return points.length < 3 ? d3_svg_lineLinear(points) : points[0] + d3_svg_lineHermite(points, d3_svg_lineMonotoneTangents(points));
+ function d3_geom_voronoiHalfEdge(edge, lSite, rSite) {
+ var va = edge.a, vb = edge.b;
+ this.edge = edge;
+ this.site = lSite;
+ this.angle = rSite ? Math.atan2(rSite.y - lSite.y, rSite.x - lSite.x) : edge.l === lSite ? Math.atan2(vb.x - va.x, va.y - vb.y) : Math.atan2(va.x - vb.x, vb.y - va.y);
}
- d3.geom.hull = function(vertices) {
- var x = d3_svg_lineX, y = d3_svg_lineY;
- if (arguments.length) return hull(vertices);
- function hull(data) {
- if (data.length < 3) return [];
- var fx = d3_functor(x), fy = d3_functor(y), n = data.length, vertices, plen = n - 1, points = [], stack = [], d, i, j, h = 0, x1, y1, x2, y2, u, v, a, sp;
- if (fx === d3_svg_lineX && y === d3_svg_lineY) vertices = data; else for (i = 0,
- vertices = []; i < n; ++i) {
- vertices.push([ +fx.call(this, d = data[i], i), +fy.call(this, d, i) ]);
- }
- for (i = 1; i < n; ++i) {
- if (vertices[i][1] < vertices[h][1] || vertices[i][1] == vertices[h][1] && vertices[i][0] < vertices[h][0]) h = i;
- }
- for (i = 0; i < n; ++i) {
- if (i === h) continue;
- y1 = vertices[i][1] - vertices[h][1];
- x1 = vertices[i][0] - vertices[h][0];
- points.push({
- angle: Math.atan2(y1, x1),
- index: i
- });
+ d3_geom_voronoiHalfEdge.prototype = {
+ start: function() {
+ return this.edge.l === this.site ? this.edge.a : this.edge.b;
+ },
+ end: function() {
+ return this.edge.l === this.site ? this.edge.b : this.edge.a;
+ }
+ };
+ function d3_geom_voronoiRedBlackTree() {
+ this._ = null;
+ }
+ function d3_geom_voronoiRedBlackNode(node) {
+ node.U = node.C = node.L = node.R = node.P = node.N = null;
+ }
+ d3_geom_voronoiRedBlackTree.prototype = {
+ insert: function(after, node) {
+ var parent, grandpa, uncle;
+ if (after) {
+ node.P = after;
+ node.N = after.N;
+ if (after.N) after.N.P = node;
+ after.N = node;
+ if (after.R) {
+ after = after.R;
+ while (after.L) after = after.L;
+ after.L = node;
+ } else {
+ after.R = node;
+ }
+ parent = after;
+ } else if (this._) {
+ after = d3_geom_voronoiRedBlackFirst(this._);
+ node.P = null;
+ node.N = after;
+ after.P = after.L = node;
+ parent = after;
+ } else {
+ node.P = node.N = null;
+ this._ = node;
+ parent = null;
}
- points.sort(function(a, b) {
- return a.angle - b.angle;
- });
- a = points[0].angle;
- v = points[0].index;
- u = 0;
- for (i = 1; i < plen; ++i) {
- j = points[i].index;
- if (a == points[i].angle) {
- x1 = vertices[v][0] - vertices[h][0];
- y1 = vertices[v][1] - vertices[h][1];
- x2 = vertices[j][0] - vertices[h][0];
- y2 = vertices[j][1] - vertices[h][1];
- if (x1 * x1 + y1 * y1 >= x2 * x2 + y2 * y2) {
- points[i].index = -1;
- continue;
+ node.L = node.R = null;
+ node.U = parent;
+ node.C = true;
+ after = node;
+ while (parent && parent.C) {
+ grandpa = parent.U;
+ if (parent === grandpa.L) {
+ uncle = grandpa.R;
+ if (uncle && uncle.C) {
+ parent.C = uncle.C = false;
+ grandpa.C = true;
+ after = grandpa;
} else {
- points[u].index = -1;
+ if (after === parent.R) {
+ d3_geom_voronoiRedBlackRotateLeft(this, parent);
+ after = parent;
+ parent = after.U;
+ }
+ parent.C = false;
+ grandpa.C = true;
+ d3_geom_voronoiRedBlackRotateRight(this, grandpa);
+ }
+ } else {
+ uncle = grandpa.L;
+ if (uncle && uncle.C) {
+ parent.C = uncle.C = false;
+ grandpa.C = true;
+ after = grandpa;
+ } else {
+ if (after === parent.L) {
+ d3_geom_voronoiRedBlackRotateRight(this, parent);
+ after = parent;
+ parent = after.U;
+ }
+ parent.C = false;
+ grandpa.C = true;
+ d3_geom_voronoiRedBlackRotateLeft(this, grandpa);
}
}
- a = points[i].angle;
- u = i;
- v = j;
+ parent = after.U;
}
- stack.push(h);
- for (i = 0, j = 0; i < 2; ++j) {
- if (points[j].index > -1) {
- stack.push(points[j].index);
- i++;
- }
+ this._.C = false;
+ },
+ remove: function(node) {
+ if (node.N) node.N.P = node.P;
+ if (node.P) node.P.N = node.N;
+ node.N = node.P = null;
+ var parent = node.U, sibling, left = node.L, right = node.R, next, red;
+ if (!left) next = right; else if (!right) next = left; else next = d3_geom_voronoiRedBlackFirst(right);
+ if (parent) {
+ if (parent.L === node) parent.L = next; else parent.R = next;
+ } else {
+ this._ = next;
}
- sp = stack.length;
- for (;j < plen; ++j) {
- if (points[j].index < 0) continue;
- while (!d3_geom_hullCCW(stack[sp - 2], stack[sp - 1], points[j].index, vertices)) {
- --sp;
+ if (left && right) {
+ red = next.C;
+ next.C = node.C;
+ next.L = left;
+ left.U = next;
+ if (next !== right) {
+ parent = next.U;
+ next.U = node.U;
+ node = next.R;
+ parent.L = node;
+ next.R = right;
+ right.U = next;
+ } else {
+ next.U = parent;
+ parent = next;
+ node = next.R;
}
- stack[sp++] = points[j].index;
+ } else {
+ red = node.C;
+ node = next;
}
- var poly = [];
- for (i = sp - 1; i >= 0; --i) poly.push(data[stack[i]]);
- return poly;
- }
- hull.x = function(_) {
- return arguments.length ? (x = _, hull) : x;
- };
- hull.y = function(_) {
- return arguments.length ? (y = _, hull) : y;
- };
- return hull;
- };
- function d3_geom_hullCCW(i1, i2, i3, v) {
- var t, a, b, c, d, e, f;
- t = v[i1];
- a = t[0];
- b = t[1];
- t = v[i2];
- c = t[0];
- d = t[1];
- t = v[i3];
- e = t[0];
- f = t[1];
- return (f - b) * (c - a) - (d - b) * (e - a) > 0;
- }
- d3.geom.polygon = function(coordinates) {
- d3_subclass(coordinates, d3_geom_polygonPrototype);
- return coordinates;
- };
- var d3_geom_polygonPrototype = d3.geom.polygon.prototype = [];
- d3_geom_polygonPrototype.area = function() {
- var i = -1, n = this.length, a, b = this[n - 1], area = 0;
- while (++i < n) {
- a = b;
- b = this[i];
- area += a[1] * b[0] - a[0] * b[1];
+ if (node) node.U = parent;
+ if (red) return;
+ if (node && node.C) {
+ node.C = false;
+ return;
+ }
+ do {
+ if (node === this._) break;
+ if (node === parent.L) {
+ sibling = parent.R;
+ if (sibling.C) {
+ sibling.C = false;
+ parent.C = true;
+ d3_geom_voronoiRedBlackRotateLeft(this, parent);
+ sibling = parent.R;
+ }
+ if (sibling.L && sibling.L.C || sibling.R && sibling.R.C) {
+ if (!sibling.R || !sibling.R.C) {
+ sibling.L.C = false;
+ sibling.C = true;
+ d3_geom_voronoiRedBlackRotateRight(this, sibling);
+ sibling = parent.R;
+ }
+ sibling.C = parent.C;
+ parent.C = sibling.R.C = false;
+ d3_geom_voronoiRedBlackRotateLeft(this, parent);
+ node = this._;
+ break;
+ }
+ } else {
+ sibling = parent.L;
+ if (sibling.C) {
+ sibling.C = false;
+ parent.C = true;
+ d3_geom_voronoiRedBlackRotateRight(this, parent);
+ sibling = parent.L;
+ }
+ if (sibling.L && sibling.L.C || sibling.R && sibling.R.C) {
+ if (!sibling.L || !sibling.L.C) {
+ sibling.R.C = false;
+ sibling.C = true;
+ d3_geom_voronoiRedBlackRotateLeft(this, sibling);
+ sibling = parent.L;
+ }
+ sibling.C = parent.C;
+ parent.C = sibling.L.C = false;
+ d3_geom_voronoiRedBlackRotateRight(this, parent);
+ node = this._;
+ break;
+ }
+ }
+ sibling.C = true;
+ node = parent;
+ parent = parent.U;
+ } while (!node.C);
+ if (node) node.C = false;
}
- return area * .5;
};
- d3_geom_polygonPrototype.centroid = function(k) {
- var i = -1, n = this.length, x = 0, y = 0, a, b = this[n - 1], c;
- if (!arguments.length) k = -1 / (6 * this.area());
- while (++i < n) {
- a = b;
- b = this[i];
- c = a[0] * b[1] - b[0] * a[1];
- x += (a[0] + b[0]) * c;
- y += (a[1] + b[1]) * c;
+ function d3_geom_voronoiRedBlackRotateLeft(tree, node) {
+ var p = node, q = node.R, parent = p.U;
+ if (parent) {
+ if (parent.L === p) parent.L = q; else parent.R = q;
+ } else {
+ tree._ = q;
+ }
+ q.U = parent;
+ p.U = q;
+ p.R = q.L;
+ if (p.R) p.R.U = p;
+ q.L = p;
+ }
+ function d3_geom_voronoiRedBlackRotateRight(tree, node) {
+ var p = node, q = node.L, parent = p.U;
+ if (parent) {
+ if (parent.L === p) parent.L = q; else parent.R = q;
+ } else {
+ tree._ = q;
}
- return [ x * k, y * k ];
- };
- d3_geom_polygonPrototype.clip = function(subject) {
- var input, closed = d3_geom_polygonClosed(subject), i = -1, n = this.length - d3_geom_polygonClosed(this), j, m, a = this[n - 1], b, c, d;
- while (++i < n) {
- input = subject.slice();
- subject.length = 0;
- b = this[i];
- c = input[(m = input.length - closed) - 1];
- j = -1;
- while (++j < m) {
- d = input[j];
- if (d3_geom_polygonInside(d, a, b)) {
- if (!d3_geom_polygonInside(c, a, b)) {
- subject.push(d3_geom_polygonIntersect(c, d, a, b));
- }
- subject.push(d);
- } else if (d3_geom_polygonInside(c, a, b)) {
- subject.push(d3_geom_polygonIntersect(c, d, a, b));
+ q.U = parent;
+ p.U = q;
+ p.L = q.R;
+ if (p.L) p.L.U = p;
+ q.R = p;
+ }
+ function d3_geom_voronoiRedBlackFirst(node) {
+ while (node.L) node = node.L;
+ return node;
+ }
+ function d3_geom_voronoi(sites, bbox) {
+ var site = sites.sort(d3_geom_voronoiVertexOrder).pop(), x0, y0, circle;
+ d3_geom_voronoiEdges = [];
+ d3_geom_voronoiCells = new Array(sites.length);
+ d3_geom_voronoiBeaches = new d3_geom_voronoiRedBlackTree();
+ d3_geom_voronoiCircles = new d3_geom_voronoiRedBlackTree();
+ while (true) {
+ circle = d3_geom_voronoiFirstCircle;
+ if (site && (!circle || site.y < circle.y || site.y === circle.y && site.x < circle.x)) {
+ if (site.x !== x0 || site.y !== y0) {
+ d3_geom_voronoiCells[site.i] = new d3_geom_voronoiCell(site);
+ d3_geom_voronoiAddBeach(site);
+ x0 = site.x, y0 = site.y;
}
- c = d;
+ site = sites.pop();
+ } else if (circle) {
+ d3_geom_voronoiRemoveBeach(circle.arc);
+ } else {
+ break;
}
- if (closed) subject.push(subject[0]);
- a = b;
}
- return subject;
- };
- function d3_geom_polygonInside(p, a, b) {
- return (b[0] - a[0]) * (p[1] - a[1]) < (b[1] - a[1]) * (p[0] - a[0]);
- }
- function d3_geom_polygonIntersect(c, d, a, b) {
- var x1 = c[0], x3 = a[0], x21 = d[0] - x1, x43 = b[0] - x3, y1 = c[1], y3 = a[1], y21 = d[1] - y1, y43 = b[1] - y3, ua = (x43 * (y1 - y3) - y43 * (x1 - x3)) / (y43 * x21 - x43 * y21);
- return [ x1 + ua * x21, y1 + ua * y21 ];
+ if (bbox) d3_geom_voronoiClipEdges(bbox), d3_geom_voronoiCloseCells(bbox);
+ var diagram = {
+ cells: d3_geom_voronoiCells,
+ edges: d3_geom_voronoiEdges
+ };
+ d3_geom_voronoiBeaches = d3_geom_voronoiCircles = d3_geom_voronoiEdges = d3_geom_voronoiCells = null;
+ return diagram;
}
- function d3_geom_polygonClosed(coordinates) {
- var a = coordinates[0], b = coordinates[coordinates.length - 1];
- return !(a[0] - b[0] || a[1] - b[1]);
+ function d3_geom_voronoiVertexOrder(a, b) {
+ return b.y - a.y || b.x - a.x;
}
- d3.geom.delaunay = function(vertices) {
- var edges = vertices.map(function() {
- return [];
- }), triangles = [];
- d3_geom_voronoiTessellate(vertices, function(e) {
- edges[e.region.l.index].push(vertices[e.region.r.index]);
- });
- edges.forEach(function(edge, i) {
- var v = vertices[i], cx = v[0], cy = v[1];
- edge.forEach(function(v) {
- v.angle = Math.atan2(v[0] - cx, v[1] - cy);
- });
- edge.sort(function(a, b) {
- return a.angle - b.angle;
- });
- for (var j = 0, m = edge.length - 1; j < m; j++) {
- triangles.push([ v, edge[j], edge[j + 1] ]);
- }
- });
- return triangles;
- };
d3.geom.voronoi = function(points) {
- var x = d3_svg_lineX, y = d3_svg_lineY, clipPolygon = null;
- if (arguments.length) return voronoi(points);
+ var x = d3_geom_pointX, y = d3_geom_pointY, fx = x, fy = y, clipExtent = d3_geom_voronoiClipExtent;
+ if (points) return voronoi(points);
function voronoi(data) {
- var points, polygons = data.map(function() {
- return [];
- }), fx = d3_functor(x), fy = d3_functor(y), d, i, n = data.length, Z = 1e6;
- if (fx === d3_svg_lineX && fy === d3_svg_lineY) points = data; else for (points = new Array(n),
- i = 0; i < n; ++i) {
- points[i] = [ +fx.call(this, d = data[i], i), +fy.call(this, d, i) ];
- }
- d3_geom_voronoiTessellate(points, function(e) {
- var s1, s2, x1, x2, y1, y2;
- if (e.a === 1 && e.b >= 0) {
- s1 = e.ep.r;
- s2 = e.ep.l;
- } else {
- s1 = e.ep.l;
- s2 = e.ep.r;
- }
- if (e.a === 1) {
- y1 = s1 ? s1.y : -Z;
- x1 = e.c - e.b * y1;
- y2 = s2 ? s2.y : Z;
- x2 = e.c - e.b * y2;
- } else {
- x1 = s1 ? s1.x : -Z;
- y1 = e.c - e.a * x1;
- x2 = s2 ? s2.x : Z;
- y2 = e.c - e.a * x2;
- }
- var v1 = [ x1, y1 ], v2 = [ x2, y2 ];
- polygons[e.region.l.index].push(v1, v2);
- polygons[e.region.r.index].push(v1, v2);
+ var polygons = new Array(data.length), x0 = clipExtent[0][0], y0 = clipExtent[0][1], x1 = clipExtent[1][0], y1 = clipExtent[1][1];
+ d3_geom_voronoi(sites(data), clipExtent).cells.forEach(function(cell, i) {
+ var edges = cell.edges, site = cell.site, polygon = polygons[i] = edges.length ? edges.map(function(e) {
+ var s = e.start();
+ return [ s.x, s.y ];
+ }) : site.x >= x0 && site.x <= x1 && site.y >= y0 && site.y <= y1 ? [ [ x0, y1 ], [ x1, y1 ], [ x1, y0 ], [ x0, y0 ] ] : [];
+ polygon.point = data[i];
});
- polygons = polygons.map(function(polygon, i) {
- var cx = points[i][0], cy = points[i][1], angle = polygon.map(function(v) {
- return Math.atan2(v[0] - cx, v[1] - cy);
- }), order = d3.range(polygon.length).sort(function(a, b) {
- return angle[a] - angle[b];
- });
- return order.filter(function(d, i) {
- return !i || angle[d] - angle[order[i - 1]] > ε;
- }).map(function(d) {
- return polygon[d];
- });
+ return polygons;
+ }
+ function sites(data) {
+ return data.map(function(d, i) {
+ return {
+ x: Math.round(fx(d, i) / ε) * ε,
+ y: Math.round(fy(d, i) / ε) * ε,
+ i: i
+ };
});
- polygons.forEach(function(polygon, i) {
- var n = polygon.length;
- if (!n) return polygon.push([ -Z, -Z ], [ -Z, Z ], [ Z, Z ], [ Z, -Z ]);
- if (n > 2) return;
- var p0 = points[i], p1 = polygon[0], p2 = polygon[1], x0 = p0[0], y0 = p0[1], x1 = p1[0], y1 = p1[1], x2 = p2[0], y2 = p2[1], dx = Math.abs(x2 - x1), dy = y2 - y1;
- if (Math.abs(dy) < ε) {
- var y = y0 < y1 ? -Z : Z;
- polygon.push([ -Z, y ], [ Z, y ]);
- } else if (dx < ε) {
- var x = x0 < x1 ? -Z : Z;
- polygon.push([ x, -Z ], [ x, Z ]);
- } else {
- var y = (x2 - x1) * (y1 - y0) < (x1 - x0) * (y2 - y1) ? Z : -Z, z = Math.abs(dy) - dx;
- if (Math.abs(z) < ε) {
- polygon.push([ dy < 0 ? y : -y, y ]);
- } else {
- if (z > 0) y *= -1;
- polygon.push([ -Z, y ], [ Z, y ]);
+ }
+ voronoi.links = function(data) {
+ return d3_geom_voronoi(sites(data)).edges.filter(function(edge) {
+ return edge.l && edge.r;
+ }).map(function(edge) {
+ return {
+ source: data[edge.l.i],
+ target: data[edge.r.i]
+ };
+ });
+ };
+ voronoi.triangles = function(data) {
+ var triangles = [];
+ d3_geom_voronoi(sites(data)).cells.forEach(function(cell, i) {
+ var site = cell.site, edges = cell.edges.sort(d3_geom_voronoiHalfEdgeOrder), j = -1, m = edges.length, e0, s0, e1 = edges[m - 1].edge, s1 = e1.l === site ? e1.r : e1.l;
+ while (++j < m) {
+ e0 = e1;
+ s0 = s1;
+ e1 = edges[j].edge;
+ s1 = e1.l === site ? e1.r : e1.l;
+ if (i < s0.i && i < s1.i && d3_geom_voronoiTriangleArea(site, s0, s1) < 0) {
+ triangles.push([ data[i], data[s0.i], data[s1.i] ]);
}
}
});
- if (clipPolygon) for (i = 0; i < n; ++i) clipPolygon.clip(polygons[i]);
- for (i = 0; i < n; ++i) polygons[i].point = data[i];
- return polygons;
- }
+ return triangles;
+ };
voronoi.x = function(_) {
- return arguments.length ? (x = _, voronoi) : x;
+ return arguments.length ? (fx = d3_functor(x = _), voronoi) : x;
};
voronoi.y = function(_) {
- return arguments.length ? (y = _, voronoi) : y;
+ return arguments.length ? (fy = d3_functor(y = _), voronoi) : y;
};
voronoi.clipExtent = function(_) {
- if (!arguments.length) return clipPolygon && [ clipPolygon[0], clipPolygon[2] ];
- if (_ == null) clipPolygon = null; else {
- var x1 = +_[0][0], y1 = +_[0][1], x2 = +_[1][0], y2 = +_[1][1];
- clipPolygon = d3.geom.polygon([ [ x1, y1 ], [ x1, y2 ], [ x2, y2 ], [ x2, y1 ] ]);
- }
+ if (!arguments.length) return clipExtent === d3_geom_voronoiClipExtent ? null : clipExtent;
+ clipExtent = _ == null ? d3_geom_voronoiClipExtent : _;
return voronoi;
};
voronoi.size = function(_) {
- if (!arguments.length) return clipPolygon && clipPolygon[2];
+ if (!arguments.length) return clipExtent === d3_geom_voronoiClipExtent ? null : clipExtent && clipExtent[1];
return voronoi.clipExtent(_ && [ [ 0, 0 ], _ ]);
};
- voronoi.links = function(data) {
- var points, graph = data.map(function() {
- return [];
- }), links = [], fx = d3_functor(x), fy = d3_functor(y), d, i, n = data.length;
- if (fx === d3_svg_lineX && fy === d3_svg_lineY) points = data; else for (points = new Array(n),
- i = 0; i < n; ++i) {
- points[i] = [ +fx.call(this, d = data[i], i), +fy.call(this, d, i) ];
- }
- d3_geom_voronoiTessellate(points, function(e) {
- var l = e.region.l.index, r = e.region.r.index;
- if (graph[l][r]) return;
- graph[l][r] = graph[r][l] = true;
- links.push({
- source: data[l],
- target: data[r]
- });
- });
- return links;
- };
- voronoi.triangles = function(data) {
- if (x === d3_svg_lineX && y === d3_svg_lineY) return d3.geom.delaunay(data);
- var points = new Array(n), fx = d3_functor(x), fy = d3_functor(y), d, i = -1, n = data.length;
- while (++i < n) {
- (points[i] = [ +fx.call(this, d = data[i], i), +fy.call(this, d, i) ]).data = d;
- }
- return d3.geom.delaunay(points).map(function(triangle) {
- return triangle.map(function(point) {
- return point.data;
- });
- });
- };
return voronoi;
};
- var d3_geom_voronoiOpposite = {
- l: "r",
- r: "l"
- };
- function d3_geom_voronoiTessellate(points, callback) {
- var Sites = {
- list: points.map(function(v, i) {
- return {
- index: i,
- x: v[0],
- y: v[1]
- };
- }).sort(function(a, b) {
- return a.y < b.y ? -1 : a.y > b.y ? 1 : a.x < b.x ? -1 : a.x > b.x ? 1 : 0;
- }),
- bottomSite: null
- };
- var EdgeList = {
- list: [],
- leftEnd: null,
- rightEnd: null,
- init: function() {
- EdgeList.leftEnd = EdgeList.createHalfEdge(null, "l");
- EdgeList.rightEnd = EdgeList.createHalfEdge(null, "l");
- EdgeList.leftEnd.r = EdgeList.rightEnd;
- EdgeList.rightEnd.l = EdgeList.leftEnd;
- EdgeList.list.unshift(EdgeList.leftEnd, EdgeList.rightEnd);
- },
- createHalfEdge: function(edge, side) {
- return {
- edge: edge,
- side: side,
- vertex: null,
- l: null,
- r: null
- };
- },
- insert: function(lb, he) {
- he.l = lb;
- he.r = lb.r;
- lb.r.l = he;
- lb.r = he;
- },
- leftBound: function(p) {
- var he = EdgeList.leftEnd;
- do {
- he = he.r;
- } while (he != EdgeList.rightEnd && Geom.rightOf(he, p));
- he = he.l;
- return he;
- },
- del: function(he) {
- he.l.r = he.r;
- he.r.l = he.l;
- he.edge = null;
- },
- right: function(he) {
- return he.r;
- },
- left: function(he) {
- return he.l;
- },
- leftRegion: function(he) {
- return he.edge == null ? Sites.bottomSite : he.edge.region[he.side];
- },
- rightRegion: function(he) {
- return he.edge == null ? Sites.bottomSite : he.edge.region[d3_geom_voronoiOpposite[he.side]];
- }
- };
- var Geom = {
- bisect: function(s1, s2) {
- var newEdge = {
- region: {
- l: s1,
- r: s2
- },
- ep: {
- l: null,
- r: null
- }
- };
- var dx = s2.x - s1.x, dy = s2.y - s1.y, adx = dx > 0 ? dx : -dx, ady = dy > 0 ? dy : -dy;
- newEdge.c = s1.x * dx + s1.y * dy + (dx * dx + dy * dy) * .5;
- if (adx > ady) {
- newEdge.a = 1;
- newEdge.b = dy / dx;
- newEdge.c /= dx;
- } else {
- newEdge.b = 1;
- newEdge.a = dx / dy;
- newEdge.c /= dy;
- }
- return newEdge;
- },
- intersect: function(el1, el2) {
- var e1 = el1.edge, e2 = el2.edge;
- if (!e1 || !e2 || e1.region.r == e2.region.r) {
- return null;
- }
- var d = e1.a * e2.b - e1.b * e2.a;
- if (Math.abs(d) < 1e-10) {
- return null;
- }
- var xint = (e1.c * e2.b - e2.c * e1.b) / d, yint = (e2.c * e1.a - e1.c * e2.a) / d, e1r = e1.region.r, e2r = e2.region.r, el, e;
- if (e1r.y < e2r.y || e1r.y == e2r.y && e1r.x < e2r.x) {
- el = el1;
- e = e1;
- } else {
- el = el2;
- e = e2;
- }
- var rightOfSite = xint >= e.region.r.x;
- if (rightOfSite && el.side === "l" || !rightOfSite && el.side === "r") {
- return null;
- }
- return {
- x: xint,
- y: yint
- };
- },
- rightOf: function(he, p) {
- var e = he.edge, topsite = e.region.r, rightOfSite = p.x > topsite.x;
- if (rightOfSite && he.side === "l") {
- return 1;
- }
- if (!rightOfSite && he.side === "r") {
- return 0;
- }
- if (e.a === 1) {
- var dyp = p.y - topsite.y, dxp = p.x - topsite.x, fast = 0, above = 0;
- if (!rightOfSite && e.b < 0 || rightOfSite && e.b >= 0) {
- above = fast = dyp >= e.b * dxp;
- } else {
- above = p.x + p.y * e.b > e.c;
- if (e.b < 0) {
- above = !above;
- }
- if (!above) {
- fast = 1;
- }
- }
- if (!fast) {
- var dxs = topsite.x - e.region.l.x;
- above = e.b * (dxp * dxp - dyp * dyp) < dxs * dyp * (1 + 2 * dxp / dxs + e.b * e.b);
- if (e.b < 0) {
- above = !above;
- }
- }
- } else {
- var yl = e.c - e.a * p.x, t1 = p.y - yl, t2 = p.x - topsite.x, t3 = yl - topsite.y;
- above = t1 * t1 > t2 * t2 + t3 * t3;
- }
- return he.side === "l" ? above : !above;
- },
- endPoint: function(edge, side, site) {
- edge.ep[side] = site;
- if (!edge.ep[d3_geom_voronoiOpposite[side]]) return;
- callback(edge);
- },
- distance: function(s, t) {
- var dx = s.x - t.x, dy = s.y - t.y;
- return Math.sqrt(dx * dx + dy * dy);
- }
- };
- var EventQueue = {
- list: [],
- insert: function(he, site, offset) {
- he.vertex = site;
- he.ystar = site.y + offset;
- for (var i = 0, list = EventQueue.list, l = list.length; i < l; i++) {
- var next = list[i];
- if (he.ystar > next.ystar || he.ystar == next.ystar && site.x > next.vertex.x) {
- continue;
- } else {
- break;
- }
- }
- list.splice(i, 0, he);
- },
- del: function(he) {
- for (var i = 0, ls = EventQueue.list, l = ls.length; i < l && ls[i] != he; ++i) {}
- ls.splice(i, 1);
- },
- empty: function() {
- return EventQueue.list.length === 0;
- },
- nextEvent: function(he) {
- for (var i = 0, ls = EventQueue.list, l = ls.length; i < l; ++i) {
- if (ls[i] == he) return ls[i + 1];
- }
- return null;
- },
- min: function() {
- var elem = EventQueue.list[0];
- return {
- x: elem.vertex.x,
- y: elem.ystar
- };
- },
- extractMin: function() {
- return EventQueue.list.shift();
- }
- };
- EdgeList.init();
- Sites.bottomSite = Sites.list.shift();
- var newSite = Sites.list.shift(), newIntStar;
- var lbnd, rbnd, llbnd, rrbnd, bisector;
- var bot, top, temp, p, v;
- var e, pm;
- while (true) {
- if (!EventQueue.empty()) {
- newIntStar = EventQueue.min();
- }
- if (newSite && (EventQueue.empty() || newSite.y < newIntStar.y || newSite.y == newIntStar.y && newSite.x < newIntStar.x)) {
- lbnd = EdgeList.leftBound(newSite);
- rbnd = EdgeList.right(lbnd);
- bot = EdgeList.rightRegion(lbnd);
- e = Geom.bisect(bot, newSite);
- bisector = EdgeList.createHalfEdge(e, "l");
- EdgeList.insert(lbnd, bisector);
- p = Geom.intersect(lbnd, bisector);
- if (p) {
- EventQueue.del(lbnd);
- EventQueue.insert(lbnd, p, Geom.distance(p, newSite));
- }
- lbnd = bisector;
- bisector = EdgeList.createHalfEdge(e, "r");
- EdgeList.insert(lbnd, bisector);
- p = Geom.intersect(bisector, rbnd);
- if (p) {
- EventQueue.insert(bisector, p, Geom.distance(p, newSite));
- }
- newSite = Sites.list.shift();
- } else if (!EventQueue.empty()) {
- lbnd = EventQueue.extractMin();
- llbnd = EdgeList.left(lbnd);
- rbnd = EdgeList.right(lbnd);
- rrbnd = EdgeList.right(rbnd);
- bot = EdgeList.leftRegion(lbnd);
- top = EdgeList.rightRegion(rbnd);
- v = lbnd.vertex;
- Geom.endPoint(lbnd.edge, lbnd.side, v);
- Geom.endPoint(rbnd.edge, rbnd.side, v);
- EdgeList.del(lbnd);
- EventQueue.del(rbnd);
- EdgeList.del(rbnd);
- pm = "l";
- if (bot.y > top.y) {
- temp = bot;
- bot = top;
- top = temp;
- pm = "r";
- }
- e = Geom.bisect(bot, top);
- bisector = EdgeList.createHalfEdge(e, pm);
- EdgeList.insert(llbnd, bisector);
- Geom.endPoint(e, d3_geom_voronoiOpposite[pm], v);
- p = Geom.intersect(llbnd, bisector);
- if (p) {
- EventQueue.del(llbnd);
- EventQueue.insert(llbnd, p, Geom.distance(p, bot));
- }
- p = Geom.intersect(bisector, rrbnd);
- if (p) {
- EventQueue.insert(bisector, p, Geom.distance(p, bot));
- }
- } else {
- break;
- }
- }
- for (lbnd = EdgeList.right(EdgeList.leftEnd); lbnd != EdgeList.rightEnd; lbnd = EdgeList.right(lbnd)) {
- callback(lbnd.edge);
- }
+ var d3_geom_voronoiClipExtent = [ [ -1e6, -1e6 ], [ 1e6, 1e6 ] ];
+ function d3_geom_voronoiTriangleArea(a, b, c) {
+ return (a.x - c.x) * (b.y - a.y) - (a.x - b.x) * (c.y - a.y);
}
+ d3.geom.delaunay = function(vertices) {
+ return d3.geom.voronoi().triangles(vertices);
+ };
d3.geom.quadtree = function(points, x1, y1, x2, y2) {
- var x = d3_svg_lineX, y = d3_svg_lineY, compat;
+ var x = d3_geom_pointX, y = d3_geom_pointY, compat;
if (compat = arguments.length) {
x = d3_geom_quadtreeCompatX;
y = d3_geom_quadtreeCompatY;
@@ -18606,7 +18608,7 @@ d3 = function() {
if (n.leaf) {
var nx = n.x, ny = n.y;
if (nx != null) {
- if (Math.abs(nx - x) + Math.abs(ny - y) < .01) {
+ if (abs(nx - x) + abs(ny - y) < .01) {
insertChild(n, d, x, y, x1, y1, x2, y2);
} else {
var nPoint = n.point;
@@ -18852,7 +18854,7 @@ d3 = function() {
var i = name.indexOf("-"), t = i >= 0 ? name.substring(0, i) : name, m = i >= 0 ? name.substring(i + 1) : "in";
t = d3_ease.get(t) || d3_ease_default;
m = d3_ease_mode.get(m) || d3_identity;
- return d3_ease_clamp(m(t.apply(null, Array.prototype.slice.call(arguments, 1))));
+ return d3_ease_clamp(m(t.apply(null, d3_arraySlice.call(arguments, 1))));
};
function d3_ease_clamp(f) {
return function(t) {
@@ -18887,7 +18889,7 @@ d3 = function() {
};
}
function d3_ease_sin(t) {
- return 1 - Math.cos(t * π / 2);
+ return 1 - Math.cos(t * halfπ);
}
function d3_ease_exp(t) {
return Math.pow(2, 10 * (t - 1));
@@ -18898,9 +18900,9 @@ d3 = function() {
function d3_ease_elastic(a, p) {
var s;
if (arguments.length < 2) p = .45;
- if (arguments.length) s = p / (2 * π) * Math.asin(1 / a); else a = 1, s = p / 4;
+ if (arguments.length) s = p / τ * Math.asin(1 / a); else a = 1, s = p / 4;
return function(t) {
- return 1 + a * Math.pow(2, 10 * -t) * Math.sin((t - s) * 2 * π / p);
+ return 1 + a * Math.pow(2, -10 * t) * Math.sin((t - s) * τ / p);
};
}
function d3_ease_back(s) {
@@ -19134,7 +19136,7 @@ d3 = function() {
});
});
}
- k = (2 * π - padding * n) / k;
+ k = (τ - padding * n) / k;
x = 0, i = -1;
while (++i < n) {
x0 = x, j = -1;
@@ -19361,7 +19363,7 @@ d3 = function() {
return force;
};
force.start = function() {
- var i, j, n = nodes.length, m = links.length, w = size[0], h = size[1], neighbors, o;
+ var i, n = nodes.length, m = links.length, w = size[0], h = size[1], neighbors, o;
for (i = 0; i < n; ++i) {
(o = nodes[i]).index = i;
o.weight = 0;
@@ -19387,13 +19389,8 @@ d3 = function() {
charges = [];
if (typeof charge === "function") for (i = 0; i < n; ++i) charges[i] = +charge.call(this, nodes[i], i); else for (i = 0; i < n; ++i) charges[i] = charge;
function position(dimension, size) {
- var neighbors = neighbor(i), j = -1, m = neighbors.length, x;
- while (++j < m) if (!isNaN(x = neighbors[j][dimension])) return x;
- return Math.random() * size;
- }
- function neighbor() {
if (!neighbors) {
- neighbors = [];
+ neighbors = new Array(n);
for (j = 0; j < n; ++j) {
neighbors[j] = [];
}
@@ -19403,7 +19400,9 @@ d3 = function() {
neighbors[o.target.index].push(o.source);
}
}
- return neighbors[i];
+ var candidates = neighbors[i], j = -1, m = candidates.length, x;
+ while (++j < m) if (!isNaN(x = candidates[j][dimension])) return x;
+ return Math.random() * size;
}
return force.resume();
};
@@ -19472,17 +19471,19 @@ d3 = function() {
node.depth = depth;
nodes.push(node);
if (childs && (n = childs.length)) {
- var i = -1, n, c = node.children = [], v = 0, j = depth + 1, d;
+ var i = -1, n, c = node.children = new Array(n), v = 0, j = depth + 1, d;
while (++i < n) {
- d = recurse(childs[i], j, nodes);
+ d = c[i] = recurse(childs[i], j, nodes);
d.parent = node;
- c.push(d);
v += d.value;
}
if (sort) c.sort(sort);
if (value) node.value = v;
- } else if (value) {
- node.value = +value.call(hierarchy, node, depth) || 0;
+ } else {
+ delete node.children;
+ if (value) {
+ node.value = +value.call(hierarchy, node, depth) || 0;
+ }
}
return node;
}
@@ -19586,7 +19587,7 @@ d3 = function() {
return d3_layout_hierarchyRebind(partition, hierarchy);
};
d3.layout.pie = function() {
- var value = Number, sort = d3_layout_pieSortByValue, startAngle = 0, endAngle = 2 * π;
+ var value = Number, sort = d3_layout_pieSortByValue, startAngle = 0, endAngle = τ;
function pie(data) {
var values = data.map(function(d, i) {
return +value.call(pie, d, i);
@@ -20696,7 +20697,7 @@ d3 = function() {
function d3_scale_ordinal(domain, ranger) {
var index, range, rangeBand;
function scale(x) {
- return range[((index.get(x) || index.set(x, domain.push(x))) - 1) % range.length];
+ return range[((index.get(x) || ranger.t === "range" && index.set(x, domain.push(x))) - 1) % range.length];
}
function steps(start, step) {
return d3.range(domain.length).map(function(i) {
@@ -20907,6 +20908,7 @@ d3 = function() {
};
return identity;
}
+ d3.svg = {};
d3.svg.arc = function() {
var innerRadius = d3_svg_arcInnerRadius, outerRadius = d3_svg_arcOuterRadius, startAngle = d3_svg_arcStartAngle, endAngle = d3_svg_arcEndAngle;
function arc() {
@@ -20940,7 +20942,7 @@ d3 = function() {
};
return arc;
};
- var d3_svg_arcOffset = -π / 2, d3_svg_arcMax = 2 * π - 1e-6;
+ var d3_svg_arcOffset = -halfπ, d3_svg_arcMax = τ - ε;
function d3_svg_arcInnerRadius(d) {
return d.innerRadius;
}
@@ -20953,6 +20955,255 @@ d3 = function() {
function d3_svg_arcEndAngle(d) {
return d.endAngle;
}
+ function d3_svg_line(projection) {
+ var x = d3_geom_pointX, y = d3_geom_pointY, defined = d3_true, interpolate = d3_svg_lineLinear, interpolateKey = interpolate.key, tension = .7;
+ function line(data) {
+ var segments = [], points = [], i = -1, n = data.length, d, fx = d3_functor(x), fy = d3_functor(y);
+ function segment() {
+ segments.push("M", interpolate(projection(points), tension));
+ }
+ while (++i < n) {
+ if (defined.call(this, d = data[i], i)) {
+ points.push([ +fx.call(this, d, i), +fy.call(this, d, i) ]);
+ } else if (points.length) {
+ segment();
+ points = [];
+ }
+ }
+ if (points.length) segment();
+ return segments.length ? segments.join("") : null;
+ }
+ line.x = function(_) {
+ if (!arguments.length) return x;
+ x = _;
+ return line;
+ };
+ line.y = function(_) {
+ if (!arguments.length) return y;
+ y = _;
+ return line;
+ };
+ line.defined = function(_) {
+ if (!arguments.length) return defined;
+ defined = _;
+ return line;
+ };
+ line.interpolate = function(_) {
+ if (!arguments.length) return interpolateKey;
+ if (typeof _ === "function") interpolateKey = interpolate = _; else interpolateKey = (interpolate = d3_svg_lineInterpolators.get(_) || d3_svg_lineLinear).key;
+ return line;
+ };
+ line.tension = function(_) {
+ if (!arguments.length) return tension;
+ tension = _;
+ return line;
+ };
+ return line;
+ }
+ d3.svg.line = function() {
+ return d3_svg_line(d3_identity);
+ };
+ var d3_svg_lineInterpolators = d3.map({
+ linear: d3_svg_lineLinear,
+ "linear-closed": d3_svg_lineLinearClosed,
+ step: d3_svg_lineStep,
+ "step-before": d3_svg_lineStepBefore,
+ "step-after": d3_svg_lineStepAfter,
+ basis: d3_svg_lineBasis,
+ "basis-open": d3_svg_lineBasisOpen,
+ "basis-closed": d3_svg_lineBasisClosed,
+ bundle: d3_svg_lineBundle,
+ cardinal: d3_svg_lineCardinal,
+ "cardinal-open": d3_svg_lineCardinalOpen,
+ "cardinal-closed": d3_svg_lineCardinalClosed,
+ monotone: d3_svg_lineMonotone
+ });
+ d3_svg_lineInterpolators.forEach(function(key, value) {
+ value.key = key;
+ value.closed = /-closed$/.test(key);
+ });
+ function d3_svg_lineLinear(points) {
+ return points.join("L");
+ }
+ function d3_svg_lineLinearClosed(points) {
+ return d3_svg_lineLinear(points) + "Z";
+ }
+ function d3_svg_lineStep(points) {
+ var i = 0, n = points.length, p = points[0], path = [ p[0], ",", p[1] ];
+ while (++i < n) path.push("H", (p[0] + (p = points[i])[0]) / 2, "V", p[1]);
+ if (n > 1) path.push("H", p[0]);
+ return path.join("");
+ }
+ function d3_svg_lineStepBefore(points) {
+ var i = 0, n = points.length, p = points[0], path = [ p[0], ",", p[1] ];
+ while (++i < n) path.push("V", (p = points[i])[1], "H", p[0]);
+ return path.join("");
+ }
+ function d3_svg_lineStepAfter(points) {
+ var i = 0, n = points.length, p = points[0], path = [ p[0], ",", p[1] ];
+ while (++i < n) path.push("H", (p = points[i])[0], "V", p[1]);
+ return path.join("");
+ }
+ function d3_svg_lineCardinalOpen(points, tension) {
+ return points.length < 4 ? d3_svg_lineLinear(points) : points[1] + d3_svg_lineHermite(points.slice(1, points.length - 1), d3_svg_lineCardinalTangents(points, tension));
+ }
+ function d3_svg_lineCardinalClosed(points, tension) {
+ return points.length < 3 ? d3_svg_lineLinear(points) : points[0] + d3_svg_lineHermite((points.push(points[0]),
+ points), d3_svg_lineCardinalTangents([ points[points.length - 2] ].concat(points, [ points[1] ]), tension));
+ }
+ function d3_svg_lineCardinal(points, tension) {
+ return points.length < 3 ? d3_svg_lineLinear(points) : points[0] + d3_svg_lineHermite(points, d3_svg_lineCardinalTangents(points, tension));
+ }
+ function d3_svg_lineHermite(points, tangents) {
+ if (tangents.length < 1 || points.length != tangents.length && points.length != tangents.length + 2) {
+ return d3_svg_lineLinear(points);
+ }
+ var quad = points.length != tangents.length, path = "", p0 = points[0], p = points[1], t0 = tangents[0], t = t0, pi = 1;
+ if (quad) {
+ path += "Q" + (p[0] - t0[0] * 2 / 3) + "," + (p[1] - t0[1] * 2 / 3) + "," + p[0] + "," + p[1];
+ p0 = points[1];
+ pi = 2;
+ }
+ if (tangents.length > 1) {
+ t = tangents[1];
+ p = points[pi];
+ pi++;
+ path += "C" + (p0[0] + t0[0]) + "," + (p0[1] + t0[1]) + "," + (p[0] - t[0]) + "," + (p[1] - t[1]) + "," + p[0] + "," + p[1];
+ for (var i = 2; i < tangents.length; i++, pi++) {
+ p = points[pi];
+ t = tangents[i];
+ path += "S" + (p[0] - t[0]) + "," + (p[1] - t[1]) + "," + p[0] + "," + p[1];
+ }
+ }
+ if (quad) {
+ var lp = points[pi];
+ path += "Q" + (p[0] + t[0] * 2 / 3) + "," + (p[1] + t[1] * 2 / 3) + "," + lp[0] + "," + lp[1];
+ }
+ return path;
+ }
+ function d3_svg_lineCardinalTangents(points, tension) {
+ var tangents = [], a = (1 - tension) / 2, p0, p1 = points[0], p2 = points[1], i = 1, n = points.length;
+ while (++i < n) {
+ p0 = p1;
+ p1 = p2;
+ p2 = points[i];
+ tangents.push([ a * (p2[0] - p0[0]), a * (p2[1] - p0[1]) ]);
+ }
+ return tangents;
+ }
+ function d3_svg_lineBasis(points) {
+ if (points.length < 3) return d3_svg_lineLinear(points);
+ var i = 1, n = points.length, pi = points[0], x0 = pi[0], y0 = pi[1], px = [ x0, x0, x0, (pi = points[1])[0] ], py = [ y0, y0, y0, pi[1] ], path = [ x0, ",", y0, "L", d3_svg_lineDot4(d3_svg_lineBasisBezier3, px), ",", d3_svg_lineDot4(d3_svg_lineBasisBezier3, py) ];
+ points.push(points[n - 1]);
+ while (++i <= n) {
+ pi = points[i];
+ px.shift();
+ px.push(pi[0]);
+ py.shift();
+ py.push(pi[1]);
+ d3_svg_lineBasisBezier(path, px, py);
+ }
+ points.pop();
+ path.push("L", pi);
+ return path.join("");
+ }
+ function d3_svg_lineBasisOpen(points) {
+ if (points.length < 4) return d3_svg_lineLinear(points);
+ var path = [], i = -1, n = points.length, pi, px = [ 0 ], py = [ 0 ];
+ while (++i < 3) {
+ pi = points[i];
+ px.push(pi[0]);
+ py.push(pi[1]);
+ }
+ path.push(d3_svg_lineDot4(d3_svg_lineBasisBezier3, px) + "," + d3_svg_lineDot4(d3_svg_lineBasisBezier3, py));
+ --i;
+ while (++i < n) {
+ pi = points[i];
+ px.shift();
+ px.push(pi[0]);
+ py.shift();
+ py.push(pi[1]);
+ d3_svg_lineBasisBezier(path, px, py);
+ }
+ return path.join("");
+ }
+ function d3_svg_lineBasisClosed(points) {
+ var path, i = -1, n = points.length, m = n + 4, pi, px = [], py = [];
+ while (++i < 4) {
+ pi = points[i % n];
+ px.push(pi[0]);
+ py.push(pi[1]);
+ }
+ path = [ d3_svg_lineDot4(d3_svg_lineBasisBezier3, px), ",", d3_svg_lineDot4(d3_svg_lineBasisBezier3, py) ];
+ --i;
+ while (++i < m) {
+ pi = points[i % n];
+ px.shift();
+ px.push(pi[0]);
+ py.shift();
+ py.push(pi[1]);
+ d3_svg_lineBasisBezier(path, px, py);
+ }
+ return path.join("");
+ }
+ function d3_svg_lineBundle(points, tension) {
+ var n = points.length - 1;
+ if (n) {
+ var x0 = points[0][0], y0 = points[0][1], dx = points[n][0] - x0, dy = points[n][1] - y0, i = -1, p, t;
+ while (++i <= n) {
+ p = points[i];
+ t = i / n;
+ p[0] = tension * p[0] + (1 - tension) * (x0 + t * dx);
+ p[1] = tension * p[1] + (1 - tension) * (y0 + t * dy);
+ }
+ }
+ return d3_svg_lineBasis(points);
+ }
+ function d3_svg_lineDot4(a, b) {
+ return a[0] * b[0] + a[1] * b[1] + a[2] * b[2] + a[3] * b[3];
+ }
+ var d3_svg_lineBasisBezier1 = [ 0, 2 / 3, 1 / 3, 0 ], d3_svg_lineBasisBezier2 = [ 0, 1 / 3, 2 / 3, 0 ], d3_svg_lineBasisBezier3 = [ 0, 1 / 6, 2 / 3, 1 / 6 ];
+ function d3_svg_lineBasisBezier(path, x, y) {
+ path.push("C", d3_svg_lineDot4(d3_svg_lineBasisBezier1, x), ",", d3_svg_lineDot4(d3_svg_lineBasisBezier1, y), ",", d3_svg_lineDot4(d3_svg_lineBasisBezier2, x), ",", d3_svg_lineDot4(d3_svg_lineBasisBezier2, y), ",", d3_svg_lineDot4(d3_svg_lineBasisBezier3, x), ",", d3_svg_lineDot4(d3_svg_lineBasisBezier3, y));
+ }
+ function d3_svg_lineSlope(p0, p1) {
+ return (p1[1] - p0[1]) / (p1[0] - p0[0]);
+ }
+ function d3_svg_lineFiniteDifferences(points) {
+ var i = 0, j = points.length - 1, m = [], p0 = points[0], p1 = points[1], d = m[0] = d3_svg_lineSlope(p0, p1);
+ while (++i < j) {
+ m[i] = (d + (d = d3_svg_lineSlope(p0 = p1, p1 = points[i + 1]))) / 2;
+ }
+ m[i] = d;
+ return m;
+ }
+ function d3_svg_lineMonotoneTangents(points) {
+ var tangents = [], d, a, b, s, m = d3_svg_lineFiniteDifferences(points), i = -1, j = points.length - 1;
+ while (++i < j) {
+ d = d3_svg_lineSlope(points[i], points[i + 1]);
+ if (abs(d) < ε) {
+ m[i] = m[i + 1] = 0;
+ } else {
+ a = m[i] / d;
+ b = m[i + 1] / d;
+ s = a * a + b * b;
+ if (s > 9) {
+ s = d * 3 / Math.sqrt(s);
+ m[i] = s * a;
+ m[i + 1] = s * b;
+ }
+ }
+ }
+ i = -1;
+ while (++i <= j) {
+ s = (points[Math.min(j, i + 1)][0] - points[Math.max(0, i - 1)][0]) / (6 * (1 + m[i] * m[i]));
+ tangents.push([ s || 0, m[i] * s || 0 ]);
+ }
+ return tangents;
+ }
+ function d3_svg_lineMonotone(points) {
+ return points.length < 3 ? d3_svg_lineLinear(points) : points[0] + d3_svg_lineHermite(points, d3_svg_lineMonotoneTangents(points));
+ }
d3.svg.line.radial = function() {
var line = d3_svg_line(d3_svg_lineRadial);
line.radius = line.x, delete line.x;
@@ -20971,7 +21222,7 @@ d3 = function() {
return points;
}
function d3_svg_area(projection) {
- var x0 = d3_svg_lineX, x1 = d3_svg_lineX, y0 = 0, y1 = d3_svg_lineY, defined = d3_true, interpolate = d3_svg_lineLinear, interpolateKey = interpolate.key, interpolateReverse = interpolate, L = "L", tension = .7;
+ var x0 = d3_geom_pointX, x1 = d3_geom_pointX, y0 = 0, y1 = d3_geom_pointY, defined = d3_true, interpolate = d3_svg_lineLinear, interpolateKey = interpolate.key, interpolateReverse = interpolate, L = "L", tension = .7;
function area(data) {
var segments = [], points0 = [], points1 = [], i = -1, n = data.length, d, fx0 = d3_functor(x0), fy0 = d3_functor(y0), fx1 = x0 === x1 ? function() {
return x;
@@ -21458,9 +21709,10 @@ d3 = function() {
};
++lock.count;
d3.timer(function(elapsed) {
- var d = node.__data__, ease = transition.ease, delay = transition.delay, duration = transition.duration, tweened = [];
- if (delay <= elapsed) return start(elapsed);
- d3_timer_replace(start, delay, time);
+ var d = node.__data__, ease = transition.ease, delay = transition.delay, duration = transition.duration, timer = d3_timer_active, tweened = [];
+ timer.t = delay + time;
+ if (delay <= elapsed) return start(elapsed - delay);
+ timer.c = start;
function start(elapsed) {
if (lock.active > id) return stop();
lock.active = id;
@@ -21470,12 +21722,14 @@ d3 = function() {
tweened.push(value);
}
});
- if (tick(elapsed)) return 1;
- d3_timer_replace(tick, 0, time);
+ d3.timer(function() {
+ timer.c = tick(elapsed || 1) ? d3_true : tick;
+ return 1;
+ }, 0, time);
}
function tick(elapsed) {
if (lock.active !== id) return stop();
- var t = (elapsed - delay) / duration, e = ease(t), n = tweened.length;
+ var t = elapsed / duration, e = ease(t), n = tweened.length;
while (n > 0) {
tweened[--n].call(node, e);
}
@@ -21496,11 +21750,10 @@ d3 = function() {
function axis(g) {
g.each(function() {
var g = d3.select(this);
- var ticks = tickValues == null ? scale.ticks ? scale.ticks.apply(scale, tickArguments_) : scale.domain() : tickValues, tickFormat = tickFormat_ == null ? scale.tickFormat ? scale.tickFormat.apply(scale, tickArguments_) : d3_identity : tickFormat_, tick = g.selectAll(".tick").data(ticks, d3_identity), tickEnter = tick.enter().insert("g", ".domain").attr("class", "tick").style("opacity", 1e-6), tickExit = d3.transition(tick.exit()).style("opacity", 1e-6).remove(), tickUpdate = d3.transition(tick).style("opacity", 1), tickTransform;
- var range = d3_scaleRange(scale), path = g.selectAll(".domain").data([ 0 ]), pathUpdate = (path.enter().append("path").attr("class", "domain"),
+ var scale0 = this.__chart__ || scale, scale1 = this.__chart__ = scale.copy();
+ var ticks = tickValues == null ? scale1.ticks ? scale1.ticks.apply(scale1, tickArguments_) : scale1.domain() : tickValues, tickFormat = tickFormat_ == null ? scale1.tickFormat ? scale1.tickFormat.apply(scale1, tickArguments_) : d3_identity : tickFormat_, tick = g.selectAll(".tick").data(ticks, scale1), tickEnter = tick.enter().insert("g", ".domain").attr("class", "tick").style("opacity", ε), tickExit = d3.transition(tick.exit()).style("opacity", ε).remove(), tickUpdate = d3.transition(tick).style("opacity", 1), tickTransform;
+ var range = d3_scaleRange(scale1), path = g.selectAll(".domain").data([ 0 ]), pathUpdate = (path.enter().append("path").attr("class", "domain"),
d3.transition(path));
- var scale1 = scale.copy(), scale0 = this.__chart__ || scale1;
- this.__chart__ = scale1;
tickEnter.append("line");
tickEnter.append("text");
var lineEnter = tickEnter.select("line"), lineUpdate = tickUpdate.select("line"), text = tick.select("text").text(tickFormat), textEnter = tickEnter.select("text"), textUpdate = tickUpdate.select("text");
@@ -21553,7 +21806,7 @@ d3 = function() {
break;
}
}
- if (scale.rangeBand) {
+ if (scale1.rangeBand) {
var dx = scale1.rangeBand() / 2, x = function(d) {
return scale1(d) + dx;
};
@@ -22376,7 +22629,7 @@ d3 = function() {
pm: 1
});
function d3_time_zone(d) {
- var z = d.getTimezoneOffset(), zs = z > 0 ? "-" : "+", zh = ~~(Math.abs(z) / 60), zm = Math.abs(z) % 60;
+ var z = d.getTimezoneOffset(), zs = z > 0 ? "-" : "+", zh = ~~(abs(z) / 60), zm = abs(z) % 60;
return zs + d3_time_formatPad(zh, "0", 2) + d3_time_formatPad(zm, "0", 2);
}
function d3_time_parseLiteralPercent(date, string, i) {
@@ -22498,7 +22751,7 @@ d3 = function() {
range: interval
}, skip ];
if (method) interval = method[0], skip = method[1];
- return interval.range(extent[0], d3_time_scaleDate(+extent[1] + 1), skip);
+ return interval.range(extent[0], d3_time_scaleDate(+extent[1] + 1), skip < 1 ? 1 : skip);
};
scale.tickFormat = function() {
return format;
diff --git a/diamondash/widgets/graph/tests/js/views.test.js b/diamondash/widgets/graph/tests/js/views.test.js
index a1d3ba0..c3b8ff4 100644
--- a/diamondash/widgets/graph/tests/js/views.test.js
+++ b/diamondash/widgets/graph/tests/js/views.test.js
@@ -421,7 +421,8 @@ describe("diamondash.widgets.graph", function() {
it("should draw its axis", function() {
assert.equal(
graph.$('.axis').text(),
- '01-01 00:00');
+ ['01-01 00:00',
+ '01-01 00:00'].join(''));
graph.render();
@hodgestar
Copy link

👍

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment