Merge pull request #5103 from bykoianko/release-70-uturn-loop-fixbeta-559beta-558beta-557beta-556beta-555beta-554beta-553beta-552beta-551beta-550beta-549release-70

[routing][release-70] Preventing interpretation loop features self intersection as uturn

4 files changed, 89 insertions, 6 deletions

diff --git a/routing/index_graph_starter.cpp b/routing/index_graph_starter.cpp
index 37c31baf51..1ffe4d8099 100644
--- a/routing/index_graph_starter.cpp
+++ b/routing/index_graph_starter.cpp
@@ -419,7 +419,7 @@ bool IndexGraphStarter::IsUTurn(TVertexType const & u, TVertexType const & v)
 
   auto const su = Compare(pu.first.GetPointId(), pu.second.GetPointId());
   auto const sv = Compare(pv.first.GetPointId(), pv.second.GetPointId());
-  return su != 0 && sv != 0 && su != sv;
+  return pu.second == pv.first && su != 0 && sv != 0 && su != sv;
 }
 
 double IndexGraphStarter::GetPenalties(TVertexType const & u, TVertexType const & v)
diff --git a/routing/routing_tests/index_graph_test.cpp b/routing/routing_tests/index_graph_test.cpp
index 46032edeb5..5b7a63d829 100644
--- a/routing/routing_tests/index_graph_test.cpp
+++ b/routing/routing_tests/index_graph_test.cpp
@@ -33,8 +33,9 @@ void TestRoute(IndexGraph & graph, RoadPoint const & start, RoadPoint const & fi
                size_t expectedLength, vector<RoadPoint> const * expectedRoute = nullptr)
 {
   vector<RoadPoint> route;
+  double timeSec = 0.0;
   IndexGraphStarter starter(graph, start, finish);
-  auto const resultCode = CalculateRoute(starter, route);
+  auto const resultCode = CalculateRoute(starter, route, timeSec);
 
   TEST_EQUAL(resultCode, AStarAlgorithm<IndexGraphStarter>::Result::OK, ());
   TEST_EQUAL(route.size(), expectedLength, ());
@@ -361,4 +362,60 @@ UNIT_TEST(SerializeSimpleGraph)
     TEST_EQUAL(graph.GetJointId({2, 1}), Joint::kInvalidId, ());
   }
 }
+
+//      Finish
+// 0.0003    *---------*
+//           |         |
+//           |         |
+//           |         |
+//           |         |
+//           |         |
+// 0.0002    *         *
+//           |         |
+//           |         |
+// 0.00015   *    F0   *
+//            \       /
+//              \   /
+// 0.0001         *---F0-*----*
+//                            ^
+//                            |
+//                            F1
+//                            |
+//                            |
+// 0                          * Start
+//   0         0.0001       0.0002
+// F0 is a two-way feature with a loop and F1 is an one-way one-segment feature.
+unique_ptr<IndexGraph> BuildLoopGraph()
+{
+  unique_ptr<TestGeometryLoader> loader = make_unique<TestGeometryLoader>();
+  loader->AddRoad(0 /* feature id */, false /* one way */, 100.0 /* speed */,
+                  RoadGeometry::Points({{0.0002, 0.0001}, {0.00015, 0.0001}, {0.0001, 0.0001},
+                                        {0.00015, 0.00015}, {0.00015, 0.0002}, {0.00015, 0.0003},
+                                        {0.0003, 0.00005}, {0.0002, 0.00005}, {0.00015, 0.00005},
+                                        {0.0001, 0.0001}}));
+  loader->AddRoad(1 /* feature id */, true /* one way */, 100.0 /* speed */,
+                  RoadGeometry::Points({{0.0002, 0.0}, {0.0002, 0.0001}/*, {0.0002, 0.0002}*/}));
+
+  vector<Joint> const joints = {
+    MakeJoint({{0 /* feature id */, 2 /* point id */}, {0, 9}}),         /* joint at point (1, 1) */
+    MakeJoint({{1, 1}, {0, 0}}),                                         /* joint at point (2, 1) */
+  };
+
+  traffic::TrafficCache const trafficCache;
+  unique_ptr<IndexGraph> graph =
+      make_unique<IndexGraph>(move(loader), CreateEstimator(trafficCache));
+  graph->Import(joints);
+  return graph;
+}
+
+// This test checks that the route from Start to Finish doesn't make an extra loop in F0.
+// If it was so the route time had been much more.
+UNIT_CLASS_TEST(RestrictionTest, LoopGraph)
+{
+  Init(BuildLoopGraph());
+  SetStarter(RoadPoint(1, 0) /* start */, RoadPoint(0, 7) /* finish */);
+
+  double constexpr kExpectedRouteTimeSec = 2.313397748;
+  TestRouteTime(*m_starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, kExpectedRouteTimeSec);
+}
 }  // namespace routing_test
diff --git a/routing/routing_tests/index_graph_tools.cpp b/routing/routing_tests/index_graph_tools.cpp
index b1f32b15f2..66b5d13b43 100644
--- a/routing/routing_tests/index_graph_tools.cpp
+++ b/routing/routing_tests/index_graph_tools.cpp
@@ -43,13 +43,15 @@ shared_ptr<EdgeEstimator> CreateEstimator(traffic::TrafficCache const & trafficC
 }
 
 AStarAlgorithm<IndexGraphStarter>::Result CalculateRoute(IndexGraphStarter & starter,
-                                                         vector<RoadPoint> & roadPoints)
+                                                         vector<RoadPoint> & roadPoints,
+                                                         double & timeSec)
 {
   AStarAlgorithm<IndexGraphStarter> algorithm;
   RoutingResult<IndexGraphStarter::TVertexType> routingResult;
 
   auto const resultCode = algorithm.FindPath(starter, starter.GetStartVertex(),
                                              starter.GetFinishVertex(), routingResult, {}, {});
+  timeSec = routingResult.distance;
 
   vector<Joint::Id> path;
   for (auto const & u : routingResult.path)
@@ -76,7 +78,8 @@ void TestRouteSegments(IndexGraphStarter & starter,
                        vector<RoadPoint> const & expectedRoute)
 {
   vector<RoadPoint> route;
-  auto const resultCode = CalculateRoute(starter, route);
+  double timeSec = 0.0;
+  auto const resultCode = CalculateRoute(starter, route, timeSec);
   TEST_EQUAL(resultCode, expectedRouteResult, ());
   TEST_EQUAL(route, expectedRoute, ());
 }
@@ -86,7 +89,8 @@ void TestRouteGeometry(IndexGraphStarter & starter,
                        vector<m2::PointD> const & expectedRouteGeom)
 {
   vector<RoadPoint> route;
-  auto const resultCode = CalculateRoute(starter, route);
+  double timeSec = 0.0;
+  auto const resultCode = CalculateRoute(starter, route, timeSec);
 
   TEST_EQUAL(resultCode, expectedRouteResult, ());
   vector<m2::PointD> geom;
@@ -101,6 +105,19 @@ void TestRouteGeometry(IndexGraphStarter & starter,
   TEST_EQUAL(geom, expectedRouteGeom, ());
 }
 
+void TestRouteTime(IndexGraphStarter & starter,
+                   AStarAlgorithm<IndexGraphStarter>::Result expectedRouteResult,
+                   double expectedTime)
+{
+  vector<RoadPoint> route;
+  double timeSec = 0.0;
+  auto const resultCode = CalculateRoute(starter, route, timeSec);
+
+  TEST_EQUAL(resultCode, expectedRouteResult, ());
+  double const kEpsilon = 1e-6;
+  TEST(my::AlmostEqualAbs(timeSec, expectedTime, kEpsilon), ());
+}
+
 void TestRestrictionPermutations(RestrictionVec restrictions,
                                  vector<m2::PointD> const & expectedRouteGeom,
                                  RoadPoint const & start, RoadPoint const & finish,
diff --git a/routing/routing_tests/index_graph_tools.hpp b/routing/routing_tests/index_graph_tools.hpp
index 25107f8bc4..2306612a9a 100644
--- a/routing/routing_tests/index_graph_tools.hpp
+++ b/routing/routing_tests/index_graph_tools.hpp
@@ -9,6 +9,8 @@
 
 #include "traffic/traffic_info.hpp"
 
+#include "indexer/classificator_loader.hpp"
+
 #include "geometry/point2d.hpp"
 
 #include "std/algorithm.hpp"
@@ -23,6 +25,8 @@ using namespace routing;
 
 struct RestrictionTest
 {
+  RestrictionTest() { classificator::Load(); }
+
   void Init(unique_ptr<IndexGraph> graph) { m_graph = move(graph); }
   void SetStarter(RoadPoint const & start, RoadPoint const & finish)
   {
@@ -119,7 +123,8 @@ routing::Joint MakeJoint(vector<routing::RoadPoint> const & points);
 shared_ptr<routing::EdgeEstimator> CreateEstimator(traffic::TrafficCache const & trafficCache);
 
 routing::AStarAlgorithm<routing::IndexGraphStarter>::Result CalculateRoute(
-    routing::IndexGraphStarter & graph, vector<routing::RoadPoint> & roadPoints);
+    routing::IndexGraphStarter & graph, vector<routing::RoadPoint> & roadPoints,
+    double & timeSec);
 
 void TestRouteSegments(
     routing::IndexGraphStarter & starter,
@@ -131,6 +136,10 @@ void TestRouteGeometry(
     routing::AStarAlgorithm<routing::IndexGraphStarter>::Result expectedRouteResult,
     vector<m2::PointD> const & expectedRouteGeom);
 
+void TestRouteTime(IndexGraphStarter & starter,
+                   AStarAlgorithm<IndexGraphStarter>::Result expectedRouteResult,
+                   double expectedTime);
+
 /// \brief Applies all possible permulations of |restrictions| to graph in |restrictionTest| and
 /// tests resulting routes.
 /// \note restrictionTest should have valid |restrictionTest.m_graph|.