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-2022 German Aerospace Center (DLR) and others.
4// This program and the accompanying materials are made available under the
5// terms of the Eclipse Public License 2.0 which is available at
6// https://www.eclipse.org/legal/epl-2.0/
7// This Source Code may also be made available under the following Secondary
8// Licenses when the conditions for such availability set forth in the Eclipse
9// Public License 2.0 are satisfied: GNU General Public License, version 2
10// or later which is available at
11// https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
12// SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
13/****************************************************************************/
19// Algorithms for network computation
20/****************************************************************************/
21#pragma once
22#include <config.h>
23
24#include <map>
25#include "NBEdgeCont.h"
26#include "NBNodeCont.h"
27
28// ===========================================================================
29// class declarations
30// ===========================================================================
31class NBEdge;
32class NBNode;
33
34// ===========================================================================
35// class definitions
36// ===========================================================================
37// ---------------------------------------------------------------------------
38// NBTurningDirectionsComputer
39// ---------------------------------------------------------------------------
40/* @class NBTurningDirectionsComputer
41 * @brief Computes turnaround destinations for all edges (if exist)
42 */
44public:
49 static void computeTurnDirections(NBNodeCont& nc, bool warn = true);
50
56 static void computeTurnDirectionsForNode(NBNode* node, bool warn);
57
58private:
65 struct Combination {
68 double angle;
69 };
70
71
76 public:
78 int operator()(const Combination& c1, const Combination& c2) const {
79 if (c1.angle != c2.angle) {
80 return c1.angle > c2.angle;
81 }
82 if (c1.from != c2.from) {
83 return c1.from->getID() < c2.from->getID();
84 }
85 return c1.to->getID() < c2.to->getID();
86 }
87 };
88};
89
90
91
92// ---------------------------------------------------------------------------
93// NBNodesEdgesSorter
94// ---------------------------------------------------------------------------
95/* @class NBNodesEdgesSorter
96 * @brief Sorts a node's edges clockwise regarding driving direction
97 */
99public:
104 static void sortNodesEdges(NBNodeCont& nc, bool useNodeShape = false);
105
111 public:
112 explicit crossing_by_junction_angle_sorter(const NBNode* node, const EdgeVector& ordering);
113
114 int operator()(const std::unique_ptr<NBNode::Crossing>& c1, const std::unique_ptr<NBNode::Crossing>& c2) const {
115 const int r1 = getMinRank(c1->edges);
116 const int r2 = getMinRank(c2->edges);
117 if (r1 == r2) {
118 return c1->edges.size() > c2->edges.size();
119 } else {
120 return (int)(r1 < r2);
121 }
122 }
123
124 private:
126 int getMinRank(const EdgeVector& e) const {
127 int result = (int)myOrdering.size();
128 for (EdgeVector::const_iterator it = e.begin(); it != e.end(); ++it) {
129 int rank = (int)std::distance(myOrdering.begin(), std::find(myOrdering.begin(), myOrdering.end(), *it));
130 result = MIN2(result, rank);
131 }
132 return result;
133 }
134
135 private:
137 };
138
144 static void swapWhenReversed(const NBNode* const n,
145 const std::vector<NBEdge*>::iterator& i1,
146 const std::vector<NBEdge*>::iterator& i2);
147
148
153 public:
155 int operator()(NBEdge* e1, NBEdge* e2) const {
156 return getConvAngle(e1) < getConvAngle(e2);
157 }
158
159 protected:
161 double getConvAngle(NBEdge* e) const {
162 double angle = e->getAngleAtNode(myNode);
163 if (angle < 0.) {
164 angle = 360. + angle;
165 }
166 // convert angle if the edge is an outgoing edge
167 if (e->getFromNode() == myNode) {
168 angle += (double) 180.;
169 if (angle >= (double) 360.) {
170 angle -= (double) 360.;
171 }
172 }
173 if (angle < 0.1 || angle > 359.9) {
174 angle = (double) 0.;
175 }
176 assert(angle >= 0 && angle < (double)360);
177 return angle;
178 }
179
180 private:
183
184 };
185
186};
187
188
189
190// ---------------------------------------------------------------------------
191// NBNodeTypeComputer
192// ---------------------------------------------------------------------------
193/* @class NBNodeTypeComputer
194 * @brief Computes node types
195 */
197public:
202
207
209 static bool isRailwayNode(const NBNode* n);
210};
211
212
213
214// ---------------------------------------------------------------------------
215// NBEdgePriorityComputer
216// ---------------------------------------------------------------------------
217/* @class NBEdgePriorityComputer
218 * @brief Computes edge priorities within a node
219 */
221public:
225 static void computeEdgePriorities(NBNodeCont& nc);
226
227private:
231 static void setPriorityJunctionPriorities(NBNode& n, bool forceStraight = false);
232
234 static double getScore(const NBEdge* e1, const NBEdge* e2, int minPrio, int maxPrio, int maxNumLanes, double maxSpeed);
235
237 static void markBestParallel(const NBNode& n, NBEdge* bestFirst, NBEdge* bestSecond);
238
245 static NBEdge* extractAndMarkFirst(NBNode& n, std::vector<NBEdge*>& s, int prio = 1);
246
252 static bool samePriority(const NBEdge* const e1, const NBEdge* const e2);
253
255 static bool hasDifferentPriorities(const EdgeVector& edges, const NBEdge* excluded);
256
257};
std::vector< NBEdge * > EdgeVector
container for (sorted) edges
Definition: NBCont.h:42
T MIN2(T a, T b)
Definition: StdDefs.h:71
The representation of a single edge during network building.
Definition: NBEdge.h:92
const std::string & getID() const
Definition: NBEdge.h:1526
NBNode * getFromNode() const
Returns the origin node of the edge.
Definition: NBEdge.h:545
double getAngleAtNode(const NBNode *const node) const
Returns the angle of the edge's geometry at the given node.
Definition: NBEdge.cpp:2083
static double getScore(const NBEdge *e1, const NBEdge *e2, int minPrio, int maxPrio, int maxNumLanes, double maxSpeed)
score pair of edges for multi-criteria evaluatoin of angle, priority, laneNumber and speed
static void markBestParallel(const NBNode &n, NBEdge *bestFirst, NBEdge *bestSecond)
set priority for edges that are parallel to the best edges
static NBEdge * extractAndMarkFirst(NBNode &n, std::vector< NBEdge * > &s, int prio=1)
Sets the priorites in case of a priority junction.
static bool hasDifferentPriorities(const EdgeVector &edges, const NBEdge *excluded)
return whether the priorite attribute can be used to distinguish the edges
static void computeEdgePriorities(NBNodeCont &nc)
Computes edge priorities within a node.
static void setPriorityJunctionPriorities(NBNode &n, bool forceStraight=false)
Sets the priorites in case of a priority junction.
static bool samePriority(const NBEdge *const e1, const NBEdge *const e2)
Returns whether both edges have the same priority.
Container for nodes during the netbuilding process.
Definition: NBNodeCont.h:58
Represents a single node (junction) during network building.
Definition: NBNode.h:66
static bool isRailwayNode(const NBNode *n)
whether the given node only has rail edges
static void computeNodeTypes(NBNodeCont &nc, NBTrafficLightLogicCont &tlc)
Computes node types.
static void validateRailCrossings(NBNodeCont &nc, NBTrafficLightLogicCont &tlc)
Checks rail_crossing for validity.
Sorts crossings by minimum clockwise clockwise edge angle. Use the ordering found in myAllEdges of th...
Definition: NBAlgorithms.h:110
int getMinRank(const EdgeVector &e) const
retrieves the minimum index in myAllEdges
Definition: NBAlgorithms.h:126
crossing_by_junction_angle_sorter(const NBNode *node, const EdgeVector &ordering)
int operator()(const std::unique_ptr< NBNode::Crossing > &c1, const std::unique_ptr< NBNode::Crossing > &c2) const
Definition: NBAlgorithms.h:114
Sorts incoming and outgoing edges clockwise around the given node.
Definition: NBAlgorithms.h:152
int operator()(NBEdge *e1, NBEdge *e2) const
Definition: NBAlgorithms.h:155
NBNode * myNode
The node to compute the relative angle of.
Definition: NBAlgorithms.h:182
double getConvAngle(NBEdge *e) const
Converts the angle of the edge if it is an incoming edge.
Definition: NBAlgorithms.h:161
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.
static void sortNodesEdges(NBNodeCont &nc, bool useNodeShape=false)
Sorts a node's edges clockwise regarding driving direction.
A container for traffic light definitions and built programs.
Sorts "Combination"s by decreasing angle.
Definition: NBAlgorithms.h:75
int operator()(const Combination &c1, const Combination &c2) const
Definition: NBAlgorithms.h:78
static void computeTurnDirections(NBNodeCont &nc, bool warn=true)
Computes turnaround destinations for all edges (if exist)
static void computeTurnDirectionsForNode(NBNode *node, bool warn)
Computes turnaround destinations for all incoming edges of the given nodes (if any)
Stores the information about the angle between an incoming ("from") and an outgoing ("to") edge.
Definition: NBAlgorithms.h:65