Add U-Turns

[boldtrn]

This PR fixes #1064. This PR is adding U-Turn instructions.

We recognize 3 types of U-Turns:

• Heading is opposite to the orientation of the first instruction. Convert CONTINUE => U-TURN
• At waypoints, if we have to turn around at the waypoint. Convert CONTINUE => U-TURN
• When performing two turn in the same direction in a very short distance. The street before and after the turn have to have the same name and the orientation has to be more or less opposite. This converts two TURNS => One U-TURN.

http://localhost:8989/?point=48.005027%2C7.997961&point=48.005874%2C7.999538&heading=230

http://localhost:8989/?point=48.017509%2C8.008572&point=48.019012%2C8.008116&point=48.018319%2C8.010836&vehicle=bike

http://localhost:8989/?point=47.996983%2C7.841899&point=47.996987%2C7.842087

The third method performs pretty well for cars and fixes most of the u-turns. One issue is that we require two turn instructions. In some cases we don't create a turn instruction because there is no other possible turn, in this case we cannot convert the instruction to a u-turn, e.g., here.

I also required that the road to u-turn on is a one way. I have seen some cases where a u-turn was created that is not a real u-turn. Here are some examples in Baden-Württemberg. I found these examples using measurement, with foot and printed the location of every u-turn. So these examples are not very frequent, but they exist:

• http://localhost:8989/?point=48.870569%2C8.646058&point=48.870509%2C8.645768
• http://localhost:8989/?point=47.881974%2C7.824572&point=47.882046%2C7.824427
• http://localhost:8989/?point=47.954715%2C7.777317&point=47.954693%2C7.777017
• http://localhost:8989/?point=48.893573%2C10.004784&point=48.893471%2C10.005176&vehicle=foot
• http://localhost:8989/?point=49.769659%2C9.469453&point=49.769784%2C9.469732

When only showing u-turns for one-way streets the samples above don't produce turn instructions. When thinking about this a bit more I think usually u-turns are only relevant for major roads that are usually one-ways separated from each other with designated u-turn lanes or u-turning at traffic lights. So this limitation makes sense for me.

TODO:

• Add U-turn icon
• Decide if we want different signs for left and right u-turns
• Decide if we want a different translation for the different u-turns

[karussell]

A heading per instruction is not a bad idea as e.g. the very first continue after every via or start point could need something like "go north" which the client then could at least create on its own.

But before exposing this into the public JSON response lets think twice or more about the "if" and "how" :)

While doing that I realized that in most cases GraphHopper won't actually lead you back on the same edge that you were coming

What do you mean here? With a via point it is not that unlikely (?)

[boldtrn]

What do you mean here? With a via point it is not that unlikely (?)

Yes exactly, the typical case would be a via-point. But GrapHopper calculates the instructions independently for every path between waypoints (see PathMerger). So Having a route a->b->c, GH calculates instructions for a->b and b->c. Therefore, it is not easy to create a u-turn instruction at b. One solution could be to pass some contextual information about the last path (a->b) into the creation of the next path (b->c). Another idea could be to merge the instructions by adding a u-turn if necessary. This could be done by adding the orientation for the last part of the edge in every last instruction and the orientation for every first instruction, so the merger could see if they are opposite and add a u-turn. If they are 90° the merger could add a regular turn instruction (might be the case when placing a waypoint on an intersection.

A heading per instruction is not a bad idea as e.g. the very first continue after every via or start point could need something like "go north" which the client then could at least create on its own.

Yes, so I only added it for the first instruction after a waypoint, but we could also do this for every instruction (not sure if that would be needed).

[boldtrn]

After thinking about this a bit more, we could also create a u-turn instruction as the first instruction if the first heading is going into the opposite way of the requested heading. This should be actually quite easy as well. This could be done in the PathMerger or in a new class "InstructionMerger"?

[karussell]

Yes it could be done in PathMerger or if necessary in a new class.

[devemux86]

Another idea could be to post-process the instructions after their generation.
Then knowing them all, can do such things as skip / merge / u-turn?

[boldtrn]

Ok, I updated the code.

I create a u-turn instruction for waypoints, this means if we are going from a->b->a, there will be u-turn instruction at b. I do a heading check, if the difference between the two headings is very small (currently I have 1°, which could be further improved).

I also added an initial u-turn if there was a heading for the first point and if the heading is pointing in the other direction than the heading of the first edge. (Diff > 170°)

After giving this some more thought I am not sure if it is a good idea to calculate an initial u-turn on the server side. Think about a user is parked in his garage and plans a route. The heading might be completely off at this point. Once the route is calculated he wants to start the navigation and starts riding. The first instruction would be "turn around", which is a bit weird. Probably we should add some logic on the client side for this, as the client knows the initial heading of the continue instruction.

WDYT? Should we add this or should I remove this again?

[boldtrn]

Something I just came up with could solve case 1). But this would require extra computation power. We could add the starting and end heading of every instruction. Essentially this would require 2 azimut calculations per instruction. This would allow us to check the instruction list for short instructions with repeating turn signs, like it would appear for u-turns in case 1).

E.g.

>----- Turn right
                |
<----- Turn right

I think the question is if we would want this or not? This would probably further decrease the ch speed.

[boldtrn]

We also need an icon for the front end here.

[devemux86]

Note that in your example, being parked and planning a route, the GPS could return 0° location bearing, which essentially won't participate in route initial direction.
(GPS bearing would become accurate when device moves, not when it's stationary)

[boldtrn]

Note that in your example, being parked and planning a route, the GPS could return 0° location bearing, which essentially won't participate in route initial direction.
(GPS bearing would become accurate when device moves, not when it's stationary)

Yes, I had the same thought, see my comment above:

After giving this some more thought I am not sure if it is a good idea to calculate an initial u-turn on the server side. Think about a user is parked in his garage and plans a route. The heading might be completely off at this point. Once the route is calculated he wants to start the navigation and starts riding. The first instruction would be "turn around", which is a bit weird. Probably we should add some logic on the client side for this, as the client knows the initial heading of the continue instruction.

So I think we should remove it again. Let me know what you think.

[karussell]

Sorry, I'm a bit late with this ... would you mind updating the PR? probably just recreate the translation files.

Probably we should add some logic on the client side for this, as the client knows the initial heading of the continue instruction

The heading variable is already something where the client can and should pass this information - or is this already solved (?)

Essentially this would require 2 azimut calculations per instruction.

Isn't one of those calculations already done in the instruction creation code?

[boldtrn]

Ok, so I updated this PR.

The heading variable is already something where the client can and should pass this information - or is this already solved (?)

Yes, this is how I implemented it :). However, I am not sure if it wouldn't simply work better to do this on the client side. Here we could also check if the user is moving or not and all that.

We could also add this to GH though. We could add a speed or is_moving variable. It the user is moving, we could create a bigger penalty for a u-turn, whereas when being parked, performing a u-turn is often easier.

I am really not sure what we should do here? WDYT @devemux86, would you see this on the client or server side, and why?

Isn't one of those calculations already done in the instruction creation code?

Yes, well we could add the heading for every instruction and not just for via instructions which would make this easier in the end. Probably the best would be to solve this case during the instruction creation and not in a post processing step. Will try if it's possible.

[karussell]

We could add a speed or is_moving variable

Why would this be necessary? Why not just omit the heading if it is unknown? (and then no u-turn instruction is created)

would you see this on the client or server side, and why?

What exactly do you want to see on the client side?

Probably the best would be to solve this case during the instruction creation and not in a post processing step. Will try if it's possible.

Sounds good!

[devemux86]

What exactly do you want to see on the client side?

Indeed what's the actual use case or do we complicate things?
GPS bearing exists after some device movement, at that point the instructions were already calculated.

[boldtrn]

Why would this be necessary? Why not just omit the heading if it is unknown? (and then no u-turn instruction is created)

Ok, maybe I was thinking too complicated then :). Let's leave it as it is currently.

What exactly do you want to see on the client side?

The initial U-turn when being parked parallel to a street and needing to start in the other direction as currently facing. I was just thinking that it might be easier/better to do this on the client side.

[devemux86]

The initial U-turn when being parked parallel to a street and needing to start in the other direction as currently facing. I was just thinking that it might be easier/better to do this on the client side.

That could very easily fail by GPS accuracy.. 🙁
GPS can shows us some meters away in other direction, GraphHopper will retrieve that as start point, snap position to reverse lane and we'll have unwanted routing.

[boldtrn]

Ok, I updated this PR. It contains 3 features:

• U-turns for Via points
• U-turns for start if heading points in the opposite direction
• U turns for turning between two separated one-way lane roads that belong to the same road, if the connection between the two is short (<35m) and is only one edge. This only works if there are instructions, like two left turns. The second instruction will be ignored and the first will be converted to a u-turn. This could be further improved when we solve Instructions: Missing instruction when turning onto road with separated one way lanes #1048.

Let me know what you think.

[boldtrn]

I updated this PR. Now I am quite happy with the results. When running measurement this PR was even a bit faster than the current master (well it shouldn't actually be faster, but the performance impact is not that huge). I updated the first comment to contain the relevant information.

[karussell]

Should we differentiate left and right U-turns (and adapt the signs accordingly) like @devemux86 mentioned?

[boldtrn]

We could, but I am not sure if the cost use factor makes sense.

The benefit would be to be able to create u turns in a certain direction. But I am not sure how often u-turns would be done in the "wrong" direction.

The downside of this would be that we need a spatial rule index to check if we are in a left hand traffic country.

An alternative would be to differentiate between turn around and u-turn. U turns would have a direction and would be calculated in the instruction class. Turn around would be calculated for via points in the path merger.

I think differentiating between u turns and turn around would be a nice addition. WDYT?

[boldtrn]

Btw I think "turn around" and "u turn" is a synonym, so we might need a different name :).

[devemux86]

The downside of this would be that we need a spatial rule index to check if we are in a left hand traffic country.

That would be a benefit for other cases in the library too.
Like mentioned above, if having that information, could use it also in roundabouts.

BTW is there the thought to allow setting the rule of the road externally by the apps, instead to calculate it inside the library, or it's better to have it always inside?

[boldtrn]

Like mentioned above, if having that information, could use it also in roundabouts.

Yes true :). I am still not 100% sure if this wouldn't be easier done on the client side? Also the benefit for roundabouts is not that huge IMHO.

I think for roundabouts it would interesting to calculate the exiting angle (we got that already, maybe we need a bit more info) and create a turn instruction image on demand. For example if we know that we exit 80° to the left and the we go right around (might be possible to calculate from the edge geometry) we could generate a perfectly matching image. Might be easy to do with on demand SVG creation? Just a crazy thought :), but that would be really cool.

BTW is there the thought to allow setting the rule of the road externally by the apps, instead to calculate it inside the library, or it's better to have it always inside?

Isn't it enough to have it on the client side? I think besides the direction of roundabouts the changes for the routing are not that big and this could be easily done on the client side?

[devemux86]

Isn't it enough to have it on the client side?

Client can calculate or simply request users to set the rule of the road for their region.
But then need to declate it to any routing library, so that library can generate the proper instructions.

[boldtrn]

I just pushed a change. We now have U_TURN_LEFT, U_TURN_RIGHT (these are calculated for u-turns that use an intermediate short connecting road in between), and U_TURN_UNKNOWN (which would be used for generic, please turn around instructions, e.g. at waypoints etc. where GH does not calculate the actual turn movement).

Icon wise we could now use directed u-turn icons for the specified u-turns. For the unknown we could also create a more generic turn around icone, for example like this.

WDYT?

[devemux86]

For the unknown we could also create a more generic turn around icone, for example like this.

That icon is for right-hand traffic roundabouts, not u-turns.
For a generic u-turn without known direction, the usual icon without the arrow could work.

[boldtrn]

That icon is for right-hand traffic roundabouts, not u-turns.
For a generic u-turn without known direction, the usual icon without the arrow could work.

Yes, this was just an example :). We could also just turn around the continue straight arrow, so that it points in the other direction. Another option would be a u-turn symbol without an arrow head, yes.

[boldtrn]

I just updated this PR and resolved the merge conflict. This should be mergeable now?

[karussell]

LGTM

I think afterwards we should compare measurement with 3 points, currently there are just 2 and then the PathMerger is probably not activated.

[boldtrn]

I think afterwards we should compare measurement with 3 points, currently there are just 2 and then the PathMerger is probably not activated.

Thanks for merging this :). I couldn't follow your comment, sorry. What do you mean by that?

[karussell]

In the measurement class we use 2 point for querying so there won't be any u-turn calculation. If we use 3 points we could better see the performance impact of this change.

[boldtrn]

In the measurement class we use 2 point for querying so there won't be any u-turn calculation. If we use 3 points we could better see the performance impact of this change.

Ah, ok, now I understand what you mean by that. There are still u-turns, but no "via-point u-turns". Sounds good, should I create a PR that creates multi point routes?

[karussell]

Just mean to do the perf comparison in this case. Not sure if such a thing is necessary in the long run.