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