1/** 2 * @name RouteBoxer 3 * @version 1.0 4 * @copyright (c) 2010 Google Inc. 5 * @author Thor Mitchell 6 * 7 * @fileoverview The RouteBoxer class takes a path, such as the Polyline for a 8 * route generated by a Directions request, and generates a set of LatLngBounds 9 * objects that are guaranteed to contain every point within a given distance 10 * of that route. These LatLngBounds objects can then be used to generate 11 * requests to spatial search services that support bounds filtering (such as 12 * the Google Maps Data API) in order to implement search along a route. 13 * <br/><br/> 14 * RouteBoxer overlays a grid of the specified size on the route, identifies 15 * every grid cell that the route passes through, and generates a set of bounds 16 * that cover all of these cells, and their nearest neighbours. Consequently 17 * the bounds returned will extend up to ~3x the specified distance from the 18 * route in places. 19 */ 20 21/* 22 * Licensed under the Apache License, Version 2.0 (the "License"); 23 * you may not use this file except in compliance with the License. 24 * You may obtain a copy of the License at 25 * 26 * http://www.apache.org/licenses/LICENSE-2.0 27 * 28 * Unless required by applicable law or agreed to in writing, software 29 * distributed under the License is distributed on an "AS IS" BASIS, 30 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 31 * See the License for the specific language governing permissions and 32 * limitations under the License. 33 */ 34 35/** 36 * Creates a new RouteBoxer 37 * 38 * @constructor 39 */ 40function RouteBoxer() { 41 this.R = 6371; // earth's mean radius in km 42} 43 44/** 45 * Generates boxes for a given route and distance 46 * 47 * @param {google.maps.LatLng[] | google.maps.Polyline} path The path along 48 * which to create boxes. The path object can be either an Array of 49 * google.maps.LatLng objects or a Maps API v2 or Maps API v3 50 * google.maps.Polyline object. 51 * @param {Number} range The distance in kms around the route that the generated 52 * boxes must cover. 53 * @return {google.maps.LatLngBounds[]} An array of boxes that covers the whole 54 * path. 55 */ 56RouteBoxer.prototype.box = function (path, range) { 57 // Two dimensional array representing the cells in the grid overlaid on the path 58 this.grid_ = null; 59 60 // Array that holds the latitude coordinate of each vertical grid line 61 this.latGrid_ = []; 62 63 // Array that holds the longitude coordinate of each horizontal grid line 64 this.lngGrid_ = []; 65 66 // Array of bounds that cover the whole route formed by merging cells that 67 // the route intersects first horizontally, and then vertically 68 this.boxesX_ = []; 69 70 // Array of bounds that cover the whole route formed by merging cells that 71 // the route intersects first vertically, and then horizontally 72 this.boxesY_ = []; 73 74 // The array of LatLngs representing the vertices of the path 75 var vertices = null; 76 77 // If necessary convert the path into an array of LatLng objects 78 if (path instanceof Array) { 79 // already an arry of LatLngs (eg. v3 overview_path) 80 vertices = path; 81 } else if (path instanceof google.maps.Polyline) { 82 if (path.getPath) { 83 // v3 Maps API Polyline object 84 vertices = new Array(path.getPath().getLength()); 85 for (var i = 0; i < vertices.length; i++) { 86 vertices[i] = path.getPath().getAt(i); 87 } 88 } else { 89 // v2 Maps API Polyline object 90 vertices = new Array(path.getVertexCount()); 91 for (var j = 0; j < vertices.length; j++) { 92 vertices[j] = path.getVertex(j); 93 } 94 } 95 } 96 97 // Build the grid that is overlaid on the route 98 this.buildGrid_(vertices, range); 99 100 // Identify the grid cells that the route intersects 101 this.findIntersectingCells_(vertices); 102 103 // Merge adjacent intersected grid cells (and their neighbours) into two sets 104 // of bounds, both of which cover them completely 105 this.mergeIntersectingCells_(); 106 107 // Return the set of merged bounds that has the fewest elements 108 return (this.boxesX_.length <= this.boxesY_.length ? 109 this.boxesX_ : 110 this.boxesY_); 111}; 112 113/** 114 * Generates boxes for a given route and distance 115 * 116 * @param {LatLng[]} vertices The vertices of the path over which to lay the grid 117 * @param {Number} range The spacing of the grid cells. 118 */ 119RouteBoxer.prototype.buildGrid_ = function (vertices, range) { 120 121 // Create a LatLngBounds object that contains the whole path 122 var routeBounds = new google.maps.LatLngBounds(); 123 for (var i = 0; i < vertices.length; i++) { 124 routeBounds.extend(vertices[i]); 125 } 126 127 // Find the center of the bounding box of the path 128 var routeBoundsCenter = routeBounds.getCenter(); 129 130 // Starting from the center define grid lines outwards vertically until they 131 // extend beyond the edge of the bounding box by more than one cell 132 this.latGrid_.push(routeBoundsCenter.lat()); 133 134 // Add lines from the center out to the north
135 this.latGrid_.push(routeBoundsCenter.rhumbDestinationPoint(0, range).lat()); 136 for (i = 2; this.latGrid_[i - 2] < routeBounds.getNorthEast().lat(); i++) { 137 this.latGrid_.push(routeBoundsCenter.rhumbDestinationPoint(0, range * i).lat()); 138 } 139 140 // Add lines from the center out to the south 141 for (i = 1; this.latGrid_[1] > routeBounds.getSouthWest().lat(); i++) { 142 this.latGrid_.unshift(routeBoundsCenter.rhumbDestinationPoint(180, range * i).lat()); 143 } 144 145 // Starting from the center define grid lines outwards horizontally until they 146 // extend beyond the edge of the bounding box by more than one cell 147 this.lngGrid_.push(routeBoundsCenter.lng()); 148 149 // Add lines from the center out to the east 150 this.lngGrid_.push(routeBoundsCenter.rhumbDestinationPoint(90, range).lng()); 151 for (i = 2; this.lngGrid_[i - 2] < routeBounds.getNorthEast().lng(); i++) { 152 this.lngGrid_.push(routeBoundsCenter.rhumbDestinationPoint(90, range * i).lng()); 153 } 154 155 // Add lines from the center out to the west 156 for (i = 1; this.lngGrid_[1] >
156 routeBounds.getSouthWest().lng(); i++) { 157 this.lngGrid_.unshift(routeBoundsCenter.rhumbDestinationPoint(270, range * i).lng()); 158 } 159 160 // Create a two dimensional array representing this grid 161 this.grid_ = new Array(this.lngGrid_.length); 162 for (i = 0; i < this.grid_.length; i++) { 163 this.grid_[i] = new Array(this.latGrid_.length); 164 } 165}; 166 167/** 168 * Find all of the cells in the overlaid grid that the path intersects 169 * 170 * @param {LatLng[]} vertices The vertices of the path 171 */ 172RouteBoxer.prototype.findIntersectingCells_ = function (vertices) { 173 // Find the cell where the path begins 174 var hintXY = this.getCellCoords_(vertices[0]); 175 176 // Mark that cell and it's neighbours for inclusion in the boxes 177 this.markCell_(hintXY); 178 179 // Work through each vertex on the path identifying which grid cell it is in 180 for (var i = 1; i < vertices.length; i++) { 181 // Use the known cell of the previous vertex to help find the cell of this vertex 182 var gridXY = this.getGridCoordsFromHint_(vertices[i], vertices[i - 1], hintXY); 183 184 if (gridXY[0] === hintXY[0] && gridXY[1] === hintXY[1]) { 185 // This vertex is in the same cell as the previous vertex 186 // The cell will already have been marked for inclusion in the boxes 187 continue; 188 189 } else if ((Math.abs(hintXY[0] - gridXY[0]) === 1 && hintXY[1] === gridXY[1]) || 190 (hintXY[0] === gridXY[0] && Math.abs(hintXY[1] - gridXY[1]) === 1)) { 191 // This vertex is in a cell that shares an edge with the previous cell 192 // Mark this cell and it's neighbours for inclusion in the boxes 193 this.markCell_(gridXY); 194 195 } else { 196 // This vertex is in a cell that does not share an edge with the previous 197 // cell. This means that the path passes through other cells between 198 // this vertex and the previous vertex, and we must determine which cells 199 // it passes through 200 this.getGridIntersects_(vertices[i - 1], vertices[i], hintXY, gridXY); 201 } 202 203 // Use this cell to find and compare with the next one 204 hintXY = gridXY; 205 } 206}; 207 208/** 209 * Find the cell a path vertex is in by brute force iteration over the grid 210 * 211 * @param {LatLng[]} latlng The latlng of the vertex 212 * @return {Number[][]} The cell coordinates of this vertex in the grid 213 */ 214RouteBoxer.prototype.getCellCoords_ = function (latlng) { 215 for (var x = 0; this.lngGrid_[x] < latlng.lng(); x++) {} 216 for (var y = 0; this.latGrid_[y] < latlng.lat(); y++) {} 217 return ([x - 1, y - 1]); 218}; 219 220/** 221 * Find the cell a path vertex is in based on the known location of a nearby 222 * vertex. This saves searching the whole grid when working through vertices 223 * on the polyline that are likely to be in close proximity to each other. 224 * 225 * @param {LatLng[]} latlng The latlng of the vertex to locate in the grid 226 * @param {LatLng[]} hintlatlng The latlng of the vertex with a known location 227 * @param {Number[]} hint The cell containing the vertex with a known location 228 * @return {Number[]} The cell coordinates of the vertex to locate in the grid 229 */ 230RouteBoxer.prototype.getGridCoordsFromHint_ = function (latlng, hintlatlng, hint) { 231 var x, y; 232 if (latlng.lng() > hintlatlng.lng()) { 233 for (x = hint[0]; this.lngGrid_[x + 1] < latlng.lng(); x++) {} 234 } else { 235 for (x = hint[0]; this.lngGrid_[x] > latlng.lng(); x--) {} 236 } 237 238 if (latlng.lat() > hintlatlng.lat()) { 239 for (y = hint[1]; this.latGrid_[y + 1] < latlng.lat(); y++) {} 240 } else { 241 for (y = hint[1]; this.latGrid_[y] > latlng.lat(); y--) {} 242 } 243 244 return ([x, y]); 245}; 246 247 248/** 249 * Identify the grid squares that a path segment between two vertices 250 * intersects with by: 251 * 1. Finding the bearing between the start and end of the segment 252 * 2. Using the delta between the lat of the start and the lat of each 253 * latGrid boundary to find the distance to each latGrid boundary 254 * 3. Finding the lng of the intersection of the line with each latGrid 255 * boundary using the distance to the intersection and bearing of the line 256 * 4. Determining the x-coord on the grid of the point of intersection 257 * 5. Filling in all squares between the x-coord of the previous intersection 258 * (or start) and the current one (or end) at the current y coordinate, 259 * which is known for the grid line being intersected 260 * 261 * @param {LatLng} start The latlng of the vertex at the start of the segment 262 * @param {LatLng} end The latlng of the vertex at the end of the segment 263 * @param {Number[]} startXY The cell containing the start vertex 264 * @param {Number[]} endXY The cell containing the vend vertex 265 */ 266RouteBoxer.prototype.getGridIntersects_ = function (start, end, startXY, endXY) { 267 var edgePoint, edgeXY, i; 268 var brng = start.rhumbBearingTo(end); // Step 1. 269 270 var hint = start; 271 var hintXY = startXY; 272 273 // Handle a line segment that travels south first 274 if (end.lat() > start.lat()) { 275 // Iterate over the east to west grid lines between the start and end cells 276 for (i = startXY[1] + 1; i <= endXY[1]; i++) { 277 // Find the latlng of the point where the path segment intersects with 278 // this grid line (Step 2 & 3) 279 edgePoint = this.getGridIntersect_(start, brng, this.latGrid_[i]); 280 281 // Find the cell containing this intersect point (Step 4) 282 edgeXY = this.getGridCoordsFromHint_(edgePoint, hint, hintXY); 283 284 // Mark every cell the path has crossed between this grid and the start, 285 // or the previous east to west grid line it crossed (Step 5) 286 this.fillInGridSquares_(hintXY[0], edgeXY[0], i - 1); 287 288 // Use the point where it crossed this grid line as the reference for the 289 // next iteration 290 hint = edgePoint; 291 hintXY = edgeXY; 292 } 293 294 // Mark every cell the path has crossed between the last east to west grid 295 // line it crossed and the end (Step 5) 296 this.fillInGridSquares_(hintXY[0], endXY[0], i - 1); 297 298 } else { 299 // Iterate over the east to west grid lines between the start and end cells 300 for (i = startXY[1]; i > endXY[1]; i--) { 301 // Find the latlng of the point where the path segment intersects with 302 // this grid line (Step 2 & 3) 303 edgePoint = this.getGridIntersect_(start, brng, this.latGrid_[i]); 304 305 // Find the cell containing this intersect point (Step 4) 306 edgeXY = this.getGridCoordsFromHint_(edgePoint, hint, hintXY); 307 308 // Mark every cell the path has crossed between this grid and the start, 309 // or the previous east to west grid line it crossed (Step 5) 310 this.fillInGridSquares_(hintXY[0], edgeXY[0], i); 311 312 // Use the point where it crossed this grid line as the reference for the 313 // next iteration 314 hint = edgePoint; 315 hintXY = edgeXY; 316 } 317 318 // Mark every cell the path has crossed between the last east to west grid 319 // line it crossed and the end (Step 5) 320 this.fillInGridSquares_(hintXY[0], endXY[0], i); 321 322 } 323}; 324 325/** 326 * Find the latlng at which a path segment intersects with a given 327 * line of latitude 328 * 329 * @param {LatLng} start The vertex at the start of the path segment 330 * @param {Number} brng The bearing of the line from start to end 331 * @param {Number} gridLineLat The latitude of the grid line being intersected 332 * @return {LatLng} The latlng of the point where the path segment intersects 333 * the grid line 334 */ 335RouteBoxer.prototype.getGridIntersect_ = function (start, brng, gridLineLat) { 336 var d = this.R * ((gridLineLat.toRad() - start.lat().toRad()) / Math.cos(brng.toRad()));
337 return start.rhumbDestinationPoint(brng, d); 338}; 339 340/** 341 * Mark all cells in a given row of the grid that lie between two columns 342 * for inclusion in the boxes 343 * 344 * @param {Number} startx The first column to include 345 * @param {Number} endx The last column to include 346 * @param {Number} y The row of the cells to include 347 */ 348RouteBoxer.prototype.fillInGridSquares_ = function (startx, endx, y) { 349 var x; 350 if (startx < endx) { 351 for (x = startx; x <= endx; x++) { 352 this.markCell_([x, y]); 353 } 354 } else { 355 for (x = startx; x >= endx; x--) { 356 this.markCell_([x, y]); 357 } 358 } 359}; 360 361/** 362 * Mark a cell and the 8 immediate neighbours for inclusion in the boxes 363 * 364 * @param {Number[]} square The cell to mark 365 */ 366RouteBoxer.prototype.markCell_ = function (cell) { 367 var x = cell[0]; 368 var y = cell[1]; 369 this.grid_[x - 1][y - 1] = 1; 370 this.grid_[x][y - 1] = 1; 371 this.grid_[x + 1][y - 1] = 1; 372 this.grid_[x - 1][y] = 1; 373 this.grid_[x][y] = 1; 374 this.grid_[x + 1][y] = 1; 375 this.grid_[x - 1][y + 1] = 1; 376 this.grid_[x][y + 1] = 1; 377 this.grid_[x + 1][y + 1] = 1; 378}; 379 380/** 381 * Create two sets of bounding boxes, both of which cover all of the cells that 382 * have been marked for inclusion. 383 * 384 * The first set is created by combining adjacent cells in the same column into 385 * a set of vertical rectangular boxes, and then combining boxes of the same 386 * height that are adjacent horizontally. 387 * 388 * The second set is created by combining adjacent cells in the same row into 389 * a set of horizontal rectangular boxes, and then combining boxes of the same 390 * width that are adjacent vertically. 391 * 392 */ 393RouteBoxer.prototype.mergeIntersectingCells_ = function () { 394 var x, y, box; 395 396 // The box we are currently expanding with new cells 397 var currentBox = null; 398 399 // Traverse the grid a row at a time 400 for (y = 0; y < this.grid_[0].length; y++) { 401 for (x = 0; x < this.grid_.length; x++) { 402 403 if (this.grid_[x][y]) { 404 // This cell is marked for inclusion. If the previous cell in this 405 // row was also marked for inclusion, merge this cell into it's box. 406 // Otherwise start a new box. 407 box = this.getCellBounds_([x, y]); 408 if (currentBox) { 409 currentBox.extend(box.getNorthEast()); 410 } else { 411 currentBox = box; 412 } 413 414 } else { 415 // This cell is not marked for inclusion. If the previous cell was 416 // marked for inclusion, merge it's box with a box that spans the same 417 // columns from the row below if possible. 418 this.mergeBoxesY_(currentBox); 419 currentBox = null; 420 } 421 } 422 // If the last cell was marked for inclusion, merge it's box with a matching 423 // box from the row below if possible. 424 this.mergeBoxesY_(currentBox); 425 currentBox = null; 426 } 427 428 // Traverse the grid a column at a time 429 for (x = 0; x < this.grid_.length; x++) { 430 for (y = 0; y < this.grid_[0].length; y++) { 431 if (this.grid_[x][y]) { 432 433 // This cell is marked for inclusion. If the previous cell in this 434 // column was also marked for inclusion, merge this cell into it's box. 435 // Otherwise start a new box. 436 if (currentBox) { 437 box = this.getCellBounds_([x, y]); 438 currentBox.extend(box.getNorthEast()); 439 } else { 440 currentBox = this.getCellBounds_([x, y]); 441 } 442 443 } else { 444 // This cell is not marked for inclusion. If the previous cell was 445 // marked for inclusion, merge it's box with a box that spans the same 446 // rows from the column to the left if possible. 447 this.mergeBoxesX_(currentBox); 448 currentBox = null; 449 450 } 451 } 452 // If the last cell was marked for inclusion, merge it's box with a matching 453 // box from the column to the left if possible. 454 this.mergeBoxesX_(currentBox); 455 currentBox = null; 456 } 457}; 458 459/** 460 * Search for an existing box in an adjacent row to the given box that spans the 461 * same set of columns and if one is found merge the given box into it. If one 462 * is not found, append this box to the list of existing boxes. 463 * 464 * @param {LatLngBounds} The box to merge 465 */ 466RouteBoxer.prototype.mergeBoxesX_ = function (box) { 467 if (box !== null) { 468 for (var i = 0; i < this.boxesX_.length; i++) { 469 if (this.boxesX_[i].getNorthEast().lng() === box.getSouthWest
469().lng() && 470 this.boxesX_[i].getSouthWest().lat() === box.getSouthWest().lat() && 471 this.boxesX_[i].getNorthEast().lat() === box.getNorthEast().lat()) { 472 this.boxesX_[i].extend(box.getNorthEast()); 473 return; 474 } 475 } 476 this.boxesX_.push(box); 477 } 478}; 479 480/** 481 * Search for an existing box in an adjacent column to the given box that spans 482 * the same set of rows and if one is found merge the given box into it. If one 483 * is not found, append this box to the list of existing boxes. 484 * 485 * @param {LatLngBounds} The box to merge 486 */ 487RouteBoxer.prototype.mergeBoxesY_ = function (box) { 488 if (box !== null) { 489 for (var i = 0; i < this.boxesY_.length; i++) { 490 if (this.boxesY_[i].getNorthEast().lat() === box.getSouthWest().lat() && 491 this.boxesY_[i].getSouthWest().lng() === box.getSouthWest().lng() && 492 this.boxesY_[i].getNorthEast().lng() === box.getNorthEast().lng()) { 493 this.boxesY_[i].extend(box.getNorthEast()); 494 return; 495 } 496 } 497 this.boxesY_.push(box); 498 } 499}; 500 501/** 502 * Obtain the LatLng of the origin of a cell on the grid 503 * 504 * @param {Number[]} cell The cell to lookup. 505 * @return {LatLng} The latlng of the origin of the cell. 506 */ 507RouteBoxer.prototype.getCellBounds_ = function (cell) { 508 return new google.maps.LatLngBounds( 509 new google.maps.LatLng(this.latGrid_[cell[1]], this.lngGrid_[cell[0]]), 510 new google.maps.LatLng(this.latGrid_[cell[1] + 1], this.lngGrid_[cell[0] + 1])); 511}; 512 513/* Based on the Latitude/longitude spherical geodesy formulae & scripts 514 at http://www.movable-type.co.uk/scripts/latlong.html 515 (c) Chris Veness 2002-2010 516*/ 517google.maps.LatLng.prototype.rhumbDestinationPoint = function (brng, dist) { 518 var R = 6371; // earth's mean radius in km 519 var d = parseFloat(dist) / R; // d = angular distance covered on earth's surface 520 var lat1 = this.lat().toRad(), lon1 = this.lng().toRad(); 521 brng = brng.toRad(); 522 523 var lat2 = lat1 + d * Math.cos(brng); 524 var dLat = lat2 - lat1; 525 var dPhi = Math.log(Math.tan(lat2 / 2 + Math.PI / 4) / Math.tan(lat1 / 2 + Math.PI / 4)); 526 var q = (Math.abs(dLat) > 1e-10) ? dLat / dPhi : Math.cos(lat1); 527 var dLon = d * Math.sin(brng) / q; 528 // check for going past the pole 529 if (Math.abs(lat2) > Math.PI / 2) { 530 lat2 = lat2 > 0 ? Math.PI - lat2 : - (Math.PI - lat2); 531 } 532 var lon2 = (lon1 + dLon + Math.PI) % (2 * Math.PI) - Math.PI; 533 534 if (isNaN(lat2) || isNaN(lon2)) { 535 return null; 536 } 537 return new google.maps.LatLng(lat2.toDeg(), lon2.toDeg()); 538}; 539 540google.maps.LatLng.prototype.rhumbBearingTo = function (dest) { 541 var dLon = (dest.lng() - this.lng()).toRad(); 542 var dPhi = Math.log(Math.tan(dest.lat().toRad() / 2 + Math.PI / 4) / Math.tan(this.lat().toRad() / 2 + Math.PI / 4)); 543 if (Math.abs(dLon) > Math.PI) { 544 dLon = dLon > 0 ? -(2 * Math.PI - dLon) : (2 * Math.PI + dLon); 545 } 546 return Math.atan2(dLon, dPhi).toBrng(); 547}; 548 549/** 550 * Extend the Number object to convert degrees to radians 551 * 552 * @return {Number} Bearing in radians 553 * @ignore 554 */ 555Number.prototype.toRad = function () { 556 return this * Math.PI / 180; 557}; 558 559/** 560 * Extend the Number object to convert radians to degrees 561 * 562 * @return {Number} Bearing in degrees 563 * @ignore 564 */ 565Number.prototype.toDeg = function () { 566 return this * 180 / Math.PI; 567}; 568 569/** 570 * Normalize a heading in degrees to between 0 and +360 571 * 572 * @return {Number} Return 573 * @ignore 574 */ 575Number.prototype.toBrng = function () { 576 return (this.toDeg() + 360) % 360; 577};
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.