Merge pull request #5086 from dobriy-eeh/invert-index-graph

[routing] Invert index graph

18 files changed, 462 insertions, 545 deletions

diff --git a/routing/CMakeLists.txt b/routing/CMakeLists.txt
index 90b931fec5..4c8b0b7f01 100644
--- a/routing/CMakeLists.txt
+++ b/routing/CMakeLists.txt
@@ -95,6 +95,7 @@ set(
   routing_session.cpp
   routing_session.hpp
   routing_settings.hpp
+  segment.hpp
   single_mwm_router.cpp
   single_mwm_router.hpp
   speed_camera.cpp
diff --git a/routing/edge_estimator.cpp b/routing/edge_estimator.cpp
index 9d6f3c48f4..be1c06eb84 100644
--- a/routing/edge_estimator.cpp
+++ b/routing/edge_estimator.cpp
@@ -41,8 +41,7 @@ public:
   // EdgeEstimator overrides:
   void Start(MwmSet::MwmId const & mwmId) override;
   void Finish() override;
-  double CalcEdgesWeight(uint32_t featureId, RoadGeometry const & road, uint32_t pointFrom,
-                         uint32_t pointTo) const override;
+  double CalcSegmentWeight(Segment const & segment, RoadGeometry const & road) const override;
   double CalcHeuristic(m2::PointD const & from, m2::PointD const & to) const override;
 
 private:
@@ -67,12 +66,10 @@ void CarEdgeEstimator::Finish()
   m_trafficColoring.reset();
 }
 
-double CarEdgeEstimator::CalcEdgesWeight(uint32_t featureId, RoadGeometry const & road,
-                                         uint32_t pointFrom, uint32_t pointTo) const
+double CarEdgeEstimator::CalcSegmentWeight(Segment const & segment, RoadGeometry const & road) const
 {
-  uint32_t const start = min(pointFrom, pointTo);
-  uint32_t const finish = max(pointFrom, pointTo);
-  ASSERT_LESS(finish, road.GetPointsCount(), ());
+  ASSERT_LESS(segment.GetPointId(true /* front */), road.GetPointsCount(), ());
+  ASSERT_LESS(segment.GetPointId(false /* front */), road.GetPointsCount(), ());
 
   // Current time estimation are too optimistic.
   // Need more accurate tuning: traffic lights, traffic jams, road models and so on.
@@ -80,23 +77,21 @@ double CarEdgeEstimator::CalcEdgesWeight(uint32_t featureId, RoadGeometry const
   // 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 result = TimeBetweenSec(road.GetPoint(segment.GetPointId(false /* front */)),
+                                 road.GetPoint(segment.GetPointId(true /* front */)), speedMPS) *
+                  kTimePenalty;
+
+  if (m_trafficColoring)
   {
-    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));
-      SpeedGroup const speedGroup = (it == m_trafficColoring->cend()) ? SpeedGroup::Unknown
-                                                                      : it->second;
-      ASSERT_LESS(speedGroup, SpeedGroup::Count, ());
-      edgeWeight *= CalcTrafficFactor(speedGroup);
-    }
-    result += edgeWeight;
+    auto const dir = segment.IsForward() ? TrafficInfo::RoadSegmentId::kForwardDirection
+                                         : TrafficInfo::RoadSegmentId::kReverseDirection;
+    auto const it = m_trafficColoring->find(
+        TrafficInfo::RoadSegmentId(segment.GetFeatureId(), segment.GetSegmentIdx(), dir));
+    SpeedGroup const speedGroup =
+        (it == m_trafficColoring->cend()) ? SpeedGroup::Unknown : it->second;
+    ASSERT_LESS(speedGroup, SpeedGroup::Count, ());
+    result *= CalcTrafficFactor(speedGroup);
   }
 
   return result;
diff --git a/routing/edge_estimator.hpp b/routing/edge_estimator.hpp
index f78f2a7c25..1b64e84fa0 100644
--- a/routing/edge_estimator.hpp
+++ b/routing/edge_estimator.hpp
@@ -1,6 +1,7 @@
 #pragma once
 
 #include "routing/geometry.hpp"
+#include "routing/segment.hpp"
 #include "routing/vehicle_model.hpp"
 
 #include "traffic/traffic_cache.hpp"
@@ -21,11 +22,9 @@ public:
 
   virtual void Start(MwmSet::MwmId const & mwmId) = 0;
   virtual void Finish() = 0;
-  virtual double CalcEdgesWeight(uint32_t featureId, RoadGeometry const & road, uint32_t pointFrom,
-                                 uint32_t pointTo) const = 0;
+  virtual double CalcSegmentWeight(Segment const & segment, RoadGeometry const & road) const = 0;
   virtual double CalcHeuristic(m2::PointD const & from, m2::PointD const & to) const = 0;
 
-
   static shared_ptr<EdgeEstimator> CreateForCar(IVehicleModel const & vehicleModel,
                                                 traffic::TrafficCache const & trafficCache);
 };
diff --git a/routing/index_graph.cpp b/routing/index_graph.cpp
index 856a13d1c4..5772766a2b 100644
--- a/routing/index_graph.cpp
+++ b/routing/index_graph.cpp
@@ -13,23 +13,21 @@ IndexGraph::IndexGraph(unique_ptr<GeometryLoader> loader, shared_ptr<EdgeEstimat
   ASSERT(m_estimator, ());
 }
 
-void IndexGraph::GetEdgeList(Joint::Id jointId, bool isOutgoing, vector<JointEdge> & edges)
+void IndexGraph::GetEdgeList(Segment const & segment, bool isOutgoing, vector<SegmentEdge> & edges)
 {
-  m_jointIndex.ForEachPoint(jointId, [this, &edges, isOutgoing](RoadPoint const & rp) {
-    GetNeighboringEdges(rp, isOutgoing, edges);
-  });
-}
-
-m2::PointD const & IndexGraph::GetPoint(Joint::Id jointId)
-{
-  return m_geometry.GetPoint(m_jointIndex.GetPoint(jointId));
-}
+  RoadPoint const roadPoint = segment.GetRoadPoint(isOutgoing);
+  Joint::Id const jointId = m_roadIndex.GetJointId(roadPoint);
 
-m2::PointD const & IndexGraph::GetPoint(RoadPoint const & rp)
-{
-  RoadGeometry const & road = GetGeometry().GetRoad(rp.GetFeatureId());
-  CHECK_LESS(rp.GetPointId(), road.GetPointsCount(), ());
-  return road.GetPoint(rp.GetPointId());
+  if (jointId != Joint::kInvalidId)
+  {
+    m_jointIndex.ForEachPoint(jointId, [&](RoadPoint const & rp) {
+      GetNeighboringEdges(segment, rp, isOutgoing, edges);
+    });
+  }
+  else
+  {
+    GetNeighboringEdges(segment, roadPoint, isOutgoing, edges);
+  }
 }
 
 void IndexGraph::Build(uint32_t numJoints) { m_jointIndex.Build(m_roadIndex, numJoints); }
@@ -41,62 +39,34 @@ void IndexGraph::Import(vector<Joint> const & joints)
   Build(static_cast<uint32_t>(joints.size()));
 }
 
-Joint::Id IndexGraph::InsertJoint(RoadPoint const & rp)
+double IndexGraph::CalcSegmentWeight(Segment const & segment)
 {
-  Joint::Id const existId = m_roadIndex.GetJointId(rp);
-  if (existId != Joint::kInvalidId)
-    return existId;
-
-  Joint::Id const jointId = m_jointIndex.InsertJoint(rp);
-  m_roadIndex.AddJoint(rp, jointId);
-  return jointId;
+  return m_estimator->CalcSegmentWeight(segment, m_geometry.GetRoad(segment.GetFeatureId()));
 }
 
-bool IndexGraph::JointLiesOnRoad(Joint::Id jointId, uint32_t featureId) const
-{
-  bool result = false;
-  m_jointIndex.ForEachPoint(jointId, [&result, featureId](RoadPoint const & rp) {
-    if (rp.GetFeatureId() == featureId)
-      result = true;
-  });
-
-  return result;
-}
-
-void IndexGraph::GetNeighboringEdges(RoadPoint const & rp, bool isOutgoing,
-                                     vector<JointEdge> & edges)
+void IndexGraph::GetNeighboringEdges(Segment const & from, RoadPoint const & rp, bool isOutgoing,
+                                     vector<SegmentEdge> & edges)
 {
   RoadGeometry const & road = m_geometry.GetRoad(rp.GetFeatureId());
-
   bool const bidirectional = !road.IsOneWay();
-  if (!isOutgoing || bidirectional)
-    GetNeighboringEdge(road, rp, false /* forward */, edges);
 
-  if (isOutgoing || bidirectional)
-    GetNeighboringEdge(road, rp, true /* forward */, edges);
-}
+  if ((isOutgoing || bidirectional) && rp.GetPointId() + 1 < road.GetPointsCount())
+  {
+    GetNeighboringEdge(from, Segment(rp.GetFeatureId(), rp.GetPointId(), isOutgoing), isOutgoing,
+                       edges);
+  }
 
-void IndexGraph::GetNeighboringEdge(RoadGeometry const & road, RoadPoint const & rp, bool forward,
-                                    vector<JointEdge> & edges) const
-{
-  pair<Joint::Id, uint32_t> const & neighbor = m_roadIndex.FindNeighbor(rp, forward);
-  if (neighbor.first != Joint::kInvalidId)
+  if ((!isOutgoing || bidirectional) && rp.GetPointId() > 0)
   {
-    double const distance =
-        m_estimator->CalcEdgesWeight(rp.GetFeatureId(), road, rp.GetPointId(), neighbor.second);
-    edges.push_back({neighbor.first, distance});
+    GetNeighboringEdge(from, Segment(rp.GetFeatureId(), rp.GetPointId() - 1, !isOutgoing),
+                       isOutgoing, edges);
   }
 }
 
-void IndexGraph::GetDirectedEdge(uint32_t featureId, uint32_t pointFrom, uint32_t pointTo,
-                                 Joint::Id target, bool forward, vector<JointEdge> & edges)
+void IndexGraph::GetNeighboringEdge(Segment const & from, Segment const & to, bool isOutgoing,
+                                    vector<SegmentEdge> & edges)
 {
-  RoadGeometry const & road = m_geometry.GetRoad(featureId);
-
-  if (road.IsOneWay() && forward != (pointFrom < pointTo))
-    return;
-
-  double const distance = m_estimator->CalcEdgesWeight(featureId, road, pointFrom, pointTo);
-  edges.emplace_back(target, distance);
+  double const weight = CalcSegmentWeight(isOutgoing ? to : from);
+  edges.emplace_back(to, weight);
 }
 }  // namespace routing
diff --git a/routing/index_graph.hpp b/routing/index_graph.hpp
index fa5430af06..e9b441dc02 100644
--- a/routing/index_graph.hpp
+++ b/routing/index_graph.hpp
@@ -6,6 +6,7 @@
 #include "routing/joint_index.hpp"
 #include "routing/road_index.hpp"
 #include "routing/road_point.hpp"
+#include "routing/segment.hpp"
 
 #include "geometry/point2d.hpp"
 
@@ -17,35 +18,16 @@
 
 namespace routing
 {
-class JointEdge final
-{
-public:
-  JointEdge(Joint::Id target, double weight) : m_target(target), m_weight(weight) {}
-  Joint::Id GetTarget() const { return m_target; }
-  double GetWeight() const { return m_weight; }
-
-private:
-  // Target is vertex going to for outgoing edges, vertex going from for ingoing edges.
-  Joint::Id const m_target;
-  double const m_weight;
-};
-
 class IndexGraph final
 {
 public:
   IndexGraph() = default;
   explicit IndexGraph(unique_ptr<GeometryLoader> loader, shared_ptr<EdgeEstimator> estimator);
 
-  // Creates edge for points in same feature.
-  void GetDirectedEdge(uint32_t featureId, uint32_t pointFrom, uint32_t pointTo, Joint::Id target,
-                       bool forward, vector<JointEdge> & edges);
-  void GetNeighboringEdges(RoadPoint const & rp, bool isOutgoing, vector<JointEdge> & edges);
+  // Put outgoing (or ingoing) egdes for segment to the 'edges' vector.
+  void GetEdgeList(Segment const & segment, bool isOutgoing, vector<SegmentEdge> & edges);
 
-  // Put outgoing (or ingoing) egdes for jointId to the 'edges' vector.
-  void GetEdgeList(Joint::Id jointId, bool isOutgoing, vector<JointEdge> & edges);
   Joint::Id GetJointId(RoadPoint const & rp) const { return m_roadIndex.GetJointId(rp); }
-  m2::PointD const & GetPoint(Joint::Id jointId);
-  m2::PointD const & GetPoint(RoadPoint const & rp);
 
   Geometry & GetGeometry() { return m_geometry; }
   EdgeEstimator const & GetEstimator() const { return *m_estimator; }
@@ -57,8 +39,6 @@ public:
 
   void Build(uint32_t numJoints);
   void Import(vector<Joint> const & joints);
-  Joint::Id InsertJoint(RoadPoint const & rp);
-  bool JointLiesOnRoad(Joint::Id jointId, uint32_t featureId) const;
 
   void PushFromSerializer(Joint::Id jointId, RoadPoint const & rp)
   {
@@ -71,15 +51,12 @@ public:
     m_roadIndex.ForEachRoad(forward<F>(f));
   }
 
-  template <typename F>
-  void ForEachPoint(Joint::Id jointId, F && f) const
-  {
-    m_jointIndex.ForEachPoint(jointId, forward<F>(f));
-  }
-
 private:
-  void GetNeighboringEdge(RoadGeometry const & road, RoadPoint const & rp, bool forward,
-                          vector<JointEdge> & edges) const;
+  double CalcSegmentWeight(Segment const & segment);
+  void GetNeighboringEdges(Segment const & from, RoadPoint const & rp, bool isOutgoing,
+                           vector<SegmentEdge> & edges);
+  void GetNeighboringEdge(Segment const & from, Segment const & to, bool isOutgoing,
+                          vector<SegmentEdge> & edges);
 
   Geometry m_geometry;
   shared_ptr<EdgeEstimator> m_estimator;
diff --git a/routing/index_graph_starter.cpp b/routing/index_graph_starter.cpp
index 327bc70e81..4362e2e11c 100644
--- a/routing/index_graph_starter.cpp
+++ b/routing/index_graph_starter.cpp
@@ -4,190 +4,103 @@
 
 namespace routing
 {
-IndexGraphStarter::IndexGraphStarter(IndexGraph & graph, RoadPoint const & startPoint,
-                                     RoadPoint const & finishPoint)
-  : m_graph(graph)
-  , m_start(graph, startPoint, graph.GetNumJoints())
-  , m_finish(graph, finishPoint, graph.GetNumJoints() + 1)
-{
-  m_start.SetupJointId(graph);
+// static
+Segment constexpr IndexGraphStarter::kStartFakeSegment;
+Segment constexpr IndexGraphStarter::kFinishFakeSegment;
 
-  if (startPoint == finishPoint)
-    m_finish.m_jointId = m_start.m_jointId;
-  else
-    m_finish.SetupJointId(graph);
+IndexGraphStarter::IndexGraphStarter(IndexGraph & graph, FakeVertex const & start,
+                                     FakeVertex const & finish)
+  : m_graph(graph), m_start(start), m_finish(finish)
+{
 }
 
-m2::PointD const & IndexGraphStarter::GetPoint(Joint::Id jointId)
+m2::PointD const & IndexGraphStarter::GetPoint(Segment const & segment, bool front)
 {
-  if (jointId == m_start.m_fakeId)
-    return m_graph.GetGeometry().GetPoint(m_start.m_point);
+  if (segment == kStartFakeSegment)
+    return m_start.GetPoint();
 
-  if (jointId == m_finish.m_fakeId)
-    return m_graph.GetGeometry().GetPoint(m_finish.m_point);
+  if (segment == kFinishFakeSegment)
+    return m_finish.GetPoint();
 
-  return m_graph.GetPoint(jointId);
+  return m_graph.GetGeometry().GetPoint(segment.GetRoadPoint(front));
 }
 
-m2::PointD const & IndexGraphStarter::GetPoint(RoadPoint const & rp)
+// static
+size_t IndexGraphStarter::GetRouteNumPoints(vector<Segment> const & route)
 {
-  return m_graph.GetPoint(rp);
+  // if route contains start and finish fakes only, it doesn't have segment points.
+  // TODO: add start and finish when RecounstructRoute will be reworked.
+  if (route.size() <= 2)
+    return 0;
+
+  // -2 for fake start and finish.
+  // +1 for front point of first segment.
+  return route.size() - 1;
 }
 
-void IndexGraphStarter::RedressRoute(vector<Joint::Id> const & route,
-                                     vector<RoutePoint> & routePoints)
+m2::PointD const & IndexGraphStarter::GetRoutePoint(vector<Segment> const & route,
+                                                    size_t pointIndex)
 {
-  if (route.size() < 2)
+  if (pointIndex == 0)
   {
-    if (route.size() == 1)
-      routePoints.emplace_back(m_start.m_point, 0.0 /* time */);
-    return;
+    CHECK_GREATER(route.size(), 1, ());
+    return GetPoint(route[1], false /* front */);
   }
 
-  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];
-    Joint::Id const nextJoint = route[i + 1];
-
-    RoadPoint rp0;
-    RoadPoint rp1;
-    FindPointsWithCommonFeature(prevJoint, nextJoint, rp0, rp1);
-    if (i == 0)
-      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();
-
-    RoadGeometry const roadGeometry = m_graph.GetGeometry().GetRoad(featureId);
-
-    uint32_t const step = pointFrom < pointTo ? 1 : -1;
-
-    for (uint32_t prevPointId = pointFrom; prevPointId != pointTo; prevPointId += step)
-    {
-      uint32_t const pointId = prevPointId + step;
-      routeTime += estimator.CalcEdgesWeight(featureId, roadGeometry, prevPointId, pointId);
-      routePoints.emplace_back(featureId, pointId, routeTime);
-    }
-  }
+  CHECK_LESS(pointIndex, route.size(), ());
+  return GetPoint(route[pointIndex], true /* front */);
 }
 
-void IndexGraphStarter::GetEdgesList(Joint::Id jointId, bool isOutgoing, vector<JointEdge> & edges)
+void IndexGraphStarter::GetEdgesList(Segment const & segment, bool isOutgoing,
+                                     vector<SegmentEdge> & edges)
 {
   edges.clear();
 
-  if (jointId == m_start.m_fakeId)
+  if (segment == kStartFakeSegment)
   {
-    GetFakeEdges(m_start, m_finish, isOutgoing, edges);
+    GetFakeToNormalEdges(m_start, edges);
     return;
   }
 
-  if (jointId == m_finish.m_fakeId)
+  if (segment == kFinishFakeSegment)
   {
-    GetFakeEdges(m_finish, m_start, isOutgoing, edges);
+    GetFakeToNormalEdges(m_finish, edges);
     return;
   }
 
-  m_graph.GetEdgeList(jointId, isOutgoing, edges);
-  GetArrivalFakeEdges(jointId, m_start, isOutgoing, edges);
-  GetArrivalFakeEdges(jointId, m_finish, isOutgoing, edges);
-}
-
-void IndexGraphStarter::GetFakeEdges(IndexGraphStarter::FakeJoint const & from,
-                                     IndexGraphStarter::FakeJoint const & to, bool isOutgoing,
-                                     vector<JointEdge> & edges)
-{
-  m_graph.GetNeighboringEdges(from.m_point, isOutgoing, edges);
-
-  if (!to.BelongsToGraph() && from.m_point.GetFeatureId() == to.m_point.GetFeatureId())
-  {
-    m_graph.GetDirectedEdge(from.m_point.GetFeatureId(), from.m_point.GetPointId(),
-                            to.m_point.GetPointId(), to.m_jointId, isOutgoing, edges);
-  }
+  m_graph.GetEdgeList(segment, isOutgoing, edges);
+  GetNormalToFakeEdge(segment, m_start, kStartFakeSegment, isOutgoing, edges);
+  GetNormalToFakeEdge(segment, m_finish, kFinishFakeSegment, isOutgoing, edges);
 }
 
-void IndexGraphStarter::GetArrivalFakeEdges(Joint::Id jointId,
-                                            IndexGraphStarter::FakeJoint const & fakeJoint,
-                                            bool isOutgoing, vector<JointEdge> & edges)
+void IndexGraphStarter::GetFakeToNormalEdges(FakeVertex const & fakeVertex,
+                                             vector<SegmentEdge> & edges)
 {
-  if (fakeJoint.BelongsToGraph())
-    return;
+  GetFakeToNormalEdge(fakeVertex, true /* forward */, edges);
 
-  if (!m_graph.JointLiesOnRoad(jointId, fakeJoint.m_point.GetFeatureId()))
-    return;
-
-  vector<JointEdge> startEdges;
-  m_graph.GetNeighboringEdges(fakeJoint.m_point, !isOutgoing, startEdges);
-  for (JointEdge const & edge : startEdges)
-  {
-    if (edge.GetTarget() == jointId)
-      edges.emplace_back(fakeJoint.m_jointId, edge.GetWeight());
-  }
+  if (!m_graph.GetGeometry().GetRoad(fakeVertex.GetFeatureId()).IsOneWay())
+    GetFakeToNormalEdge(fakeVertex, false /* forward */, edges);
 }
 
-void IndexGraphStarter::FindPointsWithCommonFeature(Joint::Id jointId0, Joint::Id jointId1,
-                                                    RoadPoint & result0, RoadPoint & result1)
+void IndexGraphStarter::GetFakeToNormalEdge(FakeVertex const & fakeVertex, bool forward,
+                                            vector<SegmentEdge> & edges)
 {
-  bool found = false;
-  double minWeight = -1.0;
-
-  ForEachPoint(jointId0, [&](RoadPoint const & rp0) {
-    ForEachPoint(jointId1, [&](RoadPoint const & rp1) {
-      if (rp0.GetFeatureId() != rp1.GetFeatureId())
-        return;
-
-      RoadGeometry const & road = m_graph.GetGeometry().GetRoad(rp0.GetFeatureId());
-      if (road.IsOneWay() && rp0.GetPointId() > rp1.GetPointId())
-        return;
-
-      if (found)
-      {
-        if (minWeight < 0.0)
-        {
-          // CalcEdgesWeight is very expensive.
-          // So calculate it only if second common feature found.
-          RoadGeometry const & prevRoad = m_graph.GetGeometry().GetRoad(result0.GetFeatureId());
-          minWeight = m_graph.GetEstimator().CalcEdgesWeight(
-              rp0.GetFeatureId(), prevRoad, result0.GetPointId(), result1.GetPointId());
-        }
-
-        double const weight = m_graph.GetEstimator().CalcEdgesWeight(
-            rp0.GetFeatureId(), road, rp0.GetPointId(), rp1.GetPointId());
-        if (weight < minWeight)
-        {
-          minWeight = weight;
-          result0 = rp0;
-          result1 = rp1;
-        }
-      }
-      else
-      {
-        result0 = rp0;
-        result1 = rp1;
-        found = true;
-      }
-    });
-  });
-
-  CHECK(found, ("Can't find common feature for joints", jointId0, jointId1));
+  Segment const segment(fakeVertex.GetFeatureId(), fakeVertex.GetSegmentIdx(), forward);
+  RoadPoint const & roadPoint = segment.GetRoadPoint(true /* front */);
+  m2::PointD const & pointTo = m_graph.GetGeometry().GetPoint(roadPoint);
+  double const weight = m_graph.GetEstimator().CalcHeuristic(fakeVertex.GetPoint(), pointTo);
+  edges.emplace_back(segment, weight);
 }
 
-// IndexGraphStarter::FakeJoint --------------------------------------------------------------------
-IndexGraphStarter::FakeJoint::FakeJoint(IndexGraph const & graph, RoadPoint const & point,
-                                        Joint::Id fakeId)
-  : m_point(point), m_fakeId(fakeId), m_jointId(Joint::kInvalidId)
+void IndexGraphStarter::GetNormalToFakeEdge(Segment const & segment, FakeVertex const & fakeVertex,
+                                            Segment const & fakeSegment, bool isOutgoing,
+                                            vector<SegmentEdge> & edges)
 {
-}
+  if (!fakeVertex.Fits(segment))
+    return;
 
-void IndexGraphStarter::FakeJoint::SetupJointId(IndexGraph const & graph)
-{
-  m_jointId = graph.GetJointId(m_point);
-  if (m_jointId == Joint::kInvalidId)
-    m_jointId = m_fakeId;
+  m2::PointD const & pointFrom = m_graph.GetGeometry().GetPoint(segment.GetRoadPoint(isOutgoing));
+  double const weight = m_graph.GetEstimator().CalcHeuristic(pointFrom, fakeVertex.GetPoint());
+  edges.emplace_back(fakeSegment, weight);
 }
 }  // namespace routing
diff --git a/routing/index_graph_starter.hpp b/routing/index_graph_starter.hpp
index f6f22f8a23..7a30d6cb9a 100644
--- a/routing/index_graph_starter.hpp
+++ b/routing/index_graph_starter.hpp
@@ -4,97 +4,85 @@
 #include "routing/joint.hpp"
 #include "routing/route_point.hpp"
 
+#include "std/limits.hpp"
 #include "std/utility.hpp"
+#include "std/vector.hpp"
 
 namespace routing
 {
-// The problem:
-// IndexGraph contains only road points connected in joints.
-// So it is possible IndexGraph doesn't contain start and finish.
-//
-// IndexGraphStarter adds fake start and finish joint ids for AStarAlgorithm.
-//
+// IndexGraphStarter adds fake start and finish vertexes for AStarAlgorithm.
 class IndexGraphStarter final
 {
 public:
   // AStarAlgorithm types aliases:
-  using TVertexType = Joint::Id;
-  using TEdgeType = JointEdge;
+  using TVertexType = Segment;
+  using TEdgeType = SegmentEdge;
 
-  IndexGraphStarter(IndexGraph & graph, RoadPoint const & startPoint,
-                    RoadPoint const & finishPoint);
+  class FakeVertex final
+  {
+  public:
+    FakeVertex(uint32_t featureId, uint32_t segmentIdx, m2::PointD const & point)
+      : m_featureId(featureId), m_segmentIdx(segmentIdx), m_point(point)
+    {
+    }
+
+    uint32_t GetFeatureId() const { return m_featureId; }
+    uint32_t GetSegmentIdx() const { return m_segmentIdx; }
+    m2::PointD const & GetPoint() const { return m_point; }
+
+    bool Fits(Segment const & segment) const
+    {
+      return segment.GetFeatureId() == m_featureId && segment.GetSegmentIdx() == m_segmentIdx;
+    }
+
+  private:
+    uint32_t const m_featureId;
+    uint32_t const m_segmentIdx;
+    m2::PointD const m_point;
+  };
+
+  IndexGraphStarter(IndexGraph & graph, FakeVertex const & start, FakeVertex const & finish);
 
   IndexGraph & GetGraph() const { return m_graph; }
-  Joint::Id GetStartJoint() const { return m_start.m_jointId; }
-  Joint::Id GetFinishJoint() const { return m_finish.m_jointId; }
+  Segment const & GetStart() const { return kStartFakeSegment; }
+  Segment const & GetFinish() const { return kFinishFakeSegment; }
+  m2::PointD const & GetPoint(Segment const & segment, bool isOutgoing);
 
-  m2::PointD const & GetPoint(Joint::Id jointId);
-  m2::PointD const & GetPoint(RoadPoint const & rp);
+  static size_t GetRouteNumPoints(vector<Segment> const & route);
+  m2::PointD const & GetRoutePoint(vector<Segment> const & route, size_t pointIndex);
 
-  void GetOutgoingEdgesList(Joint::Id jointId, vector<JointEdge> & edges)
+  void GetOutgoingEdgesList(TVertexType const & segment, vector<TEdgeType> & edges)
   {
-    GetEdgesList(jointId, true /* isOutgoing */, edges);
+    GetEdgesList(segment, true /* isOutgoing */, edges);
   }
 
-  void GetIngoingEdgesList(Joint::Id jointId, vector<JointEdge> & edges)
+  void GetIngoingEdgesList(TVertexType const & segment, vector<TEdgeType> & edges)
   {
-    GetEdgesList(jointId, false /* isOutgoing */, edges);
+    GetEdgesList(segment, false /* isOutgoing */, edges);
   }
 
-  double HeuristicCostEstimate(Joint::Id from, Joint::Id to)
+  double HeuristicCostEstimate(TVertexType const & from, TVertexType const & to)
   {
-    return m_graph.GetEstimator().CalcHeuristic(GetPoint(from), GetPoint(to));
+    return m_graph.GetEstimator().CalcHeuristic(GetPoint(from, true /* front */),
+                                                GetPoint(to, true /* front */));
   }
 
-  // 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<RoutePoint> & routePoints);
-
 private:
-  struct FakeJoint final
-  {
-    FakeJoint(IndexGraph const & graph, RoadPoint const & point, Joint::Id fakeId);
-
-    void SetupJointId(IndexGraph const & graph);
-    bool BelongsToGraph() const { return m_jointId != m_fakeId; }
-
-    RoadPoint const m_point;
-    Joint::Id const m_fakeId;
-    Joint::Id m_jointId;
-  };
-
-  template <typename F>
-  void ForEachPoint(Joint::Id jointId, F && f) const
-  {
-    if (jointId == m_start.m_fakeId)
-    {
-      f(m_start.m_point);
-      return;
-    }
-
-    if (jointId == m_finish.m_fakeId)
-    {
-      f(m_finish.m_point);
-      return;
-    }
-
-    m_graph.ForEachPoint(jointId, forward<F>(f));
-  }
-
-  void GetEdgesList(Joint::Id jointId, bool isOutgoing, vector<JointEdge> & edges);
-  void GetFakeEdges(FakeJoint const & from, FakeJoint const & to, bool isOutgoing,
-                    vector<JointEdge> & edges);
-  void GetArrivalFakeEdges(Joint::Id jointId, FakeJoint const & fakeJoint, bool isOutgoing,
-                           vector<JointEdge> & edges);
-
-  // Find two road points lying on the same feature.
-  // If there are several pairs of such points, return pair with minimal distance.
-  void FindPointsWithCommonFeature(Joint::Id jointId0, Joint::Id jointId1, RoadPoint & result0,
-                                   RoadPoint & result1);
+  static Segment constexpr kStartFakeSegment =
+      Segment(numeric_limits<uint32_t>::max(), numeric_limits<uint32_t>::max(), false);
+  static Segment constexpr kFinishFakeSegment =
+      Segment(numeric_limits<uint32_t>::max(), numeric_limits<uint32_t>::max(), true);
+
+  void GetEdgesList(Segment const & segment, bool isOutgoing, vector<SegmentEdge> & edges);
+  void GetFakeToNormalEdges(FakeVertex const & fakeVertex, vector<SegmentEdge> & edges);
+  void GetFakeToNormalEdge(FakeVertex const & fakeVertex, bool forward,
+                           vector<SegmentEdge> & edges);
+  void GetNormalToFakeEdge(Segment const & segment, FakeVertex const & fakeVertex,
+                           Segment const & fakeSegment, bool isOutgoing,
+                           vector<SegmentEdge> & edges);
 
   IndexGraph & m_graph;
-  FakeJoint m_start;
-  FakeJoint m_finish;
+  FakeVertex const m_start;
+  FakeVertex const m_finish;
 };
 }  // namespace routing
diff --git a/routing/joint_index.cpp b/routing/joint_index.cpp
index 33b0a69dcb..b298618e5f 100644
--- a/routing/joint_index.cpp
+++ b/routing/joint_index.cpp
@@ -4,23 +4,8 @@
 
 namespace routing
 {
-Joint::Id JointIndex::InsertJoint(RoadPoint const & rp)
-{
-  Joint::Id const jointId = GetNumJoints();
-  m_points.emplace_back(rp);
-  m_offsets.emplace_back(m_points.size());
-  return jointId;
-}
-
-void JointIndex::AppendToJoint(Joint::Id jointId, RoadPoint const & rp)
-{
-  m_dynamicJoints[jointId].AddPoint(rp);
-}
-
 void JointIndex::Build(RoadIndex const & roadIndex, uint32_t numJoints)
 {
-  m_dynamicJoints.clear();
-
   // + 1 is protection for 'End' method from out of bounds.
   // Call End(numJoints-1) requires more size, so add one more item.
   // Therefore m_offsets.size() == numJoints + 1,
diff --git a/routing/joint_index.hpp b/routing/joint_index.hpp
index af9dabe129..4bcb12e4ac 100644
--- a/routing/joint_index.hpp
+++ b/routing/joint_index.hpp
@@ -32,19 +32,9 @@ public:
   {
     for (uint32_t i = Begin(jointId); i < End(jointId); ++i)
       f(m_points[i]);
-
-    auto const & it = m_dynamicJoints.find(jointId);
-    if (it != m_dynamicJoints.end())
-    {
-      Joint const & joint = it->second;
-      for (size_t i = 0; i < joint.GetSize(); ++i)
-        f(joint.GetEntry(i));
-    }
   }
 
   void Build(RoadIndex const & roadIndex, uint32_t numJoints);
-  Joint::Id InsertJoint(RoadPoint const & rp);
-  void AppendToJoint(Joint::Id jointId, RoadPoint const & rp);
 
 private:
   // Begin index for jointId entries.
@@ -64,6 +54,5 @@ private:
 
   vector<uint32_t> m_offsets;
   vector<RoadPoint> m_points;
-  unordered_map<Joint::Id, Joint> m_dynamicJoints;
 };
 }  // namespace routing
diff --git a/routing/routing.pro b/routing/routing.pro
index 36e75a7aa0..2aee2c37de 100644
--- a/routing/routing.pro
+++ b/routing/routing.pro
@@ -110,6 +110,7 @@ HEADERS += \
     routing_serialization.hpp \
     routing_session.hpp \
     routing_settings.hpp \
+    segment.hpp \
     single_mwm_router.hpp \
     speed_camera.hpp \
     turn_candidate.hpp \
diff --git a/routing/routing_tests/applying_traffic_test.cpp b/routing/routing_tests/applying_traffic_test.cpp
index f9e2bebbda..be63f039b5 100644
--- a/routing/routing_tests/applying_traffic_test.cpp
+++ b/routing/routing_tests/applying_traffic_test.cpp
@@ -44,9 +44,14 @@ using namespace traffic;
 //      F0      F1          F8
 //    ↗          ↖         |
 // 0 *              *--F7--->*
+//                  ^
+//                  F9
+//                  |
+//-1                *
 //   0       1      2       3
 //                Start
-// Note. This graph contains of 9 one segment directed features.
+//
+// Note. This graph consists of 10 one segment directed features.
 unique_ptr<IndexGraph> BuildXXGraph(shared_ptr<EdgeEstimator> estimator)
 {
   unique_ptr<TestGeometryLoader> loader = make_unique<TestGeometryLoader>();
@@ -68,10 +73,12 @@ unique_ptr<IndexGraph> BuildXXGraph(shared_ptr<EdgeEstimator> estimator)
                   RoadGeometry::Points({{2.0, 0.0}, {3.0, 0.0}}));
   loader->AddRoad(8 /* featureId */, true /* oneWay */, 1.0 /* speed */,
                   RoadGeometry::Points({{3.0, 0.0}, {3.0, 1.0}}));
+  loader->AddRoad(9 /* featureId */, true /* oneWay */, 1.0 /* speed */,
+                  RoadGeometry::Points({{2.0, -1.0}, {2.0, 0.0}}));
 
   vector<Joint> const joints = {
       MakeJoint({{0 /* feature id */, 0 /* point id */}}), /* joint at point (0, 0) */
-      MakeJoint({{1, 0}, {7, 0}}),                         /* joint at point (2, 0) */
+      MakeJoint({{1, 0}, {7, 0}, {9, 1}}),                 /* joint at point (2, 0) */
       MakeJoint({{0, 1}, {1, 1}, {2, 0}, {3, 0}}),         /* joint at point (1, 1) */
       MakeJoint({{2, 1}}),                                 /* joint at point (0, 2) */
       MakeJoint({{3, 1}, {4, 1}, {5, 0}, {6, 0}}),         /* joint at point (2, 2) */
@@ -127,8 +134,10 @@ UNIT_CLASS_TEST(ApplyingTrafficTest, XXGraph_EmptyTrafficColoring)
   SetEstimator({} /* coloring */);
 
   unique_ptr<IndexGraph> graph = BuildXXGraph(GetEstimator());
-  IndexGraphStarter starter(*graph, RoadPoint(1, 0) /* start */, RoadPoint(6, 1) /* finish */);
-  vector<m2::PointD> const expectedGeom = {{2 /* x */, 0 /* y */}, {1, 1}, {2, 2}, {3, 3}};
+  IndexGraphStarter::FakeVertex const start(9, 0, m2::PointD(2.0, -1.0));
+  IndexGraphStarter::FakeVertex const finish(6, 0, m2::PointD(3.0, 3.0));
+  IndexGraphStarter starter(*graph, start, finish);
+  vector<m2::PointD> const expectedGeom = {{2 /* x */, -1 /* y */}, {2, 0}, {1, 1}, {2, 2}, {3, 3}};
   TestRouteGeometry(starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom);
 }
 
@@ -141,8 +150,10 @@ UNIT_CLASS_TEST(ApplyingTrafficTest, XXGraph_G0onF3)
   SetEstimator(move(coloring));
 
   unique_ptr<IndexGraph> graph = BuildXXGraph(GetEstimator());
-  IndexGraphStarter starter(*graph, RoadPoint(1, 0) /* start */, RoadPoint(6, 1) /* finish */);
-  vector<m2::PointD> const expectedGeom = {{2 /* x */, 0 /* y */}, {3, 0}, {3, 1}, {2, 2}, {3, 3}};
+  IndexGraphStarter::FakeVertex const start(9, 0, m2::PointD(2.0, -1.0));
+  IndexGraphStarter::FakeVertex const finish(6, 0, m2::PointD(3.0, 3.0));
+  IndexGraphStarter starter(*graph, start, finish);
+  vector<m2::PointD> const expectedGeom = {{2 /* x */, -1 /* y */}, {2, 0}, {3, 0}, {3, 1}, {2, 2}, {3, 3}};
   EstimatorGuard guard(MwmSet::MwmId(), *GetEstimator());
   TestRouteGeometry(starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom);
 }
@@ -156,8 +167,10 @@ UNIT_CLASS_TEST(ApplyingTrafficTest, XXGraph_TempBlockonF3)
   SetEstimator(move(coloring));
 
   unique_ptr<IndexGraph> graph = BuildXXGraph(GetEstimator());
-  IndexGraphStarter starter(*graph, RoadPoint(1, 0) /* start */, RoadPoint(6, 1) /* finish */);
-  vector<m2::PointD> const expectedGeom = {{2 /* x */, 0 /* y */}, {3, 0}, {3, 1}, {2, 2}, {3, 3}};
+  IndexGraphStarter::FakeVertex const start(9, 0, m2::PointD(2.0, -1.0));
+  IndexGraphStarter::FakeVertex const finish(6, 0, m2::PointD(3.0, 3.0));
+  IndexGraphStarter starter(*graph, start, finish);
+  vector<m2::PointD> const expectedGeom = {{2 /* x */, -1 /* y */}, {2, 0}, {3, 0}, {3, 1}, {2, 2}, {3, 3}};
   EstimatorGuard guard(MwmSet::MwmId(), *GetEstimator());
   TestRouteGeometry(starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom);
 }
@@ -171,8 +184,10 @@ UNIT_CLASS_TEST(ApplyingTrafficTest, XXGraph_G0onF3ReverseDir)
   SetEstimator(move(coloring));
 
   unique_ptr<IndexGraph> graph = BuildXXGraph(GetEstimator());
-  IndexGraphStarter starter(*graph, RoadPoint(1, 0) /* start */, RoadPoint(6, 1) /* finish */);
-  vector<m2::PointD> const expectedGeom = {{2 /* x */, 0 /* y */}, {1, 1}, {2, 2}, {3, 3}};
+  IndexGraphStarter::FakeVertex const start(9, 0, m2::PointD(2.0, -1.0));
+  IndexGraphStarter::FakeVertex const finish(6, 0, m2::PointD(3.0, 3.0));
+  IndexGraphStarter starter(*graph, start, finish);
+  vector<m2::PointD> const expectedGeom = {{2 /* x */, -1 /* y */}, {2, 0}, {1, 1}, {2, 2}, {3, 3}};
   EstimatorGuard guard(MwmSet::MwmId(), *GetEstimator());
   TestRouteGeometry(starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom);
 }
@@ -192,8 +207,10 @@ UNIT_CLASS_TEST(ApplyingTrafficTest, XXGraph_G0onF3andF6andG4onF8andF4)
   SetEstimator(move(coloring));
 
   unique_ptr<IndexGraph> graph = BuildXXGraph(GetEstimator());
-  IndexGraphStarter starter(*graph, RoadPoint(1, 0) /* start */, RoadPoint(6, 1) /* finish */);
-  vector<m2::PointD> const expectedGeom = {{2 /* x */, 0 /* y */}, {3, 0}, {3, 1}, {2, 2}, {3, 3}};
+  IndexGraphStarter::FakeVertex const start(9, 0, m2::PointD(2.0, -1.0));
+  IndexGraphStarter::FakeVertex const finish(6, 0, m2::PointD(3.0, 3.0));
+  IndexGraphStarter starter(*graph, start, finish);
+  vector<m2::PointD> const expectedGeom = {{2 /* x */, -1 /* y */}, {2, 0}, {3, 0}, {3, 1}, {2, 2}, {3, 3}};
   EstimatorGuard guard(MwmSet::MwmId(), *GetEstimator());
   TestRouteGeometry(starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom);
 }
@@ -204,8 +221,10 @@ UNIT_CLASS_TEST(ApplyingTrafficTest, XXGraph_ChangingTraffic)
   // No trafic at all.
   SetEstimator({} /* coloring */);
   unique_ptr<IndexGraph> graph = BuildXXGraph(GetEstimator());
-  IndexGraphStarter starter(*graph, RoadPoint(1, 0) /* start */, RoadPoint(6, 1) /* finish */);
-  vector<m2::PointD> const noTrafficGeom = {{2 /* x */, 0 /* y */}, {1, 1}, {2, 2}, {3, 3}};
+  IndexGraphStarter::FakeVertex const start(9, 0, m2::PointD(2.0, -1.0));
+  IndexGraphStarter::FakeVertex const finish(6, 0, m2::PointD(3.0, 3.0));
+  IndexGraphStarter starter(*graph, start, finish);
+  vector<m2::PointD> const noTrafficGeom = {{2 /* x */, -1 /* y */}, {2, 0}, {1, 1}, {2, 2}, {3, 3}};
   {
     EstimatorGuard guard(MwmSet::MwmId(), *GetEstimator());
     TestRouteGeometry(starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, noTrafficGeom);
@@ -218,7 +237,7 @@ UNIT_CLASS_TEST(ApplyingTrafficTest, XXGraph_ChangingTraffic)
   UpdateTrafficInfo(move(coloringHeavyF3));
   {
     EstimatorGuard guard(MwmSet::MwmId(), *GetEstimator());
-    vector<m2::PointD> const heavyF3Geom = {{2 /* x */, 0 /* y */}, {3, 0}, {3, 1}, {2, 2}, {3, 3}};
+    vector<m2::PointD> const heavyF3Geom = {{2 /* x */, -1 /* y */}, {2, 0}, {3, 0}, {3, 1}, {2, 2}, {3, 3}};
     TestRouteGeometry(starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, heavyF3Geom);
   }
 
diff --git a/routing/routing_tests/index_graph_test.cpp b/routing/routing_tests/index_graph_test.cpp
index 617884ff75..218145da34 100644
--- a/routing/routing_tests/index_graph_test.cpp
+++ b/routing/routing_tests/index_graph_test.cpp
@@ -27,48 +27,60 @@ namespace
 using namespace routing;
 using namespace routing_test;
 
-void TestRoute(IndexGraph & graph, RoadPoint const & start, RoadPoint const & finish,
-               size_t expectedLength, vector<RoadPoint> const * expectedRoute = nullptr)
+void TestRoute(IndexGraph & graph, IndexGraphStarter::FakeVertex const & start,
+               IndexGraphStarter::FakeVertex const & finish, size_t expectedLength,
+               vector<Segment> const * expectedRoute = nullptr)
 {
-  LOG(LINFO, ("Test route", start.GetFeatureId(), ",", start.GetPointId(), "=>",
-              finish.GetFeatureId(), ",", finish.GetPointId()));
+  LOG(LINFO, ("Test route", start.GetFeatureId(), ",", start.GetSegmentIdx(), "=>",
+              finish.GetFeatureId(), ",", finish.GetSegmentIdx()));
 
   IndexGraphStarter starter(graph, start, finish);
-  vector<RoadPoint> roadPoints;
-  auto const resultCode = CalculateRoute(starter, roadPoints);
+  vector<Segment> route;
+  auto const resultCode = CalculateRoute(starter, route);
   TEST_EQUAL(resultCode, AStarAlgorithm<IndexGraphStarter>::Result::OK, ());
 
-  TEST_EQUAL(roadPoints.size(), expectedLength, ());
+  TEST_GREATER(route.size(), 2, ());
+  // Erase fake points.
+  route.erase(route.begin());
+  route.pop_back();
+
+  TEST_EQUAL(route.size(), expectedLength, ("route =", route));
 
   if (expectedRoute)
-    TEST_EQUAL(roadPoints, *expectedRoute, ());
+    TEST_EQUAL(route, *expectedRoute, ());
 }
 
-void TestEdges(IndexGraph & graph, Joint::Id jointId, vector<Joint::Id> const & expectedTargets,
-               bool forward)
+void TestEdges(IndexGraph & graph, Segment const & segment, vector<Segment> const & expectedTargets,
+               bool isOutgoing)
 {
-  vector<JointEdge> edges;
-  graph.GetEdgeList(jointId, forward, edges);
+  ASSERT(segment.IsForward() || !graph.GetGeometry().GetRoad(segment.GetFeatureId()).IsOneWay(),
+         ());
+
+  vector<SegmentEdge> edges;
+  graph.GetEdgeList(segment, isOutgoing, edges);
 
-  vector<Joint::Id> targets;
-  for (JointEdge const & edge : edges)
+  vector<Segment> targets;
+  for (SegmentEdge const & edge : edges)
     targets.push_back(edge.GetTarget());
 
   sort(targets.begin(), targets.end());
 
-  TEST_EQUAL(targets, expectedTargets, ());
+  vector<Segment> sortedExpectedTargets(expectedTargets);
+  sort(sortedExpectedTargets.begin(), sortedExpectedTargets.end());
+
+  TEST_EQUAL(targets, sortedExpectedTargets, ());
 }
 
-void TestOutgoingEdges(IndexGraph & graph, Joint::Id jointId,
-                       vector<Joint::Id> const & expectedTargets)
+void TestOutgoingEdges(IndexGraph & graph, Segment const & segment,
+                       vector<Segment> const & expectedTargets)
 {
-  TestEdges(graph, jointId, expectedTargets, true);
+  TestEdges(graph, segment, expectedTargets, true /* isOutgoing */);
 }
 
-void TestIngoingEdges(IndexGraph & graph, Joint::Id jointId,
-                      vector<Joint::Id> const & expectedTargets)
+void TestIngoingEdges(IndexGraph & graph, Segment const & segment,
+                      vector<Segment> const & expectedTargets)
 {
-  TestEdges(graph, jointId, expectedTargets, false);
+  TestEdges(graph, segment, expectedTargets, false /* isOutgoing */);
 }
 
 uint32_t AbsDelta(uint32_t v0, uint32_t v1) { return v0 > v1 ? v0 - v1 : v1 - v0; }
@@ -117,19 +129,21 @@ UNIT_TEST(EdgesTest)
   joints.emplace_back(MakeJoint({{2, 1}, {4, 2}}));  // J5
   graph.Import(joints);
 
-  TestOutgoingEdges(graph, 0, {1, 2});
-  TestOutgoingEdges(graph, 1, {0, 5});
-  TestOutgoingEdges(graph, 2, {3});
-  TestOutgoingEdges(graph, 3, {1, 2});
-  TestOutgoingEdges(graph, 4, {0, 5});
-  TestOutgoingEdges(graph, 5, {4});
-
-  TestIngoingEdges(graph, 0, {1, 4});
-  TestIngoingEdges(graph, 1, {0, 3});
-  TestIngoingEdges(graph, 2, {0, 3});
-  TestIngoingEdges(graph, 3, {2});
-  TestIngoingEdges(graph, 4, {5});
-  TestIngoingEdges(graph, 5, {1, 4});
+  TestOutgoingEdges(graph, {0, 0, true}, {{0, 0, false}, {0, 1, true}, {3, 1, true}});
+  TestIngoingEdges(graph, {0, 0, true}, {{0, 0, false}});
+  TestOutgoingEdges(graph, {0, 0, false}, {{0, 0, true}});
+  TestIngoingEdges(graph, {0, 0, false}, {{0, 0, true}, {0, 1, false}, {3, 0, true}});
+
+  TestOutgoingEdges(graph, {0, 2, true}, {{0, 2, false}, {0, 3, true}, {4, 1, true}});
+  TestIngoingEdges(graph, {0, 2, true}, {{0, 2, false}, {0, 1, true}});
+  TestOutgoingEdges(graph, {0, 2, false}, {{0, 2, true}, {0, 1, false}});
+  TestIngoingEdges(graph, {0, 2, false}, {{0, 2, true}, {0, 3, false}, {4, 0, true}});
+
+  TestOutgoingEdges(graph, {3, 0, true}, {{3, 1, true}, {0, 0, false}, {0, 1, true}});
+  TestIngoingEdges(graph, {3, 0, true}, {{2, 0, false}});
+
+  TestOutgoingEdges(graph, {4, 1, true}, {{2, 0, false}});
+  TestIngoingEdges(graph, {4, 1, true}, {{4, 0, true}, {0, 2, true}, {0, 3, false}});
 }
 
 //  Roads     R1:
@@ -148,33 +162,41 @@ UNIT_TEST(FindPathCross)
       RoadGeometry::Points({{-2.0, 0.0}, {-1.0, 0.0}, {0.0, 0.0}, {1.0, 0.0}, {2.0, 0.0}}));
   loader->AddRoad(
       1 /* featureId */, false, 1.0 /* speed */,
-      RoadGeometry::Points({{0.0, -2.0}, {-1.0, 0.0}, {0.0, 0.0}, {0.0, 1.0}, {0.0, 2.0}}));
+      RoadGeometry::Points({{0.0, -2.0}, {0.0, -1.0}, {0.0, 0.0}, {0.0, 1.0}, {0.0, 2.0}}));
 
   traffic::TrafficCache const trafficCache;
   IndexGraph graph(move(loader), CreateEstimator(trafficCache));
 
   graph.Import({MakeJoint({{0, 2}, {1, 2}})});
 
-  vector<RoadPoint> points;
-  for (uint32_t i = 0; i < 5; ++i)
+  vector<IndexGraphStarter::FakeVertex> endPoints;
+  for (uint32_t i = 0; i < 4; ++i)
   {
-    points.emplace_back(0, i);
-    points.emplace_back(1, i);
+    endPoints.emplace_back(0, i, m2::PointD(-1.5 + i, 0.0));
+    endPoints.emplace_back(1, i, m2::PointD(0.0, -1.5 + i));
   }
 
-  for (auto const & start : points)
+  for (auto const & start : endPoints)
   {
-    for (auto const & finish : points)
+    for (auto const & finish : endPoints)
     {
-      uint32_t expectedLength;
-      // Length of the route is the number of route points.
-      // Example: p0 --- p1 --- p2
-      // 2 segments, 3 points,
-      // Therefore route length = geometrical length + 1
+      uint32_t expectedLength = 0;
       if (start.GetFeatureId() == finish.GetFeatureId())
-        expectedLength = AbsDelta(start.GetPointId(), finish.GetPointId()) + 1;
+      {
+        expectedLength = AbsDelta(start.GetSegmentIdx(), finish.GetSegmentIdx()) + 1;
+      }
       else
-        expectedLength = AbsDelta(start.GetPointId(), 2) + AbsDelta(finish.GetPointId(), 2) + 1;
+      {
+        if (start.GetSegmentIdx() < 2)
+          expectedLength += 2 - start.GetSegmentIdx();
+        else
+          expectedLength += start.GetSegmentIdx() - 1;
+
+        if (finish.GetSegmentIdx() < 2)
+          expectedLength += 2 - finish.GetSegmentIdx();
+        else
+          expectedLength += finish.GetSegmentIdx() - 1;
+      }
       TestRoute(graph, start, finish, expectedLength);
     }
   }
@@ -200,8 +222,8 @@ UNIT_TEST(FindPathManhattan)
     RoadGeometry::Points avenue;
     for (uint32_t j = 0; j < kCitySize; ++j)
     {
-      street.emplace_back(static_cast<double>(i), static_cast<double>(j));
-      avenue.emplace_back(static_cast<double>(j), static_cast<double>(i));
+      street.emplace_back(static_cast<double>(j), static_cast<double>(i));
+      avenue.emplace_back(static_cast<double>(i), static_cast<double>(j));
     }
     loader->AddRoad(i, false, 1.0 /* speed */, street);
     loader->AddRoad(i + kCitySize, false, 1.0 /* speed */, avenue);
@@ -218,65 +240,64 @@ UNIT_TEST(FindPathManhattan)
   }
   graph.Import(joints);
 
-  for (uint32_t startY = 0; startY < kCitySize; ++startY)
+  vector<IndexGraphStarter::FakeVertex> endPoints;
+  for (uint32_t featureId = 0; featureId < kCitySize; ++featureId)
   {
-    for (uint32_t startX = 0; startX < kCitySize; ++startX)
+    for (uint32_t segmentId = 0; segmentId < kCitySize - 1; ++segmentId)
     {
-      for (uint32_t finishY = 0; finishY < kCitySize; ++finishY)
-      {
-        for (uint32_t finishX = 0; finishX < kCitySize; ++finishX)
-          TestRoute(graph, {startX, startY}, {finishX, finishY},
-                    AbsDelta(startX, finishX) + AbsDelta(startY, finishY) + 1);
-      }
+      endPoints.emplace_back(featureId, segmentId, m2::PointD(0.5 + segmentId, featureId));
+      endPoints.emplace_back(featureId + kCitySize, segmentId,
+                             m2::PointD(featureId, 0.5 + segmentId));
     }
   }
-}
 
-// Roads                          y:
-//
-//  R0:         * - * - *         -1
-//            /           \
-//  R1:   J0 * -* - * - *- * J1    0
-//            \           /
-//  R2:         * - * - *          1
-//
-//     x:    0  1   2   3  4
-//
-UNIT_TEST(RedressRace)
-{
-  unique_ptr<TestGeometryLoader> loader = make_unique<TestGeometryLoader>();
-
-  loader->AddRoad(
-      0 /* featureId */, false, 1.0 /* speed */,
-      RoadGeometry::Points({{0.0, 0.0}, {1.0, -1.0}, {2.0, -1.0}, {3.0, -1.0}, {4.0, 0.0}}));
-
-  loader->AddRoad(
-      1 /* featureId */, false, 1.0 /* speed */,
-      RoadGeometry::Points({{0.0, 0.0}, {1.0, 0.0}, {2.0, 0.0}, {3.0, 0.0}, {4.0, 0.0}}));
+  for (auto const & start : endPoints)
+  {
+    for (auto const & finish : endPoints)
+    {
+      uint32_t expectedLength = 0;
 
-  loader->AddRoad(
-      2 /* featureId */, false, 1.0 /* speed */,
-      RoadGeometry::Points({{0.0, 0.0}, {1.0, 1.0}, {2.0, 1.0}, {3.0, 1.0}, {4.0, 0.0}}));
+      auto const startFeatureOffset = start.GetFeatureId() < kCitySize
+                                          ? start.GetFeatureId()
+                                          : start.GetFeatureId() - kCitySize;
+      auto const finishFeatureOffset = finish.GetFeatureId() < kCitySize
+                                           ? finish.GetFeatureId()
+                                           : finish.GetFeatureId() - kCitySize;
 
-  traffic::TrafficCache const trafficCache;
-  IndexGraph graph(move(loader), CreateEstimator(trafficCache));
-
-  vector<Joint> joints;
-  joints.emplace_back(MakeJoint({{0, 0}, {1, 0}, {2, 0}}));  // J0
-  joints.emplace_back(MakeJoint({{0, 4}, {1, 4}, {2, 4}}));  // J1
-  graph.Import(joints);
+      if (start.GetFeatureId() < kCitySize == finish.GetFeatureId() < kCitySize)
+      {
+        uint32_t segDelta = AbsDelta(start.GetSegmentIdx(), finish.GetSegmentIdx());
+        if (segDelta == 0 && start.GetFeatureId() != finish.GetFeatureId())
+          segDelta = 1;
+        expectedLength += segDelta;
+        expectedLength += AbsDelta(startFeatureOffset, finishFeatureOffset) + 1;
+      }
+      else
+      {
+        if (start.GetSegmentIdx() < finishFeatureOffset)
+          expectedLength += finishFeatureOffset - start.GetSegmentIdx();
+        else
+          expectedLength += start.GetSegmentIdx() - finishFeatureOffset + 1;
+
+        if (finish.GetSegmentIdx() < startFeatureOffset)
+          expectedLength += startFeatureOffset - finish.GetSegmentIdx();
+        else
+          expectedLength += finish.GetSegmentIdx() - startFeatureOffset + 1;
+      }
 
-  vector<RoadPoint> const expectedRoute({{1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}});
-  TestRoute(graph, {0, 0}, {0, 4}, 5, &expectedRoute);
+      TestRoute(graph, start, finish, expectedLength);
+    }
+  }
 }
 
-// Roads                                       y:
+// Roads                                          y:
 //
-//  fast road R0            * - * - *         -1
-//                        /           \
-//  slow road R1      J0 *  - - * - -  * J1    0
+//  fast road R0              * - * - *           -1
+//                          /           \
+//  slow road R1    * - -  *  - - * - -  * - - *   0
+//                        J0            J1
 //
-//                 x:    0  1   2   3  4
+//            x:    0      1  2   3   4  5     6
 //
 UNIT_TEST(RoadSpeed)
 {
@@ -284,21 +305,26 @@ UNIT_TEST(RoadSpeed)
 
   loader->AddRoad(
       0 /* featureId */, false, 10.0 /* speed */,
-      RoadGeometry::Points({{0.0, 0.0}, {1.0, -1.0}, {2.0, -1.0}, {3.0, -1.0}, {4.0, 0.0}}));
+      RoadGeometry::Points({{1.0, 0.0}, {2.0, -1.0}, {3.0, -1.0}, {4.0, -1.0}, {5.0, 0.0}}));
 
-  loader->AddRoad(1 /* featureId */, false, 1.0 /* speed */,
-                  RoadGeometry::Points({{0.0, 0.0}, {2.0, 0.0}, {4.0, 0.0}}));
+  loader->AddRoad(
+      1 /* featureId */, false, 1.0 /* speed */,
+      RoadGeometry::Points({{0.0, 0.0}, {1.0, 0.0}, {3.0, 0.0}, {5.0, 0.0}, {6.0, 0.0}}));
 
   traffic::TrafficCache const trafficCache;
   IndexGraph graph(move(loader), CreateEstimator(trafficCache));
 
   vector<Joint> joints;
-  joints.emplace_back(MakeJoint({{0, 0}, {1, 0}}));  // J0
-  joints.emplace_back(MakeJoint({{0, 4}, {1, 2}}));  // J1
+  joints.emplace_back(MakeJoint({{0, 0}, {1, 1}}));  // J0
+  joints.emplace_back(MakeJoint({{0, 4}, {1, 3}}));  // J1
   graph.Import(joints);
 
-  vector<RoadPoint> const expectedRoute({{0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}});
-  TestRoute(graph, {0, 0}, {0, 4}, 5, &expectedRoute);
+  IndexGraphStarter::FakeVertex const start(1, 0, m2::PointD(0.5, 0));
+  IndexGraphStarter::FakeVertex const finish(1, 3, m2::PointD(5.5, 0));
+
+  vector<Segment> const expectedRoute(
+      {{1, 0, true}, {0, 0, true}, {0, 1, true}, {0, 2, true}, {0, 3, true}, {1, 3, true}});
+  TestRoute(graph, start, finish, 6, &expectedRoute);
 }
 
 //
diff --git a/routing/routing_tests/index_graph_tools.cpp b/routing/routing_tests/index_graph_tools.cpp
index 261a6c53ff..3859f2c417 100644
--- a/routing/routing_tests/index_graph_tools.cpp
+++ b/routing/routing_tests/index_graph_tools.cpp
@@ -36,25 +36,19 @@ Joint MakeJoint(vector<RoadPoint> const & points)
 
 shared_ptr<EdgeEstimator> CreateEstimator(traffic::TrafficCache const & trafficCache)
 {
-  return EdgeEstimator::CreateForCar(*make_shared<CarModelFactory>()->GetVehicleModel(), trafficCache);
+  return EdgeEstimator::CreateForCar(*make_shared<CarModelFactory>()->GetVehicleModel(),
+                                     trafficCache);
 }
 
 AStarAlgorithm<IndexGraphStarter>::Result CalculateRoute(IndexGraphStarter & starter,
-                                                         vector<RoadPoint> & roadPoints)
+                                                          vector<Segment> & roadPoints)
 {
   AStarAlgorithm<IndexGraphStarter> algorithm;
-  RoutingResult<Joint::Id> routingResult;
-  auto const resultCode = algorithm.FindPath(
-      starter, starter.GetStartJoint(), starter.GetFinishJoint(), routingResult, {}, {});
-
-  vector<RoutePoint> routePoints;
-  starter.RedressRoute(routingResult.path, routePoints);
-
-  roadPoints.clear();
-  roadPoints.reserve(routePoints.size());
-  for (auto const & point : routePoints)
-    roadPoints.push_back(point.GetRoadPoint());
+  RoutingResult<Segment> routingResult;
+  auto const resultCode = algorithm.FindPathBidirectional(
+      starter, starter.GetStart(), starter.GetFinish(), routingResult, {}, {});
 
+  roadPoints = routingResult.path;
   return resultCode;
 }
 
@@ -62,16 +56,12 @@ void TestRouteGeometry(IndexGraphStarter & starter,
                        AStarAlgorithm<IndexGraphStarter>::Result expectedRouteResult,
                        vector<m2::PointD> const & expectedRouteGeom)
 {
-  vector<RoadPoint> route;
+  vector<Segment> route;
   auto const resultCode = CalculateRoute(starter, route);
   TEST_EQUAL(resultCode, expectedRouteResult, ());
-  TEST_EQUAL(route.size(), expectedRouteGeom.size(), ());
-  for (size_t i = 0; i < route.size(); ++i)
-  {
-    // When PR with applying restricions is merged IndexGraph::GetRoad() should be used here instead.
-    RoadGeometry roadGeom = starter.GetGraph().GetGeometry().GetRoad(route[i].GetFeatureId());
-    CHECK_LESS(route[i].GetPointId(), roadGeom.GetPointsCount(), ());
-    TEST_EQUAL(expectedRouteGeom[i], roadGeom.GetPoint(route[i].GetPointId()), ());
-  }
+  TEST_EQUAL(IndexGraphStarter::GetRouteNumPoints(route), expectedRouteGeom.size(), ());
+
+  for (size_t i = 0; i < IndexGraphStarter::GetRouteNumPoints(route); ++i)
+    TEST_EQUAL(expectedRouteGeom[i], starter.GetRoutePoint(route, i), ());
 }
 }  // namespace routing_test
diff --git a/routing/routing_tests/index_graph_tools.hpp b/routing/routing_tests/index_graph_tools.hpp
index 8cc0f0b94d..4c5494b1b3 100644
--- a/routing/routing_tests/index_graph_tools.hpp
+++ b/routing/routing_tests/index_graph_tools.hpp
@@ -4,6 +4,7 @@
 #include "routing/index_graph.hpp"
 #include "routing/index_graph_starter.hpp"
 #include "routing/road_point.hpp"
+#include "routing/segment.hpp"
 
 #include "routing/base/astar_algorithm.hpp"
 
@@ -37,7 +38,7 @@ 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 & starter, vector<routing::Segment> & roadPoints);
 
 void TestRouteSegments(
     routing::IndexGraphStarter & starter,
diff --git a/routing/segment.hpp b/routing/segment.hpp
new file mode 100644
index 0000000000..67c6c05a88
--- /dev/null
+++ b/routing/segment.hpp
@@ -0,0 +1,85 @@
+#pragma once
+
+#include "routing/road_point.hpp"
+
+#include "std/cstdint.hpp"
+#include "std/sstream.hpp"
+#include "std/string.hpp"
+
+namespace routing
+{
+// This is directed road segment used as vertex in index graph.
+//
+// You can imagine the segment as a material arrow.
+// Head of each arrow is connected to fletchings of next arrows with invisible links:
+// these are the edges of the graph.
+//
+// Position of the segment is a position of the arrowhead: GetPointId(true).
+// This position is used in heuristic and edges weight calculations.
+class Segment final
+{
+public:
+  Segment() = default;
+
+  constexpr Segment(uint32_t featureId, uint32_t segmentIdx, bool forward)
+    : m_featureId(featureId), m_segmentIdx(segmentIdx), m_forward(forward)
+  {
+  }
+
+  uint32_t GetFeatureId() const { return m_featureId; }
+  uint32_t GetSegmentIdx() const { return m_segmentIdx; }
+  bool IsForward() const { return m_forward; }
+
+  uint32_t GetPointId(bool front) const
+  {
+    return m_forward == front ? m_segmentIdx + 1 : m_segmentIdx;
+  }
+
+  RoadPoint GetRoadPoint(bool front) const { return RoadPoint(m_featureId, GetPointId(front)); }
+
+  bool operator<(Segment const & seg) const
+  {
+    if (m_featureId != seg.m_featureId)
+      return m_featureId < seg.m_featureId;
+
+    if (m_segmentIdx != seg.m_segmentIdx)
+      return m_segmentIdx < seg.m_segmentIdx;
+
+    return m_forward < seg.m_forward;
+  }
+
+  bool operator==(Segment const & seg) const
+  {
+    return m_featureId == seg.m_featureId && m_segmentIdx == seg.m_segmentIdx &&
+           m_forward == seg.m_forward;
+  }
+
+  bool operator!=(Segment const & seg) const { return !(*this == seg); }
+
+private:
+  uint32_t m_featureId = 0;
+  uint32_t m_segmentIdx = 0;
+  bool m_forward = true;
+};
+
+class SegmentEdge final
+{
+public:
+  SegmentEdge(Segment const & target, double weight) : m_target(target), m_weight(weight) {}
+  Segment const & GetTarget() const { return m_target; }
+  double GetWeight() const { return m_weight; }
+
+private:
+  // Target is vertex going to for outgoing edges, vertex going from for ingoing edges.
+  Segment const m_target;
+  double const m_weight;
+};
+
+inline string DebugPrint(Segment const & segment)
+{
+  ostringstream out;
+  out << "Segment(" << segment.GetFeatureId() << ", " << segment.GetSegmentIdx() << ", "
+      << segment.IsForward() << ")";
+  return out.str();
+}
+}  // namespace routing
diff --git a/routing/single_mwm_router.cpp b/routing/single_mwm_router.cpp
index 1c8e9c0a88..79ee46d313 100644
--- a/routing/single_mwm_router.cpp
+++ b/routing/single_mwm_router.cpp
@@ -92,8 +92,10 @@ IRouter::ResultCode SingleMwmRouter::DoCalculateRoute(MwmSet::MwmId const & mwmI
   if (!FindClosestEdge(mwmId, finalPoint, finishEdge))
     return IRouter::EndPointNotFound;
 
-  RoadPoint const start(startEdge.GetFeatureId().m_index, startEdge.GetSegId());
-  RoadPoint const finish(finishEdge.GetFeatureId().m_index, finishEdge.GetSegId());
+  IndexGraphStarter::FakeVertex const start(startEdge.GetFeatureId().m_index, startEdge.GetSegId(),
+                                            startPoint);
+  IndexGraphStarter::FakeVertex const finish(finishEdge.GetFeatureId().m_index,
+                                             finishEdge.GetSegId(), finalPoint);
 
   EstimatorGuard guard(mwmId, *m_estimator);
 
@@ -107,12 +109,12 @@ IRouter::ResultCode SingleMwmRouter::DoCalculateRoute(MwmSet::MwmId const & mwmI
   IndexGraphStarter starter(graph, start, finish);
 
   AStarProgress progress(0, 100);
-  progress.Initialize(graph.GetGeometry().GetPoint(start), graph.GetGeometry().GetPoint(finish));
+  progress.Initialize(startPoint, finalPoint);
 
   uint32_t drawPointsStep = 0;
-  auto onVisitJunction = [&](Joint::Id const & from, Joint::Id const & to) {
-    m2::PointD const & pointFrom = starter.GetPoint(from);
-    m2::PointD const & pointTo = starter.GetPoint(to);
+  auto onVisitJunction = [&](Segment const & from, Segment const & to) {
+    m2::PointD const & pointFrom = starter.GetPoint(from, true /* front */);
+    m2::PointD const & pointTo = starter.GetPoint(to, true /* front */);
     auto const lastValue = progress.GetLastValue();
     auto const newValue = progress.GetProgressForBidirectedAlgo(pointFrom, pointTo);
     if (newValue - lastValue > kProgressInterval)
@@ -124,10 +126,9 @@ IRouter::ResultCode SingleMwmRouter::DoCalculateRoute(MwmSet::MwmId const & mwmI
 
   AStarAlgorithm<IndexGraphStarter> algorithm;
 
-  RoutingResult<Joint::Id> routingResult;
-  auto const resultCode =
-      algorithm.FindPathBidirectional(starter, starter.GetStartJoint(), starter.GetFinishJoint(),
-                                      routingResult, delegate, onVisitJunction);
+  RoutingResult<Segment> routingResult;
+  auto const resultCode = algorithm.FindPathBidirectional(
+      starter, starter.GetStart(), starter.GetFinish(), routingResult, delegate, onVisitJunction);
 
   switch (resultCode)
   {
@@ -200,30 +201,18 @@ bool SingleMwmRouter::LoadIndex(MwmSet::MwmId const & mwmId, string const & coun
   }
 }
 
-bool SingleMwmRouter::BuildRoute(MwmSet::MwmId const & mwmId, vector<Joint::Id> const & joints,
+bool SingleMwmRouter::BuildRoute(MwmSet::MwmId const & mwmId, vector<Segment> const & segments,
                                  RouterDelegate const & delegate, IndexGraphStarter & starter,
                                  Route & route) const
 {
-  vector<RoutePoint> routePoints;
-  starter.RedressRoute(joints, routePoints);
-
-  // ReconstructRoute removes equal points: do it self to match time indexes.
-  // TODO: rework ReconstructRoute and remove all time indexes stuff.
-  routePoints.erase(unique(routePoints.begin(), routePoints.end(),
-                           [&](RoutePoint const & rp0, RoutePoint const & rp1) {
-                             return starter.GetPoint(rp0.GetRoadPoint()) ==
-                                    starter.GetPoint(rp1.GetRoadPoint());
-                           }),
-                    routePoints.end());
-
   vector<Junction> junctions;
-  junctions.reserve(routePoints.size());
+  size_t const numPoints = IndexGraphStarter::GetRouteNumPoints(segments);
+  junctions.reserve(numPoints);
 
-  // TODO: Use real altitudes for pedestrian and bicycle routing.
-  for (RoutePoint const & routePoint : routePoints)
+  for (size_t i = 0; i < numPoints; ++i)
   {
-    junctions.emplace_back(starter.GetPoint(routePoint.GetRoadPoint()),
-                           feature::kDefaultAltitudeMeters);
+    // TODO: Use real altitudes for pedestrian and bicycle routing.
+    junctions.emplace_back(starter.GetRoutePoint(segments, i), feature::kDefaultAltitudeMeters);
   }
 
   shared_ptr<traffic::TrafficInfo::Coloring> trafficColoring = m_trafficCache.GetTrafficInfo(mwmId);
@@ -231,8 +220,7 @@ bool SingleMwmRouter::BuildRoute(MwmSet::MwmId const & mwmId, vector<Joint::Id>
   vector<Junction> const oldJunctions(junctions);
 
   CHECK(m_directionsEngine, ());
-  ReconstructRoute(*m_directionsEngine, m_roadGraph, trafficColoring, delegate,
-                   junctions, route);
+  ReconstructRoute(*m_directionsEngine, m_roadGraph, trafficColoring, delegate, junctions, route);
 
   if (junctions != oldJunctions)
   {
@@ -241,27 +229,12 @@ bool SingleMwmRouter::BuildRoute(MwmSet::MwmId const & mwmId, vector<Joint::Id>
     return false;
   }
 
-  // ReconstructRoute duplicates all points except start and finish.
-  // Therefore one needs fix time indexes to fit reconstructed polyline.
-  if (routePoints.size() < 2 || route.GetPoly().GetSize() + 2 != routePoints.size() * 2)
+  if (!route.IsValid())
   {
-    LOG(LERROR, ("Can't fix route times: polyline size =", route.GetPoly().GetSize(),
-                 "route points size =", routePoints.size()));
+    LOG(LERROR, ("ReconstructRoute failed. Segments:", segments.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;
 }
 
@@ -273,7 +246,8 @@ unique_ptr<SingleMwmRouter> SingleMwmRouter::CreateCarRouter(
   // @TODO Bicycle turn generation engine is used now. It's ok for the time being.
   // But later a special car turn generation engine should be implemented.
   auto directionsEngine = make_unique<BicycleDirectionsEngine>(index);
-  auto estimator = EdgeEstimator::CreateForCar(*vehicleModelFactory->GetVehicleModel(), trafficCache);
+  auto estimator =
+      EdgeEstimator::CreateForCar(*vehicleModelFactory->GetVehicleModel(), trafficCache);
   auto router =
       make_unique<SingleMwmRouter>("astar-bidirectional-car", index, trafficCache,
                                    move(vehicleModelFactory), estimator, move(directionsEngine));
diff --git a/routing/single_mwm_router.hpp b/routing/single_mwm_router.hpp
index 321dcd1ad4..16615d4cd8 100644
--- a/routing/single_mwm_router.hpp
+++ b/routing/single_mwm_router.hpp
@@ -46,7 +46,7 @@ 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,
+  bool BuildRoute(MwmSet::MwmId const & mwmId, vector<Segment> const & segments,
                   RouterDelegate const & delegate, IndexGraphStarter & starter,
                   Route & route) const;
 
diff --git a/xcode/routing/routing.xcodeproj/project.pbxproj b/xcode/routing/routing.xcodeproj/project.pbxproj
index bf68fc18f5..08efd2cbef 100644
--- a/xcode/routing/routing.xcodeproj/project.pbxproj
+++ b/xcode/routing/routing.xcodeproj/project.pbxproj
@@ -16,6 +16,7 @@
 		0C0DF9251DE898CF0055A22F /* single_mwm_router.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0C0DF9231DE898CF0055A22F /* single_mwm_router.cpp */; };
 		0C0DF9261DE898CF0055A22F /* single_mwm_router.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 0C0DF9241DE898CF0055A22F /* single_mwm_router.hpp */; };
 		0C0DF92A1DE898FF0055A22F /* routing_helpers.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0C0DF9281DE898FF0055A22F /* routing_helpers.cpp */; };
+		0C470E701E0D4EB1005B824D /* segment.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 0C470E6F1E0D4EB1005B824D /* segment.hpp */; };
 		0C5FEC541DDE191E0017688C /* edge_estimator.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0C5FEC521DDE191E0017688C /* edge_estimator.cpp */; };
 		0C5FEC551DDE191E0017688C /* edge_estimator.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 0C5FEC531DDE191E0017688C /* edge_estimator.hpp */; };
 		0C5FEC5E1DDE192A0017688C /* geometry.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0C5FEC561DDE192A0017688C /* geometry.cpp */; };
@@ -252,6 +253,7 @@
 		0C0DF9231DE898CF0055A22F /* single_mwm_router.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = single_mwm_router.cpp; sourceTree = "<group>"; };
 		0C0DF9241DE898CF0055A22F /* single_mwm_router.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = single_mwm_router.hpp; sourceTree = "<group>"; };
 		0C0DF9281DE898FF0055A22F /* routing_helpers.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = routing_helpers.cpp; sourceTree = "<group>"; };
+		0C470E6F1E0D4EB1005B824D /* segment.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = segment.hpp; sourceTree = "<group>"; };
 		0C5FEC521DDE191E0017688C /* edge_estimator.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = edge_estimator.cpp; sourceTree = "<group>"; };
 		0C5FEC531DDE191E0017688C /* edge_estimator.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = edge_estimator.hpp; sourceTree = "<group>"; };
 		0C5FEC561DDE192A0017688C /* geometry.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = geometry.cpp; sourceTree = "<group>"; };
@@ -671,6 +673,7 @@
 		675343FA1A3F640D00A0A8C3 /* routing */ = {
 			isa = PBXGroup;
 			children = (
+				0C470E6F1E0D4EB1005B824D /* segment.hpp */,
 				0C5FEC521DDE191E0017688C /* edge_estimator.cpp */,
 				0C5FEC531DDE191E0017688C /* edge_estimator.hpp */,
 				56EA2FD41D8FD8590083F01A /* routing_helpers.hpp */,
@@ -801,6 +804,7 @@
 				674F9BCB1B0A580E00704FFA /* async_router.hpp in Headers */,
 				0C08AA391DF8329B004195DD /* routing_exceptions.hpp in Headers */,
 				674F9BD11B0A580E00704FFA /* online_cross_fetcher.hpp in Headers */,
+				0C470E701E0D4EB1005B824D /* segment.hpp in Headers */,
 				A120B3531B4A7C1C002F3808 /* astar_algorithm.hpp in Headers */,
 				0C5FEC5F1DDE192A0017688C /* geometry.hpp in Headers */,
 				674A28B21B1605D2001A525C /* osrm_engine.hpp in Headers */,