/* Copyright (c) 2006-2010 by OpenLayers Contributors (see authors.txt for
* full list of contributors). Published under the Clear BSD license.
* See http://svn.openlayers.org/trunk/openlayers/license.txt 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
*
*/
initialize: function(points) {
OpenLayers.Geometry.Curve.prototype.initialize.apply(this, arguments);
},
/**
* 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
*/
removeComponent: function(point) {
if ( this.components && (this.components.length > 2)) {
OpenLayers.Geometry.Collection.prototype.removeComponent.apply(this,
arguments);
}
},
/**
* 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;
},
CLASS_NAME: "OpenLayers.Geometry.LineString"
});