Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2012-2026 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 5758 : NBTurningDirectionsComputer::computeTurnDirections(NBNodeCont& nc, bool warn) {
53 217364 : for (std::map<std::string, NBNode*>::const_iterator i = nc.begin(); i != nc.end(); ++i) {
54 211606 : computeTurnDirectionsForNode(i->second, warn);
55 : }
56 5758 : }
57 :
58 : void
59 216083 : 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 583129 : for (std::vector<NBEdge*>::const_iterator k = incoming.begin(); k != incoming.end(); ++k) {
64 367046 : (*k)->setTurningDestination(nullptr);
65 : }
66 : std::vector<Combination> combinations;
67 216083 : const bool geometryLike = node->geometryLike();
68 582920 : for (NBEdge* outedge : outgoing) {
69 1225114 : for (NBEdge* e : incoming) {
70 : // @todo: check whether NBHelpers::relAngle is properly defined and whether it should really be used, here
71 858277 : const double signedAngle = NBHelpers::normRelAngle(e->getAngleAtNode(node), outedge->getAngleAtNode(node));
72 858277 : 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 605908 : continue;
81 : }
82 612638 : 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 612638 : const bool badPermissions = ((outedge->getPermissions() & e->getPermissions() & ~SVC_PEDESTRIAN) == 0
89 87048 : && !geometryLike
90 694866 : && outedge->getPermissions() != e->getPermissions());
91 : if (e->getFromNode() == outedge->getToNode()
92 240173 : && (angle > 120 || e->getFromNode()->getPosition() == e->getToNode()->getPosition())
93 847644 : && !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 233389 : angle += 360;
105 : }
106 612638 : if (angle < 160) {
107 361053 : if (angle > 135) {
108 : // could be a turnaround with a green median island, look at
109 : // angle further away from the junction
110 5268 : const double inFA = getFarAngleAtNode(e, node);
111 5268 : const double outFA = getFarAngleAtNode(outedge, node);
112 5268 : 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 5268 : if (signedFarAngle > -160) {
119 4484 : continue;
120 : }
121 : } else {
122 355785 : continue;
123 : }
124 : }
125 252369 : if (badPermissions) {
126 : // penalty
127 5212 : angle -= 90;
128 : }
129 : Combination c;
130 252369 : c.from = e;
131 252369 : c.to = outedge;
132 252369 : c.angle = angle;
133 252369 : combinations.push_back(c);
134 : }
135 : }
136 : // sort combinations so that the ones with the highest angle are at the begin
137 216083 : 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 468452 : 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 494388 : if (seen.find((*j).from) != seen.end() || seen.find((*j).to) != seen.end()) {
151 : // do not regard already set edges
152 12377 : if ((*j).angle > 360 && warn) {
153 681 : WRITE_WARNINGF(TL("Ambiguity in turnarounds computation at junction '%'."), node->getID());
154 : //std::cout << " already seen: " << toString(seen) << "\n";
155 : warn = false;
156 : }
157 12377 : continue;
158 : }
159 : // mark as seen
160 239992 : seen.insert((*j).from);
161 239992 : seen.insert((*j).to);
162 : // set turnaround information
163 239992 : 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 239992 : (*j).from->setTurningDestination((*j).to, onlyPossible);
170 : }
171 216083 : }
172 :
173 :
174 : double
175 10536 : 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 10536 : if (e->getToNode() == n) {
181 : // search upstream
182 5268 : atNode = e->getGeometry().back();
183 5804 : while (dist > 0) {
184 5804 : const double length = next->getGeometry().length();
185 5804 : if (dist <= length) {
186 1956 : far = next->getGeometry().positionAtOffset(length - dist);
187 : break;
188 : } else {
189 3848 : far = next->getGeometry().front();
190 3848 : dist -= length;
191 3848 : 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 5268 : atNode = e->getGeometry().front();
203 6728 : while (dist > 0) {
204 6728 : const double length = next->getGeometry().length();
205 6728 : if (dist <= length) {
206 2530 : far = next->getGeometry().positionAtOffset(dist);
207 : break;
208 : } else {
209 4198 : far = next->getGeometry().back();
210 4198 : dist -= length;
211 4198 : if (next->getToNode()->getOutgoingEdges().size() == 1) {
212 1460 : 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 10536 : return GeomHelper::legacyDegree(angle);
222 : }
223 :
224 :
225 : // ---------------------------------------------------------------------------
226 : // NBNodesEdgesSorter
227 : // ---------------------------------------------------------------------------
228 : void
229 5591 : NBNodesEdgesSorter::sortNodesEdges(NBNodeCont& nc, bool useNodeShape) {
230 196210 : for (std::map<std::string, NBNode*>::const_iterator i = nc.begin(); i != nc.end(); ++i) {
231 190619 : i->second->sortEdges(useNodeShape);
232 : }
233 5591 : }
234 :
235 :
236 : void
237 631962 : NBNodesEdgesSorter::swapWhenReversed(const NBNode* const n,
238 : const std::vector<NBEdge*>::iterator& i1,
239 : const std::vector<NBEdge*>::iterator& i2) {
240 631962 : NBEdge* e1 = *i1;
241 631962 : 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 631962 : if (e2->getToNode() == n && e2->isTurningDirectionAt(e1)) {
247 : std::swap(*i1, *i2);
248 : }
249 631962 : }
250 :
251 :
252 : // ---------------------------------------------------------------------------
253 : // NBNodeTypeComputer
254 : // ---------------------------------------------------------------------------
255 : void
256 1841 : NBNodeTypeComputer::computeNodeTypes(NBNodeCont& nc, NBTrafficLightLogicCont& tlc) {
257 1841 : validateRailCrossings(nc, tlc);
258 1841 : const OptionsCont& oc = OptionsCont::getOptions();
259 3682 : const double rightBeforeLeftSpeed = oc.getFloat("junctions.right-before-left.speed-threshold");
260 59473 : for (const auto& nodeIt : nc) {
261 57632 : NBNode* const n = nodeIt.second;
262 : // the type may already be set from the data
263 57632 : if (n->myType != SumoXMLNodeType::UNKNOWN && n->myType != SumoXMLNodeType::DEAD_END) {
264 29529 : n->myTypeWasGuessed = false;
265 29529 : continue;
266 : }
267 : // check whether the node was set to be unregulated by the user
268 84309 : if (oc.getBool("keep-nodes-unregulated") || oc.isInStringVector("keep-nodes-unregulated.explicit", n->getID())
269 112412 : || (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 28196 : for (NBEdge* e : n->getEdges()) {
276 28168 : if (!isWaterway(e->getPermissions())) {
277 : waterway = false;
278 : break;
279 : }
280 : }
281 28103 : 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 28075 : if (n->myIncomingEdges.size() == 1) {
288 13633 : n->myType = SumoXMLNodeType::PRIORITY;
289 13633 : continue;
290 : }
291 : // @todo "isSimpleContinuation" should be revalidated
292 14442 : if (n->isSimpleContinuation()) {
293 1408 : n->myType = SumoXMLNodeType::PRIORITY;
294 1408 : continue;
295 : }
296 13034 : if (isRailwayNode(n)) {
297 333 : if (n->unsignalizedOperation()
298 73 : && (int)n->getIncomingEdges().size() == 2
299 392 : && (int)n->getOutgoingEdges().size() == 1) {
300 : // avoid slowing down when there are no foe vehicles
301 46 : n->myType = SumoXMLNodeType::ZIPPER;
302 : } else {
303 : // priority instead of unregulated to ensure that collisions can be detected
304 287 : n->myType = SumoXMLNodeType::PRIORITY;
305 : }
306 333 : continue;
307 : }
308 : // determine the type
309 25402 : SumoXMLNodeType type = oc.getBool("junctions.left-before-right") ? SumoXMLNodeType::LEFT_BEFORE_RIGHT : SumoXMLNodeType::RIGHT_BEFORE_LEFT;
310 38954 : for (EdgeVector::const_iterator i = n->myIncomingEdges.begin(); i != n->myIncomingEdges.end(); i++) {
311 36562 : 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 19719 : if (n->getOppositeIncoming(*j) == *i && n->myIncomingEdges.size() > 2) {
314 5407 : continue;
315 : }
316 : // @todo check against a legal document
317 : // @todo figure out when SumoXMLNodeType::PRIORITY_STOP is appropriate
318 14312 : const double s1 = (*i)->getSpeed();
319 14312 : const double s2 = (*j)->getSpeed();
320 14312 : const int p1 = (*i)->getPriority();
321 14312 : const int p2 = (*j)->getPriority();
322 23873 : 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 12701 : n->myType = type;
330 12701 : n->myTypeWasGuessed = true;
331 : }
332 1841 : }
333 :
334 :
335 : void
336 1997 : NBNodeTypeComputer::validateRailCrossings(NBNodeCont& nc, NBTrafficLightLogicCont& tlc) {
337 82862 : for (std::map<std::string, NBNode*>::const_iterator i = nc.begin(); i != nc.end(); ++i) {
338 80865 : NBNode* n = (*i).second;
339 80865 : 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 2267 : for (NBEdge* e : n->getIncomingEdges()) {
347 1492 : if ((e->getPermissions() & ~SVC_RAIL_CLASSES) != 0) {
348 576 : numNonRailIn += 1;
349 576 : if (e->getPermissions() != SVC_PEDESTRIAN) {
350 170 : numNonRailwayNonPed++;
351 : }
352 576 : nonRailNodes.insert(e->getFromNode());
353 916 : } else if ((e->getPermissions() & SVC_RAIL_CLASSES) != 0) {
354 916 : numRailway++;
355 : }
356 : }
357 2261 : for (NBEdge* e : n->getOutgoingEdges()) {
358 1486 : if ((e->getPermissions() & ~SVC_RAIL_CLASSES) != 0) {
359 573 : numNonRailOut += 1;
360 573 : nonRailNodes.insert(e->getToNode());
361 : }
362 : }
363 775 : if (numNonRailIn == 0 || numNonRailOut == 0 || numRailway == 0) {
364 : // not a crossing (maybe unregulated or rail_signal)
365 999 : WRITE_WARNINGF(TL("Converting invalid rail_crossing to priority junction '%'."), n->getID());
366 333 : n->myType = SumoXMLNodeType::PRIORITY;
367 442 : } 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 1997 : }
384 :
385 :
386 : bool
387 110774 : NBNodeTypeComputer::isRailwayNode(const NBNode* n) {
388 : bool hasRailway = false;
389 118309 : for (NBEdge* e : n->getIncomingEdges()) {
390 112682 : if ((e->getPermissions() & ~(SVC_RAIL_CLASSES | SVC_TAXI)) != 0) {
391 : return false;
392 7535 : } 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 1841 : NBEdgePriorityComputer::computeEdgePriorities(NBNodeCont& nc) {
404 59473 : for (const auto& node : nc) {
405 : // preset all junction's edge priorities to zero
406 264522 : for (NBEdge* const edge : node.second->myAllEdges) {
407 206890 : edge->setJunctionPriority(node.second, NBEdge::JunctionPriority::MINOR_ROAD);
408 : }
409 57632 : node.second->markBentPriority(false);
410 : // check if the junction is not a real junction
411 57632 : if (node.second->myIncomingEdges.size() == 1 && node.second->myOutgoingEdges.size() == 1) {
412 16149 : 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 31222 : 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 31218 : setPriorityJunctionPriorities(*node.second);
425 : }
426 : }
427 : }
428 1841 : }
429 :
430 :
431 : void
432 31658 : NBEdgePriorityComputer::setPriorityJunctionPriorities(NBNode& n, bool forceStraight) {
433 31658 : if (n.myIncomingEdges.size() == 0 || n.myOutgoingEdges.size() == 0) {
434 15320 : 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 168600 : for (NBEdge* const edge : n.myAllEdges) {
443 140606 : all |= edge->getPermissions();
444 : }
445 : if ((all & (SVC_PASSENGER & SVC_TRAM & SVC_BUS)) != 0) {
446 : all = (SVC_PASSENGER & SVC_TRAM & SVC_BUS);
447 27994 : } else if ((all & ~SVC_VULNERABLE) != 0) {
448 : all &= ~SVC_VULNERABLE;
449 : }
450 27994 : if (forceStraight) {
451 : // called a second time, preset all junction's edge priorities to zero
452 2942 : for (NBEdge* const edge : n.myAllEdges) {
453 2502 : edge->setJunctionPriority(&n, NBEdge::JunctionPriority::MINOR_ROAD);
454 : minPrio = MIN2(minPrio, edge->getPriority());
455 : maxPrio = MAX2(maxPrio, edge->getPriority());
456 2502 : maxNumLanes = MAX2(maxNumLanes, edge->getNumLanesThatAllow(all, false));
457 2502 : maxSpeed = MAX2(maxSpeed, edge->getSpeed());
458 : }
459 : }
460 27994 : EdgeVector incoming = n.myIncomingEdges;
461 27994 : 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 27994 : std::sort(incoming.begin(), incoming.end(), NBContHelper::edge_by_priority_sorter(all));
466 : EdgeVector bestIncoming;
467 27994 : NBEdge* bestIn = incoming[0];
468 81339 : while (incoming.size() > 0 && (forceStraight || samePriority(bestIn, incoming[0], all))) {
469 53345 : 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 27994 : sort(outgoing.begin(), outgoing.end(), NBContHelper::edge_by_priority_sorter(all));
475 : EdgeVector bestOutgoing;
476 27994 : const NBEdge* const firstOut = outgoing[0];
477 83799 : while (outgoing.size() > 0 && (forceStraight || samePriority(firstOut, outgoing[0], all))) { //->getPriority()==best->getPriority())
478 55805 : bestOutgoing.push_back(*outgoing.begin());
479 : outgoing.erase(outgoing.begin());
480 : }
481 : // special case: user input makes mainDirection unambiguous
482 : const bool mainDirectionExplicit = (
483 11656 : bestIncoming.size() == 1 && n.myIncomingEdges.size() <= 2
484 9902 : && (incoming.size() == 0 || bestIncoming[0]->getPriority() > incoming[0]->getPriority())
485 8294 : && bestOutgoing.size() == 1 && n.myOutgoingEdges.size() <= 2
486 4965 : && (outgoing.size() == 0 || bestOutgoing[0]->getPriority() > outgoing[0]->getPriority())
487 32291 : && !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 27994 : incoming = n.myIncomingEdges;
495 27994 : outgoing = n.myOutgoingEdges;
496 81339 : for (i = bestIncoming.begin(); i != bestIncoming.end(); ++i) {
497 106690 : std::sort(incoming.begin(), incoming.end(), NBContHelper::edge_opposite_direction_sorter(*i, &n, !forceStraight));
498 53345 : counterIncomingEdges[*i] = *incoming.begin();
499 106690 : std::sort(outgoing.begin(), outgoing.end(), NBContHelper::edge_opposite_direction_sorter(*i, &n, !forceStraight));
500 53345 : 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 27994 : if (bestIncoming.size() == 1) {
530 : // let's mark this road as the best
531 11656 : NBEdge* best1 = extractAndMarkFirst(n, bestIncoming);
532 19378 : 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 7722 : NBEdge* s = counterIncomingEdges.find(best1)->second;
537 7722 : const double minAngleDiff = GeomHelper::getMinAngleDiff(best1->getAngleAtNode(&n), s->getAngleAtNode(&n));
538 : if (minAngleDiff > 180 - 45
539 7722 : || (minAngleDiff > 75 && s->getPriority() == best1->getPriority() && hasDifferentPriorities(incoming, best1))) {
540 1685 : s->setJunctionPriority(&n, NBEdge::PRIORITY_ROAD);
541 : }
542 : }
543 11656 : markBestParallel(n, best1, nullptr);
544 : assert(bestOutgoing.size() != 0);
545 : // mark the best outgoing as the continuation
546 11656 : sort(bestOutgoing.begin(), bestOutgoing.end(), NBContHelper::edge_similar_direction_sorter(best1));
547 : // assign extra priority if the priorities are unambiguous (regardless of geometry)
548 11656 : NBEdge* bestOut = extractAndMarkFirst(n, bestOutgoing);
549 19378 : 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 11656 : 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 11656 : if (isBent && hasTLS && !forceStraight) {
562 : // redo but force straight computation
563 196 : 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 58027 : for (i = bestIncoming.begin(); i != bestIncoming.end(); ++i) {
578 : EdgeVector::iterator j;
579 41689 : NBEdge* t1 = *i;
580 41689 : double angle1 = t1->getAngleAtNode(&n) + 180;
581 41689 : if (angle1 >= 360) {
582 0 : angle1 -= 360;
583 : }
584 79596 : for (j = i + 1; j != bestIncoming.end(); ++j) {
585 37907 : NBEdge* t2 = *j;
586 37907 : double angle2 = t2->getAngleAtNode(&n) + 180;
587 37907 : if (angle2 >= 360) {
588 0 : angle2 -= 360;
589 : }
590 37907 : double score = forceStraight ? getScore(t1, t2, minPrio, maxPrio, maxNumLanes, maxSpeed, all) : 0;
591 37907 : double angle = GeomHelper::getMinAngleDiff(angle1, angle2) + 45 * score;
592 37907 : 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 22473 : bestFirst = *i;
596 22473 : bestSecond = *j;
597 : }
598 : }
599 : }
600 16338 : bestFirst->setJunctionPriority(&n, NBEdge::PRIORITY_ROAD);
601 16338 : 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 16338 : if (bestOutgoing.size() != 0) {
608 16338 : extractAndMarkFirst(n, bestOutgoing);
609 : }
610 16338 : bestSecond->setJunctionPriority(&n, NBEdge::PRIORITY_ROAD);
611 16338 : 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 16338 : if (bestOutgoing.size() != 0) {
618 14684 : extractAndMarkFirst(n, bestOutgoing);
619 : }
620 16338 : const bool isBent = GeomHelper::getMinAngleDiff(bestFirst->getAngleAtNode(&n), bestSecond->getAngleAtNode(&n)) < 135;
621 16338 : if (isBent && hasTLS && !forceStraight) {
622 : // redo but force straight computation
623 244 : setPriorityJunctionPriorities(n, true);
624 : } else {
625 : n.markBentPriority(isBent);
626 16094 : markBestParallel(n, bestFirst, bestSecond);
627 : }
628 27994 : }
629 :
630 : double
631 1629 : 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 1629 : 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 1629 : * e1->getNumLanesThatAllow(permissions, false) / maxNumLanes
641 1629 : * e1->getSpeed() / maxSpeed
642 1629 : * normPrio2
643 1629 : * e2->getNumLanesThatAllow(permissions, false) / maxNumLanes
644 1629 : * e2->getSpeed() / maxSpeed);
645 : }
646 :
647 : void
648 27750 : NBEdgePriorityComputer::markBestParallel(const NBNode& n, NBEdge* bestFirst, NBEdge* bestSecond) {
649 : // edges running parallel to the main direction should also be prioritised
650 27750 : const double a1 = bestFirst->getAngleAtNode(&n);
651 27750 : const double a2 = bestSecond == nullptr ? a1 : bestSecond->getAngleAtNode(&n);
652 27750 : SVCPermissions p1 = bestFirst->getPermissions();
653 27750 : SVCPermissions p2 = bestSecond == nullptr ? p1 : bestSecond->getPermissions();
654 96374 : 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 68624 : SVCPermissions perm = e->getPermissions();
658 68624 : if (((GeomHelper::getMinAngleDiff(e->getAngleAtNode(&n), a1) < 10
659 39924 : || GeomHelper::getMinAngleDiff(e->getAngleAtNode(&n), a2) < 10))
660 84871 : && (p1 & perm) == 0 && (p2 & perm) == 0) {
661 345 : e->setJunctionPriority(&n, NBEdge::PRIORITY_ROAD);
662 : }
663 : }
664 27750 : }
665 :
666 :
667 : NBEdge*
668 54334 : NBEdgePriorityComputer::extractAndMarkFirst(NBNode& n, std::vector<NBEdge*>& s, int prio) {
669 54334 : if (s.size() == 0) {
670 : return nullptr;
671 : }
672 54334 : NBEdge* ret = s.front();
673 : s.erase(s.begin());
674 54334 : ret->setJunctionPriority(&n, prio);
675 54334 : return ret;
676 : }
677 :
678 :
679 : bool
680 129899 : NBEdgePriorityComputer::samePriority(const NBEdge* const e1, const NBEdge* const e2, SVCPermissions permissions) {
681 129899 : if (e1 == e2) {
682 : return true;
683 : }
684 74791 : if (e1->getPriority() != e2->getPriority()) {
685 : return false;
686 : }
687 59475 : if ((int) e1->getSpeed() != (int) e2->getSpeed()) {
688 : return false;
689 : }
690 55447 : return e1->getNumLanesThatAllow(permissions, false) == (int) e2->getNumLanesThatAllow(permissions, false);
691 : }
692 :
693 :
694 : bool
695 874 : NBEdgePriorityComputer::hasDifferentPriorities(const EdgeVector& edges, const NBEdge* excluded) {
696 874 : if (edges.size() < 2) {
697 : return false;
698 : }
699 874 : int prio = edges[0] == excluded ? edges[1]->getPriority() : edges[0]->getPriority();
700 2805 : for (auto e : edges) {
701 2028 : if (e != excluded && e->getPriority() != prio) {
702 : return true;
703 : }
704 : }
705 : return false;
706 : }
707 :
708 :
709 191500 : NBNodesEdgesSorter::crossing_by_junction_angle_sorter::crossing_by_junction_angle_sorter(const NBNode* node, const EdgeVector& ordering) {
710 : // reorder based on getAngleAtNodeToCenter
711 191500 : myOrdering = ordering;
712 191500 : sort(myOrdering.begin(), myOrdering.end(), NBContHelper::edge_by_angle_to_nodeShapeCentroid_sorter(node));
713 : // let the first edge remain the first
714 191500 : rotate(myOrdering.begin(), std::find(myOrdering.begin(), myOrdering.end(), ordering.front()), myOrdering.end());
715 191500 : }
716 :
717 :
718 : /****************************************************************************/
|
