From 9d1a016d430caa34bba37b106ddf4ae44ac6a7e1 Mon Sep 17 00:00:00 2001 From: Vladimir Byko-Ianko Date: Thu, 15 Feb 2018 16:20:47 +0300 Subject: Removing slight turns if a route follows the main road and other possible turns go to link. --- routing/bicycle_directions.cpp | 7 +++- routing/routing_integration_tests/turn_test.cpp | 36 +++++++++++++++++- routing/turn_candidate.hpp | 40 ++++++++++---------- routing/turns_generator.cpp | 50 +++++++++++++++++++------ 4 files changed, 98 insertions(+), 35 deletions(-) (limited to 'routing') diff --git a/routing/bicycle_directions.cpp b/routing/bicycle_directions.cpp index 97d6429094..8a504c8eba 100644 --- a/routing/bicycle_directions.cpp +++ b/routing/bicycle_directions.cpp @@ -263,6 +263,8 @@ void BicycleDirectionsEngine::GetSegmentRangeAndAdjacentEdges( ASSERT_NOT_EQUAL(highwayClass, ftypes::HighwayClass::Error, ()); ASSERT_NOT_EQUAL(highwayClass, ftypes::HighwayClass::Undefined, ()); + bool const isLink = ftypes::IsLinkChecker::Instance()(ft); + double angle = 0; if (inEdge.GetFeatureId().m_mwmId == edge.GetFeatureId().m_mwmId) @@ -281,11 +283,12 @@ void BicycleDirectionsEngine::GetSegmentRangeAndAdjacentEdges( // should not be used for turn generation. outgoingTurns.isCandidatesAngleValid = false; } - outgoingTurns.candidates.emplace_back(angle, ConvertEdgeToSegment(*m_numMwmIds, edge), highwayClass); + outgoingTurns.candidates.emplace_back(angle, ConvertEdgeToSegment(*m_numMwmIds, edge), + highwayClass, isLink); } if (outgoingTurns.isCandidatesAngleValid) - sort(outgoingTurns.candidates.begin(), outgoingTurns.candidates.end(), my::LessBy(&TurnCandidate::angle)); + sort(outgoingTurns.candidates.begin(), outgoingTurns.candidates.end(), my::LessBy(&TurnCandidate::m_angle)); } void BicycleDirectionsEngine::GetEdges(RoadGraphBase const & graph, Junction const & currJunction, diff --git a/routing/routing_integration_tests/turn_test.cpp b/routing/routing_integration_tests/turn_test.cpp index 54ed125ee8..bfbe6245f7 100644 --- a/routing/routing_integration_tests/turn_test.cpp +++ b/routing/routing_integration_tests/turn_test.cpp @@ -583,8 +583,7 @@ UNIT_TEST(NetherlandsGorinchemBridgeTest) IRouter::ResultCode const result = routeResult.second; TEST_EQUAL(result, IRouter::NoError, ()); - integration::TestTurnCount(route, 1 /* expectedTurnCount */); - integration::GetNthTurn(route, 0).TestValid().TestDirection(CarDirection::TurnSlightLeft); + integration::TestTurnCount(route, 0 /* expectedTurnCount */); } UNIT_TEST(RussiaVoronigProspTrudaTest) @@ -621,6 +620,24 @@ UNIT_TEST(GermanyFrankfurtAirportTest) integration::GetNthTurn(route, 1).TestValid().TestDirection(CarDirection::TurnSlightRight); } + +UNIT_TEST(GermanyFrankfurtAirport2Test) +{ + TRouteResult const routeResult = + integration::CalculateRoute(integration::GetVehicleComponents(), + MercatorBounds::FromLatLon(50.03249, 8.50814), {0., 0.}, + MercatorBounds::FromLatLon(50.02079, 8.49445)); + + Route const & route = *routeResult.first; + IRouter::ResultCode const result = routeResult.second; + + TEST_EQUAL(result, IRouter::NoError, ()); + integration::TestTurnCount(route, 1 /* expectedTurnCount */); + + integration::GetNthTurn(route, 0).TestValid().TestDirection(CarDirection::TurnSlightRight); +} + + // Test on absence of unnecessary turn which may appear between two turns in the test. UNIT_TEST(RussiaKubinkaTest) { @@ -732,3 +749,18 @@ UNIT_TEST(RussiaMoscowMKADToSvobodaTest) integration::GetNthTurn(route, 0).TestValid().TestOneOfDirections( {CarDirection::TurnSlightRight, CarDirection::TurnRight}); } + +// Test that there's no turns if to follow MKAD. +UNIT_TEST(RussiaMoscowMKADTest) +{ + TRouteResult const routeResult = + integration::CalculateRoute(integration::GetVehicleComponents(), + MercatorBounds::FromLatLon(55.90394, 37.61034), {0., 0.}, + MercatorBounds::FromLatLon(55.77431, 37.36945)); + + Route const & route = *routeResult.first; + IRouter::ResultCode const result = routeResult.second; + + TEST_EQUAL(result, IRouter::NoError, ()); + integration::TestTurnCount(route, 0 /* expectedTurnCount */); +} diff --git a/routing/turn_candidate.hpp b/routing/turn_candidate.hpp index e06c863c70..dd83385534 100644 --- a/routing/turn_candidate.hpp +++ b/routing/turn_candidate.hpp @@ -21,33 +21,33 @@ namespace turns */ struct TurnCandidate { - /*! - * angle is an angle of the turn in degrees. It means angle is 180 minus - * an angle between the current edge and the edge of the candidate. A counterclockwise rotation. - * The current edge is an edge which belongs the route and located before the junction. - * angle belongs to the range [-180; 180]; - */ - double angle; - /*! - * |m_segment| is a first segment of a possible way from the junction. - */ + +/// angle is an angle of the turn in degrees. It means angle is 180 minus +/// an angle between the current edge and the edge of the candidate. A counterclockwise rotation. +/// The current edge is an edge which belongs the route and located before the junction. +/// angle belongs to the range [-180; 180]; + double m_angle; + +/// |m_segment| is a first segment of a possible way from the junction. Segment m_segment; - /*! - * \brief highwayClass field for the road class caching. Because feature reading is a long - * function. - */ - ftypes::HighwayClass highwayClass; - - TurnCandidate(double a, Segment const & segment, ftypes::HighwayClass c) - : angle(a), m_segment(segment), highwayClass(c) + +/// \brief highwayClass field for the road class caching. Because feature reading is a long +/// function. + ftypes::HighwayClass m_highwayClass; + +/// If |isLink| is true than the turn candidate is a link. + bool m_isLink; + + TurnCandidate(double a, Segment const & segment, ftypes::HighwayClass c, bool isLink) + : m_angle(a), m_segment(segment), m_highwayClass(c), m_isLink(isLink) { } bool IsAlmostEqual(TurnCandidate const & rhs) const { double constexpr kEpsilon = 0.01; - return my::AlmostEqualAbs(angle, rhs.angle, kEpsilon) && m_segment == rhs.m_segment && - highwayClass == rhs.highwayClass; + return my::AlmostEqualAbs(m_angle, rhs.m_angle, kEpsilon) && m_segment == rhs.m_segment && + m_highwayClass == rhs.m_highwayClass && m_isLink == rhs.m_isLink; } }; diff --git a/routing/turns_generator.cpp b/routing/turns_generator.cpp index 0e004f19e5..0daaffa7d1 100644 --- a/routing/turns_generator.cpp +++ b/routing/turns_generator.cpp @@ -57,7 +57,7 @@ bool KeepTurnByHighwayClass(CarDirection turn, TurnCandidates const & possibleTu { if (t.m_segment == firstOutgoingSegment) continue; - ftypes::HighwayClass const highwayClass = t.highwayClass; + ftypes::HighwayClass const highwayClass = t.m_highwayClass; if (static_cast(highwayClass) > static_cast(maxClassForPossibleTurns)) maxClassForPossibleTurns = highwayClass; } @@ -105,7 +105,7 @@ bool KeepRoundaboutTurnByHighwayClass(CarDirection turn, TurnCandidates const & { if (!validFirstOutgoingSeg || t.m_segment == firstOutgoingSegment) continue; - if (static_cast(t.highwayClass) != static_cast(ftypes::HighwayClass::Service)) + if (static_cast(t.m_highwayClass) != static_cast(ftypes::HighwayClass::Service)) return true; } return false; @@ -132,7 +132,7 @@ bool DiscardTurnByIngoingAndOutgoingEdges(CarDirection intermediateDirection, bo { for (auto const & c : turnCandidates.candidates) { - if (!IsGoStraightOrSlightTurn(IntermediateDirection(c.angle))) + if (!IsGoStraightOrSlightTurn(IntermediateDirection(c.m_angle))) { otherTurnCandidatesGoAlmostStraight = false; break; @@ -289,6 +289,17 @@ size_t GetOutgoingPointIndex(const size_t start, const size_t end, const size_t { return end > start ? start + i : start - i; } + +size_t GetLinkNumber(vector const & candidates) +{ + size_t candidateLinkNumber = 0; + for (auto const & c : candidates) + { + if (c.m_isLink) + ++candidateLinkNumber; + } + return candidateLinkNumber; +} } // namespace namespace routing @@ -707,15 +718,32 @@ void GetTurnDirection(IRoutingResult const & result, NumMwmIds const & numMwmIds return; } - auto const notSoCloseToTheTurnPoint = - GetPointForTurn(turnInfo.m_ingoing.m_path, junctionPoint, kNotSoCloseMaxPointsCount, - kNotSoCloseMinDistMeters, GetIngoingPointIndex); - - if (!KeepTurnByIngoingEdges(junctionPoint, notSoCloseToTheTurnPoint, outgoingPoint, hasMultiTurns, - nodes.candidates.size() + ingoingCount)) + if (IsGoStraightOrSlightTurn(turn.m_turn)) { - turn.m_turn = CarDirection::None; - return; + auto const notSoCloseToTheTurnPoint = + GetPointForTurn(turnInfo.m_ingoing.m_path, junctionPoint, kNotSoCloseMaxPointsCount, + kNotSoCloseMinDistMeters, GetIngoingPointIndex); + + // Removing a slight turn if there's only one way to leave the turn and there's no ingoing edges. + if (!KeepTurnByIngoingEdges(junctionPoint, notSoCloseToTheTurnPoint, outgoingPoint, hasMultiTurns, + nodes.candidates.size() + ingoingCount)) + { + turn.m_turn = CarDirection::None; + return; + } + + // Removing a slight turn if ingoing and outgoing edge are not links and all other + // possible ways out are links. + if (!turnInfo.m_ingoing.m_isLink && !turnInfo.m_outgoing.m_isLink && + turnInfo.m_ingoing.m_highwayClass == turnInfo.m_outgoing.m_highwayClass) + { + size_t const candidateLinkNumber = GetLinkNumber(nodes.candidates); + if (candidateLinkNumber + 1 == nodes.candidates.size()) + { + turn.m_turn = CarDirection::None; + return; + } + } } if (turn.m_turn == CarDirection::GoStraight) -- cgit v1.2.3