Lumatic Routing
At Lumatic, we’re reinventing the navigation experience from the ground up to be easy to use for pedestrians, cyclists and transit riders. On the back-end, we’re using existing services when we can, but we’re also not afraid to roll our own systems when we can’t.
When it comes to the actual routing algorithms, we’ve tried using all the existing services we can find, but they have all proven to be too limiting for one reason or another. For example, information about street crossings is usually not provided, even though this is an extremely useful tool for pedestrian navigation and affirmation.
In order to obtain the flexibility we desire, we’ve found it necessary to begin development of our own customized routing algorithms on top of Open Street Map (OSM). This is easier said than done, because OSM data is almost completely free form, unstructured, user-generated data. It consists of “nodes” and “ways,” which are simply lists of connected nodes. Ways could be used to store anything from census lines, to building polygons to pieces of walking paths, streets or highways, and the only way to know what’s what is to look at the tags, which are often not completely consistent.
It wasn’t easy, but we’ve developed robust algorithms for processing that jumble of data into a reliable graph structure. Here’s a sample view of the completed graph (green) overlaid on top of OSM (blue):
With the graph structure, everything becomes easier. We can now perform our own routing, which puts us on par with other services like Bing or Mapquest,
However, because we’re doing it ourselves, we can also get all the information we need about street crossings. We can correct errors in the underlying street data when we find them (Bing and other services are not perfect). We can even customize routing based on all sorts of things — don’t want to walk up hills? Want to take the scenic route? Want the quickest route, or the cheapest route, or some combination inbetween based on your preferences? Want the routing algorithm to steer around steep hills, or know that you have a Muni pass and take that into account when assessing public transportation options? These are all things that you can look forward to from us at Lumatic in the future.
- Stuart Heinrich, Chief Graphics and Computer Vision Engineer