OpenTripPlanner is a multimodal trip planner that lets you plan a trip where you ride your bike to a train, put your bike on the train, then walk your bike on the sidewalk of a one-way street for the last quarter-block of your journey.
A few days ago, I finished adding area routing to OpenTripPlanner. In New York, we don’t see a lot of large pedestrian areas; Central Park doesn’t count because it has paths through it and is otherwise not really a great shortcut due to terrain. But in Venice, there is the famous Piazza San Marco, along with many other pedestrian plazas. Here, it makes sense to make a diagonal trip and shave a few minutes off your journey. And that is now what OTP can do:
Here’s how it works on the inside:
First, you need to know that OTP represents its network as a graph — a collection of vertices connected by weighted, directional edges. Typically, vertices are intersections and edges are sections of streets, although in the transit portion of the graph, transit stops are each several vertices and links between consecutive stops are edges. Here’s a diagram by Andrew Byrd showing a sample of the network structure:
The central question of routing is: what is the shortest path between two vertices? For multimodal routing, the shortest path will depend on whether one is walking or biking, and, for transit, what time of day it is. We also attempt to incorporate user preferences to avoid trips with many transfers, as well as preferences about maximum walking distance, wheelchair accessibility, and bicycling routes (fast vs bike lanes vs least hills). Every edge has several costs associated with it, representing the time it will take to traverse the edge as well as any inconvenience factors such as hills. This means that “shortest” really means “least cost”, where cost is some combination of time and other factors. To find this path, we search the graph, updating our state as we go. Our state includes information like whether we are on a bus, how many transfers we have taken, and how far we have walked.
The naive approach to area routing would be to simply treat each area as a really big vertex; all of the incoming streets (edges) would be connected to it, and it would internally figure out the straight-line distance from incoming edge to outgoing edge and compute a cost based on that distance. This would work well for convex polygons, but for concave polygons or polygons with holes (e.g. the Starbucks in the middle of Pioneer Square in Portland), you might need to take a complicated path. This is the case in the Piazza San Marco, although an error in the OSM prevents me from demonstrating it for you there. In the case of a horseshoe-shaped area, you might need to cross the same area twice; typically, visiting the same vertex twice is forbidden since that would mean a trip looping back on itself. So we needed something a little more sophisticated.
The strategy for developing area routing was suggested by OTP developer Matt Conway. The notion is that you always want to go from a corner to another corner (even if one of those corners is the corner of an obstacle in the middle of the area). If you instead walked to an edge, you would either have to walk along that edge to find a corner before continuing, or you would have to turn away from the edge and thus backtrack. Clearly, neither of these is going to be a shortest path. The problem of finding the corners that you can visit from a given location turns out to be equivalent to finding those that you could see from that location if all obstacles were infinitely high and opaque. That’s because anything you can see, you can walk in a straight line to. Finding these corners is a well-studied problem in computational geometry; the structure you need to generate is called a visibility graph.
For a convex polygon, of course, you can see any vertex from any other; the graph is the complete graph and has a number of edges which is roughly the square of the number of vertices. But for a concave polygon, things are more complicated.
Here’s an example: the polygon is in black, and the visibility graph, excluding edges shared with the polygon, is in green. Computing the visibility graph efficiently requires some computational geometry. So I pulled out my copy of de Berg et al, which provided a straightforward algorithm and then said that other, better algorithms were available. Unfortunately, they weren’t available already implemented in Java. But fortunately, I found VisiLibity, a C++ library that I was able to port. C++ has somewhat complicated semantics and translating the code to the much simpler semantics of Java was a bit tricky. But, after some false starts, I managed to make the port work.
Then we had another problem: certain very complicated structures turned out to have too many edges. A simple case was a circle, approximated by 500 vertices equidistant from a center point. There were roughly 125,000 edges created for this. By comparison, there are only about 77,000 edges in all the streets of Manhattan. Clearly, something had to be done to reduce the number of edges.
Here’s an example from Portland:
This output from our debugging visualization tool shows two separate areas; I’ve marked up the larger area with blue dots showing its entrances.
I decided to only compute the visibility graph for a subset of vertices. The subset I used was: (a) all vertices with incoming edges (the entrances/exits to the area) (b) all concave vertices of the outer polygon (those that stick in), and (c) all vertices of all holes. This reduced the set of edges somewhat, but there were still edges present that would never be used. Rather than slow down trip planning for users, I decided to do some precomputation while building the graph. This is one of the standard strategies for speeding up software: spending computation time in advance to avoid slowdowns during actual use. So, looking only at the entrances and exits, I precomputed a path from each entrance to each exit. Those paths each used some set of edges; any edge that was not in any of those sets would never be on a shortest path and could be removed.
Here’s an image showing the before/after from this approach:
This is some sort of parking structure at a train station in Martinez, CA. Matt Conway provided the example as it illustrated some bugs in my VisiLibity port, but it turned out to also be a pretty good test of the edge reduction.
Finally, there’s at one known issue with the code as-written. Here’s that trip across Piazza San Marco again. You’ll notice the path taken is not a perfect diagonal; it travels along the edge of the Piazza for a bit at the end. That’s because what you see as one open space in the image is actually three separate piazzas; the north-east section is called the Piazzetta dei Leoni, and is treated as a separate area. It would be pretty easy to merge adjacent areas, but I haven’t done yet it because it’s very rare and because it would be hard to figure out how to give correct narrative directions (“cross the Piazza San Marco and the Piazzetta dei Leoni”). Patches would be appreciated!
b-roll is an ongoing series on the OpenPlans blog.
We’ll be giving you updates on in-progress work across our projects, straight from the floor.