diff options
26 files changed, 282 insertions, 90 deletions
diff --git a/generator/routing_index_generator.cpp b/generator/routing_index_generator.cpp index c446e8de10..aeabf2d6e7 100644 --- a/generator/routing_index_generator.cpp +++ b/generator/routing_index_generator.cpp @@ -175,10 +175,10 @@ private: // Calculate distance from the starting border point to the transition along the border. // It could be measured clockwise or counterclockwise, direction doesn't matter. -RouteWeight CalcDistanceAlongTheBorders(vector<m2::RegionD> const & borders, - CrossMwmConnectorSerializer::Transition const & transition) +double CalcDistanceAlongTheBorders(vector<m2::RegionD> const & borders, + CrossMwmConnectorSerializer::Transition const & transition) { - RouteWeight distance = GetAStarWeightZero<RouteWeight>(); + auto distance = GetAStarWeightZero<double>(); for (m2::RegionD const & region : borders) { @@ -192,11 +192,11 @@ RouteWeight CalcDistanceAlongTheBorders(vector<m2::RegionD> const & borders, if (m2::RegionD::IsIntersect(transition.GetBackPoint(), transition.GetFrontPoint(), *prev, curr, intersection)) { - distance += RouteWeight(prev->Length(intersection)); + distance += prev->Length(intersection); return distance; } - distance += RouteWeight(prev->Length(curr)); + distance += prev->Length(curr); prev = &curr; } } @@ -324,13 +324,13 @@ void FillWeights(string const & path, string const & mwmFile, string const & cou connector.FillWeights([&](Segment const & enter, Segment const & exit) { auto it0 = weights.find(enter); if (it0 == weights.end()) - return RouteWeight(CrossMwmConnector::kNoRoute); + return CrossMwmConnector::kNoRoute; auto it1 = it0->second.find(exit); if (it1 == it0->second.end()) - return RouteWeight(CrossMwmConnector::kNoRoute); + return CrossMwmConnector::kNoRoute; - return it1->second; + return it1->second.ToCrossMwmWeight(); }); LOG(LINFO, ("Leaps finished, elapsed:", timer.ElapsedSeconds(), "seconds, routes found:", diff --git a/routing/CMakeLists.txt b/routing/CMakeLists.txt index 5e54c2e88e..cc9117d0f0 100644 --- a/routing/CMakeLists.txt +++ b/routing/CMakeLists.txt @@ -15,6 +15,7 @@ set( base/astar_weight.hpp base/followed_polyline.cpp base/followed_polyline.hpp + base/routing_result.hpp bicycle_directions.cpp bicycle_directions.hpp checkpoint_predictor.cpp diff --git a/routing/base/astar_algorithm.hpp b/routing/base/astar_algorithm.hpp index 072ae2e5a3..6fd675db9d 100644 --- a/routing/base/astar_algorithm.hpp +++ b/routing/base/astar_algorithm.hpp @@ -1,6 +1,7 @@ #pragma once #include "routing/base/astar_weight.hpp" +#include "routing/base/routing_result.hpp" #include "base/assert.hpp" #include "base/cancellable.hpp" @@ -13,22 +14,6 @@ namespace routing { - -template <typename TVertexType, typename TWeightType> -struct RoutingResult -{ - std::vector<TVertexType> path; - TWeightType distance; - - RoutingResult() : distance(GetAStarWeightZero<TWeightType>()) {} - - void Clear() - { - path.clear(); - distance = GetAStarWeightZero<TWeightType>(); - } -}; - template <typename TGraph> class AStarAlgorithm { diff --git a/routing/base/routing_result.hpp b/routing/base/routing_result.hpp new file mode 100644 index 0000000000..ec2837ffb2 --- /dev/null +++ b/routing/base/routing_result.hpp @@ -0,0 +1,21 @@ +#pragma once + +#include "routing/base/astar_weight.hpp" + +#include <vector> + +namespace routing +{ +template <typename TVertexType, typename TWeightType> +struct RoutingResult +{ + std::vector<TVertexType> path; + TWeightType distance; + RoutingResult() : distance(GetAStarWeightZero<TWeightType>()) {} + void Clear() + { + path.clear(); + distance = GetAStarWeightZero<TWeightType>(); + } +}; +} // namespace routing diff --git a/routing/cross_mwm_connector.cpp b/routing/cross_mwm_connector.cpp index 64297d37a0..1b17386f65 100644 --- a/routing/cross_mwm_connector.cpp +++ b/routing/cross_mwm_connector.cpp @@ -149,8 +149,8 @@ std::string DebugPrint(CrossMwmConnector::WeightsLoadState state) void CrossMwmConnector::AddEdge(Segment const & segment, Weight weight, std::vector<SegmentEdge> & edges) const { - if (weight != static_cast<Weight>(kNoRoute)) - edges.emplace_back(segment, RouteWeight(static_cast<double>(weight))); + if (weight != kNoRoute) + edges.emplace_back(segment, RouteWeight::FromCrossMwmWeight(weight)); } CrossMwmConnector::Transition const & CrossMwmConnector::GetTransition( diff --git a/routing/cross_mwm_connector.hpp b/routing/cross_mwm_connector.hpp index 1b5d49ac72..904ca0637c 100644 --- a/routing/cross_mwm_connector.hpp +++ b/routing/cross_mwm_connector.hpp @@ -62,9 +62,9 @@ public: { for (Segment const & exit : m_exits) { - RouteWeight const weight = calcWeight(enter, exit); + auto const weight = calcWeight(enter, exit); // Edges weights should be >= astar heuristic, so use std::ceil. - m_weights.push_back(static_cast<Weight>(std::ceil(weight.GetWeight()))); + m_weights.push_back(static_cast<Weight>(std::ceil(weight))); } } } diff --git a/routing/cross_mwm_osrm_graph.cpp b/routing/cross_mwm_osrm_graph.cpp index 58c7aae429..d7aa3a1fb8 100644 --- a/routing/cross_mwm_osrm_graph.cpp +++ b/routing/cross_mwm_osrm_graph.cpp @@ -103,8 +103,9 @@ void AddSegmentEdge(NumMwmIds const & numMwmIds, OsrmFtSegMapping const & segMap double constexpr kAstarHeuristicFactor = 100000; //// Osrm multiplies seconds to 10, so we need to divide it back. double constexpr kOSRMWeightToSecondsMultiplier = 0.1; - edges.emplace_back(segment, RouteWeight(osrmEdge.GetWeight() * kOSRMWeightToSecondsMultiplier * - kAstarHeuristicFactor)); + edges.emplace_back( + segment, RouteWeight::FromCrossMwmWeight( + osrmEdge.GetWeight() * kOSRMWeightToSecondsMultiplier * kAstarHeuristicFactor)); } } // namespace diff --git a/routing/cross_mwm_router.cpp b/routing/cross_mwm_router.cpp index df4e6a15c6..5a04b2e314 100644 --- a/routing/cross_mwm_router.cpp +++ b/routing/cross_mwm_router.cpp @@ -1,8 +1,9 @@ #include "routing/cross_mwm_router.hpp" +#include "routing/base/astar_algorithm.hpp" +#include "routing/base/routing_result.hpp" #include "routing/cross_mwm_road_graph.hpp" -#include "base/astar_algorithm.hpp" #include "base/timer.hpp" namespace routing diff --git a/routing/geometry.hpp b/routing/geometry.hpp index aa432b27dd..d30cffa347 100644 --- a/routing/geometry.hpp +++ b/routing/geometry.hpp @@ -57,6 +57,8 @@ public: return pointId == 0 || pointId + 1 == GetPointsCount(); } + void SetTransitAllowedForTests(bool transitAllowed) { m_isTransitAllowed = transitAllowed; } + private: buffer_vector<Junction, 32> m_junctions; double m_speed = 0.0; diff --git a/routing/index_graph.cpp b/routing/index_graph.cpp index 27f91c479e..013576e364 100644 --- a/routing/index_graph.cpp +++ b/routing/index_graph.cpp @@ -112,13 +112,14 @@ void IndexGraph::GetIngoingEdgesList(Segment const & segment, vector<SegmentEdge RouteWeight IndexGraph::HeuristicCostEstimate(Segment const & from, Segment const & to) { return RouteWeight( - m_estimator->CalcHeuristic(GetPoint(from, true /* front */), GetPoint(to, true /* front */))); + m_estimator->CalcHeuristic(GetPoint(from, true /* front */), GetPoint(to, true /* front */)), + 0); } RouteWeight IndexGraph::CalcSegmentWeight(Segment const & segment) { return RouteWeight( - m_estimator->CalcSegmentWeight(segment, m_geometry.GetRoad(segment.GetFeatureId()))); + m_estimator->CalcSegmentWeight(segment, m_geometry.GetRoad(segment.GetFeatureId())), 0); } void IndexGraph::GetNeighboringEdges(Segment const & from, RoadPoint const & rp, bool isOutgoing, @@ -168,11 +169,16 @@ void IndexGraph::GetNeighboringEdge(Segment const & from, Segment const & to, bo edges.emplace_back(to, weight); } -RouteWeight IndexGraph::GetPenalties(Segment const & u, Segment const & v) const +RouteWeight IndexGraph::GetPenalties(Segment const & u, Segment const & v) { + bool fromTransitAllowed = m_geometry.GetRoad(u.GetFeatureId()).IsTransitAllowed(); + bool toTransitAllowed = m_geometry.GetRoad(v.GetFeatureId()).IsTransitAllowed(); + + uint32_t transitPenalty = fromTransitAllowed == toTransitAllowed ? 0 : 1; + if (IsUTurn(u, v)) - return RouteWeight(m_estimator->GetUTurnPenalty()); + return RouteWeight(m_estimator->GetUTurnPenalty(), transitPenalty); - return RouteWeight(0.0); + return RouteWeight(0.0, transitPenalty); } } // namespace routing diff --git a/routing/index_graph.hpp b/routing/index_graph.hpp index 459b7b69bd..7d65f5ee70 100644 --- a/routing/index_graph.hpp +++ b/routing/index_graph.hpp @@ -83,7 +83,7 @@ private: vector<SegmentEdge> & edges); void GetNeighboringEdge(Segment const & from, Segment const & to, bool isOutgoing, vector<SegmentEdge> & edges); - RouteWeight GetPenalties(Segment const & u, Segment const & v) const; + RouteWeight GetPenalties(Segment const & u, Segment const & v); m2::PointD const & GetPoint(Segment const & segment, bool front) { return GetGeometry().GetRoad(segment.GetFeatureId()).GetPoint(segment.GetPointId(front)); diff --git a/routing/index_graph_starter.cpp b/routing/index_graph_starter.cpp index e2273321f0..046143dd09 100644 --- a/routing/index_graph_starter.cpp +++ b/routing/index_graph_starter.cpp @@ -214,6 +214,38 @@ set<NumMwmId> IndexGraphStarter::GetMwms() const return mwms; } +bool IndexGraphStarter::CheckRoutingResultMeetsRestrictions( + RoutingResult<Segment, RouteWeight> const & result) const +{ + uint32_t nontransitCrossAllowed = 0; + auto isRealOrPart = [this](Segment const & segment) { + if (!IsFakeSegment(segment)) + return true; + return m_fake.m_fakeToReal.find(segment) != m_fake.m_fakeToReal.end(); + }; + auto isTransitAllowed = [this](Segment const & segment) { + auto real = segment; + bool const convertionResult = ConvertToReal(real); + CHECK(convertionResult, ()); + return m_graph.GetRoadGeometry(real.GetMwmId(), real.GetFeatureId()).IsTransitAllowed(); + }; + + auto const firstRealOrPart = find_if(result.path.begin(), result.path.end(), isRealOrPart); + if (firstRealOrPart != result.path.end() && !isTransitAllowed(*firstRealOrPart)) + ++nontransitCrossAllowed; + + auto const lastRealOrPart = find_if(result.path.rbegin(), result.path.rend(), isRealOrPart); + // If firstRealOrPart and lastRealOrPart point to the same segment increment + // nontransitCrossAllowed once + if (lastRealOrPart != result.path.rend() && (lastRealOrPart.base() - 1) != firstRealOrPart && + !isTransitAllowed(*lastRealOrPart)) + { + ++nontransitCrossAllowed; + } + + return nontransitCrossAllowed >= result.distance.GetNontransitCross(); +} + void IndexGraphStarter::GetEdgesList(Segment const & segment, bool isOutgoing, vector<SegmentEdge> & edges) const { @@ -238,7 +270,7 @@ void IndexGraphStarter::GetEdgesList(Segment const & segment, bool isOutgoing, if (it != adjacentEdges.end()) { for (auto const & s : it->second) - edges.emplace_back(s, RouteWeight(CalcSegmentWeight(isOutgoing ? s : segment))); + edges.emplace_back(s, CalcSegmentWeight(isOutgoing ? s : segment)); } } else @@ -249,24 +281,27 @@ void IndexGraphStarter::GetEdgesList(Segment const & segment, bool isOutgoing, AddFakeEdges(segment, edges); } -double IndexGraphStarter::CalcSegmentWeight(Segment const & segment) const +RouteWeight IndexGraphStarter::CalcSegmentWeight(Segment const & segment) const { if (!IsFakeSegment(segment)) { - return m_graph.GetEstimator().CalcSegmentWeight( - segment, m_graph.GetRoadGeometry(segment.GetMwmId(), segment.GetFeatureId())); + return RouteWeight( + m_graph.GetEstimator().CalcSegmentWeight( + segment, m_graph.GetRoadGeometry(segment.GetMwmId(), segment.GetFeatureId())), + 0); } auto const fakeVertexIt = m_fake.m_segmentToVertex.find(segment); CHECK(fakeVertexIt != m_fake.m_segmentToVertex.end(), ("Requested junction for invalid fake segment.")); - return m_graph.GetEstimator().CalcLeapWeight(fakeVertexIt->second.GetPointFrom(), - fakeVertexIt->second.GetPointTo()); + return RouteWeight(m_graph.GetEstimator().CalcLeapWeight(fakeVertexIt->second.GetPointFrom(), + fakeVertexIt->second.GetPointTo()), + 0); } -double IndexGraphStarter::CalcRouteSegmentWeight(vector<Segment> const & route, - size_t segmentIndex) const +RouteWeight IndexGraphStarter::CalcRouteSegmentWeight(vector<Segment> const & route, + size_t segmentIndex) const { CHECK_LESS( segmentIndex, route.size(), @@ -383,7 +418,7 @@ void IndexGraphStarter::AddStart(FakeEnding const & startEnding, FakeEnding cons // Check fake segment is connected to source segment. if (GetJunction(s, false /* front */) == GetJunction(segment, true) || GetJunction(s, true) == GetJunction(segment, false)) - fakeEdges.emplace_back(s, RouteWeight(edge.GetWeight())); + fakeEdges.emplace_back(s, edge.GetWeight()); } } edges.insert(edges.end(), fakeEdges.begin(), fakeEdges.end()); @@ -414,8 +449,10 @@ void IndexGraphStarter::ConnectLeapToTransitions(Segment const & segment, bool i // point. So |isEnter| below should be set to true. m_graph.ForEachTransition( segment.GetMwmId(), !isOutgoing /* isEnter */, [&](Segment const & transition) { - edges.emplace_back(transition, RouteWeight(m_graph.GetEstimator().CalcLeapWeight( - segmentPoint, GetPoint(transition, isOutgoing)))); + edges.emplace_back(transition, + RouteWeight(m_graph.GetEstimator().CalcLeapWeight( + segmentPoint, GetPoint(transition, isOutgoing)), + 0)); }); } diff --git a/routing/index_graph_starter.hpp b/routing/index_graph_starter.hpp index 72414bd358..2e9967809b 100644 --- a/routing/index_graph_starter.hpp +++ b/routing/index_graph_starter.hpp @@ -1,5 +1,6 @@ #pragma once +#include "routing/base/routing_result.hpp" #include "routing/index_graph.hpp" #include "routing/joint.hpp" #include "routing/num_mwm_id.hpp" @@ -83,6 +84,11 @@ public: std::set<NumMwmId> GetMwms() const; + // Checks |result| meets nontransit crossing restrictions according to placement of + // |result.path| start and finish in transit/nontransit area and number of nontransit crosses + bool CheckRoutingResultMeetsRestrictions( + RoutingResult<Segment, RouteWeight> const & result) const; + void GetEdgesList(Segment const & segment, bool isOutgoing, std::vector<SegmentEdge> & edges) const; @@ -99,11 +105,12 @@ public: RouteWeight HeuristicCostEstimate(TVertexType const & from, TVertexType const & to) const { return RouteWeight(m_graph.GetEstimator().CalcHeuristic(GetPoint(from, true /* front */), - GetPoint(to, true /* front */))); + GetPoint(to, true /* front */)), + 0); } - double CalcSegmentWeight(Segment const & segment) const; - double CalcRouteSegmentWeight(std::vector<Segment> const & route, size_t segmentIndex) const; + RouteWeight CalcSegmentWeight(Segment const & segment) const; + RouteWeight CalcRouteSegmentWeight(std::vector<Segment> const & route, size_t segmentIndex) const; bool IsLeap(NumMwmId mwmId) const; diff --git a/routing/index_router.cpp b/routing/index_router.cpp index 4c44b5b4c4..8ff50d8e64 100644 --- a/routing/index_router.cpp +++ b/routing/index_router.cpp @@ -2,6 +2,7 @@ #include "routing/base/astar_algorithm.hpp" #include "routing/base/astar_progress.hpp" +#include "routing/base/routing_result.hpp" #include "routing/bicycle_directions.hpp" #include "routing/index_graph.hpp" #include "routing/index_graph_loader.hpp" @@ -532,6 +533,9 @@ IRouter::ResultCode IndexRouter::CalculateSubroute(Checkpoints const & checkpoin if (result != IRouter::NoError) return result; + if (!starter.CheckRoutingResultMeetsRestrictions(routingResult)) + return IRouter::RouteNotFound; + IRouter::ResultCode const leapsResult = ProcessLeaps(routingResult.path, delegate, starter.GetGraph().GetMode(), starter, subroute); if (leapsResult != IRouter::NoError) @@ -580,8 +584,7 @@ IRouter::ResultCode IndexRouter::AdjustRoute(Checkpoints const & checkpoints, for (size_t i = lastSubroute.GetBeginSegmentIdx(); i < lastSubroute.GetEndSegmentIdx(); ++i) { auto const & step = steps[i]; - prevEdges.emplace_back(step.GetSegment(), - RouteWeight(starter.CalcSegmentWeight(step.GetSegment()))); + prevEdges.emplace_back(step.GetSegment(), starter.CalcSegmentWeight(step.GetSegment())); } uint32_t visitCount = 0; @@ -603,7 +606,7 @@ IRouter::ResultCode IndexRouter::AdjustRoute(Checkpoints const & checkpoints, RoutingResult<Segment, RouteWeight> result; auto resultCode = ConvertResult<IndexGraphStarter>( algorithm.AdjustRoute(starter, starter.GetStartSegment(), prevEdges, - RouteWeight(kAdjustLimitSec), result, delegate, onVisitJunction)); + RouteWeight(kAdjustLimitSec, 0), result, delegate, onVisitJunction)); if (resultCode != IRouter::NoError) return resultCode; @@ -785,7 +788,7 @@ IRouter::ResultCode IndexRouter::RedressRoute(vector<Segment> const & segments, for (size_t i = 0; i + 1 < numPoints; ++i) { - time += starter.CalcRouteSegmentWeight(segments, i); + time += starter.CalcRouteSegmentWeight(segments, i).GetWeight(); times.emplace_back(static_cast<uint32_t>(i + 1), time); } diff --git a/routing/route_weight.cpp b/routing/route_weight.cpp index f962b6d345..a8645f457d 100644 --- a/routing/route_weight.cpp +++ b/routing/route_weight.cpp @@ -1,17 +1,26 @@ #include "routing/route_weight.hpp" +#include "routing/cross_mwm_connector.hpp" + using namespace std; namespace routing { +double RouteWeight::ToCrossMwmWeight() const +{ + if (m_nontransitCross > 0) + return CrossMwmConnector::kNoRoute; + return GetWeight(); +} + ostream & operator<<(ostream & os, RouteWeight const & routeWeight) { - os << routeWeight.GetWeight(); + os << "(" << routeWeight.GetNontransitCross() << ", " << routeWeight.GetWeight() << ")"; return os; } RouteWeight operator*(double lhs, RouteWeight const & rhs) { - return RouteWeight(lhs * rhs.GetWeight()); + return RouteWeight(lhs * rhs.GetWeight(), rhs.GetNontransitCross()); } } // namespace routing diff --git a/routing/route_weight.hpp b/routing/route_weight.hpp index adebf609bc..0119ae3957 100644 --- a/routing/route_weight.hpp +++ b/routing/route_weight.hpp @@ -2,6 +2,7 @@ #include "routing/base/astar_weight.hpp" +#include <cstdint> #include <iostream> #include <limits> @@ -12,11 +13,22 @@ class RouteWeight final public: RouteWeight() = default; - constexpr explicit RouteWeight(double weight) : m_weight(weight) {} + constexpr RouteWeight(double weight, int32_t nontransitCross) + : m_weight(weight), m_nontransitCross(nontransitCross) + { + } double GetWeight() const { return m_weight; } + int32_t GetNontransitCross() const { return m_nontransitCross; } + static RouteWeight FromCrossMwmWeight(double weight) { return RouteWeight(weight, 0); } + double ToCrossMwmWeight() const; - bool operator<(RouteWeight const & rhs) const { return m_weight < rhs.m_weight; } + bool operator<(RouteWeight const & rhs) const + { + if (m_nontransitCross != rhs.m_nontransitCross) + return m_nontransitCross < rhs.m_nontransitCross; + return m_weight < rhs.m_weight; + } bool operator==(RouteWeight const & rhs) const { return !((*this) < rhs) && !(rhs < (*this)); } @@ -28,24 +40,26 @@ public: RouteWeight operator+(RouteWeight const & rhs) const { - return RouteWeight(m_weight + rhs.m_weight); + return RouteWeight(m_weight + rhs.m_weight, m_nontransitCross + rhs.m_nontransitCross); } RouteWeight operator-(RouteWeight const & rhs) const { - return RouteWeight(m_weight - rhs.m_weight); + return RouteWeight(m_weight - rhs.m_weight, m_nontransitCross - rhs.m_nontransitCross); } RouteWeight & operator+=(RouteWeight const & rhs) { m_weight += rhs.m_weight; + m_nontransitCross += rhs.m_nontransitCross; return *this; } - RouteWeight operator-() const { return RouteWeight(-m_weight); } + RouteWeight operator-() const { return RouteWeight(-m_weight, -m_nontransitCross); } private: double m_weight = 0.0; + int32_t m_nontransitCross = 0; }; std::ostream & operator<<(std::ostream & os, RouteWeight const & routeWeight); @@ -55,19 +69,19 @@ RouteWeight operator*(double lhs, RouteWeight const & rhs); template <> constexpr RouteWeight GetAStarWeightMax<RouteWeight>() { - return RouteWeight(std::numeric_limits<double>::max()); + return RouteWeight(std::numeric_limits<double>::max(), std::numeric_limits<int32_t>::max()); } template <> constexpr RouteWeight GetAStarWeightZero<RouteWeight>() { - return RouteWeight(0.0); + return RouteWeight(0.0, 0); } template <> constexpr RouteWeight GetAStarWeightEpsilon<RouteWeight>() { - return RouteWeight(GetAStarWeightEpsilon<double>()); + return RouteWeight(GetAStarWeightEpsilon<double>(), 0); } } // namespace routing diff --git a/routing/routing.pro b/routing/routing.pro index 89cbb030bf..1ec33a943e 100644 --- a/routing/routing.pro +++ b/routing/routing.pro @@ -76,6 +76,7 @@ HEADERS += \ base/astar_algorithm.hpp \ base/astar_weight.hpp \ base/followed_polyline.hpp \ + base/routing_result.hpp \ bicycle_directions.hpp \ checkpoint_predictor.hpp \ checkpoints.hpp \ diff --git a/routing/routing_algorithm.cpp b/routing/routing_algorithm.cpp index 8540a834ba..3323122289 100644 --- a/routing/routing_algorithm.cpp +++ b/routing/routing_algorithm.cpp @@ -1,7 +1,8 @@ -#include "routing/road_graph.hpp" #include "routing/routing_algorithm.hpp" + #include "routing/base/astar_algorithm.hpp" #include "routing/base/astar_progress.hpp" +#include "routing/road_graph.hpp" #include "base/assert.hpp" diff --git a/routing/routing_algorithm.hpp b/routing/routing_algorithm.hpp index 1101ee2782..e1eb72467b 100644 --- a/routing/routing_algorithm.hpp +++ b/routing/routing_algorithm.hpp @@ -1,10 +1,10 @@ #pragma once -#include "base/cancellable.hpp" - +#include "routing/base/routing_result.hpp" #include "routing/road_graph.hpp" #include "routing/router.hpp" -#include "routing/base/astar_algorithm.hpp" + +#include "base/cancellable.hpp" #include "std/functional.hpp" #include "std/string.hpp" diff --git a/routing/routing_tests/astar_algorithm_test.cpp b/routing/routing_tests/astar_algorithm_test.cpp index 7a0f82bbc2..cdcc237247 100644 --- a/routing/routing_tests/astar_algorithm_test.cpp +++ b/routing/routing_tests/astar_algorithm_test.cpp @@ -1,6 +1,8 @@ #include "testing/testing.hpp" #include "routing/base/astar_algorithm.hpp" +#include "routing/base/routing_result.hpp" + #include "std/map.hpp" #include "std/utility.hpp" #include "std/vector.hpp" diff --git a/routing/routing_tests/cross_mwm_connector_test.cpp b/routing/routing_tests/cross_mwm_connector_test.cpp index 8d3c886ab5..a7802b066a 100644 --- a/routing/routing_tests/cross_mwm_connector_test.cpp +++ b/routing/routing_tests/cross_mwm_connector_test.cpp @@ -143,7 +143,7 @@ UNIT_TEST(TwoWayExit) UNIT_TEST(Serialization) { - RouteWeight constexpr kEdgesWeight = RouteWeight(4444.0); + double constexpr kEdgesWeight = 4444.0; vector<uint8_t> buffer; { @@ -231,28 +231,25 @@ UNIT_TEST(Serialization) ()); TestEdges(connector, Segment(mwmId, 10, 1, true /* forward */), true /* isOutgoing */, - {{Segment(mwmId, 20, 2, false /* forward */), kEdgesWeight}}); + {{Segment(mwmId, 20, 2, false /* forward */), + RouteWeight::FromCrossMwmWeight(kEdgesWeight)}}); TestEdges(connector, Segment(mwmId, 20, 2, true /* forward */), true /* isOutgoing */, - {{Segment(mwmId, 20, 2, false /* forward */), kEdgesWeight}}); + {{Segment(mwmId, 20, 2, false /* forward */), + RouteWeight::FromCrossMwmWeight(kEdgesWeight)}}); - TestEdges(connector, Segment(mwmId, 20, 2, false /* forward */), false /* isOutgoing */, - {{Segment(mwmId, 10, 1, true /* forward */), kEdgesWeight}, - {Segment(mwmId, 20, 2, true /* forward */), kEdgesWeight}}); + TestEdges( + connector, Segment(mwmId, 20, 2, false /* forward */), false /* isOutgoing */, + {{Segment(mwmId, 10, 1, true /* forward */), RouteWeight::FromCrossMwmWeight(kEdgesWeight)}, + {Segment(mwmId, 20, 2, true /* forward */), RouteWeight::FromCrossMwmWeight(kEdgesWeight)}}); } UNIT_TEST(WeightsSerialization) { size_t constexpr kNumTransitions = 3; - vector<RouteWeight> const weights = {RouteWeight(4.0), - RouteWeight(20.0), - RouteWeight(CrossMwmConnector::kNoRoute), - RouteWeight(12.0), - RouteWeight(CrossMwmConnector::kNoRoute), - RouteWeight(40.0), - RouteWeight(48.0), - RouteWeight(24.0), - RouteWeight(12.0)}; + vector<double> const weights = { + 4.0, 20.0, CrossMwmConnector::kNoRoute, 12.0, CrossMwmConnector::kNoRoute, 40.0, 48.0, + 24.0, 12.0}; TEST_EQUAL(weights.size(), kNumTransitions * kNumTransitions, ()); vector<uint8_t> buffer; @@ -311,10 +308,10 @@ UNIT_TEST(WeightsSerialization) for (uint32_t exitId = 0; exitId < kNumTransitions; ++exitId) { auto const weight = weights[weightIdx]; - if (weight != RouteWeight(CrossMwmConnector::kNoRoute)) + if (weight != CrossMwmConnector::kNoRoute) { expectedEdges.emplace_back(Segment(mwmId, exitId, 1 /* segmentIdx */, false /* forward */), - weight); + RouteWeight::FromCrossMwmWeight(weight)); } ++weightIdx; } diff --git a/routing/routing_tests/index_graph_tools.cpp b/routing/routing_tests/index_graph_tools.cpp index 7577f3748d..3cf02c754e 100644 --- a/routing/routing_tests/index_graph_tools.cpp +++ b/routing/routing_tests/index_graph_tools.cpp @@ -2,6 +2,8 @@ #include "testing/testing.hpp" +#include "routing/base/routing_result.hpp" + #include "routing_common/car_model.hpp" #include "base/assert.hpp" @@ -21,11 +23,12 @@ void TestGeometryLoader::Load(uint32_t featureId, RoadGeometry & road) } void TestGeometryLoader::AddRoad(uint32_t featureId, bool oneWay, float speed, - RoadGeometry::Points const & points) + RoadGeometry::Points const & points, bool transitAllowed) { auto it = m_roads.find(featureId); CHECK(it == m_roads.end(), ("Already contains feature", featureId)); m_roads[featureId] = RoadGeometry(oneWay, speed, points); + m_roads[featureId].SetTransitAllowedForTests(transitAllowed); } // ZeroGeometryLoader ------------------------------------------------------------------------------ @@ -287,6 +290,9 @@ AStarAlgorithm<IndexGraphStarter>::Result CalculateRoute(IndexGraphStarter & sta starter, starter.GetStartSegment(), starter.GetFinishSegment(), routingResult, {} /* cancellable */, {} /* onVisitedVertexCallback */); + if (!starter.CheckRoutingResultMeetsRestrictions(routingResult)) + resultCode == AStarAlgorithm<IndexGraphStarter>::Result::NoPath; + timeSec = routingResult.distance.GetWeight(); roadPoints = routingResult.path; return resultCode; diff --git a/routing/routing_tests/index_graph_tools.hpp b/routing/routing_tests/index_graph_tools.hpp index 946b885070..520411a7df 100644 --- a/routing/routing_tests/index_graph_tools.hpp +++ b/routing/routing_tests/index_graph_tools.hpp @@ -62,7 +62,7 @@ public: void Load(uint32_t featureId, routing::RoadGeometry & road) override; void AddRoad(uint32_t featureId, bool oneWay, float speed, - routing::RoadGeometry::Points const & points); + routing::RoadGeometry::Points const & points, bool transitAllowed = true); private: unordered_map<uint32_t, routing::RoadGeometry> m_roads; diff --git a/routing/routing_tests/restriction_test.cpp b/routing/routing_tests/restriction_test.cpp index 012cf7ecaa..e1e3a12089 100644 --- a/routing/routing_tests/restriction_test.cpp +++ b/routing/routing_tests/restriction_test.cpp @@ -896,4 +896,97 @@ UNIT_CLASS_TEST(RestrictionTest, FGraph_RestrictionF0F2Only) m2::PointD(1, 1), *m_graph), move(restrictions), *this); } + +// *---F4---* +// | | +// F3 F5 +// | | +// 0 Start *---F0---*---F1---*---F2---* Finish +// 0 1 2 3 +unique_ptr<WorldGraph> BuildNontransitGraph(bool transitStart, bool transitShortWay, + bool transitLongWay) +{ + unique_ptr<TestGeometryLoader> loader = make_unique<TestGeometryLoader>(); + loader->AddRoad(0 /* feature id */, false /* one way */, 1.0 /* speed */, + RoadGeometry::Points({{0.0, 0.0}, {1.0, 0.0}}), + transitStart /* transitAllowed */); + loader->AddRoad(1 /* feature id */, false /* one way */, 1.0 /* speed */, + RoadGeometry::Points({{1.0, 0.0}, {2.0, 0.0}}), + transitShortWay /* transitAllowed */); + loader->AddRoad(2 /* feature id */, false /* one way */, 1.0 /* speed */, + RoadGeometry::Points({{2.0, 0.0}, {3.0, 0.0}}), true /* transitAllowed */); + loader->AddRoad(3 /* feature id */, false /* one way */, 1.0 /* speed */, + RoadGeometry::Points({{1.0, 0.0}, {1.0, 1.0}}), true /* transitAllowed */); + loader->AddRoad(4 /* feature id */, false /* one way */, 1.0 /* speed */, + RoadGeometry::Points({{1.0, 1.0}, {2.0, 1.0}}), + transitLongWay /* transitAllowed */); + loader->AddRoad(5 /* feature id */, false /* one way */, 1.0 /* speed */, + RoadGeometry::Points({{2.0, 1.0}, {2.0, 0.0}}), true /* transitAllowed */); + + vector<Joint> const joints = { + MakeJoint({{0 /* feature id */, 0 /* point id */}}), /* joint at point (0, 0) */ + MakeJoint({{0, 1}, {1, 0}, {3, 0}}), /* joint at point (1, 0) */ + MakeJoint({{1, 1}, {2, 0}, {5, 1}}), /* joint at point (2, 0) */ + MakeJoint({{3, 1}, {4, 0}}), /* joint at point (1, 1) */ + MakeJoint({{4, 1}, {5, 0}}), /* joint at point (2, 1) */ + MakeJoint({{2, 1}}), /* joint at point (3, 0) */ + }; + + traffic::TrafficCache const trafficCache; + shared_ptr<EdgeEstimator> estimator = CreateEstimatorForCar(trafficCache); + return BuildWorldGraph(move(loader), estimator, joints); +} + +UNIT_CLASS_TEST(RestrictionTest, NontransitStart) +{ + Init(BuildNontransitGraph(false /* transitStart */, true /* transitShortWay */, + true /* transitLongWay */)); + vector<m2::PointD> const expectedGeom = {{0 /* x */, 0 /* y */}, {1, 0}, {2, 0}, {3, 0}}; + + SetStarter(routing::IndexGraphStarter::MakeFakeEnding( + Segment(kTestNumMwmId, 0, 0, true /* forward */), m2::PointD(0, 0), *m_graph), + routing::IndexGraphStarter::MakeFakeEnding( + Segment(kTestNumMwmId, 2, 0, true /* forward */), m2::PointD(3, 0), *m_graph)); + TestRouteGeometry(*m_starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); +} + +UNIT_CLASS_TEST(RestrictionTest, NontransitShortWay) +{ + Init(BuildNontransitGraph(true /* transitStart */, false /* transitShortWay */, + true /* transitLongWay */)); + vector<m2::PointD> const expectedGeom = { + {0 /* x */, 0 /* y */}, {1, 0}, {1, 1}, {2, 1}, {2, 0}, {3, 0}}; + + SetStarter(routing::IndexGraphStarter::MakeFakeEnding( + Segment(kTestNumMwmId, 0, 0, true /* forward */), m2::PointD(0, 0), *m_graph), + routing::IndexGraphStarter::MakeFakeEnding( + Segment(kTestNumMwmId, 2, 0, true /* forward */), m2::PointD(3, 0), *m_graph)); + TestRouteGeometry(*m_starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); +} + +UNIT_CLASS_TEST(RestrictionTest, NontransitWay) +{ + Init(BuildNontransitGraph(true /* transitStart */, false /* transitShortWay */, + false /* transitLongWay */)); + + SetStarter(routing::IndexGraphStarter::MakeFakeEnding( + Segment(kTestNumMwmId, 0, 0, true /* forward */), m2::PointD(0, 0), *m_graph), + routing::IndexGraphStarter::MakeFakeEnding( + Segment(kTestNumMwmId, 2, 0, true /* forward */), m2::PointD(3, 0), *m_graph)); + TestRouteGeometry(*m_starter, AStarAlgorithm<IndexGraphStarter>::Result::NoPath, {}); +} + +UNIT_CLASS_TEST(RestrictionTest, NontransiStartAndShortWay) +{ + Init(BuildNontransitGraph(false /* transitStart */, false /* transitShortWay */, + true /* transitLongWay */)); + // We can get F1 because F0 is in the same nontransit area/ + vector<m2::PointD> const expectedGeom = {{0 /* x */, 0 /* y */}, {1, 0}, {2, 0}, {3, 0}}; + + SetStarter(routing::IndexGraphStarter::MakeFakeEnding( + Segment(kTestNumMwmId, 0, 0, true /* forward */), m2::PointD(0, 0), *m_graph), + routing::IndexGraphStarter::MakeFakeEnding( + Segment(kTestNumMwmId, 2, 0, true /* forward */), m2::PointD(3, 0), *m_graph)); + TestRouteGeometry(*m_starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); +} } // namespace routing_test diff --git a/routing/world_graph.cpp b/routing/world_graph.cpp index 16397dde50..976ce62a4d 100644 --- a/routing/world_graph.cpp +++ b/routing/world_graph.cpp @@ -63,7 +63,8 @@ void WorldGraph::GetIngoingEdgesList(Segment const & segment, vector<SegmentEdge RouteWeight WorldGraph::HeuristicCostEstimate(Segment const & from, Segment const & to) { return RouteWeight( - m_estimator->CalcHeuristic(GetPoint(from, true /* front */), GetPoint(to, true /* front */))); + m_estimator->CalcHeuristic(GetPoint(from, true /* front */), GetPoint(to, true /* front */)), + 0); } void WorldGraph::GetTwins(Segment const & segment, bool isOutgoing, vector<SegmentEdge> & edges) @@ -75,7 +76,7 @@ void WorldGraph::GetTwins(Segment const & segment, bool isOutgoing, vector<Segme m2::PointD const & from = GetPoint(segment, true /* front */); m2::PointD const & to = GetPoint(twin, true /* front */); double const weight = m_estimator->CalcHeuristic(from, to); - edges.emplace_back(twin, RouteWeight(weight)); + edges.emplace_back(twin, RouteWeight(weight, 0)); } } diff --git a/xcode/routing/routing.xcodeproj/project.pbxproj b/xcode/routing/routing.xcodeproj/project.pbxproj index b017aa98cd..8a13e2944f 100644 --- a/xcode/routing/routing.xcodeproj/project.pbxproj +++ b/xcode/routing/routing.xcodeproj/project.pbxproj @@ -56,6 +56,7 @@ 3462FDAD1DC1E5BF00906FD7 /* libopening_hours.a in Frameworks */ = {isa = PBXBuildFile; fileRef = 3462FDAC1DC1E5BF00906FD7 /* libopening_hours.a */; }; 349D1CE01E3F589900A878FD /* restrictions_serialization.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 349D1CDE1E3F589900A878FD /* restrictions_serialization.cpp */; }; 349D1CE11E3F589900A878FD /* restrictions_serialization.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 349D1CDF1E3F589900A878FD /* restrictions_serialization.hpp */; }; + 405F48DC1F6AD01C005BA81A /* routing_result.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 405F48DB1F6AD01C005BA81A /* routing_result.hpp */; }; 40A111CD1F2F6776005E6AD5 /* route_weight.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 40A111CB1F2F6776005E6AD5 /* route_weight.cpp */; }; 40A111CE1F2F6776005E6AD5 /* route_weight.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 40A111CC1F2F6776005E6AD5 /* route_weight.hpp */; }; 40A111D01F2F9704005E6AD5 /* astar_weight.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 40A111CF1F2F9704005E6AD5 /* astar_weight.hpp */; }; @@ -338,6 +339,7 @@ 349D1CDF1E3F589900A878FD /* restrictions_serialization.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = restrictions_serialization.hpp; 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>"; }; + 405F48DB1F6AD01C005BA81A /* routing_result.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = routing_result.hpp; sourceTree = "<group>"; }; 40A111CB1F2F6776005E6AD5 /* route_weight.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = route_weight.cpp; sourceTree = "<group>"; }; 40A111CC1F2F6776005E6AD5 /* route_weight.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = route_weight.hpp; sourceTree = "<group>"; }; 40A111CF1F2F9704005E6AD5 /* astar_weight.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = astar_weight.hpp; sourceTree = "<group>"; }; @@ -640,6 +642,7 @@ 671F58BC1B874EC80032311E /* followed_polyline.hpp */, A1616E2D1B6B60B3003F078E /* astar_progress.hpp */, A120B3521B4A7C1C002F3808 /* astar_algorithm.hpp */, + 405F48DB1F6AD01C005BA81A /* routing_result.hpp */, ); path = base; sourceTree = "<group>"; @@ -1002,6 +1005,7 @@ A120B3511B4A7C0A002F3808 /* routing_algorithm.hpp in Headers */, 0C5FEC6B1DDE193F0017688C /* road_point.hpp in Headers */, 56099E2B1CC7C97D00A7772A /* turn_candidate.hpp in Headers */, + 405F48DC1F6AD01C005BA81A /* routing_result.hpp in Headers */, 56C4392D1E93E5DF00998E29 /* transition_points.hpp in Headers */, 0C5FEC551DDE191E0017688C /* edge_estimator.hpp in Headers */, 670B84C11A9381D900CE4492 /* cross_routing_context.hpp in Headers */, |