Implementation ExitHighwayToRight and ExitHighwayToLeft and tests on it.

2 files changed, 102 insertions, 17 deletions

diff --git a/routing/routing_integration_tests/turn_test.cpp b/routing/routing_integration_tests/turn_test.cpp
index b4404dd478..a2b137d479 100644
--- a/routing/routing_integration_tests/turn_test.cpp
+++ b/routing/routing_integration_tests/turn_test.cpp
@@ -180,7 +180,7 @@ UNIT_TEST(RussiaMoscowNoTurnsOnMKADTurnTest)
   integration::GetNthTurn(route, 0)
       .TestValid()
       .TestPoint({37.68276, 67.14062})
-      .TestOneOfDirections({CarDirection::TurnSlightRight, CarDirection::TurnRight});
+      .TestDirection(CarDirection::ExitHighwayToRight);
 
   integration::TestRouteLength(route, 43233.7);
 }
@@ -267,11 +267,9 @@ UNIT_TEST(RussiaMoscowMKADPutilkovskeShosseTurnTest)
 
   TEST_EQUAL(result, IRouter::NoError, ());
   integration::TestTurnCount(route, 1 /* expectedTurnCount */);
-  integration::GetNthTurn(route, 0).TestValid().TestOneOfDirections(
-      {CarDirection::TurnSlightRight, CarDirection::TurnRight});
+  integration::GetNthTurn(route, 0).TestValid().TestDirection(CarDirection::ExitHighwayToRight);
 }
 
-// Fails due to uneeded "GoStraight".
 UNIT_TEST(RussiaMoscowPetushkovaShodniaReverTurnTest)
 {
   TRouteResult const routeResult =
@@ -286,7 +284,6 @@ UNIT_TEST(RussiaMoscowPetushkovaShodniaReverTurnTest)
   integration::TestTurnCount(route, 0 /* expectedTurnCount */);
 }
 
-// Fails because consider service roads are roundabout exits.
 UNIT_TEST(RussiaHugeRoundaboutTurnTest)
 {
   TRouteResult const routeResult =
@@ -309,7 +306,6 @@ UNIT_TEST(RussiaHugeRoundaboutTurnTest)
       .TestRoundAboutExitNum(5);
 }
 
-// Fails: generates "GoStraight" description instead of TurnSlightRight/TurnRight.
 UNIT_TEST(BelarusMiskProspNezavisimostiMKADTurnTest)
 {
   TRouteResult const routeResult =
@@ -322,8 +318,7 @@ UNIT_TEST(BelarusMiskProspNezavisimostiMKADTurnTest)
 
   TEST_EQUAL(result, IRouter::NoError, ());
   integration::TestTurnCount(route, 1 /* expectedTurnCount */);
-  integration::GetNthTurn(route, 0).TestValid().TestOneOfDirections(
-      {CarDirection::TurnSlightRight, CarDirection::TurnRight});
+  integration::GetNthTurn(route, 0).TestValid().TestDirection(CarDirection::ExitHighwayToRight);
 }
 
 // Test case: turning form one street to another one with the same name.
@@ -357,8 +352,7 @@ UNIT_TEST(RussiaMoscowMKADLeningradkaTest)
 
   TEST_EQUAL(result, IRouter::NoError, ());
   integration::TestTurnCount(route, 1 /* expectedTurnCount */);
-  integration::GetNthTurn(route, 0).TestValid().TestOneOfDirections(
-      {CarDirection::TurnSlightRight, CarDirection::TurnRight});
+  integration::GetNthTurn(route, 0).TestValid().TestDirection(CarDirection::ExitHighwayToRight);
 }
 
 UNIT_TEST(BelarusMKADShosseinai)
@@ -616,7 +610,7 @@ UNIT_TEST(GermanyFrankfurtAirportTest)
   TEST_EQUAL(result, IRouter::NoError, ());
   integration::TestTurnCount(route, 2 /* expectedTurnCount */);
 
-  integration::GetNthTurn(route, 0).TestValid().TestDirection(CarDirection::TurnSlightRight);
+  integration::GetNthTurn(route, 0).TestValid().TestDirection(CarDirection::ExitHighwayToRight);
   integration::GetNthTurn(route, 1).TestValid().TestDirection(CarDirection::TurnSlightRight);
 }
 
@@ -652,8 +646,7 @@ UNIT_TEST(RussiaKubinkaTest)
   TEST_EQUAL(result, IRouter::NoError, ());
   integration::TestTurnCount(route, 2 /* expectedTurnCount */);
 
-  integration::GetNthTurn(route, 0).TestValid().TestOneOfDirections(
-      {CarDirection::TurnSlightRight, CarDirection::TurnRight});
+  integration::GetNthTurn(route, 0).TestValid().TestDirection(CarDirection::ExitHighwayToRight);
   integration::GetNthTurn(route, 1).TestValid().TestOneOfDirections(
       {CarDirection::TurnSlightLeft, CarDirection::TurnLeft});
 }
@@ -746,8 +739,7 @@ UNIT_TEST(RussiaMoscowMKADToSvobodaTest)
 
   TEST_EQUAL(result, IRouter::NoError, ());
   integration::TestTurnCount(route, 1 /* expectedTurnCount */);
-  integration::GetNthTurn(route, 0).TestValid().TestOneOfDirections(
-      {CarDirection::TurnSlightRight, CarDirection::TurnRight});
+  integration::GetNthTurn(route, 0).TestValid().TestDirection(CarDirection::ExitHighwayToRight);
 }
 
 // Test that there's no turns if to follow MKAD.
@@ -809,3 +801,18 @@ UNIT_TEST(BelorussiaMinskTest)
   integration::TestTurnCount(route, 1 /* expectedTurnCount */);
   integration::GetNthTurn(route, 0).TestValid().TestDirection(CarDirection::TurnRight);
 }
+
+UNIT_TEST(EnglandLondonExitToLeftTest)
+{
+  TRouteResult const routeResult =
+      integration::CalculateRoute(integration::GetVehicleComponents<VehicleType::Car>(),
+                                  MercatorBounds::FromLatLon(51.603582, 0.266995), {0., 0.},
+                                  MercatorBounds::FromLatLon(51.606785, 0.264055));
+
+  Route const & route = *routeResult.first;
+  IRouter::ResultCode const result = routeResult.second;
+
+  TEST_EQUAL(result, IRouter::NoError, ());
+  integration::TestTurnCount(route, 1 /* expectedTurnCount */);
+  integration::GetNthTurn(route, 0).TestValid().TestDirection(CarDirection::ExitHighwayToLeft);
+}
diff --git a/routing/turns_generator.cpp b/routing/turns_generator.cpp
index ac2f6d3cbb..ec73809265 100644
--- a/routing/turns_generator.cpp
+++ b/routing/turns_generator.cpp
@@ -10,6 +10,7 @@
 #include "geometry/angles.hpp"
 
 #include "base/macros.hpp"
+#include "base/stl_helpers.hpp"
 
 #include "std/cmath.hpp"
 #include "std/numeric.hpp"
@@ -27,6 +28,71 @@ double constexpr kMinIngoingDistMeters = 300.;
 size_t constexpr kNotSoCloseMaxPointsCount = 3;
 double constexpr kNotSoCloseMinDistMeters = 30.;
 
+bool IsHighway(ftypes::HighwayClass hwClass, bool isLink)
+{
+  return hwClass == ftypes::HighwayClass::Trunk && !isLink;
+}
+
+bool IsLinkOrSmallRoad(ftypes::HighwayClass hwClass, bool isLink)
+{
+  return isLink || hwClass == ftypes::HighwayClass::LivingStreet ||
+         hwClass == ftypes::HighwayClass::Service ||
+         hwClass == ftypes::HighwayClass::Pedestrian;
+}
+
+/// \brief Fills |turn| with |CarDirection::ExitHighwayToRight| or |CarDirection::ExitHighwayToLeft|
+/// and returns true. Or does not change |turn| and returns false.
+/// \note The method makes a decision about |turn| based on geometry of the route and turn
+/// candidates, so it works correctly for both left and right hand traffic.
+bool IsExit(TurnCandidates const & possibleTurns, TurnInfo const & turnInfo,
+            Segment const & firstOutgoingSeg, CarDirection & turn)
+{
+  if (!possibleTurns.isCandidatesAngleValid)
+    return false;
+
+  if (!IsHighway(turnInfo.m_ingoing.m_highwayClass, turnInfo.m_ingoing.m_isLink) ||
+      !IsLinkOrSmallRoad(turnInfo.m_outgoing.m_highwayClass, turnInfo.m_outgoing.m_isLink))
+  {
+    return false;
+  }
+
+  // Considering cases when the route goes from a highway to a link or a small road.
+  // Checking all turn candidates (sorted by its angle) and looking for the road which is a
+  // continuation of the ingoing segment. If the continuation is on the right hand of the route
+  // it's an exit to the left. If the continuation is on the left hand of the route
+  // it's an exit to the right.
+  // Note. The angle which is using for sorting turn candidates in |possibleTurns.candidates|
+  // is a counterclockwise angle between the ingoing route edge and corresponding candidate.
+  // For left turns the angle is less than zero and for it is more than zero.
+  bool isCandidateBeforeOutgoing = true;
+  bool isHighwayCandidateBeforeOutgoing = true;
+  size_t highwayCandidateNumber = 0;
+
+  for (auto const & c : possibleTurns.candidates)
+  {
+    if (c.m_segment == firstOutgoingSeg)
+    {
+      isCandidateBeforeOutgoing = false;
+      continue;
+    }
+
+    if (IsHighway(c.m_highwayClass, c.m_isLink))
+    {
+      ++highwayCandidateNumber;
+      if (highwayCandidateNumber >= 2)
+        return false; // There're two or more highway candidates from the junction.
+      isHighwayCandidateBeforeOutgoing = isCandidateBeforeOutgoing;
+    }
+  }
+  if (highwayCandidateNumber == 1)
+  {
+    turn = isHighwayCandidateBeforeOutgoing ? CarDirection::ExitHighwayToRight
+                                            : CarDirection::ExitHighwayToLeft;
+    return true;
+  }
+  return false;
+}
+
 /*!
  * \brief Returns false when
  * - the route leads from one big road to another one;
@@ -669,12 +735,25 @@ void GetTurnDirection(IRoutingResult const & result, NumMwmIds const & numMwmIds
   size_t ingoingCount;
   result.GetPossibleTurns(turnInfo.m_ingoing.m_segmentRange, ingoingPointOneSegment, junctionPoint,
                           ingoingCount, nodes);
+  if (nodes.isCandidatesAngleValid)
+  {
+    ASSERT(is_sorted(nodes.candidates.begin(), nodes.candidates
+        .end(), my::LessBy(&TurnCandidate::m_angle)),
+           ("Turn candidates should be sorted by its angle field."));
+  }
 
   if (nodes.candidates.size() == 0)
     return;
 
   bool const hasMultiTurns = HasMultiTurns(numMwmIds, nodes, turnInfo);
 
+  // Checking for exits from highways.
+  Segment firstOutgoingSeg;
+  bool const isFirstOutgoingSegValid =
+      turnInfo.m_outgoing.m_segmentRange.GetFirstSegment(numMwmIds, firstOutgoingSeg);
+  if (isFirstOutgoingSegValid && IsExit(nodes, turnInfo, firstOutgoingSeg, turn.m_turn))
+    return;
+
   if (DiscardTurnByIngoingAndOutgoingEdges(intermediateDirection, hasMultiTurns, turnInfo, turn, nodes))
     return;
 
@@ -684,8 +763,7 @@ void GetTurnDirection(IRoutingResult const & result, NumMwmIds const & numMwmIds
   }
   else
   {
-    Segment firstOutgoingSeg;
-    if (turnInfo.m_outgoing.m_segmentRange.GetFirstSegment(numMwmIds, firstOutgoingSeg))
+    if (isFirstOutgoingSegValid)
     {
       if (nodes.candidates.front().m_segment == firstOutgoingSeg)
         turn.m_turn = LeftmostDirection(turnAngle);