Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2012-2024 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 : /****************************************************************************/
14 : /// @file NBAlgorithms.h
15 : /// @author Daniel Krajzewicz
16 : /// @author Jakob Erdmann
17 : /// @date 02. March 2012
18 : ///
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 : // ===========================================================================
31 : class NBEdge;
32 : class 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 : */
43 : class NBTurningDirectionsComputer {
44 : public:
45 : /** @brief Computes turnaround destinations for all edges (if exist)
46 : * @param[in] nc The container of nodes to loop along
47 : * @param[in] warn Whether warnings shall be issued
48 : */
49 : static void computeTurnDirections(NBNodeCont& nc, bool warn = true);
50 :
51 : /** @brief Computes turnaround destinations for all incoming edges of the given nodes (if any)
52 : * @param[in] node The node for which to compute turnaround destinations
53 : * @param[in] warn Whether warnings shall be issued
54 : * @note: This is needed by netedit
55 : */
56 : static void computeTurnDirectionsForNode(NBNode* node, bool warn);
57 :
58 : /// @brief compute angle to junction at a point further away
59 : static double getFarAngleAtNode(const NBEdge* e, const NBNode* n, double dist = 50);
60 :
61 : private:
62 : /** @struct Combination
63 : * @brief Stores the information about the angle between an incoming ("from") and an outgoing ("to") edge
64 : *
65 : * Note that the angle is increased by 360 if the edges connect the same two nodes in
66 : * opposite direction.
67 : */
68 : struct Combination {
69 : NBEdge* from;
70 : NBEdge* to;
71 : double angle;
72 : };
73 :
74 :
75 : /** @class combination_by_angle_sorter
76 : * @brief Sorts "Combination"s by decreasing angle
77 : */
78 : class combination_by_angle_sorter {
79 : public:
80 : explicit combination_by_angle_sorter() { }
81 245557 : int operator()(const Combination& c1, const Combination& c2) const {
82 245557 : if (c1.angle != c2.angle) {
83 59788 : return c1.angle > c2.angle;
84 : }
85 185769 : if (c1.from != c2.from) {
86 185345 : if (c1.to == c2.to && c1.from->getPermissions() != c2.from->getPermissions()) {
87 192 : if (c1.from->getPermissions() == c1.to->getPermissions()) {
88 : return true;
89 151 : } else if (c2.from->getPermissions() == c1.to->getPermissions()) {
90 : return false;
91 : }
92 : }
93 185272 : return c1.from->getID() < c2.from->getID();
94 : }
95 424 : if (c1.to->getPermissions() != c2.to->getPermissions()) {
96 213 : if (c1.to->getPermissions() == c1.from->getPermissions()) {
97 : return true;
98 171 : } else if (c2.to->getPermissions() == c1.from->getPermissions()) {
99 : return false;
100 : }
101 : }
102 358 : 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 : */
115 : class NBNodesEdgesSorter {
116 : public:
117 : /** @brief Sorts a node's edges clockwise regarding driving direction
118 : * @param[in] nc The container of nodes to loop along
119 : * @param[in] useNodeShape Whether to sort based on the node shape (instead of only the edge angle)
120 : */
121 : static void sortNodesEdges(NBNodeCont& nc, bool useNodeShape = false);
122 :
123 : /** @class crossing_by_junction_angle_sorter
124 : * @brief Sorts crossings by minimum clockwise clockwise edge angle. Use the
125 : * ordering found in myAllEdges of the given node
126 : */
127 349827 : class crossing_by_junction_angle_sorter {
128 : public:
129 : explicit crossing_by_junction_angle_sorter(const NBNode* node, const EdgeVector& ordering);
130 :
131 2820 : int operator()(const std::unique_ptr<NBNode::Crossing>& c1, const std::unique_ptr<NBNode::Crossing>& c2) const {
132 2820 : const int r1 = getMinRank(c1->edges);
133 2820 : const int r2 = getMinRank(c2->edges);
134 2820 : if (r1 == r2) {
135 38 : return c1->edges.size() > c2->edges.size();
136 : } else {
137 2782 : return (int)(r1 < r2);
138 : }
139 : }
140 :
141 : private:
142 : /// @brief retrieves the minimum index in myAllEdges
143 5640 : int getMinRank(const EdgeVector& e) const {
144 5640 : int result = (int)myOrdering.size();
145 15252 : for (EdgeVector::const_iterator it = e.begin(); it != e.end(); ++it) {
146 9612 : int rank = (int)std::distance(myOrdering.begin(), std::find(myOrdering.begin(), myOrdering.end(), *it));
147 : result = MIN2(result, rank);
148 : }
149 5640 : return result;
150 : }
151 :
152 : private:
153 : EdgeVector myOrdering;
154 : };
155 :
156 : /** @brief Assures correct order for same-angle opposite-direction edges
157 : * @param[in] n The currently processed node
158 : * @param[in] i1 Pointer to first edge
159 : * @param[in] i2 Pointer to second edge
160 : */
161 : static void swapWhenReversed(const NBNode* const n,
162 : const std::vector<NBEdge*>::iterator& i1,
163 : const std::vector<NBEdge*>::iterator& i2);
164 :
165 :
166 : /** @class edge_by_junction_angle_sorter
167 : * @brief Sorts incoming and outgoing edges clockwise around the given node
168 : */
169 : class edge_by_junction_angle_sorter {
170 : public:
171 : explicit edge_by_junction_angle_sorter(NBNode* n) : myNode(n) {}
172 1426007 : int operator()(NBEdge* e1, NBEdge* e2) const {
173 1426007 : const double a1 = e1->getAngleAtNodeNormalized(myNode);
174 1426007 : const double a2 = e2->getAngleAtNodeNormalized(myNode);
175 1426007 : return a1 < a2 || (a1 == a2 && e1->getNumericalID() < e2->getNumericalID());
176 : }
177 :
178 : private:
179 : /// @brief The node to compute the relative angle of
180 : NBNode* myNode;
181 :
182 : };
183 :
184 : };
185 :
186 :
187 :
188 : // ---------------------------------------------------------------------------
189 : // NBNodeTypeComputer
190 : // ---------------------------------------------------------------------------
191 : /* @class NBNodeTypeComputer
192 : * @brief Computes node types
193 : */
194 : class NBNodeTypeComputer {
195 : public:
196 : /** @brief Computes node types
197 : * @param[in] nc The container of nodes to loop along
198 : */
199 : static void computeNodeTypes(NBNodeCont& nc, NBTrafficLightLogicCont& tlc);
200 :
201 : /** @brief Checks rail_crossing for validity
202 : * @param[in] nc The container of nodes to loop along
203 : */
204 : static void validateRailCrossings(NBNodeCont& nc, NBTrafficLightLogicCont& tlc);
205 :
206 : /// @brief whether the given node only has rail edges
207 : static bool isRailwayNode(const NBNode* n);
208 : };
209 :
210 :
211 :
212 : // ---------------------------------------------------------------------------
213 : // NBEdgePriorityComputer
214 : // ---------------------------------------------------------------------------
215 : /* @class NBEdgePriorityComputer
216 : * @brief Computes edge priorities within a node
217 : */
218 : class NBEdgePriorityComputer {
219 : public:
220 : /** @brief Computes edge priorities within a node
221 : * @param[in] nc The container of nodes to loop along
222 : */
223 : static void computeEdgePriorities(NBNodeCont& nc);
224 :
225 : private:
226 : /** @brief Sets the priorites in case of a priority junction
227 : * @param[in] n The node to set edges' priorities
228 : */
229 : static void setPriorityJunctionPriorities(NBNode& n, bool forceStraight = false);
230 :
231 : /// @brief score pair of edges for multi-criteria evaluatoin of angle, priority, laneNumber and speed
232 : static double getScore(const NBEdge* e1, const NBEdge* e2, int minPrio, int maxPrio, int maxNumLanes, double maxSpeed);
233 :
234 : /// @brief set priority for edges that are parallel to the best edges
235 : static void markBestParallel(const NBNode& n, NBEdge* bestFirst, NBEdge* bestSecond);
236 :
237 : /** @brief Sets the priorites in case of a priority junction
238 : * @param[in] n The node to set edges' priorities
239 : * @param[in] s The vector of edges to get and mark the first from
240 : * @param[in] prio The priority to assign
241 : * @return The vector's first edge
242 : */
243 : static NBEdge* extractAndMarkFirst(NBNode& n, std::vector<NBEdge*>& s, int prio = 1);
244 :
245 : /** @brief Returns whether both edges have the same priority
246 : * @param[in] e1 The first edge
247 : * @param[in] e2 The second edge
248 : * Whether both edges have the same priority
249 : */
250 : static bool samePriority(const NBEdge* const e1, const NBEdge* const e2);
251 :
252 : /// @brief return whether the priorite attribute can be used to distinguish the edges
253 : static bool hasDifferentPriorities(const EdgeVector& edges, const NBEdge* excluded);
254 :
255 : };
|
