Bounding boxes along a route, now as an Android libraryBounding boxes along a route, now as an Android library

• Take the bounding box of the whole route and extend it by one grid cell in every direction.
• Overlay a grid of square cells across that area, where the cell size follows the distance you asked for.
• Mark every cell that intersects a vertex of the route, along with the eight cells surrounding it.
• Merge the marked cells into as few non overlapping rectangles as the shape allows.

The merge step is where the practical value sits. Fewer rectangles means fewer lookups later, so the output is a compact cover of the corridor rather than a raw pile of grid squares.

RouteBoxer was originally a helper for maps in the browser. The authors ported it to Android because mobile developers had no equivalent, building the work on the Google Maps Android API inside Android Studio and shipping it as a library. It can be added to a project either as a compiled library file or as a source module.

One property of the algorithm deserves attention before use. The authors report that the number of generated boxes grows exponentially as the distance increases. A wider corridor is not a little more expensive, it is a lot more, so the distance parameter and the grid resolution are the two knobs to watch.