Indoor mapping

This is a page to collect ideas about using OpenTripPlanner for indoor mapping. Most of these ideas are not in the issue tracker yet, because we need to think about them a bit first.

Area Routing

OTP should be able to route users through areas (such as large rooms, public plazas, &c.). Here's a more complex example:

For the best routing, I think we need to decompose a polygon to a visibility graph that should be integrated with the main graph. I haven't found a library that does this in Java yet, but some software is listed in the Spatial network analysis software page on Wikipedia.

__________________________________
|                                |
|           ______               |
|           |~~~~|               |
|           |~~~~|               |
|           |____|               |
|                                |
|                                |
|     _______________________    |
|     |                     |    |
|     |                     |    |
|     |                     |    |
|     |                     |    |
|     |                     |    |
|a    |---------------------|   b|
|     |                     |    |
|_____|                     |____|

The horseshoe shape is a hard-surface plaza, and the dashed line is a path connecting the two sides of the plaza (this is something that one might see, for example, at a large university quad). The area filled with ~ is my meager attempt at portraying water. I suspect that, in OSM, a pond or other untraversable area is often modeled as an area on top of other areas.

Here is how I think we should build the visibility graph: first, we need to parse all the areas in OSM and retain ones that either a) are traversable or b) are not traversable but lie within traversable areas. Implementing this efficiently is left as an excercise for the reader. Once that is done, we subtract b) from a) to give us routable areas.

Then we can build a visibility graph. We loop through all the vertices of the polygons and build an edge from each vertex to every other vertex if a straight-line path does not go outside the polygon. It may be wise to simplify the polygons before doing this to avoid inflating the graph unnecessarily.

This should be costed based on the surface type of the area. If it's a concrete plaza, it should be costed about the same as a sidewalk. However, if it's a grassy or gravel-covered area, it should be costed higher than concrete so that the trip planner will be inclined to use paths through parks instead of just cutting across them.

The other little wrinkle is that, especially with parks, there often are untraversable areas. For instance, in Golden Gate Park, it's quite impossible to walk from the conservatory up to Arguello Boulevard but the OSM data does not indicate this. Probably we should only apply the feature to a limited set of OSM tags.

Some have suggested that we might be able to generate these paths dynamically to keep the graph small. Probably the steps would be largely the same, but the data would be serialized after the subtracted polygons are made, and edges would be generated using a directed search.

There is some discussion about this issue in the 2012-01-19 check-in.

Elevators/Lifts

This has been included in OpenTripPlanner 0.5, see ticket #582. OSM nodes tagged highway=elevator connected to ways with levels defined by level= tags, layer= tags or level_map relations will be routed on properly.