diff options
| -rw-r--r-- | routing/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | routing/fake_edges_container.hpp | 30 | ||||
| -rw-r--r-- | routing/index_graph_starter.cpp | 484 | ||||
| -rw-r--r-- | routing/index_graph_starter.hpp | 124 | ||||
| -rw-r--r-- | routing/index_road_graph.cpp | 23 | ||||
| -rw-r--r-- | routing/index_router.cpp | 74 | ||||
| -rw-r--r-- | routing/index_router.hpp | 7 | ||||
| -rw-r--r-- | routing/routing.pro | 1 | ||||
| -rw-r--r-- | routing/routing_tests/cumulative_restriction_test.cpp | 72 | ||||
| -rw-r--r-- | routing/routing_tests/index_graph_test.cpp | 114 | ||||
| -rw-r--r-- | routing/routing_tests/index_graph_tools.cpp | 8 | ||||
| -rw-r--r-- | routing/routing_tests/restriction_test.cpp | 2 | ||||
| -rw-r--r-- | xcode/routing/routing.xcodeproj/project.pbxproj | 4 |
13 files changed, 499 insertions, 445 deletions
diff --git a/routing/CMakeLists.txt b/routing/CMakeLists.txt index 9ba0a8ddc4..5e54c2e88e 100644 --- a/routing/CMakeLists.txt +++ b/routing/CMakeLists.txt @@ -42,6 +42,7 @@ set( directions_engine.hpp edge_estimator.cpp edge_estimator.hpp + fake_edges_container.hpp features_road_graph.cpp features_road_graph.hpp geometry.cpp diff --git a/routing/fake_edges_container.hpp b/routing/fake_edges_container.hpp new file mode 100644 index 0000000000..882e250232 --- /dev/null +++ b/routing/fake_edges_container.hpp @@ -0,0 +1,30 @@ +#pragma once + +#include "routing/index_graph_starter.hpp" + +#include <cstddef> +#include <cstdint> +#include <memory> +#include <utility> + +namespace routing +{ +class FakeEdgesContainer final +{ + friend class IndexGraphStarter; + +public: + FakeEdgesContainer(IndexGraphStarter && starter) + : m_finishId(starter.m_finishId) + , m_fake(std::move(starter.m_fake)) + { + } + + size_t GetNumFakeEdges() const { return m_fake.m_segmentToVertex.size(); } + +private: + // finish segment id + uint32_t m_finishId; + IndexGraphStarter::FakeGraph m_fake; +}; +} // namespace routing diff --git a/routing/index_graph_starter.cpp b/routing/index_graph_starter.cpp index 4bffc02ae2..0e4b0adcdf 100644 --- a/routing/index_graph_starter.cpp +++ b/routing/index_graph_starter.cpp @@ -1,161 +1,131 @@ #include "routing/index_graph_starter.hpp" +#include "routing/fake_edges_container.hpp" + #include "geometry/distance.hpp" +#include "base/math.hpp" +#include "base/stl_helpers.hpp" +#include "base/stl_iterator.hpp" + namespace { using namespace routing; using namespace std; -Segment InvertDirection(Segment const & segment) +Segment GetReverseSegment(Segment const & segment) { return Segment(segment.GetMwmId(), segment.GetFeatureId(), segment.GetSegmentIdx(), !segment.IsForward()); } -Junction InterpolateJunction(Segment const & segment, m2::PointD const & point, WorldGraph & graph) +Junction CalcProjectionToSegment(Segment const & segment, m2::PointD const & point, + WorldGraph & graph) { - Junction const & begin = graph.GetJunction(segment, false /* front */); - Junction const & end = graph.GetJunction(segment, true /* front */); - - m2::PointD const segmentDir = end.GetPoint() - begin.GetPoint(); - if (segmentDir.IsAlmostZero()) - return Junction(point, begin.GetAltitude()); - - m2::PointD const pointDir = point - begin.GetPoint(); - - double const ratio = m2::DotProduct(segmentDir, pointDir) / segmentDir.SquaredLength(); - if (ratio <= 0.0) - return Junction(point, begin.GetAltitude()); - - if (ratio >= 1.0) - return Junction(point, end.GetAltitude()); - - return Junction(point, static_cast<feature::TAltitude>( - (1.0 - ratio) * static_cast<double>(begin.GetAltitude()) + - ratio * (static_cast<double>(end.GetAltitude())))); + auto const & begin = graph.GetJunction(segment, false /* front */); + auto const & end = graph.GetJunction(segment, true /* front */); + m2::ProjectionToSection<m2::PointD> projection; + projection.SetBounds(begin.GetPoint(), end.GetPoint()); + auto projectedPoint = projection(point); + auto const distBeginToEnd = graph.GetEstimator().CalcLeapWeight(begin.GetPoint(), end.GetPoint()); + + double constexpr kEpsMeters = 2.0; + if (my::AlmostEqualAbs(distBeginToEnd, 0.0, kEpsMeters)) + return Junction(projectedPoint, begin.GetAltitude()); + + auto const distBeginToProjection = + graph.GetEstimator().CalcLeapWeight(begin.GetPoint(), projectedPoint); + auto const altitude = begin.GetAltitude() + (end.GetAltitude() - begin.GetAltitude()) * + distBeginToProjection / distBeginToEnd; + return Junction(projectedPoint, altitude); } -Junction CalcProjectionToSegment(Segment const & segment, Junction const & junction, - WorldGraph & graph) +template<typename K, typename V> +bool IsIntersectionEmpty(map<K, V> const & lhs, map<K, V> const & rhs) { - m2::ProjectionToSection<m2::PointD> projection; - projection.SetBounds(graph.GetPoint(segment, false /* front */), - graph.GetPoint(segment, true /* front */)); - return Junction(projection(junction.GetPoint()), junction.GetAltitude()); + auto const counter = set_intersection(lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), + CounterIterator(), my::LessBy(&pair<K, V>::first)); + return counter.GetCount() == 0; } } // namespace namespace routing { -void IndexGraphStarter::AddFakeVertex(Segment const & existentSegment, Segment const & newSegment, - FakeVertex const & newVertex, bool isOutgoing, - bool isPartOfReal, Segment const & realSegment) +// FakeGraph ------------------------------------------------------------------- +void IndexGraphStarter::FakeGraph::AddFakeVertex(Segment const & existentSegment, + Segment const & newSegment, + FakeVertex const & newVertex, bool isOutgoing, + bool isPartOfReal, Segment const & realSegment) { auto const & segmentFrom = isOutgoing ? existentSegment : newSegment; auto const & segmentTo = isOutgoing ? newSegment : existentSegment; - m_fake.m_outgoing[segmentFrom].insert(segmentTo); - m_fake.m_ingoing[segmentTo].insert(segmentFrom); - m_fake.m_segmentToVertex[newSegment] = newVertex; + m_outgoing[segmentFrom].insert(segmentTo); + m_ingoing[segmentTo].insert(segmentFrom); + m_segmentToVertex[newSegment] = newVertex; if (isPartOfReal) { - m_fake.m_realToFake[realSegment].insert(newSegment); - m_fake.m_fakeToReal[newSegment] = realSegment; + m_realToFake[realSegment].insert(newSegment); + m_fakeToReal[newSegment] = realSegment; } } -Segment IndexGraphStarter::GetSegment(FakeVertex const & vertex, uint32_t & newNumber) const +Segment IndexGraphStarter::FakeGraph::GetSegment(FakeVertex const & vertex, + uint32_t & newNumber) const { - for (auto const & v : m_fake.m_segmentToVertex) + for (auto const & kv : m_segmentToVertex) { - if (v.second == vertex) - return v.first; + if (kv.second == vertex) + return kv.first; } return GetFakeSegment(newNumber++); } -void IndexGraphStarter::AddEnding(FakeEnding const & thisEnding, FakeEnding const & otherEnding, - bool isStart, uint32_t & fakeNumerationStart, bool strictForward) +void IndexGraphStarter::FakeGraph::Append(FakeGraph const & rhs) { - CHECK_EQUAL(thisEnding.m_projectionJunctions.size(), thisEnding.m_projectionSegments.size(), ()); - CHECK_EQUAL(otherEnding.m_projectionJunctions.size(), otherEnding.m_projectionSegments.size(), ()); - Segment dummy; + CHECK(IsIntersectionEmpty(m_segmentToVertex, rhs.m_segmentToVertex), ("Fake segment ids are not unique")); + m_segmentToVertex.insert(rhs.m_segmentToVertex.begin(), rhs.m_segmentToVertex.end()); - map<Segment, Junction> otherSegments; - for (size_t i = 0; i < otherEnding.m_projectionSegments.size(); ++i) - otherSegments[otherEnding.m_projectionSegments[i]] = otherEnding.m_projectionJunctions[i]; + for (auto const & kv : rhs.m_outgoing) + m_outgoing[kv.first].insert(kv.second.begin(), kv.second.end()); - // Add pure fake vertex - auto fakeSegment = GetFakeSegment(fakeNumerationStart++); - FakeVertex fakeVertex(thisEnding.m_originJunction, thisEnding.m_originJunction, - FakeVertex::Type::PureFake); - m_fake.m_segmentToVertex[fakeSegment] = fakeVertex; - for (uint32_t i = 0; i < thisEnding.m_projectionJunctions.size(); ++i) - { - // Add projection edges - auto projectionSegment = GetFakeSegment(fakeNumerationStart++); - FakeVertex projection( - isStart ? thisEnding.m_originJunction : thisEnding.m_projectionJunctions[i], - isStart ? thisEnding.m_projectionJunctions[i] : thisEnding.m_originJunction, - FakeVertex::Type::Projection); - AddFakeVertex(fakeSegment, projectionSegment, projection, isStart /* isOutgoing */, - false /* isPartOfReal */, dummy /* realSegment */); + for (auto const & kv : rhs.m_ingoing) + m_ingoing[kv.first].insert(kv.second.begin(), kv.second.end()); - // Add fake parts of real - auto frontJunction = m_graph.GetJunction(thisEnding.m_projectionSegments[i], - thisEnding.m_projectionSegments[i].IsForward()); - auto backJunction = m_graph.GetJunction(thisEnding.m_projectionSegments[i], - !thisEnding.m_projectionSegments[i].IsForward()); + for (auto const & kv : rhs.m_realToFake) + m_realToFake[kv.first].insert(kv.second.begin(), kv.second.end()); - // Check whether we have projections to same real segment from both endings. - auto const & it = otherSegments.find(thisEnding.m_projectionSegments[i]); - if (it != otherSegments.end()) - { - auto const & otherJunction = it->second; - auto distBackToThis = m_graph.GetEstimator().CalcLeapWeight( - backJunction.GetPoint(), thisEnding.m_projectionJunctions[i].GetPoint()); - auto distBackToOther = - m_graph.GetEstimator().CalcLeapWeight(backJunction.GetPoint(), otherJunction.GetPoint()); - distBackToThis < distBackToOther ? frontJunction = otherJunction - : backJunction = otherJunction; - } + m_fakeToReal.insert(rhs.m_fakeToReal.begin(), rhs.m_fakeToReal.end()); +} - FakeVertex forwardPartOfReal(isStart ? thisEnding.m_projectionJunctions[i] : backJunction, - isStart ? frontJunction : thisEnding.m_projectionJunctions[i], - FakeVertex::Type::PartOfReal); - auto fakeForwardSegment = GetSegment(forwardPartOfReal, fakeNumerationStart); - AddFakeVertex(projectionSegment, fakeForwardSegment, forwardPartOfReal, - isStart /* isOutgoing */, true /* isPartOfReal */, - thisEnding.m_projectionSegments[i]); - - bool oneWay = m_graph - .GetRoadGeometry(thisEnding.m_projectionSegments[i].GetMwmId(), - thisEnding.m_projectionSegments[i].GetFeatureId()) - .IsOneWay(); - if (!strictForward && !oneWay) - { - Segment backwardSegment = InvertDirection(thisEnding.m_projectionSegments[i]); - FakeVertex backwardPartOfReal(isStart ? thisEnding.m_projectionJunctions[i] : frontJunction, - isStart ? backJunction : thisEnding.m_projectionJunctions[i], - FakeVertex::Type::PartOfReal); - auto fakeBackwardSegment = GetSegment(backwardPartOfReal, fakeNumerationStart); - AddFakeVertex(projectionSegment, fakeBackwardSegment, backwardPartOfReal, - isStart /* isOutgoing */, true /* isPartOfReal */, backwardSegment); - } - } +// IndexGraphStarter ----------------------------------------------------------- +// static +IndexGraphStarter::FakeEnding IndexGraphStarter::MakeFakeEnding(Segment const & segment, + m2::PointD const & point, + WorldGraph & graph) +{ + IndexGraphStarter::FakeEnding ending; + auto const & projectedJunction = CalcProjectionToSegment(segment, point, graph); + ending.m_originJunction = Junction(point, projectedJunction.GetAltitude()); + ending.m_projections.push_back(Projection{segment, projectedJunction}); + return ending; } -void IndexGraphStarter::AddStart(FakeEnding const & startEnding, FakeEnding const & finishEnding, - uint32_t & fakeNumerationStart, bool strictForward) +// static +void IndexGraphStarter::CheckValidRoute(vector<Segment> const & segments) { - AddEnding(startEnding, finishEnding, true /* isStart */, fakeNumerationStart, strictForward); + // Valid route contains at least 3 segments: + // start fake, finish fake and at least one normal nearest segment. + CHECK_GREATER_OR_EQUAL(segments.size(), 3, ()); + CHECK(IsFakeSegment(segments.front()), ()); + CHECK(IsFakeSegment(segments.back()), ()); } -void IndexGraphStarter::AddFinish(FakeEnding const & finishEnding, FakeEnding const & startEnding, - uint32_t & fakeNumerationStart) + +// static +size_t IndexGraphStarter::GetRouteNumPoints(vector<Segment> const & segments) { - AddEnding(finishEnding, startEnding, false /* isStart */, fakeNumerationStart, - false /* strictForward */); + CheckValidRoute(segments); + return segments.size() + 1; } IndexGraphStarter::IndexGraphStarter(FakeEnding const & startEnding, @@ -164,74 +134,21 @@ IndexGraphStarter::IndexGraphStarter(FakeEnding const & startEnding, : m_graph(graph) { m_startId = fakeNumerationStart; - AddStart(startEnding, finishEnding, fakeNumerationStart, strictForward); + AddStart(startEnding, finishEnding, strictForward, fakeNumerationStart); m_finishId = fakeNumerationStart; AddFinish(finishEnding, startEnding, fakeNumerationStart); } -IndexGraphStarter::IndexGraphStarter(vector<IndexGraphStarter> starters) - : m_graph(starters.front().m_graph) -{ - m_startId = starters.front().m_startId; - m_finishId = starters.back().m_finishId; - - for (auto const & starter : starters) - { - m_fake.m_segmentToVertex.insert(starter.m_fake.m_segmentToVertex.begin(), - starter.m_fake.m_segmentToVertex.end()); - - for (auto const & s : starter.m_fake.m_outgoing) - m_fake.m_outgoing[s.first].insert(s.second.begin(), s.second.end()); - - for (auto const & s : starter.m_fake.m_ingoing) - m_fake.m_ingoing[s.first].insert(s.second.begin(), s.second.end()); - - for (auto const & s : starter.m_fake.m_realToFake) - m_fake.m_realToFake[s.first].insert(s.second.begin(), s.second.end()); - - m_fake.m_fakeToReal.insert(starter.m_fake.m_fakeToReal.begin(), - starter.m_fake.m_fakeToReal.end()); - } -} - void IndexGraphStarter::Append(FakeEdgesContainer const & container) { m_finishId = container.m_finishId; - - m_fake.m_segmentToVertex.insert(container.m_fake.m_segmentToVertex.begin(), - container.m_fake.m_segmentToVertex.end()); - - for (auto const & s : container.m_fake.m_outgoing) - m_fake.m_outgoing[s.first].insert(s.second.begin(), s.second.end()); - - for (auto const & s : container.m_fake.m_ingoing) - m_fake.m_ingoing[s.first].insert(s.second.begin(), s.second.end()); - - for (auto const & s : container.m_fake.m_realToFake) - m_fake.m_realToFake[s.first].insert(s.second.begin(), s.second.end()); - - m_fake.m_fakeToReal.insert(container.m_fake.m_fakeToReal.begin(), - container.m_fake.m_fakeToReal.end()); -} - -// static -IndexGraphStarter::FakeEnding IndexGraphStarter::MakeFakeEnding(Segment const & segment, - m2::PointD const & point, - WorldGraph & graph) -{ - IndexGraphStarter::FakeEnding ending; - ending.m_originJunction = InterpolateJunction(segment, point, graph); - ending.m_projectionJunctions.push_back( - CalcProjectionToSegment(segment, ending.m_originJunction, graph)); - ending.m_projectionSegments.push_back(segment); - return ending; + m_fake.Append(container.m_fake); } Junction const & IndexGraphStarter::GetStartJunction() const { auto const & startSegment = GetFakeSegment(m_startId); - - auto it = m_fake.m_segmentToVertex.find(startSegment); + auto const it = m_fake.m_segmentToVertex.find(startSegment); CHECK(it != m_fake.m_segmentToVertex.end(), ("Requested junction for invalid fake segment.")); return it->second.GetJunctionFrom(); @@ -240,8 +157,7 @@ Junction const & IndexGraphStarter::GetStartJunction() const Junction const & IndexGraphStarter::GetFinishJunction() const { auto const & finishSegment = GetFakeSegment(m_finishId); - - auto it = m_fake.m_segmentToVertex.find(finishSegment); + auto const it = m_fake.m_segmentToVertex.find(finishSegment); CHECK(it != m_fake.m_segmentToVertex.end(), ("Requested junction for invalid fake segment.")); return it->second.GetJunctionTo(); @@ -252,7 +168,7 @@ bool IndexGraphStarter::ConvertToReal(Segment & segment) const if (!IsFakeSegment(segment)) return true; - auto const & it = m_fake.m_fakeToReal.find(segment); + auto const it = m_fake.m_fakeToReal.find(segment); if (it == m_fake.m_fakeToReal.end()) return false; @@ -265,62 +181,83 @@ Junction const & IndexGraphStarter::GetJunction(Segment const & segment, bool fr if (!IsFakeSegment(segment)) return m_graph.GetJunction(segment, front); - auto fakeVertexIt = m_fake.m_segmentToVertex.find(segment); + auto const fakeVertexIt = m_fake.m_segmentToVertex.find(segment); CHECK(fakeVertexIt != m_fake.m_segmentToVertex.end(), ("Requested junction for invalid fake segment.")); return front ? fakeVertexIt->second.GetJunctionTo() : fakeVertexIt->second.GetJunctionFrom(); } -m2::PointD const & IndexGraphStarter::GetPoint(Segment const & segment, bool front) const +Junction const & IndexGraphStarter::GetRouteJunction(vector<Segment> const & segments, + size_t pointIndex) const { - return GetJunction(segment, front).GetPoint(); + CHECK(!segments.empty(), ()); + CHECK_LESS_OR_EQUAL( + pointIndex, segments.size(), + ("Point with index", pointIndex, "does not exist in route with size", segments.size())); + if (pointIndex == segments.size()) + return GetJunction(segments[pointIndex - 1], true /* front */); + return GetJunction(segments[pointIndex], false); } -// static -void IndexGraphStarter::CheckValidRoute(vector<Segment> const & segments) +m2::PointD const & IndexGraphStarter::GetPoint(Segment const & segment, bool front) const { - // Valid route contains at least 3 segments: - // start fake, finish fake and at least one normal nearest segment. - CHECK_GREATER_OR_EQUAL(segments.size(), 3, ()); - CHECK(IsFakeSegment(segments.front()), ()); - CHECK(IsFakeSegment(segments.back()), ()); + return GetJunction(segment, front).GetPoint(); } set<NumMwmId> IndexGraphStarter::GetMwms() const { set<NumMwmId> mwms; - for (auto const & s : m_fake.m_fakeToReal) - mwms.insert(s.second.GetMwmId()); + for (auto const & kv : m_fake.m_fakeToReal) + mwms.insert(kv.second.GetMwmId()); return mwms; } -// static -size_t IndexGraphStarter::GetRouteNumPoints(vector<Segment> const & segments) +void IndexGraphStarter::GetEdgesList(Segment const & segment, bool isOutgoing, + vector<SegmentEdge> & edges) const { - CheckValidRoute(segments); - return segments.size() + 1; -} + edges.clear(); + if (IsFakeSegment(segment)) + { + auto const vertexIt = m_fake.m_segmentToVertex.find(segment); + CHECK(vertexIt != m_fake.m_segmentToVertex.end(), + ("Can not map fake segment", segment, "to fake vertex.")); -Junction const & IndexGraphStarter::GetRouteJunction(vector<Segment> const & segments, - size_t pointIndex) const -{ - CHECK_LESS_OR_EQUAL( - pointIndex, segments.size(), - ("Point with index", pointIndex, "does not exist in route with size", segments.size())); - if (pointIndex == segments.size()) - return GetJunction(segments[pointIndex - 1], true); - return GetJunction(segments[pointIndex], false); + if (vertexIt->second.GetType() == FakeVertex::Type::PartOfReal) + { + auto const realIt = m_fake.m_fakeToReal.find(segment); + CHECK(realIt != m_fake.m_fakeToReal.end(), + ("Can not map fake segment", segment, "to real segment.")); + AddRealEdges(realIt->second, isOutgoing, edges); + } + + auto const & adjacentEdges = isOutgoing ? m_fake.m_outgoing : m_fake.m_ingoing; + + auto const it = adjacentEdges.find(segment); + if (it != adjacentEdges.end()) + { + for (auto const & s : it->second) + edges.emplace_back(s, RouteWeight(CalcSegmentWeight(isOutgoing ? s : segment))); + } + } + else + { + AddRealEdges(segment, isOutgoing, edges); + } + + AddFakeEdges(segment, edges); } double IndexGraphStarter::CalcSegmentWeight(Segment const & segment) const { if (!IsFakeSegment(segment)) + { return m_graph.GetEstimator().CalcSegmentWeight( segment, m_graph.GetRoadGeometry(segment.GetMwmId(), segment.GetFeatureId())); + } - auto fakeVertexIt = m_fake.m_segmentToVertex.find(segment); + auto const fakeVertexIt = m_fake.m_segmentToVertex.find(segment); CHECK(fakeVertexIt != m_fake.m_segmentToVertex.end(), ("Requested junction for invalid fake segment.")); @@ -339,30 +276,117 @@ double IndexGraphStarter::CalcRouteSegmentWeight(vector<Segment> const & route, bool IndexGraphStarter::IsLeap(NumMwmId mwmId) const { - bool inProjectedMwmIds = false; - for (auto const & s : m_fake.m_fakeToReal) + if (mwmId == kFakeNumMwmId) + return false; + + for (auto const & kv : m_fake.m_fakeToReal) + { + if (kv.second.GetMwmId() == mwmId) + return false; + } + + return m_graph.GetEstimator().LeapIsAllowed(mwmId); +} + +void IndexGraphStarter::AddEnding(FakeEnding const & thisEnding, FakeEnding const & otherEnding, + bool isStart, bool strictForward, uint32_t & fakeNumerationStart) +{ + Segment const dummy = Segment(); + + map<Segment, Junction> otherSegments; + for (auto const & p : otherEnding.m_projections) + otherSegments[p.m_segment] = p.m_junction; + + // Add pure fake vertex + auto const fakeSegment = GetFakeSegment(fakeNumerationStart++); + FakeVertex fakeVertex(thisEnding.m_originJunction, thisEnding.m_originJunction, + FakeVertex::Type::PureFake); + m_fake.m_segmentToVertex[fakeSegment] = fakeVertex; + for (auto const & projection : thisEnding.m_projections) { - if (s.second.GetMwmId() == mwmId) + // Add projection edges + auto const projectionSegment = GetFakeSegment(fakeNumerationStart++); + FakeVertex projectionVertex(isStart ? thisEnding.m_originJunction : projection.m_junction, + isStart ? projection.m_junction : thisEnding.m_originJunction, + FakeVertex::Type::PureFake); + m_fake.AddFakeVertex(fakeSegment, projectionSegment, projectionVertex, isStart /* isOutgoing */, + false /* isPartOfReal */, dummy /* realSegment */); + + // Add fake parts of real + auto frontJunction = + m_graph.GetJunction(projection.m_segment, projection.m_segment.IsForward()); + auto backJunction = + m_graph.GetJunction(projection.m_segment, !projection.m_segment.IsForward()); + + // Check whether we have projections to same real segment from both endings. + auto const it = otherSegments.find(projection.m_segment); + if (it != otherSegments.end()) { - inProjectedMwmIds = true; - break; + auto const & otherJunction = it->second; + auto const distBackToThis = m_graph.GetEstimator().CalcLeapWeight( + backJunction.GetPoint(), projection.m_junction.GetPoint()); + auto const distBackToOther = + m_graph.GetEstimator().CalcLeapWeight(backJunction.GetPoint(), otherJunction.GetPoint()); + if (distBackToThis < distBackToOther) + frontJunction = otherJunction; + else + backJunction = otherJunction; } - } - return mwmId != kFakeNumMwmId && !inProjectedMwmIds && - m_graph.GetEstimator().LeapIsAllowed(mwmId); + FakeVertex forwardPartOfReal(isStart ? projection.m_junction : backJunction, + isStart ? frontJunction : projection.m_junction, + FakeVertex::Type::PartOfReal); + auto const fakeForwardSegment = m_fake.GetSegment(forwardPartOfReal, fakeNumerationStart); + m_fake.AddFakeVertex(projectionSegment, fakeForwardSegment, forwardPartOfReal, + isStart /* isOutgoing */, true /* isPartOfReal */, projection.m_segment); + + bool const oneWay = + m_graph + .GetRoadGeometry(projection.m_segment.GetMwmId(), projection.m_segment.GetFeatureId()) + .IsOneWay(); + if (!strictForward && !oneWay) + { + auto const backwardSegment = GetReverseSegment(projection.m_segment); + FakeVertex backwardPartOfReal(isStart ? projection.m_junction : frontJunction, + isStart ? backJunction : projection.m_junction, + FakeVertex::Type::PartOfReal); + auto const fakeBackwardSegment = m_fake.GetSegment(backwardPartOfReal, fakeNumerationStart); + m_fake.AddFakeVertex(projectionSegment, fakeBackwardSegment, backwardPartOfReal, + isStart /* isOutgoing */, true /* isPartOfReal */, backwardSegment); + } + } } -void IndexGraphStarter::AddFakeEdges(vector<SegmentEdge> & edges) const +void IndexGraphStarter::AddStart(FakeEnding const & startEnding, FakeEnding const & finishEnding, + bool strictForward, uint32_t & fakeNumerationStart) { - for (auto const & edge : edges) + AddEnding(startEnding, finishEnding, true /* isStart */, strictForward, fakeNumerationStart); + } + + void IndexGraphStarter::AddFinish(FakeEnding const & finishEnding, FakeEnding const & startEnding, + uint32_t & fakeNumerationStart) { - auto const & it = m_fake.m_realToFake.find(edge.GetTarget()); - if (it == m_fake.m_realToFake.end()) - continue; - for (auto const & s : it->second) - edges.emplace_back(s, RouteWeight(edge.GetWeight())); + AddEnding(finishEnding, startEnding, false /* isStart */, false /* strictForward */, + fakeNumerationStart); } + + void IndexGraphStarter::AddFakeEdges(Segment const & segment, vector<SegmentEdge> & edges) const + { + vector<SegmentEdge> fakeEdges; + for (auto const & edge : edges) + { + auto const it = m_fake.m_realToFake.find(edge.GetTarget()); + if (it == m_fake.m_realToFake.end()) + continue; + for (auto const & s : it->second) + { + // 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())); + } + } + edges.insert(edges.end(), fakeEdges.begin(), fakeEdges.end()); } void IndexGraphStarter::AddRealEdges(Segment const & segment, bool isOutgoing, @@ -378,41 +402,6 @@ void IndexGraphStarter::AddRealEdges(Segment const & segment, bool isOutgoing, m_graph.GetEdgeList(segment, isOutgoing, IsLeap(segment.GetMwmId()), edges); } -void IndexGraphStarter::GetEdgesList(Segment const & segment, bool isOutgoing, - vector<SegmentEdge> & edges) const -{ - edges.clear(); - if (IsFakeSegment(segment)) - { - auto const & vertexIt = m_fake.m_segmentToVertex.find(segment); - CHECK(vertexIt != m_fake.m_segmentToVertex.end(), - ("Can not map fake segment", segment, "to fake vertex.")); - - if (vertexIt->second.GetType() == FakeVertex::Type::PartOfReal) - { - auto const & realIt = m_fake.m_fakeToReal.find(segment); - CHECK(realIt != m_fake.m_fakeToReal.end(), - ("Can not map fake segment", segment, "to real segment.")); - AddRealEdges(realIt->second, isOutgoing, edges); - } - - auto const & fakeGraph = isOutgoing ? m_fake.m_outgoing : m_fake.m_ingoing; - - auto it = fakeGraph.find(segment); - if (it != fakeGraph.end()) - { - for (auto const & s : it->second) - edges.emplace_back(s, RouteWeight(CalcSegmentWeight(isOutgoing ? s : segment))); - } - } - else - { - AddRealEdges(segment, isOutgoing, edges); - } - - AddFakeEdges(edges); -} - void IndexGraphStarter::ConnectLeapToTransitions(Segment const & segment, bool isOutgoing, vector<SegmentEdge> & edges) const { @@ -421,12 +410,13 @@ void IndexGraphStarter::ConnectLeapToTransitions(Segment const & segment, bool i // Note. If |isOutgoing| == true it's necessary to add edges which connect the start with all // exits of its mwm. So |isEnter| below should be set to false. - // If |isOutgoing| == false all enters of the finish mwm should be connected with the finish point. - // So |isEnter| below should be set to true. + // If |isOutgoing| == false all enters of the finish mwm should be connected with the finish + // 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)))); }); } + } // namespace routing diff --git a/routing/index_graph_starter.hpp b/routing/index_graph_starter.hpp index 96122dd106..0611b22658 100644 --- a/routing/index_graph_starter.hpp +++ b/routing/index_graph_starter.hpp @@ -6,6 +6,7 @@ #include "routing/route_point.hpp" #include "routing/world_graph.hpp" +#include <cstddef> #include <cstdint> #include <limits> #include <map> @@ -26,40 +27,46 @@ public: using TEdgeType = IndexGraph::TEdgeType; using TWeightType = IndexGraph::TWeightType; - struct FakeEnding + struct Projection final + { + Segment m_segment; + Junction m_junction; + }; + + struct FakeEnding final { Junction m_originJunction; - std::vector<Junction> m_projectionJunctions; - std::vector<Segment> m_projectionSegments; + std::vector<Projection> m_projections; }; friend class FakeEdgesContainer; - static uint32_t constexpr kFakeFeatureId = numeric_limits<uint32_t>::max(); + static uint32_t constexpr kFakeFeatureId = std::numeric_limits<uint32_t>::max(); static FakeEnding MakeFakeEnding(Segment const & segment, m2::PointD const & point, WorldGraph & graph); static void CheckValidRoute(std::vector<Segment> const & segments); static size_t GetRouteNumPoints(std::vector<Segment> const & route); + static bool IsFakeSegment(Segment const & segment) + { + return segment.GetFeatureId() == kFakeFeatureId; + } + // strictForward flag specifies which parts of real segment should be placed from the start // vertex. true: place exactly one fake edge to the m_segment with indicated m_forward. false: // place two fake edges to the m_segment with both directions. IndexGraphStarter(FakeEnding const & startEnding, FakeEnding const & finishEnding, uint32_t fakeNumerationStart, bool strictForward, WorldGraph & graph); - // Merge starters to single IndexGraphStarter. - // Expects starters[0] has WorldGraph which is valid for all starters, starters.size() >= 1. - IndexGraphStarter(std::vector<IndexGraphStarter> starters); - void Append(FakeEdgesContainer const & container); - WorldGraph & GetGraph() { return m_graph; } + WorldGraph & GetGraph() const { return m_graph; } Junction const & GetStartJunction() const; Junction const & GetFinishJunction() const; Segment GetStartSegment() const { return GetFakeSegment(m_startId); } Segment GetFinishSegment() const { return GetFakeSegment(m_finishId); } - // If segment is real return true and does not modify segment. + // If segment is real returns true and does not modify segment. // If segment is part of real converts it to real and returns true. // Otherwise returns false and does not modify segment. bool ConvertToReal(Segment & segment) const; @@ -94,35 +101,24 @@ public: bool IsLeap(NumMwmId mwmId) const; - static bool IsFakeSegment(Segment const & segment) - { - return segment.GetFeatureId() == kFakeFeatureId; - } - private: - static Segment GetFakeSegment(uint32_t i) - { - return Segment(kFakeNumMwmId, kFakeFeatureId, i, false); - } - class FakeVertex final { public: enum class Type { PureFake, - Projection, PartOfReal, }; + // For unit tests only. FakeVertex(NumMwmId mwmId, uint32_t featureId, uint32_t segmentIdx, m2::PointD const & point) - : m_junctionFrom(point, feature::kDefaultAltitudeMeters) - , m_junctionTo(point, feature::kDefaultAltitudeMeters) + : m_from(point, feature::kDefaultAltitudeMeters), m_to(point, feature::kDefaultAltitudeMeters) { } - FakeVertex(Junction const & junctionFrom, Junction const & junctionTo, Type type) - : m_junctionFrom(junctionFrom), m_junctionTo(junctionTo), m_type(type) + FakeVertex(Junction const & from, Junction const & to, Type type) + : m_from(from), m_to(to), m_type(type) { } @@ -131,47 +127,66 @@ private: bool operator==(FakeVertex const & rhs) const { - return m_junctionFrom == rhs.m_junctionFrom && m_junctionTo == rhs.m_junctionTo && - m_type == rhs.m_type; + return m_from == rhs.m_from && m_to == rhs.m_to && m_type == rhs.m_type; } Type GetType() const { return m_type; } - Junction const & GetJunctionFrom() const { return m_junctionFrom; } - m2::PointD const & GetPointFrom() const { return m_junctionFrom.GetPoint(); } - Junction const & GetJunctionTo() const { return m_junctionTo; } - m2::PointD const & GetPointTo() const { return m_junctionTo.GetPoint(); } + Junction const & GetJunctionFrom() const { return m_from; } + m2::PointD const & GetPointFrom() const { return m_from.GetPoint(); } + Junction const & GetJunctionTo() const { return m_to; } + m2::PointD const & GetPointTo() const { return m_to.GetPoint(); } private: - Junction m_junctionFrom; - Junction m_junctionTo; + Junction m_from; + Junction m_to; Type m_type = Type::PureFake; }; - struct FakeGraph + struct FakeGraph final { + // Adds vertex. Connects newSegment to existentSegment. Adds ingoing and + // outgoing edges, fills segment to vertex mapping. Fill real to fake and fake to real + // mapping if isPartOfReal is true. + void AddFakeVertex(Segment const & existentSegment, Segment const & newSegment, + FakeVertex const & newVertex, bool isOutgoing, bool isPartOfReal, + Segment const & realSegment); + // Returns existent segment if possible. If segment does not exist makes new segment, + // increments newNumber. + Segment GetSegment(FakeVertex const & vertex, uint32_t & newNumber) const; + void Append(FakeGraph const & rhs); + + // Key is fake segment, value is set of outgoing fake segments std::map<Segment, std::set<Segment>> m_outgoing; + // Key is fake segment, value is set of ingoing fake segments std::map<Segment, std::set<Segment>> m_ingoing; + // Key is fake segment, value is fake vertex which corresponds fake segment std::map<Segment, FakeVertex> m_segmentToVertex; + // Key is fake segment of type FakeVertex::Type::PartOfReal, value is corresponding real segment std::map<Segment, Segment> m_fakeToReal; + // Key is real segment, value is set of fake segments with type FakeVertex::Type::PartOfReal + // which are parts of this real segment std::map<Segment, std::set<Segment>> m_realToFake; }; - void AddFakeVertex(Segment const & existentSegment, Segment const & newSegment, - FakeVertex const & newVertex, bool isOutgoing, bool isPartOfReal, - Segment const & realSegment); + static Segment GetFakeSegment(uint32_t segmentIdx) + { + return Segment(kFakeNumMwmId, kFakeFeatureId, segmentIdx, false); + } + + // Creates fake edges for fake ending and adds it to fake graph. |otherEnding| used to generate + // propper fake edges in case both endings have projections to the same segment. void AddEnding(FakeEnding const & thisEnding, FakeEnding const & otherEnding, bool isStart, - uint32_t & fakeNumerationStart, bool strictForward); - void AddStart(FakeEnding const & startEnding, FakeEnding const & finishEnding, - uint32_t & fakeNumerationStart, bool strictForward); + bool strictForward, uint32_t & fakeNumerationStart); + void AddStart(FakeEnding const & startEnding, FakeEnding const & finishEnding, bool strictForward, + uint32_t & fakeNumerationStart); void AddFinish(FakeEnding const & finishEnding, FakeEnding const & startEnding, uint32_t & fakeNumerationStart); - // Returns existent segment if possible. If segment does not exist makes new segment, - // increments newNumber. - Segment GetSegment(FakeVertex const & vertex, uint32_t & newNumber) const; - - void AddFakeEdges(vector<SegmentEdge> & edges) const; + // Adds fake edges of type PartOfReal which correspond real edges from |edges| and are connected + // to |segment| + void AddFakeEdges(Segment const & segment, vector<SegmentEdge> & edges) const; + // Adds real edges from m_graph void AddRealEdges(Segment const & segment, bool isOutgoing, std::vector<SegmentEdge> & edges) const; /// \brief If |isOutgoing| == true fills |edges| with SegmentEdge(s) which connects @@ -182,25 +197,10 @@ private: std::vector<SegmentEdge> & edges) const; WorldGraph & m_graph; + // Start segment id uint32_t m_startId; + // Finish segment id uint32_t m_finishId; FakeGraph m_fake; }; - -class FakeEdgesContainer final -{ - friend class IndexGraphStarter; - -public: - FakeEdgesContainer(IndexGraphStarter && starter) - : m_finishId(move(starter.m_finishId)), m_fake(move(starter.m_fake)) - { - } - - size_t GetNumFakeEdges() const { return m_fake.m_segmentToVertex.size(); } - -private: - uint32_t m_finishId; - IndexGraphStarter::FakeGraph m_fake; -}; } // namespace routing diff --git a/routing/index_road_graph.cpp b/routing/index_road_graph.cpp index 787c153942..a1e35d8e2e 100644 --- a/routing/index_road_graph.cpp +++ b/routing/index_road_graph.cpp @@ -4,10 +4,7 @@ #include <cstdint> -namespace -{ using namespace std; -} // namespace namespace routing { @@ -89,18 +86,15 @@ void IndexRoadGraph::GetRouteEdges(TEdgeVector & edges) const for (Segment const & segment : m_segments) { - auto featureIdHandle = FeatureID(); + auto featureId = FeatureID(); if (!IndexGraphStarter::IsFakeSegment(segment)) { platform::CountryFile const & file = m_numMwmIds->GetFile(segment.GetMwmId()); - MwmSet::MwmHandle const handle = m_index.GetMwmHandleByCountryFile(file); - if (!handle.IsAlive()) - MYTHROW(RoutingException, ("Can't get mwm handle for", file)); - - featureIdHandle = FeatureID(handle.GetId(), segment.GetFeatureId()); + MwmSet::MwmId const mwmId = m_index.GetMwmIdByCountryFile(file); + featureId = FeatureID(mwmId, segment.GetFeatureId()); } - edges.emplace_back(featureIdHandle, segment.IsForward(), segment.GetSegmentIdx(), + edges.emplace_back(featureId, segment.IsForward(), segment.GetSegmentIdx(), m_starter.GetJunction(segment, false /* front */), m_starter.GetJunction(segment, true /* front */)); } @@ -126,13 +120,10 @@ void IndexRoadGraph::GetEdges(Junction const & junction, bool isOutgoing, TEdgeV continue; platform::CountryFile const & file = m_numMwmIds->GetFile(segment.GetMwmId()); - MwmSet::MwmHandle const handle = m_index.GetMwmHandleByCountryFile(file); - if (!handle.IsAlive()) - MYTHROW(RoutingException, ("Can't get mwm handle for", file)); + MwmSet::MwmId const mwmId = m_index.GetMwmIdByCountryFile(file); - edges.emplace_back(FeatureID(MwmSet::MwmId(handle.GetInfo()), segment.GetFeatureId()), - segment.IsForward(), segment.GetSegmentIdx(), - m_starter.GetJunction(segment, false /* front */), + edges.emplace_back(FeatureID(mwmId, segment.GetFeatureId()), segment.IsForward(), + segment.GetSegmentIdx(), m_starter.GetJunction(segment, false /* front */), m_starter.GetJunction(segment, true /* front */)); } } diff --git a/routing/index_router.cpp b/routing/index_router.cpp index 76298ce6f9..fc9b63bca1 100644 --- a/routing/index_router.cpp +++ b/routing/index_router.cpp @@ -6,6 +6,7 @@ #include "routing/index_graph.hpp" #include "routing/index_graph_loader.hpp" #include "routing/index_graph_serialization.hpp" +#include "routing/index_graph_starter.hpp" #include "routing/index_road_graph.hpp" #include "routing/pedestrian_directions.hpp" #include "routing/restriction_loader.hpp" @@ -388,10 +389,9 @@ IRouter::ResultCode IndexRouter::DoCalculateRoute(Checkpoints const & checkpoint } size_t subrouteSegmentsBegin = 0; - uint32_t fakeSegmentsNumerationStart = 0; vector<Route::SubrouteAttrs> subroutes; PushPassedSubroutes(checkpoints, subroutes); - vector<IndexGraphStarter> starters; + unique_ptr<IndexGraphStarter> starter; for (size_t i = checkpoints.GetPassedIdx(); i < checkpoints.GetNumSubroutes(); ++i) { @@ -416,13 +416,14 @@ IRouter::ResultCode IndexRouter::DoCalculateRoute(Checkpoints const & checkpoint bool const isStartSegmentStrictForward = i == checkpoints.GetPassedIdx() ? startSegmentIsAlmostCodirectionalDirection : true; - starters.emplace_back(IndexGraphStarter::MakeFakeEnding(startSegment, startCheckpoint, graph), - IndexGraphStarter::MakeFakeEnding(finishSegment, finishCheckpoint, graph), - fakeSegmentsNumerationStart, isStartSegmentStrictForward, graph); + IndexGraphStarter subrouteStarter( + IndexGraphStarter::MakeFakeEnding(startSegment, startCheckpoint, graph), + IndexGraphStarter::MakeFakeEnding(finishSegment, finishCheckpoint, graph), + starter ? starter->GetNumFakeSegments() : 0, isStartSegmentStrictForward, graph); vector<Segment> subroute; Junction startJunction; - auto const result = CalculateSubroute(checkpoints, i, startSegment, delegate, starters.back(), + auto const result = CalculateSubroute(checkpoints, i, startSegment, delegate, subrouteStarter, subroute, startJunction); if (result != IRouter::NoError) @@ -433,10 +434,13 @@ IRouter::ResultCode IndexRouter::DoCalculateRoute(Checkpoints const & checkpoint segments.insert(segments.end(), subroute.begin(), subroute.end()); size_t subrouteSegmentsEnd = segments.size(); - subroutes.emplace_back(starters.back().GetStartJunction(), starters.back().GetFinishJunction(), + subroutes.emplace_back(subrouteStarter.GetStartJunction(), subrouteStarter.GetFinishJunction(), subrouteSegmentsBegin, subrouteSegmentsEnd); subrouteSegmentsBegin = subrouteSegmentsEnd; - fakeSegmentsNumerationStart += starters.back().GetNumFakeSegments(); + if (!starter) + starter = make_unique<IndexGraphStarter>(move(subrouteStarter)); + else + starter->Append(FakeEdgesContainer(move(subrouteStarter))); } route.SetCurrentSubrouteIdx(checkpoints.GetPassedIdx()); @@ -444,18 +448,16 @@ IRouter::ResultCode IndexRouter::DoCalculateRoute(Checkpoints const & checkpoint IndexGraphStarter::CheckValidRoute(segments); - IndexGraphStarter starter(starters); - - auto redressResult = RedressRoute(segments, delegate, starter, route); + auto redressResult = RedressRoute(segments, delegate, *starter, route); if (redressResult != IRouter::NoError) return redressResult; m_lastRoute = make_unique<SegmentedRoute>(checkpoints.GetStart(), checkpoints.GetFinish(), route.GetSubroutes()); for (Segment const & segment : segments) - m_lastRoute->AddStep(segment, starter.GetPoint(segment, true /* front */)); + m_lastRoute->AddStep(segment, starter->GetPoint(segment, true /* front */)); - m_lastFakeEdges = make_unique<FakeEdgesContainer>(move(starter)); + m_lastFakeEdges = make_unique<FakeEdgesContainer>(move(*starter)); return IRouter::NoError; } @@ -474,12 +476,11 @@ IRouter::ResultCode IndexRouter::CalculateSubroute(Checkpoints const & checkpoin { case VehicleType::Pedestrian: case VehicleType::Bicycle: - starter.SetMode(WorldGraph::Mode::NoLeaps); + starter.GetGraph().SetMode(WorldGraph::Mode::NoLeaps); break; case VehicleType::Car: - starter.SetMode(AreMwmsNear(startSegment.GetMwmId(), finishSegment.GetMwmId()) - ? WorldGraph::Mode::LeapsIfPossible - : WorldGraph::Mode::LeapsOnly); + starter.GetGraph().SetMode(AreMwmsNear(starter.GetMwms()) ? WorldGraph::Mode::LeapsIfPossible + : WorldGraph::Mode::LeapsOnly); break; } @@ -700,10 +701,9 @@ IRouter::ResultCode IndexRouter::ProcessLeaps(vector<Segment> const & input, for (size_t i = 0; i < input.size(); ++i) { Segment current = input[i]; - starter.ConvertToReal(current); - if ((prevMode == WorldGraph::Mode::LeapsOnly && IndexGraphStarter::IsFakeSegment(current)) - || (prevMode != WorldGraph::Mode::LeapsOnly && !starter.IsLeap(current.GetMwmId()))) + if ((prevMode == WorldGraph::Mode::LeapsOnly && !starter.ConvertToReal(current)) || + (prevMode != WorldGraph::Mode::LeapsOnly && !starter.IsLeap(current.GetMwmId()))) { output.push_back(current); continue; @@ -740,6 +740,12 @@ IRouter::ResultCode IndexRouter::ProcessLeaps(vector<Segment> const & input, } if (result != IRouter::NoError) return result; + + // Start and finish segments may be changed by starter.ConvertToReal. It was necessary to use it + // in worldGraph but we need to reset them to original values. + routingResult.path.front() = input[i - 1]; + routingResult.path.back() = input[i]; + output.insert(output.end(), routingResult.path.cbegin(), routingResult.path.cend()); } @@ -750,6 +756,7 @@ IRouter::ResultCode IndexRouter::RedressRoute(vector<Segment> const & segments, RouterDelegate const & delegate, IndexGraphStarter & starter, Route & route) const { + CHECK(!segments.empty(), ()); vector<Junction> junctions; size_t const numPoints = IndexGraphStarter::GetRouteNumPoints(segments); junctions.reserve(numPoints); @@ -765,15 +772,15 @@ IRouter::ResultCode IndexRouter::RedressRoute(vector<Segment> const & segments, double time = 0.0; times.emplace_back(static_cast<uint32_t>(0), 0.0); - for (size_t i = 0; i < numPoints - 1; ++i) + for (size_t i = 0; i + 1 < numPoints; ++i) { time += starter.CalcRouteSegmentWeight(segments, i); times.emplace_back(static_cast<uint32_t>(i + 1), time); } CHECK(m_directionsEngine, ()); - ReconstructRoute(*m_directionsEngine, roadGraph, m_trafficStash, delegate, junctions, - std::move(times), route); + ReconstructRoute(*m_directionsEngine, roadGraph, m_trafficStash, delegate, junctions, move(times), + route); if (!route.IsValid()) { @@ -787,24 +794,15 @@ IRouter::ResultCode IndexRouter::RedressRoute(vector<Segment> const & segments, return IRouter::NoError; } -bool IndexRouter::AreMwmsNear(std::set<NumMwmId> mwmIds) const +bool IndexRouter::AreMwmsNear(set<NumMwmId> const & mwmIds) const { - // Function fails on first mwm which is not near to all other mwms. - // Maximal complexity is O((size of mwms clique)^2). - // Mwm clique maximal size is 4 (4 color theorem). for (auto const & outerId : mwmIds) { - m2::RectD const startMwmRect = m_countryRectFn(m_numMwmIds->GetFile(outerId).GetName()); - for (auto const & innerId : mwmIds) - { - bool areMwmsNear = false; - m_numMwmTree->ForEachInRect(startMwmRect, [&](NumMwmId id) { - if (id == innerId) - areMwmsNear = true; - }); - if (!areMwmsNear) - return false; - } + m2::RectD const rect = m_countryRectFn(m_numMwmIds->GetFile(outerId).GetName()); + size_t found = 0; + m_numMwmTree->ForEachInRect(rect, [&](NumMwmId id) { found += mwmIds.count(id); }); + if (found != mwmIds.size()) + return false; } return true; } diff --git a/routing/index_router.hpp b/routing/index_router.hpp index 571c72c9eb..cc01b38802 100644 --- a/routing/index_router.hpp +++ b/routing/index_router.hpp @@ -3,8 +3,8 @@ #include "routing/cross_mwm_graph.hpp" #include "routing/directions_engine.hpp" #include "routing/edge_estimator.hpp" +#include "routing/fake_edges_container.hpp" #include "routing/features_road_graph.hpp" -#include "routing/index_graph_starter.hpp" #include "routing/joint.hpp" #include "routing/num_mwm_id.hpp" #include "routing/router.hpp" @@ -19,8 +19,9 @@ #include "geometry/tree4d.hpp" +#include "std/unique_ptr.hpp" + #include <functional> -#include <memory> #include <set> #include <string> #include <vector> @@ -103,7 +104,7 @@ private: RouterDelegate const & delegate, IndexGraphStarter & starter, Route & route) const; - bool AreMwmsNear(std::set<NumMwmId> mwmIds) const; + bool AreMwmsNear(std::set<NumMwmId> const & mwmIds) const; VehicleType m_vehicleType; bool m_loadAltitudes; diff --git a/routing/routing.pro b/routing/routing.pro index 002ee02c89..89cbb030bf 100644 --- a/routing/routing.pro +++ b/routing/routing.pro @@ -90,6 +90,7 @@ HEADERS += \ cross_routing_context.hpp \ directions_engine.hpp \ edge_estimator.hpp \ + fake_edges_container.hpp \ features_road_graph.hpp \ geometry.hpp \ index_graph.hpp \ diff --git a/routing/routing_tests/cumulative_restriction_test.cpp b/routing/routing_tests/cumulative_restriction_test.cpp index f82a8da9f7..736879b0ae 100644 --- a/routing/routing_tests/cumulative_restriction_test.cpp +++ b/routing/routing_tests/cumulative_restriction_test.cpp @@ -91,10 +91,10 @@ UNIT_CLASS_TEST(RestrictionTest, XYGraph_RestrictionF1F3Only) vector<m2::PointD> const expectedGeom = {{2 /* x */, 0 /* y */}, {1, 1}, {2, 2}, {2, 3}}; TestRestrictions( expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, - routing::IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 1, 0, true /* forward */), - m2::PointD(2, 0), *m_graph), - routing::IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 5, 0, true /* forward */), - m2::PointD(2, 3), *m_graph), + IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 1, 0, true /* forward */), + m2::PointD(2, 0), *m_graph), + IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 5, 0, true /* forward */), + m2::PointD(2, 3), *m_graph), move(restrictions), *this); } @@ -108,10 +108,10 @@ UNIT_CLASS_TEST(RestrictionTest, XYGraph_RestrictionF3F5Only) vector<m2::PointD> const expectedGeom = {{2 /* x */, 0 /* y */}, {1, 1}, {2, 2}, {2, 3}}; TestRestrictions( expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, - routing::IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 1, 0, true /* forward */), - m2::PointD(2, 0), *m_graph), - routing::IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 5, 0, true /* forward */), - m2::PointD(2, 3), *m_graph), + IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 1, 0, true /* forward */), + m2::PointD(2, 0), *m_graph), + IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 5, 0, true /* forward */), + m2::PointD(2, 3), *m_graph), move(restrictions), *this); } @@ -127,10 +127,10 @@ UNIT_CLASS_TEST(RestrictionTest, XYGraph_PermutationsF3F5OnlyF1F3Only) vector<m2::PointD> const expectedGeom = {{2 /* x */, 0 /* y */}, {1, 1}, {2, 2}, {2, 3}}; TestRestrictions( expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, - routing::IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 1, 0, true /* forward */), - m2::PointD(2, 0), *m_graph), - routing::IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 5, 0, true /* forward */), - m2::PointD(2, 3), *m_graph), + IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 1, 0, true /* forward */), + m2::PointD(2, 0), *m_graph), + IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 5, 0, true /* forward */), + m2::PointD(2, 3), *m_graph), move(restrictions), *this); } @@ -146,10 +146,10 @@ UNIT_CLASS_TEST(RestrictionTest, XYGraph_PermutationsF3F5OnlyAndF0F2No) vector<m2::PointD> const expectedGeom = {{2 /* x */, 0 /* y */}, {1, 1}, {2, 2}, {2, 3}}; TestRestrictions( expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, - routing::IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 1, 0, true /* forward */), - m2::PointD(2, 0), *m_graph), - routing::IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 5, 0, true /* forward */), - m2::PointD(2, 3), *m_graph), + IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 1, 0, true /* forward */), + m2::PointD(2, 0), *m_graph), + IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 5, 0, true /* forward */), + m2::PointD(2, 3), *m_graph), move(restrictions), *this); } @@ -165,10 +165,10 @@ UNIT_CLASS_TEST(RestrictionTest, XYGraph_RestrictionF3F5OnlyAndF1F3No) TestRestrictions( {} /* expectedGeom */, AStarAlgorithm<IndexGraphStarter>::Result::NoPath, - routing::IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 1, 0, true /* forward */), - m2::PointD(2, 0), *m_graph), - routing::IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 5, 0, true /* forward */), - m2::PointD(2, 3), *m_graph), + IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 1, 0, true /* forward */), + m2::PointD(2, 0), *m_graph), + IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 5, 0, true /* forward */), + m2::PointD(2, 3), *m_graph), move(restrictions), *this); } @@ -243,10 +243,10 @@ UNIT_CLASS_TEST(RestrictionTest, XXGraph) vector<m2::PointD> const expectedGeom = {{2 /* x */, -1 /* y */}, {2, 0}, {1, 1}, {2, 2}, {3, 3}}; TestRestrictions( expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, - routing::IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 9, 0, true /* forward */), - m2::PointD(2, -1), *m_graph), - routing::IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 6, 0, true /* forward */), - m2::PointD(3, 3), *m_graph), + IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 9, 0, true /* forward */), + m2::PointD(2, -1), *m_graph), + IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 6, 0, true /* forward */), + m2::PointD(3, 3), *m_graph), move(restrictions), *this); } @@ -262,10 +262,10 @@ UNIT_CLASS_TEST(RestrictionTest, XXGraph_PermutationsF1F3OnlyAndF3F6Only) vector<m2::PointD> const expectedGeom = {{2 /* x */, -1 /* y */}, {2, 0}, {1, 1}, {2, 2}, {3, 3}}; TestRestrictions( expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, - routing::IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 9, 0, true /* forward */), - m2::PointD(2, -1), *m_graph), - routing::IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 6, 0, true /* forward */), - m2::PointD(3, 3), *m_graph), + IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 9, 0, true /* forward */), + m2::PointD(2, -1), *m_graph), + IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 6, 0, true /* forward */), + m2::PointD(3, 3), *m_graph), move(restrictions), *this); } @@ -280,10 +280,10 @@ UNIT_CLASS_TEST(RestrictionTest, XXGraph_RestrictionF1F3No) TestRestrictions( expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, - routing::IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 9, 0, true /* forward */), - m2::PointD(2, -1), *m_graph), - routing::IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 6, 0, true /* forward */), - m2::PointD(3, 3), *m_graph), + IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 9, 0, true /* forward */), + m2::PointD(2, -1), *m_graph), + IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 6, 0, true /* forward */), + m2::PointD(3, 3), *m_graph), move(restrictions), *this); } @@ -302,10 +302,10 @@ UNIT_CLASS_TEST(RestrictionTest, XXGraph_PermutationsF1F3NoF7F8OnlyF8F4OnlyF4F6O {2 /* x */, -1 /* y */}, {2, 0}, {3, 0}, {3, 1}, {2, 2}, {3, 3}}; TestRestrictions( expectedGeom, AStarAlgorithm<IndexGraphStarter>::Result::OK, - routing::IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 9, 0, true /* forward */), - m2::PointD(2, -1), *m_graph), - routing::IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 6, 0, true /* forward */), - m2::PointD(3, 3), *m_graph), + IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 9, 0, true /* forward */), + m2::PointD(2, -1), *m_graph), + IndexGraphStarter::MakeFakeEnding(Segment(kTestNumMwmId, 6, 0, true /* forward */), + m2::PointD(3, 3), *m_graph), move(restrictions), *this); } } // namespace diff --git a/routing/routing_tests/index_graph_test.cpp b/routing/routing_tests/index_graph_test.cpp index a2eaf1850a..6a8dab0129 100644 --- a/routing/routing_tests/index_graph_test.cpp +++ b/routing/routing_tests/index_graph_test.cpp @@ -52,11 +52,8 @@ void TestRoute(IndexGraphStarter::FakeEnding const & start, for (auto const & s : route) { auto real = s; - if (IndexGraphStarter::IsFakeSegment(real)) - { - if (!starter.ConvertToReal(real)) - continue; - } + if (!starter.ConvertToReal(real)) + continue; noFakeRoute.push_back(real); } @@ -211,24 +208,24 @@ UNIT_TEST(FindPathCross) for (auto const & finish : endPoints) { uint32_t expectedLength = 0; - if (start.m_projectionSegments[0].GetFeatureId() == - finish.m_projectionSegments[0].GetFeatureId()) + if (start.m_projections[0].m_segment.GetFeatureId() == + finish.m_projections[0].m_segment.GetFeatureId()) { - expectedLength = AbsDelta(start.m_projectionSegments[0].GetSegmentIdx(), - finish.m_projectionSegments[0].GetSegmentIdx()) + + expectedLength = AbsDelta(start.m_projections[0].m_segment.GetSegmentIdx(), + finish.m_projections[0].m_segment.GetSegmentIdx()) + 1; } else { - if (start.m_projectionSegments[0].GetSegmentIdx() < 2) - expectedLength += 2 - start.m_projectionSegments[0].GetSegmentIdx(); + if (start.m_projections[0].m_segment.GetSegmentIdx() < 2) + expectedLength += 2 - start.m_projections[0].m_segment.GetSegmentIdx(); else - expectedLength += start.m_projectionSegments[0].GetSegmentIdx() - 1; + expectedLength += start.m_projections[0].m_segment.GetSegmentIdx() - 1; - if (finish.m_projectionSegments[0].GetSegmentIdx() < 2) - expectedLength += 2 - finish.m_projectionSegments[0].GetSegmentIdx(); + if (finish.m_projections[0].m_segment.GetSegmentIdx() < 2) + expectedLength += 2 - finish.m_projections[0].m_segment.GetSegmentIdx(); else - expectedLength += finish.m_projectionSegments[0].GetSegmentIdx() - 1; + expectedLength += finish.m_projections[0].m_segment.GetSegmentIdx() - 1; } TestRoute(start, finish, expectedLength, nullptr, *worldGraph); } @@ -295,36 +292,46 @@ UNIT_TEST(FindPathManhattan) uint32_t expectedLength = 0; auto const startFeatureOffset = - start.m_projectionSegments[0].GetFeatureId() < kCitySize - ? start.m_projectionSegments[0].GetFeatureId() - : start.m_projectionSegments[0].GetFeatureId() - kCitySize; + start.m_projections[0].m_segment.GetFeatureId() < kCitySize + ? start.m_projections[0].m_segment.GetFeatureId() + : start.m_projections[0].m_segment.GetFeatureId() - kCitySize; auto const finishFeatureOffset = - finish.m_projectionSegments[0].GetFeatureId() < kCitySize - ? finish.m_projectionSegments[0].GetFeatureId() - : finish.m_projectionSegments[0].GetFeatureId() - kCitySize; + finish.m_projections[0].m_segment.GetFeatureId() < kCitySize + ? finish.m_projections[0].m_segment.GetFeatureId() + : finish.m_projections[0].m_segment.GetFeatureId() - kCitySize; - if (start.m_projectionSegments[0].GetFeatureId() < kCitySize == - finish.m_projectionSegments[0].GetFeatureId() < kCitySize) + if (start.m_projections[0].m_segment.GetFeatureId() < kCitySize == + finish.m_projections[0].m_segment.GetFeatureId() < kCitySize) { - uint32_t segDelta = AbsDelta(start.m_projectionSegments[0].GetSegmentIdx(), - finish.m_projectionSegments[0].GetSegmentIdx()); - if (segDelta == 0 && start.m_projectionSegments[0].GetFeatureId() != - finish.m_projectionSegments[0].GetFeatureId()) + uint32_t segDelta = AbsDelta(start.m_projections[0].m_segment.GetSegmentIdx(), + finish.m_projections[0].m_segment.GetSegmentIdx()); + if (segDelta == 0 && start.m_projections[0].m_segment.GetFeatureId() != + finish.m_projections[0].m_segment.GetFeatureId()) segDelta = 1; expectedLength += segDelta; expectedLength += AbsDelta(startFeatureOffset, finishFeatureOffset) + 1; } else { - if (start.m_projectionSegments[0].GetSegmentIdx() < finishFeatureOffset) - expectedLength += finishFeatureOffset - start.m_projectionSegments[0].GetSegmentIdx(); + if (start.m_projections[0].m_segment.GetSegmentIdx() < finishFeatureOffset) + { + expectedLength += finishFeatureOffset - start.m_projections[0].m_segment.GetSegmentIdx(); + } else - expectedLength += start.m_projectionSegments[0].GetSegmentIdx() - finishFeatureOffset + 1; - - if (finish.m_projectionSegments[0].GetSegmentIdx() < startFeatureOffset) - expectedLength += startFeatureOffset - finish.m_projectionSegments[0].GetSegmentIdx(); + { + expectedLength += + start.m_projections[0].m_segment.GetSegmentIdx() - finishFeatureOffset + 1; + } + + if (finish.m_projections[0].m_segment.GetSegmentIdx() < startFeatureOffset) + { + expectedLength += startFeatureOffset - finish.m_projections[0].m_segment.GetSegmentIdx(); + } else - expectedLength += finish.m_projectionSegments[0].GetSegmentIdx() - startFeatureOffset + 1; + { + expectedLength += + finish.m_projections[0].m_segment.GetSegmentIdx() - startFeatureOffset + 1; + } } TestRoute(start, finish, expectedLength, nullptr, *worldGraph); @@ -373,7 +380,7 @@ UNIT_TEST(RoadSpeed) {kTestNumMwmId, 0, 2, true}, {kTestNumMwmId, 0, 3, true}, {kTestNumMwmId, 1, 3, true}}); - TestRoute(start, finish, 6, &expectedRoute, *worldGraph); + TestRoute(start, finish, expectedRoute.size(), &expectedRoute, *worldGraph); } // Roads y: @@ -402,7 +409,40 @@ UNIT_TEST(OneSegmentWay) vector<Segment> const expectedRoute( {{kTestNumMwmId, 0 /* featureId */, 0 /* seg id */, true /* forward */}}); - TestRoute(start, finish, 1 /* expectedLength */, &expectedRoute, *worldGraph); + TestRoute(start, finish, expectedRoute.size(), &expectedRoute, *worldGraph); +} + +// +// Roads y: +// +// R0 * - - - - - - - ->* 0 +// ^ ^ +// finish start +// +// x: 0 1 2 3 +// +UNIT_TEST(OneSegmentWayBackward) +{ + unique_ptr<TestGeometryLoader> loader = make_unique<TestGeometryLoader>(); + + loader->AddRoad(0 /* featureId */, true /* one way */, 1.0 /* speed */, + RoadGeometry::Points({{0.0, 0.0}, {3.0, 0.0}})); + + traffic::TrafficCache const trafficCache; + shared_ptr<EdgeEstimator> estimator = CreateEstimatorForCar(trafficCache); + unique_ptr<WorldGraph> worldGraph = BuildWorldGraph(move(loader), estimator, vector<Joint>()); + + auto const start = IndexGraphStarter::MakeFakeEnding( + Segment(kTestNumMwmId, 0, 0, true /* forward */), m2::PointD(2, 0), *worldGraph); + auto const finish = IndexGraphStarter::MakeFakeEnding( + Segment(kTestNumMwmId, 0, 0, true /* forward */), m2::PointD(1, 0), *worldGraph); + + IndexGraphStarter starter(start, finish, 0 /* fakeNumerationStart */, false /* strictForward */, + *worldGraph); + vector<Segment> route; + double timeSec; + auto const resultCode = CalculateRoute(starter, route, timeSec); + TEST_EQUAL(resultCode, AStarAlgorithm<IndexGraphStarter>::Result::NoPath, ()); } // @@ -541,7 +581,7 @@ UNIT_CLASS_TEST(RestrictionTest, LoopGraph) {kTestNumMwmId, 0, 7, false}, {kTestNumMwmId, 0, 6, false}, {kTestNumMwmId, 2, 0, true}}; - TestRoute(start, finish, 7, &expectedRoute, *m_graph); + TestRoute(start, finish, expectedRoute.size(), &expectedRoute, *m_graph); } UNIT_TEST(IndexGraph_OnlyTopology_1) diff --git a/routing/routing_tests/index_graph_tools.cpp b/routing/routing_tests/index_graph_tools.cpp index 78c3624408..f8574dff24 100644 --- a/routing/routing_tests/index_graph_tools.cpp +++ b/routing/routing_tests/index_graph_tools.cpp @@ -141,11 +141,9 @@ bool TestIndexGraphTopology::FindPath(Vertex start, Vertex finish, double & path for (size_t i = 1; i + 1 < routeSegs.size(); ++i) { auto seg = routeSegs[i]; - if (IndexGraphStarter::IsFakeSegment(seg)) - { - if (!starter.ConvertToReal(seg)) - continue; - } + if (!starter.ConvertToReal(seg)) + continue; + auto const it = builder.m_segmentToEdge.find(seg); CHECK(it != builder.m_segmentToEdge.cend(), ()); auto const & edge = it->second; diff --git a/routing/routing_tests/restriction_test.cpp b/routing/routing_tests/restriction_test.cpp index fd9073b539..012cf7ecaa 100644 --- a/routing/routing_tests/restriction_test.cpp +++ b/routing/routing_tests/restriction_test.cpp @@ -807,7 +807,7 @@ unique_ptr<WorldGraph> BuildLineGraph() loader->AddRoad(0 /* feature id */, true /* one way */, 1.0 /* speed */, RoadGeometry::Points({{0.0, 0.0}, {0.0, 1.0}})); loader->AddRoad(1 /* feature id */, false /* one way */, 1.0 /* speed */, - RoadGeometry::Points({{1.0, 0.0}, {2.0, 0.0}, {3.0, 0.0}, {3.0, 0.0}})); + RoadGeometry::Points({{1.0, 0.0}, {2.0, 0.0}, {3.0, 0.0}, {4.0, 0.0}})); loader->AddRoad(2 /* feature id */, true /* one way */, 1.0 /* speed */, RoadGeometry::Points({{4.0, 0.0}, {5.0, 0.0}})); diff --git a/xcode/routing/routing.xcodeproj/project.pbxproj b/xcode/routing/routing.xcodeproj/project.pbxproj index 0911dfab12..b017aa98cd 100644 --- a/xcode/routing/routing.xcodeproj/project.pbxproj +++ b/xcode/routing/routing.xcodeproj/project.pbxproj @@ -59,6 +59,7 @@ 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 */; }; + 40C227FE1F61C07C0046696C /* fake_edges_container.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 40C227FD1F61C07C0046696C /* fake_edges_container.hpp */; }; 56099E291CC7C97D00A7772A /* loaded_path_segment.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 56099E251CC7C97D00A7772A /* loaded_path_segment.hpp */; }; 56099E2A1CC7C97D00A7772A /* routing_result_graph.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 56099E261CC7C97D00A7772A /* routing_result_graph.hpp */; }; 56099E2B1CC7C97D00A7772A /* turn_candidate.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 56099E271CC7C97D00A7772A /* turn_candidate.hpp */; }; @@ -340,6 +341,7 @@ 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>"; }; + 40C227FD1F61C07C0046696C /* fake_edges_container.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = fake_edges_container.hpp; sourceTree = "<group>"; }; 56099E251CC7C97D00A7772A /* loaded_path_segment.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = loaded_path_segment.hpp; sourceTree = "<group>"; }; 56099E261CC7C97D00A7772A /* routing_result_graph.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = routing_result_graph.hpp; sourceTree = "<group>"; }; 56099E271CC7C97D00A7772A /* turn_candidate.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = turn_candidate.hpp; sourceTree = "<group>"; }; @@ -813,6 +815,7 @@ 56CC5A361E3884960016AC46 /* cross_mwm_index_graph.hpp */, 0C5FEC521DDE191E0017688C /* edge_estimator.cpp */, 0C5FEC531DDE191E0017688C /* edge_estimator.hpp */, + 40C227FD1F61C07C0046696C /* fake_edges_container.hpp */, 674F9BBC1B0A580E00704FFA /* features_road_graph.cpp */, 674F9BBD1B0A580E00704FFA /* features_road_graph.hpp */, 0C5FEC561DDE192A0017688C /* geometry.cpp */, @@ -991,6 +994,7 @@ 0C090C881E4E276700D52AFD /* world_graph.hpp in Headers */, 0C08AA351DF83223004195DD /* index_graph_serialization.hpp in Headers */, 5694CECD1EBA25F7004576D3 /* road_access.hpp in Headers */, + 40C227FE1F61C07C0046696C /* fake_edges_container.hpp in Headers */, 670D049F1B0B4A970013A7AC /* nearest_edge_finder.hpp in Headers */, A120B34F1B4A7C0A002F3808 /* online_absent_fetcher.hpp in Headers */, 0C62BFE61E8ADC3100055A79 /* coding.hpp in Headers */, |