|
// https://github.com/d3/d3-geo-polygon Version 1.3.0. Copyright 2018 Mike Bostock. |
|
(function (global, factory) { |
|
typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports, require('d3-array'), require('d3-geo'), require('d3-geo-projection')) : |
|
typeof define === 'function' && define.amd ? define(['exports', 'd3-array', 'd3-geo', 'd3-geo-projection'], factory) : |
|
(factory((global.d3 = global.d3 || {}),global.d3,global.d3,global.d3)); |
|
}(this, (function (exports,d3Array,d3Geo,d3GeoProjection) { 'use strict'; |
|
|
|
function noop() {} |
|
|
|
var clipBuffer = function() { |
|
var lines = [], |
|
line; |
|
return { |
|
point: function(x, y, i, t) { |
|
var point = [x, y]; |
|
// when called by clipPolygon, store index and t |
|
if (arguments.length > 2) { point.index = i; point.t = t; } |
|
line.push(point); |
|
}, |
|
lineStart: function() { |
|
lines.push(line = []); |
|
}, |
|
lineEnd: noop, |
|
rejoin: function() { |
|
if (lines.length > 1) lines.push(lines.pop().concat(lines.shift())); |
|
}, |
|
result: function() { |
|
var result = lines; |
|
lines = []; |
|
line = null; |
|
return result; |
|
} |
|
}; |
|
}; |
|
|
|
var epsilon = 1e-6; |
|
var epsilon2 = 1e-12; |
|
var pi = Math.PI; |
|
var halfPi = pi / 2; |
|
var quarterPi = pi / 4; |
|
var tau = pi * 2; |
|
|
|
var degrees = 180 / pi; |
|
var radians = pi / 180; |
|
|
|
var abs = Math.abs; |
|
|
|
var atan2 = Math.atan2; |
|
var cos = Math.cos; |
|
|
|
|
|
|
|
|
|
var max = Math.max; |
|
var min = Math.min; |
|
|
|
var sin = Math.sin; |
|
var sign = Math.sign || function(x) { return x > 0 ? 1 : x < 0 ? -1 : 0; }; |
|
var sqrt = Math.sqrt; |
|
|
|
|
|
function acos(x) { |
|
return x > 1 ? 0 : x < -1 ? pi : Math.acos(x); |
|
} |
|
|
|
function asin(x) { |
|
return x > 1 ? halfPi : x < -1 ? -halfPi : Math.asin(x); |
|
} |
|
|
|
var pointEqual = function(a, b) { |
|
return abs(a[0] - b[0]) < epsilon && abs(a[1] - b[1]) < epsilon; |
|
}; |
|
|
|
function Intersection(point, points, other, entry) { |
|
this.x = point; |
|
this.z = points; |
|
this.o = other; // another intersection |
|
this.e = entry; // is an entry? |
|
this.v = false; // visited |
|
this.n = this.p = null; // next & previous |
|
} |
|
|
|
// A generalized polygon clipping algorithm: given a polygon that has been cut |
|
// into its visible line segments, and rejoins the segments by interpolating |
|
// along the clip edge. |
|
var clipRejoin = function(segments, compareIntersection, startInside, interpolate, stream) { |
|
var subject = [], |
|
clip = [], |
|
i, |
|
n; |
|
|
|
segments.forEach(function(segment) { |
|
if ((n = segment.length - 1) <= 0) return; |
|
var n, p0 = segment[0], p1 = segment[n], x; |
|
|
|
// If the first and last points of a segment are coincident, then treat as a |
|
// closed ring. TODO if all rings are closed, then the winding order of the |
|
// exterior ring should be checked. |
|
if (pointEqual(p0, p1)) { |
|
stream.lineStart(); |
|
for (i = 0; i < n; ++i) stream.point((p0 = segment[i])[0], p0[1]); |
|
stream.lineEnd(); |
|
return; |
|
} |
|
|
|
subject.push(x = new Intersection(p0, segment, null, true)); |
|
clip.push(x.o = new Intersection(p0, null, x, false)); |
|
subject.push(x = new Intersection(p1, segment, null, false)); |
|
clip.push(x.o = new Intersection(p1, null, x, true)); |
|
}); |
|
|
|
if (!subject.length) return; |
|
|
|
clip.sort(compareIntersection); |
|
link(subject); |
|
link(clip); |
|
|
|
for (i = 0, n = clip.length; i < n; ++i) { |
|
clip[i].e = startInside = !startInside; |
|
} |
|
|
|
var start = subject[0], |
|
points, |
|
point; |
|
|
|
while (1) { |
|
// Find first unvisited intersection. |
|
var current = start, |
|
isSubject = true; |
|
while (current.v) if ((current = current.n) === start) return; |
|
points = current.z; |
|
stream.lineStart(); |
|
do { |
|
current.v = current.o.v = true; |
|
if (current.e) { |
|
if (isSubject) { |
|
for (i = 0, n = points.length; i < n; ++i) stream.point((point = points[i])[0], point[1]); |
|
} else { |
|
interpolate(current.x, current.n.x, 1, stream); |
|
} |
|
current = current.n; |
|
} else { |
|
if (isSubject) { |
|
points = current.p.z; |
|
for (i = points.length - 1; i >= 0; --i) stream.point((point = points[i])[0], point[1]); |
|
} else { |
|
interpolate(current.x, current.p.x, -1, stream); |
|
} |
|
current = current.p; |
|
} |
|
current = current.o; |
|
points = current.z; |
|
isSubject = !isSubject; |
|
} while (!current.v); |
|
stream.lineEnd(); |
|
} |
|
}; |
|
|
|
function link(array) { |
|
if (!(n = array.length)) return; |
|
var n, |
|
i = 0, |
|
a = array[0], |
|
b; |
|
while (++i < n) { |
|
a.n = b = array[i]; |
|
b.p = a; |
|
a = b; |
|
} |
|
a.n = b = array[0]; |
|
b.p = a; |
|
} |
|
|
|
// Adds floating point numbers with twice the normal precision. |
|
// Reference: J. R. Shewchuk, Adaptive Precision Floating-Point Arithmetic and |
|
// Fast Robust Geometric Predicates, Discrete & Computational Geometry 18(3) |
|
// 305–363 (1997). |
|
// Code adapted from GeographicLib by Charles F. F. Karney, |
|
// http://geographiclib.sourceforge.net/ |
|
|
|
var adder = function() { |
|
return new Adder; |
|
}; |
|
|
|
function Adder() { |
|
this.reset(); |
|
} |
|
|
|
Adder.prototype = { |
|
constructor: Adder, |
|
reset: function() { |
|
this.s = // rounded value |
|
this.t = 0; // exact error |
|
}, |
|
add: function(y) { |
|
add(temp, y, this.t); |
|
add(this, temp.s, this.s); |
|
if (this.s) this.t += temp.t; |
|
else this.s = temp.t; |
|
}, |
|
valueOf: function() { |
|
return this.s; |
|
} |
|
}; |
|
|
|
var temp = new Adder; |
|
|
|
function add(adder, a, b) { |
|
var x = adder.s = a + b, |
|
bv = x - a, |
|
av = x - bv; |
|
adder.t = (a - av) + (b - bv); |
|
} |
|
|
|
function spherical(cartesian) { |
|
return [atan2(cartesian[1], cartesian[0]), asin(cartesian[2])]; |
|
} |
|
|
|
function cartesian(spherical) { |
|
var lambda = spherical[0], phi = spherical[1], cosPhi = cos(phi); |
|
return [cosPhi * cos(lambda), cosPhi * sin(lambda), sin(phi)]; |
|
} |
|
|
|
function cartesianDot(a, b) { |
|
return a[0] * b[0] + a[1] * b[1] + a[2] * b[2]; |
|
} |
|
|
|
function cartesianCross(a, b) { |
|
return [a[1] * b[2] - a[2] * b[1], a[2] * b[0] - a[0] * b[2], a[0] * b[1] - a[1] * b[0]]; |
|
} |
|
|
|
// TODO return a |
|
|
|
|
|
|
|
|
|
// TODO return d |
|
function cartesianNormalizeInPlace(d) { |
|
var l = sqrt(d[0] * d[0] + d[1] * d[1] + d[2] * d[2]); |
|
d[0] /= l, d[1] /= l, d[2] /= l; |
|
} |
|
|
|
function cartesianEqual(a, b) { |
|
var dx = b[0] - a[0], |
|
dy = b[1] - a[1], |
|
dz = b[2] - a[2]; |
|
return dx * dx + dy * dy + dz * dz < epsilon2 * epsilon2; |
|
} |
|
|
|
var sum = adder(); |
|
|
|
var polygonContains = function(polygon, point) { |
|
var lambda = point[0], |
|
phi = point[1], |
|
normal = [sin(lambda), -cos(lambda), 0], |
|
angle = 0, |
|
winding = 0; |
|
|
|
sum.reset(); |
|
|
|
for (var i = 0, n = polygon.length; i < n; ++i) { |
|
if (!(m = (ring = polygon[i]).length)) continue; |
|
var ring, |
|
m, |
|
point0 = ring[m - 1], |
|
lambda0 = point0[0], |
|
phi0 = point0[1] / 2 + quarterPi, |
|
sinPhi0 = sin(phi0), |
|
cosPhi0 = cos(phi0); |
|
|
|
for (var j = 0; j < m; ++j, lambda0 = lambda1, sinPhi0 = sinPhi1, cosPhi0 = cosPhi1, point0 = point1) { |
|
var point1 = ring[j], |
|
lambda1 = point1[0], |
|
phi1 = point1[1] / 2 + quarterPi, |
|
sinPhi1 = sin(phi1), |
|
cosPhi1 = cos(phi1), |
|
delta = lambda1 - lambda0, |
|
sign$$1 = delta >= 0 ? 1 : -1, |
|
absDelta = sign$$1 * delta, |
|
antimeridian = absDelta > pi, |
|
k = sinPhi0 * sinPhi1; |
|
|
|
sum.add(atan2(k * sign$$1 * sin(absDelta), cosPhi0 * cosPhi1 + k * cos(absDelta))); |
|
angle += antimeridian ? delta + sign$$1 * tau : delta; |
|
|
|
// Are the longitudes either side of the point’s meridian (lambda), |
|
// and are the latitudes smaller than the parallel (phi)? |
|
if (antimeridian ^ lambda0 >= lambda ^ lambda1 >= lambda) { |
|
var arc = cartesianCross(cartesian(point0), cartesian(point1)); |
|
cartesianNormalizeInPlace(arc); |
|
var intersection = cartesianCross(normal, arc); |
|
cartesianNormalizeInPlace(intersection); |
|
var phiArc = (antimeridian ^ delta >= 0 ? -1 : 1) * asin(intersection[2]); |
|
if (phi > phiArc || phi === phiArc && (arc[0] || arc[1])) { |
|
winding += antimeridian ^ delta >= 0 ? 1 : -1; |
|
} |
|
} |
|
} |
|
} |
|
|
|
// First, determine whether the South pole is inside or outside: |
|
// |
|
// It is inside if: |
|
// * the polygon winds around it in a clockwise direction. |
|
// * the polygon does not (cumulatively) wind around it, but has a negative |
|
// (counter-clockwise) area. |
|
// |
|
// Second, count the (signed) number of times a segment crosses a lambda |
|
// from the point to the South pole. If it is zero, then the point is the |
|
// same side as the South pole. |
|
|
|
return (angle < -epsilon || angle < epsilon && sum < -epsilon) ^ (winding & 1); |
|
}; |
|
|
|
var clip = function(pointVisible, clipLine, interpolate, start, sort) { |
|
if (typeof sort === "undefined") sort = compareIntersection; |
|
|
|
return function(sink) { |
|
var line = clipLine(sink), |
|
ringBuffer = clipBuffer(), |
|
ringSink = clipLine(ringBuffer), |
|
polygonStarted = false, |
|
polygon, |
|
segments, |
|
ring; |
|
|
|
var clip = { |
|
point: point, |
|
lineStart: lineStart, |
|
lineEnd: lineEnd, |
|
polygonStart: function() { |
|
clip.point = pointRing; |
|
clip.lineStart = ringStart; |
|
clip.lineEnd = ringEnd; |
|
segments = []; |
|
polygon = []; |
|
}, |
|
polygonEnd: function() { |
|
clip.point = point; |
|
clip.lineStart = lineStart; |
|
clip.lineEnd = lineEnd; |
|
segments = d3Array.merge(segments); |
|
var startInside = polygonContains(polygon, start); |
|
if (segments.length) { |
|
if (!polygonStarted) sink.polygonStart(), polygonStarted = true; |
|
clipRejoin(segments, sort, startInside, interpolate, sink); |
|
} else if (startInside) { |
|
if (!polygonStarted) sink.polygonStart(), polygonStarted = true; |
|
sink.lineStart(); |
|
interpolate(null, null, 1, sink); |
|
sink.lineEnd(); |
|
} |
|
if (polygonStarted) sink.polygonEnd(), polygonStarted = false; |
|
segments = polygon = null; |
|
}, |
|
sphere: function() { |
|
sink.polygonStart(); |
|
sink.lineStart(); |
|
interpolate(null, null, 1, sink); |
|
sink.lineEnd(); |
|
sink.polygonEnd(); |
|
} |
|
}; |
|
|
|
function point(lambda, phi) { |
|
if (pointVisible(lambda, phi)) sink.point(lambda, phi); |
|
} |
|
|
|
function pointLine(lambda, phi) { |
|
line.point(lambda, phi); |
|
} |
|
|
|
function lineStart() { |
|
clip.point = pointLine; |
|
line.lineStart(); |
|
} |
|
|
|
function lineEnd() { |
|
clip.point = point; |
|
line.lineEnd(); |
|
} |
|
|
|
function pointRing(lambda, phi, close) { |
|
ring.push([lambda, phi]); |
|
ringSink.point(lambda, phi, close); |
|
} |
|
|
|
function ringStart() { |
|
ringSink.lineStart(); |
|
ring = []; |
|
} |
|
|
|
function ringEnd() { |
|
pointRing(ring[0][0], ring[0][1], true); |
|
ringSink.lineEnd(); |
|
|
|
var clean = ringSink.clean(), |
|
ringSegments = ringBuffer.result(), |
|
i, n = ringSegments.length, m, |
|
segment, |
|
point; |
|
|
|
ring.pop(); |
|
polygon.push(ring); |
|
ring = null; |
|
|
|
if (!n) return; |
|
|
|
// No intersections. |
|
if (clean & 1) { |
|
segment = ringSegments[0]; |
|
if ((m = segment.length - 1) > 0) { |
|
if (!polygonStarted) sink.polygonStart(), polygonStarted = true; |
|
sink.lineStart(); |
|
for (i = 0; i < m; ++i) sink.point((point = segment[i])[0], point[1]); |
|
sink.lineEnd(); |
|
} |
|
return; |
|
} |
|
|
|
// Rejoin connected segments. |
|
// TODO reuse ringBuffer.rejoin()? |
|
if (n > 1 && clean & 2) ringSegments.push(ringSegments.pop().concat(ringSegments.shift())); |
|
|
|
segments.push(ringSegments.filter(validSegment)); |
|
} |
|
|
|
return clip; |
|
}; |
|
}; |
|
|
|
function validSegment(segment) { |
|
return segment.length > 1; |
|
} |
|
|
|
// Intersections are sorted along the clip edge. For both antimeridian cutting |
|
// and circle clipping, the same comparison is used. |
|
function compareIntersection(a, b) { |
|
return ((a = a.x)[0] < 0 ? a[1] - halfPi - epsilon : halfPi - a[1]) |
|
- ((b = b.x)[0] < 0 ? b[1] - halfPi - epsilon : halfPi - b[1]); |
|
} |
|
|
|
function intersectSegment(from, to) { |
|
this.from = from, this.to = to; |
|
this.normal = cartesianCross(from, to); |
|
this.fromNormal = cartesianCross(this.normal, from); |
|
this.toNormal = cartesianCross(this.normal, to); |
|
} |
|
|
|
// >> here a and b are segments processed by intersectSegment |
|
function intersect(a, b) { |
|
var axb = cartesianCross(a.normal, b.normal); |
|
cartesianNormalizeInPlace(axb); |
|
var a0 = cartesianDot(axb, a.fromNormal), |
|
a1 = cartesianDot(axb, a.toNormal), |
|
b0 = cartesianDot(axb, b.fromNormal), |
|
b1 = cartesianDot(axb, b.toNormal); |
|
|
|
if (a0 > 0 && a1 < 0 && b0 > 0 && b1 < 0) { |
|
return axb; |
|
} |
|
|
|
if (a0 < 0 && a1 > 0 && b0 < 0 && b1 > 0) { |
|
axb[0] = -axb[0], axb[1] = -axb[1], axb[2] = -axb[2]; |
|
return axb; |
|
} |
|
} |
|
|
|
function intersectPointOnLine(p, a) { |
|
var a0 = cartesianDot(p, a.fromNormal), |
|
a1 = cartesianDot(p, a.toNormal); |
|
p = cartesianDot(p, a.normal); |
|
|
|
return abs(p) < epsilon2 && (a0 > -epsilon2 && a1 < epsilon2 || a0 < epsilon2 && a1 > -epsilon2); |
|
} |
|
|
|
var intersectCoincident = {}; |
|
|
|
|
|
// todo: publicly expose d3.geoIntersect(segment0, segment1) ?? |
|
// cf. https://github.com/d3/d3/commit/3dbdf87974dc2588c29db0533a8500ccddb25daa#diff-65daf69cea7d039d72c1eca7c13326b0 |
|
|
|
var clipNone = function(stream) { return stream; }; |
|
|
|
// clipPolygon |
|
var clipPolygon = function (p) { |
|
var segments = []; |
|
|
|
if (p.type != "Polygon") return clipNone; // todo: MultiPolygon? |
|
|
|
var polygon = p.coordinates.map(function(ring) { |
|
var c, c0; |
|
ring = ring.map(function(point, i) { |
|
c = cartesian(point = [point[0] * radians, point[1] * radians]); |
|
if (i) segments.push(new intersectSegment(c0, c)); |
|
c0 = c; |
|
return point; |
|
}); |
|
ring.pop(); |
|
return ring; |
|
}); |
|
|
|
|
|
function visible(lambda, phi) { |
|
return polygonContains(polygon, [lambda, phi]); |
|
} |
|
|
|
function randsign(i,j) { |
|
return sign(sin(100 * i + j)); |
|
} |
|
|
|
function clipLine(stream) { |
|
var point0, |
|
lambda00, |
|
phi00, |
|
v00, |
|
v0, |
|
clean; |
|
return { |
|
lineStart: function() { |
|
point0 = null; |
|
clean = 1; |
|
}, |
|
point: function(lambda, phi, close) { |
|
if (cos(lambda) == -1) lambda -= sign(sin(lambda)) * 1e-5; // move away from -180/180 https://github.com/d3/d3-geo/pull/108#issuecomment-323798937 |
|
if (close) lambda = lambda00, phi = phi00; |
|
var point = cartesian([lambda, phi]), |
|
v = v0, |
|
intersection, |
|
i, j, s, t; |
|
if (point0) { |
|
var segment = new intersectSegment(point0, point), |
|
intersections = []; |
|
for (i = 0, j = 100; i < segments.length && j > 0; ++i) { |
|
s = segments[i]; |
|
intersection = intersect(segment, s); |
|
if (intersection) { |
|
if (intersection === intersectCoincident || |
|
cartesianEqual(intersection, point0) || cartesianEqual(intersection, point) || |
|
cartesianEqual(intersection, s.from) || cartesianEqual(intersection, s.to)) { |
|
t = 1e-4; |
|
lambda = (lambda + 3 * pi + randsign(i,j) * t) % (2 * pi) - pi; |
|
phi = min(pi / 2 - 1e-4, max(1e-4 - pi / 2, phi + randsign(i,j) * t)); |
|
segment = new intersectSegment(point0, point = cartesian([lambda, phi])); |
|
i = -1, --j; |
|
intersections.length = 0; |
|
continue; |
|
} |
|
var sph = spherical(intersection); |
|
intersection.distance = clipPolygonDistance(point0, intersection); |
|
intersection.index = i; |
|
intersection.t = clipPolygonDistance(s.from, intersection); |
|
intersection[0] = sph[0], intersection[1] = sph[1], intersection.pop(); |
|
intersections.push(intersection); |
|
} |
|
} |
|
if (intersections.length) { |
|
clean = 0; |
|
intersections.sort(function(a, b) { return a.distance - b.distance; }); |
|
for (i = 0; i < intersections.length; ++i) { |
|
intersection = intersections[i]; |
|
v = !v; |
|
if (v) { |
|
stream.lineStart(); |
|
stream.point(intersection[0], intersection[1], intersection.index, intersection.t); |
|
} else { |
|
stream.point(intersection[0], intersection[1], intersection.index, intersection.t); |
|
stream.lineEnd(); |
|
} |
|
} |
|
} |
|
if (v) stream.point(lambda, phi); |
|
} else { |
|
for (i = 0, j = 100; i < segments.length && j > 0; ++i) { |
|
s = segments[i]; |
|
if (intersectPointOnLine(point, s)) { |
|
t = 1e-4; |
|
lambda = (lambda + 3 * pi + randsign(i,j) * t) % (2 * pi) - pi; |
|
phi = min(pi / 2 - 1e-4, max(1e-4 - pi / 2, phi + randsign(i,j) * t)); |
|
point = cartesian([lambda, phi]); |
|
i = -1, --j; |
|
} |
|
} |
|
v00 = v = visible(lambda00 = lambda, phi00 = phi); |
|
if (v) stream.lineStart(), stream.point(lambda, phi); |
|
} |
|
point0 = point, v0 = v; |
|
}, |
|
lineEnd: function() { |
|
if (v0) stream.lineEnd(); |
|
}, |
|
// Rejoin first and last segments if there were intersections and the first |
|
// and last points were visible. |
|
clean: function() { |
|
return clean | ((v00 && v0) << 1); |
|
} |
|
}; |
|
} |
|
|
|
function interpolate(from, to, direction, stream) { |
|
if (from == null) { |
|
var n = polygon.length; |
|
polygon.forEach(function(ring, i) { |
|
ring.forEach(function(point) { stream.point(point[0], point[1]); }); |
|
if (i < n - 1) stream.lineEnd(), stream.lineStart(); |
|
}); |
|
} else if (from.index !== to.index && from.index != null && to.index != null) { |
|
for (var i = from.index; i !== to.index; i = (i + direction + segments.length) % segments.length) { |
|
var segment = segments[i], |
|
point = spherical(direction > 0 ? segment.to : segment.from); |
|
stream.point(point[0], point[1]); |
|
} |
|
} |
|
} |
|
|
|
var c = clip(visible, clipLine, interpolate, polygon[0][0], clipPolygonSort); |
|
|
|
c.polygon = function() { |
|
return { |
|
type: "Polygon", |
|
coordinates: polygon.map(function(e) { |
|
return e.map(function(d) { |
|
return [ d[0] * degrees, d[1] * degrees]; |
|
}); |
|
}) |
|
}; |
|
}; |
|
|
|
return c; |
|
}; |
|
|
|
function clipPolygonSort(a, b) { |
|
a = a.x, b = b.x; |
|
return a.index - b.index || a.t - b.t; |
|
} |
|
|
|
// Geodesic coordinates for two 3D points. |
|
function clipPolygonDistance(a, b) { |
|
var axb = cartesianCross(a, b); |
|
return atan2(sqrt(cartesianDot(axb, axb)), cartesianDot(a, b)); |
|
} |
|
|
|
var abs$1 = Math.abs; |
|
|
|
var atan2$1 = Math.atan2; |
|
|
|
var cos$1 = Math.cos; |
|
|
|
|
|
|
|
var max$1 = Math.max; |
|
var min$1 = Math.min; |
|
|
|
|
|
|
|
var sin$1 = Math.sin; |
|
|
|
|
|
var epsilon$1 = 1e-6; |
|
|
|
var pi$1 = Math.PI; |
|
var halfPi$1 = pi$1 / 2; |
|
|
|
|
|
var sqrt2 = sqrt$1(2); |
|
var sqrtPi = sqrt$1(pi$1); |
|
|
|
var degrees$1 = 180 / pi$1; |
|
var radians$1 = pi$1 / 180; |
|
|
|
|
|
|
|
function asin$1(x) { |
|
return x > 1 ? halfPi$1 : x < -1 ? -halfPi$1 : Math.asin(x); |
|
} |
|
|
|
|
|
|
|
function sqrt$1(x) { |
|
return x > 0 ? Math.sqrt(x) : 0; |
|
} |
|
|
|
// Note: 6-element arrays are used to denote the 3x3 affine transform matrix: |
|
// [a, b, c, |
|
// d, e, f, |
|
// 0, 0, 1] - this redundant row is left out. |
|
|
|
// Transform matrix for [a0, a1] -> [b0, b1]. |
|
var matrix = function(a, b) { |
|
var u = subtract(a[1], a[0]), |
|
v = subtract(b[1], b[0]), |
|
phi = angle(u, v), |
|
s = length(u) / length(v); |
|
|
|
return multiply([ |
|
1, 0, a[0][0], |
|
0, 1, a[0][1] |
|
], multiply([ |
|
s, 0, 0, |
|
0, s, 0 |
|
], multiply([ |
|
cos$1(phi), sin$1(phi), 0, |
|
-sin$1(phi), cos$1(phi), 0 |
|
], [ |
|
1, 0, -b[0][0], |
|
0, 1, -b[0][1] |
|
]))); |
|
}; |
|
|
|
// Inverts a transform matrix. |
|
function inverse(m) { |
|
var k = 1 / (m[0] * m[4] - m[1] * m[3]); |
|
return [ |
|
k * m[4], -k * m[1], k * (m[1] * m[5] - m[2] * m[4]), |
|
-k * m[3], k * m[0], k * (m[2] * m[3] - m[0] * m[5]) |
|
]; |
|
} |
|
|
|
// Multiplies two 3x2 matrices. |
|
function multiply(a, b) { |
|
return [ |
|
a[0] * b[0] + a[1] * b[3], |
|
a[0] * b[1] + a[1] * b[4], |
|
a[0] * b[2] + a[1] * b[5] + a[2], |
|
a[3] * b[0] + a[4] * b[3], |
|
a[3] * b[1] + a[4] * b[4], |
|
a[3] * b[2] + a[4] * b[5] + a[5] |
|
]; |
|
} |
|
|
|
// Subtracts 2D vectors. |
|
function subtract(a, b) { |
|
return [a[0] - b[0], a[1] - b[1]]; |
|
} |
|
|
|
// Magnitude of a 2D vector. |
|
function length(v) { |
|
return sqrt$1(v[0] * v[0] + v[1] * v[1]); |
|
} |
|
|
|
// Angle between two 2D vectors. |
|
function angle(a, b) { |
|
return atan2$1(a[0] * b[1] - a[1] * b[0], a[0] * b[0] + a[1] * b[1]); |
|
} |
|
|
|
// Creates a polyhedral projection. |
|
// * root: a spanning tree of polygon faces. Nodes are automatically |
|
// augmented with a transform matrix. |
|
// * face: a function that returns the appropriate node for a given {lambda, phi} |
|
// point (radians). |
|
// * r: rotation angle for final polyhedral net. Defaults to -30 degrees (for |
|
// butterflies). |
|
var polyhedral = function(root, face, r) { |
|
|
|
r = (r == null ? -30 : r) * radians$1; // TODO automate |
|
|
|
recurse(root, {transform: [ |
|
cos$1(r), sin$1(r), 0, |
|
-sin$1(r), cos$1(r), 0 |
|
]}); |
|
|
|
function recurse(node, parent) { |
|
node.edges = faceEdges(node.face); |
|
// Find shared edge. |
|
if (parent.face) { |
|
var shared = node.shared = sharedEdge(node.face, parent.face), |
|
m = matrix(shared.map(parent.project), shared.map(node.project)); |
|
node.transform = parent.transform ? multiply(parent.transform, m) : m; |
|
// Replace shared edge in parent edges array. |
|
var edges = parent.edges; |
|
for (var i = 0, n = edges.length; i < n; ++i) { |
|
if (pointEqual$1(shared[0], edges[i][1]) && pointEqual$1(shared[1], edges[i][0])) edges[i] = node; |
|
if (pointEqual$1(shared[0], edges[i][0]) && pointEqual$1(shared[1], edges[i][1])) edges[i] = node; |
|
} |
|
edges = node.edges; |
|
for (i = 0, n = edges.length; i < n; ++i) { |
|
if (pointEqual$1(shared[0], edges[i][0]) && pointEqual$1(shared[1], edges[i][1])) edges[i] = parent; |
|
if (pointEqual$1(shared[0], edges[i][1]) && pointEqual$1(shared[1], edges[i][0])) edges[i] = parent; |
|
} |
|
} else { |
|
node.transform = parent.transform; |
|
} |
|
if (node.children) { |
|
node.children.forEach(function(child) { |
|
recurse(child, node); |
|
}); |
|
} |
|
return node; |
|
} |
|
|
|
function forward(lambda, phi) { |
|
var node = face(lambda, phi), |
|
point = node.project([lambda * degrees$1, phi * degrees$1]), |
|
t; |
|
if (t = node.transform) { |
|
return [ |
|
t[0] * point[0] + t[1] * point[1] + t[2], |
|
-(t[3] * point[0] + t[4] * point[1] + t[5]) |
|
]; |
|
} |
|
point[1] = -point[1]; |
|
return point; |
|
} |
|
|
|
// Naive inverse! A faster solution would use bounding boxes, or even a |
|
// polygonal quadtree. |
|
if (hasInverse(root)) forward.invert = function(x, y) { |
|
var coordinates = faceInvert(root, [x, -y]); |
|
return coordinates && (coordinates[0] *= radians, coordinates[1] *= radians, coordinates); |
|
}; |
|
|
|
function faceInvert(node, coordinates) { |
|
var invert = node.project.invert, |
|
t = node.transform, |
|
point = coordinates; |
|
if (t) { |
|
t = inverse(t); |
|
point = [ |
|
t[0] * point[0] + t[1] * point[1] + t[2], |
|
(t[3] * point[0] + t[4] * point[1] + t[5]) |
|
]; |
|
} |
|
if (invert && node === faceDegrees(p = invert(point))) return p; |
|
var p, |
|
children = node.children; |
|
for (var i = 0, n = children && children.length; i < n; ++i) { |
|
if (p = faceInvert(children[i], coordinates)) return p; |
|
} |
|
} |
|
|
|
function faceDegrees(coordinates) { |
|
return face(coordinates[0] * radians$1, coordinates[1] * radians$1); |
|
} |
|
|
|
var proj = d3Geo.geoProjection(forward), |
|
stream_ = proj.stream; |
|
|
|
// run around the mesh of faces and stream all vertices to create the clipping polygon |
|
var polygon = []; |
|
outline({point: function(lambda, phi) { polygon.push([lambda, phi]); }}, root); |
|
polygon.push(polygon[0]); |
|
proj.preclip(clipPolygon({ type: "Polygon", coordinates: [ polygon ] })); |
|
|
|
function noClip(s) { return s; } |
|
|
|
proj.stream = function(stream) { |
|
var rotate = proj.rotate(), |
|
preclip = proj.preclip(), |
|
rotateStream = stream_(stream), |
|
sphereStream = (proj.preclip(noClip).rotate([0, 0]), stream_(stream)); |
|
proj.rotate(rotate); |
|
proj.preclip(preclip); |
|
rotateStream.sphere = function() { |
|
sphereStream.polygonStart(); |
|
sphereStream.lineStart(); |
|
outline(sphereStream, root); |
|
sphereStream.lineEnd(); |
|
sphereStream.polygonEnd(); |
|
}; |
|
return rotateStream; |
|
}; |
|
|
|
proj.root = function() { return root; }; |
|
return proj; |
|
}; |
|
|
|
function outline(stream, node, parent) { |
|
var point, |
|
edges = node.edges, |
|
n = edges.length, |
|
edge, |
|
multiPoint = {type: "MultiPoint", coordinates: node.face}, |
|
notPoles = node.face.filter(function(d) { return abs$1(d[1]) !== 90; }), |
|
b = d3Geo.geoBounds({type: "MultiPoint", coordinates: notPoles}), |
|
inside = false, |
|
j = -1, |
|
dx = b[1][0] - b[0][0]; |
|
// TODO |
|
node.centroid = dx === 180 || dx === 360 |
|
? [(b[0][0] + b[1][0]) / 2, (b[0][1] + b[1][1]) / 2] |
|
: d3Geo.geoCentroid(multiPoint); |
|
// First find the shared edge… |
|
if (parent) while (++j < n) { |
|
if (edges[j] === parent) break; |
|
} |
|
++j; |
|
for (var i = 0; i < n; ++i) { |
|
edge = edges[(i + j) % n]; |
|
if (Array.isArray(edge)) { |
|
if (!inside) { |
|
stream.point((point = d3Geo.geoInterpolate(edge[0], node.centroid)(epsilon$1))[0], point[1]); |
|
inside = true; |
|
} |
|
stream.point((point = d3Geo.geoInterpolate(edge[1], node.centroid)(epsilon$1))[0], point[1]); |
|
} else { |
|
inside = false; |
|
if (edge !== parent) outline(stream, edge, node); |
|
} |
|
} |
|
} |
|
|
|
// Tests equality of two spherical points. |
|
function pointEqual$1(a, b) { |
|
return a && b && a[0] === b[0] && a[1] === b[1]; |
|
} |
|
|
|
// Finds a shared edge given two clockwise polygons. |
|
function sharedEdge(a, b) { |
|
var x, y, n = a.length, found = null; |
|
for (var i = 0; i < n; ++i) { |
|
x = a[i]; |
|
for (var j = b.length; --j >= 0;) { |
|
y = b[j]; |
|
if (x[0] === y[0] && x[1] === y[1]) { |
|
if (found) return [found, x]; |
|
found = x; |
|
} |
|
} |
|
} |
|
} |
|
|
|
// Converts an array of n face vertices to an array of n + 1 edges. |
|
function faceEdges(face) { |
|
var n = face.length, |
|
edges = []; |
|
for (var a = face[n - 1], i = 0; i < n; ++i) edges.push([a, a = face[i]]); |
|
return edges; |
|
} |
|
|
|
function hasInverse(node) { |
|
return node.project.invert || node.children && node.children.some(hasInverse); |
|
} |
|
|
|
// TODO generate on-the-fly to avoid external modification. |
|
var octahedron = [ |
|
[0, 90], |
|
[-90, 0], [0, 0], [90, 0], [180, 0], |
|
[0, -90] |
|
]; |
|
|
|
var octahedron$1 = [ |
|
[0, 2, 1], |
|
[0, 3, 2], |
|
[5, 1, 2], |
|
[5, 2, 3], |
|
[0, 1, 4], |
|
[0, 4, 3], |
|
[5, 4, 1], |
|
[5, 3, 4] |
|
].map(function(face) { |
|
return face.map(function(i) { |
|
return octahedron[i]; |
|
}); |
|
}); |
|
|
|
"./octahedron"; |
|
|
|
var butterfly = function(faceProjection) { |
|
|
|
faceProjection = faceProjection || function(face) { |
|
var c = d3Geo.geoCentroid({type: "MultiPoint", coordinates: face}); |
|
return d3Geo.geoGnomonic().scale(1).translate([0, 0]).rotate([-c[0], -c[1]]); |
|
}; |
|
|
|
var faces = octahedron$1.map(function(face) { |
|
return {face: face, project: faceProjection(face)}; |
|
}); |
|
|
|
[-1, 0, 0, 1, 0, 1, 4, 5].forEach(function(d, i) { |
|
var node = faces[d]; |
|
node && (node.children || (node.children = [])).push(faces[i]); |
|
}); |
|
|
|
return polyhedral(faces[0], function(lambda, phi) { |
|
return faces[lambda < -pi$1 / 2 ? phi < 0 ? 6 : 4 |
|
: lambda < 0 ? phi < 0 ? 2 : 0 |
|
: lambda < pi$1 / 2 ? phi < 0 ? 3 : 1 |
|
: phi < 0 ? 7 : 5]; |
|
}) |
|
.scale(101.858) |
|
.center([0, 45]); |
|
}; |
|
|
|
var kx = 2 / sqrt$1(3); |
|
|
|
function collignonK(a, b) { |
|
var p = d3GeoProjection.geoCollignonRaw(a, b); |
|
return [p[0] * kx, p[1]]; |
|
} |
|
|
|
collignonK.invert = function(x,y) { |
|
return d3GeoProjection.geoCollignonRaw.invert(x / kx, y); |
|
}; |
|
|
|
var collignon = function(faceProjection) { |
|
|
|
faceProjection = faceProjection || function(face) { |
|
var c = d3Geo.geoCentroid({type: "MultiPoint", coordinates: face}); |
|
return d3Geo.geoProjection(collignonK).translate([0, 0]).scale(1).rotate(c[1] > 0 ? [-c[0], 0] : [180 - c[0], 180]); |
|
}; |
|
|
|
var faces = octahedron$1.map(function(face) { |
|
return {face: face, project: faceProjection(face)}; |
|
}); |
|
|
|
[-1, 0, 0, 1, 0, 1, 4, 5].forEach(function(d, i) { |
|
var node = faces[d]; |
|
node && (node.children || (node.children = [])).push(faces[i]); |
|
}); |
|
|
|
return polyhedral(faces[0], function(lambda, phi) { |
|
return faces[lambda < -pi$1 / 2 ? phi < 0 ? 6 : 4 |
|
: lambda < 0 ? phi < 0 ? 2 : 0 |
|
: lambda < pi$1 / 2 ? phi < 0 ? 3 : 1 |
|
: phi < 0 ? 7 : 5]; |
|
}) |
|
.scale(121.906) |
|
.center([0, 48.5904]); |
|
}; |
|
|
|
var waterman = function(faceProjection) { |
|
|
|
faceProjection = faceProjection || function(face) { |
|
var c = face.length === 6 ? d3Geo.geoCentroid({type: "MultiPoint", coordinates: face}) : face[0]; |
|
return d3Geo.geoGnomonic().scale(1).translate([0, 0]).rotate([-c[0], -c[1]]); |
|
}; |
|
|
|
var w5 = octahedron$1.map(function(face) { |
|
var xyz = face.map(cartesian$1), |
|
n = xyz.length, |
|
a = xyz[n - 1], |
|
b, |
|
hexagon = []; |
|
for (var i = 0; i < n; ++i) { |
|
b = xyz[i]; |
|
hexagon.push(spherical$1([ |
|
a[0] * 0.9486832980505138 + b[0] * 0.31622776601683794, |
|
a[1] * 0.9486832980505138 + b[1] * 0.31622776601683794, |
|
a[2] * 0.9486832980505138 + b[2] * 0.31622776601683794 |
|
]), spherical$1([ |
|
b[0] * 0.9486832980505138 + a[0] * 0.31622776601683794, |
|
b[1] * 0.9486832980505138 + a[1] * 0.31622776601683794, |
|
b[2] * 0.9486832980505138 + a[2] * 0.31622776601683794 |
|
])); |
|
a = b; |
|
} |
|
return hexagon; |
|
}); |
|
|
|
var cornerNormals = []; |
|
|
|
var parents = [-1, 0, 0, 1, 0, 1, 4, 5]; |
|
|
|
w5.forEach(function(hexagon, j) { |
|
var face = octahedron$1[j], |
|
n = face.length, |
|
normals = cornerNormals[j] = []; |
|
for (var i = 0; i < n; ++i) { |
|
w5.push([ |
|
face[i], |
|
hexagon[(i * 2 + 2) % (2 * n)], |
|
hexagon[(i * 2 + 1) % (2 * n)] |
|
]); |
|
parents.push(j); |
|
normals.push(cross( |
|
cartesian$1(hexagon[(i * 2 + 2) % (2 * n)]), |
|
cartesian$1(hexagon[(i * 2 + 1) % (2 * n)]) |
|
)); |
|
} |
|
}); |
|
|
|
var faces = w5.map(function(face) { |
|
return { |
|
project: faceProjection(face), |
|
face: face |
|
}; |
|
}); |
|
|
|
parents.forEach(function(d, i) { |
|
var parent = faces[d]; |
|
parent && (parent.children || (parent.children = [])).push(faces[i]); |
|
}); |
|
|
|
function face(lambda, phi) { |
|
var cosphi = cos$1(phi), |
|
p = [cosphi * cos$1(lambda), cosphi * sin$1(lambda), sin$1(phi)]; |
|
|
|
var hexagon = lambda < -pi$1 / 2 ? phi < 0 ? 6 : 4 |
|
: lambda < 0 ? phi < 0 ? 2 : 0 |
|
: lambda < pi$1 / 2 ? phi < 0 ? 3 : 1 |
|
: phi < 0 ? 7 : 5; |
|
|
|
var n = cornerNormals[hexagon]; |
|
|
|
return faces[dot(n[0], p) < 0 ? 8 + 3 * hexagon |
|
: dot(n[1], p) < 0 ? 8 + 3 * hexagon + 1 |
|
: dot(n[2], p) < 0 ? 8 + 3 * hexagon + 2 |
|
: hexagon]; |
|
} |
|
|
|
return polyhedral(faces[0], face) |
|
.scale(110.625) |
|
.center([0,45]); |
|
}; |
|
|
|
function dot(a, b) { |
|
for (var i = 0, n = a.length, s = 0; i < n; ++i) s += a[i] * b[i]; |
|
return s; |
|
} |
|
|
|
function cross(a, b) { |
|
return [ |
|
a[1] * b[2] - a[2] * b[1], |
|
a[2] * b[0] - a[0] * b[2], |
|
a[0] * b[1] - a[1] * b[0] |
|
]; |
|
} |
|
|
|
// Converts 3D Cartesian to spherical coordinates (degrees). |
|
function spherical$1(cartesian) { |
|
return [ |
|
atan2$1(cartesian[1], cartesian[0]) * degrees$1, |
|
asin$1(max$1(-1, min$1(1, cartesian[2]))) * degrees$1 |
|
]; |
|
} |
|
|
|
// Converts spherical coordinates (degrees) to 3D Cartesian. |
|
function cartesian$1(coordinates) { |
|
var lambda = coordinates[0] * radians$1, |
|
phi = coordinates[1] * radians$1, |
|
cosphi = cos$1(phi); |
|
return [ |
|
cosphi * cos$1(lambda), |
|
cosphi * sin$1(lambda), |
|
sin$1(phi) |
|
]; |
|
} |
|
|
|
var voronoi = function (parents, rotation, poly, faceProjection) { |
|
|
|
// it is possible to pass a specific projection on each face |
|
// by default is is a gnomonic projection centered on the face's centroid |
|
// scale 1 by convention |
|
faceProjection = faceProjection || function(face) { |
|
return d3Geo.geoGnomonic() |
|
.scale(1) |
|
.translate([0, 0]) |
|
.rotate([-face.site[0], -face.site[1]]); |
|
}; |
|
|
|
|
|
// the faces from the polyhedron each yield |
|
// - face: its vertices |
|
// - site: its voronoi site (here: centroid of the pentagon) |
|
// - project: local projection on this face |
|
var faces = poly.map(function(face) { |
|
var polygon = face.slice(); |
|
face = face.slice(0,-1); |
|
face.site = d3Geo.geoCentroid({type: "Polygon", coordinates: [polygon]}); |
|
return { |
|
face: face, |
|
site: face.site, |
|
project: faceProjection(face) |
|
}; |
|
}); |
|
|
|
// Build a tree of the faces, starting with face 0 (North Pole) |
|
// which has no parent (-1) |
|
parents |
|
.forEach(function(d, i) { |
|
var node = faces[d]; |
|
node && (node.children || (node.children = [])).push(faces[i]); |
|
}); |
|
|
|
// use the voronoi construction to find the relevant face |
|
// i.e. the one whose centre is closest to the point |
|
function voronoiface(lambda, phi) { |
|
lambda *= degrees; |
|
phi *= degrees; |
|
var d0 = Infinity; |
|
var found = -1; |
|
for (var i = 0; i < faces.length; i++) { |
|
var d = d3Geo.geoDistance(faces[i].site, [lambda, phi]); |
|
if (d < d0) { d0 = d; found = i; } |
|
} |
|
return faces[found]; |
|
} |
|
|
|
return polyhedral(faces[0], voronoiface, rotation) |
|
}; |
|
|
|
var dodecahedral = function(parents, rotation, polygons) { |
|
var A0 = asin(1/sqrt(3)) * degrees, |
|
A1 = acos((sqrt(15) - sqrt(3))/6) * degrees, |
|
A2 = 90 - A1, |
|
A3 = acos(-(sqrt(3) + sqrt(15))/6) * degrees; |
|
|
|
if (!polygons) polygons = [ |
|
[[45,A0],[0,A1],[180,A1],[135,A0],[90,A2],[45,A0]], |
|
[[45,A0],[A2,0],[-A2,0],[-45,A0],[0,A1],[45,A0]], |
|
[[45,A0],[90,A2],[90,-A2],[45,-A0],[A2,0],[45,A0]], |
|
[[0,A1],[-45,A0],[-90,A2],[-135,A0],[180,A1],[0,A1]], |
|
[[A2,0],[45,-A0],[0,-A1],[-45,-A0],[-A2,0],[A2,0]], |
|
[[90,A2],[135,A0],[A3,0],[135,-A0],[90,-A2],[90,A2]], |
|
[[45,-A0],[90,-A2],[135,-A0],[180,-A1],[0,-A1],[45,-A0]], |
|
[[135,A0],[180,A1],[-135,A0],[-A3,0],[A3,0],[135,A0]], |
|
[[-45,A0],[-A2,0],[-45,-A0],[-90,-A2],[-90,A2],[-45,A0]], |
|
[[-45,-A0],[0,-A1],[180,-A1],[-135,-A0],[-90,-A2],[-45,-A0]], |
|
[[135,-A0],[A3,0],[-A3,0],[-135,-A0],[180,-A1],[135,-A0]], |
|
[[-135,A0],[-90,A2],[-90,-A2],[-135,-A0],[-A3,0],[-135,A0]] |
|
]; |
|
|
|
if (rotation === undefined) rotation = (72 * 1.5); |
|
|
|
// See http://blockbuilder.org/Fil/80822180c2dd077ca8fb015f06abef2b |
|
// for the arrangement of faces |
|
// example: [-1,0,0,0,1,0,2,0,1,11,6,3] |
|
if (!parents) parents = [-1,0,4,8,1,2,2,3,1,8,6,3]; |
|
var projection = voronoi(parents, rotation, polygons) |
|
.rotate([-8,0,-32]) |
|
.scale(99.8); |
|
|
|
return projection; |
|
|
|
}; |
|
|
|
// if necessary, the following line could export a copy of the d3-geo-projection versions under the names xxxxUnclipped |
|
// export {geoPolyhedral as geoPolyhedralUnclipped, geoPolyhedralButterfly as geoPolyhedralButterflyUnclipped, geoPolyhedralCollignon as geoPolyhedralCollignonUnclipped, geoPolyhedralWaterman as geoPolyhedralWatermanUnclipped} from "./node_modules/d3-geo-projection/index"; |
|
|
|
// if necessary, the following line could export a copy of these versions under the names xxxxClipped |
|
// export {default as geoPolyhedral, default as geoPolyhedralClipped} from "./src/polyhedral/index"; |
|
// export {default as geoPolyhedralButterfly, default as geoPolyhedralButterflyClipped} from "./src/polyhedral/butterfly.js"; |
|
// export {default as geoPolyhedralCollignon, default as geoPolyhedralCollignonClipped} from "./src/polyhedral/collignon.js"; |
|
// export {default as geoPolyhedralWaterman, default as geoPolyhedralWatermanClipped} from "./src/polyhedral/waterman.js"; |
|
|
|
exports.geoClipPolygon = clipPolygon; |
|
exports.geoPolyhedral = polyhedral; |
|
exports.geoPolyhedralButterfly = butterfly; |
|
exports.geoPolyhedralCollignon = collignon; |
|
exports.geoPolyhedralWaterman = waterman; |
|
exports.geoVoronoiProjection = voronoi; |
|
exports.geoDodecahedral = dodecahedral; |
|
|
|
Object.defineProperty(exports, '__esModule', { value: true }); |
|
|
|
}))); |