Skip to content

Instantly share code, notes, and snippets.

@veltman
Last active July 3, 2016 05:32
Show Gist options
  • Save veltman/2bed63c8d7bc8559d6eddb8a248ec3ee to your computer and use it in GitHub Desktop.
Save veltman/2bed63c8d7bc8559d6eddb8a248ec3ee to your computer and use it in GitHub Desktop.
Unrolling Maryland

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

<!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
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment