Project-OSRM / osrm-backend

Open Source Routing Machine - C++ backend
http://map.project-osrm.org
BSD 2-Clause "Simplified" License
6.42k stars 3.4k forks source link

Add automatic bearing filter to map matching plugin #4792

Open TheMarex opened 6 years ago

TheMarex commented 6 years ago

If the user does not pass a bearing parameter, we will include candidates (green dots) for all orientations for every input trace points (red dots).

bearing filter svg

However we could infer the bearing for every tracepoint from the trace (black arrows) and use these as bearing values to filter the candidates. In this example it could for example filter out candidates on the cross streets since they have a different bearing.

danpat commented 6 years ago

I implemented this on a local branch, but the results were, on average, a bit disappointing. There was a modest speedup, but it came at the cost of a lot more failed matches, and was overall not worth it IMO.

For idealized cases like the diagram above, yep, it works great, and in dense areas, definitely decreased the number of candidates (in one example, candidates for a point dropped from 28 down to 12), and the speedup was measurable, perhaps 5-10% for overall query time.

However, figuring out the bearing filter is not simple. Using the mean of the incoming/outgoing bearing (as shown above) tended to fail in many cases. This can be somewhat solved by setting the bearing range to something large (like +/- 120 degrees), but that mostly defeats the purpose of filtering it the first place, and still tends to filter out the correct candidate in some cases. Noisy data is .... noisy.