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.dev/sumo
3// Copyright (C) 2012-2023 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
59 static double getFarAngleAtNode(const NBEdge* e, const NBNode* n, double dist = 50);
60
61private:
68 struct Combination {
71 double angle;
72 };
73
74
79 public:
81 int operator()(const Combination& c1, const Combination& c2) const {
82 if (c1.angle != c2.angle) {
83 return c1.angle > c2.angle;
84 }
85 if (c1.from != c2.from) {
86 if (c1.to == c2.to && c1.from->getPermissions() != c2.from->getPermissions()) {
87 if (c1.from->getPermissions() == c1.to->getPermissions()) {
88 return true;
89 } else if (c2.from->getPermissions() == c1.to->getPermissions()) {
90 return false;
91 }
92 }
93 return c1.from->getID() < c2.from->getID();
94 }
95 if (c1.to->getPermissions() != c2.to->getPermissions()) {
96 if (c1.to->getPermissions() == c1.from->getPermissions()) {
97 return true;
98 } else if (c2.to->getPermissions() == c1.from->getPermissions()) {
99 return false;
100 }
101 }
102 return c1.to->getID() < c2.to->getID();
103 }
104 };
105};
106
107
108
109// ---------------------------------------------------------------------------
110// NBNodesEdgesSorter
111// ---------------------------------------------------------------------------
112/* @class NBNodesEdgesSorter
113 * @brief Sorts a node's edges clockwise regarding driving direction
114 */
116public:
121 static void sortNodesEdges(NBNodeCont& nc, bool useNodeShape = false);
122
128 public:
129 explicit crossing_by_junction_angle_sorter(const NBNode* node, const EdgeVector& ordering);
130
131 int operator()(const std::unique_ptr<NBNode::Crossing>& c1, const std::unique_ptr<NBNode::Crossing>& c2) const {
132 const int r1 = getMinRank(c1->edges);
133 const int r2 = getMinRank(c2->edges);
134 if (r1 == r2) {
135 return c1->edges.size() > c2->edges.size();
136 } else {
137 return (int)(r1 < r2);
138 }
139 }
140
141 private:
143 int getMinRank(const EdgeVector& e) const {
144 int result = (int)myOrdering.size();
145 for (EdgeVector::const_iterator it = e.begin(); it != e.end(); ++it) {
146 int rank = (int)std::distance(myOrdering.begin(), std::find(myOrdering.begin(), myOrdering.end(), *it));
147 result = MIN2(result, rank);
148 }
149 return result;
150 }
151
152 private:
154 };
155
161 static void swapWhenReversed(const NBNode* const n,
162 const std::vector<NBEdge*>::iterator& i1,
163 const std::vector<NBEdge*>::iterator& i2);
164
165
170 public:
172 int operator()(NBEdge* e1, NBEdge* e2) const {
173 return getConvAngle(e1) < getConvAngle(e2);
174 }
175
176 protected:
178 double getConvAngle(NBEdge* e) const {
179 double angle = e->getAngleAtNode(myNode);
180 if (angle < 0.) {
181 angle = 360. + angle;
182 }
183 // convert angle if the edge is an outgoing edge
184 if (e->getFromNode() == myNode) {
185 angle += (double) 180.;
186 if (angle >= (double) 360.) {
187 angle -= (double) 360.;
188 }
189 }
190 if (angle < 0.1 || angle > 359.9) {
191 angle = (double) 0.;
192 }
193 assert(angle >= 0 && angle < (double)360);
194 return angle;
195 }
196
197 private:
200
201 };
202
203};
204
205
206
207// ---------------------------------------------------------------------------
208// NBNodeTypeComputer
209// ---------------------------------------------------------------------------
210/* @class NBNodeTypeComputer
211 * @brief Computes node types
212 */
214public:
219
224
226 static bool isRailwayNode(const NBNode* n);
227};
228
229
230
231// ---------------------------------------------------------------------------
232// NBEdgePriorityComputer
233// ---------------------------------------------------------------------------
234/* @class NBEdgePriorityComputer
235 * @brief Computes edge priorities within a node
236 */
238public:
242 static void computeEdgePriorities(NBNodeCont& nc);
243
244private:
248 static void setPriorityJunctionPriorities(NBNode& n, bool forceStraight = false);
249
251 static double getScore(const NBEdge* e1, const NBEdge* e2, int minPrio, int maxPrio, int maxNumLanes, double maxSpeed);
252
254 static void markBestParallel(const NBNode& n, NBEdge* bestFirst, NBEdge* bestSecond);
255
262 static NBEdge* extractAndMarkFirst(NBNode& n, std::vector<NBEdge*>& s, int prio = 1);
263
269 static bool samePriority(const NBEdge* const e1, const NBEdge* const e2);
270
272 static bool hasDifferentPriorities(const EdgeVector& edges, const NBEdge* excluded);
273
274};
std::vector< NBEdge * > EdgeVector
container for (sorted) edges
Definition: NBCont.h:42
T MIN2(T a, T b)
Definition: StdDefs.h:76
The representation of a single edge during network building.
Definition: NBEdge.h:92
SVCPermissions getPermissions(int lane=-1) const
get the union of allowed classes over all lanes or for a specific lane
Definition: NBEdge.cpp:4232
const std::string & getID() const
Definition: NBEdge.h:1515
NBNode * getFromNode() const
Returns the origin node of the edge.
Definition: NBEdge.h:529
double getAngleAtNode(const NBNode *const node) const
Returns the angle of the edge's geometry at the given node.
Definition: NBEdge.cpp:2077
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:57
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:127
int getMinRank(const EdgeVector &e) const
retrieves the minimum index in myAllEdges
Definition: NBAlgorithms.h:143
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:131
Sorts incoming and outgoing edges clockwise around the given node.
Definition: NBAlgorithms.h:169
int operator()(NBEdge *e1, NBEdge *e2) const
Definition: NBAlgorithms.h:172
NBNode * myNode
The node to compute the relative angle of.
Definition: NBAlgorithms.h:199
double getConvAngle(NBEdge *e) const
Converts the angle of the edge if it is an incoming edge.
Definition: NBAlgorithms.h:178
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:78
int operator()(const Combination &c1, const Combination &c2) const
Definition: NBAlgorithms.h:81
static double getFarAngleAtNode(const NBEdge *e, const NBNode *n, double dist=50)
compute angle to junction at a point further away
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:68