Algorithms

The OS-Matcher uses a hierarchy of routers, each addressing a specific domain of routing targets at a different scale.

The innermost router is responsible for routing on the street graph while the outermost tries to find routes as continuously as possible with the help of its underlying routers.

Note

As described in the Overview, we have a street map \(M\) and sampling points \(S_1\) to \(S_n\) which are to be mapped onto \(M\).

To prepare the algorithms, a simple directed graph \(G\) gets built from the street map \(M\), while interconnecting them with each other.

In the following sections, we describe and illustrate all the routers, beginning with the innermost one.

• Dijkstra router
• Directed candidate router
• Sampling point router
• Backtrack router
• Skip router
• Piecewise router