Skip to content

Instantly share code, notes, and snippets.

@wboykinm
Forked from veltman/README.md
Last active May 31, 2016 17:46
Show Gist options
  • Save wboykinm/b8bdc5e9a4650f73d6958eac51fa0a47 to your computer and use it in GitHub Desktop.
Save wboykinm/b8bdc5e9a4650f73d6958eac51fa0a47 to your computer and use it in GitHub Desktop.
Strip map

Creating an automatic strip map based on some geographic features and a chosen "spine." The approximate steps:

  1. Pick a LineString (e.g. the Norway coast) to straighten out.
  2. Simplify that LineString.
  3. Turn that simplified LineString into a set of zones, one per segment.
  4. Rotate/translate each zone to its destination position, anchoring it to the end of the previous segment and rotating it to match the desired angle (e.g. horizontal).
  5. Warp the contents of each zone to the resulting rectangle with a bilinear warp.

Steps 4 & 5 are separate for this demo but they could be calculated in a single step in real life.

Some issues:

  • There are some faint seams between zones, maybe some sort of clipping / subpixel artifact.
  • This requires making a separate copy of all the features for each zone, which is not super-efficient. Instead you could probably use some sort of point-in-polygon test and put the warping functions from each zone together into some compound projection function.
  • Depending on the rotation angle of the final map, the features involved, and the shape of the zones, a feature that extends way past the zone can sort of "curl" over itself when it gets warped, which flips the content of a zone to the wrong side. This could probably be avoided by actually geographically clipping everything ahead of time so that it doesn't extend way beyond the area of interest for the final map.

See also:

Line simplification
Ribbon Map of the Father of Waters
Lake Michigan Unfurled
Unrolling Maryland
Warp-off
John Ogilby's Britannia Atlas
California Coastline Ring
A Linear View of the World: Strip Maps as a Unique Form of Cartographic Representation

<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<style>
path {
fill: none;
stroke-width: 2px;
stroke-linejoin: round;
}
.state {
stroke: #999;
stroke-width: 1px;
fill: papayawhip;
}
.simplified {
stroke: #de1e3d;
stroke-width: 2px;
stroke-dasharray: 8,8;
}
.zone {
stroke: #0eb8ba;
}
.hidden {
display: none;
}
</style>
</head>
<body>
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.17/d3.min.js"></script>
<script src="warper.js"></script>
<script src="simplify.js"></script>
<script>
var stripWidth = 80;
var projection = d3.geo.conicConformal()
.parallels([36, 37 + 15 / 60])
.rotate([119, -35 - 20 / 60])
.scale(3433)
.translate([355, 498]);
var line = d3.svg.line();
// Top point
var origin = [50, 100];
d3.json("norway.geojson",function(err,ca){
// Preproject to screen coords
ca.coordinates[0] = ca.coordinates[0].map(projection);
// Get coastline
var ls = ca.coordinates[0].slice(0, 155);
// Get simplified vertices
var simplified = simplify(ls, 1000);
var zones = d3.select("body").append("svg")
.attr("width", 960)
.attr("height", 720)
.selectAll("g")
.data(getZones(simplified))
.enter()
.append("g");
zones.append("defs")
.append("clipPath")
.attr("id",function(d, i){
return "clip" + i;
})
.append("path");
var inner = zones.append("g")
.attr("class",function(d, i) {
return i ? "hidden" : null;
});
inner.append("path")
.attr("class", "state");
inner.append("line")
.attr("class", "simplified fade hidden");
// Put boundary outside so it isn't clipped
zones.append("path")
.attr("class", "zone fade hidden");
zones.call(update);
// Step-by-step for demo purposes
d3.select("body")
.transition()
.duration(1000)
.each("end", clipState)
.transition()
.each("end", showLine)
.transition()
.each("end", showZones)
.transition()
.each("end", move);
// 1. Clip out the rest of CA
function clipState() {
inner.classed("hidden", false)
.attr("clip-path",function(d, i){
return "url(#clip" + i + ")";
});
}
// 2. Show the simplified line
function showLine() {
inner.select(".simplified")
.classed("hidden", false);
}
// 3. Show the zone boundaries
function showZones() {
zones.select(".zone")
.classed("hidden", false);
}
// 4. Rotate/translate all the zones
function move() {
warpZones(zones.data());
zones.transition()
.duration(2000)
.each("end",align)
.call(update);
}
// 5. Warp the zones to rectangles
function align(z) {
z.project = function(d){
return z.warp(z.translate(d));
};
z.boundary = z.corners;
d3.select(this)
.transition()
.duration(750)
.call(update)
.each("end",fade);
}
// 6. Fade out
function fade() {
d3.select(this).selectAll(".fade")
.transition()
.duration(500)
.style("opacity", 0);
}
// Redraw
function update(sel) {
sel.select(".zone")
.attr("d",function(d){
// TODO why does this not work?
// return line(d.boundary);
return line(d.boundary.slice(0,4)) + "Z";
});
sel.select(".state")
.attr("d",function(d){
return d.path(ca);
});
sel.select(".simplified")
.attr("x1",function(d){
return d.ends[0][0];
})
.attr("x2",function(d){
return d.ends[1][0];
})
.attr("y1",function(d){
return d.ends[0][1];
})
.attr("y2",function(d){
return d.ends[1][1];
});
sel.select("clipPath path")
.attr("d",function(d){
return line(d.boundary.slice(0,4)) + "Z";
});
}
});
// Turn a simplified LineString into one group per segment
function getZones(simp) {
return simp.slice(1).map(function(p, i){
return {
boundary: getBoundary(simp[i - 1], simp[i], p, simp[i + 2]),
ends: [simp[i], p],
path: d3.geo.path().projection(null)
};
});
}
function warpZones(zones) {
zones.forEach(function(z,i){
var angle = getAngle(z.ends[0], z.ends[1]),
anchor = i ? zones[i - 1].ends[1] : origin;
// Anchor points to end of prev segment
var translate = [
anchor[0] - z.ends[0][0],
anchor[1] - z.ends[0][1]
];
// Get translation/rotation function
z.translate = translateAndRotate(translate, z.ends[0], angle);
// Warp the boundary line and the simplified segment
z.ends = z.ends.map(z.translate);
z.boundary = z.boundary.map(z.translate);
var top = bisect(null, z.ends[0], z.ends[1]),
bottom = bisect(z.ends[0], z.ends[1], null);
z.corners = [top[0], top[1], bottom[1], bottom[0], top[0]];
z.corners.push(z.corners[0]);
// See: http://bl.ocks.org/veltman/8f5a157276b1dc18ce2fba1bc06dfb48
z.warp = warper(z.boundary, z.corners);
z.project = function(d){
return z.translate(d);
};
z.path.projection(d3.geo.transform({
point: function(x, y) {
var p = z.project([x, y]);
this.stream.point(p[0], p[1]);
}
}));
});
}
function getBoundary(prev, first, second, next) {
// if prev is undefined, top is perpendicular through first
// otherwise top bisects the prev-first-second angle
// if next is undefined, bottom is perpendicular through second
// otherwise bottom bisects the first-second-next angle
var top = bisect(prev, first, second),
bottom = bisect(first, second, next);
return [top[0], top[1], bottom[1], bottom[0], top[0]];
}
function getAngle(a, b) {
return Math.atan2(b[1] - a[1], b[0] - a[0]);
}
// Given an anchor point, initial translate, and angle rotation
// Return a function to translate+rotate a point
function translateAndRotate(translate, anchor, angle) {
var cos = Math.cos(angle),
sin = Math.sin(angle);
return function(point) {
return [
translate[0] + anchor[0] + ( cos * (point[0] - anchor[0]) + sin * (point[1] - anchor[1])),
translate[1] + anchor[1] + ( -sin * (point[0] - anchor[0]) + cos * (point[1] - anchor[1]))
];
};
}
// Hacky angle bisector
function bisect(start, vertex, end) {
var at,
bt,
adjusted,
right,
left;
if (start) {
at = getAngle(start, vertex);
}
if (end) {
bt = getAngle(vertex, end);
}
if (!start) {
at = bt;
}
if (!end) {
bt = at;
}
adjusted = bt - at;
if (adjusted <= -Math.PI) {
adjusted = 2 * Math.PI + adjusted;
} else if (adjusted > Math.PI) {
adjusted = adjusted - 2 * Math.PI;
}
right = (adjusted - Math.PI) / 2;
left = Math.PI + right;
left += at;
right += at;
return [
[vertex[0] + stripWidth * Math.cos(left) / 2, vertex[1] + stripWidth * Math.sin(left) / 2],
[vertex[0] + stripWidth * Math.cos(right) / 2, vertex[1] + stripWidth * Math.sin(right) / 2]
];
}
function id(d) {
return d;
}
d3.select(self.frameElement).style("height", "720px");
</script>
</body>
</html>
Display the source blob
Display the rendered blob
Raw
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
// Rough Visvalingam simplification
// Better: https://bost.ocks.org/mike/simplify/
function simplify(points, threshold) {
var heap = binaryHeap(function(a, b){
return a.area < b.area;
}),
last = 0,
check;
points.forEach(function(point, i){
point[2] = i;
point.prev = points[i - 1];
point.next = points[i + 1];
point.area = getArea(point.prev, point, point.next);
heap.insert(point);
});
while (check = heap.pop()) {
check.area = last = Math.max(check.area, last);
if (check.prev) {
check.prev.next = check.next;
recalc(check.prev);
}
if (check.next) {
check.next.prev = check.prev;
recalc(check.next);
}
}
return points.filter(function(p){
return p.area > threshold;
});
function recalc(point) {
point.area = getArea(point.prev, point, point.next);
heap.update(point);
}
function getArea(a,b,c) {
if (!a || !c) {
return Infinity;
}
return Math.abs(a[0] * b[1] - a[0] * c[1] + b[0] * c[1] - b[0] * a[1] + c[0] * a[1] - c[0] * b[1]) / 2;
}
}
function binaryHeap(comparator) {
var heap = {},
nodes = [];
heap.remove = function(val) {
var len = nodes.length,
end;
for (var i = 0; i < len; i++) {
if (nodes[i] === val) {
end = nodes.pop();
if (i < len - 1) {
nodes[i] = end;
this.sink(i);
}
break;
}
}
return this;
};
heap.pop = function() {
var top = nodes.shift();
if (nodes.length) {
nodes.unshift(nodes.pop());
this.sink(0);
}
return top;
};
heap.bubble = function(i) {
var pi = Math.floor((i + 1) / 2) - 1;
if (i > 0 && this.compare(i, pi)) {
this.swap(i, pi);
this.bubble(pi);
}
return this;
};
heap.sink = function(i) {
var len = nodes.length,
ci = 2 * i + 1;
if (ci < len - 1 && this.compare(ci + 1, ci)) {
ci++;
}
if (ci < len && this.compare(ci, i)) {
this.swap(i, ci);
this.sink(ci);
}
return this;
};
heap.compare = function(i, j) {
return comparator(nodes[i], nodes[j]);
};
heap.insert = function(d) {
this.bubble(nodes.push(d) - 1);
};
heap.size = function() {
return nodes.length;
}
heap.swap = function(i, j) {
var swap = nodes[i];
nodes[i] = nodes[j];
nodes[j] = swap;
};
heap.update = function(d) {
this.remove(d);
this.insert(d);
// bubble / sink instead?
}
heap.nodes = nodes;
return heap;
}
function warper(start,end) {
var u0 = start[0][0],
v0 = start[0][1],
u1 = start[1][0],
v1 = start[1][1],
u2 = start[2][0],
v2 = start[2][1],
u3 = start[3][0],
v3 = start[3][1],
x0 = end[0][0],
y0 = end[0][1],
x1 = end[1][0],
y1 = end[1][1],
x2 = end[2][0],
y2 = end[2][1],
x3 = end[3][0],
y3 = end[3][1];
var square = [
[1,u0,v0,u0 * v0,0,0,0,0],
[1,u1,v1,u1 * v1,0,0,0,0],
[1,u2,v2,u2 * v2,0,0,0,0],
[1,u3,v3,u3 * v3,0,0,0,0],
[0,0,0,0,1,u0,v0,u0 * v0],
[0,0,0,0,1,u1,v1,u1 * v1],
[0,0,0,0,1,u2,v2,u2 * v2],
[0,0,0,0,1,u3,v3,u3 * v3]
];
var inverted = invert(square);
var s = multiply(inverted,[x0,x1,x2,x3,y0,y1,y2,y3]);
return function(p) {
return [
s[0] + s[1] * p[0] + s[2] * p[1] + s[3] * p[0] * p[1],
s[4] + s[5] * p[0] + s[6] * p[1] + s[7] * p[0] * p[1],
];
};
}
function multiply(matrix,vector) {
return matrix.map(function(row){
var sum = 0;
row.forEach(function(c,i){
sum += c * vector[i];
});
return sum;
});
}
function invert(matrix) {
var size = matrix.length,
base,
swap,
augmented;
// Augment w/ identity matrix
augmented = matrix.map(function(row,i){
return row.slice(0).concat(row.slice(0).map(function(d,j){
return j === i ? 1 : 0;
}));
});
// Process each row
for (var r = 0; r < size; r++) {
base = augmented[r][r];
// Zero on diagonal, swap with a lower row
if (!base) {
for (var rr = r + 1; rr < size; rr++) {
if (augmented[rr][r]) {
// swap
swap = augmented[rr];
augmented[rr] = augmented[r];
augmented[r] = swap;
base = augmented[r][r];
break;
}
}
if (!base) {
throw new Error("Not invertable :(");
}
}
// 1 on the diagonal
for (var c = 0; c < size * 2; c++) {
augmented[r][c] = augmented[r][c] / base;
}
// Zeroes elsewhere
for (var q = 0; q < size; q++) {
if (q !== r) {
base = augmented[q][r];
for (var p = 0; p < size * 2; p++) {
augmented[q][p] -= base * augmented[r][p];
}
}
}
}
return augmented.map(function(row){
return row.slice(size);
});
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment