1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
|
#pragma once
#include "routing/base/astar_graph.hpp"
#include "routing/base/routing_result.hpp"
#include "routing/fake_ending.hpp"
#include "routing/fake_feature_ids.hpp"
#include "routing/fake_graph.hpp"
#include "routing/fake_vertex.hpp"
#include "routing/index_graph.hpp"
#include "routing/joint.hpp"
#include "routing/route_point.hpp"
#include "routing/route_weight.hpp"
#include "routing/segment.hpp"
#include "routing/world_graph.hpp"
#include "routing_common/num_mwm_id.hpp"
#include <cstddef>
#include <cstdint>
#include <limits>
#include <set>
#include <utility>
#include <vector>
namespace routing
{
class FakeEdgesContainer;
// IndexGraphStarter adds fake start and finish vertices for AStarAlgorithm.
class IndexGraphStarter : public AStarGraph<IndexGraph::Vertex, IndexGraph::Edge, IndexGraph::Weight>
{
public:
friend class FakeEdgesContainer;
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);
void Append(FakeEdgesContainer const & container);
WorldGraph & GetGraph() const { return m_graph; }
WorldGraphMode GetMode() const { return m_graph.GetMode(); }
Junction const & GetStartJunction() const;
Junction const & GetFinishJunction() const;
Segment GetStartSegment() const { return GetFakeSegment(m_start.m_id); }
Segment GetFinishSegment() const { return GetFakeSegment(m_finish.m_id); }
// 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;
Junction const & GetJunction(Segment const & segment, bool front) const;
Junction const & GetRouteJunction(std::vector<Segment> const & route, size_t pointIndex) const;
m2::PointD const & GetPoint(Segment const & segment, bool front) const;
bool IsRoutingOptionsGood(Segment const & segment) const;
uint32_t GetNumFakeSegments() const
{
// Maximal number of fake segments in fake graph is numeric_limits<uint32_t>::max()
// because segment idx type is uint32_t.
CHECK_LESS_OR_EQUAL(m_fake.GetSize(), std::numeric_limits<uint32_t>::max(), ());
return static_cast<uint32_t>(m_fake.GetSize());
}
std::set<NumMwmId> GetMwms() const;
std::set<NumMwmId> GetStartMwms() const;
std::set<NumMwmId> GetFinishMwms() const;
// Checks whether |weight| meets non-pass-through crossing restrictions according to placement of
// start and finish in pass-through/non-pass-through area and number of non-pass-through crosses.
bool CheckLength(RouteWeight const & weight);
void GetEdgeList(Segment const & segment, bool isOutgoing,
std::vector<JointEdge> & edges, std::vector<RouteWeight> & parentWeights) const
{
return m_graph.GetEdgeList(segment, isOutgoing, edges, parentWeights);
}
void GetEdgesList(Segment const & segment, bool isOutgoing,
std::vector<SegmentEdge> & edges) const;
void GetOutgoingEdgesList(Vertex const & segment, std::vector<Edge> & edges) override
{
GetEdgesList(segment, true /* isOutgoing */, edges);
}
void GetIngoingEdgesList(Vertex const & segment, std::vector<Edge> & edges) override
{
GetEdgesList(segment, false /* isOutgoing */, edges);
}
RouteWeight HeuristicCostEstimate(Vertex const & from, Vertex const & to) override
{
return m_graph.HeuristicCostEstimate(GetPoint(from, true /* front */),
GetPoint(to, true /* front */));
}
RouteWeight HeuristicCostEstimate(Vertex const & from, m2::PointD const & to) const
{
return m_graph.HeuristicCostEstimate(GetPoint(from, true /* front */), to);
}
bool IsJoint(Segment const & segment, bool fromStart)
{
return GetGraph().GetIndexGraph(segment.GetMwmId()).IsJoint(segment.GetRoadPoint(fromStart));
}
RouteWeight CalcSegmentWeight(Segment const & segment) const;
double CalcSegmentETA(Segment const & segment) const;
~IndexGraphStarter() override = default;
private:
// Start or finish ending information.
struct Ending
{
bool OverlapsWithMwm(NumMwmId mwmId) const;
// Fake segment id.
uint32_t m_id = 0;
// Real segments connected to the ending.
std::set<Segment> m_real;
};
static Segment GetFakeSegment(uint32_t segmentIdx)
{
// We currently ignore |isForward| and use FakeGraph to get ingoing/outgoing.
// But all fake segments are oneway and placement of segment head and tail
// correspond forward direction.
return Segment(kFakeNumMwmId, kFakeFeatureId, segmentIdx, true /* isForward */);
}
static Segment GetFakeSegmentAndIncr(uint32_t & segmentIdx)
{
CHECK_LESS(segmentIdx, std::numeric_limits<uint32_t>::max(), ());
return GetFakeSegment(segmentIdx++);
}
// 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,
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);
// Adds fake edges of type PartOfReal which correspond real edges from |edges| and are connected
// to |segment|
void AddFakeEdges(Segment const & segment, bool isOutgoing, std::vector<SegmentEdge> & edges) const;
// Checks whether ending belongs to pass-through or non-pass-through zone.
bool EndingPassThroughAllowed(Ending const & ending);
// Start segment is located in a pass-through/non-pass-through area.
bool StartPassThroughAllowed();
// Finish segment is located in a pass-through/non-pass-through area.
bool FinishPassThroughAllowed();
static uint32_t constexpr kFakeFeatureId = FakeFeatureIds::kIndexGraphStarterId;
WorldGraph & m_graph;
// Start segment id
Ending m_start;
// Finish segment id
Ending m_finish;
double m_startToFinishDistanceM;
FakeGraph<Segment, FakeVertex> m_fake;
RoutingOptions m_avoidRoutingOptions;
};
} // namespace routing
|
