Skip to content

Instantly share code, notes, and snippets.

@Fil
Last active March 4, 2018 20:44
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Fil/80822180c2dd077ca8fb015f06abef2b to your computer and use it in GitHub Desktop.
Save Fil/80822180c2dd077ca8fb015f06abef2b to your computer and use it in GitHub Desktop.
Dodecahedral projection with d3-geo-polygon [UNLISTED]
license: mit
// 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 });
})));
<!DOCTYPE html>
<meta charset="utf-8">
<style>
#sphere {
stroke: black;
stroke-width: 1;
fill: rgba(10,10,10,0.05);
}
.links path { stroke-width: 0}
#countries path {
fill: none;
stroke: none;
}
#graticule {
fill: none;
stroke: #aaa;
stroke-width: 0.5
}
.polygons {
stroke: #444;
}
.sites {
stroke: black;
fill: white;
}
</style>
<svg width="960" height="600"></svg>
<script src="https://unpkg.com/d3"></script>
<script src="https://unpkg.com/topojson"></script>
<script src="https://unpkg.com/d3-geo-polygon"></script>
<script src="d3-geo-polygon.js"></script>
<script>
var radians = Math.PI / 180, degrees = 1 / radians;
d3.json("https://unpkg.com/world-atlas/world/110m.json", function(error, world) {
world = topojson.feature(world, world.objects.countries);
var width = 960, height = 500;
// See http://blockbuilder.org/Fil/80822180c2dd077ca8fb015f06abef2b
// for the arrangement of faces
// example: [-1,0,0,0,1,0,2,0,1,11,6,3]
var parents = [-1,0,4,8,1,2,2,3,1,8,6,3];
projection = d3.geoDodecahedral(parents);
projection.fitExtent([[20,20],[width-20, height-20]], {type:"Sphere"})
//projection = d3.geoBertin1953();//.rotate([0.1,0,0.0001])
//projection = d3.geoPolyhedralButterfly();//.rotate([0.1,0,0.0001])
var path = d3.geoPath().projection(projection);
var svg = d3.select("svg");
if (1) svg.append('path')
.attr('id', 'sphere')
.datum({ type: "Sphere" })
.attr('d', path);
if (1) svg.append('path')
.attr('id', 'graticule')
.datum(d3.geoGraticule()())
.attr('d', path);
var countries = svg.append('g').attr('id', 'countries')
if(1) countries
.selectAll('path')
.data(world.features)
.enter()
.append('path')
.attr("d", path)
.style('fill', (_,i) => d3.schemeCategory20[i%20]);
var rotate = projection.rotate();
projection.rotate([0,0,0])
// run the tree of faces to get all sites and folds
var sites = [], folds = [];
function recurse(face) {
sites.push(face.site);
if (face.children) face.children.forEach(function(child){
folds.push({type:"LineString", coordinates: child.shared});
recurse(child);
});
}
recurse(projection.root());
// draw folds
svg.append('g')
.attr('class', 'folds')
.selectAll('path')
.data(folds)
.enter()
.append('path')
.attr('d', path)
.style('stroke-width', 0.5)
.style('stroke-dasharray', "5 3")
.style('stroke', '#888');
// draw sites
svg.append('g')
.attr('class', 'sites')
.selectAll('circle')
.data(sites)
.enter()
.append('circle')
.attr('transform', d => `translate(${projection(d)})`)
.attr('r', 10);
svg.append('g')
.selectAll('text')
.data(sites)
.enter()
.append('text')
.text((d,i) => i)
.attr('transform', d => `translate(${projection(d)})`)
.attr('text-anchor', 'middle')
.attr('dy', 5);
});
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment