Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2025 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 NBContHelper.h
15 : /// @author Daniel Krajzewicz
16 : /// @author Jakob Erdmann
17 : /// @author Michael Behrisch
18 : /// @date Mon, 17 Dec 2001
19 : ///
20 : // Some methods for traversing lists of edges
21 : /****************************************************************************/
22 : #pragma once
23 : #include <config.h>
24 :
25 : #include <vector>
26 : #include <iostream>
27 : #include <cmath>
28 : #include <algorithm>
29 : #include <cassert>
30 : #include "NBHelpers.h"
31 : #include "NBCont.h"
32 : #include "NBEdge.h"
33 : #include "NBNode.h"
34 : #include <utils/common/StdDefs.h>
35 : #include <utils/geom/GeomHelper.h>
36 :
37 :
38 : // ===========================================================================
39 : // class definitions
40 : // ===========================================================================
41 : /**
42 : * NBContHelper
43 : * Some static helper methods that traverse a sorted list of edges in both
44 : * directions
45 : */
46 : class NBContHelper {
47 : public:
48 : /** Moves the given iterator clockwise within the given container
49 : of edges sorted clockwise */
50 : static void nextCW(const EdgeVector& edges,
51 : EdgeVector::const_iterator& from);
52 :
53 : /** Moves the given iterator counter clockwise within the given container
54 : of edges sorted clockwise */
55 : static void nextCCW(const EdgeVector& edges,
56 : EdgeVector::const_iterator& from);
57 :
58 : static double getMaxSpeed(const EdgeVector& edges);
59 :
60 : static double getMinSpeed(const EdgeVector& edges);
61 :
62 : /** writes the vector of bools to the given stream */
63 : static std::ostream& out(std::ostream& os, const std::vector<bool>& v);
64 :
65 :
66 : /**
67 : * relative_outgoing_edge_sorter
68 : * Class to sort edges by their angle in relation to the node the
69 : * edge using this class is incoming into. This is normally done to
70 : * sort edges outgoing from the node the using edge is incoming in
71 : * by their angle in relation to the using edge's angle (this angle
72 : * is the reference angle).
73 : */
74 : class relative_outgoing_edge_sorter {
75 : public:
76 : /// constructor
77 136602 : explicit relative_outgoing_edge_sorter(NBEdge* e) : myAngle(e->getEndAngle()) {}
78 : /// constructor
79 : explicit relative_outgoing_edge_sorter(double angle) : myAngle(angle) {}
80 :
81 : public:
82 : /// comparing operation
83 : bool operator()(const NBEdge* e1, const NBEdge* e2) const;
84 :
85 : private:
86 : /// @brief the reference angle to compare edges agains
87 : double myAngle;
88 : };
89 :
90 :
91 : /**
92 : * relative_incoming_edge_sorter
93 : * Class to sort edges by their angle in relation to an outgoing edge.
94 : * This is normally done to sort edges incoming at the starting node of this edge
95 : * by their angle in relation to the using edge's angle (this angle
96 : * is the reference angle).
97 : */
98 : class relative_incoming_edge_sorter {
99 : public:
100 : /// constructor
101 3482 : explicit relative_incoming_edge_sorter(NBEdge* e) : myAngle(e->getStartAngle()) {}
102 : /// constructor
103 : explicit relative_incoming_edge_sorter(double angle) : myAngle(angle) {}
104 :
105 : public:
106 : /// comparing operation
107 : bool operator()(const NBEdge* e1, const NBEdge* e2) const;
108 :
109 : private:
110 : /// @brief the reference angle to compare edges agains
111 : double myAngle;
112 : };
113 :
114 :
115 : /**
116 : * edge_by_priority_sorter
117 : * Class to sort edges by their priority
118 : */
119 : class edge_by_priority_sorter {
120 : public:
121 : edge_by_priority_sorter(SVCPermissions permissions) : myPermissions(permissions) {}
122 : /// comparing operator
123 168459 : int operator()(NBEdge* e1, NBEdge* e2) const {
124 168459 : if (e1->getPriority() != e2->getPriority()) {
125 40963 : return e1->getPriority() > e2->getPriority();
126 : }
127 127496 : if (e1->getSpeed() != e2->getSpeed()) {
128 9864 : return e1->getSpeed() > e2->getSpeed();
129 : }
130 117632 : return e1->getNumLanesThatAllow(myPermissions, false) > e2->getNumLanesThatAllow(myPermissions, false);
131 : }
132 :
133 : private:
134 : SVCPermissions myPermissions;
135 : };
136 :
137 : // ---------------------------
138 :
139 : /**
140 : * @class edge_opposite_direction_sorter
141 : * @brief Class to sort edges by their angle in relation to the given edge
142 : *
143 : * The resulting sorted list has the edge in the most opposite direction
144 : * to the given edge as her first entry.
145 : */
146 : class edge_opposite_direction_sorter {
147 : public:
148 : /** @brief Constructor
149 : * @param[in] e The edge to which the sorting relates
150 : * @param[in] n The node to consider
151 : */
152 124842 : explicit edge_opposite_direction_sorter(const NBEdge* const e, const NBNode* const n, bool regardPriority) :
153 124842 : myNode(n),
154 124842 : myEdge(e),
155 124842 : myRegardPriority(regardPriority) {
156 124842 : myAngle = getEdgeAngleAt(e, n);
157 : }
158 :
159 : /** @brief Comparing operation
160 : * @param[in] e1 The first edge to compare
161 : * @param[in] e2 The second edge to compare
162 : * @return Which edge is more opposite to the related one
163 : */
164 374884 : int operator()(NBEdge* e1, NBEdge* e2) const {
165 374884 : if (!myRegardPriority || e1->getPriority() == e2->getPriority() || e1 == myEdge || e2 == myEdge) {
166 334600 : return getDiff(e1) > getDiff(e2);
167 : } else {
168 40284 : return e1->getPriority() > e2->getPriority();
169 : }
170 : }
171 :
172 : protected:
173 : /** @brief Computes the angle difference between the related and the given edge
174 : * @param[in] e The edge to compare the angle difference of
175 : * @return The angle difference
176 : */
177 669200 : double getDiff(const NBEdge* const e) const {
178 669200 : return fabs(GeomHelper::angleDiff(getEdgeAngleAt(e, myNode), myAngle));
179 : }
180 :
181 : /** @brief Returns the given edge's angle at the given node
182 : *
183 : * Please note that we always consider the "outgoing direction".
184 : * @param[in] e The edge to which the sorting relates
185 : * @param[in] n The node to consider
186 : */
187 794042 : double getEdgeAngleAt(const NBEdge* const e, const NBNode* const n) const {
188 794042 : if (e->getFromNode() == n) {
189 283646 : return e->getGeometry().angleAt2D(0);
190 : } else {
191 510396 : return e->getGeometry()[-1].angleTo2D(e->getGeometry()[-2]);
192 : }
193 : }
194 :
195 : private:
196 :
197 : /// @brief The related node
198 : const NBNode* const myNode;
199 :
200 : /// @brief the reference edge
201 : const NBEdge* const myEdge;
202 :
203 : /// @brief The angle of the related edge at the given node
204 : double myAngle;
205 :
206 : /// @brief Whether edge priority may override closer angles
207 : bool myRegardPriority;
208 :
209 : };
210 :
211 : // ---------------------------
212 :
213 : /**
214 : * edge_similar_direction_sorter
215 : * Class to sort edges by their angle in relation to the given edge
216 : * The resulting list should have the edge in the most similar direction
217 : * to the given edge as its first entry
218 : */
219 : class edge_similar_direction_sorter {
220 : public:
221 : /// constructor
222 46243 : explicit edge_similar_direction_sorter(const NBEdge* const e, bool outgoing = true) :
223 46243 : myCompareOutgoing(outgoing),
224 92892 : myAngle(outgoing ? e->getShapeEndAngle() : e->getShapeStartAngle())
225 : {}
226 :
227 : /// comparing operation
228 97439 : int operator()(const NBEdge* e1, const NBEdge* e2) const {
229 97439 : const double d1 = angleDiff(myCompareOutgoing ? e1->getShapeStartAngle() : e1->getShapeEndAngle(), myAngle);
230 97439 : const double d2 = angleDiff(myCompareOutgoing ? e2->getShapeStartAngle() : e2->getShapeEndAngle(), myAngle);
231 97439 : if (fabs(fabs(d1) - fabs(d2)) < NUMERICAL_EPS) {
232 5372 : if (fabs(d1 - d2) > NUMERICAL_EPS) {
233 5251 : return d1 < d2;
234 : } else {
235 121 : return e1->getNumericalID() < e2->getNumericalID();
236 : }
237 : }
238 92067 : return fabs(d1) < fabs(d2);
239 : }
240 :
241 : private:
242 : double angleDiff(const double angle1, const double angle2) const {
243 194878 : double d = angle2 - angle1;
244 206675 : while (d >= 180.) {
245 11797 : d -= 360.;
246 : }
247 214558 : while (d < -180.) {
248 19680 : d += 360.;
249 : }
250 : return d;
251 : }
252 :
253 :
254 : private:
255 : /// the angle to find the edge with the opposite direction
256 : bool myCompareOutgoing;
257 : double myAngle;
258 : };
259 :
260 :
261 : /**
262 : * @class node_with_incoming_finder
263 : */
264 : class node_with_incoming_finder {
265 : public:
266 : /// constructor
267 : node_with_incoming_finder(const NBEdge* const e);
268 :
269 : bool operator()(const NBNode* const n) const;
270 :
271 : private:
272 : const NBEdge* const myEdge;
273 :
274 : };
275 :
276 :
277 : /**
278 : * @class node_with_outgoing_finder
279 : */
280 : class node_with_outgoing_finder {
281 : public:
282 : /// constructor
283 : node_with_outgoing_finder(const NBEdge* const e);
284 :
285 : bool operator()(const NBNode* const n) const;
286 :
287 : private:
288 : const NBEdge* const myEdge;
289 :
290 : };
291 :
292 :
293 :
294 :
295 : class edge_with_destination_finder {
296 : public:
297 : /// constructor
298 : edge_with_destination_finder(NBNode* dest);
299 :
300 : bool operator()(NBEdge* e) const;
301 :
302 : private:
303 : NBNode* myDestinationNode;
304 :
305 : private:
306 : /// @brief invalidated assignment operator
307 : edge_with_destination_finder& operator=(const edge_with_destination_finder& s);
308 :
309 : };
310 :
311 :
312 : /** Tries to return the first edge within the given container which
313 : connects both given nodes */
314 : static NBEdge* findConnectingEdge(const EdgeVector& edges,
315 : NBNode* from, NBNode* to);
316 :
317 :
318 : /** returns the maximum speed allowed on the edges */
319 : static double maxSpeed(const EdgeVector& ev);
320 :
321 : /**
322 : * same_connection_edge_sorter
323 : * This class is used to sort edges which connect the same nodes.
324 : * The edges are sorted in dependence to edges connecting them. The
325 : * rightmost will be the first in the list; the leftmost the last one.
326 : */
327 : class same_connection_edge_sorter {
328 : public:
329 : /// constructor
330 : explicit same_connection_edge_sorter() { }
331 :
332 : /// comparing operation
333 22 : int operator()(NBEdge* e1, NBEdge* e2) const {
334 22 : std::pair<double, double> mm1 = getMinMaxRelAngles(e1);
335 22 : std::pair<double, double> mm2 = getMinMaxRelAngles(e2);
336 22 : if (mm1.first == mm2.first && mm1.second == mm2.second) {
337 : // ok, let's simply sort them arbitrarily
338 14 : return e1->getID() < e2->getID();
339 : }
340 :
341 : assert(
342 : (mm1.first <= mm2.first && mm1.second <= mm2.second)
343 : ||
344 : (mm1.first >= mm2.first && mm1.second >= mm2.second));
345 14 : return (mm1.first >= mm2.first && mm1.second >= mm2.second);
346 : }
347 :
348 : /**
349 : *
350 : */
351 44 : std::pair<double, double> getMinMaxRelAngles(NBEdge* e) const {
352 : double min = 360;
353 : double max = 360;
354 44 : const EdgeVector& ev = e->getConnectedEdges();
355 110 : for (EdgeVector::const_iterator i = ev.begin(); i != ev.end(); ++i) {
356 66 : double angle = NBHelpers::normRelAngle(
357 : e->getTotalAngle(), (*i)->getTotalAngle());
358 66 : if (min == 360 || min > angle) {
359 : min = angle;
360 : }
361 66 : if (max == 360 || max < angle) {
362 : max = angle;
363 : }
364 : }
365 44 : return std::pair<double, double>(min, max);
366 44 : }
367 : };
368 :
369 :
370 : friend std::ostream& operator<<(std::ostream& os, const EdgeVector& ev);
371 :
372 : class opposite_finder {
373 : public:
374 : /// constructor
375 : opposite_finder(NBEdge* edge)
376 24816 : : myReferenceEdge(edge) { }
377 :
378 40535 : bool operator()(NBEdge* e) const {
379 63680 : return e->isTurningDirectionAt(myReferenceEdge) ||
380 23145 : myReferenceEdge->isTurningDirectionAt(e);
381 : }
382 :
383 : private:
384 : NBEdge* myReferenceEdge;
385 :
386 : };
387 :
388 : /**
389 : * edge_by_angle_to_nodeShapeCentroid_sorter
390 : * Class to sort edges by their angle in relation to the node shape
391 : * */
392 : class edge_by_angle_to_nodeShapeCentroid_sorter {
393 : public:
394 : /// constructor
395 : explicit edge_by_angle_to_nodeShapeCentroid_sorter(const NBNode* n) : myNode(n) {}
396 :
397 : public:
398 : /// comparing operation
399 : bool operator()(const NBEdge* e1, const NBEdge* e2) const;
400 :
401 : private:
402 : /// the edge to compute the relative angle of
403 : const NBNode* myNode;
404 : };
405 :
406 : };
|
