search

graphhopper / map-matching

The map matching functionality is now located in the main repository https://github.com/graphhopper/graphhopper#map-matching
https://www.graphhopper.com/open-source/
Apache License 2.0
785 stars 273 forks source link

If too distant GPS entries split route #58

Open karussell opened 8 years ago

karussell commented 8 years ago

Currently the matching fails if too distant GPS/GPX entries but instead we should create two routes and make it happen.

stefanholder commented 8 years ago

In general, the matching fails if there is an HMM break. This happens if no candidate can be found for a GPS position or if there are no routes between the candidates of subsequent GPS positions.

The hmm-lib 1.0, which will be released soon, allows splitting the sequence of GPS positions at the HMM breaks and matching each sub-sequence individually.

Even if GPS entries are distant, the matching should not fail as long as there is still a route between the candidates. Can you please provide an example trace?

karussell commented 8 years ago

The problem is if the normal matching distance is like 200 or 400m and then you get something like 4km where you'd only guess and also we would need to increase the search limit giving us slightly worse performance as long as we do not utilize CH (see #60)

stefanholder commented 8 years ago

At BMW, we successfully matched traces with the hmm-lib where GPS positions were 3 min (= 5 km for 100 km/h) apart. For such low frequency traces fastest routes instead of shortest routes should be computed between candidates.

Hence, I would recommend to increase the search limit instead of splitting the GPS trace.

karussell commented 8 years ago

This makes probably sense for cars but definitely not for pedestrians or bikes because the intermediate route is just guessing, even if fastest (btw: we do 'fastest' as default). And I would offer the user the choice until it is okay to guess and when it should be splitted.

stefanholder commented 8 years ago

Ok, sounds good.

kodonnell commented 8 years ago

Somewhat relevant discussion here - that is, cellular data can also have varying separations between trilaterated (non-GPS) coordinates, and it'd be preferrable to not split the route. I imagine the same would be true of any wifi/beacon technologies. So, yes, I agree that giving the user the choice would be good.