1 /* Copyright (c) 2006-2008 MetaCarta, Inc., published under the Clear BSD
2 * license. See http://svn.openlayers.org/trunk/openlayers/license.txt for the
3 * full text of the license. */
6 * @requires OpenLayers/Geometry/Curve.js
10 * Class: OpenLayers.Geometry.LineString
11 * A LineString is a Curve which, once two points have been added to it, can
12 * never be less than two points long.
15 * - <OpenLayers.Geometry.Curve>
17 OpenLayers.Geometry.LineString = OpenLayers.Class(OpenLayers.Geometry.Curve, {
20 * Constructor: OpenLayers.Geometry.LineString
21 * Create a new LineString geometry
24 * points - {Array(<OpenLayers.Geometry.Point>)} An array of points used to
25 * generate the linestring
28 initialize: function(points) {
29 OpenLayers.Geometry.Curve.prototype.initialize.apply(this, arguments);
33 * APIMethod: removeComponent
34 * Only allows removal of a point if there are three or more points in
35 * the linestring. (otherwise the result would be just a single point)
38 * point - {<OpenLayers.Geometry.Point>} The point to be removed
40 removeComponent: function(point) {
41 if ( this.components && (this.components.length > 2)) {
42 OpenLayers.Geometry.Collection.prototype.removeComponent.apply(this,
48 * APIMethod: intersects
49 * Test for instersection between two geometries. This is a cheapo
50 * implementation of the Bently-Ottmann algorigithm. It doesn't
51 * really keep track of a sweep line data structure. It is closer
52 * to the brute force method, except that segments are sorted and
53 * potential intersections are only calculated when bounding boxes
57 * geometry - {<OpenLayers.Geometry>}
60 * {Boolean} The input geometry intersects this geometry.
62 intersects: function(geometry) {
63 var intersect = false;
64 var type = geometry.CLASS_NAME;
65 if(type == "OpenLayers.Geometry.LineString" ||
66 type == "OpenLayers.Geometry.LinearRing" ||
67 type == "OpenLayers.Geometry.Point") {
68 var segs1 = this.getSortedSegments();
70 if(type == "OpenLayers.Geometry.Point") {
72 x1: geometry.x, y1: geometry.y,
73 x2: geometry.x, y2: geometry.y
76 segs2 = geometry.getSortedSegments();
78 var seg1, seg1x1, seg1x2, seg1y1, seg1y2,
81 outer: for(var i=0, len=segs1.length; i<len; ++i) {
87 inner: for(var j=0, jlen=segs2.length; j<jlen; ++j) {
89 if(seg2.x1 > seg1x2) {
90 // seg1 still left of seg2
93 if(seg2.x2 < seg1x1) {
94 // seg2 still left of seg1
99 if(Math.min(seg2y1, seg2y2) > Math.max(seg1y1, seg1y2)) {
103 if(Math.max(seg2y1, seg2y2) < Math.min(seg1y1, seg1y2)) {
107 if(OpenLayers.Geometry.segmentsIntersect(seg1, seg2)) {
114 intersect = geometry.intersects(this);
120 * Method: getSortedSegments
123 * {Array} An array of segment objects. Segment objects have properties
124 * x1, y1, x2, and y2. The start point is represented by x1 and y1.
125 * The end point is represented by x2 and y2. Start and end are
126 * ordered so that x1 < x2.
128 getSortedSegments: function() {
129 var numSeg = this.components.length - 1;
130 var segments = new Array(numSeg);
131 for(var i=0; i<numSeg; ++i) {
132 point1 = this.components[i];
133 point2 = this.components[i + 1];
134 if(point1.x < point2.x) {
150 // more efficient to define this somewhere static
151 function byX1(seg1, seg2) {
152 return seg1.x1 - seg2.x1;
154 return segments.sort(byX1);
158 * Method: splitWithSegment
159 * Split this geometry with the given segment.
162 * seg - {Object} An object with x1, y1, x2, and y2 properties referencing
163 * segment endpoint coordinates.
164 * options - {Object} Properties of this object will be used to determine
165 * how the split is conducted.
168 * edge - {Boolean} Allow splitting when only edges intersect. Default is
169 * true. If false, a vertex on the source segment must be within the
170 * tolerance distance of the intersection to be considered a split.
171 * tolerance - {Number} If a non-null value is provided, intersections
172 * within the tolerance distance of one of the source segment's
173 * endpoints will be assumed to occur at the endpoint.
176 * {Object} An object with *lines* and *points* properties. If the given
177 * segment intersects this linestring, the lines array will reference
178 * geometries that result from the split. The points array will contain
179 * all intersection points. Intersection points are sorted along the
180 * segment (in order from x1,y1 to x2,y2).
182 splitWithSegment: function(seg, options) {
183 var edge = !(options && options.edge === false);
184 var tolerance = options && options.tolerance;
186 var verts = this.getVertices();
188 var intersections = [];
190 var vert1, vert2, point;
191 var node, vertex, target;
192 var interOptions = {point: true, tolerance: tolerance};
194 for(var i=0, stop=verts.length-2; i<=stop; ++i) {
196 points.push(vert1.clone());
198 target = {x1: vert1.x, y1: vert1.y, x2: vert2.x, y2: vert2.y};
199 point = OpenLayers.Geometry.segmentsIntersect(
200 seg, target, interOptions
202 if(point instanceof OpenLayers.Geometry.Point) {
203 if((point.x === seg.x1 && point.y === seg.y1) ||
204 (point.x === seg.x2 && point.y === seg.y2) ||
205 point.equals(vert1) || point.equals(vert2)) {
211 // push intersections different than the previous
212 if(!point.equals(intersections[intersections.length-1])) {
213 intersections.push(point.clone());
216 if(point.equals(vert1)) {
220 if(point.equals(vert2)) {
224 if(!point.equals(vert1)) {
227 lines.push(new OpenLayers.Geometry.LineString(points));
228 points = [point.clone()];
233 points.push(vert2.clone());
234 lines.push(new OpenLayers.Geometry.LineString(points));
236 if(intersections.length > 0) {
237 // sort intersections along segment
238 var xDir = seg.x1 < seg.x2 ? 1 : -1;
239 var yDir = seg.y1 < seg.y2 ? 1 : -1;
242 points: intersections.sort(function(p1, p2) {
243 return (xDir * p1.x - xDir * p2.x) || (yDir * p1.y - yDir * p2.y);
252 * Use this geometry (the source) to attempt to split a target geometry.
255 * target - {<OpenLayers.Geometry>} The target geometry.
256 * options - {Object} Properties of this object will be used to determine
257 * how the split is conducted.
260 * mutual - {Boolean} Split the source geometry in addition to the target
261 * geometry. Default is false.
262 * edge - {Boolean} Allow splitting when only edges intersect. Default is
263 * true. If false, a vertex on the source must be within the tolerance
264 * distance of the intersection to be considered a split.
265 * tolerance - {Number} If a non-null value is provided, intersections
266 * within the tolerance distance of an existing vertex on the source
267 * will be assumed to occur at the vertex.
270 * {Array} A list of geometries (of this same type as the target) that
271 * result from splitting the target with the source geometry. The
272 * source and target geometry will remain unmodified. If no split
273 * results, null will be returned. If mutual is true and a split
274 * results, return will be an array of two arrays - the first will be
275 * all geometries that result from splitting the source geometry and
276 * the second will be all geometries that result from splitting the
279 split: function(target, options) {
281 var mutual = options && options.mutual;
282 var sourceSplit, targetSplit, sourceParts, targetParts;
283 if(target instanceof OpenLayers.Geometry.LineString) {
284 var verts = this.getVertices();
285 var vert1, vert2, seg, splits, lines, point;
288 for(var i=0, stop=verts.length-2; i<=stop; ++i) {
292 x1: vert1.x, y1: vert1.y,
293 x2: vert2.x, y2: vert2.y
295 targetParts = targetParts || [target];
297 points.push(vert1.clone());
299 for(var j=0; j<targetParts.length; ++j) {
300 splits = targetParts[j].splitWithSegment(seg, options);
302 // splice in new features
303 lines = splits.lines;
304 if(lines.length > 0) {
306 Array.prototype.splice.apply(targetParts, lines);
307 j += lines.length - 2;
310 for(var k=0, len=splits.points.length; k<len; ++k) {
311 point = splits.points[k];
312 if(!point.equals(vert1)) {
314 sourceParts.push(new OpenLayers.Geometry.LineString(points));
315 if(point.equals(vert2)) {
318 points = [point.clone()];
326 if(mutual && sourceParts.length > 0 && points.length > 0) {
327 points.push(vert2.clone());
328 sourceParts.push(new OpenLayers.Geometry.LineString(points));
331 results = target.splitWith(this, options);
333 if(targetParts && targetParts.length > 1) {
338 if(sourceParts && sourceParts.length > 1) {
343 if(targetSplit || sourceSplit) {
345 results = [sourceParts, targetParts];
347 results = targetParts;
355 * Split this geometry (the target) with the given geometry (the source).
358 * geometry - {<OpenLayers.Geometry>} A geometry used to split this
359 * geometry (the source).
360 * options - {Object} Properties of this object will be used to determine
361 * how the split is conducted.
364 * mutual - {Boolean} Split the source geometry in addition to the target
365 * geometry. Default is false.
366 * edge - {Boolean} Allow splitting when only edges intersect. Default is
367 * true. If false, a vertex on the source must be within the tolerance
368 * distance of the intersection to be considered a split.
369 * tolerance - {Number} If a non-null value is provided, intersections
370 * within the tolerance distance of an existing vertex on the source
371 * will be assumed to occur at the vertex.
374 * {Array} A list of geometries (of this same type as the target) that
375 * result from splitting the target with the source geometry. The
376 * source and target geometry will remain unmodified. If no split
377 * results, null will be returned. If mutual is true and a split
378 * results, return will be an array of two arrays - the first will be
379 * all geometries that result from splitting the source geometry and
380 * the second will be all geometries that result from splitting the
383 splitWith: function(geometry, options) {
384 return geometry.split(this, options);
389 * APIMethod: getVertices
390 * Return a list of all points in this geometry.
393 * nodes - {Boolean} For lines, only return vertices that are
394 * endpoints. If false, for lines, only vertices that are not
395 * endpoints will be returned. If not provided, all vertices will
399 * {Array} A list of all vertices in the geometry.
401 getVertices: function(nodes) {
406 this.components[this.components.length-1]
408 } else if (nodes === false) {
409 vertices = this.components.slice(1, this.components.length-1);
411 vertices = this.components.slice();
417 * APIMethod: distanceTo
418 * Calculate the closest distance between two geometries (on the x-y plane).
421 * geometry - {<OpenLayers.Geometry>} The target geometry.
422 * options - {Object} Optional properties for configuring the distance
426 * details - {Boolean} Return details from the distance calculation.
428 * edge - {Boolean} Calculate the distance from this geometry to the
429 * nearest edge of the target geometry. Default is true. If true,
430 * calling distanceTo from a geometry that is wholly contained within
431 * the target will result in a non-zero distance. If false, whenever
432 * geometries intersect, calling distanceTo will return 0. If false,
433 * details cannot be returned.
436 * {Number | Object} The distance between this geometry and the target.
437 * If details is true, the return will be an object with distance,
438 * x0, y0, x1, and x2 properties. The x0 and y0 properties represent
439 * the coordinates of the closest point on this geometry. The x1 and y1
440 * properties represent the coordinates of the closest point on the
443 distanceTo: function(geometry, options) {
444 var edge = !(options && options.edge === false);
445 var details = edge && options && options.details;
446 var result, best = {};
447 var min = Number.POSITIVE_INFINITY;
448 if(geometry instanceof OpenLayers.Geometry.Point) {
449 var segs = this.getSortedSegments();
453 for(var i=0, len=segs.length; i<len; ++i) {
455 result = OpenLayers.Geometry.distanceToSegment(geometry, seg);
456 if(result.distance < min) {
457 min = result.distance;
463 // if distance increases and we cross y0 to the right of x0, no need to keep looking.
464 if(seg.x2 > x && ((y > seg.y1 && y < seg.y2) || (y < seg.y1 && y > seg.y2))) {
471 distance: best.distance,
472 x0: best.x, y0: best.y,
476 best = best.distance;
478 } else if(geometry instanceof OpenLayers.Geometry.LineString) {
479 var segs0 = this.getSortedSegments();
480 var segs1 = geometry.getSortedSegments();
481 var seg0, seg1, intersection, x0, y0;
482 var len1 = segs1.length;
483 var interOptions = {point: true};
484 outer: for(var i=0, len=segs0.length; i<len; ++i) {
488 for(var j=0; j<len1; ++j) {
490 intersection = OpenLayers.Geometry.segmentsIntersect(seg0, seg1, interOptions);
495 x0: intersection.x, y0: intersection.y,
496 x1: intersection.x, y1: intersection.y
500 result = OpenLayers.Geometry.distanceToSegment({x: x0, y: y0}, seg1);
501 if(result.distance < min) {
502 min = result.distance;
506 x1: result.x, y1: result.y
513 best = best.distance;
516 // check the final vertex in this line's sorted segments
518 result = geometry.distanceTo(
519 new OpenLayers.Geometry.Point(seg0.x2, seg0.y2),
522 var dist = details ? result.distance : result;
527 x0: result.x1, y0: result.y1,
528 x1: result.x0, y1: result.y0
537 best = geometry.distanceTo(this, options);
538 // swap since target comes from this line
541 distance: best.distance,
542 x0: best.x1, y0: best.y1,
543 x1: best.x0, y1: best.y0
550 CLASS_NAME: "OpenLayers.Geometry.LineString"