diff options
author | Mikhail Gorbushin <m.gorbushin@corp.mail.ru> | 2019-05-23 14:03:00 +0300 |
---|---|---|
committer | Vladimir Byko-Ianko <bykoianko@gmail.com> | 2019-05-24 17:29:38 +0300 |
commit | c4fd55a3aa634e4bbaad2d34c641ae784aa7f8dc (patch) | |
tree | c2ceb1a6c0781d26ab16d876c49ad198f25d9b6f /routing | |
parent | 67af21aaa3a5c5d733cbe1d5774071264522cafd (diff) |
review fixes
Diffstat (limited to 'routing')
-rw-r--r-- | routing/index_router.cpp | 11 | ||||
-rw-r--r-- | routing/leaps_postprocessor.cpp | 1 | ||||
-rw-r--r-- | routing/leaps_postprocessor.hpp | 15 | ||||
-rw-r--r-- | routing/routing_tests/astar_algorithm_test.cpp | 1 |
4 files changed, 25 insertions, 3 deletions
diff --git a/routing/index_router.cpp b/routing/index_router.cpp index e609775819..c6da691b49 100644 --- a/routing/index_router.cpp +++ b/routing/index_router.cpp @@ -647,8 +647,15 @@ RouterResultCode IndexRouter::CalculateSubroute(Checkpoints const & checkpoints, if (leapsResult != RouterResultCode::NoError) return leapsResult; - LeapsPostProcessor leapsPostProcessor(subrouteWithoutPostprocessing, starter); - subroute = leapsPostProcessor.GetProcessedPath(); + if (mode == WorldGraphMode::LeapsOnly) + { + LeapsPostProcessor leapsPostProcessor(subrouteWithoutPostprocessing, starter); + subroute = leapsPostProcessor.GetProcessedPath(); + } + else + { + subroute = move(subrouteWithoutPostprocessing); + } } LOG(LINFO, ("Time for routing in mode:", starter.GetGraph().GetMode(), "is", diff --git a/routing/leaps_postprocessor.cpp b/routing/leaps_postprocessor.cpp index d57d012574..9401cde9c9 100644 --- a/routing/leaps_postprocessor.cpp +++ b/routing/leaps_postprocessor.cpp @@ -8,7 +8,6 @@ #include <algorithm> #include <iterator> #include <sstream> -#include <string> #include <utility> namespace diff --git a/routing/leaps_postprocessor.hpp b/routing/leaps_postprocessor.hpp index 3cd57523ef..b5a9ed0a36 100644 --- a/routing/leaps_postprocessor.hpp +++ b/routing/leaps_postprocessor.hpp @@ -15,6 +15,21 @@ namespace routing { +/// \brief After LeapsOnly mode we can have Loops in the path, like this: +/// Path through features: {f0, f1, ..., f9}. +/// *-f0->*-f1->*-f2->*-f3-> * -f6->*-f7->*-f8->*-f9-> +/// | ↑ +/// f4 f5 +/// ↓ | +/// * <------- intermediate point. +/// +/// As you can see, we can go from f3 to f6 but because of heuristic searching of intermediate +/// points in LeapsOnly routing algorithm, we build route through this point and received next path: +/// {..., f3, f4, f5, f6, ... } - this is Loop. +/// So next class provides local optimization and relax such paths: +/// (... f3 -> f4 -> f5 -> f6 ...) to (... f3 -> f6 ...). +/// +/// Works for: O(N). Where N it is path's length. class LeapsPostProcessor { public: diff --git a/routing/routing_tests/astar_algorithm_test.cpp b/routing/routing_tests/astar_algorithm_test.cpp index ef9bd802f0..3c3b73a9db 100644 --- a/routing/routing_tests/astar_algorithm_test.cpp +++ b/routing/routing_tests/astar_algorithm_test.cpp @@ -6,6 +6,7 @@ #include "routing/routing_tests/routing_algorithm.hpp" +#include <cstdint> #include <map> #include <utility> #include <vector> |