Skip to content

Instantly share code, notes, and snippets.

@Fil
Last active October 31, 2018 13:31
Show Gist options
  • Save Fil/61bf310184055add159620a977112069 to your computer and use it in GitHub Desktop.
Save Fil/61bf310184055add159620a977112069 to your computer and use it in GitHub Desktop.
Dodecahedral projection
license: mit

Obliging a USGS request.

Using:

In this implementation a list of shorter links allows you to control the faces that should be connected.

Built with blockbuilder.org

<!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@5"></script>
<script src="https://unpkg.com/topojson"></script>
<script src="https://unpkg.com/d3-geo-voronoi@0"></script>
<script src="https://unpkg.com/d3-geo-polygon"></script>
<script src="kruskal.js"></script>
<script>
var radians = Math.PI / 180, degrees = 1 / radians;
d3.json("https://unpkg.com/visionscarto-world-atlas/world/110m.json").then(function(world) {
world = topojson.feature(world, world.objects.countries);
var width = 960, height = 500;
var n = world.features.length;
function spherical(cartesian) {
return [
Math.atan2(cartesian[1], cartesian[0]),
Math.asin(Math.max(-1, Math.min(1, cartesian[2])))
];
}
function to_degrees(v){
return v.map(d => d * degrees);
}
function normalize (a) {
var d = Math.sqrt(a[0]*a[0] + a[1]*a[1] + a[2]*a[2]);
return a.map (e => e / d);
}
var g = (1 + Math.sqrt(5)) / 2;
var vertices = [
[0, 1, g],
[g, 0, 1],
[1, g, 0]
];
vertices = d3.merge([
vertices,
vertices.map(d => d.map(e => e * (e == 1 ? -1 : 1))),
vertices.map(d => d.map(e => e * (e > 1 ? -1 : 1))),
vertices.map(d => d.map(e => e * (e > 0 ? -1 : 1)))
])
.map(normalize)
.map(spherical)
.map(to_degrees)
var points = {
type: "FeatureCollection",
features: vertices.map(function(f, i) {
return {
type: "Point",
index: i,
coordinates: f
}
})
}
var v = d3.geoVoronoi()(points);
var links = v.links().features.map(d => d.properties)//.filter(d => d.urquhart)
// prefer certain links
links.forEach(l => {
var u = d3.extent([l.source.index, l.target.index]).join('-');
l.length = 1 - 0.5 * (['0-1', '1-4', '1-8', '2-4', '2-5', '3-7', '3-8', '6-10', '8-9'].indexOf(u) > -1)
})
var k = {
type: "FeatureCollection",
features: kruskal(links).map(l => ({
type:"LineString",
coordinates: [l.source.coordinates, l.target.coordinates],
properties: l
}))
};
var myriahedral = function(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
var i = 0;
faceProjection = faceProjection || function(face) {
var c = d3.geoCentroid({type: "MultiPoint", coordinates: face});
return d3.geoGnomonic()
.scale(1)
.translate([0, 0])
.rotate([-c[0], -c[1]]);
};
// the faces from the polyhedron each yield
// - face: its vertices
// - contains: does this face contain a point?
// - project: local projection on this face
var faces = poly.map(function(face) {
var polygon = face.slice();
face = face.slice(0,-1);
return {
face: face,
contains: function(lambda, phi) {
// todo: use geoVoronoi.find() instead?
return d3.geoContains({ type: "Polygon", coordinates: [ polygon ] },
[lambda * degrees, phi * degrees]);
},
project: faceProjection(face)
};
});
// Build a tree of the faces, starting with face 0 (North Pole)
// which has no parent (-1)
var parents = [-1];
var search = poly.length - 1;
do {
k.features.forEach(l => {
var s = l.properties.source.index,
t = l.properties.target.index;
if (parents[s] !== undefined && parents[t] === undefined) {
parents[t] = s;
search --;
}
else if (parents[t] !== undefined && parents[s] === undefined) {
parents[s] = t;
search --;
}
});
} while (search > 0);
console.log('vertices', JSON.stringify(vertices));
console.log('parents', JSON.stringify(parents));
parents
.forEach(function(d, i) {
var node = faces[d];
node && (node.children || (node.children = [])).push(faces[i]);
});
//console.log('faces', faces)
// Polyhedral projection
var proj = d3.geoPolyhedral(faces[0], function(lambda, phi) {
for (var i = 0; i < faces.length; i++) {
if (faces[i].contains(lambda, phi)) return faces[i];
}
})
.angle(108)
.rotate([-8,0,-32])
.fitExtent([[20,20],[width-20, height-20]], {type:"Sphere"})
proj.faces = faces;
return proj;
};
var projection = myriahedral(
v.polygons().features.map(d => d.geometry.coordinates[0])
);
//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.schemePaired[i%10]);
projection.rotate([0,0,0])
// this is a bit tedious…
var ko = k.features.map(d => {
var x = d.coordinates.map(projection),
delta = [x[1][0]-x[0][0], x[1][1]-x[0][1]];
var angle = Math.atan2(delta[1], delta[0]),
len = Math.sqrt(delta[0]*delta[0] + delta[1]*delta[1]);
var A = 0.61803 /* g - 1 - epsilon */, B = 36 * radians;
var y0 = [x[0][0] + len * Math.cos(angle + B) * A,
x[0][1] + len * Math.sin(angle + B) * A
];
var y1 = [x[0][0] + len * Math.cos(angle - B) * A,
x[0][1] + len * Math.sin(angle - B) * A
];
return [y0,y1].map(projection.invert);
});
if (1) svg.append('g')
.selectAll('path')
.data([{type:"MultiLineString", coordinates: ko}])
.enter()
.append('path')
.attr('d', path)
.attr('fill', 'none')
.attr('stroke', 'black')
.attr('stroke-width', 0.5)
.attr('stroke-dasharray', '3')
if (1) svg.append('g')
.attr('class', 'sites')
.selectAll('circle')
.data(points.features)
.enter()
.append('circle')
.attr('transform', d => `translate(${projection(d.coordinates)})`)
.attr('r', 10);
if (1) svg.append('g')
.selectAll('text')
.data(points.features)
.enter()
.append('text')
.text((d,i) => i)
.attr('transform', d => `translate(${projection(d.coordinates)})`)
.attr('text-anchor', 'middle')
.attr('dy', 5);
svg.append('g')
.attr('class', 'links')
.selectAll('path')
.data(k.features)
.enter()
.append('path')
.attr('d', path)
.attr('stroke', 'black')
.attr('fill', 'none');
// gentle animation
if (0) d3.interval(function(elapsed) {
projection.rotate([ elapsed / 150, 0, 0.001 ]);
svg.selectAll('path')
.attr('d', path);
}, 50);
});
</script>
// https://github.com/mikolalysenko/union-find
UnionFind = (function() {
"use strict"; "use restrict";
function UnionFind(count) {
this.roots = new Array(count);
this.ranks = new Array(count);
for(var i=0; i<count; ++i) {
this.roots[i] = i;
this.ranks[i] = 0;
}
}
var proto = UnionFind.prototype
Object.defineProperty(proto, "length", {
"get": function() {
return this.roots.length
}
})
proto.makeSet = function() {
var n = this.roots.length;
this.roots.push(n);
this.ranks.push(0);
return n;
}
proto.find = function(x) {
var x0 = x
var roots = this.roots;
while(roots[x] !== x) {
x = roots[x]
}
while(roots[x0] !== x) {
var y = roots[x0]
roots[x0] = x
x0 = y
}
return x;
}
proto.link = function(x, y) {
var xr = this.find(x)
, yr = this.find(y);
if(xr === yr) {
return;
}
var ranks = this.ranks
, roots = this.roots
, xd = ranks[xr]
, yd = ranks[yr];
if(xd < yd) {
roots[xr] = yr;
} else if(yd < xd) {
roots[yr] = xr;
} else {
roots[yr] = xr;
++ranks[xr];
}
}
return UnionFind;
})()
function kruskal(graph, dist) {
// 1 A := ø
const A = [];
// 2 pour chaque sommet v de G :
// 3 créerEnsemble(v)
let n = -Infinity;
graph.forEach(l => {
if (l.source.index > n) n = l.source.index;
if (l.target.index > n) n = l.target.index;
})
const uf = new UnionFind(n);
// 4 trier les arêtes de G par poids croissant
graph = graph.map(l => {
l.w = l.length || dist(l.source, l.target);
return l;
})
graph.sort((a,b) => d3.ascending(a.w, b.w))
// 5 pour chaque arête (u, v) de G prise par poids croissant :
.forEach(l => {
// 6 si find(u) ≠ find(v) :
if (uf.find(l.source.index) != uf.find(l.target.index)) {
// 7 ajouter l'arête (u, v) à l'ensemble A
A.push(l);
// 8 union(u, v)
uf.link(l.source.index, l.target.index);
}
});
// 9 retourner A
return A;
// yield uf;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment