RouteBoxer

The RouteBoxer class generates a set of LatLngBounds objects that are guaranteed to cover every point within a specified distance of a path, such as that generated for a route by the DirectionsService class. The primary use case for this class is to support implementing Search along a route against a Spatial db that supports bounding box queries.

Note that it is not the intention of the class to limit the bounding boxes to only those regions within the specified distance of the route, which is not possible given that routes are not rectangular. Consequently searches performed using these bounding boxes may return results up to ~3x the given distance from the route (twice the distance across the diagonal of a square with sides of the given distance).

How to use the class

To use the RouteBoxer class, first load the RouteBoxer.js file into your page:

<script type="text/javascript" src="../../routeboxer/src/RouteBoxer.js"></script>

Then create a RouteBoxer object, and pass an array of google.maps.LatLng objects and a distance to the RouteBoxer.box() method. If implementing search along a route the overview_polyline property of a google.maps.DirectionsRoute object contains a suitable array of LatLng objects:

var directionService = new google.maps.DirectionsService();
var rboxer = new RouteBoxer();
var distance = 20; // km

directionService.route(request, function(result, status) {
  if (status == google.maps.DirectionsStatus.OK) {

    // Box the overview path of the first route
    var path = result.routes[0].overview_path;
    var boxes = routeBoxer.box(path, distance);

    for (var i = 0; i < boxes.length; i++) {
      var bounds = box[i];
      // Perform search over this bounds
    }
  }
});

To visualise the boxes generated for a given route see the example.

How the RouteBoxer class works

The RouteBoxer class generates the boxes for a route in a number of steps.

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

Step 7

Step 8

Step 9

Step 10

A grid is overlaid on the route with square cells spaced at the specified distance. The grid is centered on the bounding box of the route polyline, and extends one cell further out in each direction than is necessary to cover the entire route.

Every cell in the grid that the route intersects with is identified. To do this the vertices on the route polyline are traversed, and the cell containing each vertex is marked. If a cell that is marked does not share an edge with the cell for the previous vertex, the intermediate cells are also marked.

When a cell is marked, each of the 8 cells surrounding it are also marked.

When all of the route vertices have been traversed, any point within the specified distance of the route is guaranteed to be in one of the marked cells of the grid.

The marked cells are then merged into a set of non overlapping rectangular boxes. Two different approaches are taken to this. The first approach merges cells that adjoin horizontally into a set of wide boxes, each one cell tall.

Each box is then compared to the boxes on the row below, and if there is a box of the same width and horizontal position they are merged.

The second approach follows the same technique, but first merges cells vertically into a set of tall boxes, each one cell wide.

Each of these boxes are then compared with the boxes in the column to the left, and if there is a box with the same height and vertical position they are merged.

When the two approaches are complete the number of boxes that resulted from each approach are compared.

The set of boxes that is smallest in number are returned to the application.