[Navigation] Unnecessary TurnRight in some situations

AntonM030481 commented

2022-04-21 17:19:55 +00:00

(Migrated from github.com)

We have some funny situation like this:
When route goes through the bridge TurnRight direction is received:
right_turn
Why?

TurnRight direction determined by angle (51 degrees here) between:

last ingoing segment vector (black one)
vector determined by points A and B (red one).
A - Go back 2 segments from junction, but not more than 100 meters (30 meters here).
B - Go back 2 segments from junction, but not more than 120 meters (130 meters here).

TurnRigh direction is not discarded (like TurnSlightRight), even if no alternative turns are available.

We have some funny situation like this: When route goes through the bridge TurnRight direction is received: <img width="1375" alt="right_turn" src="https://user-images.githubusercontent.com/85622715/164514597-efd524e8-0b3e-4bdf-9331-3aaa07cbfa69.png"> Why? 1. TurnRight direction determined by angle (51 degrees here) between: - last ingoing segment vector (black one) - vector determined by points A and B (red one). A - Go back 2 segments from junction, but not more than 100 meters (30 meters here). B - Go back 2 segments from junction, but not more than 120 meters (130 meters here). 2. TurnRigh direction is not discarded (like TurnSlightRight), even if no alternative turns are available.

AntonM030481 commented

2022-04-21 17:31:37 +00:00

(Migrated from github.com)

Another example:

TurnRight directions determined because of angles (52 and 56 here).
TurnRigh direction is not discarded (like TurnSlightRight), even if alternative turns have lower priority compared to route.
Also it's not discarded (like TurnSlightRight) because of alternatives are not aligned with ingoing segment.

Another example: ![image](https://user-images.githubusercontent.com/85622715/164517167-c7e50def-8dd6-43d1-a914-121e5d2854d2.png) 1. TurnRight directions determined because of angles (52 and 56 here). 3. TurnRigh direction is not discarded (like TurnSlightRight), even if alternative turns have lower priority compared to route. Also it's not discarded (like TurnSlightRight) because of alternatives are not aligned with ingoing segment.

AntonM030481 commented

2022-04-21 17:45:19 +00:00

(Migrated from github.com)

My suggestion is to reconsider:

Turn direction determination.

allow more segments to go back
reduce distances. It's too high now. I suppose it was set for highways
change distance limits based on turn speed limits

Discarding of TurnRigh directions (like TurnSlightRight), even if no alternative turns are available and no ingoing segments.

Maybe Right/Left turns should be discarded just like SlightTurns. Other navigators normally discard it.

TurnRigh direction is not discarded (like TurnSlightRight), even if alternative turns have lower priority compared to route.
Also it's not discarded (like TurnSlightRight) because of alternatives are not aligned with ingoing segment.

It's better to not change it.

My suggestion is to reconsider: 1. Turn direction determination. - allow more segments to go back - reduce distances. It's too high now. I suppose it was set for highways - change distance limits based on turn speed limits 2. Discarding of TurnRigh directions (like TurnSlightRight), even if no alternative turns are available and no ingoing segments. - Maybe Right/Left turns should be discarded just like SlightTurns. Other navigators normally discard it. 3. TurnRigh direction is not discarded (like TurnSlightRight), even if alternative turns have lower priority compared to route. Also it's not discarded (like TurnSlightRight) because of alternatives are not aligned with ingoing segment. - It's better to not change it.

biodranik commented

2022-04-21 20:25:47 +00:00

(Migrated from github.com)

@vng could it be that directions are wrong because of different road types (with and without a bridge)?

AntonM030481 commented

2022-04-21 21:12:37 +00:00

(Migrated from github.com)

It happens to any route. With or without bridge.
With bridge such directions are just more awkward.

It happens to any route. With or without bridge. With bridge such directions are just more awkward.

AntonM030481 commented

2022-04-21 21:31:46 +00:00

(Migrated from github.com)

Just to clarify. For logic from point 1 following code is responsible
(no bugs, the question is only about design and parameters):

m2::PointD const junctionPoint = turnInfo.m_ingoing.m_path.back().GetPoint();
  size_t const segmentIndexForIngoingPoint = isStartFakeLoop ? outgoingSegmentIndex - 1 : outgoingSegmentIndex;

  m2::PointD const ingoingPoint = GetPointForTurn(
      result, segmentIndexForIngoingPoint, numMwmIds, vehicleSettings.m_maxIngoingPointsCount,
      vehicleSettings.m_minIngoingDistMeters, false /* forward */);
  m2::PointD const outgoingPoint = GetPointForTurn(
      result, outgoingSegmentIndex, numMwmIds, vehicleSettings.m_maxOutgoingPointsCount,
      vehicleSettings.m_minOutgoingDistMeters, true /* forward */);

  double const turnAngle = base::RadToDeg(PiMinusTwoVectorsAngle(junctionPoint, ingoingPoint, outgoingPoint));
  CarDirection const intermediateDirection = IntermediateDirection(turnAngle);

Just to clarify. For logic from point 1 following code is responsible (no bugs, the question is only about design and parameters): ``` m2::PointD const junctionPoint = turnInfo.m_ingoing.m_path.back().GetPoint(); size_t const segmentIndexForIngoingPoint = isStartFakeLoop ? outgoingSegmentIndex - 1 : outgoingSegmentIndex; m2::PointD const ingoingPoint = GetPointForTurn( result, segmentIndexForIngoingPoint, numMwmIds, vehicleSettings.m_maxIngoingPointsCount, vehicleSettings.m_minIngoingDistMeters, false /* forward */); m2::PointD const outgoingPoint = GetPointForTurn( result, outgoingSegmentIndex, numMwmIds, vehicleSettings.m_maxOutgoingPointsCount, vehicleSettings.m_minOutgoingDistMeters, true /* forward */); double const turnAngle = base::RadToDeg(PiMinusTwoVectorsAngle(junctionPoint, ingoingPoint, outgoingPoint)); CarDirection const intermediateDirection = IntermediateDirection(turnAngle); ```

AntonM030481 commented

2022-04-26 19:46:49 +00:00

(Migrated from github.com)

@vng what do you think?

vng commented

2022-04-26 19:55:54 +00:00

(Migrated from github.com)

About what? If the example on topic start, why do we have turn instruction if there are no alternative turns on the way? Am I missing something?

AntonM030481 commented

2022-04-27 06:26:32 +00:00

(Migrated from github.com)

@vng it was from the very begining. I don't know why.
Looks like no need to keep such single turn no matter what is its angle.
If everyone is OK with it, I will make changes.

@vng it was from the very begining. I don't know why. Looks like no need to keep such single turn no matter what is its angle. If everyone is OK with it, I will make changes.

vng commented

2022-04-27 06:54:02 +00:00

(Migrated from github.com)

Hm, please, check this test RussiaMoscowSvobodaStTest.
Seems like we added regression here (+1 turn) and exactly on the bridge. There was no bridge turn before, according to the test.

Hm, please, check this test RussiaMoscowSvobodaStTest. Seems like we added regression here (+1 turn) and exactly on the bridge. There was no bridge turn before, according to the test.

AntonM030481 commented

2022-04-27 07:05:48 +00:00

(Migrated from github.com)

The question 1 (Turn direction determination) is much more complicated.
But I think we need to change it too.

The question 1 (Turn direction determination) is much more complicated. But I think we need to change it too.

AntonM030481 commented

2022-04-27 07:15:52 +00:00

(Migrated from github.com)

This is is bicycle_turn_test.cpp::TurnsNearKhladkombinatTest
We have TurnRight here because of 53 degrees angle between ingoing segment (black),
and vector from ingoingPoint to outgoingPoint (red).
Both points defined according to the code from organicmaps/organicmaps#2438 (comment).
Here my suggestion is to not allow to go back second time for ingoingPoint determination.
It should not be done because of sharp angle with 1st back edge.
For some reason now we have this check for outgoingPoint only (and only when segment changes, not path points inside segment).

This is is bicycle_turn_test.cpp::TurnsNearKhladkombinatTest We have TurnRight here because of 53 degrees angle between ingoing segment (black), and vector from ingoingPoint to outgoingPoint (red). Both points defined according to the code from https://git.omaps.dev/organicmaps/organicmaps/issues/2438#issuecomment-1105781360. Here my suggestion is to not allow to go back second time for ingoingPoint determination. It should not be done because of sharp angle with 1st back edge. For some reason now we have this check for outgoingPoint only (and only when segment changes, not path points inside segment). ![image](https://user-images.githubusercontent.com/85622715/165461069-68391261-1092-4306-813d-cc88d85e2dd8.png)

AntonM030481 commented

2022-04-27 07:28:38 +00:00

(Migrated from github.com)

Hm, please, check this test RussiaMoscowSvobodaStTest.
Seems like we added regression here (+1 turn) and exactly on the bridge. There was no bridge turn before, according to the test.

Agree. Looks like I not by intension removed discarding of RightTurn/LeftTurn if no alternative is present.
So I will put it back.

But again I don't think that determination by angle between vectors of TurnLeft is appropriate here (before discarding).
Just imagine additional alternative real TurnLeft here (then discarding will not be applied)

> Hm, please, check this test RussiaMoscowSvobodaStTest. > Seems like we added regression here (+1 turn) and exactly on the bridge. There was no bridge turn before, according to the test. Agree. Looks like I not by intension removed discarding of RightTurn/LeftTurn if no alternative is present. So I will put it back. But again I don't think that determination by angle between vectors of TurnLeft is appropriate here (before discarding). Just imagine additional alternative real TurnLeft here (then discarding will not be applied) <img width="793" alt="image" src="https://user-images.githubusercontent.com/85622715/165464506-dacd73ae-2f37-4d2a-b7b6-dc8cca7582d7.png">

vng commented

2022-04-27 07:49:46 +00:00

(Migrated from github.com)

But again I don't think that determination by angle between vectors of TurnLeft is appropriate here (before discarding). Just imagine additional alternative real TurnLeft here (then discarding will not be applied)

I understand, but have no ideas here. Please, make as you think will be better. You are really doing great with turns :)

`But again I don't think that determination by angle between vectors of TurnLeft is appropriate here (before discarding). Just imagine additional alternative real TurnLeft here (then discarding will not be applied)` I understand, but have no ideas here. Please, make as you think will be better. You are really doing great with turns :)

vng commented

2022-04-27 07:50:49 +00:00

(Migrated from github.com)

Do we have real geometry points when calculating turns or only ingoing/outgoing edge's points?

AntonM030481 commented

2022-04-27 07:55:24 +00:00

(Migrated from github.com)

Do we have real geometry points when calculating turns or only ingoing/outgoing edge's points?

Sure. We have all the data.

> Do we have real geometry points when calculating turns or only ingoing/outgoing edge's points? Sure. We have all the data.

AntonM030481 commented

2022-04-27 07:58:26 +00:00

(Migrated from github.com)

I understand, but have no ideas here. Please, make as you think will be better. You are really doing great with turns :)

Thank you :)
Ok I will make all changes by myself.
And I hope for assistance in generation of new interesting UnitTests only :)

> I understand, but have no ideas here. Please, make as you think will be better. You are really doing great with turns :) Thank you :) Ok I will make all changes by myself. And I hope for assistance in generation of new interesting UnitTests only :)

AntonM030481 commented

2022-04-27 08:06:25 +00:00

(Migrated from github.com)

BTW, why we don't use OSRM directions?

vng commented

2022-04-27 08:26:09 +00:00

(Migrated from github.com)

Well, we did use algorithm part before (~2014-2016), but later folks made own routing implementation based on A*.
Contraction hierarchies (that was used in OSRM, now I don't know its architecture) are not suitable for traffic. Pedestrian routing also not good with CH.

If you think that we can take some parts of OSRM (like turns resolving), feel free to investigate.

Well, we did use algorithm part before (~2014-2016), but later folks made own routing implementation based on A*. Contraction hierarchies (that was used in OSRM, now I don't know its architecture) are not suitable for traffic. Pedestrian routing also not good with CH. If you think that we can take some parts of OSRM (like turns resolving), feel free to investigate.

👍 1

vng commented

2022-04-27 08:29:25 +00:00

(Migrated from github.com)

I did OSRM compression and adaptation for mobiles in Mapbox, but now they use Valhalla engine. And seems like OSRM is not in active developing, while Valhalla is.

👍 1

AntonM030481 commented

2022-04-27 08:33:16 +00:00

(Migrated from github.com)

Thank you for clarification.
Let's make the best Turn Resolving by ourself!
I digged in so much that I can not resist from doing it :)

Thank you for clarification. Let's make the best Turn Resolving by ourself! I digged in so much that I can not resist from doing it :)

❤️ 1

Rows
Columns

[Navigation] Unnecessary TurnRight in some situations #2438