https://volgainfo.net/apps/system/js/simplify/simplify.js

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