Improve off route detection

[Fabi755]

This will fix the problems described in #58.

Following things are done

1. Improve movingAwayFromManeuver logic.
2. Mark maximumDistanceOffRoute as deprecated

Instead of removing maximumDistanceOffRoute directly, I marked the option as deprecated, while some projects may already use this in their code.

Let me know if I can adjust something more or you find some problem in my code.

[boldtrn]

Thanks a lot for looking into this.

Could you maybe check the formatting of your change, it uses a different indentation than the rest of the code. I know that the exciting formatting is a huge mess, we should probably reformat the whole source code in one go, but we should probably do this without any other changes mixed in. So it would be nice if you could reformat the code to have a similar indentation.

A quick thing that I spotted was the change from RingBuffer to List. Any reason to do this? The nice thing about RingBuffer was that it was capped at 3 entries, with a list, we could end up storing millions of records for no reason if a user is offroute for a long time.

[Fabi755]

Thanks for your fast response!

I know that the exciting formatting is a huge mess, we should probably reformat the whole source code in one go, but we should probably do this without any other changes mixed in.

Make sense! I will force the IDE keeping the current format.

A quick thing that I spotted was the change from RingBuffer to List. Any reason to do this? The nice thing about RingBuffer was that it was capped at 3 entries, with a list, we could end up storing millions of records for no reason if a user is offroute for a long time.

I have copied this, form the iOS solution, that was the origin for the Android code of Mapbox site (I read this on some Mapbox issue). The problem with the RingBuffer is, when we calculate distance by first & last position, the first position may already replaced by newer one. Often updated positions will be always below our minimum of 50 meters threshold.

We need the first position to calculate our traveled distance. My first attempt was to use the current distance to maneuver, but this can be initial more then our threshold of 50 meters. So the first location is our point zero for comparing.

I will have a look if I find some cleaner solution for tracking our direction and first distance point without generating a full location history.

[Fabi755]

To prevent using a list with all historical positions, we always need to store the first position, and the last two positions.

My current ideas are:

1. Extend the ring buffer with a paramter where we can configure that the first value should not be used/overwritten. I don't like that we use the real ring-buffer pattern here, and it looks like we can not use the base class ArrayDeque for this.
2. Use list/array and drop the middle value(s) in the detection logic. So the list will not increase the size over 3 items. Seems little bit hacky for me.
3. Use two parameters. One integer for store the first position, and the existing ring buffer to detect the movement direction. Then we have two parameters that store the same data. Feels wrong.

I'm not happy with all of them. Maybe you know a pattern or have some more ideas that would be more cleaner?

[boldtrn]

How about we do a check like this, and add after the pop:

if (distancesAwayFromManeuver.size >= 3) {
  // We replace the first one, in order to keep the history with the last one
  distancesAwayFromManeuver.pop()
}

[Fabi755]

Ahh, right! I have thinking all the time with the wrong calculation. While check our current position with the last one, we don't need the second value for comparing.

Thank you!

[boldtrn]

Sorry for the delay! I will try to review this PR in the next days. As this is a very critical part of the navigation, I would like to give this proper testing and debugging.

[Fabi755]

I'm currently run some final tests.. please wait a little bit with merging :-)

[Fabi755]

I found two more things that maybe can improved.

1. The internal OffRouteDetector get calles by NavigationRouteProcessor. This is only happening when we use the internal one. Some idea why this not an interface function that always is called?

While I use my own OffRoute engine this part is missing and leads to wrong off route results. Maybe I can build this by myself, but it would be easier if this is already supported by default.

2. In ToleranceUtils the radius for off route detection is calculated. If we are near a maneuver the radius is smaller. So far so good. By default the maneuver radius is 40 and the off distance is 50. On near maneuver the distance is 25 (min reroute / 2). In short: If we are in a maneuver zone (40 meters radius) the off route distance is calculated with 25 meters. If the next step will be more then 25m we get an off route event.

I see the problem here in the default values and the calculation of minimumDistanceBeforeRerouting / 2. My idea would be to create a new navigation option that can be used to control this value and changing the default values to work each other. If we want to force a right usage, we need to check the values and be sure that the zone radius is not smaller than the new near-maneuver-re-route-threshold option.

Any ideas or discussions before I start to resolve them? :-)

[boldtrn]

The internal OffRouteDetector get calles by NavigationRouteProcessor. This is only happening when we use the internal one. Some idea why this not an interface function that always is called?

I am not sure if I can follow you here. You can set the OffRouteDetector using MapboxNavigation#setOffRouteEngine. You should extend OffRouteDetector then it should work fine. Or is there something else missing?

In short: If we are in a maneuver zone (40 meters radius) the off route distance is calculated with 25 meters. If the next step will be more then 25m we get an off route event.

I am not sure if I can follow you here. Isn't this code checking if we are close to an intersection (these are points where we can leave the route), distanceToNextIntersection <= navigationOptions.maneuverZoneRadius(). If yes, then we are extra sensible about moving away from the route, because we are using navigationOptions.minimumDistanceBeforeRerouting() / 2. This would mean the distance before rerouting is reduced, if we are close to an intersection and would trigger a rerouting a lot easier. I think this approach is not too unreasonable?

[boldtrn]

This PR looks good to me @Fabi755. Do you want to merge this soon or do you want to add something else here as well?

[Fabi755]

I think we can merge this now. If some users have similar problems or I detect something more I will create a new pull request.