Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-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 NBContHelper.cpp
15 : /// @author Daniel Krajzewicz
16 : /// @author Jakob Erdmann
17 : /// @author Michael Behrisch
18 : /// @date Tue, 20 Nov 2001
19 : ///
20 : // Some methods for traversing lists of edges
21 : /****************************************************************************/
22 : #include <config.h>
23 :
24 : #include <vector>
25 : #include <map>
26 : #include <cassert>
27 : #include "NBContHelper.h"
28 : #include <utils/geom/GeomHelper.h>
29 :
30 :
31 : // ===========================================================================
32 : // method definitions
33 : // ===========================================================================
34 : /* -------------------------------------------------------------------------
35 : * utility methods
36 : * ----------------------------------------------------------------------- */
37 : void
38 4597736 : NBContHelper::nextCW(const EdgeVector& edges, EdgeVector::const_iterator& from) {
39 : from++;
40 4597736 : if (from == edges.end()) {
41 759899 : from = edges.begin();
42 : }
43 4597736 : }
44 :
45 :
46 : void
47 4463604 : NBContHelper::nextCCW(const EdgeVector& edges, EdgeVector::const_iterator& from) {
48 4463604 : if (from == edges.begin()) {
49 554480 : from = edges.end() - 1;
50 : } else {
51 : --from;
52 : }
53 4463604 : }
54 :
55 :
56 : std::ostream&
57 0 : NBContHelper::out(std::ostream& os, const std::vector<bool>& v) {
58 0 : for (std::vector<bool>::const_iterator i = v.begin(); i != v.end(); i++) {
59 : os << *i;
60 : }
61 0 : return os;
62 : }
63 :
64 :
65 : NBEdge*
66 0 : NBContHelper::findConnectingEdge(const EdgeVector& edges,
67 : NBNode* from, NBNode* to) {
68 0 : for (EdgeVector::const_iterator i = edges.begin(); i != edges.end(); i++) {
69 0 : if ((*i)->getToNode() == to && (*i)->getFromNode() == from) {
70 : return *i;
71 : }
72 : }
73 : return nullptr;
74 : }
75 :
76 :
77 :
78 : double
79 2811 : NBContHelper::maxSpeed(const EdgeVector& ev) {
80 : assert(ev.size() > 0);
81 2811 : double max = (*(ev.begin()))->getSpeed();
82 11418 : for (EdgeVector::const_iterator i = ev.begin() + 1; i != ev.end(); i++) {
83 : max =
84 8607 : max > (*i)->getSpeed()
85 8607 : ? max : (*i)->getSpeed();
86 : }
87 2811 : return max;
88 : }
89 :
90 :
91 :
92 : /* -------------------------------------------------------------------------
93 : * methods from node_with_incoming_finder
94 : * ----------------------------------------------------------------------- */
95 1052761 : NBContHelper::node_with_incoming_finder::node_with_incoming_finder(const NBEdge* const e)
96 1052761 : : myEdge(e) {}
97 :
98 :
99 : bool
100 2798537 : NBContHelper::node_with_incoming_finder::operator()(const NBNode* const n) const {
101 : const EdgeVector& incoming = n->getIncomingEdges();
102 2798537 : return std::find(incoming.begin(), incoming.end(), myEdge) != incoming.end();
103 : }
104 :
105 :
106 :
107 : /* -------------------------------------------------------------------------
108 : * methods from node_with_outgoing_finder
109 : * ----------------------------------------------------------------------- */
110 1053298 : NBContHelper::node_with_outgoing_finder::node_with_outgoing_finder(const NBEdge* const e)
111 1053298 : : myEdge(e) {}
112 :
113 :
114 : bool
115 2809385 : NBContHelper::node_with_outgoing_finder::operator()(const NBNode* const n) const {
116 : const EdgeVector& outgoing = n->getOutgoingEdges();
117 2809385 : return std::find(outgoing.begin(), outgoing.end(), myEdge) != outgoing.end();
118 : }
119 :
120 :
121 : /* -------------------------------------------------------------------------
122 : * methods from edge_with_destination_finder
123 : * ----------------------------------------------------------------------- */
124 0 : NBContHelper::edge_with_destination_finder::edge_with_destination_finder(NBNode* dest)
125 0 : : myDestinationNode(dest) {}
126 :
127 :
128 : bool
129 0 : NBContHelper::edge_with_destination_finder::operator()(NBEdge* e) const {
130 0 : return e->getToNode() == myDestinationNode;
131 : }
132 :
133 :
134 : /* -------------------------------------------------------------------------
135 : * methods from relative_outgoing_edge_sorter
136 : * ----------------------------------------------------------------------- */
137 : bool
138 196360 : NBContHelper::relative_outgoing_edge_sorter::operator()(const NBEdge* e1, const NBEdge* e2) const {
139 : assert(e1 != nullptr && e2 != nullptr);
140 196360 : double relAngle1 = NBHelpers::normRelAngle(myAngle, e1->getStartAngle());
141 196360 : double relAngle2 = NBHelpers::normRelAngle(myAngle, e2->getStartAngle());
142 196360 : const double length1 = e1->getGeometry().length2D();
143 196360 : const double length2 = e2->getGeometry().length2D();
144 :
145 196360 : double lookAhead = 2 * NBEdge::ANGLE_LOOKAHEAD;
146 196769 : while (fabs(relAngle1 - relAngle2) < 3.0) {
147 : // look at further geometry segments to resolve ambiguity
148 : const double offset1 = MAX2(0.0, MIN2(length1, lookAhead));
149 : const double offset2 = MAX2(0.0, MIN2(length2, lookAhead));
150 636 : const Position referencePos1 = e1->getGeometry().positionAtOffset2D(offset1);
151 636 : const Position referencePos2 = e2->getGeometry().positionAtOffset2D(offset2);
152 636 : const double angle1 = GeomHelper::legacyDegree(e1->getFromNode()->getPosition().angleTo2D(referencePos1), true);
153 636 : const double angle2 = GeomHelper::legacyDegree(e2->getFromNode()->getPosition().angleTo2D(referencePos2), true);
154 636 : relAngle1 = NBHelpers::normRelAngle(myAngle, angle1);
155 636 : relAngle2 = NBHelpers::normRelAngle(myAngle, angle2);
156 636 : if (lookAhead > MAX2(length1, length2)) {
157 : break;
158 : }
159 409 : lookAhead *= 2;
160 : }
161 196360 : if (fabs(relAngle1 - relAngle2) < NUMERICAL_EPS) {
162 : // need to break ties for windows debug version, numerical id may be -1 for both
163 152 : return e1->getID() > e2->getID();
164 : }
165 196208 : return relAngle1 > relAngle2;
166 : }
167 :
168 :
169 : /* -------------------------------------------------------------------------
170 : * methods from relative_incoming_edge_sorter
171 : * ----------------------------------------------------------------------- */
172 : bool
173 3018 : NBContHelper::relative_incoming_edge_sorter::operator()(const NBEdge* e1, const NBEdge* e2) const {
174 : assert(e1 != nullptr && e2 != nullptr);
175 3018 : double relAngle1 = NBHelpers::normRelAngle(myAngle, e1->getEndAngle());
176 3018 : double relAngle2 = NBHelpers::normRelAngle(myAngle, e2->getEndAngle());
177 3018 : const double length1 = e1->getGeometry().length2D();
178 3018 : const double length2 = e2->getGeometry().length2D();
179 :
180 3018 : double lookAhead = 2 * NBEdge::ANGLE_LOOKAHEAD;
181 3075 : while (fabs(relAngle1 - relAngle2) < 3.0) {
182 : // look at further geometry segments to resolve ambiguity
183 64 : const double offset1 = MAX2(0.0, MIN2(length1, length1 - lookAhead));
184 64 : const double offset2 = MAX2(0.0, MIN2(length2, length2 - lookAhead));
185 64 : const Position referencePos1 = e1->getGeometry().positionAtOffset2D(offset1);
186 64 : const Position referencePos2 = e2->getGeometry().positionAtOffset2D(offset2);
187 64 : const double angle1 = GeomHelper::legacyDegree(referencePos1.angleTo2D(e1->getToNode()->getPosition()), true);
188 64 : const double angle2 = GeomHelper::legacyDegree(referencePos2.angleTo2D(e2->getToNode()->getPosition()), true);
189 64 : relAngle1 = NBHelpers::normRelAngle(myAngle, angle1);
190 64 : relAngle2 = NBHelpers::normRelAngle(myAngle, angle2);
191 64 : if (lookAhead > MAX2(length1, length2)) {
192 : break;
193 : }
194 57 : lookAhead *= 2;
195 : }
196 3018 : if (fabs(relAngle1 - relAngle2) < NUMERICAL_EPS) {
197 : // need to break ties for windows debug version, numerical id may be -1 for both
198 4 : return e1->getID() > e2->getID();
199 : }
200 3014 : return relAngle1 > relAngle2;
201 : }
202 :
203 :
204 : std::ostream&
205 0 : operator<<(std::ostream& os, const EdgeVector& ev) {
206 0 : for (EdgeVector::const_iterator i = ev.begin(); i != ev.end(); i++) {
207 0 : if (i != ev.begin()) {
208 0 : os << ", ";
209 : }
210 0 : os << (*i)->getID();
211 : }
212 0 : return os;
213 : }
214 :
215 :
216 : double
217 0 : NBContHelper::getMaxSpeed(const EdgeVector& edges) {
218 0 : if (edges.size() == 0) {
219 : return -1;
220 : }
221 0 : double ret = (*(edges.begin()))->getSpeed();
222 0 : for (EdgeVector::const_iterator i = edges.begin() + 1; i != edges.end(); i++) {
223 0 : if ((*i)->getSpeed() > ret) {
224 0 : ret = (*i)->getSpeed();
225 : }
226 : }
227 : return ret;
228 : }
229 :
230 :
231 : double
232 0 : NBContHelper::getMinSpeed(const EdgeVector& edges) {
233 0 : if (edges.size() == 0) {
234 : return -1;
235 : }
236 0 : double ret = (*(edges.begin()))->getSpeed();
237 0 : for (EdgeVector::const_iterator i = edges.begin() + 1; i != edges.end(); i++) {
238 0 : if ((*i)->getSpeed() < ret) {
239 0 : ret = (*i)->getSpeed();
240 : }
241 : }
242 : return ret;
243 : }
244 :
245 :
246 : bool
247 2256882 : NBContHelper::edge_by_angle_to_nodeShapeCentroid_sorter::operator()(const NBEdge* e1, const NBEdge* e2) const {
248 : assert(e1->getFromNode() == myNode || e1->getToNode() == myNode);
249 : assert(e2->getFromNode() == myNode || e2->getToNode() == myNode);
250 2256882 : const double angle1 = e1->getAngleAtNodeToCenter(myNode);
251 2256882 : const double angle2 = e2->getAngleAtNodeToCenter(myNode);
252 2256882 : const double absDiff = fabs(angle1 - angle2);
253 :
254 : // cannot trust the angle difference hence a heuristic:
255 2256882 : if (absDiff < 2 || absDiff > (360 - 2)) {
256 232080 : const bool sameDir = ((e1->getFromNode() == myNode && e2->getFromNode() == myNode)
257 502263 : || (e1->getToNode() == myNode && e2->getToNode() == myNode));
258 : if (sameDir) {
259 : // put edges that allow pedestrians on the 'outside', but be aware if both allow / disallow
260 6916 : const bool e1Peds = (e1->getPermissions() & SVC_PEDESTRIAN) != 0;
261 6916 : const bool e2Peds = (e2->getPermissions() & SVC_PEDESTRIAN) != 0;
262 6916 : if (e1->getToNode() == myNode) {
263 3845 : if (e1Peds && !e2Peds) {
264 : return true;
265 3485 : } else if (!e1Peds && e2Peds) {
266 : return false;
267 : }
268 : } else {
269 3071 : if (!e1Peds && e2Peds) {
270 : return true;
271 2784 : } else if (e1Peds && !e2Peds) {
272 : return false;
273 : }
274 : }
275 : // break ties to ensure strictly weak ordering
276 4822 : return e1->getID() < e2->getID();
277 : } else {
278 : // sort incoming before outgoing, no need to break ties here
279 266338 : return e1->getToNode() == myNode;
280 : }
281 : }
282 1983628 : return angle1 < angle2;
283 : }
284 :
285 :
286 : /****************************************************************************/
|
