Eclipse SUMO - Simulation of Urban MObility
NBAlgorithms.h
Go to the documentation of this file.
1 /****************************************************************************/
2 // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo
3 // Copyright (C) 2012-2019 German Aerospace Center (DLR) and others.
4 // This program and the accompanying materials
5 // are made available under the terms of the Eclipse Public License v2.0
6 // which accompanies this distribution, and is available at
7 // http://www.eclipse.org/legal/epl-v20.html
8 // SPDX-License-Identifier: EPL-2.0
9 /****************************************************************************/
15 // Algorithms for network computation
16 /****************************************************************************/
17 #ifndef NBAlgorithms_h
18 #define NBAlgorithms_h
19 
20 
21 // ===========================================================================
22 // included modules
23 // ===========================================================================
24 #include <config.h>
25 
26 #include <map>
27 #include "NBEdgeCont.h"
28 #include "NBNodeCont.h"
29 
30 // ===========================================================================
31 // class declarations
32 // ===========================================================================
33 class NBEdge;
34 class NBNode;
35 
36 // ===========================================================================
37 // class definitions
38 // ===========================================================================
39 // ---------------------------------------------------------------------------
40 // NBTurningDirectionsComputer
41 // ---------------------------------------------------------------------------
42 /* @class NBTurningDirectionsComputer
43  * @brief Computes turnaround destinations for all edges (if exist)
44  */
46 public:
51  static void computeTurnDirections(NBNodeCont& nc, bool warn = true);
52 
58  static void computeTurnDirectionsForNode(NBNode* node, bool warn);
59 
60 private:
67  struct Combination {
70  double angle;
71  };
72 
73 
78  public:
80  int operator()(const Combination& c1, const Combination& c2) const {
81  if (c1.angle != c2.angle) {
82  return c1.angle > c2.angle;
83  }
84  if (c1.from != c2.from) {
85  return c1.from->getID() < c2.from->getID();
86  }
87  return c1.to->getID() < c2.to->getID();
88  }
89  };
90 };
91 
92 
93 
94 // ---------------------------------------------------------------------------
95 // NBNodesEdgesSorter
96 // ---------------------------------------------------------------------------
97 /* @class NBNodesEdgesSorter
98  * @brief Sorts a node's edges clockwise regarding driving direction
99  */
101 public:
106  static void sortNodesEdges(NBNodeCont& nc, bool useNodeShape = false);
107 
113  public:
114  explicit crossing_by_junction_angle_sorter(const NBNode* node, const EdgeVector& ordering);
115 
116  int operator()(const NBNode::Crossing* c1, const NBNode::Crossing* c2) const {
117  const int r1 = getMinRank(c1->edges);
118  const int r2 = getMinRank(c2->edges);
119  if (r1 == r2) {
120  return c1->edges.size() > c2->edges.size();
121  } else {
122  return (int)(r1 < r2);
123  }
124  }
125 
126  private:
128  int getMinRank(const EdgeVector& e) const {
129  int result = (int)myOrdering.size();
130  for (EdgeVector::const_iterator it = e.begin(); it != e.end(); ++it) {
131  int rank = (int)std::distance(myOrdering.begin(), std::find(myOrdering.begin(), myOrdering.end(), *it));
132  result = MIN2(result, rank);
133  }
134  return result;
135  }
136 
137  private:
139 
140  private:
143 
144  };
150  static void swapWhenReversed(const NBNode* const n,
151  const std::vector<NBEdge*>::iterator& i1,
152  const std::vector<NBEdge*>::iterator& i2);
153 
154 
159  public:
161  int operator()(NBEdge* e1, NBEdge* e2) const {
162  return getConvAngle(e1) < getConvAngle(e2);
163  }
164 
165  protected:
167  double getConvAngle(NBEdge* e) const {
168  double angle = e->getAngleAtNode(myNode);
169  if (angle < 0.) {
170  angle = 360. + angle;
171  }
172  // convert angle if the edge is an outgoing edge
173  if (e->getFromNode() == myNode) {
174  angle += (double) 180.;
175  if (angle >= (double) 360.) {
176  angle -= (double) 360.;
177  }
178  }
179  if (angle < 0.1 || angle > 359.9) {
180  angle = (double) 0.;
181  }
182  assert(angle >= 0 && angle < (double)360);
183  return angle;
184  }
185 
186  private:
189 
190  };
191 
192 };
193 
194 
195 
196 // ---------------------------------------------------------------------------
197 // NBNodeTypeComputer
198 // ---------------------------------------------------------------------------
199 /* @class NBNodeTypeComputer
200  * @brief Computes node types
201  */
203 public:
207  static void computeNodeTypes(NBNodeCont& nc, NBTrafficLightLogicCont& tlc);
208 
213 
215  static bool isRailwayNode(const NBNode* n);
216 };
217 
218 
219 
220 // ---------------------------------------------------------------------------
221 // NBEdgePriorityComputer
222 // ---------------------------------------------------------------------------
223 /* @class NBEdgePriorityComputer
224  * @brief Computes edge priorities within a node
225  */
227 public:
231  static void computeEdgePriorities(NBNodeCont& nc);
232 
233 private:
237  static void setPriorityJunctionPriorities(NBNode& n);
238 
240  static void markBestParallel(const NBNode& n, NBEdge* bestFirst, NBEdge* bestSecond);
241 
248  static NBEdge* extractAndMarkFirst(NBNode& n, std::vector<NBEdge*>& s, int prio = 1);
249 
255  static bool samePriority(const NBEdge* const e1, const NBEdge* const e2);
256 
258  static bool hasDifferentPriorities(const EdgeVector& edges, const NBEdge* excluded);
259 
260 };
261 
262 #endif
263 
264 /****************************************************************************/
265 
NBNodeTypeComputer::validateRailCrossings
static void validateRailCrossings(NBNodeCont &nc, NBTrafficLightLogicCont &tlc)
Checks rail_crossing for validity.
Definition: NBAlgorithms.cpp:236
NBNodesEdgesSorter::crossing_by_junction_angle_sorter::operator()
int operator()(const NBNode::Crossing *c1, const NBNode::Crossing *c2) const
Definition: NBAlgorithms.h:116
NBTurningDirectionsComputer::Combination::to
NBEdge * to
Definition: NBAlgorithms.h:69
MIN2
T MIN2(T a, T b)
Definition: StdDefs.h:73
NBNodesEdgesSorter
Definition: NBAlgorithms.h:100
NBTurningDirectionsComputer::Combination::from
NBEdge * from
Definition: NBAlgorithms.h:68
NBEdgePriorityComputer::extractAndMarkFirst
static NBEdge * extractAndMarkFirst(NBNode &n, std::vector< NBEdge * > &s, int prio=1)
Sets the priorites in case of a priority junction.
Definition: NBAlgorithms.cpp:470
NBEdgePriorityComputer::samePriority
static bool samePriority(const NBEdge *const e1, const NBEdge *const e2)
Returns whether both edges have the same priority.
Definition: NBAlgorithms.cpp:482
NBNodesEdgesSorter::crossing_by_junction_angle_sorter::crossing_by_junction_angle_sorter
crossing_by_junction_angle_sorter(const NBNode *node, const EdgeVector &ordering)
Definition: NBAlgorithms.cpp:511
NBTrafficLightLogicCont
A container for traffic light definitions and built programs.
Definition: NBTrafficLightLogicCont.h:57
NBEdgePriorityComputer::setPriorityJunctionPriorities
static void setPriorityJunctionPriorities(NBNode &n)
Sets the priorites in case of a priority junction.
Definition: NBAlgorithms.cpp:325
NBNodesEdgesSorter::swapWhenReversed
static void swapWhenReversed(const NBNode *const n, const std::vector< NBEdge * >::iterator &i1, const std::vector< NBEdge * >::iterator &i2)
Assures correct order for same-angle opposite-direction edges.
Definition: NBAlgorithms.cpp:144
EdgeVector
std::vector< NBEdge * > EdgeVector
container for (sorted) edges
Definition: NBCont.h:34
NBTurningDirectionsComputer
Definition: NBAlgorithms.h:45
NBNodesEdgesSorter::crossing_by_junction_angle_sorter::getMinRank
int getMinRank(const EdgeVector &e) const
retrieves the minimum index in myAllEdges
Definition: NBAlgorithms.h:128
NBEdgeCont.h
NBNodesEdgesSorter::crossing_by_junction_angle_sorter::myOrdering
EdgeVector myOrdering
Definition: NBAlgorithms.h:138
NBEdgePriorityComputer::markBestParallel
static void markBestParallel(const NBNode &n, NBEdge *bestFirst, NBEdge *bestSecond)
set priority for edges that are parallel to the best edges
Definition: NBAlgorithms.cpp:450
NBEdgePriorityComputer::computeEdgePriorities
static void computeEdgePriorities(NBNodeCont &nc)
Computes edge priorities within a node.
Definition: NBAlgorithms.cpp:299
NBEdgePriorityComputer
Definition: NBAlgorithms.h:226
NBNodesEdgesSorter::sortNodesEdges
static void sortNodesEdges(NBNodeCont &nc, bool useNodeShape=false)
Sorts a node's edges clockwise regarding driving direction.
Definition: NBAlgorithms.cpp:136
NBNodeCont
Container for nodes during the netbuilding process.
Definition: NBNodeCont.h:59
NBTurningDirectionsComputer::combination_by_angle_sorter
Sorts "Combination"s by decreasing angle.
Definition: NBAlgorithms.h:77
NBEdge
The representation of a single edge during network building.
Definition: NBEdge.h:91
NBTurningDirectionsComputer::Combination::angle
double angle
Definition: NBAlgorithms.h:70
NBTurningDirectionsComputer::computeTurnDirectionsForNode
static void computeTurnDirectionsForNode(NBNode *node, bool warn)
Computes turnaround destinations for all incoming edges of the given nodes (if any)
Definition: NBAlgorithms.cpp:54
NBNodeTypeComputer
Definition: NBAlgorithms.h:202
NBTurningDirectionsComputer::Combination
Stores the information about the angle between an incoming ("from") and an outgoing ("to") edge.
Definition: NBAlgorithms.h:67
NBTurningDirectionsComputer::combination_by_angle_sorter::combination_by_angle_sorter
combination_by_angle_sorter()
Definition: NBAlgorithms.h:79
NBNodesEdgesSorter::edge_by_junction_angle_sorter::edge_by_junction_angle_sorter
edge_by_junction_angle_sorter(NBNode *n)
Definition: NBAlgorithms.h:160
NBNodesEdgesSorter::edge_by_junction_angle_sorter::getConvAngle
double getConvAngle(NBEdge *e) const
Converts the angle of the edge if it is an incoming edge.
Definition: NBAlgorithms.h:167
NBNodesEdgesSorter::edge_by_junction_angle_sorter::operator()
int operator()(NBEdge *e1, NBEdge *e2) const
Definition: NBAlgorithms.h:161
NBNodeCont.h
NBEdgePriorityComputer::hasDifferentPriorities
static bool hasDifferentPriorities(const EdgeVector &edges, const NBEdge *excluded)
return whether the priorite attribute can be used to distinguish the edges
Definition: NBAlgorithms.cpp:497
NBTurningDirectionsComputer::combination_by_angle_sorter::operator()
int operator()(const Combination &c1, const Combination &c2) const
Definition: NBAlgorithms.h:80
NBNode::Crossing::edges
EdgeVector edges
The edges being crossed.
Definition: NBNode.h:137
NBNodeTypeComputer::isRailwayNode
static bool isRailwayNode(const NBNode *n)
whether the given node only has rail edges
Definition: NBAlgorithms.cpp:282
config.h
NBNodesEdgesSorter::crossing_by_junction_angle_sorter::operator=
crossing_by_junction_angle_sorter & operator=(const crossing_by_junction_angle_sorter &s)
invalidated assignment operator
NBNodesEdgesSorter::edge_by_junction_angle_sorter
Sorts incoming and outgoing edges clockwise around the given node.
Definition: NBAlgorithms.h:158
NBNodesEdgesSorter::edge_by_junction_angle_sorter::myNode
NBNode * myNode
The node to compute the relative angle of.
Definition: NBAlgorithms.h:188
NBTurningDirectionsComputer::computeTurnDirections
static void computeTurnDirections(NBNodeCont &nc, bool warn=true)
Computes turnaround destinations for all edges (if exist)
Definition: NBAlgorithms.cpp:47
NBNode
Represents a single node (junction) during network building.
Definition: NBNode.h:67
NBNode::Crossing
A definition of a pedestrian crossing.
Definition: NBNode.h:131
NBEdge::getAngleAtNode
double getAngleAtNode(const NBNode *const node) const
Returns the angle of the edge's geometry at the given node.
Definition: NBEdge.cpp:1836
NBNodeTypeComputer::computeNodeTypes
static void computeNodeTypes(NBNodeCont &nc, NBTrafficLightLogicCont &tlc)
Computes node types.
Definition: NBAlgorithms.cpp:163
NBEdge::getFromNode
NBNode * getFromNode() const
Returns the origin node of the edge.
Definition: NBEdge.h:491
NBNodesEdgesSorter::crossing_by_junction_angle_sorter
Sorts crossings by minimum clockwise clockwise edge angle. Use the ordering found in myAllEdges of th...
Definition: NBAlgorithms.h:112
NBEdge::getID
const std::string & getID() const
Definition: NBEdge.h:1380