Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2012-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 NBAlgorithms.cpp
15 : /// @author Daniel Krajzewicz
16 : /// @author Jakob Erdmann
17 : /// @date 02. March 2012
18 : ///
19 : // Algorithms for network computation
20 : /****************************************************************************/
21 : #include <config.h>
22 :
23 : #include <sstream>
24 : #include <iostream>
25 : #include <cassert>
26 : #include <algorithm>
27 : #include <utils/common/MsgHandler.h>
28 : #include <utils/common/ToString.h>
29 : #include <utils/options/OptionsCont.h>
30 : #include "NBEdge.h"
31 : #include "NBOwnTLDef.h"
32 : #include "NBTrafficLightLogicCont.h"
33 : #include "NBNodeCont.h"
34 : #include "NBTypeCont.h"
35 : #include "NBNode.h"
36 : #include "NBAlgorithms.h"
37 :
38 :
39 : //#define DEBUG_SETPRIORITIES
40 : //#define DEBUG_TURNAROUNDS
41 : #define DEBUGCOND (n.getID() == "C")
42 : //#define DEBUGCOND2(obj) (obj->getID() == "")
43 : #define DEBUGCOND2(obj) (true)
44 :
45 : // ===========================================================================
46 : // method definitions
47 : // ===========================================================================
48 : // ---------------------------------------------------------------------------
49 : // NBTurningDirectionsComputer
50 : // ---------------------------------------------------------------------------
51 : void
52 5669 : NBTurningDirectionsComputer::computeTurnDirections(NBNodeCont& nc, bool warn) {
53 215543 : for (std::map<std::string, NBNode*>::const_iterator i = nc.begin(); i != nc.end(); ++i) {
54 209874 : computeTurnDirectionsForNode(i->second, warn);
55 : }
56 5669 : }
57 :
58 : void
59 214382 : NBTurningDirectionsComputer::computeTurnDirectionsForNode(NBNode* node, bool warn) {
60 : const std::vector<NBEdge*>& incoming = node->getIncomingEdges();
61 : const std::vector<NBEdge*>& outgoing = node->getOutgoingEdges();
62 : // reset turning directions since this may be called multiple times
63 578650 : for (std::vector<NBEdge*>::const_iterator k = incoming.begin(); k != incoming.end(); ++k) {
64 364268 : (*k)->setTurningDestination(nullptr);
65 : }
66 : std::vector<Combination> combinations;
67 214382 : const bool geometryLike = node->geometryLike();
68 578398 : for (NBEdge* outedge : outgoing) {
69 1216369 : for (NBEdge* e : incoming) {
70 : // @todo: check whether NBHelpers::relAngle is properly defined and whether it should really be used, here
71 852353 : const double signedAngle = NBHelpers::normRelAngle(e->getAngleAtNode(node), outedge->getAngleAtNode(node));
72 852353 : if (signedAngle > 0 && signedAngle < 177 && e->getGeometry().back().distanceTo2D(outedge->getGeometry().front()) < POSITION_EPS) {
73 : // backwards curving edges can only be turnaround when there are
74 : // non-default endpoints
75 : #ifdef DEBUG_TURNAROUNDS
76 : if (DEBUGCOND2(node)) {
77 : std::cout << "incoming=" << e->getID() << " outgoing=" << outedge->getID() << " signedAngle=" << signedAngle << " skipped\n";
78 : }
79 : #endif
80 602352 : continue;
81 : }
82 608836 : double angle = fabs(signedAngle);
83 : #ifdef DEBUG_TURNAROUNDS
84 : if (DEBUGCOND2(node)) {
85 : std::cout << "incoming=" << e->getID() << " outgoing=" << outedge->getID() << " relAngle=" << NBHelpers::relAngle(e->getAngleAtNode(node), outedge->getAngleAtNode(node)) << "\n";
86 : }
87 : #endif
88 608836 : const bool badPermissions = ((outedge->getPermissions() & e->getPermissions() & ~SVC_PEDESTRIAN) == 0
89 87249 : && !geometryLike
90 691264 : && outedge->getPermissions() != e->getPermissions());
91 : if (e->getFromNode() == outedge->getToNode()
92 238214 : && (angle > 120 || e->getFromNode()->getPosition() == e->getToNode()->getPosition())
93 841867 : && !badPermissions) {
94 : // they connect the same nodes; should be the turnaround direction
95 : // we'll assign a maximum number
96 : //
97 : // @todo: indeed, we have observed some pathological intersections
98 : // see "294831560" in OSM/adlershof. Here, several edges are connecting
99 : // same nodes. We have to do the angle check before...
100 : //
101 : // @todo: and well, there are some other as well, see plain import
102 : // of delphi_muenchen (elmar), intersection "59534191". Not that it would
103 : // be realistic in any means; we will warn, here.
104 231396 : angle += 360;
105 : }
106 608836 : if (angle < 160) {
107 359581 : if (angle > 135) {
108 : // could be a turnaround with a green median island, look at
109 : // angle further away from the junction
110 5169 : const double inFA = getFarAngleAtNode(e, node);
111 5169 : const double outFA = getFarAngleAtNode(outedge, node);
112 5169 : const double signedFarAngle = NBHelpers::normRelAngle(inFA, outFA);
113 : #ifdef DEBUG_TURNAROUNDS
114 : if (DEBUGCOND2(node)) {
115 : std::cout << " inFA=" << inFA << " outFA=" << outFA << " sFA=" << signedFarAngle << "\n";
116 : }
117 : #endif
118 5169 : if (signedFarAngle > -160) {
119 4423 : continue;
120 : }
121 : } else {
122 354412 : continue;
123 : }
124 : }
125 250001 : if (badPermissions) {
126 : // penalty
127 5233 : angle -= 90;
128 : }
129 : Combination c;
130 250001 : c.from = e;
131 250001 : c.to = outedge;
132 250001 : c.angle = angle;
133 250001 : combinations.push_back(c);
134 : }
135 : }
136 : // sort combinations so that the ones with the highest angle are at the begin
137 214382 : std::sort(combinations.begin(), combinations.end(), combination_by_angle_sorter());
138 : std::set<NBEdge*> seen;
139 : #ifdef DEBUG_TURNAROUNDS
140 : if (DEBUGCOND2(node)) {
141 : std::cout << "check combinations at " << node->getID() << "\n";
142 : }
143 : #endif
144 464383 : for (std::vector<Combination>::const_iterator j = combinations.begin(); j != combinations.end(); ++j) {
145 : #ifdef DEBUG_TURNAROUNDS
146 : if (DEBUGCOND2(node)) {
147 : std::cout << " from=" << (*j).from->getID() << " to=" << (*j).to->getID() << " a=" << (*j).angle << "\n";
148 : }
149 : #endif
150 490014 : if (seen.find((*j).from) != seen.end() || seen.find((*j).to) != seen.end()) {
151 : // do not regard already set edges
152 12015 : if ((*j).angle > 360 && warn) {
153 609 : WRITE_WARNINGF(TL("Ambiguity in turnarounds computation at junction '%'."), node->getID());
154 : //std::cout << " already seen: " << toString(seen) << "\n";
155 : warn = false;
156 : }
157 12015 : continue;
158 : }
159 : // mark as seen
160 237986 : seen.insert((*j).from);
161 237986 : seen.insert((*j).to);
162 : // set turnaround information
163 237986 : bool onlyPossible = (*j).from->getConnections().size() != 0 && !(*j).from->isConnectedTo((*j).to);
164 : #ifdef DEBUG_TURNAROUNDS
165 : if (DEBUGCOND2(node)) {
166 : std::cout << " setTurningDestination from=" << (*j).from->getID() << " to=" << (*j).to->getID() << " onlyPossible=" << onlyPossible << "\n";
167 : }
168 : #endif
169 237986 : (*j).from->setTurningDestination((*j).to, onlyPossible);
170 : }
171 214382 : }
172 :
173 :
174 : double
175 10338 : NBTurningDirectionsComputer::getFarAngleAtNode(const NBEdge* e, const NBNode* n, double dist) {
176 : Position atNode;
177 : Position far;
178 : double angle;
179 : const NBEdge* next = e;
180 10338 : if (e->getToNode() == n) {
181 : // search upstream
182 5169 : atNode = e->getGeometry().back();
183 5705 : while (dist > 0) {
184 5705 : const double length = next->getGeometry().length();
185 5705 : if (dist <= length) {
186 1935 : far = next->getGeometry().positionAtOffset(length - dist);
187 : break;
188 : } else {
189 3770 : far = next->getGeometry().front();
190 3770 : dist -= length;
191 3770 : if (next->getToNode()->getIncomingEdges().size() == 1) {
192 536 : next = next->getToNode()->getIncomingEdges().front();
193 : } else {
194 : break;
195 : }
196 : }
197 : }
198 : angle = far.angleTo2D(atNode);
199 : //std::cout << " e=" << e->getID() << " n=" << n->getID() << " far=" << far << " atNode=" << atNode << " a=" << RAD2DEG(angle) << "\n";
200 : } else {
201 : // search downstream
202 5169 : atNode = e->getGeometry().front();
203 6614 : while (dist > 0) {
204 6614 : const double length = next->getGeometry().length();
205 6614 : if (dist <= length) {
206 2492 : far = next->getGeometry().positionAtOffset(dist);
207 : break;
208 : } else {
209 4122 : far = next->getGeometry().back();
210 4122 : dist -= length;
211 4122 : if (next->getToNode()->getOutgoingEdges().size() == 1) {
212 1445 : next = next->getToNode()->getOutgoingEdges().front();
213 : } else {
214 : break;
215 : }
216 : }
217 : }
218 : angle = atNode.angleTo2D(far);
219 : //std::cout << " e=" << e->getID() << " n=" << n->getID() << " atNode=" << atNode << " far=" << far << " a=" << RAD2DEG(angle) << "\n";
220 : }
221 10338 : return GeomHelper::legacyDegree(angle);
222 : }
223 :
224 :
225 : // ---------------------------------------------------------------------------
226 : // NBNodesEdgesSorter
227 : // ---------------------------------------------------------------------------
228 : void
229 5507 : NBNodesEdgesSorter::sortNodesEdges(NBNodeCont& nc, bool useNodeShape) {
230 194512 : for (std::map<std::string, NBNode*>::const_iterator i = nc.begin(); i != nc.end(); ++i) {
231 189005 : i->second->sortEdges(useNodeShape);
232 : }
233 5507 : }
234 :
235 :
236 : void
237 626679 : NBNodesEdgesSorter::swapWhenReversed(const NBNode* const n,
238 : const std::vector<NBEdge*>::iterator& i1,
239 : const std::vector<NBEdge*>::iterator& i2) {
240 626679 : NBEdge* e1 = *i1;
241 626679 : NBEdge* e2 = *i2;
242 : // @todo: The difference between "isTurningDirectionAt" and "isTurnaround"
243 : // is not nice. Maybe we could get rid of it if we would always mark edges
244 : // as turnarounds, even if they do not have to be added, as mentioned in
245 : // notes on NBTurningDirectionsComputer::computeTurnDirectionsForNode
246 626679 : if (e2->getToNode() == n && e2->isTurningDirectionAt(e1)) {
247 : std::swap(*i1, *i2);
248 : }
249 626679 : }
250 :
251 :
252 : // ---------------------------------------------------------------------------
253 : // NBNodeTypeComputer
254 : // ---------------------------------------------------------------------------
255 : void
256 1813 : NBNodeTypeComputer::computeNodeTypes(NBNodeCont& nc, NBTrafficLightLogicCont& tlc) {
257 1813 : validateRailCrossings(nc, tlc);
258 1813 : const OptionsCont& oc = OptionsCont::getOptions();
259 3626 : const double rightBeforeLeftSpeed = oc.getFloat("junctions.right-before-left.speed-threshold");
260 58907 : for (const auto& nodeIt : nc) {
261 57094 : NBNode* const n = nodeIt.second;
262 : // the type may already be set from the data
263 57094 : if (n->myType != SumoXMLNodeType::UNKNOWN && n->myType != SumoXMLNodeType::DEAD_END) {
264 29214 : n->myTypeWasGuessed = false;
265 29214 : continue;
266 : }
267 : // check whether the node was set to be unregulated by the user
268 83640 : if (oc.getBool("keep-nodes-unregulated") || oc.isInStringVector("keep-nodes-unregulated.explicit", n->getID())
269 111520 : || (oc.getBool("keep-nodes-unregulated.district-nodes") && (n->isNearDistrict() || n->isDistrict()))) {
270 0 : n->myType = SumoXMLNodeType::NOJUNCTION;
271 0 : continue;
272 : }
273 : // check whether the node is a waterway node. Set to unregulated by default
274 : bool waterway = true;
275 27973 : for (NBEdge* e : n->getEdges()) {
276 27945 : if (!isWaterway(e->getPermissions())) {
277 : waterway = false;
278 : break;
279 : }
280 : }
281 27880 : if (waterway && (n->myType == SumoXMLNodeType::UNKNOWN || n->myType == SumoXMLNodeType::DEAD_END)) {
282 28 : n->myType = SumoXMLNodeType::NOJUNCTION;
283 28 : continue;
284 : }
285 :
286 : // check whether the junction is not a real junction
287 27852 : if (n->myIncomingEdges.size() == 1) {
288 13509 : n->myType = SumoXMLNodeType::PRIORITY;
289 13509 : continue;
290 : }
291 : // @todo "isSimpleContinuation" should be revalidated
292 14343 : if (n->isSimpleContinuation()) {
293 1374 : n->myType = SumoXMLNodeType::PRIORITY;
294 1374 : continue;
295 : }
296 12969 : if (isRailwayNode(n)) {
297 317 : if (n->unsignalizedOperation()
298 57 : && (int)n->getIncomingEdges().size() == 2
299 371 : && (int)n->getOutgoingEdges().size() == 1) {
300 : // avoid slowing down when there are no foe vehicles
301 41 : n->myType = SumoXMLNodeType::ZIPPER;
302 : } else {
303 : // priority instead of unregulated to ensure that collisions can be detected
304 276 : n->myType = SumoXMLNodeType::PRIORITY;
305 : }
306 317 : continue;
307 : }
308 : // determine the type
309 25304 : SumoXMLNodeType type = oc.getBool("junctions.left-before-right") ? SumoXMLNodeType::LEFT_BEFORE_RIGHT : SumoXMLNodeType::RIGHT_BEFORE_LEFT;
310 38896 : for (EdgeVector::const_iterator i = n->myIncomingEdges.begin(); i != n->myIncomingEdges.end(); i++) {
311 36558 : for (EdgeVector::const_iterator j = i + 1; j != n->myIncomingEdges.end(); j++) {
312 : // @todo "getOppositeIncoming" should probably be refactored into something the edge knows
313 19716 : if (n->getOppositeIncoming(*j) == *i && n->myIncomingEdges.size() > 2) {
314 5411 : continue;
315 : }
316 : // @todo check against a legal document
317 : // @todo figure out when SumoXMLNodeType::PRIORITY_STOP is appropriate
318 14305 : const double s1 = (*i)->getSpeed();
319 14305 : const double s2 = (*j)->getSpeed();
320 14305 : const int p1 = (*i)->getPriority();
321 14305 : const int p2 = (*j)->getPriority();
322 23864 : if (fabs(s1 - s2) > (9.5 / 3.6) || MAX2(s1, s2) >= rightBeforeLeftSpeed || p1 != p2) {
323 : type = SumoXMLNodeType::PRIORITY;
324 : break;
325 : }
326 : }
327 : }
328 : // save type
329 12652 : n->myType = type;
330 12652 : n->myTypeWasGuessed = true;
331 : }
332 1813 : }
333 :
334 :
335 : void
336 1969 : NBNodeTypeComputer::validateRailCrossings(NBNodeCont& nc, NBTrafficLightLogicCont& tlc) {
337 82296 : for (std::map<std::string, NBNode*>::const_iterator i = nc.begin(); i != nc.end(); ++i) {
338 80327 : NBNode* n = (*i).second;
339 80327 : if (n->myType == SumoXMLNodeType::RAIL_CROSSING) {
340 : // check if it really is a rail crossing
341 : int numRailway = 0;
342 : int numNonRailIn = 0;
343 : int numNonRailOut = 0;
344 : std::set<const NBNode*> nonRailNodes;
345 : int numNonRailwayNonPed = 0;
346 2234 : for (NBEdge* e : n->getIncomingEdges()) {
347 1468 : if ((e->getPermissions() & ~SVC_RAIL_CLASSES) != 0) {
348 575 : numNonRailIn += 1;
349 575 : if (e->getPermissions() != SVC_PEDESTRIAN) {
350 169 : numNonRailwayNonPed++;
351 : }
352 575 : nonRailNodes.insert(e->getFromNode());
353 893 : } else if ((e->getPermissions() & SVC_RAIL_CLASSES) != 0) {
354 893 : numRailway++;
355 : }
356 : }
357 2228 : for (NBEdge* e : n->getOutgoingEdges()) {
358 1462 : if ((e->getPermissions() & ~SVC_RAIL_CLASSES) != 0) {
359 572 : numNonRailOut += 1;
360 572 : nonRailNodes.insert(e->getToNode());
361 : }
362 : }
363 766 : if (numNonRailIn == 0 || numNonRailOut == 0 || numRailway == 0) {
364 : // not a crossing (maybe unregulated or rail_signal)
365 975 : WRITE_WARNINGF(TL("Converting invalid rail_crossing to priority junction '%'."), n->getID());
366 325 : n->myType = SumoXMLNodeType::PRIORITY;
367 441 : } else if (numNonRailwayNonPed > 2 || nonRailNodes.size() > 2) {
368 : // does not look like a rail crossing (roads in conflict). maybe a traffic light?
369 75 : WRITE_WARNINGF(TL("Converting invalid rail_crossing to traffic_light at junction '%'."), n->getID());
370 25 : TrafficLightType type = SUMOXMLDefinitions::TrafficLightTypes.get(OptionsCont::getOptions().getString("tls.default-type"));
371 25 : NBTrafficLightDefinition* tlDef = new NBOwnTLDef(n->getID(), n, 0, type);
372 25 : n->myType = SumoXMLNodeType::TRAFFIC_LIGHT;
373 25 : if (!tlc.insert(tlDef)) {
374 : // actually, nothing should fail here
375 0 : n->removeTrafficLight(tlDef);
376 0 : n->myType = SumoXMLNodeType::PRIORITY;
377 0 : delete tlDef;
378 0 : WRITE_WARNINGF(TL("Could not allocate tls '%'."), n->getID());
379 : }
380 : }
381 : }
382 : }
383 1969 : }
384 :
385 :
386 : bool
387 110233 : NBNodeTypeComputer::isRailwayNode(const NBNode* n) {
388 : bool hasRailway = false;
389 116471 : for (NBEdge* e : n->getIncomingEdges()) {
390 111341 : if ((e->getPermissions() & ~(SVC_RAIL_CLASSES | SVC_TAXI)) != 0) {
391 : return false;
392 6238 : } else if ((e->getPermissions() & SVC_RAIL_CLASSES) != 0) {
393 : hasRailway = true;
394 : }
395 : }
396 : return hasRailway;
397 : }
398 :
399 : // ---------------------------------------------------------------------------
400 : // NBEdgePriorityComputer
401 : // ---------------------------------------------------------------------------
402 : void
403 1813 : NBEdgePriorityComputer::computeEdgePriorities(NBNodeCont& nc) {
404 58907 : for (const auto& node : nc) {
405 : // preset all junction's edge priorities to zero
406 262102 : for (NBEdge* const edge : node.second->myAllEdges) {
407 205008 : edge->setJunctionPriority(node.second, NBEdge::JunctionPriority::MINOR_ROAD);
408 : }
409 57094 : node.second->markBentPriority(false);
410 : // check if the junction is not a real junction
411 57094 : if (node.second->myIncomingEdges.size() == 1 && node.second->myOutgoingEdges.size() == 1) {
412 16085 : continue;
413 : }
414 : // compute the priorities on junction when needed
415 : if (node.second->getType() != SumoXMLNodeType::RIGHT_BEFORE_LEFT
416 : && node.second->getType() != SumoXMLNodeType::LEFT_BEFORE_RIGHT
417 : && node.second->getType() != SumoXMLNodeType::ALLWAY_STOP
418 : && node.second->getType() != SumoXMLNodeType::NOJUNCTION) {
419 30794 : if (node.second->getRightOfWay() == RightOfWay::EDGEPRIORITY) {
420 24 : for (NBEdge* e : node.second->getIncomingEdges()) {
421 20 : e->setJunctionPriority(node.second, e->getPriority());
422 : }
423 : } else {
424 30790 : setPriorityJunctionPriorities(*node.second);
425 : }
426 : }
427 : }
428 1813 : }
429 :
430 :
431 : void
432 31229 : NBEdgePriorityComputer::setPriorityJunctionPriorities(NBNode& n, bool forceStraight) {
433 31229 : if (n.myIncomingEdges.size() == 0 || n.myOutgoingEdges.size() == 0) {
434 15182 : return;
435 : }
436 : int minPrio = std::numeric_limits<int>::max();
437 : int maxPrio = -std::numeric_limits<int>::max();
438 : int maxNumLanes = -std::numeric_limits<int>::max();
439 : double maxSpeed = -std::numeric_limits<double>::max();
440 : // check available vClasses to consider for lane number comparison
441 : SVCPermissions all = 0;
442 166600 : for (NBEdge* const edge : n.myAllEdges) {
443 138961 : all |= edge->getPermissions();
444 : }
445 : if ((all & (SVC_PASSENGER & SVC_TRAM & SVC_BUS)) != 0) {
446 : all = (SVC_PASSENGER & SVC_TRAM & SVC_BUS);
447 27639 : } else if ((all & ~SVC_VULNERABLE) != 0) {
448 : all &= ~SVC_VULNERABLE;
449 : }
450 27639 : if (forceStraight) {
451 : // called a second time, preset all junction's edge priorities to zero
452 2935 : for (NBEdge* const edge : n.myAllEdges) {
453 2496 : edge->setJunctionPriority(&n, NBEdge::JunctionPriority::MINOR_ROAD);
454 : minPrio = MIN2(minPrio, edge->getPriority());
455 : maxPrio = MAX2(maxPrio, edge->getPriority());
456 2496 : maxNumLanes = MAX2(maxNumLanes, edge->getNumLanesThatAllow(all, false));
457 2496 : maxSpeed = MAX2(maxSpeed, edge->getSpeed());
458 : }
459 : }
460 27639 : EdgeVector incoming = n.myIncomingEdges;
461 27639 : EdgeVector outgoing = n.myOutgoingEdges;
462 : // what we do want to have is to extract the pair of roads that are
463 : // the major roads for this junction
464 : // let's get the list of incoming edges with the highest priority
465 27639 : std::sort(incoming.begin(), incoming.end(), NBContHelper::edge_by_priority_sorter(all));
466 : EdgeVector bestIncoming;
467 27639 : NBEdge* bestIn = incoming[0];
468 80202 : while (incoming.size() > 0 && (forceStraight || samePriority(bestIn, incoming[0], all))) {
469 52563 : bestIncoming.push_back(*incoming.begin());
470 : incoming.erase(incoming.begin());
471 : }
472 : // now, let's get the list of best outgoing
473 : assert(outgoing.size() != 0);
474 27639 : sort(outgoing.begin(), outgoing.end(), NBContHelper::edge_by_priority_sorter(all));
475 : EdgeVector bestOutgoing;
476 27639 : const NBEdge* const firstOut = outgoing[0];
477 82632 : while (outgoing.size() > 0 && (forceStraight || samePriority(firstOut, outgoing[0], all))) { //->getPriority()==best->getPriority())
478 54993 : bestOutgoing.push_back(*outgoing.begin());
479 : outgoing.erase(outgoing.begin());
480 : }
481 : // special case: user input makes mainDirection unambiguous
482 : const bool mainDirectionExplicit = (
483 11592 : bestIncoming.size() == 1 && n.myIncomingEdges.size() <= 2
484 9837 : && (incoming.size() == 0 || bestIncoming[0]->getPriority() > incoming[0]->getPriority())
485 8239 : && bestOutgoing.size() == 1 && n.myOutgoingEdges.size() <= 2
486 4960 : && (outgoing.size() == 0 || bestOutgoing[0]->getPriority() > outgoing[0]->getPriority())
487 31933 : && !bestIncoming[0]->isTurningDirectionAt(bestOutgoing[0]));
488 : // now, let's compute for each of the best incoming edges
489 : // the incoming which is most opposite
490 : // the outgoing which is most opposite
491 : EdgeVector::iterator i;
492 : std::map<NBEdge*, NBEdge*> counterIncomingEdges;
493 : std::map<NBEdge*, NBEdge*> counterOutgoingEdges;
494 27639 : incoming = n.myIncomingEdges;
495 27639 : outgoing = n.myOutgoingEdges;
496 80202 : for (i = bestIncoming.begin(); i != bestIncoming.end(); ++i) {
497 105126 : std::sort(incoming.begin(), incoming.end(), NBContHelper::edge_opposite_direction_sorter(*i, &n, !forceStraight));
498 52563 : counterIncomingEdges[*i] = *incoming.begin();
499 105126 : std::sort(outgoing.begin(), outgoing.end(), NBContHelper::edge_opposite_direction_sorter(*i, &n, !forceStraight));
500 52563 : counterOutgoingEdges[*i] = *outgoing.begin();
501 : }
502 : #ifdef DEBUG_SETPRIORITIES
503 : if (DEBUGCOND) {
504 : std::map<std::string, std::string> tmp1;
505 : for (auto item : counterIncomingEdges) {
506 : tmp1[item.first->getID()] = item.second->getID();
507 : }
508 : std::map<std::string, std::string> tmp2;
509 : for (auto item : counterOutgoingEdges) {
510 : tmp2[item.first->getID()] = item.second->getID();
511 : }
512 : std::cout << "n=" << n.getID() << " forceStraight=" << forceStraight << " bestIn=" << bestIn->getID() << " bestOut=" << toString(bestOutgoing)
513 : << " counterBest=" << counterIncomingEdges.find(bestIncoming[0])->second->getID()
514 : << " mainExplicit=" << mainDirectionExplicit
515 : << " forceStraight=" << forceStraight
516 : << "\n bestIncoming=" << toString(bestIncoming) << " allIncoming=" << toString(incoming)
517 : << "\n bestOutgoing=" << toString(bestOutgoing) << " allOutgoing=" << toString(outgoing)
518 : << "\n counterIncomingEdges=" << toString(tmp1)
519 : << "\n counterOutgoingEdges=" << toString(tmp2)
520 : << "\n";
521 : }
522 : #endif
523 : // at a tls junction we must prevent an underlying bent-priority layout
524 : // because that would lead to invalid right-of-way rules for an oncoming
525 : // tls layout (but not vice versa). See #7764
526 : const bool hasTLS = n.isTLControlled();
527 : // ok, let's try
528 : // 1) there is one best incoming road
529 27639 : if (bestIncoming.size() == 1) {
530 : // let's mark this road as the best
531 11592 : NBEdge* best1 = extractAndMarkFirst(n, bestIncoming);
532 19253 : if (!mainDirectionExplicit && counterIncomingEdges.find(best1) != counterIncomingEdges.end()) {
533 : // ok, look, what we want is the opposite of the straight continuation edge
534 : // but, what if such an edge does not exist? By now, we'll determine it
535 : // geometrically
536 7661 : NBEdge* s = counterIncomingEdges.find(best1)->second;
537 7661 : const double minAngleDiff = GeomHelper::getMinAngleDiff(best1->getAngleAtNode(&n), s->getAngleAtNode(&n));
538 : if (minAngleDiff > 180 - 45
539 7661 : || (minAngleDiff > 75 && s->getPriority() == best1->getPriority() && hasDifferentPriorities(incoming, best1))) {
540 1676 : s->setJunctionPriority(&n, NBEdge::PRIORITY_ROAD);
541 : }
542 : }
543 11592 : markBestParallel(n, best1, nullptr);
544 : assert(bestOutgoing.size() != 0);
545 : // mark the best outgoing as the continuation
546 11592 : sort(bestOutgoing.begin(), bestOutgoing.end(), NBContHelper::edge_similar_direction_sorter(best1));
547 : // assign extra priority if the priorities are unambiguous (regardless of geometry)
548 11592 : NBEdge* bestOut = extractAndMarkFirst(n, bestOutgoing);
549 19253 : if (!mainDirectionExplicit && counterOutgoingEdges.find(bestOut) != counterOutgoingEdges.end()) {
550 0 : NBEdge* s = counterOutgoingEdges.find(bestOut)->second;
551 0 : if (GeomHelper::getMinAngleDiff(bestOut->getAngleAtNode(&n), s->getAngleAtNode(&n)) > 180 - 45) {
552 0 : s->setJunctionPriority(&n, NBEdge::PRIORITY_ROAD);
553 : }
554 : }
555 11592 : const bool isBent = n.getDirection(best1, bestOut) != LinkDirection::STRAIGHT;
556 : #ifdef DEBUG_SETPRIORITIES
557 : if (DEBUGCOND) {
558 : std::cout << " best1=" << best1->getID() << " bestOut=" << bestOut->getID() << " bestOutgoing=" << toString(bestOutgoing) << " mainDirectionExplicit=" << mainDirectionExplicit << " isBent=" << isBent << "\n";
559 : }
560 : #endif
561 11592 : if (isBent && hasTLS && !forceStraight) {
562 : // redo but force straight computation
563 195 : setPriorityJunctionPriorities(n, true);
564 : } else {
565 : n.markBentPriority(isBent);
566 : }
567 : return;
568 : }
569 :
570 : // ok, what we want to do in this case is to determine which incoming
571 : // has the best continuation...
572 : // This means, when several incoming roads have the same priority,
573 : // we want a (any) straight connection to be more priorised than a turning
574 : double bestAngle = -1;
575 : NBEdge* bestFirst = nullptr;
576 : NBEdge* bestSecond = nullptr;
577 57018 : for (i = bestIncoming.begin(); i != bestIncoming.end(); ++i) {
578 : EdgeVector::iterator j;
579 40971 : NBEdge* t1 = *i;
580 40971 : double angle1 = t1->getAngleAtNode(&n) + 180;
581 40971 : if (angle1 >= 360) {
582 0 : angle1 -= 360;
583 : }
584 78311 : for (j = i + 1; j != bestIncoming.end(); ++j) {
585 37340 : NBEdge* t2 = *j;
586 37340 : double angle2 = t2->getAngleAtNode(&n) + 180;
587 37340 : if (angle2 >= 360) {
588 0 : angle2 -= 360;
589 : }
590 37340 : double score = forceStraight ? getScore(t1, t2, minPrio, maxPrio, maxNumLanes, maxSpeed, all) : 0;
591 37340 : double angle = GeomHelper::getMinAngleDiff(angle1, angle2) + 45 * score;
592 37340 : if (angle > bestAngle) {
593 : //if (forceStraight) std::cout << " node=" << n.getID() << " t1=" << t1->getID() << " t2=" << t2->getID() << " angle=" << angle << " bestAngle=" << bestAngle << " score=" << score << " minPrio=" << minPrio << " maxPrio=" << maxPrio << "\n";
594 : bestAngle = MAX2(angle, bestAngle);
595 22036 : bestFirst = *i;
596 22036 : bestSecond = *j;
597 : }
598 : }
599 : }
600 16047 : bestFirst->setJunctionPriority(&n, NBEdge::PRIORITY_ROAD);
601 16047 : sort(bestOutgoing.begin(), bestOutgoing.end(), NBContHelper::edge_similar_direction_sorter(bestFirst));
602 : #ifdef DEBUG_SETPRIORITIES
603 : if (DEBUGCOND) {
604 : std::cout << " bestFirst=" << bestFirst->getID() << " bestOutgoingFirst=" << toString(bestOutgoing) << "\n";
605 : }
606 : #endif
607 16047 : if (bestOutgoing.size() != 0) {
608 16047 : extractAndMarkFirst(n, bestOutgoing);
609 : }
610 16047 : bestSecond->setJunctionPriority(&n, NBEdge::PRIORITY_ROAD);
611 16047 : sort(bestOutgoing.begin(), bestOutgoing.end(), NBContHelper::edge_similar_direction_sorter(bestSecond));
612 : #ifdef DEBUG_SETPRIORITIES
613 : if (DEBUGCOND) {
614 : std::cout << " bestSecond=" << bestSecond->getID() << " bestOutgoingSecond=" << toString(bestOutgoing) << "\n";
615 : }
616 : #endif
617 16047 : if (bestOutgoing.size() != 0) {
618 14435 : extractAndMarkFirst(n, bestOutgoing);
619 : }
620 16047 : const bool isBent = GeomHelper::getMinAngleDiff(bestFirst->getAngleAtNode(&n), bestSecond->getAngleAtNode(&n)) < 135;
621 16047 : if (isBent && hasTLS && !forceStraight) {
622 : // redo but force straight computation
623 244 : setPriorityJunctionPriorities(n, true);
624 : } else {
625 : n.markBentPriority(isBent);
626 15803 : markBestParallel(n, bestFirst, bestSecond);
627 : }
628 27639 : }
629 :
630 : double
631 1626 : NBEdgePriorityComputer::getScore(const NBEdge* e1, const NBEdge* e2, int minPrio, int maxPrio, int maxNumLanes, double maxSpeed, SVCPermissions permissions) {
632 : // normalize priorities to [0.1,1]
633 : double normPrio1 = 1;
634 : double normPrio2 = 1;
635 1626 : if (minPrio != maxPrio) {
636 934 : normPrio1 = ((e1->getPriority() - minPrio) / (maxPrio - minPrio)) * 0.9 + 0.1;
637 934 : normPrio2 = ((e2->getPriority() - minPrio) / (maxPrio - minPrio)) * 0.9 + 0.1;
638 : }
639 : return (normPrio1
640 1626 : * e1->getNumLanesThatAllow(permissions, false) / maxNumLanes
641 1626 : * e1->getSpeed() / maxSpeed
642 1626 : * normPrio2
643 1626 : * e2->getNumLanesThatAllow(permissions, false) / maxNumLanes
644 1626 : * e2->getSpeed() / maxSpeed);
645 : }
646 :
647 : void
648 27395 : NBEdgePriorityComputer::markBestParallel(const NBNode& n, NBEdge* bestFirst, NBEdge* bestSecond) {
649 : // edges running parallel to the main direction should also be prioritised
650 27395 : const double a1 = bestFirst->getAngleAtNode(&n);
651 27395 : const double a2 = bestSecond == nullptr ? a1 : bestSecond->getAngleAtNode(&n);
652 27395 : SVCPermissions p1 = bestFirst->getPermissions();
653 27395 : SVCPermissions p2 = bestSecond == nullptr ? p1 : bestSecond->getPermissions();
654 95211 : for (NBEdge* e : n.getIncomingEdges()) {
655 : // @note: this rule might also apply if there are common permissions but
656 : // then we would not further rules to resolve the priority between the best edge and its parallel edge
657 67816 : SVCPermissions perm = e->getPermissions();
658 67816 : if (((GeomHelper::getMinAngleDiff(e->getAngleAtNode(&n), a1) < 10
659 39487 : || GeomHelper::getMinAngleDiff(e->getAngleAtNode(&n), a2) < 10))
660 83755 : && (p1 & perm) == 0 && (p2 & perm) == 0) {
661 350 : e->setJunctionPriority(&n, NBEdge::PRIORITY_ROAD);
662 : }
663 : }
664 27395 : }
665 :
666 :
667 : NBEdge*
668 53666 : NBEdgePriorityComputer::extractAndMarkFirst(NBNode& n, std::vector<NBEdge*>& s, int prio) {
669 53666 : if (s.size() == 0) {
670 : return nullptr;
671 : }
672 53666 : NBEdge* ret = s.front();
673 : s.erase(s.begin());
674 53666 : ret->setJunctionPriority(&n, prio);
675 53666 : return ret;
676 : }
677 :
678 :
679 : bool
680 128273 : NBEdgePriorityComputer::samePriority(const NBEdge* const e1, const NBEdge* const e2, SVCPermissions permissions) {
681 128273 : if (e1 == e2) {
682 : return true;
683 : }
684 73873 : if (e1->getPriority() != e2->getPriority()) {
685 : return false;
686 : }
687 58551 : if ((int) e1->getSpeed() != (int) e2->getSpeed()) {
688 : return false;
689 : }
690 54559 : return e1->getNumLanesThatAllow(permissions, false) == (int) e2->getNumLanesThatAllow(permissions, false);
691 : }
692 :
693 :
694 : bool
695 871 : NBEdgePriorityComputer::hasDifferentPriorities(const EdgeVector& edges, const NBEdge* excluded) {
696 871 : if (edges.size() < 2) {
697 : return false;
698 : }
699 871 : int prio = edges[0] == excluded ? edges[1]->getPriority() : edges[0]->getPriority();
700 2795 : for (auto e : edges) {
701 2021 : if (e != excluded && e->getPriority() != prio) {
702 : return true;
703 : }
704 : }
705 : return false;
706 : }
707 :
708 :
709 189889 : NBNodesEdgesSorter::crossing_by_junction_angle_sorter::crossing_by_junction_angle_sorter(const NBNode* node, const EdgeVector& ordering) {
710 : // reorder based on getAngleAtNodeToCenter
711 189889 : myOrdering = ordering;
712 189889 : sort(myOrdering.begin(), myOrdering.end(), NBContHelper::edge_by_angle_to_nodeShapeCentroid_sorter(node));
713 : // let the first edge remain the first
714 189889 : rotate(myOrdering.begin(), std::find(myOrdering.begin(), myOrdering.end(), ordering.front()), myOrdering.end());
715 189889 : }
716 :
717 :
718 : /****************************************************************************/
|
