diff options
Diffstat (limited to 'routing/index_graph_starter.cpp')
| -rw-r--r-- | routing/index_graph_starter.cpp | 216 |
1 files changed, 112 insertions, 104 deletions
diff --git a/routing/index_graph_starter.cpp b/routing/index_graph_starter.cpp index 53f64a7b1b..e58e63eec8 100644 --- a/routing/index_graph_starter.cpp +++ b/routing/index_graph_starter.cpp @@ -1,90 +1,27 @@ #include "routing/index_graph_starter.hpp" +#include "routing/routing_exception.hpp" + namespace routing { IndexGraphStarter::IndexGraphStarter(IndexGraph const & graph, RoadPoint startPoint, RoadPoint finishPoint) : m_graph(graph) - , m_startPoint(startPoint) - , m_finishPoint(finishPoint) - , m_startImplant(graph.GetNumJoints()) - , m_finishImplant(graph.GetNumJoints() + 1) - , m_startJoint(CalcStartJoint()) - , m_finishJoint(CalcFinishJoint()) -{ -} - -Joint::Id IndexGraphStarter::CalcStartJoint() const + , m_start(graph, startPoint, graph.GetNumJoints(), graph.GetJointId(startPoint)) + , m_finish(graph, finishPoint, graph.GetNumJoints() + 1, + startPoint == finishPoint ? m_start.m_jointId : graph.GetJointId(finishPoint)) { - Joint::Id const jointId = m_graph.GetJointId(m_startPoint); - if (jointId == Joint::kInvalidId) - return m_startImplant; - - return jointId; } -Joint::Id IndexGraphStarter::CalcFinishJoint() const +m2::PointD const & IndexGraphStarter::GetPoint(Joint::Id jointId) const { - if (m_startPoint == m_finishPoint) - return CalcStartJoint(); + if (jointId == m_start.m_fakeId) + return m_graph.GetGeometry().GetPoint(m_start.m_point); - Joint::Id const jointId = m_graph.GetJointId(m_finishPoint); - if (jointId == Joint::kInvalidId) - return m_finishImplant; + if (jointId == m_finish.m_fakeId) + return m_graph.GetGeometry().GetPoint(m_finish.m_point); - return jointId; -} - -void IndexGraphStarter::GetEdgesList(Joint::Id jointId, bool isOutgoing, - vector<JointEdge> & edges) const -{ - edges.clear(); - - if (jointId == m_startImplant) - { - m_graph.AddNeighboringEdges(m_startPoint, isOutgoing, edges); - - if (FinishIsImplant() && m_startPoint.GetFeatureId() == m_finishPoint.GetFeatureId()) - m_graph.AddDirectEdge(m_startPoint.GetFeatureId(), m_startPoint.GetPointId(), - m_finishPoint.GetPointId(), m_finishJoint, isOutgoing, edges); - - return; - } - - if (jointId == m_finishImplant) - { - m_graph.AddNeighboringEdges(m_finishPoint, isOutgoing, edges); - - if (StartIsImplant() && m_startPoint.GetFeatureId() == m_finishPoint.GetFeatureId()) - m_graph.AddDirectEdge(m_finishPoint.GetFeatureId(), m_finishPoint.GetPointId(), - m_startPoint.GetPointId(), m_startJoint, isOutgoing, edges); - - return; - } - - m_graph.GetEdgesList(jointId, isOutgoing, edges); - - if (StartIsImplant() && m_graph.JointLaysOnRoad(jointId, m_startPoint.GetFeatureId())) - { - vector<JointEdge> startEdges; - m_graph.AddNeighboringEdges(m_startPoint, !isOutgoing, startEdges); - for (JointEdge const & edge : startEdges) - { - if (edge.GetTarget() == jointId) - edges.emplace_back(m_startJoint, edge.GetWeight()); - } - } - - if (FinishIsImplant() && m_graph.JointLaysOnRoad(jointId, m_finishPoint.GetFeatureId())) - { - vector<JointEdge> finishEdges; - m_graph.AddNeighboringEdges(m_finishPoint, !isOutgoing, finishEdges); - for (JointEdge const & edge : finishEdges) - { - if (edge.GetTarget() == jointId) - edges.emplace_back(m_finishJoint, edge.GetWeight()); - } - } + return m_graph.GetPoint(jointId); } void IndexGraphStarter::RedressRoute(vector<Joint::Id> const & route, @@ -93,7 +30,7 @@ void IndexGraphStarter::RedressRoute(vector<Joint::Id> const & route, if (route.size() < 2) { if (route.size() == 1) - roadPoints.emplace_back(m_startPoint); + roadPoints.emplace_back(m_start.m_point); return; } @@ -126,7 +63,7 @@ void IndexGraphStarter::RedressRoute(vector<Joint::Id> const & route, } else { - MYTHROW(RootException, + MYTHROW(RoutingException, ("Wrong equality pointFrom = pointTo =", pointFrom, ", featureId = ", featureId)); } @@ -134,6 +71,60 @@ void IndexGraphStarter::RedressRoute(vector<Joint::Id> const & route, } } +void IndexGraphStarter::GetEdgesList(Joint::Id jointId, bool isOutgoing, + vector<JointEdge> & edges) const +{ + edges.clear(); + + if (jointId == m_start.m_fakeId) + { + GetFakeEdges(m_start, m_finish, isOutgoing, edges); + return; + } + + if (jointId == m_finish.m_fakeId) + { + GetFakeEdges(m_finish, m_start, isOutgoing, edges); + return; + } + + m_graph.GetEdgesList(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) const +{ + m_graph.GetNeighboringEdges(from.m_point, isOutgoing, edges); + + if (to.IsFake() && 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); + } +} + +inline void IndexGraphStarter::GetArrivalFakeEdges(Joint::Id jointId, + IndexGraphStarter::FakeJoint const & fakeJoint, + bool isOutgoing, vector<JointEdge> & edges) const +{ + if (!fakeJoint.IsFake()) + return; + + 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()); + } +} + void IndexGraphStarter::FindPointsWithCommonFeature(Joint::Id jointId0, Joint::Id jointId1, RoadPoint & result0, RoadPoint & result1) const { @@ -142,46 +133,63 @@ void IndexGraphStarter::FindPointsWithCommonFeature(Joint::Id jointId0, Joint::I ForEachPoint(jointId0, [&](RoadPoint const & rp0) { ForEachPoint(jointId1, [&](RoadPoint const & rp1) { - if (rp0.GetFeatureId() == rp1.GetFeatureId()) - { - RoadGeometry const & road = m_graph.GetGeometry().GetRoad(rp0.GetFeatureId()); - if (!road.IsRoad()) - return; + if (rp0.GetFeatureId() != rp1.GetFeatureId()) + return; + + RoadGeometry const & road = m_graph.GetGeometry().GetRoad(rp0.GetFeatureId()); + if (!road.IsRoad()) + return; - if (road.IsOneWay() && rp0.GetPointId() > rp1.GetPointId()) - return; + if (road.IsOneWay() && rp0.GetPointId() > rp1.GetPointId()) + return; - if (found) + if (found) + { + if (minWeight < 0.0) { - 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(prevRoad, result0.GetPointId(), - result1.GetPointId()); - } - - double const weight = - m_graph.GetEstimator().CalcEdgesWeight(road, rp0.GetPointId(), rp1.GetPointId()); - if (weight < minWeight) - { - minWeight = weight; - result0 = rp0; - result1 = rp1; - } + // 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(prevRoad, result0.GetPointId(), + result1.GetPointId()); } - else + + double const weight = + m_graph.GetEstimator().CalcEdgesWeight(road, rp0.GetPointId(), rp1.GetPointId()); + if (weight < minWeight) { + minWeight = weight; result0 = rp0; result1 = rp1; - found = true; } } + else + { + result0 = rp0; + result1 = rp1; + found = true; + } }); }); if (!found) - MYTHROW(RootException, ("Can't find common feature for joints", jointId0, jointId1)); + MYTHROW(RoutingException, ("Can't find common feature for joints", jointId0, jointId1)); +} + +// IndexGraphStarter::FakeJoint -------------------------------------------------------------------- + +IndexGraphStarter::FakeJoint::FakeJoint(IndexGraph const & graph, RoadPoint point, Joint::Id fakeId, + Joint::Id suggestedId) + : m_point(point), m_fakeId(fakeId), m_jointId(CalcJointId(graph, suggestedId)) +{ +} + +Joint::Id IndexGraphStarter::FakeJoint::CalcJointId(IndexGraph const & graph, + Joint::Id suggestedId) const +{ + if (suggestedId == Joint::kInvalidId) + return m_fakeId; + + return suggestedId; } } // namespace routing |