| 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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203 |
1
3
1
2
2
2
2
1
1
2
2
2
2
2
10
7
2
8
8
10
10
8
8
8
3
3
3
2
2
9
7
7
2
1
2
3
3
3
7
2
5
1
4
4
2
2
2
2
8
8
3
5
1
4
3
1
1
16
16
1
15
3
16
1
15
4
16
9
9
22
22
22
22
6
6
16
14
14
22
22
22
| /*
* L.LineUtil contains different utility functions for line segments
* and polylines (clipping, simplification, distances, etc.)
*/
/*jshint bitwise:false */ // allow bitwise oprations for this file
L.LineUtil = {
// Simplify polyline with vertex reduction and Douglas-Peucker simplification.
// Improves rendering performance dramatically by lessening the number of points to draw.
simplify: function (/*Point[]*/ points, /*Number*/ tolerance) {
if (!tolerance || !points.length) {
return points.slice();
}
var sqTolerance = tolerance * tolerance;
// stage 1: vertex reduction
points = this._reducePoints(points, sqTolerance);
// stage 2: Douglas-Peucker simplification
points = this._simplifyDP(points, sqTolerance);
return points;
},
// distance from a point to a segment between two points
pointToSegmentDistance: function (/*Point*/ p, /*Point*/ p1, /*Point*/ p2) {
return Math.sqrt(this._sqClosestPointOnSegment(p, p1, p2, true));
},
closestPointOnSegment: function (/*Point*/ p, /*Point*/ p1, /*Point*/ p2) {
return this._sqClosestPointOnSegment(p, p1, p2);
},
// Douglas-Peucker simplification, see http://en.wikipedia.org/wiki/Douglas-Peucker_algorithm
_simplifyDP: function (points, sqTolerance) {
var len = points.length,
ArrayConstructor = typeof Uint8Array !== undefined + '' ? Uint8Array : Array,
markers = new ArrayConstructor(len);
markers[0] = markers[len - 1] = 1;
this._simplifyDPStep(points, markers, sqTolerance, 0, len - 1);
var i,
newPoints = [];
for (i = 0; i < len; i++) {
if (markers[i]) {
newPoints.push(points[i]);
}
}
return newPoints;
},
_simplifyDPStep: function (points, markers, sqTolerance, first, last) {
var maxSqDist = 0,
index, i, sqDist;
for (i = first + 1; i <= last - 1; i++) {
sqDist = this._sqClosestPointOnSegment(points[i], points[first], points[last], true);
if (sqDist > maxSqDist) {
index = i;
maxSqDist = sqDist;
}
}
if (maxSqDist > sqTolerance) {
markers[index] = 1;
this._simplifyDPStep(points, markers, sqTolerance, first, index);
this._simplifyDPStep(points, markers, sqTolerance, index, last);
}
},
// reduce points that are too close to each other to a single point
_reducePoints: function (points, sqTolerance) {
var reducedPoints = [points[0]];
for (var i = 1, prev = 0, len = points.length; i < len; i++) {
if (this._sqDist(points[i], points[prev]) > sqTolerance) {
reducedPoints.push(points[i]);
prev = i;
}
}
if (prev < len - 1) {
reducedPoints.push(points[len - 1]);
}
return reducedPoints;
},
// Cohen-Sutherland line clipping algorithm.
// Used to avoid rendering parts of a polyline that are not currently visible.
clipSegment: function (a, b, bounds, useLastCode) {
var codeA = useLastCode ? this._lastCode : this._getBitCode(a, bounds),
codeB = this._getBitCode(b, bounds),
codeOut, p, newCode;
// save 2nd code to avoid calculating it on the next segment
this._lastCode = codeB;
while (true) {
// if a,b is inside the clip window (trivial accept)
if (!(codeA | codeB)) {
return [a, b];
// if a,b is outside the clip window (trivial reject)
} else if (codeA & codeB) {
return false;
// other cases
} else {
codeOut = codeA || codeB,
p = this._getEdgeIntersection(a, b, codeOut, bounds),
newCode = this._getBitCode(p, bounds);
if (codeOut === codeA) {
a = p;
codeA = newCode;
} else {
b = p;
codeB = newCode;
}
}
}
},
_getEdgeIntersection: function (a, b, code, bounds) {
var dx = b.x - a.x,
dy = b.y - a.y,
min = bounds.min,
max = bounds.max;
if (code & 8) { // top
return new L.Point(a.x + dx * (max.y - a.y) / dy, max.y);
} else if (code & 4) { // bottom
return new L.Point(a.x + dx * (min.y - a.y) / dy, min.y);
} else if (code & 2) { // right
return new L.Point(max.x, a.y + dy * (max.x - a.x) / dx);
} else Eif (code & 1) { // left
return new L.Point(min.x, a.y + dy * (min.x - a.x) / dx);
}
},
_getBitCode: function (/*Point*/ p, bounds) {
var code = 0;
if (p.x < bounds.min.x) { // left
code |= 1;
} else if (p.x > bounds.max.x) { // right
code |= 2;
}
if (p.y < bounds.min.y) { // bottom
code |= 4;
} else if (p.y > bounds.max.y) { // top
code |= 8;
}
return code;
},
// square distance (to avoid unnecessary Math.sqrt calls)
_sqDist: function (p1, p2) {
var dx = p2.x - p1.x,
dy = p2.y - p1.y;
return dx * dx + dy * dy;
},
// return closest point on segment or distance to that point
_sqClosestPointOnSegment: function (p, p1, p2, sqDist) {
var x = p1.x,
y = p1.y,
dx = p2.x - x,
dy = p2.y - y,
dot = dx * dx + dy * dy,
t;
Eif (dot > 0) {
t = ((p.x - x) * dx + (p.y - y) * dy) / dot;
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 sqDist ? dx * dx + dy * dy : new L.Point(x, y);
}
};
|