https://nina3719.github.io/Under-The-Influence/js/history-line-simplify.js

1(function () { 'use strict';
2
3// to suit your point format, run search/replace for '.x' and '.y';
4// for 3D version, see 3d branch (configurability would draw significant performance overhead)
5
6// square distance between 2 points
7    function getSqDist(p1, p2) {
8
9        var dx = p1.x - p2.x,
10            dy = p1.y - p2.y;
11
12        return dx * dx + dy * dy;
13    }
14
15// square distance from a point to a segment
16    function getSqSegDist(p, p1, p2) {
17
18        var x = p1.x,
19            y = p1.y,
20            dx = p2.x - x,
21            dy = p2.y - y;
22
23        if (dx !== 0 || dy !== 0) {
24
25            var t = ((p.x - x) * dx + (p.y - y) * dy) / (dx * dx + dy * dy);
26
27            if (t > 1) {
28                x = p2.x;
29                y = p2.y;
30
31            } else if (t > 0) {
32                x += dx * t;
33                y += dy * t;
34            }
35        }
36
37        dx = p.x - x;
38        dy = p.y - y;
39
40        return dx * dx + dy * dy;
41    }
42// rest of the code doesn't care about point format
43
44// basic distance-based simplification
45    function simplifyRadialDist(points, sqTolerance) {
46
47        var prevPoint = points[0],
48            newPoints = [prevPoint],
49            point;
50
51        for (var i = 1, len = points.length; i < len; i++) {
52            point = points[i];
53
54            if (getSqDist(point, prevPoint) > sqTolerance) {
55                newPoints.push(point);
56                prevPoint = point;
57            }
58        }
59
60        if (prevPoint !== point) newPoints.push(point);
61
62        return newPoints;
63    }
64
65// simplification using optimized Douglas-Peucker algorithm with recursion elimination
66    function simplifyDouglasPeucker(points, sqTolerance) {
67
68        var len = points.length,
69            MarkerArray = typeof Uint8Array !== 'undefined' ? Uint8Array : Array,
70            markers = new MarkerArray(len),
71            first = 0,
72            last = len - 1,
73            stack = [],
74            newPoints = [],
75            i, maxSqDist, sqDist, index;
76
77        markers[first] = markers[last] = 1;
78
79        while (last) {
80
81            maxSqDist = 0;
82
83            for (i = first + 1; i < last; i++) {
84                sqDist = getSqSegDist(points[i], points[first], points[last]);
85
86                if (sqDist > maxSqDist) {
87                    index = i;
88                    maxSqDist = sqDist;
89                }
90            }
91
92            if (maxSqDist > sqTolerance) {
93                markers[index] = 1;
94                stack.push(first, index, index, last);
95            }
96
97            last = stack.pop();
98            first = stack.pop();
99        }
100
101        for (i = 0; i < len; i++) {
102            if (markers[i]) newPoints.push(points[i]);
103        }
104
105        return newPoints;
106    }
107
108// both algorithms combined for awesome performance
109    function simplify(points, tolerance, highestQuality) {
110
111        if (points.length <= 1) return points;
112
113        var sqTolerance = tolerance !== undefined ? tolerance * tolerance : 1;
114
115        points = highestQuality ? points : simplifyRadialDist(points, sqTolerance);
116        points = simplifyDouglasPeucker(points, sqTolerance);
117
118        return points;
119    }
120
121// export as AMD module / Node module / browser or worker variable
122    if (typeof define === 'function' && define.amd) define(function() { return simplify; });
123    else if (typeof module !== 'undefined') module.exports = simplify;
124    else if (typeof self !== 'undefined') self.simplify = simplify;
125    else window.simplify = simplify;
126
127})();