Overview

Let \(M\) be the street map and \(A\) and \(B\) two track points.

The street map \(M\) in use is the OSM map. Start and end points \(A\) and \(B\) are GPS locations, which not necessarily lay on the street map.

Candidate search

Since the start and end points are potentially unbound GPS locations, the algorithm starts with a candidate search (using class SamplingPointFinder with a definable search radius) to find nearby street segments from \(M\) resulting in a set of street segments for both points, \(S_A\) and \(S_B\).

Fig. 4 Start and Endpoint with candidates

The point is than projected onto each segment of the set resulting in a set of candidate points \(C^A\) and \(C^B\) with the candidates \(c_i^A\) and \(c_j^B\).

The candidates are ordered according to their distance. However this might not be unique as you see in the following image.

Fig. 5 Example for ambiguous candidates

The track data may contain direction data as well, which is considered as the next decision criteria (using function headingDifference()). This would result in a distinct decision in our example.

Fig. 6 Candidate rank with distance and heading

If even that is not enough to determine a priority ordering of candidates, there are three more optional categories to deal with that issue:

• originId of the street segment from the input street map data the candidate is laying on (for example the ID a street segment has in the osm database)

• originOffset + streetSegmentIndex (because it might arise that a street segment is divided in sub street segments)

• streetIndex of the street segment as it was placed in the internal data structure (as a last decision criteria which is guaranteed to be unique, for the rare cases when the input street map data has duplicate IDs)