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
|
#pragma once
#include "geometry/point2d.hpp"
#include "base/string_utils.hpp"
#include "indexer/feature_data.hpp"
#include "std/initializer_list.hpp"
#include "std/map.hpp"
#include "std/vector.hpp"
namespace routing
{
/// The Junction class represents a node description on a road network graph
class Junction
{
public:
Junction();
Junction(m2::PointD const & point);
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 m_point < r.m_point; }
m2::PointD const & GetPoint() const { return m_point; }
private:
friend string DebugPrint(Junction const & r);
// Point of the junction
m2::PointD m_point;
};
/// The Edge class represents an edge description on a road network graph
class Edge
{
public:
static Edge MakeFake(Junction const & startJunction, Junction const & endJunction);
Edge(FeatureID featureId, bool forward, uint32_t segId, Junction const & startJunction, Junction const & endJunction);
Edge(Edge const &) = default;
Edge & operator=(Edge const &) = default;
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 bool IsFake() const { return !m_featureId.IsValid(); }
Edge GetReverseEdge() const;
bool SameRoadSegmentAndDirection(Edge const & r) const;
bool operator==(Edge const & r) const;
bool operator<(Edge const & r) const;
private:
friend string DebugPrint(Edge const & r);
// Feature for which edge is defined.
FeatureID m_featureId;
// Is the feature along the road.
bool m_forward;
// Ordinal number of the segment on the road.
uint32_t m_segId;
// Start junction of the segment on the road.
Junction m_startJunction;
// End junction of the segment on the road.
Junction m_endJunction;
};
class IRoadGraph
{
public:
typedef vector<Junction> TJunctionVector;
typedef vector<Edge> TEdgeVector;
/// 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, initializer_list<m2::PointD> const & points);
RoadInfo(RoadInfo const &) = default;
RoadInfo & operator=(RoadInfo const &) = default;
buffer_vector<m2::PointD, 32> m_points;
double m_speedKMPH;
bool m_bidirectional;
};
/// This class is responsible for loading edges in a cross.
/// It loades only outgoing edges.
class CrossEdgesLoader
{
public:
CrossEdgesLoader(m2::PointD const & cross, TEdgeVector & outgoingEdges);
void operator()(FeatureID const & featureId, RoadInfo const & roadInfo);
private:
m2::PointD const m_cross;
TEdgeVector & m_outgoingEdges;
};
virtual ~IRoadGraph() = default;
/// Finds all nearest outgoing edges, that route to the junction.
void GetOutgoingEdges(Junction const & junction, TEdgeVector & edges) const;
/// Finds all nearest ingoing edges, that route to the junction.
void GetIngoingEdges(Junction const & junction, TEdgeVector & edges) const;
/// 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, m2::PointD>> const & vicinities);
/// 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;
/// Returns max speed in KM/H
virtual double GetMaxSpeedKMPH() const = 0;
/// Calls edgesLoader on each feature which is close to cross.
virtual void ForEachFeatureClosestToCross(m2::PointD const & cross,
CrossEdgesLoader & 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, m2::PointD>> & 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
void GetEdgeTypes(Edge const & edge, feature::TypesHolder & types) const;
/// @return Types for specified junction
virtual void GetJunctionTypes(Junction const & junction, feature::TypesHolder & types) const = 0;
/// Clear all temporary buffers.
virtual void ClearState() {}
private:
/// Finds all outgoing regular (non-fake) edges for junction.
void GetRegularOutgoingEdges(Junction const & junction, TEdgeVector & edges) const;
/// Determines if the edge has been split by fake edges and if yes returns these fake edges.
bool HasBeenSplitToFakes(Edge const & edge, vector<Edge> & fakeEdges) const;
// Map of outgoing edges for junction
map<Junction, TEdgeVector> m_outgoingEdges;
};
} // namespace routing
|
