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