findNextStep() needs more context

[1ec5]

findNextStep() essentially treats the route line as an unordered set of points, ignoring the route line’s directionality. It always returns the closest step, but that isn’t always correct. For example, when the next step is a U-turn, a later step may be closer than the U-turn. Assuming the route line is correct, client code will end up instructing the user to turn right into a grass field rather than turning right onto the side street:

To handle this and other cases correctly, we need to keep track of which steps along the route line have already been completed and simply return the first uncompleted step. (Client code should periodically call shouldReRoute() to handle the case where a step has been skipped successfully.) In other words, finding the next step is less of a spatial problem and more of a problem of checking items off a list.

/cc @bsudekum @mikemorris

[bsudekum]

Yeah, I've been thinking about this. My current plan is to make the developer pass in the current "known" step.

nav.findNextStep(userLocation, route, 4);

findNextStep then would only look for at steps after the fourth step. Thoughts @morganherlocker?

[1ec5]

I’ve had good results with the following approach:

1. The next step is simply the first step that hasn’t been marked completed – in other words, increment the number that you’re proposing to be passed in.
2. Keep track of the geometry of the current leg of the trip. On each location update, if the user has strayed from this geometry – as opposed to the route as a whole – recalculate the directions or at least look for a segment of the trip that the user is near.

Since the check in part (2) happens on every location update, it’s important that it works with as small a geometry as possible. Luckily, this approach also handles the case where the user has taken a shortcut or long-cut (say, due to traffic conditions), or where the user has backtracked for some reason (they got confused).

There’s no need for a dedicated findNextStep() function; it would simply be implemented as return knownStep + 1. What would help is to replace the flat route array with an array of arrays: the route should be partitioned step by step.

[fabrik42]

Hi! I'm working on a similar project called ffwdme.js and have implemented something similar: https://github.com/ffwdme/ffwdme.js/blob/master/src/core/navigation.js#L168-L182

What I basically do is, I remember the last point, where I found the user on the route, because it is very likely the next point will be close to it. Then I will search on the route segments around the last point, first only the neighbors, then only the neighbors of the neighbors and so on.

This has proven very efficient and also works very good in complicated real live scenarios, like motorway junctions.

[bsudekum]

@fabrik42 this is great!

[fabrik42]

Thanks :) If you are interested, I could try to implement something similar for navigation.js

[bsudekum]

@fabrik42 yeah that'd be great, always open to new ways to solve the problem.

[fabrik42]

Ok, I will have a look over the weekend.