diff options
Diffstat (limited to 'tipboard/static/js/lib/simplify.js')
-rw-r--r-- | tipboard/static/js/lib/simplify.js | 121 |
1 files changed, 121 insertions, 0 deletions
diff --git a/tipboard/static/js/lib/simplify.js b/tipboard/static/js/lib/simplify.js new file mode 100644 index 0000000..63a5ddb --- /dev/null +++ b/tipboard/static/js/lib/simplify.js @@ -0,0 +1,121 @@ +/* + (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 '.x' and '.y'; +// for 3D version, see 3d branch (configurability would draw significant performance overhead) + +// square distance between 2 points +function getSqDist(p1, p2) { + + var dx = p1.x - p2.x, + dy = p1.y - p2.y; + + return dx * dx + dy * dy; +} + +// square distance from a point to a segment +function getSqSegDist(p, p1, p2) { + + var x = p1.x, + y = p1.y, + dx = p2.x - x, + dy = p2.y - y; + + if (dx !== 0 || dy !== 0) { + + var t = ((p.x - x) * dx + (p.y - y) * dy) / (dx * dx + dy * dy); + + if (t > 1) { + x = p2.x; + y = p2.y; + + } else if (t > 0) { + x += dx * t; + y += dy * t; + } + } + + dx = p.x - x; + dy = p.y - 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; +} + +function simplifyDPStep(points, first, last, sqTolerance, simplified) { + var maxSqDist = 0, + index; + + for (var i = first + 1; i < last; i++) { + var sqDist = getSqSegDist(points[i], points[first], points[last]); + + if (sqDist > maxSqDist) { + index = i; + maxSqDist = sqDist; + } + } + + if (maxSqDist > sqTolerance) { + if (index - first > 1) simplifyDPStep(points, first, index, sqTolerance, simplified); + simplified.push(points[index]); + if (last - index > 1) simplifyDPStep(points, index, last, sqTolerance, simplified); + } +} + +// simplification using Ramer-Douglas-Peucker algorithm +function simplifyDouglasPeucker(points, sqTolerance) { + var last = points.length - 1; + + var simplified = [points[0]]; + simplifyDPStep(points, 0, last, sqTolerance, simplified); + simplified.push(points[last]); + + return simplified; +} + +// both algorithms combined for awesome performance +function simplify(points, tolerance, highestQuality) { + + if (points.length <= 2) 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; + +})(); |