diff options
author | Vladimir Byko-Ianko <v.bykoianko@corp.mail.ru> | 2016-11-16 08:26:16 +0300 |
---|---|---|
committer | Vladimir Byko-Ianko <v.bykoianko@corp.mail.ru> | 2016-11-25 10:25:11 +0300 |
commit | 91ead6af9046745416b136c39561d1ba598f1b07 (patch) | |
tree | 6b8eff31b91ba709b6f943ea998256eea2181a2c /routing/routing_tests/restriction_test.cpp | |
parent | eb1c85bce50a6d98fa92b1cec278643b26b59946 (diff) |
Generating restriction, implementaion implementation using them at runtime§:wq, applying them on index graph and tests on it.
Diffstat (limited to 'routing/routing_tests/restriction_test.cpp')
-rw-r--r-- | routing/routing_tests/restriction_test.cpp | 622 |
1 files changed, 622 insertions, 0 deletions
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 |