Implement turn-weight support

[xivk]

Internal data model

Let's go for full turn-weight support. We model turning weights on vertices using a turn-weights table. This idea is loosely is based on this research paper and it seems the CRP paper more or less contains this approach too.

We maintain a single table per vertex and the edges around that vertex are the indexes in that table. We model this as follows:

• Each vertex has an optional pointer to a turn weight table.
• Each edge has an optional local index indicating the index in the turn weight table. Each edge has two of these, one for it's first vertex, one for the second.

Turn weight table storage

Similar to edge types we maintain one index of highly common turning weight tables we can point to. The edge indexes are rewritten to maximize reuse of common turning weight tables. This means we have two types of turn weight tables:

• global: Commonly reused, global turn weight tables.
• local: Unique local versions at tile level.
  The turn weight table pointer has to contain a flag at vertex level to determine the type of table.

The turn weight tables can also different per used profile. We given them a string ID describing what they are for, for example 'bicycle', 'car'. These can then be reused for multiple profiles. The commonly used turning weight tables are shared.

Relation to (turn-)restrictions

There are three main types of restrictions:

• Single vertex restrictions: In this case the turning weights table will have infinite weights in all directions.
• Two edge restrictions: In this case the turning weights table will have infinite weights for the excluded turn.
• Three or more edge restrictions: These are the exception and are relative uncommon compared to the other two types. These will be modeled using conditional turn-tables. A table that is only valid if a vertex has been reached via a path beyond it's incoming edges. The path that this condition is based on has to be stored along with the table. This turn weight table is always local.

Conceptual data model

TBD

How is this handled from a profile perspective, what do we ask the profile and what do we store in the routing graph? The turn weight tables are the edge type equivalent, they can only be built after the routing graph has been interpreted by the profile(s).

Ideas:

• Storage of attributes at the vertex level. This can be used to model:
  • Traffic lights.
  • Nodes in a node cycle network.
  • Single node restrictions.
• Enable storage of edge sets for turn restrictions.
  • We can use this to model turn restrictions.
  • We would probably need to also define roles or and ordering (?). Does not seem to be a very good fit for turn restrictions.

Implementation

Implement turn-restriction support on a per-tile base. What needs to be done:

• Add turn weight tables to tiles.
  • Add a way to store pointers on vertices.
  • Add functionality to get edges a local index per vertex.
  • Add local storage for the weight tables.
  • Implement a way to compare tables, even though their columns may be in a different order.
  • Implement a global weight table index similar to the edge types.
• Implement turn weight support on Dykstra.

[pietervdvn]

This should be handled by the profile, as parsing can get pretty complicated with tags as except=hgv/emergency

Positive restrictions (as restriction=only_right_turn) should be handled by an extra preprocessing step:

1) Start with raw OSM data
2) Preprocess this which creates relations (aka supersets) for LEZ, fixes only_right_turn into the inverse for the crossroads of 'no_left_turn', 'no_straight_on' and other fun
3) Have another valid .osm file
4) Input this in itinero 2.0 tile creation
5) Do route planning

[xivk]

Preprocess this which creates relations (aka supersets) for LEZ, fixes only_right_turn into the inverse for the crossroads of 'no_left_turn', 'no_straight_on' and other fun
Have another valid .osm file

Disagree with the restriction handling being in the OSM preprocessing because it requires users to change the OSM data before loading it, Itinero should handle this internally.

Agreed with reversing the relations during preprocessing.

[xivk]

After some more research it is concluded turning weights are different from turn restrictions. Turn restrictions can be simpler (single node) and more complex (turns with a via-way). It is possible to model a single node restriction by modelling it as infinite turning weights but it doesn't seem trivial to do the same with a restriction spanning 3 edges or more.