forked from mourner/simplify-js
-
Notifications
You must be signed in to change notification settings - Fork 0
/
simplify.js
123 lines (90 loc) · 3.14 KB
/
simplify.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/*
(c) 2017, 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;
}
function simplifyDPStep(points, first, last, sqTolerance, simplified) {
var maxSqDist = sqTolerance,
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;
module.exports.default = simplify;
} else if (typeof self !== 'undefined') self.simplify = simplify;
else window.simplify = simplify;
})();