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
|
/*
* L.LineUtil contains different utility functions for line segments
* and polylines (clipping, simplification, distances, etc.)
*/
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) return points.slice();
// stage 1: vertex reduction
points = this.reducePoints(points, tolerance);
// stage 2: Douglas-Peucker simplification
points = this.simplifyDP(points, tolerance);
return points;
},
// distance from a point to a segment between two points
pointToSegmentDistance: function(/*Point*/ p, /*Point*/ p1, /*Point*/ p2) {
return Math.sqrt(this._sqPointToSegmentDist(p, p1, p2));
},
// Douglas-Peucker simplification, see http://en.wikipedia.org/wiki/Douglas-Peucker_algorithm
simplifyDP: function(points, tol) {
var maxDist2 = 0,
index = 0,
t2 = tol * tol;
for (var i = 1, len = points.length, dist2; i < len - 1; i++) {
dist2 = this._sqPointToSegmentDist(points[i], points[0], points[len - 1]);
if (dist2 > maxDist2) {
index = i;
maxDist2 = dist2;
}
}
if (maxDist2 >= t2) {
var part1 = points.slice(0, index),
part2 = points.slice(index),
simplifiedPart1 = this.simplifyDP(part1, tol).slice(0, len - 2),
simplifiedPart2 = this.simplifyDP(part2, tol);
return simplifiedPart1.concat(simplifiedPart2);
} else {
return [points[0], points[len - 1]];
}
},
// reduce points that are too close to each other to a single point
reducePoints: function(points, tol) {
var reducedPoints = [points[0]],
t2 = tol * tol;
for (var i = 1, prev = 0, len = points.length; i < len; i++) {
if (this._sqDist(points[i], points[prev]) < t2) continue;
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 min = bounds.min,
max = bounds.max;
var codeA = useLastCode ? this._lastCode : this._getBitCode(a, bounds),
codeB = this._getBitCode(b, bounds);
// 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 {
var 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 if (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) code |= 1; // left
else if (p.x > bounds.max.x) code |= 2; // right
if (p.y < bounds.min.y) code |= 4; // bottom
else if (p.y > bounds.max.y) code |= 8; // top
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;
},
// square distance from point to a segment
_sqPointToSegmentDist: function(p, p1, p2) {
var x2 = p2.x - p1.x,
y2 = p2.y - p1.y;
if (!x2 && !y2) return this._sqDist(p, p1);
var dot = (p.x - p1.x) * x2 + (p.y - p1.y) * y2,
t = dot / this._sqDist(p1, p2);
if (t < 0) return this._sqDist(p, p1);
if (t > 1) return this._sqDist(p, p2);
var proj = new L.Point(p1.x + x2 * t, p1.y + y2 * t);
return this._sqDist(p, proj);
}
};
|
