veltman/README.md

## README.md

      
    Raw
  

              README.md
            
          
    Unrolling a polyline along an arbitrary zig-zag path by simplifying the line and then rotating based on each simplified segment.
See also: Line Simplification

  
## index.html
<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="utf-8" />
  <style>

    path {
      fill: none;
      stroke-width: 3px;
      stroke-linejoin: round;
    }

    .state {
      stroke: #777;
    }

    .simplified {
      stroke: #f0f;
      stroke-dasharray: 4,2;
    }

  </style>
</head>
<body>
<div></div>
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.17/d3.min.js"></script>
<script src="simplify.js"></script>
<script>

var width = 960,
    height = 500;

var svg = d3.select("body").append("svg")
  .attr("width", width)
  .attr("height", height);

var projection = d3.geo.conicConformal()
  .parallels([38 + 18 / 60, 39 + 27 / 60])
  .rotate([77, -37 - 40 / 60])
  .scale(10185)
  .translate([520, 500]);

var line = d3.svg.line();

// Top point
var rotation = -Math.PI / 24;

d3.json("md.geojson",function(err,md){

  // Project to screen x/y
  var border = md.features[0].geometry.coordinates[0].map(projection),
      vertices = simplify(border, 250),
      groups = getGroups(border, vertices);

  var state = svg.append("path")
    .attr("class", "state")
    .datum(border)
    .attr("d", line);

  var simplified = svg.append("path")
    .attr("class", "simplified");

  setTimeout(unroll, 500);

  function unroll() {

    var next = groups.shift(),
        angle = shortest(getAngle(next.anchor, next.end) + rotation);

    simplified.datum([next.anchor, next.end])
      .attr("d", line);

    // Reset original points for tweening
    border.forEach(function(p, i){
      p.original = i < next.start[2] ? null : p.slice(0,2);
    });

    state.transition()
      .delay(150)
      .duration(300)
      .attrTween("d",function(){

        // Update path with partial rotation
        return function(t) {

          var rotate = rotator(t * angle, next.anchor);

          border.forEach(rotate);
          simplified.attr("d", line); // Update simplified line too

          return line(border);

        };

      })
      .each("end",function(){

        // Zig zag
        if (rotation > -Math.PI / 2 && next.end[0] >= 760) {
          rotation = -Math.PI - rotation;
        } else if (rotation < -Math.PI / 2 && next.end[0] <= 150) {
          rotation = -Math.PI - rotation;
        }

        if (groups.length) {
          unroll();
        } else {
          simplified.remove();
        }

      });

  }

});

// Turn into groups of anchor point, first point to rotate, last point to rotate
function getGroups(border, vertices) {

  return vertices.slice(1).map(function(v, i){

    return {
      start: i ? border[vertices[i][2] + 1] : border[0],
      end: v,
      anchor: vertices[i]
    };

  });

}

// Return function ro modify point in place based on rotation from its original x/y
// (Using .original for tweening)
function rotator(angle, anchor) {

  var cx = anchor[0],
      cy = anchor[1],
      cos = Math.cos(angle),
      sin = Math.sin(angle);

  return function(point, i) {

    var x,
        y,
        x2,
        y2;

    if (point.original) {
      x = point.original[0];
      y = point.original[1];
      x2 = (cos * (x - cx)) + (sin * (y - cy)) + cx;
      y2 = (cos * (y - cy)) - (sin * (x - cx)) + cy;

      point[0] = x2;
      point[1] = y2;
    }

  };

}

// Take the shorter angle
function shortest(angle) {

  while (angle < -Math.PI) {
    angle += 2 * Math.PI;
  }

  while (angle > Math.PI) {
    angle -= 2 * Math.PI;
  }

  return angle;

}

function getAngle(a, b) {

  return Math.atan2(b[1] - a[1], b[0] - a[0]);

}

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

## md.geojson

      
Display the source blob

    
Display the rendered blob

    
    Raw
  

              md.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.
      
    
## 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
	<!DOCTYPE html>
	<html lang="en">
	<head>
	<meta charset="utf-8" />
	<style>

	path {
	fill: none;
	stroke-width: 3px;
	stroke-linejoin: round;
	}

	.state {
	stroke: #777;
	}

	.simplified {
	stroke: #f0f;
	stroke-dasharray: 4,2;
	}

	</style>
	</head>
	<body>
	<div></div>
	<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.17/d3.min.js"></script>
	<script src="simplify.js"></script>
	<script>

	var width = 960,
	height = 500;

	var svg = d3.select("body").append("svg")
	.attr("width", width)
	.attr("height", height);

	var projection = d3.geo.conicConformal()
	.parallels([38 + 18 / 60, 39 + 27 / 60])
	.rotate([77, -37 - 40 / 60])
	.scale(10185)
	.translate([520, 500]);

	var line = d3.svg.line();

	// Top point
	var rotation = -Math.PI / 24;

	d3.json("md.geojson",function(err,md){

	// Project to screen x/y
	var border = md.features[0].geometry.coordinates[0].map(projection),
	vertices = simplify(border, 250),
	groups = getGroups(border, vertices);

	var state = svg.append("path")
	.attr("class", "state")
	.datum(border)
	.attr("d", line);

	var simplified = svg.append("path")
	.attr("class", "simplified");

	setTimeout(unroll, 500);

	function unroll() {

	var next = groups.shift(),
	angle = shortest(getAngle(next.anchor, next.end) + rotation);

	simplified.datum([next.anchor, next.end])
	.attr("d", line);

	// Reset original points for tweening
	border.forEach(function(p, i){
	p.original = i < next.start[2] ? null : p.slice(0,2);
	});

	state.transition()
	.delay(150)
	.duration(300)
	.attrTween("d",function(){

	// Update path with partial rotation
	return function(t) {

	var rotate = rotator(t * angle, next.anchor);

	border.forEach(rotate);
	simplified.attr("d", line); // Update simplified line too

	return line(border);

	};

	})
	.each("end",function(){

	// Zig zag
	if (rotation > -Math.PI / 2 && next.end[0] >= 760) {
	rotation = -Math.PI - rotation;
	} else if (rotation < -Math.PI / 2 && next.end[0] <= 150) {
	rotation = -Math.PI - rotation;
	}

	if (groups.length) {
	unroll();
	} else {
	simplified.remove();
	}

	});

	}

	});

	// Turn into groups of anchor point, first point to rotate, last point to rotate
	function getGroups(border, vertices) {

	return vertices.slice(1).map(function(v, i){

	return {
	start: i ? border[vertices[i][2] + 1] : border[0],
	end: v,
	anchor: vertices[i]
	};

	});

	}

	// Return function ro modify point in place based on rotation from its original x/y
	// (Using .original for tweening)
	function rotator(angle, anchor) {

	var cx = anchor[0],
	cy = anchor[1],
	cos = Math.cos(angle),
	sin = Math.sin(angle);

	return function(point, i) {

	var x,
	y,
	x2,
	y2;

	if (point.original) {
	x = point.original[0];
	y = point.original[1];
	x2 = (cos * (x - cx)) + (sin * (y - cy)) + cx;
	y2 = (cos * (y - cy)) - (sin * (x - cx)) + cy;

	point[0] = x2;
	point[1] = y2;
	}

	};

	}

	// Take the shorter angle
	function shortest(angle) {

	while (angle < -Math.PI) {
	angle += 2 * Math.PI;
	}

	while (angle > Math.PI) {
	angle -= 2 * Math.PI;
	}

	return angle;

	}

	function getAngle(a, b) {

	return Math.atan2(b[1] - a[1], b[0] - a[0]);

	}

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

	}