From c5ba5b0456a711d157e317f220e9c739226e7f50 Mon Sep 17 00:00:00 2001 From: Joar Wandborg Date: Tue, 10 Jan 2012 01:54:37 +0100 Subject: Installed leaflet in extlib --- extlib/leaflet/src/geometry/LineUtil.js | 159 ++++++++++++++++++++++++++++++++ 1 file changed, 159 insertions(+) create mode 100644 extlib/leaflet/src/geometry/LineUtil.js (limited to 'extlib/leaflet/src/geometry/LineUtil.js') diff --git a/extlib/leaflet/src/geometry/LineUtil.js b/extlib/leaflet/src/geometry/LineUtil.js new file mode 100644 index 00000000..72a80855 --- /dev/null +++ b/extlib/leaflet/src/geometry/LineUtil.js @@ -0,0 +1,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); + } +}; \ No newline at end of file -- cgit v1.2.3