diff options
Diffstat (limited to 'misc/openlayers/lib/OpenLayers/Geometry/LineString.js')
| -rw-r--r-- | misc/openlayers/lib/OpenLayers/Geometry/LineString.js | 646 |
1 files changed, 646 insertions, 0 deletions
diff --git a/misc/openlayers/lib/OpenLayers/Geometry/LineString.js b/misc/openlayers/lib/OpenLayers/Geometry/LineString.js new file mode 100644 index 0000000..b7d7dac --- /dev/null +++ b/misc/openlayers/lib/OpenLayers/Geometry/LineString.js @@ -0,0 +1,646 @@ +/* Copyright (c) 2006-2013 by OpenLayers Contributors (see authors.txt for + * full list of contributors). Published under the 2-clause BSD license. + * See license.txt in the OpenLayers distribution or repository for the + * full text of the license. */ + +/** + * @requires OpenLayers/Geometry/Curve.js + */ + +/** + * Class: OpenLayers.Geometry.LineString + * A LineString is a Curve which, once two points have been added to it, can + * never be less than two points long. + * + * Inherits from: + * - <OpenLayers.Geometry.Curve> + */ +OpenLayers.Geometry.LineString = OpenLayers.Class(OpenLayers.Geometry.Curve, { + + /** + * Constructor: OpenLayers.Geometry.LineString + * Create a new LineString geometry + * + * Parameters: + * points - {Array(<OpenLayers.Geometry.Point>)} An array of points used to + * generate the linestring + * + */ + + /** + * APIMethod: removeComponent + * Only allows removal of a point if there are three or more points in + * the linestring. (otherwise the result would be just a single point) + * + * Parameters: + * point - {<OpenLayers.Geometry.Point>} The point to be removed + * + * Returns: + * {Boolean} The component was removed. + */ + removeComponent: function(point) { + var removed = this.components && (this.components.length > 2); + if (removed) { + OpenLayers.Geometry.Collection.prototype.removeComponent.apply(this, + arguments); + } + return removed; + }, + + /** + * APIMethod: intersects + * Test for instersection between two geometries. This is a cheapo + * implementation of the Bently-Ottmann algorigithm. It doesn't + * really keep track of a sweep line data structure. It is closer + * to the brute force method, except that segments are sorted and + * potential intersections are only calculated when bounding boxes + * intersect. + * + * Parameters: + * geometry - {<OpenLayers.Geometry>} + * + * Returns: + * {Boolean} The input geometry intersects this geometry. + */ + intersects: function(geometry) { + var intersect = false; + var type = geometry.CLASS_NAME; + if(type == "OpenLayers.Geometry.LineString" || + type == "OpenLayers.Geometry.LinearRing" || + type == "OpenLayers.Geometry.Point") { + var segs1 = this.getSortedSegments(); + var segs2; + if(type == "OpenLayers.Geometry.Point") { + segs2 = [{ + x1: geometry.x, y1: geometry.y, + x2: geometry.x, y2: geometry.y + }]; + } else { + segs2 = geometry.getSortedSegments(); + } + var seg1, seg1x1, seg1x2, seg1y1, seg1y2, + seg2, seg2y1, seg2y2; + // sweep right + outer: for(var i=0, len=segs1.length; i<len; ++i) { + seg1 = segs1[i]; + seg1x1 = seg1.x1; + seg1x2 = seg1.x2; + seg1y1 = seg1.y1; + seg1y2 = seg1.y2; + inner: for(var j=0, jlen=segs2.length; j<jlen; ++j) { + seg2 = segs2[j]; + if(seg2.x1 > seg1x2) { + // seg1 still left of seg2 + break; + } + if(seg2.x2 < seg1x1) { + // seg2 still left of seg1 + continue; + } + seg2y1 = seg2.y1; + seg2y2 = seg2.y2; + if(Math.min(seg2y1, seg2y2) > Math.max(seg1y1, seg1y2)) { + // seg2 above seg1 + continue; + } + if(Math.max(seg2y1, seg2y2) < Math.min(seg1y1, seg1y2)) { + // seg2 below seg1 + continue; + } + if(OpenLayers.Geometry.segmentsIntersect(seg1, seg2)) { + intersect = true; + break outer; + } + } + } + } else { + intersect = geometry.intersects(this); + } + return intersect; + }, + + /** + * Method: getSortedSegments + * + * Returns: + * {Array} An array of segment objects. Segment objects have properties + * x1, y1, x2, and y2. The start point is represented by x1 and y1. + * The end point is represented by x2 and y2. Start and end are + * ordered so that x1 < x2. + */ + getSortedSegments: function() { + var numSeg = this.components.length - 1; + var segments = new Array(numSeg), point1, point2; + for(var i=0; i<numSeg; ++i) { + point1 = this.components[i]; + point2 = this.components[i + 1]; + if(point1.x < point2.x) { + segments[i] = { + x1: point1.x, + y1: point1.y, + x2: point2.x, + y2: point2.y + }; + } else { + segments[i] = { + x1: point2.x, + y1: point2.y, + x2: point1.x, + y2: point1.y + }; + } + } + // more efficient to define this somewhere static + function byX1(seg1, seg2) { + return seg1.x1 - seg2.x1; + } + return segments.sort(byX1); + }, + + /** + * Method: splitWithSegment + * Split this geometry with the given segment. + * + * Parameters: + * seg - {Object} An object with x1, y1, x2, and y2 properties referencing + * segment endpoint coordinates. + * options - {Object} Properties of this object will be used to determine + * how the split is conducted. + * + * Valid options: + * edge - {Boolean} Allow splitting when only edges intersect. Default is + * true. If false, a vertex on the source segment must be within the + * tolerance distance of the intersection to be considered a split. + * tolerance - {Number} If a non-null value is provided, intersections + * within the tolerance distance of one of the source segment's + * endpoints will be assumed to occur at the endpoint. + * + * Returns: + * {Object} An object with *lines* and *points* properties. If the given + * segment intersects this linestring, the lines array will reference + * geometries that result from the split. The points array will contain + * all intersection points. Intersection points are sorted along the + * segment (in order from x1,y1 to x2,y2). + */ + splitWithSegment: function(seg, options) { + var edge = !(options && options.edge === false); + var tolerance = options && options.tolerance; + var lines = []; + var verts = this.getVertices(); + var points = []; + var intersections = []; + var split = false; + var vert1, vert2, point; + var node, vertex, target; + var interOptions = {point: true, tolerance: tolerance}; + var result = null; + for(var i=0, stop=verts.length-2; i<=stop; ++i) { + vert1 = verts[i]; + points.push(vert1.clone()); + vert2 = verts[i+1]; + target = {x1: vert1.x, y1: vert1.y, x2: vert2.x, y2: vert2.y}; + point = OpenLayers.Geometry.segmentsIntersect( + seg, target, interOptions + ); + if(point instanceof OpenLayers.Geometry.Point) { + if((point.x === seg.x1 && point.y === seg.y1) || + (point.x === seg.x2 && point.y === seg.y2) || + point.equals(vert1) || point.equals(vert2)) { + vertex = true; + } else { + vertex = false; + } + if(vertex || edge) { + // push intersections different than the previous + if(!point.equals(intersections[intersections.length-1])) { + intersections.push(point.clone()); + } + if(i === 0) { + if(point.equals(vert1)) { + continue; + } + } + if(point.equals(vert2)) { + continue; + } + split = true; + if(!point.equals(vert1)) { + points.push(point); + } + lines.push(new OpenLayers.Geometry.LineString(points)); + points = [point.clone()]; + } + } + } + if(split) { + points.push(vert2.clone()); + lines.push(new OpenLayers.Geometry.LineString(points)); + } + if(intersections.length > 0) { + // sort intersections along segment + var xDir = seg.x1 < seg.x2 ? 1 : -1; + var yDir = seg.y1 < seg.y2 ? 1 : -1; + result = { + lines: lines, + points: intersections.sort(function(p1, p2) { + return (xDir * p1.x - xDir * p2.x) || (yDir * p1.y - yDir * p2.y); + }) + }; + } + return result; + }, + + /** + * Method: split + * Use this geometry (the source) to attempt to split a target geometry. + * + * Parameters: + * target - {<OpenLayers.Geometry>} The target geometry. + * options - {Object} Properties of this object will be used to determine + * how the split is conducted. + * + * Valid options: + * mutual - {Boolean} Split the source geometry in addition to the target + * geometry. Default is false. + * edge - {Boolean} Allow splitting when only edges intersect. Default is + * true. If false, a vertex on the source must be within the tolerance + * distance of the intersection to be considered a split. + * tolerance - {Number} If a non-null value is provided, intersections + * within the tolerance distance of an existing vertex on the source + * will be assumed to occur at the vertex. + * + * Returns: + * {Array} A list of geometries (of this same type as the target) that + * result from splitting the target with the source geometry. The + * source and target geometry will remain unmodified. If no split + * results, null will be returned. If mutual is true and a split + * results, return will be an array of two arrays - the first will be + * all geometries that result from splitting the source geometry and + * the second will be all geometries that result from splitting the + * target geometry. + */ + split: function(target, options) { + var results = null; + var mutual = options && options.mutual; + var sourceSplit, targetSplit, sourceParts, targetParts; + if(target instanceof OpenLayers.Geometry.LineString) { + var verts = this.getVertices(); + var vert1, vert2, seg, splits, lines, point; + var points = []; + sourceParts = []; + for(var i=0, stop=verts.length-2; i<=stop; ++i) { + vert1 = verts[i]; + vert2 = verts[i+1]; + seg = { + x1: vert1.x, y1: vert1.y, + x2: vert2.x, y2: vert2.y + }; + targetParts = targetParts || [target]; + if(mutual) { + points.push(vert1.clone()); + } + for(var j=0; j<targetParts.length; ++j) { + splits = targetParts[j].splitWithSegment(seg, options); + if(splits) { + // splice in new features + lines = splits.lines; + if(lines.length > 0) { + lines.unshift(j, 1); + Array.prototype.splice.apply(targetParts, lines); + j += lines.length - 2; + } + if(mutual) { + for(var k=0, len=splits.points.length; k<len; ++k) { + point = splits.points[k]; + if(!point.equals(vert1)) { + points.push(point); + sourceParts.push(new OpenLayers.Geometry.LineString(points)); + if(point.equals(vert2)) { + points = []; + } else { + points = [point.clone()]; + } + } + } + } + } + } + } + if(mutual && sourceParts.length > 0 && points.length > 0) { + points.push(vert2.clone()); + sourceParts.push(new OpenLayers.Geometry.LineString(points)); + } + } else { + results = target.splitWith(this, options); + } + if(targetParts && targetParts.length > 1) { + targetSplit = true; + } else { + targetParts = []; + } + if(sourceParts && sourceParts.length > 1) { + sourceSplit = true; + } else { + sourceParts = []; + } + if(targetSplit || sourceSplit) { + if(mutual) { + results = [sourceParts, targetParts]; + } else { + results = targetParts; + } + } + return results; + }, + + /** + * Method: splitWith + * Split this geometry (the target) with the given geometry (the source). + * + * Parameters: + * geometry - {<OpenLayers.Geometry>} A geometry used to split this + * geometry (the source). + * options - {Object} Properties of this object will be used to determine + * how the split is conducted. + * + * Valid options: + * mutual - {Boolean} Split the source geometry in addition to the target + * geometry. Default is false. + * edge - {Boolean} Allow splitting when only edges intersect. Default is + * true. If false, a vertex on the source must be within the tolerance + * distance of the intersection to be considered a split. + * tolerance - {Number} If a non-null value is provided, intersections + * within the tolerance distance of an existing vertex on the source + * will be assumed to occur at the vertex. + * + * Returns: + * {Array} A list of geometries (of this same type as the target) that + * result from splitting the target with the source geometry. The + * source and target geometry will remain unmodified. If no split + * results, null will be returned. If mutual is true and a split + * results, return will be an array of two arrays - the first will be + * all geometries that result from splitting the source geometry and + * the second will be all geometries that result from splitting the + * target geometry. + */ + splitWith: function(geometry, options) { + return geometry.split(this, options); + + }, + + /** + * APIMethod: getVertices + * Return a list of all points in this geometry. + * + * Parameters: + * nodes - {Boolean} For lines, only return vertices that are + * endpoints. If false, for lines, only vertices that are not + * endpoints will be returned. If not provided, all vertices will + * be returned. + * + * Returns: + * {Array} A list of all vertices in the geometry. + */ + getVertices: function(nodes) { + var vertices; + if(nodes === true) { + vertices = [ + this.components[0], + this.components[this.components.length-1] + ]; + } else if (nodes === false) { + vertices = this.components.slice(1, this.components.length-1); + } else { + vertices = this.components.slice(); + } + return vertices; + }, + + /** + * APIMethod: distanceTo + * Calculate the closest distance between two geometries (on the x-y plane). + * + * Parameters: + * geometry - {<OpenLayers.Geometry>} The target geometry. + * options - {Object} Optional properties for configuring the distance + * calculation. + * + * Valid options: + * details - {Boolean} Return details from the distance calculation. + * Default is false. + * edge - {Boolean} Calculate the distance from this geometry to the + * nearest edge of the target geometry. Default is true. If true, + * calling distanceTo from a geometry that is wholly contained within + * the target will result in a non-zero distance. If false, whenever + * geometries intersect, calling distanceTo will return 0. If false, + * details cannot be returned. + * + * Returns: + * {Number | Object} The distance between this geometry and the target. + * If details is true, the return will be an object with distance, + * x0, y0, x1, and x2 properties. The x0 and y0 properties represent + * the coordinates of the closest point on this geometry. The x1 and y1 + * properties represent the coordinates of the closest point on the + * target geometry. + */ + distanceTo: function(geometry, options) { + var edge = !(options && options.edge === false); + var details = edge && options && options.details; + var result, best = {}; + var min = Number.POSITIVE_INFINITY; + if(geometry instanceof OpenLayers.Geometry.Point) { + var segs = this.getSortedSegments(); + var x = geometry.x; + var y = geometry.y; + var seg; + for(var i=0, len=segs.length; i<len; ++i) { + seg = segs[i]; + result = OpenLayers.Geometry.distanceToSegment(geometry, seg); + if(result.distance < min) { + min = result.distance; + best = result; + if(min === 0) { + break; + } + } else { + // if distance increases and we cross y0 to the right of x0, no need to keep looking. + if(seg.x2 > x && ((y > seg.y1 && y < seg.y2) || (y < seg.y1 && y > seg.y2))) { + break; + } + } + } + if(details) { + best = { + distance: best.distance, + x0: best.x, y0: best.y, + x1: x, y1: y + }; + } else { + best = best.distance; + } + } else if(geometry instanceof OpenLayers.Geometry.LineString) { + var segs0 = this.getSortedSegments(); + var segs1 = geometry.getSortedSegments(); + var seg0, seg1, intersection, x0, y0; + var len1 = segs1.length; + var interOptions = {point: true}; + outer: for(var i=0, len=segs0.length; i<len; ++i) { + seg0 = segs0[i]; + x0 = seg0.x1; + y0 = seg0.y1; + for(var j=0; j<len1; ++j) { + seg1 = segs1[j]; + intersection = OpenLayers.Geometry.segmentsIntersect(seg0, seg1, interOptions); + if(intersection) { + min = 0; + best = { + distance: 0, + x0: intersection.x, y0: intersection.y, + x1: intersection.x, y1: intersection.y + }; + break outer; + } else { + result = OpenLayers.Geometry.distanceToSegment({x: x0, y: y0}, seg1); + if(result.distance < min) { + min = result.distance; + best = { + distance: min, + x0: x0, y0: y0, + x1: result.x, y1: result.y + }; + } + } + } + } + if(!details) { + best = best.distance; + } + if(min !== 0) { + // check the final vertex in this line's sorted segments + if(seg0) { + result = geometry.distanceTo( + new OpenLayers.Geometry.Point(seg0.x2, seg0.y2), + options + ); + var dist = details ? result.distance : result; + if(dist < min) { + if(details) { + best = { + distance: min, + x0: result.x1, y0: result.y1, + x1: result.x0, y1: result.y0 + }; + } else { + best = dist; + } + } + } + } + } else { + best = geometry.distanceTo(this, options); + // swap since target comes from this line + if(details) { + best = { + distance: best.distance, + x0: best.x1, y0: best.y1, + x1: best.x0, y1: best.y0 + }; + } + } + return best; + }, + + /** + * APIMethod: simplify + * This function will return a simplified LineString. + * Simplification is based on the Douglas-Peucker algorithm. + * + * + * Parameters: + * tolerance - {number} threshhold for simplification in map units + * + * Returns: + * {OpenLayers.Geometry.LineString} the simplified LineString + */ + simplify: function(tolerance){ + if (this && this !== null) { + var points = this.getVertices(); + if (points.length < 3) { + return this; + } + + var compareNumbers = function(a, b){ + return (a-b); + }; + + /** + * Private function doing the Douglas-Peucker reduction + */ + var douglasPeuckerReduction = function(points, firstPoint, lastPoint, tolerance){ + var maxDistance = 0; + var indexFarthest = 0; + + for (var index = firstPoint, distance; index < lastPoint; index++) { + distance = perpendicularDistance(points[firstPoint], points[lastPoint], points[index]); + if (distance > maxDistance) { + maxDistance = distance; + indexFarthest = index; + } + } + + if (maxDistance > tolerance && indexFarthest != firstPoint) { + //Add the largest point that exceeds the tolerance + pointIndexsToKeep.push(indexFarthest); + douglasPeuckerReduction(points, firstPoint, indexFarthest, tolerance); + douglasPeuckerReduction(points, indexFarthest, lastPoint, tolerance); + } + }; + + /** + * Private function calculating the perpendicular distance + * TODO: check whether OpenLayers.Geometry.LineString::distanceTo() is faster or slower + */ + var perpendicularDistance = function(point1, point2, point){ + //Area = |(1/2)(x1y2 + x2y3 + x3y1 - x2y1 - x3y2 - x1y3)| *Area of triangle + //Base = v((x1-x2)²+(x1-x2)²) *Base of Triangle* + //Area = .5*Base*H *Solve for height + //Height = Area/.5/Base + + var area = Math.abs(0.5 * (point1.x * point2.y + point2.x * point.y + point.x * point1.y - point2.x * point1.y - point.x * point2.y - point1.x * point.y)); + var bottom = Math.sqrt(Math.pow(point1.x - point2.x, 2) + Math.pow(point1.y - point2.y, 2)); + var height = area / bottom * 2; + + return height; + }; + + var firstPoint = 0; + var lastPoint = points.length - 1; + var pointIndexsToKeep = []; + + //Add the first and last index to the keepers + pointIndexsToKeep.push(firstPoint); + pointIndexsToKeep.push(lastPoint); + + //The first and the last point cannot be the same + while (points[firstPoint].equals(points[lastPoint])) { + lastPoint--; + //Addition: the first point not equal to first point in the LineString is kept as well + pointIndexsToKeep.push(lastPoint); + } + + douglasPeuckerReduction(points, firstPoint, lastPoint, tolerance); + var returnPoints = []; + pointIndexsToKeep.sort(compareNumbers); + for (var index = 0; index < pointIndexsToKeep.length; index++) { + returnPoints.push(points[pointIndexsToKeep[index]]); + } + return new OpenLayers.Geometry.LineString(returnPoints); + + } + else { + return this; + } + }, + + CLASS_NAME: "OpenLayers.Geometry.LineString" +}); |