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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
|
#pragma once
#include "routing/segment.hpp"
#include "geometry/point2d.hpp"
#include "base/string_utils.hpp"
#include "indexer/feature_altitude.hpp"
#include "indexer/feature_data.hpp"
#include <initializer_list>
#include <map>
#include <vector>
namespace routing
{
double constexpr kPointsEqualEpsilon = 1e-6;
/// The Junction class represents a node description on a road network graph
class Junction
{
public:
Junction();
Junction(m2::PointD const & point, feature::TAltitude altitude);
Junction(Junction const &) = default;
Junction & operator=(Junction const &) = default;
inline bool operator==(Junction const & r) const { return m_point == r.m_point; }
inline bool operator!=(Junction const & r) const { return !(*this == r); }
inline bool operator<(Junction const & r) const { return m_point < r.m_point; }
inline m2::PointD const & GetPoint() const { return m_point; }
inline feature::TAltitude GetAltitude() const { return m_altitude; }
private:
friend string DebugPrint(Junction const & r);
// Point of the junction
m2::PointD m_point;
feature::TAltitude m_altitude;
};
inline Junction MakeJunctionForTesting(m2::PointD const & point)
{
return Junction(point, feature::kDefaultAltitudeMeters);
}
inline bool AlmostEqualAbs(Junction const & lhs, Junction const & rhs)
{
return my::AlmostEqualAbs(lhs.GetPoint(), rhs.GetPoint(), kPointsEqualEpsilon);
}
/// The Edge class represents an edge description on a road network graph
class Edge
{
enum class Type
{
Real, // An edge that corresponds to some real segment.
FakeWithRealPart, // A fake edge that is a part of some real segment.
FakeWithoutRealPart // A fake edge that is not part of any real segment.
};
public:
Edge() = default;
Edge(Edge const &) = default;
Edge & operator=(Edge const &) = default;
static Edge MakeReal(FeatureID const & featureId, bool forward, uint32_t segId,
Junction const & startJunction, Junction const & endJunction);
static Edge MakeFake(Junction const & startJunction, Junction const & endJunction);
static Edge MakeFake(Junction const & startJunction, Junction const & endJunction,
Edge const & prototype);
inline FeatureID GetFeatureId() const { return m_featureId; }
inline bool IsForward() const { return m_forward; }
inline uint32_t GetSegId() const { return m_segId; }
inline Junction const & GetStartJunction() const { return m_startJunction; }
inline Junction const & GetEndJunction() const { return m_endJunction; }
inline m2::PointD const & GetStartPoint() const { return m_startJunction.GetPoint(); }
inline m2::PointD const & GetEndPoint() const { return m_endJunction.GetPoint(); }
inline bool IsFake() const { return m_type != Type::Real; }
inline bool HasRealPart() const { return m_type != Type::FakeWithoutRealPart; }
inline m2::PointD GetDirection() const
{
return GetEndJunction().GetPoint() - GetStartJunction().GetPoint();
}
Edge GetReverseEdge() const;
bool SameRoadSegmentAndDirection(Edge const & r) const;
bool operator==(Edge const & r) const;
bool operator!=(Edge const & r) const { return !(*this == r); }
bool operator<(Edge const & r) const;
private:
Edge(Type type, FeatureID const & featureId, bool forward, uint32_t segId,
Junction const & startJunction, Junction const & endJunction);
friend string DebugPrint(Edge const & r);
Type m_type = Type::FakeWithoutRealPart;
// Feature for which edge is defined.
FeatureID m_featureId;
// Is the feature along the road.
bool m_forward = true;
// Ordinal number of the segment on the road.
uint32_t m_segId = 0;
// Start junction of the segment on the road.
Junction m_startJunction;
// End junction of the segment on the road.
Junction m_endJunction;
// Note. If |m_forward| == true index of |m_startJunction| point at the feature |m_featureId|
// is less than index |m_endJunction|.
// If |m_forward| == false index of |m_startJunction| point at the feature |m_featureId|
// is more than index |m_endJunction|.
};
class RoadGraphBase
{
public:
typedef vector<Edge> TEdgeVector;
/// Finds all nearest outgoing edges, that route to the junction.
virtual void GetOutgoingEdges(Junction const & junction, TEdgeVector & edges) const = 0;
/// Finds all nearest ingoing edges, that route to the junction.
virtual void GetIngoingEdges(Junction const & junction, TEdgeVector & edges) const = 0;
/// Returns max speed in KM/H
virtual double GetMaxSpeedKMPH() const = 0;
/// @return Types for the specified edge
virtual void GetEdgeTypes(Edge const & edge, feature::TypesHolder & types) const = 0;
/// @return Types for specified junction
virtual void GetJunctionTypes(Junction const & junction, feature::TypesHolder & types) const = 0;
// TODO: remove IsRouteEdgesImplemented and IsRouteSegmentsImplemented as soon as we get rid of
// IRoadGraph and RoadGraphRouter
virtual bool IsRouteEdgesImplemented() const;
virtual bool IsRouteSegmentsImplemented() const;
virtual void GetRouteEdges(TEdgeVector & routeEdges) const;
virtual void GetRouteSegments(std::vector<Segment> & segments) const;
};
class IRoadGraph : public RoadGraphBase
{
public:
// CheckGraphConnectivity() types aliases:
using Vertex = Junction;
using Edge = routing::Edge;
using Weight = double;
enum class Mode
{
ObeyOnewayTag,
IgnoreOnewayTag,
};
/// This struct contains the part of a feature's metadata that is
/// relevant for routing.
struct RoadInfo
{
RoadInfo();
RoadInfo(RoadInfo && ri);
RoadInfo(bool bidirectional, double speedKMPH, std::initializer_list<Junction> const & points);
RoadInfo(RoadInfo const &) = default;
RoadInfo & operator=(RoadInfo const &) = default;
buffer_vector<Junction, 32> m_junctions;
double m_speedKMPH;
bool m_bidirectional;
};
/// This class is responsible for loading edges in a cross.
class ICrossEdgesLoader
{
public:
ICrossEdgesLoader(Junction const & cross, IRoadGraph::Mode mode, TEdgeVector & edges)
: m_cross(cross), m_mode(mode), m_edges(edges)
{
}
virtual ~ICrossEdgesLoader() = default;
void operator()(FeatureID const & featureId, RoadInfo const & roadInfo)
{
LoadEdges(featureId, roadInfo);
}
private:
virtual void LoadEdges(FeatureID const & featureId, RoadInfo const & roadInfo) = 0;
protected:
template <typename TFn>
void ForEachEdge(RoadInfo const & roadInfo, TFn && fn)
{
for (size_t i = 0; i < roadInfo.m_junctions.size(); ++i)
{
if (!my::AlmostEqualAbs(m_cross.GetPoint(), roadInfo.m_junctions[i].GetPoint(),
kPointsEqualEpsilon))
{
continue;
}
if (i + 1 < roadInfo.m_junctions.size())
{
// Head of the edge.
// m_cross
// o------------>o
fn(i, roadInfo.m_junctions[i + 1], true /* forward */);
}
if (i > 0)
{
// Tail of the edge.
// m_cross
// o------------>o
fn(i - 1, roadInfo.m_junctions[i - 1], false /* backward */);
}
}
}
Junction const m_cross;
IRoadGraph::Mode const m_mode;
TEdgeVector & m_edges;
};
class CrossOutgoingLoader : public ICrossEdgesLoader
{
public:
CrossOutgoingLoader(Junction const & cross, IRoadGraph::Mode mode, TEdgeVector & edges)
: ICrossEdgesLoader(cross, mode, edges)
{
}
private:
// ICrossEdgesLoader overrides:
virtual void LoadEdges(FeatureID const & featureId, RoadInfo const & roadInfo) override;
};
class CrossIngoingLoader : public ICrossEdgesLoader
{
public:
CrossIngoingLoader(Junction const & cross, IRoadGraph::Mode mode, TEdgeVector & edges)
: ICrossEdgesLoader(cross, mode, edges)
{
}
private:
// ICrossEdgesLoader overrides:
virtual void LoadEdges(FeatureID const & featureId, RoadInfo const & roadInfo) override;
};
virtual ~IRoadGraph() = default;
virtual void GetOutgoingEdges(Junction const & junction, TEdgeVector & edges) const override;
virtual void GetIngoingEdges(Junction const & junction, TEdgeVector & edges) const override;
/// Removes all fake turns and vertices from the graph.
void ResetFakes();
/// Adds fake edges from fake position rp to real vicinity
/// positions.
void AddFakeEdges(Junction const & junction, vector<pair<Edge, Junction>> const & vicinities);
void AddOutgoingFakeEdge(Edge const & e);
void AddIngoingFakeEdge(Edge const & e);
/// Returns RoadInfo for a road corresponding to featureId.
virtual RoadInfo GetRoadInfo(FeatureID const & featureId) const = 0;
/// Returns speed in KM/H for a road corresponding to featureId.
virtual double GetSpeedKMPH(FeatureID const & featureId) const = 0;
/// Returns speed in KM/H for a road corresponding to edge.
double GetSpeedKMPH(Edge const & edge) const;
/// Calls edgesLoader on each feature which is close to cross.
virtual void ForEachFeatureClosestToCross(m2::PointD const & cross,
ICrossEdgesLoader & edgesLoader) const = 0;
/// Finds the closest edges to the point.
/// @return Array of pairs of Edge and projection point on the Edge. If there is no the closest edges
/// then returns empty array.
virtual void FindClosestEdges(m2::PointD const & point, uint32_t count,
vector<pair<Edge, Junction>> & vicinities) const = 0;
/// @return Types for the specified feature
virtual void GetFeatureTypes(FeatureID const & featureId, feature::TypesHolder & types) const = 0;
/// @return Types for the specified edge
virtual void GetEdgeTypes(Edge const & edge, feature::TypesHolder & types) const override;
virtual IRoadGraph::Mode GetMode() const = 0;
/// Clear all temporary buffers.
virtual void ClearState() {}
/// \brief Finds all outgoing regular (non-fake) edges for junction.
void GetRegularOutgoingEdges(Junction const & junction, TEdgeVector & edges) const;
/// \brief Finds all ingoing regular (non-fake) edges for junction.
void GetRegularIngoingEdges(Junction const & junction, TEdgeVector & edges) const;
/// \brief Finds all outgoing fake edges for junction.
void GetFakeOutgoingEdges(Junction const & junction, TEdgeVector & edges) const;
/// \brief Finds all ingoing fake edges for junction.
void GetFakeIngoingEdges(Junction const & junction, TEdgeVector & edges) const;
private:
void AddEdge(Junction const & j, Edge const & e, std::map<Junction, TEdgeVector> & edges);
template <typename Fn>
void ForEachFakeEdge(Fn && fn)
{
for (auto const & m : m_fakeIngoingEdges)
{
for (auto const & e : m.second)
fn(e);
}
for (auto const & m : m_fakeOutgoingEdges)
{
for (auto const & e : m.second)
fn(e);
}
}
/// \note |m_fakeIngoingEdges| and |m_fakeOutgoingEdges| map junctions to sorted vectors.
/// Items to these maps should be inserted with AddEdge() method only.
std::map<Junction, TEdgeVector> m_fakeIngoingEdges;
std::map<Junction, TEdgeVector> m_fakeOutgoingEdges;
};
string DebugPrint(IRoadGraph::Mode mode);
IRoadGraph::RoadInfo MakeRoadInfoForTesting(bool bidirectional, double speedKMPH,
std::initializer_list<m2::PointD> const & points);
inline void JunctionsToPoints(vector<Junction> const & junctions, vector<m2::PointD> & points)
{
points.resize(junctions.size());
for (size_t i = 0; i < junctions.size(); ++i)
points[i] = junctions[i].GetPoint();
}
inline void JunctionsToAltitudes(vector<Junction> const & junctions, feature::TAltitudes & altitudes)
{
altitudes.resize(junctions.size());
for (size_t i = 0; i < junctions.size(); ++i)
altitudes[i] = junctions[i].GetAltitude();
}
} // namespace routing
|