-
Notifications
You must be signed in to change notification settings - Fork 0
Graph representation
This page explains how OSRM converts OSM data to an edge-expanded graph, given that the input data is correct.
Data comes from OSM, which has nodes, ways and relations
The geometric representation within OSRM is based on nodes. An OSM node is a 2D point with latitude and longitude, i.e. a geo-coordinate.
An OSM way connects a number of nodes. A way is thus a 2D poly-line, consisting of a number of segments. Several ways can share the same node where they cross.
An OSM relation relates several nodes or ways, or both. It can be used for turn restrictions, routes, and other things. A relation is often not a physical structure, but an abstraction like a bus route for example.
OSRM loads the OSM data, and transforms it into an edge-expanded graph that's better suited for modelling turn costs and turn restrictions. Suppose the followiing OSM data is loaded:
| | | d |
| a | b | c |
| | | e |
The data consists of two way: abc and dce, meeting at node c.
First, all ways are split into individual segments: ab,bc,cd,ce. For each segment, two graph nodes are created, one for each direction of the segment:
ab, ba
bc, cb
cd, dc
ce, ec
A graph edge is then created for every possible movement taking you from one graph node (direction of a OSM segment) to another. If we allow all turns (including u-turns), in the map above, we get these edges:
dc-cd
dc-cb
dc-ce
ab-ba
ab-bc
ba-ab
bc-cd
bc-cb
bc-ce
cd-dc
cb-ba
cb-bc
ce-ec
ec-cd
ec-cb
ec-ce
Edge have been written in the form "fromGraphNode-toGraphNode". Since we can only move along connected paths, the second graph node always start where the first ends.
The list above includes all possible u-turns, including u-turns in the middle of a way. For example ab-ba represents a u-turn at OSM node b of OSM way abc. OSRM removes such u-turns, and we get:
ab-bc (from ab, continue on bc)
ba-ab (from ba, do a u-turn at a and return on ab)
bc-cd (from bc, turn left onto dc)
bc-ce (from bc, turn right onto ce)
cb-ba (from cb, continue along on bc
cd-dc (from cd, do a u-turn at d and return on dc)
ce-ec (from ce, do a u turn at e and return on ec)
dc-cb (from dc, turn right onto cd)
dc-ce (from dc, continue on ce)
ec-cd (from ec, continue on cd)
ec-cb (from ec, turn left onto cb)
OSRM will also remove turns that are prohibited by turn restrictions.
Graph nodes represents a specific direction (forward or backward) of an OSM segment. There are two graph nodes for a bidirectional segment, but only one if it's a oneway segment.
Graph edges connect graph nodes, and thus represent transitioning from moving in a specific direction of one OSM segment, to moving in a specific direction of another (or the same) OSM segment. The transition can be either via a turn from one way onto another way, doing a u-turn, or moving from segment to segment along the same way.