Merge pull request #5002 from dobriy-eeh/release-fix-route-timesbeta-528

[release] [routing] fix route times

10 files changed, 119 insertions, 41 deletions

diff --git a/routing/CMakeLists.txt b/routing/CMakeLists.txt
index 3561bc0b39..7fe57ee03f 100644
--- a/routing/CMakeLists.txt
+++ b/routing/CMakeLists.txt
@@ -79,6 +79,7 @@ set(
   road_point.hpp
   route.cpp
   route.hpp
+  route_point.hpp
   router.cpp
   router.hpp
   router_delegate.cpp
diff --git a/routing/edge_estimator.cpp b/routing/edge_estimator.cpp
index 4813493c32..d929ccbc8a 100644
--- a/routing/edge_estimator.cpp
+++ b/routing/edge_estimator.cpp
@@ -70,13 +70,20 @@ double CarEdgeEstimator::CalcEdgesWeight(uint32_t featureId, RoadGeometry const
   uint32_t const finish = max(pointFrom, pointTo);
   ASSERT_LESS(finish, road.GetPointsCount(), ());
 
+  // Current time estimation are too optimistic.
+  // Need more accurate tuning: traffic lights, traffic jams, road models and so on.
+  // Add some penalty to make estimation of a more realistic.
+  // TODO: make accurate tuning, remove penalty.
+  double constexpr kTimePenalty = 1.8;
+
   double result = 0.0;
   double const speedMPS = road.GetSpeed() * kKMPH2MPS;
   auto const dir = pointFrom < pointTo ? TrafficInfo::RoadSegmentId::kForwardDirection
                                        : TrafficInfo::RoadSegmentId::kReverseDirection;
   for (uint32_t i = start; i < finish; ++i)
   {
-    double edgeWeight = TimeBetweenSec(road.GetPoint(i), road.GetPoint(i + 1), speedMPS);
+    double edgeWeight =
+        TimeBetweenSec(road.GetPoint(i), road.GetPoint(i + 1), speedMPS) * kTimePenalty;
     if (m_trafficColoring)
     {
       auto const it = m_trafficColoring->find(TrafficInfo::RoadSegmentId(featureId, i, dir));
diff --git a/routing/index_graph_starter.cpp b/routing/index_graph_starter.cpp
index d86b645369..22b64eb012 100644
--- a/routing/index_graph_starter.cpp
+++ b/routing/index_graph_starter.cpp
@@ -57,17 +57,20 @@ m2::PointD const & IndexGraphStarter::GetPoint(RoadPoint const & rp)
 }
 
 void IndexGraphStarter::RedressRoute(vector<Joint::Id> const & route,
-                                     vector<RoadPoint> & roadPoints)
+                                     vector<RoutePoint> & routePoints)
 {
   if (route.size() < 2)
   {
     if (route.size() == 1)
-      roadPoints.emplace_back(m_start.m_point);
+      routePoints.emplace_back(m_start.m_point, 0.0 /* time */);
     return;
   }
 
-  roadPoints.reserve(route.size() * 2);
+  routePoints.reserve(route.size() * 2);
 
+  EdgeEstimator const & estimator = m_graph.GetEstimator();
+
+  double routeTime = 0.0;
   for (size_t i = 0; i < route.size() - 1; ++i)
   {
     Joint::Id const prevJoint = route[i];
@@ -77,29 +80,23 @@ void IndexGraphStarter::RedressRoute(vector<Joint::Id> const & route,
     RoadPoint rp1;
     FindPointsWithCommonFeature(prevJoint, nextJoint, rp0, rp1);
     if (i == 0)
-      roadPoints.emplace_back(rp0);
+      routePoints.emplace_back(rp0, 0.0 /* time */);
 
     uint32_t const featureId = rp0.GetFeatureId();
     uint32_t const pointFrom = rp0.GetPointId();
     uint32_t const pointTo = rp1.GetPointId();
 
-    if (pointFrom < pointTo)
-    {
-      for (uint32_t pointId = pointFrom + 1; pointId < pointTo; ++pointId)
-        roadPoints.emplace_back(featureId, pointId);
-    }
-    else if (pointFrom > pointTo)
-    {
-      for (uint32_t pointId = pointFrom - 1; pointId > pointTo; --pointId)
-        roadPoints.emplace_back(featureId, pointId);
-    }
-    else
+    RoadGeometry const roadGeometry = m_graph.GetRoad(featureId);
+
+    CHECK_NOT_EQUAL(pointFrom, pointTo, ("featureId =", featureId));
+    uint32_t const step = pointFrom < pointTo ? 1 : -1;
+
+    for (uint32_t prevPointId = pointFrom; prevPointId != pointTo; prevPointId += step)
     {
-      CHECK(false,
-            ("Wrong equality pointFrom = pointTo =", pointFrom, ", featureId = ", featureId));
+      uint32_t const pointId = prevPointId + step;
+      routeTime += estimator.CalcEdgesWeight(featureId, roadGeometry, prevPointId, pointId);
+      routePoints.emplace_back(featureId, pointId, routeTime);
     }
-
-    roadPoints.emplace_back(rp1);
   }
 }
 
diff --git a/routing/index_graph_starter.hpp b/routing/index_graph_starter.hpp
index bd6140d6e6..14a13cd222 100644
--- a/routing/index_graph_starter.hpp
+++ b/routing/index_graph_starter.hpp
@@ -2,6 +2,7 @@
 
 #include "routing/index_graph.hpp"
 #include "routing/joint.hpp"
+#include "routing/route_point.hpp"
 
 #include "std/set.hpp"
 #include "std/utility.hpp"
@@ -62,7 +63,7 @@ public:
   // Add intermediate points to route (those don't correspond to any joint).
   //
   // Also convert joint ids to RoadPoints.
-  void RedressRoute(vector<Joint::Id> const & route, vector<RoadPoint> & roadPoints);
+  void RedressRoute(vector<Joint::Id> const & route, vector<RoutePoint> & routePoints);
 
 private:
   friend struct routing_test::RestrictionTest;
diff --git a/routing/route_point.hpp b/routing/route_point.hpp
new file mode 100644
index 0000000000..e652b044ef
--- /dev/null
+++ b/routing/route_point.hpp
@@ -0,0 +1,24 @@
+#pragma once
+
+#include "routing/road_point.hpp"
+
+#include "std/cstdint.hpp"
+
+namespace routing
+{
+class RoutePoint final
+{
+public:
+  RoutePoint() = default;
+  RoutePoint(RoadPoint const & rp, double time) : m_roadPoint(rp), m_time(time) {}
+  RoutePoint(uint32_t featureId, uint32_t pointId, double time) : m_roadPoint(featureId,pointId), m_time(time) {}
+
+  RoadPoint const & GetRoadPoint() const { return m_roadPoint; }
+  double GetTime() const { return m_time; }
+
+private:
+  RoadPoint m_roadPoint;
+  // time in seconds from start to arrival to point.
+  double m_time = 0.0;
+};
+}  // namespace routing
diff --git a/routing/routing.pro b/routing/routing.pro
index e0ab73694e..cb28a5aefd 100644
--- a/routing/routing.pro
+++ b/routing/routing.pro
@@ -100,6 +100,7 @@ HEADERS += \
     road_index.hpp \
     road_point.hpp \
     route.hpp \
+    route_point.hpp \
     router.hpp \
     router_delegate.hpp \
     routing_algorithm.hpp \
diff --git a/routing/routing_tests/index_graph_tools.cpp b/routing/routing_tests/index_graph_tools.cpp
index 51892a67a7..89ea259087 100644
--- a/routing/routing_tests/index_graph_tools.cpp
+++ b/routing/routing_tests/index_graph_tools.cpp
@@ -51,7 +51,14 @@ AStarAlgorithm<IndexGraphStarter>::Result CalculateRoute(IndexGraphStarter & sta
   auto const resultCode = algorithm.FindPath(
       starter, starter.GetStartJoint(), starter.GetFinishJoint(), routingResult, {}, {});
 
-  starter.RedressRoute(routingResult.path, roadPoints);
+  vector<RoutePoint> routePoints;
+  starter.RedressRoute(routingResult.path, routePoints);
+
+  roadPoints.clear();
+  roadPoints.reserve(routePoints.size());
+  for (auto const & point : routePoints)
+    roadPoints.push_back(point.GetRoadPoint());
+
   return resultCode;
 }
 
diff --git a/routing/single_mwm_router.cpp b/routing/single_mwm_router.cpp
index 085c923845..15ee3b486a 100644
--- a/routing/single_mwm_router.cpp
+++ b/routing/single_mwm_router.cpp
@@ -30,21 +30,6 @@ namespace
 size_t constexpr kMaxRoadCandidates = 6;
 float constexpr kProgressInterval = 2;
 uint32_t constexpr kDrawPointsPeriod = 10;
-
-vector<Junction> ConvertToJunctions(IndexGraphStarter & starter, vector<Joint::Id> const & joints)
-{
-  vector<RoadPoint> roadPoints;
-  starter.RedressRoute(joints, roadPoints);
-
-  vector<Junction> junctions;
-  junctions.reserve(roadPoints.size());
-
-  // TODO: Use real altitudes for pedestrian and bicycle routing.
-  for (RoadPoint const & point : roadPoints)
-    junctions.emplace_back(starter.GetPoint(point), feature::kDefaultAltitudeMeters);
-
-  return junctions;
-}
 }  // namespace
 
 namespace routing
@@ -148,9 +133,8 @@ IRouter::ResultCode SingleMwmRouter::DoCalculateRoute(MwmSet::MwmId const & mwmI
   case AStarAlgorithm<IndexGraphStarter>::Result::NoPath: return IRouter::RouteNotFound;
   case AStarAlgorithm<IndexGraphStarter>::Result::Cancelled: return IRouter::Cancelled;
   case AStarAlgorithm<IndexGraphStarter>::Result::OK:
-    vector<Junction> path = ConvertToJunctions(starter, routingResult.path);
-    shared_ptr<traffic::TrafficInfo::Coloring> trafficColoring = m_trafficCache.GetTrafficInfo(mwmId);
-    ReconstructRoute(m_directionsEngine.get(), m_roadGraph, trafficColoring, delegate, path, route);
+    if (!BuildRoute(mwmId, routingResult.path, delegate, starter, route))
+      return IRouter::InternalError;
     if (delegate.IsCancelled())
       return IRouter::Cancelled;
     return IRouter::NoError;
@@ -219,6 +203,52 @@ bool SingleMwmRouter::LoadIndex(MwmSet::MwmId const & mwmId, string const & coun
   }
 }
 
+bool SingleMwmRouter::BuildRoute(MwmSet::MwmId const & mwmId, vector<Joint::Id> const & joints,
+                                 RouterDelegate const & delegate, IndexGraphStarter & starter,
+                                 Route & route) const
+{
+  vector<RoutePoint> routePoints;
+  starter.RedressRoute(joints, routePoints);
+
+  vector<Junction> junctions;
+  junctions.reserve(routePoints.size());
+
+  // TODO: Use real altitudes for pedestrian and bicycle routing.
+  for (RoutePoint const & routePoint : routePoints)
+  {
+    junctions.emplace_back(starter.GetGraph().GetPoint(routePoint.GetRoadPoint()),
+                           feature::kDefaultAltitudeMeters);
+  }
+
+  shared_ptr<traffic::TrafficInfo::Coloring> trafficColoring = m_trafficCache.GetTrafficInfo(mwmId);
+  ReconstructRoute(m_directionsEngine.get(), m_roadGraph, trafficColoring, delegate, junctions,
+                   route);
+
+  // ReconstructRoute duplicates all points except start and finish.
+  // Therefore one needs fix time indexes to fit reconstructed polyline.
+  // TODO: rework ReconstructRoute and remove this stuff.
+  if (routePoints.size() < 2 || route.GetPoly().GetSize() + 2 != routePoints.size() * 2)
+  {
+    LOG(LERROR, ("Can't fix route times: polyline size =", route.GetPoly().GetSize(),
+                 "route points size =", routePoints.size()));
+    return false;
+  }
+
+  Route::TTimes times;
+  times.reserve(route.GetPoly().GetSize());
+  times.emplace_back(0, routePoints.front().GetTime());
+
+  for (size_t i = 1; i < routePoints.size() - 1; ++i)
+  {
+    times.emplace_back(i * 2 - 1, routePoints[i].GetTime());
+    times.emplace_back(i * 2, routePoints[i].GetTime());
+  }
+
+  times.emplace_back(route.GetPoly().GetSize() - 1, routePoints.back().GetTime());
+  route.SetSectionTimes(move(times));
+  return true;
+}
+
 // static
 unique_ptr<SingleMwmRouter> SingleMwmRouter::CreateCarRouter(
     Index const & index, traffic::TrafficCache const & trafficCache)
diff --git a/routing/single_mwm_router.hpp b/routing/single_mwm_router.hpp
index 3b758a3db8..321dcd1ad4 100644
--- a/routing/single_mwm_router.hpp
+++ b/routing/single_mwm_router.hpp
@@ -3,6 +3,7 @@
 #include "routing/directions_engine.hpp"
 #include "routing/edge_estimator.hpp"
 #include "routing/features_road_graph.hpp"
+#include "routing/joint.hpp"
 #include "routing/router.hpp"
 #include "routing/vehicle_model.hpp"
 
@@ -16,11 +17,13 @@
 namespace routing
 {
 class IndexGraph;
+class IndexGraphStarter;
 
 class SingleMwmRouter
 {
 public:
-  SingleMwmRouter(string const & name, Index const & index, traffic::TrafficCache const & trafficCache,
+  SingleMwmRouter(string const & name, Index const & index,
+                  traffic::TrafficCache const & trafficCache,
                   shared_ptr<VehicleModelFactory> vehicleModelFactory,
                   shared_ptr<EdgeEstimator> estimator,
                   unique_ptr<IDirectionsEngine> directionsEngine);
@@ -43,6 +46,9 @@ private:
   bool FindClosestEdge(MwmSet::MwmId const & mwmId, m2::PointD const & point,
                        Edge & closestEdge) const;
   bool LoadIndex(MwmSet::MwmId const & mwmId, string const & country, IndexGraph & graph);
+  bool BuildRoute(MwmSet::MwmId const & mwmId, vector<Joint::Id> const & joints,
+                  RouterDelegate const & delegate, IndexGraphStarter & starter,
+                  Route & route) const;
 
   string const m_name;
   Index const & m_index;
diff --git a/xcode/routing/routing.xcodeproj/project.pbxproj b/xcode/routing/routing.xcodeproj/project.pbxproj
index d0c63a85d7..e2fecd884e 100644
--- a/xcode/routing/routing.xcodeproj/project.pbxproj
+++ b/xcode/routing/routing.xcodeproj/project.pbxproj
@@ -30,6 +30,7 @@
 		0C5FEC6A1DDE193F0017688C /* road_index.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 0C5FEC671DDE193F0017688C /* road_index.hpp */; };
 		0C5FEC6B1DDE193F0017688C /* road_point.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 0C5FEC681DDE193F0017688C /* road_point.hpp */; };
 		0C5FEC6D1DDE19A40017688C /* index_graph_test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0C5FEC6C1DDE19A40017688C /* index_graph_test.cpp */; };
+		0C8705051E0182F200BCAF71 /* route_point.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 0C8705041E0182F200BCAF71 /* route_point.hpp */; };
 		3462FDAD1DC1E5BF00906FD7 /* libopening_hours.a in Frameworks */ = {isa = PBXBuildFile; fileRef = 3462FDAC1DC1E5BF00906FD7 /* libopening_hours.a */; };
 		56099E291CC7C97D00A7772A /* loaded_path_segment.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 56099E251CC7C97D00A7772A /* loaded_path_segment.hpp */; };
 		56099E2A1CC7C97D00A7772A /* routing_result_graph.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 56099E261CC7C97D00A7772A /* routing_result_graph.hpp */; };
@@ -269,6 +270,7 @@
 		0C5FEC671DDE193F0017688C /* road_index.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = road_index.hpp; sourceTree = "<group>"; };
 		0C5FEC681DDE193F0017688C /* road_point.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = road_point.hpp; sourceTree = "<group>"; };
 		0C5FEC6C1DDE19A40017688C /* index_graph_test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = index_graph_test.cpp; sourceTree = "<group>"; };
+		0C8705041E0182F200BCAF71 /* route_point.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = route_point.hpp; sourceTree = "<group>"; };
 		3462FDAC1DC1E5BF00906FD7 /* libopening_hours.a */ = {isa = PBXFileReference; lastKnownFileType = archive.ar; name = libopening_hours.a; path = "../../../omim-build/xcode/Debug/libopening_hours.a"; sourceTree = "<group>"; };
 		34F558351DBF2A2600A4FC11 /* common-debug.xcconfig */ = {isa = PBXFileReference; lastKnownFileType = text.xcconfig; name = "common-debug.xcconfig"; path = "../common-debug.xcconfig"; sourceTree = "<group>"; };
 		34F558361DBF2A2600A4FC11 /* common-release.xcconfig */ = {isa = PBXFileReference; lastKnownFileType = text.xcconfig; name = "common-release.xcconfig"; path = "../common-release.xcconfig"; sourceTree = "<group>"; };
@@ -713,6 +715,7 @@
 				0C5FEC661DDE193F0017688C /* road_index.cpp */,
 				0C5FEC671DDE193F0017688C /* road_index.hpp */,
 				0C5FEC681DDE193F0017688C /* road_point.hpp */,
+				0C8705041E0182F200BCAF71 /* route_point.hpp */,
 				0C08AA381DF8329B004195DD /* routing_exceptions.hpp */,
 				0C0DF9281DE898FF0055A22F /* routing_helpers.cpp */,
 				0C0DF9231DE898CF0055A22F /* single_mwm_router.cpp */,
@@ -843,6 +846,7 @@
 				6753441D1A3F644F00A0A8C3 /* router.hpp in Headers */,
 				A1616E2E1B6B60B3003F078E /* astar_progress.hpp in Headers */,
 				670EE5721B664796001E8064 /* directions_engine.hpp in Headers */,
+				0C8705051E0182F200BCAF71 /* route_point.hpp in Headers */,
 				A1876BC71BB19C4300C9C743 /* speed_camera.hpp in Headers */,
 				56EA2FD51D8FD8590083F01A /* routing_helpers.hpp in Headers */,
 				0C0DF9221DE898B70055A22F /* index_graph_starter.hpp in Headers */,