diff options
Diffstat (limited to 'routing/routing_tests')
| -rw-r--r-- | routing/routing_tests/index_graph_test.cpp | 71 | ||||
| -rw-r--r-- | routing/routing_tests/index_graph_tools.cpp | 84 | ||||
| -rw-r--r-- | routing/routing_tests/index_graph_tools.hpp | 46 | ||||
| -rw-r--r-- | routing/routing_tests/restriction_test.cpp | 622 | ||||
| -rw-r--r-- | routing/routing_tests/routing_tests.pro | 3 |
5 files changed, 765 insertions, 61 deletions
diff --git a/routing/routing_tests/index_graph_test.cpp b/routing/routing_tests/index_graph_test.cpp index 3458b7cd8e..da2ff816cf 100644 --- a/routing/routing_tests/index_graph_test.cpp +++ b/routing/routing_tests/index_graph_test.cpp @@ -1,5 +1,7 @@ #include "testing/testing.hpp" +#include "routing/routing_tests/index_graph_tools.hpp" + #include "routing/base/astar_algorithm.hpp" #include "routing/car_model.hpp" #include "routing/edge_estimator.hpp" @@ -18,75 +20,20 @@ namespace { using namespace routing; - -class TestGeometryLoader final : public GeometryLoader -{ -public: - // GeometryLoader overrides: - void Load(uint32_t featureId, RoadGeometry & road) const override; - - void AddRoad(uint32_t featureId, bool oneWay, RoadGeometry::Points const & points); - -private: - unordered_map<uint32_t, RoadGeometry> m_roads; -}; - -void TestGeometryLoader::Load(uint32_t featureId, RoadGeometry & road) const -{ - auto it = m_roads.find(featureId); - if (it == m_roads.cend()) - return; - - road = it->second; -} - -void TestGeometryLoader::AddRoad(uint32_t featureId, bool oneWay, - RoadGeometry::Points const & points) -{ - auto it = m_roads.find(featureId); - if (it != m_roads.end()) - { - ASSERT(false, ("Already contains feature", featureId)); - return; - } - - m_roads[featureId] = RoadGeometry(oneWay, 1.0 /* speed */, points); -} - -Joint MakeJoint(vector<RoadPoint> const & points) -{ - Joint joint; - for (auto const & point : points) - joint.AddPoint(point); - - return joint; -} - -shared_ptr<EdgeEstimator> CreateEstimator() -{ - return EdgeEstimator::CreateForCar(*make_shared<CarModelFactory>()->GetVehicleModel()); -} +using namespace routing_test; void TestRoute(IndexGraph const & graph, RoadPoint const & start, RoadPoint const & finish, size_t expectedLength, vector<RoadPoint> const * expectedRoute = nullptr) { - LOG(LINFO, ("Test route", start.GetFeatureId(), ",", start.GetPointId(), "=>", - finish.GetFeatureId(), ",", finish.GetPointId())); - - AStarAlgorithm<IndexGraphStarter> algorithm; - RoutingResult<Joint::Id> routingResult; - + vector<RoadPoint> route; IndexGraphStarter starter(graph, start, finish); - auto const resultCode = algorithm.FindPath(starter, starter.GetStartJoint(), - starter.GetFinishJoint(), routingResult, {}, {}); - TEST_EQUAL(resultCode, AStarAlgorithm<IndexGraphStarter>::Result::OK, ()); + AStarAlgorithm<IndexGraphStarter>::Result const resultCode = CalculateRoute(starter, route); - vector<RoadPoint> roadPoints; - starter.RedressRoute(routingResult.path, roadPoints); - TEST_EQUAL(roadPoints.size(), expectedLength, ()); + TEST_EQUAL(resultCode, AStarAlgorithm<IndexGraphStarter>::Result::OK, ()); + TEST_EQUAL(route.size(), expectedLength, ()); if (expectedRoute != nullptr) - TEST_EQUAL(roadPoints, *expectedRoute, ()); + TEST_EQUAL(route, *expectedRoute, ()); } void TestEdges(IndexGraph const & graph, Joint::Id jointId, @@ -244,6 +191,7 @@ UNIT_TEST(FindPathManhattan) street.emplace_back(static_cast<double>(i), static_cast<double>(j)); avenue.emplace_back(static_cast<double>(j), static_cast<double>(i)); } + loader->AddRoad(i, false, street); loader->AddRoad(i + kCitySize, false, avenue); } @@ -256,6 +204,7 @@ UNIT_TEST(FindPathManhattan) for (uint32_t j = 0; j < kCitySize; ++j) joints.emplace_back(MakeJoint({{i, j}, {j + kCitySize, i}})); } + graph.Import(joints); for (uint32_t startY = 0; startY < kCitySize; ++startY) diff --git a/routing/routing_tests/index_graph_tools.cpp b/routing/routing_tests/index_graph_tools.cpp new file mode 100644 index 0000000000..eba158a256 --- /dev/null +++ b/routing/routing_tests/index_graph_tools.cpp @@ -0,0 +1,84 @@ +#include "routing/routing_tests/index_graph_tools.hpp" + +#include "testing/testing.hpp" + +#include "routing/car_model.hpp" + +namespace routing_test +{ +using namespace routing; + +void TestGeometryLoader::Load(uint32_t featureId, RoadGeometry & road) const +{ + auto it = m_roads.find(featureId); + if (it == m_roads.cend()) + return; + + road = it->second; +} + +void TestGeometryLoader::AddRoad(uint32_t featureId, bool oneWay, + RoadGeometry::Points const & points) +{ + auto it = m_roads.find(featureId); + if (it != m_roads.end()) + { + ASSERT(false, ("Already contains feature", featureId)); + return; + } + + m_roads[featureId] = RoadGeometry(oneWay, 1.0 /* speed */, points); +} + +Joint MakeJoint(vector<RoadPoint> const & points) +{ + Joint joint; + for (auto const & point : points) + joint.AddPoint(point); + + return joint; +} + +shared_ptr<EdgeEstimator> CreateEstimator() +{ + return EdgeEstimator::CreateForCar(*make_shared<CarModelFactory>()->GetVehicleModel()); +} + +AStarAlgorithm<IndexGraphStarter>::Result CalculateRoute(IndexGraphStarter const & starter, + vector<RoadPoint> & roadPoints) +{ + AStarAlgorithm<IndexGraphStarter> algorithm; + RoutingResult<Joint::Id> routingResult; + AStarAlgorithm<IndexGraphStarter>::Result const resultCode = algorithm.FindPath( + starter, starter.GetStartJoint(), starter.GetFinishJoint(), routingResult, {}, {}); + + starter.RedressRoute(routingResult.path, roadPoints); + return resultCode; +} + +void TestRouteSegments(IndexGraphStarter const & starter, + AStarAlgorithm<IndexGraphStarter>::Result expectedRouteResult, + vector<RoadPoint> const & expectedRoute) +{ + vector<RoadPoint> route; + AStarAlgorithm<IndexGraphStarter>::Result const resultCode = CalculateRoute(starter, route); + TEST_EQUAL(resultCode, expectedRouteResult, ()); + TEST_EQUAL(route, expectedRoute, ()); +} + +void TestRouteGeometry(IndexGraphStarter const & starter, + AStarAlgorithm<IndexGraphStarter>::Result expectedRouteResult, + vector<m2::PointD> const & expectedRouteGeom) +{ + vector<RoadPoint> route; + AStarAlgorithm<IndexGraphStarter>::Result const resultCode = CalculateRoute(starter, route); + TEST_EQUAL(resultCode, expectedRouteResult, ()); + TEST_EQUAL(route.size(), expectedRouteGeom.size(), ()); + for (size_t i = 0; i < route.size(); ++i) + { + RoadGeometry roadGeom = starter.GetGraph().GetRoad(route[i].GetFeatureId()); + CHECK_LESS(route[i].GetPointId(), roadGeom.GetPointsCount(), ()); + TEST_EQUAL(expectedRouteGeom[i], roadGeom.GetPoint(route[i].GetPointId()), ()); + } +} +} // namespace routing_test diff --git a/routing/routing_tests/index_graph_tools.hpp b/routing/routing_tests/index_graph_tools.hpp new file mode 100644 index 0000000000..7a5482430f --- /dev/null +++ b/routing/routing_tests/index_graph_tools.hpp @@ -0,0 +1,46 @@ +#pragma once + +#include "routing/edge_estimator.hpp" +#include "routing/index_graph.hpp" +#include "routing/index_graph_starter.hpp" +#include "routing/road_point.hpp" + +#include "routing/base/astar_algorithm.hpp" + +#include "geometry/point2d.hpp" + +#include "std/algorithm.hpp" +#include "std/shared_ptr.hpp" +#include "std/unique_ptr.hpp" +#include "std/unordered_map.hpp" +#include "std/vector.hpp" + +namespace routing_test +{ +class TestGeometryLoader final : public routing::GeometryLoader +{ +public: + // GeometryLoader overrides: + void Load(uint32_t featureId, routing::RoadGeometry & road) const override; + + void AddRoad(uint32_t featureId, bool oneWay, routing::RoadGeometry::Points const & points); + +private: + unordered_map<uint32_t, routing::RoadGeometry> m_roads; +}; + +routing::Joint MakeJoint(vector<routing::RoadPoint> const & points); + +shared_ptr<routing::EdgeEstimator> CreateEstimator(); + +routing::AStarAlgorithm<routing::IndexGraphStarter>::Result CalculateRoute( + routing::IndexGraphStarter const & graph, vector<routing::RoadPoint> & roadPoints); + +void TestRouteSegments(routing::IndexGraphStarter const & starter, + routing::AStarAlgorithm<routing::IndexGraphStarter>::Result expectedRouteResult, + vector<routing::RoadPoint> const & expectedRoute); + +void TestRouteGeometry(routing::IndexGraphStarter const & starter, + routing::AStarAlgorithm<routing::IndexGraphStarter>::Result expectedRouteResult, + vector<m2::PointD> const & expectedRouteGeom); +} // namespace routing_test diff --git a/routing/routing_tests/restriction_test.cpp b/routing/routing_tests/restriction_test.cpp new file mode 100644 index 0000000000..895481763e --- /dev/null +++ b/routing/routing_tests/restriction_test.cpp @@ -0,0 +1,622 @@ +#include "testing/testing.hpp" + +#include "routing/routing_tests/index_graph_tools.hpp" + +#include "routing/car_model.hpp" + +#include "routing/geometry.hpp" +#include "geometry/point2d.hpp" + +#include "std/unique_ptr.hpp" +#include "std/vector.hpp" + +namespace +{ +using namespace routing; +using namespace routing_test; + +void TestRoutes(vector<RoadPoint> const & starts, + vector<RoadPoint> const & finishes, + vector<vector<RoadPoint>> const & expectedRoutes, + IndexGraph & graph) +{ + CHECK_EQUAL(starts.size(), expectedRoutes.size(), ()); + CHECK_EQUAL(finishes.size(), expectedRoutes.size(), ()); + + for (size_t i = 0; i < expectedRoutes.size(); ++i) + { + IndexGraphStarter starter(graph, starts[i], finishes[i]); + TestRouteSegments(starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedRoutes[i]); + } +} + +void EdgeTest(Joint::Id vertex, size_t expectedIntgoingNum, size_t expectedOutgoingNum, + IndexGraph & graph) +{ + vector<IndexGraphStarter::TEdgeType> ingoing; + graph.GetEdgesList(vertex, false /* is outgoing */, ingoing); + TEST_EQUAL(ingoing.size(), expectedIntgoingNum, ()); + + vector<IndexGraphStarter::TEdgeType> outgoing; + graph.GetEdgesList(vertex, true /* is outgoing */, outgoing); + TEST_EQUAL(outgoing.size(), expectedOutgoingNum, ()); +} + +// Finish +// 2 * +// ^ ↖ +// | F1 +// | ↖ +// 1 | * +// F0 ↖ +// | F2 +// | ↖ +// 0 *<--F3---<--F3---* Start +// 0 1 2 +// Note. F0, F1 and F2 are one segment features. F3 is a two segments feature. +unique_ptr<IndexGraph> BuildTriangularGraph() +{ + auto const loader = []() + { + unique_ptr<TestGeometryLoader> loader = make_unique<TestGeometryLoader>(); + loader->AddRoad(0 /* featureId */, true /* oneWay */, buffer_vector<m2::PointD, 32>( + {{0.0, 0.0}, {0.0, 2.0}})); + loader->AddRoad(1 /* featureId */, true /* oneWay */, buffer_vector<m2::PointD, 32>( + {{1.0, 1.0}, {0.0, 2.0}})); + loader->AddRoad(2 /* featureId */, true /* oneWay */, buffer_vector<m2::PointD, 32>( + {{0.0, 2.0}, {1.0, 1.0}})); + loader->AddRoad(3 /* featureId */, true /* oneWay */, buffer_vector<m2::PointD, 32>( + {{2.0, 0.0}, {1.0, 0.0}, {0.0, 0.0}})); + return loader; + }; + + vector<Joint> const joints = {MakeJoint({{2, 0}, {3, 0}}), /* joint at point (2, 0) */ + MakeJoint({{3, 2}, {0, 0}}), /* joint at point (0, 0) */ + MakeJoint({{2, 1}, {1, 0}}), /* joint at point (1, 1) */ + MakeJoint({{0, 1}, {1, 1}}) /* joint at point (0, 2) */ + }; + + unique_ptr<IndexGraph> graph = make_unique<IndexGraph>(loader(), CreateEstimator()); + graph->Import(joints); + return graph; +} + +// Route through triangular graph without any restrictions. +UNIT_TEST(TriangularGraph) +{ + unique_ptr<IndexGraph> graph = BuildTriangularGraph(); + IndexGraphStarter starter(*graph, RoadPoint(2, 0) /* start */, RoadPoint(1, 1) /* finish */); + vector<RoadPoint> const expectedRoute = {{2 /* feature id */, 0 /* seg id */}, + {2, 1}, {1, 1}}; + TestRouteSegments(starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedRoute); +} + +// Route through triangular graph with feature 2 disabled. +UNIT_TEST(TriangularGraph_DisableF2) +{ + unique_ptr<IndexGraph> graph = BuildTriangularGraph(); + graph->DisableEdge(graph->GetJointIdForTesting({2 /* feature id */, 0 /* point id */}), + graph->GetJointIdForTesting({2, 1})); + + IndexGraphStarter starter(*graph, RoadPoint(2, 0) /* start */, RoadPoint(1, 1) /* finish */); + vector<RoadPoint> const expectedRouteOneEdgeRemoved = {{3 /* feature id */, 0 /* seg id */}, + {3, 1}, {3, 2}, {0, 1}}; + TestRouteSegments(starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedRouteOneEdgeRemoved); +} + +// Route through triangular graph with restriction type no from feature 2 to feature 1. +UNIT_TEST(TriangularGraph_RestrictionNoF2F1) +{ + unique_ptr<IndexGraph> graph = BuildTriangularGraph(); + graph->ApplyRestrictionNo({2 /* feature id */, 1 /* seg id */}, {1, 0}, + graph->GetJointIdForTesting({1, 0})); + + IndexGraphStarter starter(*graph, RoadPoint(2, 0) /* start */, RoadPoint(1, 1) /* finish */); + vector<RoadPoint> const expectedRouteRestrictionF2F1No = {{3 /* feature id */, 0 /* seg id */}, + {3, 1}, {3, 2}, {0, 1}}; + TestRouteSegments(starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, + expectedRouteRestrictionF2F1No); +} + +// Finish +// 2 * +// ^ ↖ +// | ↖ +// | ↖ +// 1 | Fake adding one link feature +// F0 ↖ +// | ↖ +// | ↖ +// 0 *<--F1---<--F1--* Start +// 0 1 2 +// Note. F1 is a two setments feature. The others are one setment ones. +unique_ptr<IndexGraph> BuildCornerGraph() +{ + auto const loader = []() + { + unique_ptr<TestGeometryLoader> loader = make_unique<TestGeometryLoader>(); + loader->AddRoad(0 /* feature id */, true /* oneWay */, buffer_vector<m2::PointD, 32>( + {{0.0, 0.0}, {0.0, 2.0}})); + loader->AddRoad(1 /* feature id */, true /* oneWay */, buffer_vector<m2::PointD, 32>( + {{2.0, 0.0}, {1.0, 0.0}, {0.0, 0.0}})); + return loader; + }; + + vector<Joint> const joints = + {MakeJoint({{1 /* feature id */, 2 /* point id */}, {0, 0}}), /* joint at point (0, 0) */}; + + unique_ptr<IndexGraph> graph = make_unique<IndexGraph>(loader(), CreateEstimator()); + graph->Import(joints); + graph->InsertJoint({1 /* feature id */, 0 /* point id */}); // Start joint. + graph->InsertJoint({0 /* feature id */, 1 /* point id */}); // Finish joint. + return graph; +} + +// Route through corner graph without any restrictions. +UNIT_TEST(CornerGraph) +{ + unique_ptr<IndexGraph> graph = BuildCornerGraph(); + + // Route along F1 and F0. + IndexGraphStarter starter(*graph, RoadPoint(1, 0) /* start */, RoadPoint(0, 1) /* finish */); + vector<RoadPoint> const expectedRoute = {{1 /* feature id */, 0 /* point id */}, + {1, 1}, {1, 2}, {0, 1}}; + TestRouteSegments(starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedRoute); +} + +// Generate geometry based on feature 1 of corner graph. +UNIT_TEST(CornerGraph_CreateFakeFeature1Geometry) +{ + unique_ptr<IndexGraph> graph = BuildCornerGraph(); + + vector<vector<RoadPoint>> oneEdgeConnectionPaths; + graph->GetConnectionPaths(graph->GetJointIdForTesting({1 /* feature id */, 0 /* point id */}), + graph->GetJointIdForTesting({1, 2}), oneEdgeConnectionPaths); + TEST_EQUAL(oneEdgeConnectionPaths.size(), 1, ()); + + vector<RoadPoint> const expectedDirectOrder = {{1, 0}, {1, 1}, {1, 2}}; + TEST_EQUAL(oneEdgeConnectionPaths[0], expectedDirectOrder, ()); + RoadGeometry geometryDirect; + graph->CreateFakeFeatureGeometry(oneEdgeConnectionPaths[0], geometryDirect); + RoadGeometry expectedGeomentryDirect(true /* one way */, 1.0 /* speed */, + buffer_vector<m2::PointD, 32>({{2.0, 0.0}, {1.0, 0.0}, + {0.0, 0.0}})); + TEST_EQUAL(geometryDirect, expectedGeomentryDirect, ()); +} + +// Generate geometry based on reversed feature 1 of corner graph. +UNIT_TEST(CornerGraph_CreateFakeReversedFeature1Geometry) +{ + unique_ptr<IndexGraph> graph = BuildCornerGraph(); + + vector<vector<RoadPoint>> oneEdgeConnectionPaths; + graph->GetConnectionPaths(graph->GetJointIdForTesting({1 /* feature id */, 2 /* point id */}), + graph->GetJointIdForTesting({1, 0}), oneEdgeConnectionPaths); + TEST_EQUAL(oneEdgeConnectionPaths.size(), 1, ()); + + vector<RoadPoint> const expectedBackOrder = {{1, 2}, {1, 1}, {1, 0}}; + TEST_EQUAL(oneEdgeConnectionPaths[0], expectedBackOrder, ()); + RoadGeometry geometryBack; + graph->CreateFakeFeatureGeometry(oneEdgeConnectionPaths[0], geometryBack); + RoadGeometry expectedGeomentryBack(true /* one way */, 1.0 /* speed */, + buffer_vector<m2::PointD, 32>({{0.0, 0.0}, {1.0, 0.0}, + {2.0, 0.0}})); + TEST_EQUAL(geometryBack, expectedGeomentryBack, ()); +} + +// Route through corner graph with adding a fake edge. +UNIT_TEST(CornerGraph_AddFakeFeature) +{ + RoadPoint const kStart(1, 0); + RoadPoint const kFinish(0, 1); + unique_ptr<IndexGraph> graph = BuildCornerGraph(); + + graph->AddFakeFeature(graph->GetJointIdForTesting(kStart), graph->GetJointIdForTesting(kFinish), + {kStart, kFinish} /* geometrySource */); + + IndexGraphStarter starter(*graph, kStart, kFinish); + vector<RoadPoint> const expectedRouteByFakeFeature = {{IndexGraph::kStartFakeFeatureIds, 0 /* seg id */}, + {IndexGraph::kStartFakeFeatureIds, 1 /* seg id */}}; + TestRouteSegments(starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedRouteByFakeFeature); +} + +// Finish 2 Finish 1 Finish 0 +// 2 *<---F5----*<---F6---* +// ^ ↖ ^ ↖ ^ +// | Fake-1 | Fake-0 | +// | ↖ F1 ↖ F2 +// | ↖ | ↖ | +// 1 F0 * * +// | ^ ↖ ^ +// | F1 Fake-2 F2 +// | | ↖ | +// 0 *<----F4---*<---F3----* Start +// 0 1 2 +// Note. F1 and F2 are two segments features. The others are one segment ones. +unique_ptr<IndexGraph> BuildTwoSquaresGraph() +{ + auto const loader = []() + { + unique_ptr<TestGeometryLoader> loader = make_unique<TestGeometryLoader>(); + loader->AddRoad(0 /* feature id */, true /* oneWay */, buffer_vector<m2::PointD, 32>( + {{0.0, 0.0}, {0.0, 2.0}})); + loader->AddRoad(1 /* feature id */, true /* oneWay */, buffer_vector<m2::PointD, 32>( + {{1.0, 0.0}, {1.0, 1.0}, {1.0, 2.0}})); + loader->AddRoad(2 /* feature id */, true /* oneWay */, buffer_vector<m2::PointD, 32>( + {{2.0, 0.0}, {2.0, 1.0}, {2.0, 2.0}})); + loader->AddRoad(3 /* feature id */, true /* oneWay */, buffer_vector<m2::PointD, 32>( + {{2.0, 0.0}, {1.0, 0.0}})); + loader->AddRoad(4 /* feature id */, true /* oneWay */, buffer_vector<m2::PointD, 32>( + {{1.0, 0.0}, {0.0, 0.0}})); + loader->AddRoad(5 /* feature id */, true /* oneWay */, buffer_vector<m2::PointD, 32>( + {{1.0, 2.0}, {0.0, 2.0}})); + loader->AddRoad(6 /* feature id */, true /* oneWay */, buffer_vector<m2::PointD, 32>( + {{2.0, 2.0}, {1.0, 2.0}})); + return loader; + }; + + vector<Joint> const joints = { + MakeJoint({{4 /* featureId */, 1 /* pointId */}, {0, 0}}), /* joint at point (0, 0) */ + MakeJoint({{0, 1}, {5, 1}}), /* joint at point (0, 2) */ + MakeJoint({{4, 0}, {1, 0}, {3, 1}}), /* joint at point (1, 0) */ + MakeJoint({{5, 0}, {1, 2}, {6, 1}}), /* joint at point (1, 2) */ + MakeJoint({{3, 0}, {2, 0}}), /* joint at point (2, 0) */ + MakeJoint({{2, 2}, {6, 0}}), /* joint at point (2, 2) */ + }; + + unique_ptr<IndexGraph> graph = make_unique<IndexGraph>(loader(), CreateEstimator()); + graph->Import(joints); + return graph; +} + +// Route through two squares graph without any restrictions. +UNIT_TEST(TwoSquaresGraph) +{ + unique_ptr<IndexGraph> graph = BuildTwoSquaresGraph(); + + vector<RoadPoint> const starts = {{2 /* feature id */, 0 /* point id */}, {2, 0}, {2, 0}}; + vector<RoadPoint> const finishes = {{6 /* feature id */, 0 /* point id */}, {6, 1}, {5, 1}}; + vector<RoadPoint> const expectedRoute0 = {{2 /* feature id */, 0 /* point id */}, + {2, 1}, {2, 2}}; + vector<RoadPoint> const expectedRoute1 = {{2 /* feature id */, 0 /* point id */}, + {2, 1}, {2, 2}, {6, 1}}; + vector<RoadPoint> const expectedRoute2 = {{2 /* feature id */, 0 /* point id */}, + {2, 1}, {2, 2}, {6, 1}, {5, 1}}; + + TestRoutes(starts, finishes, {expectedRoute0, expectedRoute1, expectedRoute2}, *graph); +} + +// Route through two squares graph with adding a Fake-0 edge. +UNIT_TEST(TwoSquaresGraph_AddFakeFeatureZero) +{ + unique_ptr<IndexGraph> graph = BuildTwoSquaresGraph(); + graph->AddFakeFeature(graph->InsertJoint({2 /* feature id */, 1 /* point id */}), + graph->GetJointIdForTesting({6 /* feature id */, 1 /* point id */}), + {{2, 1}, {6, 1}} /* geometrySource */); + + vector<RoadPoint> const starts = {{2 /* feature id */, 0 /* point id */}, {2, 0}, {2, 0}}; + vector<RoadPoint> const finishes = {{6 /* feature id */, 0 /* point id */}, {6, 1}, {5, 1}}; + vector<RoadPoint> const expectedRoute0 = {{2 /* feature id */, 0 /* point id */}, + {2, 1}, {2, 2}}; + vector<RoadPoint> const expectedRoute1 = {{2 /* feature id */, 0 /* point id */}, + {2, 1}, {IndexGraph::kStartFakeFeatureIds, 1}}; + vector<RoadPoint> const expectedRoute2 = {{2 /* feature id */, 0 /* point id */}, + {2, 1}, {IndexGraph::kStartFakeFeatureIds, 1}, {5, 1}}; + + TestRoutes(starts, finishes, {expectedRoute0, expectedRoute1, expectedRoute2}, *graph); +} + +// Route through two squares graph with adding a Fake-0, Fake-1 and Fake-2 edge. +UNIT_TEST(TwoSquaresGraph_AddFakeFeatureZeroOneTwo) +{ + unique_ptr<IndexGraph> graph = BuildTwoSquaresGraph(); + // Adding features: Fake 0, Fake 1 and Fake 2. + graph->AddFakeFeature(graph->InsertJoint({2 /* feature id */, 1 /* point id */}), + graph->GetJointIdForTesting({6 /* feature id */, 1 /* point id */}), + {{2, 1}, {6, 1}} /* geometrySource */); + graph->AddFakeFeature(graph->InsertJoint({1 /* feature id */, 1 /* point id */}), + graph->GetJointIdForTesting({5 /* feature id */, 1 /* point id */}), + {{1, 1}, {5, 1}} /* geometrySource */); + graph->AddFakeFeature(graph->GetJointIdForTesting({2 /* feature id */, 0 /* point id */}), + graph->GetJointIdForTesting({1 /* feature id */, 1 /* point id */}), + {{2, 0}, {1, 1}} /* geometrySource */); + + vector<RoadPoint> const starts = {{2 /* feature id */, 0 /* point id */}, {2, 0}, {2, 0}}; + vector<RoadPoint> const finishes = {{6 /* feature id */, 0 /* point id */}, {6, 1}, {5, 1}}; + vector<RoadPoint> const expectedRoute0 = {{2 /* feature id */, 0 /* point id */}, + {2, 1}, {2, 2}}; + vector<RoadPoint> const expectedRoute1 = {{2 /* feature id */, 0 /* point id */}, + {2, 1}, {IndexGraph::kStartFakeFeatureIds, 1}}; + vector<RoadPoint> const expectedRoute2 = {{IndexGraph::kStartFakeFeatureIds + 2 /* Fake 2 */, 0}, + {IndexGraph::kStartFakeFeatureIds + 2 /* Fake 2 */, 1}, + {IndexGraph::kStartFakeFeatureIds + 1 /* Fake 1 */, 1}}; + TestRoutes(starts, finishes, {expectedRoute0, expectedRoute1, expectedRoute2}, *graph); + + // Disabling Fake-2 feature. + graph->DisableEdge(graph->GetJointIdForTesting({IndexGraph::kStartFakeFeatureIds + 2 /* Fake 2 */, 0}), + graph->GetJointIdForTesting({IndexGraph::kStartFakeFeatureIds + 2 /* Fake 2 */, 1})); + vector<RoadPoint> const expectedRoute2Disable2 = {{2 /* feature id */, 0 /* point id */}, + {2, 1}, {IndexGraph::kStartFakeFeatureIds, 1}, {5, 1}}; + TestRoutes(starts, finishes, {expectedRoute0, expectedRoute1, expectedRoute2Disable2}, *graph); +} + +// Finish +// 1 *-F4-*-F5-* +// | | +// F2 F3 +// | | +// 0 *---F1----*---F0---* Start +// 0 1 2 +// Note 1. All features are two-way. (It's possible to move along any direction of the features.) +// Note 2. Any feature contains of one segment. +unique_ptr<IndexGraph> BuildFlagGraph() +{ + auto const loader = []() + { + unique_ptr<TestGeometryLoader> loader = make_unique<TestGeometryLoader>(); + loader->AddRoad(0 /* feature id */, false /* one way */, buffer_vector<m2::PointD, 32>( + {{2.0, 0.0}, {1.0, 0.0}})); + loader->AddRoad(1 /* feature id */, false /* one way */, buffer_vector<m2::PointD, 32>( + {{1.0, 0.0}, {0.0, 0.0}})); + loader->AddRoad(2 /* feature id */, false /* one way */, buffer_vector<m2::PointD, 32>( + {{0.0, 0.0}, {0.0, 1.0}})); + loader->AddRoad(3 /* feature id */, false /* one way */, buffer_vector<m2::PointD, 32>( + {{1.0, 0.0}, {1.0, 1.0}})); + loader->AddRoad(4 /* feature id */, false /* one way */, buffer_vector<m2::PointD, 32>( + {{0.0, 1.0}, {0.5, 1.0}})); + loader->AddRoad(5 /* feature id */, false /* one way */, buffer_vector<m2::PointD, 32>( + {{0.5, 1.0}, {1.0, 1.0}})); + return loader; + }; + + vector<Joint> const joints = { + MakeJoint({{1 /* feature id */, 1 /* point id */}, {2, 0}}), /* joint at point (0, 0) */ + MakeJoint({{2, 1}, {4, 0}}), /* joint at point (0, 1) */ + MakeJoint({{4, 1}, {5, 0}}), /* joint at point (0.5, 1) */ + MakeJoint({{1, 0}, {3, 0}, {0, 1}}), /* joint at point (1, 0) */ + MakeJoint({{3, 1}, {5, 1}}), /* joint at point (1, 1) */ + }; + + unique_ptr<IndexGraph> graph = make_unique<IndexGraph>(loader(), CreateEstimator()); + graph->Import(joints); + // Note. It's necessary to insert start joint because the edge F0 is used + // for creating restrictions. + graph->InsertJoint({0 /* feature id */, 0 /* point id */}); // start + return graph; +} + +// @TODO(bykoianko) It's necessary to implement put several no restriction on the same junction +// ingoing edges of the same jucntion. For example test with flag graph with two restriction +// type no from F0 to F3 and form F0 to F1. + +// Route through flag graph without any restrictions. +UNIT_TEST(FlagGraph) +{ + unique_ptr<IndexGraph> graph = BuildFlagGraph(); + IndexGraphStarter starter(*graph, RoadPoint(0, 0) /* start */, RoadPoint(5, 0) /* finish */); + vector<m2::PointD> const expectedGeom = {{2 /* x */, 0 /* y */}, + {1, 0}, {1, 1}, {0.5, 1}}; + TestRouteGeometry(starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); +} + +// Route through flag graph with one restriciton (type no) from F0 to F3. +UNIT_TEST(FlagGraph_RestrictionF0F3No) +{ + unique_ptr<IndexGraph> graph = BuildFlagGraph(); + Joint::Id const restictionCenterId = graph->GetJointIdForTesting({0, 1}); + + // Testing outgoing and ingoing edge number near restriction joint. + EdgeTest(restictionCenterId, 3 /* expectedIntgoingNum */, 3 /* expectedOutgoingNum */, *graph); + graph->ApplyRestrictionNo({0 /* feature id */, 1 /* point id */}, {3 /* feature id */, 0 /* point id */}, + restictionCenterId); + EdgeTest(restictionCenterId, 2 /* expectedIntgoingNum */, 3 /* expectedOutgoingNum */, *graph); + + // Testing route building after adding the restriction. + IndexGraphStarter starter(*graph, RoadPoint(0, 0) /* start */, RoadPoint(5, 0) /* finish */); + vector<m2::PointD> const expectedGeom = {{2 /* x */, 0 /* y */}, + {1, 0}, {0, 0}, {0, 1}, {0.5, 1}}; + TestRouteGeometry(starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); +} + +// Route through flag graph with one restriciton (type only) from F0 to F1. +UNIT_TEST(FlagGraph_RestrictionF0F1Only) +{ + unique_ptr<IndexGraph> graph = BuildFlagGraph(); + Joint::Id const restictionCenterId = graph->GetJointIdForTesting({0, 1}); + graph->ApplyRestrictionOnly({0 /* feature id */, 1 /* point id */}, {1 /* feature id */, 0 /* point id */}, + restictionCenterId); + + IndexGraphStarter starter(*graph, RoadPoint(0, 0) /* start */, RoadPoint(5, 0) /* finish */); + vector<RoadPoint> const expectedRoute = {{IndexGraph::kStartFakeFeatureIds, 0 /* point id */}, + {IndexGraph::kStartFakeFeatureIds, 1}, + {IndexGraph::kStartFakeFeatureIds, 2}, + {2 /* feature id */, 1 /* point id */}, + {4, 1}}; + TestRouteSegments(starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedRoute); +} + +// 1 *-F4-*-F5-*---F6---* Finish +// | | +// F2 F3 +// | | +// 0 *---F1----*---F0---* Start +// 0 1 2 +// Note 1. All features are two-way. (It's possible to move along any direction of the features.) +// Note 2. Any feature contains of one segment. +unique_ptr<IndexGraph> BuildPosterGraph() +{ + auto loader = []() + { + unique_ptr<TestGeometryLoader> loader = make_unique<TestGeometryLoader>(); + loader->AddRoad(0 /* feature id */, false /* one way */, buffer_vector<m2::PointD, 32>( + {{2.0, 0.0}, {1.0, 0.0}})); + loader->AddRoad(1 /* feature id */, false /* one way */, buffer_vector<m2::PointD, 32>( + {{1.0, 0.0}, {0.0, 0.0}})); + loader->AddRoad(2 /* feature id */, false /* one way */, buffer_vector<m2::PointD, 32>( + {{0.0, 0.0}, {0.0, 1.0}})); + loader->AddRoad(3 /* feature id */, false /* one way */, buffer_vector<m2::PointD, 32>( + {{1.0, 0.0}, {1.0, 1.0}})); + loader->AddRoad(4 /* feature id */, false /* one way */, buffer_vector<m2::PointD, 32>( + {{0.0, 1.0}, {0.5, 1.0}})); + loader->AddRoad(5 /* feature id */, false /* one way */, buffer_vector<m2::PointD, 32>( + {{0.5, 1.0}, {1.0, 1.0}})); + loader->AddRoad(6 /* feature id */, false /* one way */, buffer_vector<m2::PointD, 32>( + {{1.0, 1.0}, {2.0, 1.0}})); + return loader; + }; + + vector<Joint> const joints = { + MakeJoint({{1 /* feature id */, 1 /* point id */}, {2, 0}}), /* joint at point (0, 0) */ + MakeJoint({{2, 1}, {4, 0}}), /* joint at point (0, 1) */ + MakeJoint({{4, 1}, {5, 0}}), /* joint at point (0.5, 1) */ + MakeJoint({{1, 0}, {3, 0}, {0, 1}}), /* joint at point (1, 0) */ + MakeJoint({{3, 1}, {5, 1}, {6, 0}}), /* joint at point (1, 1) */ + }; + + unique_ptr<IndexGraph> graph = make_unique<IndexGraph>(loader(), CreateEstimator()); + graph->Import(joints); + // Note. It's necessary to insert start and finish joints because the edge F0 is used + // for creating restrictions. + graph->InsertJoint({0 /* feature id */, 0 /* point id */}); // start + graph->InsertJoint({6 /* feature id */, 1 /* point id */}); // finish + + return graph; +} + +// Route through poster graph without any restrictions. +UNIT_TEST(PosterGraph) +{ + unique_ptr<IndexGraph> graph = BuildPosterGraph(); + IndexGraphStarter starter(*graph, RoadPoint(0, 0) /* start */, RoadPoint(6, 1) /* finish */); + vector<m2::PointD> const expectedGeom = {{2 /* x */, 0 /* y */}, + {1, 0}, {1, 1}, {2, 1}}; + + TestRouteGeometry(starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); +} + +// Route through poster graph with restrictions F0-F3 (type no). +UNIT_TEST(PosterGraph_RestrictionF0F3No) +{ + unique_ptr<IndexGraph> graph = BuildPosterGraph(); + Joint::Id const restictionCenterId = graph->GetJointIdForTesting({0, 1}); + + graph->ApplyRestrictionNo({0 /* feature id */, 1 /* point id */}, {3 /* feature id */, 0 /* point id */}, + restictionCenterId); + + IndexGraphStarter starter(*graph, RoadPoint(0, 0) /* start */, RoadPoint(6, 1) /* finish */); + vector<m2::PointD> const expectedGeom = {{2 /* x */, 0 /* y */}, + {1, 0}, {0, 0}, {0, 1}, {0.5, 1}, {1, 1}, {2, 1}}; + TestRouteGeometry(starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); +} + +// Route through poster graph with restrictions F0-F1 (type only). +UNIT_TEST(PosterGraph_RestrictionF0F1Only) +{ + unique_ptr<IndexGraph> graph = BuildPosterGraph(); + Joint::Id const restictionCenterId = graph->GetJointIdForTesting({0, 1}); + + graph->ApplyRestrictionOnly({0 /* feature id */, 1 /* point id */}, {1 /* feature id */, 0 /* point id */}, + restictionCenterId); + + IndexGraphStarter starter(*graph, RoadPoint(0, 0) /* start */, RoadPoint(6, 1) /* finish */); + vector<m2::PointD> const expectedGeom = {{2 /* x */, 0 /* y */}, + {1, 0}, {0, 0}, {0, 1}, {0.5, 1}, {1, 1}, {2, 1}}; + TestRouteGeometry(starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom); +} + +// 1 *--F1-->* +// ↗ ↘ +// F1 F1 +// ↗ ↘ +// Start 0 *---F0--->-------F0----->* Finish +// 0 1 2 3 +// Start +// Note. F0 is a two setments feature. F1 is a three segment one. +unique_ptr<IndexGraph> BuildTwoWayGraph() +{ + auto const loader = []() + { + unique_ptr<TestGeometryLoader> loader = make_unique<TestGeometryLoader>(); + loader->AddRoad(0 /* feature id */, true /* oneWay */, buffer_vector<m2::PointD, 32>( + {{0.0, 0.0}, {1.0, 0.0}, {3.0, 0}})); + loader->AddRoad(1 /* feature id */, true /* oneWay */, buffer_vector<m2::PointD, 32>( + {{0.0, 0.0}, {1.0, 1.0}, {2.0, 1.0}, {3.0, 0.0}})); + return loader; + }; + + vector<Joint> const joints = { + MakeJoint({{0 /* feature id */, 0 /* point id */}, {1, 0}}), /* joint at point (0, 0) */ + MakeJoint({{0 /* feature id */, 2 /* point id */}, {1, 3}})}; + + unique_ptr<IndexGraph> graph = make_unique<IndexGraph>(loader(), CreateEstimator()); + graph->Import(joints); + return graph; +} + +UNIT_TEST(TwoWay_GetSingleFeaturePaths) +{ + unique_ptr<IndexGraph> graph = BuildTwoWayGraph(); + vector<RoadPoint> singleFeaturePath; + + // Full feature 0. + graph->GetSingleFeaturePaths({0 /* feature id */, 0 /* point id */}, {0, 2}, singleFeaturePath); + vector<RoadPoint> const expectedF0 = {{0 /* feature id */, 0 /* point id */}, {0, 1}, {0, 2}}; + TEST_EQUAL(singleFeaturePath, expectedF0, ()); + + // Full feature 1. + graph->GetSingleFeaturePaths({1 /* feature id */, 0 /* point id */}, {1, 3}, singleFeaturePath); + vector<RoadPoint> const expectedF1 = {{1 /* feature id */, 0 /* point id */}, {1, 1}, + {1, 2}, {1, 3}}; + TEST_EQUAL(singleFeaturePath, expectedF1, ()); + + // Full feature 1 in reversed order. + graph->GetSingleFeaturePaths({1 /* feature id */, 3 /* point id */}, {1, 0}, singleFeaturePath); + vector<RoadPoint> const expectedReversedF1 = {{1 /* feature id */, 3 /* point id */}, {1, 2}, + {1, 1}, {1, 0}}; + TEST_EQUAL(singleFeaturePath, expectedReversedF1, ()); + + // Part of feature 0. + graph->GetSingleFeaturePaths({0 /* feature id */, 1 /* point id */}, {0, 2}, singleFeaturePath); + vector<RoadPoint> const expectedPartF0 = {{0 /* feature id */, 1 /* point id */}, {0, 2}}; + TEST_EQUAL(singleFeaturePath, expectedPartF0, ()); + + // Part of feature 1 in reversed order. + graph->GetSingleFeaturePaths({1 /* feature id */, 2 /* point id */}, {1, 1}, singleFeaturePath); + vector<RoadPoint> const expectedPartF1 = {{1 /* feature id */, 2 /* point id */}, {1, 1}}; + TEST_EQUAL(singleFeaturePath, expectedPartF1, ()); + + // Single point test. + graph->GetSingleFeaturePaths({0 /* feature id */, 0 /* point id */}, {0, 0}, singleFeaturePath); + vector<RoadPoint> const expectedSinglePoint = {{0 /* feature id */, 0 /* point id */}}; + TEST_EQUAL(singleFeaturePath, expectedSinglePoint, ()); +} + +UNIT_TEST(TwoWay_GetConnectionPaths) +{ + unique_ptr<IndexGraph> graph = BuildTwoWayGraph(); + vector<vector<RoadPoint>> connectionPaths; + + graph->GetConnectionPaths(graph->GetJointIdForTesting({1 /* feature id */, 0 /* point id */}), + graph->GetJointIdForTesting({0, 2}), connectionPaths); + vector<vector<RoadPoint>> const expectedConnectionPaths = { + {{0, 0}, {0, 1}, {0, 2}}, // feature 0 + {{1, 0}, {1, 1}, {1, 2}, {1, 3}}, // feature 1 + }; + sort(connectionPaths.begin(), connectionPaths.end()); + TEST_EQUAL(connectionPaths, expectedConnectionPaths, ()); +} + +UNIT_TEST(TwoWay_GetShortestConnectionPath) +{ + unique_ptr<IndexGraph> graph = BuildTwoWayGraph(); + vector<RoadPoint> shortestPath; + + graph->GetShortestConnectionPath(graph->GetJointIdForTesting({0 /* feature id */, 0 /* point id */}), + graph->GetJointIdForTesting({1, 3}), shortestPath); + vector<RoadPoint> const expectedShortestPath = { + {0, 0}, {0, 1}, {0, 2}, // feature 0 + }; + TEST_EQUAL(shortestPath, expectedShortestPath, ()); +} +} // namespace diff --git a/routing/routing_tests/routing_tests.pro b/routing/routing_tests/routing_tests.pro index 100399f067..b170fc5d4f 100644 --- a/routing/routing_tests/routing_tests.pro +++ b/routing/routing_tests/routing_tests.pro @@ -28,6 +28,7 @@ SOURCES += \ cross_routing_tests.cpp \ followed_polyline_test.cpp \ index_graph_test.cpp \ + index_graph_tools.cpp \ nearest_edge_finder_tests.cpp \ online_cross_fetcher_test.cpp \ osrm_router_test.cpp \ @@ -40,6 +41,8 @@ SOURCES += \ turns_sound_test.cpp \ turns_tts_text_tests.cpp \ vehicle_model_test.cpp \ + restriction_test.cpp \ HEADERS += \ + index_graph_tools.hpp \ road_graph_builder.hpp \ |