veltman/README.md

## README.md

      
    Raw
  

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

Pick a LineString (e.g. the California coast) to straighten out.
Simplify that LineString.
Turn that simplified LineString into a set of zones, one per segment.
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).
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.
A tiny difference in float precision can make a big difference in the warping math, so for now it truncates everything to six decimal places.

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

  
## ca.geojson

      
Display the source blob

    
Display the rendered blob

    
    Raw
  

              ca.geojson
            
          
      Loading

      Sorry, something went wrong. Reload?
      Sorry, we cannot display this file.
      Sorry, this file is invalid so it cannot be displayed.
      
          Viewer requires iframe.
      
    
## 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("ca.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){
        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]
  ];
}

d3.select(self.frameElement).style("height", "720px");

</script>
</body>
</html>

## preview.png

      
    Raw
  

              preview.png
            
          
## 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;

}

## thumbnail.png

      
    Raw
  

              thumbnail.png
            
          
## 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]
  ];

  // Prevent float precision problems in FF/Safari
  square.forEach(function(row){
    row.forEach(function(cell, i){
      row[i] = cell.toFixed(6);
    });
  });

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

}
	<!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("ca.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){
	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]
	];
	}

	d3.select(self.frameElement).style("height", "720px");

	</script>
	</body>
	</html>
	// 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]
	];

	// Prevent float precision problems in FF/Safari
	square.forEach(function(row){
	row.forEach(function(cell, i){
	row[i] = cell.toFixed(6);
	});
	});

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

	}