Skip to content

Instantly share code, notes, and snippets.

@veltman

veltman/README.md

Last active July 3, 2016 05:32
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save veltman/2bed63c8d7bc8559d6eddb8a248ec3ee to your computer and use it in GitHub Desktop.
Save veltman/2bed63c8d7bc8559d6eddb8a248ec3ee to your computer and use it in GitHub Desktop.
Download ZIP
Unrolling Maryland
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

Raw
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>
Display the source blob
Display the rendered blob
Raw
md.geojson
{"type":"FeatureCollection","features":[{"type":"Feature","properties":{},"geometry":{"type":"Polygon","coordinates":[[[-79.476662,39.721078],[-79.478866,39.531689],[-79.482648,39.521364],[-79.486873,39.205961],[-79.43983,39.217074],[-79.387023,39.26554],[-79.253891,39.337222],[-79.129816,39.419901],[-79.095428,39.462548],[-79.033884,39.467761],[-78.955483,39.442277],[-78.953333,39.463645],[-78.874744,39.522611],[-78.826009,39.588829],[-78.795857,39.606934],[-78.689455,39.54577],[-78.623037,39.539512],[-78.565929,39.519444],[-78.462899,39.52084],[-78.426537,39.559155],[-78.454376,39.574319],[-78.420549,39.624021],[-78.351905,39.640486],[-78.266833,39.618818],[-78.254077,39.640089],[-78.182759,39.69511],[-78.107834,39.682137],[-78.035992,39.63572],[-78.011343,39.604083],[-77.93905,39.587139],[-77.885124,39.615775],[-77.838008,39.606125],[-77.842174,39.564333],[-77.886436,39.551947],[-77.795631,39.489623],[-77.78611,39.447197],[-77.75309,39.423262],[-77.755789,39.333899],[-77.719029,39.321125],[-77.675846,39.324192],[-77.615939,39.302722],[-77.566596,39.306121],[-77.543228,39.266937],[-77.486813,39.247586],[-77.45768,39.22502],[-77.527282,39.146236],[-77.462617,39.076248],[-77.340287,39.062991],[-77.244603,39.020109],[-77.249803,38.985909],[-77.221502,38.97131],[-77.146601,38.96421],[-77.1199,38.934311],[-77.040999,38.99511],[-76.909395,38.892812],[-77.038598,38.791513],[-77.042298,38.718515],[-77.1059,38.696815],[-77.132501,38.673816],[-77.1302,38.635017],[-77.148651,38.6056],[-77.183767,38.600699],[-77.237724,38.55187],[-77.27422,38.48177],[-77.250172,38.382781],[-77.207312,38.359867],[-77.091073,38.407546],[-77.040638,38.444618],[-77.016371,38.445572],[-76.98828,38.394975],[-76.975492,38.347327],[-76.929554,38.321088],[-76.920932,38.291568],[-76.864292,38.268945],[-76.802347,38.280743],[-76.797452,38.236918],[-76.673462,38.234401],[-76.590637,38.214212],[-76.552957,38.187209],[-76.54038,38.152991],[-76.481036,38.115873],[-76.439841,38.138933],[-76.421214,38.106039],[-76.392335,38.102896],[-76.361237,38.059542],[-76.319476,38.043315],[-76.338535,38.119472],[-76.320136,38.138339],[-76.385244,38.217751],[-76.39932,38.259284],[-76.374481,38.296348],[-76.402894,38.311402],[-76.388348,38.387781],[-76.492699,38.482849],[-76.515706,38.528988],[-76.511278,38.615745],[-76.532398,38.678363],[-76.526655,38.72443],[-76.559884,38.767361],[-76.510078,38.801216],[-76.489878,38.838715],[-76.519442,38.863135],[-76.49068,38.884814],[-76.49368,38.910013],[-76.45028,38.941113],[-76.474198,38.972647],[-76.422181,38.989011],[-76.39408,39.011311],[-76.438928,39.052788],[-76.42186,39.081442],[-76.428681,39.131709],[-76.534185,39.190608],[-76.488883,39.202208],[-76.442482,39.195408],[-76.38938,39.235408],[-76.402355,39.258315],[-76.36439,39.31184],[-76.327579,39.314108],[-76.341443,39.354217],[-76.295678,39.350008],[-76.291078,39.318108],[-76.180074,39.377609],[-76.102232,39.435659],[-76.060989,39.447722],[-76.071975,39.475047],[-76.117253,39.496068],[-76.096072,39.536912],[-75.970337,39.557637],[-75.966955,39.53865],[-75.99657,39.476658],[-75.976601,39.447808],[-76.035002,39.401994],[-76.049846,39.370644],[-76.110527,39.372257],[-76.145524,39.334399],[-76.170422,39.332094],[-76.185674,39.285367],[-76.219338,39.261997],[-76.278527,39.145764],[-76.252968,39.133626],[-76.231117,39.061017],[-76.183908,39.096344],[-76.145174,39.092824],[-76.184207,39.046264],[-76.163988,38.999542],[-76.20236,38.973079],[-76.277478,38.982492],[-76.302846,39.025828],[-76.361727,38.939175],[-76.336104,38.905977],[-76.273083,38.941927],[-76.203638,38.928382],[-76.202598,38.862616],[-76.19109,38.82966],[-76.219328,38.812371],[-76.265808,38.847512],[-76.300889,38.82619],[-76.334619,38.772911],[-76.316146,38.729586],[-76.275015,38.712714],[-76.255093,38.736476],[-76.200334,38.670774],[-76.175159,38.673236],[-76.147158,38.63684],[-76.212427,38.606738],[-76.23665,38.628598],[-76.279589,38.60952],[-76.290043,38.569158],[-76.2473,38.523818],[-76.263968,38.503452],[-76.33636,38.492235],[-76.28302,38.413512],[-76.258189,38.318373],[-76.211446,38.302656],[-76.111296,38.286946],[-76.09972,38.253647],[-76.044108,38.241682],[-76.027487,38.280108],[-76.05022,38.304101],[-76.016682,38.332429],[-76.002282,38.374477],[-75.973876,38.36585],[-75.964237,38.324285],[-76.007375,38.304318],[-75.963453,38.251793],[-75.938577,38.272329],[-75.90004,38.232133],[-75.870318,38.243432],[-75.846377,38.210477],[-75.942375,38.187066],[-75.959616,38.137141],[-75.900355,38.14115],[-75.837563,38.113753],[-75.880515,38.075011],[-75.812913,38.058932],[-75.875297,38.011965],[-75.898956,37.974514],[-75.898316,37.925114],[-75.860727,37.91831],[-75.783815,37.972594],[-75.737997,37.963526],[-75.71315,37.976623],[-75.669711,37.950796],[-75.624341,37.994211],[-75.242266,38.027209],[-75.193796,38.096013],[-75.102947,38.311525],[-75.085518,38.32427],[-75.048939,38.451263],[-75.428728,38.452671],[-75.693521,38.460128],[-75.725829,38.869296],[-75.755953,39.245958],[-75.788658,39.658211],[-75.788359,39.721811],[-76.418784,39.721204],[-76.990903,39.7198],[-77.534758,39.720134],[-78.073736,39.722314],[-78.537702,39.72249],[-79.045548,39.722883],[-79.476662,39.721078]]]}}]}
Raw
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment