Skip to content

Instantly share code, notes, and snippets.

@monfera

monfera/README.md

Last active August 29, 2015 14:00
Show Gist options
  • Save monfera/11116182 to your computer and use it in GitHub Desktop.
Save monfera/11116182 to your computer and use it in GitHub Desktop.
Download ZIP
Misplaced line simplification
Raw
README.md

This shows why line simplification between projection and adaptive resampling is not a good idea.

Raw
index.html
<!DOCTYPE html>
<meta charset="utf-8">
<style>
.graticule {
fill: none;
stroke: #777;
stroke-width: 1px;
}
.graticule:nth-child(1) {
fill: none;
stroke-opacity: 0.6;
stroke: #000;
stroke-width: 6px;
}
.graticule:nth-child(2) {
fill: none;
stroke-opacity: 0.6;
stroke: #00f;
stroke-width: 6px;
}
.graticule:nth-child(3) {
fill: none;
stroke-opacity: 0.6;
stroke: #f00;
stroke-width: 6px;
}
.graticule:nth-child(4) {
fill: none;
stroke-opacity: 0.6;
stroke: #f70;
stroke-width: 6px;
}
.spiral {
fill: none;
stroke: black;
stroke-width: 1px;
}
</style>
<body></body>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script src="http://d3js.org/d3.geo.projection.v0.min.js"></script>
<script src="simplify.js"></script>
<script>
var width = 960,
height = 500;
// Graticule to indicate time of period
var graticule = d3.geo.graticule()
.majorStep([90,90]) // Major step indicates 6-hour intervals
.minorStep([15,0]) // Minor step indicates 1-hour intervals
.majorExtent([[-180,-70], [180,65]])
.minorExtent([[-180,-60], [180,55]])
// Spiral function derived from https://www.jasondavies.com/maps/spiral/
var n = 1e4, dy = 3, rot=50;
var deadArea = 0.2
var spiral = d3.range(0+deadArea, 1 + 1 / n - deadArea, 1 / n).map(function(t) {
return [(360 * rot * t) % 360 - 180, -90 + dy
- Math.random()
+ (Math.cos(100 * Math.PI * t) - 1) / 2
+ (Math.cos(3 * Math.PI * t) - 1) / 2
+ (90 - dy) * 2 * t];
});
var spiralBase = d3.range(1-deadArea, 0+ deadArea, -1 / n).map(function(t) {
return [(360 * rot * t) % 360 - 180, -90 + (90 - dy ) * 2 * t];
});
// Interpolating projection from Michael Bostock's http://bl.ocks.org/mbostock/5731632
function interpolatedProjection(a, b) {
var projection = d3.geo.projection(raw).scale(1),
translate = projection.translate,
α;
function raw(λ, φ) {
var pa = a([λ *= 180 / Math.PI, φ *= 180 / Math.PI]), pb = b([λ, φ]);
return [(1 - α) * pa[0] + α * pb[0], (α - 1) * pa[1] - α * pb[1]];
}
projection.alpha = function(_) {
if (!arguments.length) return α;
α = +_;
var ta = a.translate(), tb = b.translate();
translate([(1 - α) * ta[0] + α * tb[0], (1 - α) * ta[1] + α * tb[1]]);
return projection;
};
delete projection.scale;
delete projection.translate;
return projection.alpha(0);
}
// Projection transforms
function lineSimplification(proj, directionForward, features, path) {
return function(tweenArg) {
simplificationFactor=0.7-0.7*Math.pow(2*(Math.abs(tweenArg-0.5)), 4);
features.attr("d", function(d) {
return path({
type: d.type,
coordinates: d.type==='MultiLineString'
? d.coordinates.map(function(c,i) { return simplify(c, simplificationFactor, true); })
: d.coordinates
});
});
};
}
function conicCartesianToSpiral(proj, directionForward, features, path) {
return function(tweenArg) {
var _ = directionForward?tweenArg:(1-tweenArg);
proj.parallels([_*89.99, _*89.99]);
proj.scale((1-_)*(1-_)*110+40);
proj.translate([width / 2 - .5, height / 2 + Math.sqrt(_)*87])
features.attr("d", path);
};
}
function interpolationSpiralToSphere(proj, directionForward, features, path) {
return function(tweenArg) {
var _ = directionForward?tweenArg:(1-tweenArg);
proj.alpha(_);
features.attr("d", path);
};
}
function ortographicSpin(proj, directionForward, features, path) {
var originalRotation = proj.rotate();
return function(tweenArg) {
var _ = directionForward?tweenArg:(1-tweenArg);
proj.clipAngle(95);
proj.rotate([_*360, _*-90, _*-90]);
features.attr("d", path);
};
}
// Showreel with projection/transform pairs
// Items are out of order so one projection can refer to another (e.g. next one)
showReel = []
showReel[0] = {
projection: d3.geo.conicConformal().parallels([0,0]).scale(150).translate([width / 2, height / 2 ]),
transform: lineSimplification
};
showReel[1] = {
projection: showReel[0].projection,
transform: conicCartesianToSpiral
};
showReel[3] = {
projection: d3.geo.orthographic().rotate([0,0,0]).scale(250).translate([width / 2 , height / 2 ]),
transform: ortographicSpin
};
showReel[2] = {
projection: interpolatedProjection(showReel[1].projection, showReel[3].projection),
transform: interpolationSpiralToSphere
};
showReel[4] = {
projection: showReel[3].projection,
transform: lineSimplification
};
// Animation and initial output
function animate(index, directionForward) {
var delta = directionForward?1:-1,
nextIndex = Math.min(Math.max(index+delta,0), showReel.length-1),
nextDirectionForward = nextIndex===index+delta?directionForward:!directionForward,
keyframe = showReel[index],
path = d3.geo.path().projection(keyframe.projection),
features = render(path);
svg.transition()
.duration(2000)
.tween("projection", function() {
return keyframe.transform(keyframe.projection, directionForward, features, path);
})
.transition()
.duration(0)
.each('end', animate.bind(this, nextIndex, nextDirectionForward));
}
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height),
simplificationFactor = 0;
function render(path) {
svg.selectAll(".graticule")
.data(graticule.lines)
.enter().append("path")
.attr("class", "graticule")
.attr("d", path);
svg.selectAll(".spiral")
.data([{type: "MultiLineString", coordinates: [spiral]}])
.enter().append("path")
.attr("class", "spiral")
.attr("d", path);
return svg.selectAll("path");
}
animate(0, true);
</script>
Raw
simplify.js
/* Copyright (c) 2012, Vladimir Agafonkin
All rights reserved.
Redistribution and use in source and binary forms, with or without modification, are
permitted provided that the following conditions are met:
1. Redistributions of source code must retain the above copyright notice, this list of
conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice, this list
of conditions and the following disclaimer in the documentation and/or other materials
provided with the distribution.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */
/*
(c) 2013, Vladimir Agafonkin
Simplify.js, a high-performance JS polyline simplification library
mourner.github.io/simplify-js
*/
(function () { 'use strict';
// to suit your point format, run search/replace for '[0]' and '[1]';
// for 3D version, see 3d branch (configurability would draw significant performance overhead)
// square distance between 2 points
function getSqDist(p1, p2) {
var dx = p1[0] - p2[0],
dy = p1[1] - p2[1];
return dx * dx + dy * dy;
}
// square distance from a point to a segment
function getSqSegDist(p, p1, p2) {
var x = p1[0],
y = p1[1],
dx = p2[0] - x,
dy = p2[1] - y;
if (dx !== 0 || dy !== 0) {
var t = ((p[0] - x) * dx + (p[1] - y) * dy) / (dx * dx + dy * dy);
if (t > 1) {
x = p2[0];
y = p2[1];
} else if (t > 0) {
x += dx * t;
y += dy * t;
}
}
dx = p[0] - x;
dy = p[1] - y;
return dx * dx + dy * dy;
}
// rest of the code doesn't care about point format
// basic distance-based simplification
function simplifyRadialDist(points, sqTolerance) {
var prevPoint = points[0],
newPoints = [prevPoint],
point;
for (var i = 1, len = points.length; i < len; i++) {
point = points[i];
if (getSqDist(point, prevPoint) > sqTolerance) {
newPoints.push(point);
prevPoint = point;
}
}
if (prevPoint !== point) newPoints.push(point);
return newPoints;
}
// simplification using optimized Douglas-Peucker algorithm with recursion elimination
function simplifyDouglasPeucker(points, sqTolerance) {
var len = points.length,
MarkerArray = typeof Uint8Array !== 'undefined' ? Uint8Array : Array,
markers = new MarkerArray(len),
first = 0,
last = len - 1,
stack = [],
newPoints = [],
i, maxSqDist, sqDist, index;
markers[first] = markers[last] = 1;
while (last) {
maxSqDist = 0;
for (i = first + 1; i < last; i++) {
sqDist = getSqSegDist(points[i], points[first], points[last]);
if (sqDist > maxSqDist) {
index = i;
maxSqDist = sqDist;
}
}
if (maxSqDist > sqTolerance) {
markers[index] = 1;
stack.push(first, index, index, last);
}
last = stack.pop();
first = stack.pop();
}
for (i = 0; i < len; i++) {
if (markers[i]) newPoints.push(points[i]);
}
return newPoints;
}
// both algorithms combined for awesome performance
function simplify(points, tolerance, highestQuality) {
if (points.length <= 1) return points;
var sqTolerance = tolerance !== undefined ? tolerance * tolerance : 1;
points = highestQuality ? points : simplifyRadialDist(points, sqTolerance);
points = simplifyDouglasPeucker(points, sqTolerance);
return points;
}
// export as AMD module / Node module / browser or worker variable
if (typeof define === 'function' && define.amd) define(function() { return simplify; });
else if (typeof module !== 'undefined') module.exports = simplify;
else if (typeof self !== 'undefined') self.simplify = simplify;
else window.simplify = simplify;
})();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment