block by wboykinm b8bdc5e9a4650f73d6958eac51fa0a47

Strip map

Full Screen

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:

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

index.html

<!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: //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>

simplify.js

// 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;

}

warper.js

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);
  });

}