Routing Tiles

From OpenStreetMap Wiki
Jump to: navigation, search

9-tiles approach

The following picture shows the routing data limited to crossing nodes and how it matches to tiles. All non-crossing nodes have been removed during calculation of the routing data, as they are not routing relevant except for the way to the next crossing.
For simplification purposes the example does not use oneway-streets or turn-directives. Street types are ignored too and an the routing data calculated here is restricted to ways applicable for cars. Cycle ways and footways have been are ommited.

Routing relevant nodes, tile numbering convention and cross border sections

The next image shows the routing relevant nodes of the middle tile. (Which is mostly a crossing node or the node at end of a dead end street). As can be seen, when calculating routing data not only the sections inside the middle tile are relevant, however also the sections crossing the borders to the tiles around. Cross border routing sections stop at the next routing relevant nodes outside the middle tile.
Note: For simplification cross border sections could be stopped at the next crossing outside the tile of or at last node of the way crossing the border. What ever comes first.

The following image shows the routing relevant node for the middle tile and their node IDs. As convention the upper left tile (north-west tile) is called tile '1', the middle tile is called tile '5' and lower right tile (south-east tile) called tile '9'.

Generation of sections IDs

The following image shows how the IDs for the sections are generated during the computation of the routing data. The section IDs are derived from the IDs of their first and last node. Thus their sections IDs stay the same even when the routing data is calculated again, as long as their first and last node do not change.
Here is no example, where 2 sections have the same start and end node and thus would the get assigned same section ID. In such cases, additional rules have to applied in order to distinguish such such sections.

Related articles:
Quad tiles , Tiles@home, Osmarender