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.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 5333 : NBTurningDirectionsComputer::computeTurnDirections(NBNodeCont& nc, bool warn) {
53 195413 : for (std::map<std::string, NBNode*>::const_iterator i = nc.begin(); i != nc.end(); ++i) {
54 190080 : computeTurnDirectionsForNode(i->second, warn);
55 : }
56 5333 : }
57 :
58 : void
59 192159 : 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 516362 : for (std::vector<NBEdge*>::const_iterator k = incoming.begin(); k != incoming.end(); ++k) {
64 324203 : (*k)->setTurningDestination(nullptr);
65 : }
66 : std::vector<Combination> combinations;
67 192159 : const bool geometryLike = node->geometryLike();
68 516126 : for (NBEdge* outedge : outgoing) {
69 1081612 : for (NBEdge* e : incoming) {
70 : // @todo: check whether NBHelpers::relAngle is properly defined and whether it should really be used, here
71 757645 : const double signedAngle = NBHelpers::normRelAngle(e->getAngleAtNode(node), outedge->getAngleAtNode(node));
72 757645 : 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 537655 : continue;
81 : }
82 538142 : 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 538142 : const bool badPermissions = ((outedge->getPermissions() & e->getPermissions() & ~SVC_PEDESTRIAN) == 0
89 83049 : && !geometryLike
90 616505 : && outedge->getPermissions() != e->getPermissions());
91 : if (e->getFromNode() == outedge->getToNode()
92 208722 : && (angle > 120 || e->getFromNode()->getPosition() == e->getToNode()->getPosition())
93 743166 : && !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 203395 : angle += 360;
105 : }
106 538142 : if (angle < 160) {
107 318818 : if (angle > 135) {
108 : // could be a turnaround with a green median island, look at
109 : // angle further away from the junction
110 4416 : const double inFA = getFarAngleAtNode(e, node);
111 4416 : const double outFA = getFarAngleAtNode(outedge, node);
112 4416 : 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 4416 : if (signedFarAngle > -160) {
119 3750 : continue;
120 : }
121 : } else {
122 314402 : continue;
123 : }
124 : }
125 219990 : if (badPermissions) {
126 : // penalty
127 5179 : angle -= 90;
128 : }
129 : Combination c;
130 219990 : c.from = e;
131 219990 : c.to = outedge;
132 219990 : c.angle = angle;
133 219990 : combinations.push_back(c);
134 : }
135 : }
136 : // sort combinations so that the ones with the highest angle are at the begin
137 192159 : 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 412149 : 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 432379 : if (seen.find((*j).from) != seen.end() || seen.find((*j).to) != seen.end()) {
151 : // do not regard already set edges
152 9470 : if ((*j).angle > 360 && warn) {
153 462 : WRITE_WARNINGF(TL("Ambiguity in turnarounds computation at junction '%'."), node->getID());
154 : //std::cout << " already seen: " << toString(seen) << "\n";
155 : warn = false;
156 : }
157 9470 : continue;
158 : }
159 : // mark as seen
160 210520 : seen.insert((*j).from);
161 210520 : seen.insert((*j).to);
162 : // set turnaround information
163 210520 : 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 210520 : (*j).from->setTurningDestination((*j).to, onlyPossible);
170 : }
171 192159 : }
172 :
173 :
174 : double
175 8832 : 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 8832 : if (e->getToNode() == n) {
181 : // search upstream
182 4416 : atNode = e->getGeometry().back();
183 4757 : while (dist > 0) {
184 4757 : const double length = next->getGeometry().length();
185 4757 : if (dist <= length) {
186 1692 : far = next->getGeometry().positionAtOffset(length - dist);
187 1692 : break;
188 : } else {
189 3065 : far = next->getGeometry().front();
190 3065 : dist -= length;
191 3065 : if (next->getToNode()->getIncomingEdges().size() == 1) {
192 341 : 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 4416 : atNode = e->getGeometry().front();
203 5584 : while (dist > 0) {
204 5584 : const double length = next->getGeometry().length();
205 5584 : if (dist <= length) {
206 2158 : far = next->getGeometry().positionAtOffset(dist);
207 2158 : break;
208 : } else {
209 3426 : far = next->getGeometry().back();
210 3426 : dist -= length;
211 3426 : if (next->getToNode()->getOutgoingEdges().size() == 1) {
212 1168 : 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 8832 : return GeomHelper::legacyDegree(angle);
222 : }
223 :
224 :
225 : // ---------------------------------------------------------------------------
226 : // NBNodesEdgesSorter
227 : // ---------------------------------------------------------------------------
228 : void
229 5171 : NBNodesEdgesSorter::sortNodesEdges(NBNodeCont& nc, bool useNodeShape) {
230 174703 : for (std::map<std::string, NBNode*>::const_iterator i = nc.begin(); i != nc.end(); ++i) {
231 169532 : i->second->sortEdges(useNodeShape);
232 : }
233 5171 : }
234 :
235 :
236 : void
237 557584 : NBNodesEdgesSorter::swapWhenReversed(const NBNode* const n,
238 : const std::vector<NBEdge*>::iterator& i1,
239 : const std::vector<NBEdge*>::iterator& i2) {
240 557584 : NBEdge* e1 = *i1;
241 557584 : 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 557584 : if (e2->getToNode() == n && e2->isTurningDirectionAt(e1)) {
247 : std::swap(*i1, *i2);
248 : }
249 557584 : }
250 :
251 :
252 : // ---------------------------------------------------------------------------
253 : // NBNodeTypeComputer
254 : // ---------------------------------------------------------------------------
255 : void
256 1704 : NBNodeTypeComputer::computeNodeTypes(NBNodeCont& nc, NBTrafficLightLogicCont& tlc) {
257 1704 : validateRailCrossings(nc, tlc);
258 1704 : const OptionsCont& oc = OptionsCont::getOptions();
259 3408 : const double rightBeforeLeftSpeed = oc.getFloat("junctions.right-before-left.speed-threshold");
260 52507 : for (const auto& nodeIt : nc) {
261 50803 : NBNode* const n = nodeIt.second;
262 : // the type may already be set from the data
263 50803 : if (n->myType != SumoXMLNodeType::UNKNOWN && n->myType != SumoXMLNodeType::DEAD_END) {
264 23766 : n->myTypeWasGuessed = false;
265 23766 : continue;
266 : }
267 : // check whether the node was set to be unregulated by the user
268 81111 : if (oc.getBool("keep-nodes-unregulated") || oc.isInStringVector("keep-nodes-unregulated.explicit", n->getID())
269 108148 : || (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 27130 : for (NBEdge* e : n->getEdges()) {
276 27102 : if (!isWaterway(e->getPermissions())) {
277 : waterway = false;
278 : break;
279 : }
280 : }
281 27037 : 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 27009 : if (n->myIncomingEdges.size() == 1) {
288 13086 : n->myType = SumoXMLNodeType::PRIORITY;
289 13086 : continue;
290 : }
291 : // @todo "isSimpleContinuation" should be revalidated
292 13923 : if (n->isSimpleContinuation()) {
293 1322 : n->myType = SumoXMLNodeType::PRIORITY;
294 1322 : continue;
295 : }
296 12601 : if (isRailwayNode(n)) {
297 : // priority instead of unregulated to ensure that collisions can be detected
298 317 : n->myType = SumoXMLNodeType::PRIORITY;
299 317 : continue;
300 : }
301 : // determine the type
302 24568 : SumoXMLNodeType type = oc.getBool("junctions.left-before-right") ? SumoXMLNodeType::LEFT_BEFORE_RIGHT : SumoXMLNodeType::RIGHT_BEFORE_LEFT;
303 38032 : for (EdgeVector::const_iterator i = n->myIncomingEdges.begin(); i != n->myIncomingEdges.end(); i++) {
304 35909 : for (EdgeVector::const_iterator j = i + 1; j != n->myIncomingEdges.end(); j++) {
305 : // @todo "getOppositeIncoming" should probably be refactored into something the edge knows
306 19325 : if (n->getOppositeIncoming(*j) == *i && n->myIncomingEdges.size() > 2) {
307 5278 : continue;
308 : }
309 : // @todo check against a legal document
310 : // @todo figure out when SumoXMLNodeType::PRIORITY_STOP is appropriate
311 14047 : const double s1 = (*i)->getSpeed();
312 14047 : const double s2 = (*j)->getSpeed();
313 14047 : const int p1 = (*i)->getPriority();
314 14047 : const int p2 = (*j)->getPriority();
315 23353 : if (fabs(s1 - s2) > (9.5 / 3.6) || MAX2(s1, s2) >= rightBeforeLeftSpeed || p1 != p2) {
316 : type = SumoXMLNodeType::PRIORITY;
317 : break;
318 : }
319 : }
320 : }
321 : // save type
322 12284 : n->myType = type;
323 12284 : n->myTypeWasGuessed = true;
324 : }
325 1704 : }
326 :
327 :
328 : void
329 1851 : NBNodeTypeComputer::validateRailCrossings(NBNodeCont& nc, NBTrafficLightLogicCont& tlc) {
330 75287 : for (std::map<std::string, NBNode*>::const_iterator i = nc.begin(); i != nc.end(); ++i) {
331 73436 : NBNode* n = (*i).second;
332 73436 : if (n->myType == SumoXMLNodeType::RAIL_CROSSING) {
333 : // check if it really is a rail crossing
334 : int numRailway = 0;
335 : int numNonRailIn = 0;
336 : int numNonRailOut = 0;
337 : std::set<const NBNode*> nonRailNodes;
338 : int numNonRailwayNonPed = 0;
339 2201 : for (NBEdge* e : n->getIncomingEdges()) {
340 1458 : if ((e->getPermissions() & ~SVC_RAIL_CLASSES) != 0) {
341 566 : numNonRailIn += 1;
342 566 : if (e->getPermissions() != SVC_PEDESTRIAN) {
343 160 : numNonRailwayNonPed++;
344 : }
345 566 : nonRailNodes.insert(e->getFromNode());
346 892 : } else if ((e->getPermissions() & SVC_RAIL_CLASSES) != 0) {
347 892 : numRailway++;
348 : }
349 : }
350 2195 : for (NBEdge* e : n->getOutgoingEdges()) {
351 1452 : if ((e->getPermissions() & ~SVC_RAIL_CLASSES) != 0) {
352 563 : numNonRailOut += 1;
353 563 : nonRailNodes.insert(e->getToNode());
354 : }
355 : }
356 743 : if (numNonRailIn == 0 || numNonRailOut == 0 || numRailway == 0) {
357 : // not a crossing (maybe unregulated or rail_signal)
358 909 : WRITE_WARNINGF(TL("Converting invalid rail_crossing to priority junction '%'."), n->getID());
359 303 : n->myType = SumoXMLNodeType::PRIORITY;
360 440 : } else if (numNonRailwayNonPed > 2 || nonRailNodes.size() > 2) {
361 : // does not look like a rail crossing (roads in conflict). maybe a traffic light?
362 75 : WRITE_WARNINGF(TL("Converting invalid rail_crossing to traffic_light at junction '%'."), n->getID());
363 25 : TrafficLightType type = SUMOXMLDefinitions::TrafficLightTypes.get(OptionsCont::getOptions().getString("tls.default-type"));
364 25 : NBTrafficLightDefinition* tlDef = new NBOwnTLDef(n->getID(), n, 0, type);
365 25 : n->myType = SumoXMLNodeType::TRAFFIC_LIGHT;
366 25 : if (!tlc.insert(tlDef)) {
367 : // actually, nothing should fail here
368 0 : n->removeTrafficLight(tlDef);
369 0 : n->myType = SumoXMLNodeType::PRIORITY;
370 0 : delete tlDef;
371 0 : WRITE_WARNINGF(TL("Could not allocate tls '%'."), n->getID());
372 : }
373 : }
374 : }
375 : }
376 1851 : }
377 :
378 :
379 : bool
380 102500 : NBNodeTypeComputer::isRailwayNode(const NBNode* n) {
381 : bool hasRailway = false;
382 107673 : for (NBEdge* e : n->getIncomingEdges()) {
383 103106 : if ((e->getPermissions() & ~(SVC_RAIL_CLASSES | SVC_TAXI)) != 0) {
384 : return false;
385 5173 : } else if ((e->getPermissions() & SVC_RAIL_CLASSES) != 0) {
386 : hasRailway = true;
387 : }
388 : }
389 : return hasRailway;
390 : }
391 :
392 : // ---------------------------------------------------------------------------
393 : // NBEdgePriorityComputer
394 : // ---------------------------------------------------------------------------
395 : void
396 1704 : NBEdgePriorityComputer::computeEdgePriorities(NBNodeCont& nc) {
397 52507 : for (const auto& node : nc) {
398 : // preset all junction's edge priorities to zero
399 232523 : for (NBEdge* const edge : node.second->myAllEdges) {
400 181720 : edge->setJunctionPriority(node.second, NBEdge::JunctionPriority::MINOR_ROAD);
401 : }
402 50803 : node.second->markBentPriority(false);
403 : // check if the junction is not a real junction
404 50803 : if (node.second->myIncomingEdges.size() == 1 && node.second->myOutgoingEdges.size() == 1) {
405 14437 : continue;
406 : }
407 : // compute the priorities on junction when needed
408 : if (node.second->getType() != SumoXMLNodeType::RIGHT_BEFORE_LEFT
409 : && node.second->getType() != SumoXMLNodeType::LEFT_BEFORE_RIGHT
410 : && node.second->getType() != SumoXMLNodeType::ALLWAY_STOP
411 : && node.second->getType() != SumoXMLNodeType::NOJUNCTION) {
412 27085 : if (node.second->getRightOfWay() == RightOfWay::EDGEPRIORITY) {
413 24 : for (NBEdge* e : node.second->getIncomingEdges()) {
414 20 : e->setJunctionPriority(node.second, e->getPriority());
415 : }
416 : } else {
417 27081 : setPriorityJunctionPriorities(*node.second);
418 : }
419 : }
420 : }
421 1704 : }
422 :
423 :
424 : void
425 27475 : NBEdgePriorityComputer::setPriorityJunctionPriorities(NBNode& n, bool forceStraight) {
426 27475 : if (n.myIncomingEdges.size() == 0 || n.myOutgoingEdges.size() == 0) {
427 13117 : return;
428 : }
429 : int minPrio = std::numeric_limits<int>::max();
430 : int maxPrio = -std::numeric_limits<int>::max();
431 : int maxNumLanes = -std::numeric_limits<int>::max();
432 : double maxSpeed = -std::numeric_limits<double>::max();
433 24124 : if (forceStraight) {
434 : // called a second time, preset all junction's edge priorities to zero
435 2752 : for (NBEdge* const edge : n.myAllEdges) {
436 2358 : edge->setJunctionPriority(&n, NBEdge::JunctionPriority::MINOR_ROAD);
437 : minPrio = MIN2(minPrio, edge->getPriority());
438 : maxPrio = MAX2(maxPrio, edge->getPriority());
439 : maxNumLanes = MAX2(maxNumLanes, edge->getNumLanes());
440 2358 : maxSpeed = MAX2(maxSpeed, edge->getSpeed());
441 : }
442 : }
443 24124 : EdgeVector incoming = n.myIncomingEdges;
444 24124 : EdgeVector outgoing = n.myOutgoingEdges;
445 : // what we do want to have is to extract the pair of roads that are
446 : // the major roads for this junction
447 : // let's get the list of incoming edges with the highest priority
448 24124 : std::sort(incoming.begin(), incoming.end(), NBContHelper::edge_by_priority_sorter());
449 : EdgeVector bestIncoming;
450 24124 : NBEdge* bestIn = incoming[0];
451 71052 : while (incoming.size() > 0 && (forceStraight || samePriority(bestIn, incoming[0]))) {
452 46928 : bestIncoming.push_back(*incoming.begin());
453 : incoming.erase(incoming.begin());
454 : }
455 : // now, let's get the list of best outgoing
456 : assert(outgoing.size() != 0);
457 24124 : sort(outgoing.begin(), outgoing.end(), NBContHelper::edge_by_priority_sorter());
458 : EdgeVector bestOutgoing;
459 24124 : const NBEdge* const firstOut = outgoing[0];
460 73330 : while (outgoing.size() > 0 && (forceStraight || samePriority(firstOut, outgoing[0]))) { //->getPriority()==best->getPriority())
461 49206 : bestOutgoing.push_back(*outgoing.begin());
462 : outgoing.erase(outgoing.begin());
463 : }
464 : // special case: user input makes mainDirection unambiguous
465 : const bool mainDirectionExplicit = (
466 9766 : bestIncoming.size() == 1 && n.myIncomingEdges.size() <= 2
467 8173 : && (incoming.size() == 0 || bestIncoming[0]->getPriority() > incoming[0]->getPriority())
468 6883 : && bestOutgoing.size() == 1 && n.myOutgoingEdges.size() <= 2
469 3919 : && (outgoing.size() == 0 || bestOutgoing[0]->getPriority() > outgoing[0]->getPriority())
470 27499 : && !bestIncoming[0]->isTurningDirectionAt(bestOutgoing[0]));
471 : // now, let's compute for each of the best incoming edges
472 : // the incoming which is most opposite
473 : // the outgoing which is most opposite
474 : EdgeVector::iterator i;
475 : std::map<NBEdge*, NBEdge*> counterIncomingEdges;
476 : std::map<NBEdge*, NBEdge*> counterOutgoingEdges;
477 24124 : incoming = n.myIncomingEdges;
478 24124 : outgoing = n.myOutgoingEdges;
479 71052 : for (i = bestIncoming.begin(); i != bestIncoming.end(); ++i) {
480 93856 : std::sort(incoming.begin(), incoming.end(), NBContHelper::edge_opposite_direction_sorter(*i, &n, !forceStraight));
481 46928 : counterIncomingEdges[*i] = *incoming.begin();
482 93856 : std::sort(outgoing.begin(), outgoing.end(), NBContHelper::edge_opposite_direction_sorter(*i, &n, !forceStraight));
483 46928 : counterOutgoingEdges[*i] = *outgoing.begin();
484 : }
485 : #ifdef DEBUG_SETPRIORITIES
486 : if (DEBUGCOND) {
487 : std::map<std::string, std::string> tmp1;
488 : for (auto item : counterIncomingEdges) {
489 : tmp1[item.first->getID()] = item.second->getID();
490 : }
491 : std::map<std::string, std::string> tmp2;
492 : for (auto item : counterOutgoingEdges) {
493 : tmp2[item.first->getID()] = item.second->getID();
494 : }
495 : std::cout << "n=" << n.getID() << " bestIn=" << bestIn->getID() << " bestOut=" << toString(bestOutgoing)
496 : << " counterBest=" << counterIncomingEdges.find(bestIncoming[0])->second->getID()
497 : << " mainExplicit=" << mainDirectionExplicit
498 : << " forceStraight=" << forceStraight
499 : << "\n bestIncoming=" << toString(bestIncoming) << " allIncoming=" << toString(incoming)
500 : << "\n bestOutgoing=" << toString(bestOutgoing) << " allOutgoing=" << toString(outgoing)
501 : << "\n counterIncomingEdges=" << toString(tmp1)
502 : << "\n counterOutgoingEdges=" << toString(tmp2)
503 : << "\n";
504 : }
505 : #endif
506 : // at a tls junction we must prevent an underlying bent-priority layout
507 : // because that would lead to invalid right-of-way rules for an oncoming
508 : // tls layout (but not vice versa). See #7764
509 : const bool hasTLS = n.isTLControlled();
510 : // ok, let's try
511 : // 1) there is one best incoming road
512 24124 : if (bestIncoming.size() == 1) {
513 : // let's mark this road as the best
514 9766 : NBEdge* best1 = extractAndMarkFirst(n, bestIncoming);
515 16478 : if (!mainDirectionExplicit && counterIncomingEdges.find(best1) != counterIncomingEdges.end()) {
516 : // ok, look, what we want is the opposite of the straight continuation edge
517 : // but, what if such an edge does not exist? By now, we'll determine it
518 : // geometrically
519 6712 : NBEdge* s = counterIncomingEdges.find(best1)->second;
520 6712 : const double minAngleDiff = GeomHelper::getMinAngleDiff(best1->getAngleAtNode(&n), s->getAngleAtNode(&n));
521 : if (minAngleDiff > 180 - 45
522 6712 : || (minAngleDiff > 75 && s->getPriority() == best1->getPriority() && hasDifferentPriorities(incoming, best1))) {
523 1539 : s->setJunctionPriority(&n, NBEdge::PRIORITY_ROAD);
524 : }
525 : }
526 9766 : markBestParallel(n, best1, nullptr);
527 : assert(bestOutgoing.size() != 0);
528 : // mark the best outgoing as the continuation
529 9766 : sort(bestOutgoing.begin(), bestOutgoing.end(), NBContHelper::edge_similar_direction_sorter(best1));
530 : // assign extra priority if the priorities are unambiguous (regardless of geometry)
531 9766 : NBEdge* bestOut = extractAndMarkFirst(n, bestOutgoing);
532 16478 : if (!mainDirectionExplicit && counterOutgoingEdges.find(bestOut) != counterOutgoingEdges.end()) {
533 0 : NBEdge* s = counterOutgoingEdges.find(bestOut)->second;
534 0 : if (GeomHelper::getMinAngleDiff(bestOut->getAngleAtNode(&n), s->getAngleAtNode(&n)) > 180 - 45) {
535 0 : s->setJunctionPriority(&n, NBEdge::PRIORITY_ROAD);
536 : }
537 : }
538 9766 : const bool isBent = n.getDirection(best1, bestOut) != LinkDirection::STRAIGHT;
539 : #ifdef DEBUG_SETPRIORITIES
540 : if (DEBUGCOND) {
541 : std::cout << " best1=" << best1->getID() << " bestOut=" << bestOut->getID() << " bestOutgoing=" << toString(bestOutgoing) << " mainDirectionExplicit=" << mainDirectionExplicit << " isBent=" << isBent << "\n";
542 : }
543 : #endif
544 9766 : if (isBent && hasTLS && !forceStraight) {
545 : // redo but force straight computation
546 193 : setPriorityJunctionPriorities(n, true);
547 : } else {
548 : n.markBentPriority(isBent);
549 : }
550 : return;
551 : }
552 :
553 : // ok, what we want to do in this case is to determine which incoming
554 : // has the best continuation...
555 : // This means, when several incoming roads have the same priority,
556 : // we want a (any) straight connection to be more priorised than a turning
557 : double bestAngle = -1;
558 : NBEdge* bestFirst = nullptr;
559 : NBEdge* bestSecond = nullptr;
560 51520 : for (i = bestIncoming.begin(); i != bestIncoming.end(); ++i) {
561 : EdgeVector::iterator j;
562 37162 : NBEdge* t1 = *i;
563 37162 : double angle1 = t1->getAngleAtNode(&n) + 180;
564 37162 : if (angle1 >= 360) {
565 0 : angle1 -= 360;
566 : }
567 71876 : for (j = i + 1; j != bestIncoming.end(); ++j) {
568 34714 : NBEdge* t2 = *j;
569 34714 : double angle2 = t2->getAngleAtNode(&n) + 180;
570 34714 : if (angle2 >= 360) {
571 0 : angle2 -= 360;
572 : }
573 34714 : double score = forceStraight ? getScore(t1, t2, minPrio, maxPrio, maxNumLanes, maxSpeed) : 0;
574 34714 : double angle = GeomHelper::getMinAngleDiff(angle1, angle2) + 45 * score;
575 34714 : if (angle > bestAngle) {
576 : //if (forceStraight) std::cout << " node=" << n.getID() << " t1=" << t1->getID() << " t2=" << t2->getID() << " angle=" << angle << " bestAngle=" << bestAngle << " score=" << score << " minPrio=" << minPrio << " maxPrio=" << maxPrio << "\n";
577 : bestAngle = MAX2(angle, bestAngle);
578 19982 : bestFirst = *i;
579 19982 : bestSecond = *j;
580 : }
581 : }
582 : }
583 14358 : bestFirst->setJunctionPriority(&n, NBEdge::PRIORITY_ROAD);
584 14358 : sort(bestOutgoing.begin(), bestOutgoing.end(), NBContHelper::edge_similar_direction_sorter(bestFirst));
585 : #ifdef DEBUG_SETPRIORITIES
586 : if (DEBUGCOND) {
587 : std::cout << " bestFirst=" << bestFirst->getID() << " bestOutgoingFirst=" << toString(bestOutgoing) << "\n";
588 : }
589 : #endif
590 14358 : if (bestOutgoing.size() != 0) {
591 14358 : extractAndMarkFirst(n, bestOutgoing);
592 : }
593 14358 : bestSecond->setJunctionPriority(&n, NBEdge::PRIORITY_ROAD);
594 14358 : sort(bestOutgoing.begin(), bestOutgoing.end(), NBContHelper::edge_similar_direction_sorter(bestSecond));
595 : #ifdef DEBUG_SETPRIORITIES
596 : if (DEBUGCOND) {
597 : std::cout << " bestSecond=" << bestSecond->getID() << " bestOutgoingSecond=" << toString(bestOutgoing) << "\n";
598 : }
599 : #endif
600 14358 : if (bestOutgoing.size() != 0) {
601 12945 : extractAndMarkFirst(n, bestOutgoing);
602 : }
603 14358 : const bool isBent = GeomHelper::getMinAngleDiff(bestFirst->getAngleAtNode(&n), bestSecond->getAngleAtNode(&n)) < 135;
604 14358 : if (isBent && hasTLS && !forceStraight) {
605 : // redo but force straight computation
606 201 : setPriorityJunctionPriorities(n, true);
607 : } else {
608 : n.markBentPriority(isBent);
609 14157 : markBestParallel(n, bestFirst, bestSecond);
610 : }
611 24124 : }
612 :
613 : double
614 1610 : NBEdgePriorityComputer::getScore(const NBEdge* e1, const NBEdge* e2, int minPrio, int maxPrio, int maxNumLanes, double maxSpeed) {
615 : // normalize priorities to [0.1,1]
616 : double normPrio1 = 1;
617 : double normPrio2 = 1;
618 1610 : if (minPrio != maxPrio) {
619 967 : normPrio1 = ((e1->getPriority() - minPrio) / (maxPrio - minPrio)) * 0.9 + 0.1;
620 967 : normPrio2 = ((e2->getPriority() - minPrio) / (maxPrio - minPrio)) * 0.9 + 0.1;
621 : }
622 : return (normPrio1
623 1610 : * e1->getNumLanes() / maxNumLanes
624 1610 : * e1->getSpeed() / maxSpeed
625 1610 : * normPrio2
626 1610 : * e2->getNumLanes() / maxNumLanes
627 1610 : * e2->getSpeed() / maxSpeed);
628 : }
629 :
630 : void
631 23923 : NBEdgePriorityComputer::markBestParallel(const NBNode& n, NBEdge* bestFirst, NBEdge* bestSecond) {
632 : // edges running parallel to the main direction should also be prioritised
633 23923 : const double a1 = bestFirst->getAngleAtNode(&n);
634 23923 : const double a2 = bestSecond == nullptr ? a1 : bestSecond->getAngleAtNode(&n);
635 23923 : SVCPermissions p1 = bestFirst->getPermissions();
636 23923 : SVCPermissions p2 = bestSecond == nullptr ? p1 : bestSecond->getPermissions();
637 83913 : for (NBEdge* e : n.getIncomingEdges()) {
638 : // @note: this rule might also apply if there are common permissions but
639 : // then we would not further rules to resolve the priority between the best edge and its parallel edge
640 59990 : SVCPermissions perm = e->getPermissions();
641 59990 : if (((GeomHelper::getMinAngleDiff(e->getAngleAtNode(&n), a1) < 10
642 35278 : || GeomHelper::getMinAngleDiff(e->getAngleAtNode(&n), a2) < 10))
643 74219 : && (p1 & perm) == 0 && (p2 & perm) == 0) {
644 348 : e->setJunctionPriority(&n, NBEdge::PRIORITY_ROAD);
645 : }
646 : }
647 23923 : }
648 :
649 :
650 : NBEdge*
651 46835 : NBEdgePriorityComputer::extractAndMarkFirst(NBNode& n, std::vector<NBEdge*>& s, int prio) {
652 46835 : if (s.size() == 0) {
653 : return nullptr;
654 : }
655 46835 : NBEdge* ret = s.front();
656 : s.erase(s.begin());
657 46835 : ret->setJunctionPriority(&n, prio);
658 46835 : return ret;
659 : }
660 :
661 :
662 : bool
663 113142 : NBEdgePriorityComputer::samePriority(const NBEdge* const e1, const NBEdge* const e2) {
664 113142 : if (e1 == e2) {
665 : return true;
666 : }
667 65682 : if (e1->getPriority() != e2->getPriority()) {
668 : return false;
669 : }
670 53285 : if ((int) e1->getSpeed() != (int) e2->getSpeed()) {
671 : return false;
672 : }
673 49825 : return (int) e1->getNumLanes() == (int) e2->getNumLanes();
674 : }
675 :
676 :
677 : bool
678 674 : NBEdgePriorityComputer::hasDifferentPriorities(const EdgeVector& edges, const NBEdge* excluded) {
679 674 : if (edges.size() < 2) {
680 : return false;
681 : }
682 674 : int prio = edges[0] == excluded ? edges[1]->getPriority() : edges[0]->getPriority();
683 2166 : for (auto e : edges) {
684 1566 : if (e != excluded && e->getPriority() != prio) {
685 : return true;
686 : }
687 : }
688 : return false;
689 : }
690 :
691 :
692 170793 : NBNodesEdgesSorter::crossing_by_junction_angle_sorter::crossing_by_junction_angle_sorter(const NBNode* node, const EdgeVector& ordering) {
693 : // reorder based on getAngleAtNodeToCenter
694 170793 : myOrdering = ordering;
695 170793 : sort(myOrdering.begin(), myOrdering.end(), NBContHelper::edge_by_angle_to_nodeShapeCentroid_sorter(node));
696 : // let the first edge remain the first
697 170793 : rotate(myOrdering.begin(), std::find(myOrdering.begin(), myOrdering.end(), ordering.front()), myOrdering.end());
698 170793 : }
699 :
700 :
701 : /****************************************************************************/
|
