openlayers/lib/OpenLayers/Geometry/LineString.js

   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. */
   4
   5 /**
   6  * @requires OpenLayers/Geometry/Curve.js
   7  */
   8
   9 /**
  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.
  13  *
  14  * Inherits from:
  15  *  - <OpenLayers.Geometry.Curve>
  16  */
  17 OpenLayers.Geometry.LineString = OpenLayers.Class(OpenLayers.Geometry.Curve, {
  18
  19     /**
  20      * Constructor: OpenLayers.Geometry.LineString
  21      * Create a new LineString geometry
  22      *
  23      * Parameters:
  24      * points - {Array(<OpenLayers.Geometry.Point>)} An array of points used to
  25      *          generate the linestring
  26      *
  27      */
  28     initialize: function(points) {
  29         OpenLayers.Geometry.Curve.prototype.initialize.apply(this, arguments);
  30     },
  31
  32     /**
  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)
  36      *
  37      * Parameters:
  38      * point - {<OpenLayers.Geometry.Point>} The point to be removed
  39      */
  40     removeComponent: function(point) {
  41         if ( this.components && (this.components.length > 2)) {
  42             OpenLayers.Geometry.Collection.prototype.removeComponent.apply(this,
  43                                                                   arguments);
  44         }
  45     },
  46
  47     /**
  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
  54      *     intersect.
  55      *
  56      * Parameters:
  57      * geometry - {<OpenLayers.Geometry>}
  58      *
  59      * Returns:
  60      * {Boolean} The input geometry intersects this geometry.
  61      */
  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();
  69             var segs2;
  70             if(type == "OpenLayers.Geometry.Point") {
  71                 segs2 = [{
  72                     x1: geometry.x, y1: geometry.y,
  73                     x2: geometry.x, y2: geometry.y
  74                 }];
  75             } else {
  76                 segs2 = geometry.getSortedSegments();
  77             }
  78             var seg1, seg1x1, seg1x2, seg1y1, seg1y2,
  79                 seg2, seg2y1, seg2y2;
  80             // sweep right
  81             outer: for(var i=0, len=segs1.length; i<len; ++i) {
  82                 seg1 = segs1[i];
  83                 seg1x1 = seg1.x1;
  84                 seg1x2 = seg1.x2;
  85                 seg1y1 = seg1.y1;
  86                 seg1y2 = seg1.y2;
  87                 inner: for(var j=0, jlen=segs2.length; j<jlen; ++j) {
  88                     seg2 = segs2[j];
  89                     if(seg2.x1 > seg1x2) {
  90                         // seg1 still left of seg2
  91                         break;
  92                     }
  93                     if(seg2.x2 < seg1x1) {
  94                         // seg2 still left of seg1
  95                         continue;
  96                     }
  97                     seg2y1 = seg2.y1;
  98                     seg2y2 = seg2.y2;
  99                     if(Math.min(seg2y1, seg2y2) > Math.max(seg1y1, seg1y2)) {
 100                         // seg2 above seg1
 101                         continue;
 102                     }
 103                     if(Math.max(seg2y1, seg2y2) < Math.min(seg1y1, seg1y2)) {
 104                         // seg2 below seg1
 105                         continue;
 106                     }
 107                     if(OpenLayers.Geometry.segmentsIntersect(seg1, seg2)) {
 108                         intersect = true;
 109                         break outer;
 110                     }
 111                 }
 112             }
 113         } else {
 114             intersect = geometry.intersects(this);
 115         }
 116         return intersect;
 117     },
 118
 119     /**
 120      * Method: getSortedSegments
 121      *
 122      * Returns:
 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.
 127      */
 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) {
 135                 segments[i] = {
 136                     x1: point1.x,
 137                     y1: point1.y,
 138                     x2: point2.x,
 139                     y2: point2.y
 140                 };
 141             } else {
 142                 segments[i] = {
 143                     x1: point2.x,
 144                     y1: point2.y,
 145                     x2: point1.x,
 146                     y2: point1.y
 147                 };
 148             }
 149         }
 150         // more efficient to define this somewhere static
 151         function byX1(seg1, seg2) {
 152             return seg1.x1 - seg2.x1;
 153         }
 154         return segments.sort(byX1);
 155     },
 156
 157     /**
 158      * Method: splitWithSegment
 159      * Split this geometry with the given segment.
 160      *
 161      * Parameters:
 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.
 166      *
 167      * Valid options:
 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.
 174      *
 175      * Returns:
 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).
 181      */
 182     splitWithSegment: function(seg, options) {
 183         var edge = !(options && options.edge === false);
 184         var tolerance = options && options.tolerance;
 185         var lines = [];
 186         var verts = this.getVertices();
 187         var points = [];
 188         var intersections = [];
 189         var split = false;
 190         var vert1, vert2, point;
 191         var node, vertex, target;
 192         var interOptions = {point: true, tolerance: tolerance};
 193         var result = null;
 194         for(var i=0, stop=verts.length-2; i<=stop; ++i) {
 195             vert1 = verts[i];
 196             points.push(vert1.clone());
 197             vert2 = verts[i+1];
 198             target = {x1: vert1.x, y1: vert1.y, x2: vert2.x, y2: vert2.y};
 199             point = OpenLayers.Geometry.segmentsIntersect(
 200                 seg, target, interOptions
 201             );
 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)) {
 206                     vertex = true;
 207                 } else {
 208                     vertex = false;
 209                 }
 210                 if(vertex || edge) {
 211                     // push intersections different than the previous
 212                     if(!point.equals(intersections[intersections.length-1])) {
 213                         intersections.push(point.clone());
 214                     }
 215                     if(i === 0) {
 216                         if(point.equals(vert1)) {
 217                             continue;
 218                         }
 219                     }
 220                     if(point.equals(vert2)) {
 221                         continue;
 222                     }
 223                     split = true;
 224                     if(!point.equals(vert1)) {
 225                         points.push(point);
 226                     }
 227                     lines.push(new OpenLayers.Geometry.LineString(points));
 228                     points = [point.clone()];
 229                 }
 230             }
 231         }
 232         if(split) {
 233             points.push(vert2.clone());
 234             lines.push(new OpenLayers.Geometry.LineString(points));
 235         }
 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;
 240             result = {
 241                 lines: lines,
 242                 points: intersections.sort(function(p1, p2) {
 243                     return (xDir * p1.x - xDir * p2.x) || (yDir * p1.y - yDir * p2.y);
 244                 })
 245             };
 246         }
 247         return result;
 248     },
 249
 250     /**
 251      * Method: split
 252      * Use this geometry (the source) to attempt to split a target geometry.
 253      *
 254      * Parameters:
 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.
 258      *
 259      * Valid options:
 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.
 268      *
 269      * Returns:
 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
 277      *     target geometry.
 278      */
 279     split: function(target, options) {
 280         var results = null;
 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;
 286             var points = [];
 287             sourceParts = [];
 288             for(var i=0, stop=verts.length-2; i<=stop; ++i) {
 289                 vert1 = verts[i];
 290                 vert2 = verts[i+1];
 291                 seg = {
 292                     x1: vert1.x, y1: vert1.y,
 293                     x2: vert2.x, y2: vert2.y
 294                 };
 295                 targetParts = targetParts || [target];
 296                 if(mutual) {
 297                     points.push(vert1.clone());
 298                 }
 299                 for(var j=0; j<targetParts.length; ++j) {
 300                     splits = targetParts[j].splitWithSegment(seg, options);
 301                     if(splits) {
 302                         // splice in new features
 303                         lines = splits.lines;
 304                         if(lines.length > 0) {
 305                             lines.unshift(j, 1);
 306                             Array.prototype.splice.apply(targetParts, lines);
 307                             j += lines.length - 2;
 308                         }
 309                         if(mutual) {
 310                             for(var k=0, len=splits.points.length; k<len; ++k) {
 311                                 point = splits.points[k];
 312                                 if(!point.equals(vert1)) {
 313                                     points.push(point);
 314                                     sourceParts.push(new OpenLayers.Geometry.LineString(points));
 315                                     if(point.equals(vert2)) {
 316                                         points = [];
 317                                     } else {
 318                                         points = [point.clone()];
 319                                     }
 320                                 }
 321                             }
 322                         }
 323                     }
 324                 }
 325             }
 326             if(mutual && sourceParts.length > 0 && points.length > 0) {
 327                 points.push(vert2.clone());
 328                 sourceParts.push(new OpenLayers.Geometry.LineString(points));
 329             }
 330         } else {
 331             results = target.splitWith(this, options);
 332         }
 333         if(targetParts && targetParts.length > 1) {
 334             targetSplit = true;
 335         } else {
 336             targetParts = [];
 337         }
 338         if(sourceParts && sourceParts.length > 1) {
 339             sourceSplit = true;
 340         } else {
 341             sourceParts = [];
 342         }
 343         if(targetSplit || sourceSplit) {
 344             if(mutual) {
 345                 results = [sourceParts, targetParts];
 346             } else {
 347                 results = targetParts;
 348             }
 349         }
 350         return results;
 351     },
 352
 353     /**
 354      * Method: splitWith
 355      * Split this geometry (the target) with the given geometry (the source).
 356      *
 357      * Parameters:
 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.
 362      *
 363      * Valid options:
 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.
 372      *
 373      * Returns:
 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
 381      *     target geometry.
 382      */
 383     splitWith: function(geometry, options) {
 384         return geometry.split(this, options);
 385
 386     },
 387
 388     /**
 389      * APIMethod: getVertices
 390      * Return a list of all points in this geometry.
 391      *
 392      * Parameters:
 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
 396      *     be returned.
 397      *
 398      * Returns:
 399      * {Array} A list of all vertices in the geometry.
 400      */
 401     getVertices: function(nodes) {
 402         var vertices;
 403         if(nodes === true) {
 404             vertices = [
 405                 this.components[0],
 406                 this.components[this.components.length-1]
 407             ];
 408         } else if (nodes === false) {
 409             vertices = this.components.slice(1, this.components.length-1);
 410         } else {
 411             vertices = this.components.slice();
 412         }
 413         return vertices;
 414     },
 415
 416     /**
 417      * APIMethod: distanceTo
 418      * Calculate the closest distance between two geometries (on the x-y plane).
 419      *
 420      * Parameters:
 421      * geometry - {<OpenLayers.Geometry>} The target geometry.
 422      * options - {Object} Optional properties for configuring the distance
 423      *     calculation.
 424      *
 425      * Valid options:
 426      * details - {Boolean} Return details from the distance calculation.
 427      *     Default is false.
 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.
 434      *
 435      * Returns:
 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
 441      *     target geometry.
 442      */
 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();
 450             var x = geometry.x;
 451             var y = geometry.y;
 452             var seg;
 453             for(var i=0, len=segs.length; i<len; ++i) {
 454                 seg = segs[i];
 455                 result = OpenLayers.Geometry.distanceToSegment(geometry, seg);
 456                 if(result.distance < min) {
 457                     min = result.distance;
 458                     best = result;
 459                     if(min === 0) {
 460                         break;
 461                     }
 462                 } else {
 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))) {
 465                         break;
 466                     }
 467                 }
 468             }
 469             if(details) {
 470                 best = {
 471                     distance: best.distance,
 472                     x0: best.x, y0: best.y,
 473                     x1: x, y1: y
 474                 };
 475             } else {
 476                 best = best.distance;
 477             }
 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) {
 485                 seg0 = segs0[i];
 486                 x0 = seg0.x1;
 487                 y0 = seg0.y1;
 488                 for(var j=0; j<len1; ++j) {
 489                     seg1 = segs1[j];
 490                     intersection = OpenLayers.Geometry.segmentsIntersect(seg0, seg1, interOptions);
 491                     if(intersection) {
 492                         min = 0;
 493                         best = {
 494                             distance: 0,
 495                             x0: intersection.x, y0: intersection.y,
 496                             x1: intersection.x, y1: intersection.y
 497                         };
 498                         break outer;
 499                     } else {
 500                         result = OpenLayers.Geometry.distanceToSegment({x: x0, y: y0}, seg1);
 501                         if(result.distance < min) {
 502                             min = result.distance;
 503                             best = {
 504                                 distance: min,
 505                                 x0: x0, y0: y0,
 506                                 x1: result.x, y1: result.y
 507                             };
 508                         }
 509                     }
 510                 }
 511             }
 512             if(!details) {
 513                 best = best.distance;
 514             }
 515             if(min !== 0) {
 516                 // check the final vertex in this line's sorted segments
 517                 if(seg0) {
 518                     result = geometry.distanceTo(
 519                         new OpenLayers.Geometry.Point(seg0.x2, seg0.y2),
 520                         options
 521                     );
 522                     var dist = details ? result.distance : result;
 523                     if(dist < min) {
 524                         if(details) {
 525                             best = {
 526                                 distance: min,
 527                                 x0: result.x1, y0: result.y1,
 528                                 x1: result.x0, y1: result.y0
 529                             };
 530                         } else {
 531                             best = dist;
 532                         }
 533                     }
 534                 }
 535             }
 536         } else {
 537             best = geometry.distanceTo(this, options);
 538             // swap since target comes from this line
 539             if(details) {
 540                 best = {
 541                     distance: best.distance,
 542                     x0: best.x1, y0: best.y1,
 543                     x1: best.x0, y1: best.y0
 544                 };
 545             }
 546         }
 547         return best;
 548     },
 549
 550     CLASS_NAME: "OpenLayers.Geometry.LineString"
 551 });