Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2024 German Aerospace Center (DLR) and others.
4 : // This program and the accompanying materials are made available under the
5 : // terms of the Eclipse Public License 2.0 which is available at
6 : // https://www.eclipse.org/legal/epl-2.0/
7 : // This Source Code may also be made available under the following Secondary
8 : // Licenses when the conditions for such availability set forth in the Eclipse
9 : // Public License 2.0 are satisfied: GNU General Public License, version 2
10 : // or later which is available at
11 : // https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
12 : // SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
13 : /****************************************************************************/
14 : /// @file NBNode.cpp
15 : /// @author Daniel Krajzewicz
16 : /// @author Jakob Erdmann
17 : /// @author Sascha Krieg
18 : /// @author Michael Behrisch
19 : /// @date Tue, 20 Nov 2001
20 : ///
21 : // The representation of a single node
22 : /****************************************************************************/
23 : #include <config.h>
24 :
25 : #include <string>
26 : #include <map>
27 : #include <cassert>
28 : #include <algorithm>
29 : #include <vector>
30 : #include <deque>
31 : #include <set>
32 : #include <cmath>
33 : #include <iterator>
34 : #include <utils/common/UtilExceptions.h>
35 : #include <utils/common/StringUtils.h>
36 : #include <utils/options/OptionsCont.h>
37 : #include <utils/geom/GeomHelper.h>
38 : #include <utils/common/MsgHandler.h>
39 : #include <utils/common/StdDefs.h>
40 : #include <utils/common/ToString.h>
41 : #include <utils/geom/GeoConvHelper.h>
42 : #include <utils/iodevices/OutputDevice.h>
43 : #include <iomanip>
44 : #include "NBNode.h"
45 : #include "NBAlgorithms.h"
46 : #include "NBNodeCont.h"
47 : #include "NBNodeShapeComputer.h"
48 : #include "NBEdgeCont.h"
49 : #include "NBTypeCont.h"
50 : #include "NBHelpers.h"
51 : #include "NBDistrict.h"
52 : #include "NBContHelper.h"
53 : #include "NBRequest.h"
54 : #include "NBOwnTLDef.h"
55 : #include "NBLoadedSUMOTLDef.h"
56 : #include "NBTrafficLightLogicCont.h"
57 : #include "NBTrafficLightDefinition.h"
58 :
59 : // allow to extend a crossing across multiple edges
60 : #define EXTEND_CROSSING_ANGLE_THRESHOLD 35.0 // degrees
61 : // create intermediate walking areas if either of the following thresholds is exceeded
62 : #define SPLIT_CROSSING_WIDTH_THRESHOLD 1.5 // meters
63 : #define SPLIT_CROSSING_ANGLE_THRESHOLD 5 // degrees
64 :
65 : // minimum length for a weaving section at a combined on-off ramp
66 : #define MIN_WEAVE_LENGTH 20.0
67 :
68 : //#define DEBUG_CONNECTION_GUESSING
69 : //#define DEBUG_SMOOTH_GEOM
70 : //#define DEBUG_PED_STRUCTURES
71 : //#define DEBUG_EDGE_SORTING
72 : //#define DEBUG_CROSSING_OUTLINE
73 : //#define DEBUGCOND true
74 : #define DEBUG_NODE_ID "C"
75 : #define DEBUGCOND (getID() == DEBUG_NODE_ID)
76 : #define DEBUGCOND2(obj) ((obj != 0 && (obj)->getID() == DEBUG_NODE_ID))
77 : #ifdef DEBUG_PED_STRUCTURES
78 : #define DEBUGCOUT(cond, msg) DEBUGOUT(cond, msg)
79 : #else
80 : #define DEBUGCOUT(cond, msg)
81 : #endif
82 :
83 : // ===========================================================================
84 : // static members
85 : // ===========================================================================
86 : const int NBNode::FORWARD(1);
87 : const int NBNode::BACKWARD(-1);
88 : const double NBNode::UNSPECIFIED_RADIUS = -1;
89 : const int NBNode::AVOID_WIDE_LEFT_TURN(1);
90 : const int NBNode::AVOID_WIDE_RIGHT_TURN(2);
91 : const int NBNode::FOUR_CONTROL_POINTS(4);
92 : const int NBNode::AVOID_INTERSECTING_LEFT_TURNS(8);
93 : const int NBNode::SCURVE_IGNORE(16);
94 : const int NBNode::INDIRECT_LEFT(32);
95 :
96 : // ===========================================================================
97 : // method definitions
98 : // ===========================================================================
99 : /* -------------------------------------------------------------------------
100 : * NBNode::ApproachingDivider-methods
101 : * ----------------------------------------------------------------------- */
102 62266 : NBNode::ApproachingDivider::ApproachingDivider(
103 62266 : const EdgeVector& approaching, NBEdge* currentOutgoing) :
104 62266 : myApproaching(approaching),
105 62266 : myCurrentOutgoing(currentOutgoing),
106 62266 : myNumStraight(0),
107 62266 : myIsBikeEdge(currentOutgoing->getPermissions() == SVC_BICYCLE) {
108 : // collect lanes which are expliclity targeted
109 : std::set<int> approachedLanes;
110 183482 : for (const NBEdge* const approachingEdge : myApproaching) {
111 445403 : for (const NBEdge::Connection& con : approachingEdge->getConnections()) {
112 324187 : if (con.toEdge == myCurrentOutgoing) {
113 136277 : approachedLanes.insert(con.toLane);
114 : }
115 : }
116 121216 : myDirections.push_back(approachingEdge->getToNode()->getDirection(approachingEdge, currentOutgoing));
117 121216 : if (myDirections.back() == LinkDirection::STRAIGHT) {
118 50648 : myNumStraight++;
119 : }
120 : }
121 : // compute the indices of lanes that should be targeted (excluding pedestrian
122 : // lanes that will be connected from walkingAreas and forbidden lanes)
123 : // if the lane is targeted by an explicitly set connection we need
124 : // to make it available anyway
125 143863 : for (int i = 0; i < currentOutgoing->getNumLanes(); ++i) {
126 81597 : if ((currentOutgoing->getPermissions(i) == SVC_PEDESTRIAN
127 : // don't consider bicycle lanes as targets unless the target
128 : // edge is exclusively for bicycles
129 77115 : || (currentOutgoing->getPermissions(i) == SVC_BICYCLE && !myIsBikeEdge)
130 76571 : || isForbidden(currentOutgoing->getPermissions(i)))
131 81597 : && approachedLanes.count(i) == 0) {
132 3808 : continue;
133 : }
134 77789 : myAvailableLanes.push_back(i);
135 : }
136 62266 : }
137 :
138 :
139 62266 : NBNode::ApproachingDivider::~ApproachingDivider() {}
140 :
141 :
142 : void
143 128452 : NBNode::ApproachingDivider::execute(const int src, const int dest) {
144 : assert((int)myApproaching.size() > src);
145 : // get the origin edge
146 128452 : NBEdge* incomingEdge = myApproaching[src];
147 128452 : if (incomingEdge->getStep() == NBEdge::EdgeBuildingStep::LANES2LANES_DONE || incomingEdge->getStep() == NBEdge::EdgeBuildingStep::LANES2LANES_USER) {
148 39501 : return;
149 : }
150 89069 : if (myAvailableLanes.size() == 0) {
151 : return;
152 : }
153 89576 : std::vector<int> approachingLanes = incomingEdge->getConnectionLanes(myCurrentOutgoing, myIsBikeEdge || incomingEdge->getPermissions() == SVC_BICYCLE);
154 88995 : if (approachingLanes.size() == 0) {
155 : return;
156 : }
157 : #ifdef DEBUG_CONNECTION_GUESSING
158 : if (DEBUGCOND2(incomingEdge->getToNode())) {
159 : std::cout << "Bre:ex src=" << src << " dest=" << dest << " in=" << incomingEdge->getID() << " apLanes=" << toString(approachingLanes) << "\n";
160 : }
161 :
162 : #endif
163 88951 : int numConnections = (int)approachingLanes.size();
164 : double factor = 1;
165 : const bool rightOnRed = incomingEdge->getToNode()->getType() == SumoXMLNodeType::TRAFFIC_LIGHT_RIGHT_ON_RED;
166 88951 : if (myNumStraight == 1 && myDirections[src] == LinkDirection::STRAIGHT && (
167 : // we do not want to destroy ramp-like assignments where the
168 : // on-connection-per-lane rule avoids conflicts
169 : // - at a traffic light the phases are seperated so there is no conflict anyway
170 3694 : (incomingEdge->getToNode()->isTLControlled() && !rightOnRed)
171 : // - there are no incoming edges to the right
172 31445 : || src == 0
173 : // - a minor straight road is likely in conflict anyway
174 16151 : || (incomingEdge->getJunctionPriority(incomingEdge->getToNode()) == NBEdge::MINOR_ROAD && !rightOnRed))) {
175 26108 : numConnections = (int)myAvailableLanes.size();
176 26108 : factor = (double)approachingLanes.size() / (double)numConnections;
177 26108 : if (factor > 0.5) {
178 : factor = 1;
179 : }
180 : }
181 88951 : std::deque<int>* approachedLanes = spread(numConnections, dest);
182 : assert(approachedLanes->size() <= myAvailableLanes.size());
183 : // set lanes
184 88951 : const int maxFrom = (int)approachingLanes.size() - 1;
185 190716 : for (int i = 0; i < (int)approachedLanes->size(); i++) {
186 : // distribute i evenly on approaching lanes in case we are building more
187 : // connections than there are lanes
188 101765 : int fromLane = approachingLanes[MIN2((int)(i * factor), maxFrom)];
189 101765 : int approached = myAvailableLanes[(*approachedLanes)[i]];
190 203530 : incomingEdge->setConnection(fromLane, myCurrentOutgoing, approached, NBEdge::Lane2LaneInfoType::COMPUTED);
191 : }
192 88951 : delete approachedLanes;
193 88995 : }
194 :
195 :
196 : std::deque<int>*
197 88951 : NBNode::ApproachingDivider::spread(int numLanes, int dest) const {
198 88951 : std::deque<int>* ret = new std::deque<int>();
199 : // when only one lane is approached, we check, whether the double-value
200 : // is assigned more to the left or right lane
201 88951 : if (numLanes == 1) {
202 : ret->push_back(dest);
203 79763 : return ret;
204 : }
205 :
206 9188 : const int numOutgoingLanes = (int)myAvailableLanes.size();
207 : //
208 : ret->push_back(dest);
209 : int noSet = 1;
210 : int roffset = 1;
211 : int loffset = 1;
212 12872 : while (noSet < numLanes) {
213 : // It may be possible, that there are not enough lanes the source
214 : // lanes may be divided on
215 : // In this case, they remain unset
216 : // !!! this is only a hack. It is possible, that this yields in
217 : // uncommon divisions
218 9555 : if (numOutgoingLanes == noSet) {
219 : return ret;
220 : }
221 :
222 : // as due to the conversion of double->uint the numbers will be lower
223 : // than they should be, we try to append to the left side first
224 : //
225 : // check whether the left boundary of the approached street has
226 : // been overridden; if so, move all lanes to the right
227 9552 : if (dest + loffset >= numOutgoingLanes) {
228 4799 : loffset -= 1;
229 4799 : roffset += 1;
230 9940 : for (int i = 0; i < (int)ret->size(); i++) {
231 5141 : (*ret)[i] = (*ret)[i] - 1;
232 : }
233 : }
234 : // append the next lane to the left of all edges
235 : // increase the position (destination edge)
236 9552 : ret->push_back(dest + loffset);
237 9552 : noSet++;
238 9552 : loffset += 1;
239 :
240 : // as above
241 9552 : if (numOutgoingLanes == noSet) {
242 : return ret;
243 : }
244 :
245 : // now we try to append the next lane to the right side, when needed
246 3684 : if (noSet < numLanes) {
247 : // check whether the right boundary of the approached street has
248 : // been overridden; if so, move all lanes to the right
249 3262 : if (dest < roffset) {
250 764 : loffset += 1;
251 764 : roffset -= 1;
252 2344 : for (int i = 0; i < (int)ret->size(); i++) {
253 1580 : (*ret)[i] = (*ret)[i] + 1;
254 : }
255 : }
256 3262 : ret->push_front(dest - roffset);
257 3262 : noSet++;
258 3262 : roffset += 1;
259 : }
260 : }
261 : return ret;
262 : }
263 :
264 :
265 : /* -------------------------------------------------------------------------
266 : * NBNode::Crossing-methods
267 : * ----------------------------------------------------------------------- */
268 2012 : NBNode::Crossing::Crossing(const NBNode* _node, const EdgeVector& _edges, double _width, bool _priority, int _customTLIndex, int _customTLIndex2, const PositionVector& _customShape) :
269 : Parameterised(),
270 2012 : node(_node),
271 2012 : edges(_edges),
272 2012 : customWidth(_width),
273 2012 : width(_width),
274 2012 : priority(_priority),
275 : customShape(_customShape),
276 2012 : tlLinkIndex(_customTLIndex),
277 2012 : tlLinkIndex2(_customTLIndex2),
278 2012 : customTLIndex(_customTLIndex),
279 2012 : customTLIndex2(_customTLIndex2),
280 2012 : valid(true) {
281 2012 : }
282 :
283 :
284 : /* -------------------------------------------------------------------------
285 : * NBNode-methods
286 : * ----------------------------------------------------------------------- */
287 30088 : NBNode::NBNode(const std::string& id, const Position& position,
288 30088 : SumoXMLNodeType type) :
289 30088 : Named(StringUtils::convertUmlaute(id)),
290 30088 : myPosition(position),
291 30088 : myType(type),
292 30088 : myDistrict(nullptr),
293 30088 : myHaveCustomPoly(false),
294 30088 : myRequest(nullptr),
295 30088 : myRadius(UNSPECIFIED_RADIUS),
296 30088 : myKeepClear(OptionsCont::getOptions().getBool("default.junctions.keep-clear")),
297 30089 : myRightOfWay(SUMOXMLDefinitions::RightOfWayValues.get(OptionsCont::getOptions().getString("default.right-of-way"))),
298 30088 : myFringeType(FringeType::DEFAULT),
299 30088 : myDiscardAllCrossings(false),
300 30088 : myCrossingsLoadedFromSumoNet(0),
301 30088 : myDisplacementError(0),
302 30088 : myIsBentPriority(false),
303 30088 : myTypeWasGuessed(false) {
304 30088 : if (!SUMOXMLDefinitions::isValidNetID(myID)) {
305 3 : throw ProcessError(TLF("Invalid node id '%'.", myID));
306 : }
307 30096 : }
308 :
309 :
310 32778 : NBNode::NBNode(const std::string& id, const Position& position, NBDistrict* district) :
311 32778 : Named(StringUtils::convertUmlaute(id)),
312 32778 : myPosition(position),
313 32778 : myType(district == nullptr ? SumoXMLNodeType::UNKNOWN : SumoXMLNodeType::DISTRICT),
314 32778 : myDistrict(district),
315 32778 : myHaveCustomPoly(false),
316 32778 : myRequest(nullptr),
317 32778 : myRadius(UNSPECIFIED_RADIUS),
318 32778 : myKeepClear(OptionsCont::getOptions().getBool("default.junctions.keep-clear")),
319 32778 : myRightOfWay(SUMOXMLDefinitions::RightOfWayValues.get(OptionsCont::getOptions().getString("default.right-of-way"))),
320 32778 : myFringeType(FringeType::DEFAULT),
321 32778 : myDiscardAllCrossings(false),
322 32778 : myCrossingsLoadedFromSumoNet(0),
323 32778 : myDisplacementError(0),
324 32778 : myIsBentPriority(false),
325 32778 : myTypeWasGuessed(false) {
326 32778 : if (!SUMOXMLDefinitions::isValidNetID(myID)) {
327 0 : throw ProcessError(TLF("Invalid node id '%'.", myID));
328 : }
329 32778 : }
330 :
331 :
332 125730 : NBNode::~NBNode() {
333 62865 : delete myRequest;
334 251460 : }
335 :
336 :
337 : void
338 4733 : NBNode::reinit(const Position& position, SumoXMLNodeType type,
339 : bool updateEdgeGeometries) {
340 4733 : myPosition = position;
341 : // patch type
342 4733 : myType = type;
343 4733 : if (!isTrafficLight(myType)) {
344 4492 : removeTrafficLights();
345 : }
346 4733 : if (updateEdgeGeometries) {
347 2885 : for (EdgeVector::iterator i = myIncomingEdges.begin(); i != myIncomingEdges.end(); i++) {
348 1677 : PositionVector geom = (*i)->getGeometry();
349 1677 : geom[-1] = myPosition;
350 1677 : (*i)->setGeometry(geom);
351 1677 : }
352 2887 : for (EdgeVector::iterator i = myOutgoingEdges.begin(); i != myOutgoingEdges.end(); i++) {
353 1679 : PositionVector geom = (*i)->getGeometry();
354 1679 : geom[0] = myPosition;
355 1679 : (*i)->setGeometry(geom);
356 1679 : }
357 : }
358 4733 : }
359 :
360 :
361 :
362 : // ----------- Applying offset
363 : void
364 37249 : NBNode::reshiftPosition(double xoff, double yoff) {
365 : myPosition.add(xoff, yoff, 0);
366 37249 : myPoly.add(xoff, yoff, 0);
367 37256 : for (auto& wacs : myWalkingAreaCustomShapes) {
368 7 : wacs.shape.add(xoff, yoff, 0);
369 : }
370 37534 : for (auto& c : myCrossings) {
371 285 : c->customShape.add(xoff, yoff, 0);
372 : }
373 37249 : }
374 :
375 :
376 : void
377 842 : NBNode::mirrorX() {
378 : myPosition.mul(1, -1);
379 842 : myPoly.mirrorX();
380 : // mirror pre-computed geometry of crossings and walkingareas
381 874 : for (auto& c : myCrossings) {
382 32 : c->customShape.mirrorX();
383 32 : c->shape.mirrorX();
384 : }
385 874 : for (auto& wa : myWalkingAreas) {
386 32 : wa.shape.mirrorX();
387 : }
388 844 : for (auto& wacs : myWalkingAreaCustomShapes) {
389 2 : wacs.shape.mirrorX();
390 : }
391 842 : }
392 :
393 :
394 : // ----------- Methods for dealing with assigned traffic lights
395 : void
396 18291 : NBNode::addTrafficLight(NBTrafficLightDefinition* tlDef) {
397 : myTrafficLights.insert(tlDef);
398 : // rail signals receive a temporary traffic light in order to set connection tl-linkIndex
399 18291 : if (!isTrafficLight(myType) && myType != SumoXMLNodeType::RAIL_SIGNAL && myType != SumoXMLNodeType::RAIL_CROSSING) {
400 2670 : myType = SumoXMLNodeType::TRAFFIC_LIGHT;
401 : }
402 18291 : }
403 :
404 :
405 : void
406 4576 : NBNode::removeTrafficLight(NBTrafficLightDefinition* tlDef) {
407 4576 : tlDef->removeNode(this);
408 : myTrafficLights.erase(tlDef);
409 4576 : }
410 :
411 :
412 : void
413 16363 : NBNode::removeTrafficLights(bool setAsPriority) {
414 : std::set<NBTrafficLightDefinition*> trafficLights = myTrafficLights; // make a copy because we will modify the original
415 17323 : for (std::set<NBTrafficLightDefinition*>::const_iterator i = trafficLights.begin(); i != trafficLights.end(); ++i) {
416 960 : removeTrafficLight(*i);
417 : }
418 16363 : if (setAsPriority) {
419 24 : myType = myRequest != nullptr ? SumoXMLNodeType::PRIORITY : (
420 3 : myType == SumoXMLNodeType::TRAFFIC_LIGHT_NOJUNCTION ? SumoXMLNodeType::NOJUNCTION : SumoXMLNodeType::DEAD_END);
421 : }
422 16363 : }
423 :
424 :
425 : void
426 1468 : NBNode::invalidateTLS(NBTrafficLightLogicCont& tlCont, bool removedConnections, bool addedConnections) {
427 1468 : if (isTLControlled()) {
428 : std::set<NBTrafficLightDefinition*> oldDefs(myTrafficLights);
429 1266 : for (std::set<NBTrafficLightDefinition*>::iterator it = oldDefs.begin(); it != oldDefs.end(); ++it) {
430 633 : NBTrafficLightDefinition* orig = *it;
431 633 : if (dynamic_cast<NBLoadedSUMOTLDef*>(orig) != nullptr) {
432 12 : dynamic_cast<NBLoadedSUMOTLDef*>(orig)->registerModifications(removedConnections, addedConnections);
433 621 : } else if (dynamic_cast<NBOwnTLDef*>(orig) == nullptr) {
434 0 : NBTrafficLightDefinition* newDef = new NBOwnTLDef(orig->getID(), orig->getOffset(), orig->getType());
435 : const std::vector<NBNode*>& nodes = orig->getNodes();
436 0 : while (!nodes.empty()) {
437 0 : newDef->addNode(nodes.front());
438 0 : nodes.front()->removeTrafficLight(orig);
439 : }
440 0 : tlCont.removeFully(orig->getID());
441 0 : tlCont.insert(newDef);
442 : }
443 : }
444 : }
445 1468 : }
446 :
447 :
448 : void
449 7988 : NBNode::shiftTLConnectionLaneIndex(NBEdge* edge, int offset, int threshold) {
450 9721 : for (std::set<NBTrafficLightDefinition*>::iterator it = myTrafficLights.begin(); it != myTrafficLights.end(); ++it) {
451 1733 : (*it)->shiftTLConnectionLaneIndex(edge, offset, threshold);
452 : }
453 7988 : }
454 :
455 : // ----------- Prunning the input
456 : int
457 61249 : NBNode::removeSelfLoops(NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tc) {
458 : int ret = 0;
459 : int pos = 0;
460 : EdgeVector::const_iterator j = myIncomingEdges.begin();
461 159486 : while (j != myIncomingEdges.end()) {
462 : // skip edges which are only incoming and not outgoing
463 98237 : if (find(myOutgoingEdges.begin(), myOutgoingEdges.end(), *j) == myOutgoingEdges.end()) {
464 : ++j;
465 98237 : ++pos;
466 98237 : continue;
467 : }
468 : // an edge with both its origin and destination being the current
469 : // node should be removed
470 0 : NBEdge* dummy = *j;
471 0 : WRITE_WARNINGF(TL(" Removing self-looping edge '%'"), dummy->getID());
472 : // get the list of incoming edges connected to the self-loop
473 0 : EdgeVector incomingConnected = dummy->getIncomingEdges();
474 : // get the list of outgoing edges connected to the self-loop
475 0 : EdgeVector outgoingConnected = dummy->getConnectedEdges();
476 : // let the self-loop remap its connections
477 0 : dummy->remapConnections(incomingConnected);
478 0 : remapRemoved(tc, dummy, incomingConnected, outgoingConnected);
479 : // delete the self-loop
480 0 : ec.erase(dc, dummy);
481 : j = myIncomingEdges.begin() + pos;
482 0 : ++ret;
483 0 : }
484 61249 : return ret;
485 : }
486 :
487 :
488 : // -----------
489 : void
490 112594 : NBNode::addIncomingEdge(NBEdge* edge) {
491 : assert(edge != 0);
492 112594 : if (find(myIncomingEdges.begin(), myIncomingEdges.end(), edge) == myIncomingEdges.end()) {
493 110729 : myIncomingEdges.push_back(edge);
494 110729 : myAllEdges.push_back(edge);
495 : }
496 112594 : }
497 :
498 :
499 : void
500 112761 : NBNode::addOutgoingEdge(NBEdge* edge) {
501 : assert(edge != 0);
502 112761 : if (find(myOutgoingEdges.begin(), myOutgoingEdges.end(), edge) == myOutgoingEdges.end()) {
503 110895 : myOutgoingEdges.push_back(edge);
504 110895 : myAllEdges.push_back(edge);
505 : }
506 112761 : }
507 :
508 :
509 : bool
510 66784 : NBNode::isSimpleContinuation(bool checkLaneNumbers, bool checkWidth) const {
511 : // one in, one out->continuation
512 66784 : if (myIncomingEdges.size() == 1 && myOutgoingEdges.size() == 1) {
513 10195 : NBEdge* in = myIncomingEdges.front();
514 10195 : NBEdge* out = myOutgoingEdges.front();
515 : // both must have the same number of lanes
516 10187 : return ((!checkLaneNumbers || in->getNumLanes() == out->getNumLanes())
517 18803 : && (!checkWidth || in->getTotalWidth() == out->getTotalWidth()));
518 : }
519 : // two in and two out and both in reverse direction
520 56589 : if (myIncomingEdges.size() == 2 && myOutgoingEdges.size() == 2) {
521 28828 : for (EdgeVector::const_iterator i = myIncomingEdges.begin(); i != myIncomingEdges.end(); i++) {
522 22439 : NBEdge* in = *i;
523 22439 : EdgeVector::const_iterator opposite = find_if(myOutgoingEdges.begin(), myOutgoingEdges.end(), NBContHelper::opposite_finder(in));
524 : // must have an opposite edge
525 22439 : if (opposite == myOutgoingEdges.end()) {
526 8091 : return false;
527 : }
528 : // both must have the same number of lanes
529 16058 : NBContHelper::nextCW(myOutgoingEdges, opposite);
530 16058 : if (checkLaneNumbers && in->getNumLanes() != (*opposite)->getNumLanes()) {
531 : return false;
532 : }
533 14579 : if (checkWidth && in->getTotalWidth() != (*opposite)->getTotalWidth()) {
534 : return false;
535 : }
536 : }
537 : return true;
538 : }
539 : // nope
540 : return false;
541 : }
542 :
543 :
544 : PositionVector
545 262358 : NBNode::computeSmoothShape(const PositionVector& begShape,
546 : const PositionVector& endShape,
547 : int numPoints,
548 : bool isTurnaround,
549 : double extrapolateBeg,
550 : double extrapolateEnd,
551 : NBNode* recordError,
552 : int shapeFlag) const {
553 :
554 262358 : bool ok = true;
555 262358 : if ((shapeFlag & INDIRECT_LEFT) != 0) {
556 32 : return indirectLeftShape(begShape, endShape, numPoints);
557 : }
558 262326 : PositionVector init = bezierControlPoints(begShape, endShape, isTurnaround, extrapolateBeg, extrapolateEnd, ok, recordError, DEG2RAD(5), shapeFlag);
559 : #ifdef DEBUG_SMOOTH_GEOM
560 : if (DEBUGCOND) {
561 : std::cout << "computeSmoothShape node " << getID() << " begShape=" << begShape << " endShape=" << endShape << " init=" << init << " shapeFlag=" << shapeFlag << "\n";
562 : }
563 : #endif
564 262326 : if (init.size() == 0) {
565 80734 : PositionVector ret;
566 80734 : ret.push_back(begShape.back());
567 80734 : ret.push_back(endShape.front());
568 : return ret;
569 80734 : } else {
570 181592 : return init.bezier(numPoints).smoothedZFront();
571 : }
572 262326 : }
573 :
574 : PositionVector
575 264342 : NBNode::bezierControlPoints(
576 : const PositionVector& begShape,
577 : const PositionVector& endShape,
578 : bool isTurnaround,
579 : double extrapolateBeg,
580 : double extrapolateEnd,
581 : bool& ok,
582 : NBNode* recordError,
583 : double straightThresh,
584 : int shapeFlag) {
585 :
586 264342 : const Position beg = begShape.back();
587 264342 : const Position end = endShape.front();
588 : const double dist = beg.distanceTo2D(end);
589 264342 : PositionVector init;
590 264342 : if (dist < POSITION_EPS || beg.distanceTo2D(begShape[-2]) < POSITION_EPS || end.distanceTo2D(endShape[1]) < POSITION_EPS) {
591 : #ifdef DEBUG_SMOOTH_GEOM
592 : if (DEBUGCOND2(recordError)) std::cout << " bezierControlPoints failed beg=" << beg << " end=" << end
593 : << " dist=" << dist
594 : << " distBegLast=" << beg.distanceTo2D(begShape[-2])
595 : << " distEndFirst=" << end.distanceTo2D(endShape[1])
596 : << "\n";
597 : #endif
598 : // typically, this node a is a simpleContinuation. see also #2539
599 : return init;
600 : } else {
601 255160 : init.push_back(beg);
602 255160 : if (isTurnaround) {
603 : // turnarounds:
604 : // - end of incoming lane
605 : // - position between incoming/outgoing end/begin shifted by the distance orthogonally
606 : // - begin of outgoing lane
607 22237 : Position center = PositionVector::positionAtOffset2D(beg, end, beg.distanceTo2D(end) / (double) 2.);
608 22237 : center.sub(beg.y() - end.y(), end.x() - beg.x());
609 22237 : init.push_back(center);
610 : } else {
611 : const double EXT = 100;
612 232923 : const double angle = GeomHelper::angleDiff(begShape.angleAt2D(-2), endShape.angleAt2D(0));
613 232923 : PositionVector endShapeBegLine(endShape[0], endShape[1]);
614 232923 : PositionVector begShapeEndLineRev(begShape[-1], begShape[-2]);
615 232923 : endShapeBegLine.extrapolate2D(EXT, true);
616 232923 : begShapeEndLineRev.extrapolate2D(EXT, true);
617 : #ifdef DEBUG_SMOOTH_GEOM
618 : if (DEBUGCOND2(recordError)) std::cout
619 : << " endShapeBegLine=" << endShapeBegLine
620 : << " begShapeEndLineRev=" << begShapeEndLineRev
621 : << " angle=" << RAD2DEG(angle) << "\n";
622 : #endif
623 232923 : if (fabs(angle) < M_PI / 4.) {
624 : // very low angle: could be an s-shape or a straight line
625 102792 : const double displacementAngle = GeomHelper::angleDiff(begShape.angleAt2D(-2), beg.angleTo2D(end));
626 102792 : const double bendDeg = RAD2DEG(fabs(displacementAngle - angle));
627 102792 : const double halfDistance = dist / 2;
628 102792 : if (fabs(displacementAngle) <= straightThresh && fabs(angle) <= straightThresh) {
629 : #ifdef DEBUG_SMOOTH_GEOM
630 : if (DEBUGCOND2(recordError)) std::cout << " bezierControlPoints identified straight line beg=" << beg << " end=" << end
631 : << " angle=" << RAD2DEG(angle) << " displacementAngle=" << RAD2DEG(displacementAngle) << "\n";
632 : #endif
633 69213 : return PositionVector();
634 33579 : } else if (bendDeg > 22.5 && pow(bendDeg / 45, 2) / dist > 0.13) {
635 : // do not allow s-curves with extreme bends
636 : // (a linear dependency is to restrictive at low displacementAngles and too permisive at high angles)
637 : #ifdef DEBUG_SMOOTH_GEOM
638 : if (DEBUGCOND2(recordError)) std::cout << " bezierControlPoints found extreme s-curve, falling back to straight line beg=" << beg << " end=" << end
639 : << " angle=" << RAD2DEG(angle) << " displacementAngle=" << RAD2DEG(displacementAngle)
640 : << " dist=" << dist << " bendDeg=" << bendDeg << " bd2=" << pow(bendDeg / 45, 2)
641 : << " displacementError=" << sin(displacementAngle) * dist
642 : << " begShape=" << begShape << " endShape=" << endShape << "\n";
643 : #endif
644 1318 : ok = false;
645 1318 : if (recordError != nullptr && (shapeFlag & SCURVE_IGNORE) == 0) {
646 845 : recordError->myDisplacementError = MAX2(recordError->myDisplacementError, (double)fabs(sin(displacementAngle) * dist));
647 : }
648 1318 : return PositionVector();
649 : } else {
650 32261 : const double endLength = begShape[-2].distanceTo2D(begShape[-1]);
651 32261 : const double off1 = endLength + MIN2(extrapolateBeg, halfDistance);
652 64522 : init.push_back(PositionVector::positionAtOffset2D(begShapeEndLineRev[1], begShapeEndLineRev[0], off1));
653 32261 : const double off2 = EXT - MIN2(extrapolateEnd, halfDistance);
654 64522 : init.push_back(PositionVector::positionAtOffset2D(endShapeBegLine[0], endShapeBegLine[1], off2));
655 : #ifdef DEBUG_SMOOTH_GEOM
656 : if (DEBUGCOND2(recordError)) std::cout << " bezierControlPoints found s-curve beg=" << beg << " end=" << end
657 : << " angle=" << RAD2DEG(angle) << " displacementAngle=" << RAD2DEG(displacementAngle)
658 : << " halfDistance=" << halfDistance << "\n";
659 : #endif
660 : }
661 : } else {
662 : // turning
663 : // - end of incoming lane
664 : // - intersection of the extrapolated lanes
665 : // - begin of outgoing lane
666 : // attention: if there is no intersection, use a straight line
667 130131 : Position intersect = endShapeBegLine.intersectionPosition2D(begShapeEndLineRev);
668 : if (intersect == Position::INVALID) {
669 : #ifdef DEBUG_SMOOTH_GEOM
670 : if (DEBUGCOND2(recordError)) {
671 : std::cout << " bezierControlPoints failed beg=" << beg << " end=" << end << " intersect=" << intersect
672 : << " endShapeBegLine=" << endShapeBegLine
673 : << " begShapeEndLineRev=" << begShapeEndLineRev
674 : << "\n";
675 : }
676 : #endif
677 1474 : ok = false;
678 1474 : if (recordError != nullptr && (shapeFlag & SCURVE_IGNORE) == 0) {
679 : // it's unclear if this error can be solved via stretching the intersection.
680 488 : recordError->myDisplacementError = MAX2(recordError->myDisplacementError, (double)1.0);
681 : }
682 1474 : return PositionVector();
683 : }
684 128657 : const double begOffset = begShapeEndLineRev.nearest_offset_to_point2D(intersect);
685 128657 : const double endOffset = endShapeBegLine.nearest_offset_to_point2D(intersect);
686 : /*
687 : if ((shapeFlag & FOUR_CONTROL_POINTS) == 0 && (begOffset >= EXT || endOffset >= EXT)) {
688 : // intersection point lies within begShape / endShape so we cannot use it
689 : if (dist < 2) {
690 : return PositionVector();
691 : }
692 : shapeFlag |= FOUR_CONTROL_POINTS;
693 : extrapolateBeg = MIN2(10.0, dist / 2);
694 : extrapolateEnd = extrapolateBeg;
695 : }
696 : */
697 128657 : const double minControlLength = MIN2((double)1.0, dist / 2);
698 : const double distBeg = intersect.distanceTo2D(beg);
699 : const double distEnd = intersect.distanceTo2D(end);
700 128657 : const bool lengthenBeg = distBeg <= minControlLength;
701 128657 : const bool lengthenEnd = distEnd <= minControlLength;
702 : #ifdef DEBUG_SMOOTH_GEOM
703 : if (DEBUGCOND2(recordError)) std::cout
704 : << " beg=" << beg << " end=" << end << " intersect=" << intersect
705 : << " distBeg=" << distBeg << " distEnd=" << distEnd
706 : << " begOffset=" << begOffset << " endOffset=" << endOffset
707 : << " lEnd=" << lengthenEnd << " lBeg=" << lengthenBeg
708 : << "\n";
709 : #endif
710 128657 : if (lengthenBeg && lengthenEnd) {
711 : #ifdef DEBUG_SMOOTH_GEOM
712 : if (DEBUGCOND2(recordError)) {
713 : std::cout << " bezierControlPoints failed\n";
714 : }
715 : #endif
716 0 : if (recordError != nullptr && (shapeFlag & SCURVE_IGNORE) == 0) {
717 : // This should be fixable with minor stretching
718 0 : recordError->myDisplacementError = MAX2(recordError->myDisplacementError, (double)1.0);
719 : }
720 0 : ok = false;
721 0 : return PositionVector();
722 128657 : } else if ((shapeFlag & FOUR_CONTROL_POINTS)) {
723 48 : init.push_back(begShapeEndLineRev.positionAtOffset2D(EXT - extrapolateBeg));
724 96 : init.push_back(endShapeBegLine.positionAtOffset2D(EXT - extrapolateEnd));
725 128609 : } else if (lengthenBeg || lengthenEnd) {
726 369 : init.push_back(begShapeEndLineRev.positionAtOffset2D(EXT - minControlLength));
727 738 : init.push_back(endShapeBegLine.positionAtOffset2D(EXT - minControlLength));
728 128240 : } else if ((shapeFlag & AVOID_WIDE_LEFT_TURN) != 0
729 : // there are two reasons for enabling special geometry rules:
730 : // 1) sharp edge angles which could cause overshoot
731 : // 2) junction geometries with a large displacement between opposite left turns
732 : // which would cause the default geometry to overlap
733 95566 : && ((shapeFlag & AVOID_INTERSECTING_LEFT_TURNS) != 0
734 91093 : || (angle > DEG2RAD(95) && (distBeg > 20 || distEnd > 20)))) {
735 : //std::cout << " bezierControlPoints intersect=" << intersect << " dist=" << dist << " distBeg=" << distBeg << " distEnd=" << distEnd << " angle=" << RAD2DEG(angle) << " flag=" << shapeFlag << "\n";
736 5529 : const double factor = ((shapeFlag & AVOID_INTERSECTING_LEFT_TURNS) == 0 ? 1
737 4473 : : MIN2(0.6, 16 / dist));
738 9998 : init.push_back(begShapeEndLineRev.positionAtOffset2D(EXT - MIN2(distBeg * factor / 1.2, dist * factor / 1.8)));
739 9898 : init.push_back(endShapeBegLine.positionAtOffset2D(EXT - MIN2(distEnd * factor / 1.2, dist * factor / 1.8)));
740 128240 : } else if ((shapeFlag & AVOID_WIDE_RIGHT_TURN) != 0 && angle < DEG2RAD(-95) && (distBeg > 20 || distEnd > 20)) {
741 : //std::cout << " bezierControlPoints intersect=" << intersect << " distBeg=" << distBeg << " distEnd=" << distEnd << "\n";
742 0 : init.push_back(begShapeEndLineRev.positionAtOffset2D(EXT - MIN2(distBeg / 1.4, dist / 2)));
743 0 : init.push_back(endShapeBegLine.positionAtOffset2D(EXT - MIN2(distEnd / 1.4, dist / 2)));
744 : } else {
745 : double z;
746 122711 : const double z1 = begShapeEndLineRev.positionAtOffset2D(begOffset).z();
747 122711 : const double z2 = endShapeBegLine.positionAtOffset2D(endOffset).z();
748 122711 : const double z3 = 0.5 * (beg.z() + end.z());
749 : // if z1 and z2 are on the same side in regard to z3 then we
750 : // can use their avarage. Otherwise, the intersection in 3D
751 : // is not good and we are better of using z3
752 122711 : if ((z1 <= z3 && z2 <= z3) || (z1 >= z3 && z2 >= z3)) {
753 122659 : z = 0.5 * (z1 + z2);
754 : } else {
755 : z = z3;
756 : }
757 : intersect.set(intersect.x(), intersect.y(), z);
758 122711 : init.push_back(intersect);
759 : }
760 : }
761 232923 : }
762 183155 : init.push_back(end);
763 : }
764 : return init;
765 264342 : }
766 :
767 : PositionVector
768 32 : NBNode::indirectLeftShape(const PositionVector& begShape, const PositionVector& endShape, int numPoints) const {
769 : UNUSED_PARAMETER(numPoints);
770 32 : PositionVector result;
771 32 : result.push_back(begShape.back());
772 : //const double angle = GeomHelper::angleDiff(begShape.angleAt2D(-2), endShape.angleAt2D(0));
773 32 : PositionVector endShapeBegLine(endShape[0], endShape[1]);
774 32 : PositionVector begShapeEndLineRev(begShape[-1], begShape[-2]);
775 32 : endShapeBegLine.extrapolate2D(100, true);
776 32 : begShapeEndLineRev.extrapolate2D(100, true);
777 32 : Position intersect = endShapeBegLine.intersectionPosition2D(begShapeEndLineRev);
778 : if (intersect == Position::INVALID) {
779 0 : WRITE_WARNINGF(TL("Could not compute indirect left turn shape at node '%'"), getID());
780 : } else {
781 32 : Position dir = intersect;
782 32 : dir.sub(endShape[0]);
783 32 : dir.norm2D();
784 32 : const double radius = myRadius == NBNode::UNSPECIFIED_RADIUS ? OptionsCont::getOptions().getFloat("default.junctions.radius") : myRadius;
785 : dir.mul(radius);
786 32 : result.push_back(intersect + dir);
787 : }
788 32 : result.push_back(endShape.front());
789 32 : return result;
790 32 : }
791 :
792 : PositionVector
793 148741 : NBNode::computeInternalLaneShape(const NBEdge* fromE, const NBEdge::Connection& con, int numPoints, NBNode* recordError, int shapeFlag) const {
794 148741 : if (con.fromLane >= fromE->getNumLanes()) {
795 0 : throw ProcessError(TLF("Connection '%' starts at a non-existant lane.", con.getDescription(fromE)));
796 : }
797 148741 : if (con.toLane >= con.toEdge->getNumLanes()) {
798 0 : throw ProcessError(TLF("Connection '%' targets a non-existant lane.", con.getDescription(fromE)));
799 : }
800 148741 : PositionVector fromShape = fromE->getLaneShape(con.fromLane);
801 148741 : PositionVector toShape = con.toEdge->getLaneShape(con.toLane);
802 148741 : PositionVector ret;
803 148741 : bool useCustomShape = con.customShape.size() > 0;
804 148741 : if (useCustomShape) {
805 : // ensure that the shape starts and ends at the intersection boundary
806 145 : PositionVector startBorder = fromE->getNodeBorder(this);
807 145 : if (startBorder.size() == 0) {
808 208 : startBorder = fromShape.getOrthogonal(fromShape.back(), 1, true);
809 : }
810 145 : PositionVector tmp = NBEdge::startShapeAt(con.customShape, this, startBorder);
811 145 : if (tmp.size() < 2) {
812 0 : WRITE_WARNINGF(TL("Could not use custom shape for connection %."), con.getDescription(fromE));
813 : useCustomShape = false;
814 : } else {
815 145 : if (tmp.length2D() > con.customShape.length2D() + POSITION_EPS) {
816 : // shape was lengthened at the start, make sure it attaches at the center of the lane
817 80 : tmp[0] = fromShape.back();
818 65 : } else if (recordError != nullptr) {
819 16 : const double offset = tmp[0].distanceTo2D(fromShape.back());
820 16 : if (offset > fromE->getLaneWidth(con.fromLane) / 2) {
821 6 : WRITE_WARNINGF(TL("Custom shape has distance % to incoming lane for connection %."), offset, con.getDescription(fromE));
822 : }
823 : }
824 145 : PositionVector endBorder = con.toEdge->getNodeBorder(this);
825 145 : if (endBorder.size() == 0) {
826 208 : endBorder = toShape.getOrthogonal(toShape.front(), 1, false);
827 : }
828 290 : ret = NBEdge::startShapeAt(tmp.reverse(), this, endBorder).reverse();
829 145 : if (ret.size() < 2) {
830 0 : WRITE_WARNINGF(TL("Could not use custom shape for connection %."), con.getDescription(fromE));
831 : useCustomShape = false;
832 145 : } else if (ret.length2D() > tmp.length2D() + POSITION_EPS) {
833 : // shape was lengthened at the end, make sure it attaches at the center of the lane
834 50 : ret[-1] = toShape.front();
835 95 : } else if (recordError != nullptr) {
836 20 : const double offset = ret[-1].distanceTo2D(toShape.front());
837 20 : if (offset > con.toEdge->getLaneWidth(con.toLane) / 2) {
838 2 : WRITE_WARNINGF(TL("Custom shape has distance % to outgoing lane for connection %."), offset, con.getDescription(fromE));
839 : }
840 : }
841 145 : }
842 145 : }
843 148741 : if (!useCustomShape) {
844 148596 : displaceShapeAtWidthChange(fromE, con, fromShape, toShape);
845 148596 : double extrapolateBeg = 5. * fromE->getNumLanes();
846 148596 : double extrapolateEnd = 5. * con.toEdge->getNumLanes();
847 148596 : LinkDirection dir = getDirection(fromE, con.toEdge);
848 148596 : if (dir == LinkDirection::LEFT || dir == LinkDirection::TURN) {
849 57264 : shapeFlag += AVOID_WIDE_LEFT_TURN;
850 : }
851 148596 : if (con.indirectLeft) {
852 32 : shapeFlag += INDIRECT_LEFT;
853 : }
854 : #ifdef DEBUG_SMOOTH_GEOM
855 : if (DEBUGCOND) {
856 : std::cout << "computeInternalLaneShape node " << getID() << " fromE=" << fromE->getID() << " toE=" << con.toEdge->getID() << "\n";
857 : }
858 : #endif
859 148596 : ret = computeSmoothShape(fromShape, toShape,
860 148596 : numPoints, fromE->getTurnDestination() == con.toEdge,
861 : extrapolateBeg, extrapolateEnd, recordError, shapeFlag);
862 : }
863 148741 : const NBEdge::Lane& lane = fromE->getLaneStruct(con.fromLane);
864 148741 : if (lane.endOffset > 0) {
865 70 : PositionVector beg = lane.shape.getSubpart(lane.shape.length() - lane.endOffset, lane.shape.length());
866 70 : beg.append(ret);
867 : ret = beg;
868 70 : }
869 148741 : if (con.toEdge->isBidiRail() && con.toEdge->getTurnDestination(true)->getEndOffset() > 0) {
870 4 : PositionVector end = toShape.getSubpart(0, con.toEdge->getTurnDestination(true)->getEndOffset());
871 4 : ret.append(end);
872 4 : }
873 148741 : return ret;
874 148741 : }
875 :
876 :
877 : bool
878 243963 : NBNode::isConstantWidthTransition() const {
879 : return (myIncomingEdges.size() == 1
880 21529 : && myOutgoingEdges.size() == 1
881 16221 : && myIncomingEdges[0]->getNumLanes() != myOutgoingEdges[0]->getNumLanes()
882 251390 : && myIncomingEdges[0]->getTotalWidth() == myOutgoingEdges[0]->getTotalWidth());
883 : }
884 :
885 : void
886 148596 : NBNode::displaceShapeAtWidthChange(const NBEdge* from, const NBEdge::Connection& con,
887 : PositionVector& fromShape, PositionVector& toShape) const {
888 148596 : if (isConstantWidthTransition()) {
889 : // displace shapes
890 14 : NBEdge* in = myIncomingEdges[0];
891 14 : NBEdge* out = myOutgoingEdges[0];
892 14 : double outCenter = out->getLaneWidth(con.toLane) / 2;
893 27 : for (int i = 0; i < con.toLane; ++i) {
894 13 : outCenter += out->getLaneWidth(i);
895 : }
896 14 : double inCenter = in->getLaneWidth(con.fromLane) / 2;
897 25 : for (int i = 0; i < con.fromLane; ++i) {
898 11 : inCenter += in->getLaneWidth(i);
899 : }
900 : //std::cout << "displaceShapeAtWidthChange inCenter=" << inCenter << " outCenter=" << outCenter << "\n";
901 : try {
902 14 : if (in->getNumLanes() > out->getNumLanes()) {
903 : // shift toShape so the internal lane ends straight at the displaced entry point
904 3 : toShape.move2side(outCenter - inCenter);
905 : } else {
906 : // shift fromShape so the internal lane starts straight at the displaced exit point
907 11 : fromShape.move2side(inCenter - outCenter);
908 :
909 : }
910 0 : } catch (InvalidArgument&) { }
911 : } else {
912 148582 : SVCPermissions fromP = from->getPermissions(con.fromLane);
913 148582 : SVCPermissions toP = con.toEdge->getPermissions(con.toLane);
914 148582 : if ((fromP & toP) == SVC_BICYCLE && (fromP | toP) != SVC_BICYCLE) {
915 1922 : double shift = (from->getLaneWidth(con.fromLane) - con.toEdge->getLaneWidth(con.toLane)) / 2;
916 1922 : if (toP == SVC_BICYCLE) {
917 : // let connection to dedicated bicycle lane start on the right side of a mixed lane for straight an right-going connections
918 : // (on the left side for left turns)
919 : // XXX indirect left turns should also start on the right side
920 733 : LinkDirection dir = getDirection(from, con.toEdge);
921 733 : if ((dir == LinkDirection::LEFT) || (dir == LinkDirection::PARTLEFT) || (dir == LinkDirection::TURN)) {
922 320 : fromShape.move2side(-shift);
923 : } else {
924 413 : fromShape.move2side(shift);
925 : }
926 1189 : } else if (fromP == SVC_BICYCLE) {
927 : // let connection from dedicated bicycle end on the right side of a mixed lane
928 580 : toShape.move2side(-shift);
929 : }
930 : }
931 : }
932 148596 : }
933 :
934 : bool
935 770749 : NBNode::needsCont(const NBEdge* fromE, const NBEdge* otherFromE,
936 : const NBEdge::Connection& c, const NBEdge::Connection& otherC, bool checkOnlyTLS) const {
937 770749 : const NBEdge* toE = c.toEdge;
938 770749 : const NBEdge* otherToE = otherC.toEdge;
939 :
940 770749 : if (!checkOnlyTLS) {
941 755808 : if (myType == SumoXMLNodeType::RIGHT_BEFORE_LEFT
942 : || myType == SumoXMLNodeType::LEFT_BEFORE_RIGHT
943 755808 : || myType == SumoXMLNodeType::ALLWAY_STOP) {
944 : return false;
945 : }
946 690204 : LinkDirection d1 = getDirection(fromE, toE);
947 690204 : const bool thisRight = (d1 == LinkDirection::RIGHT || d1 == LinkDirection::PARTRIGHT);
948 933199 : const bool rightTurnConflict = (thisRight &&
949 242995 : NBNode::rightTurnConflict(fromE, toE, c.fromLane, otherFromE, otherToE, otherC.fromLane));
950 690204 : if (thisRight && !rightTurnConflict) {
951 : return false;
952 : }
953 447514 : if (myRequest && myRequest->indirectLeftTurnConflict(fromE, c, otherFromE, otherC, false)) {
954 : return true;
955 : }
956 447482 : if (!(foes(otherFromE, otherToE, fromE, toE) || myRequest == nullptr || rightTurnConflict)) {
957 : // if they do not cross, no waiting place is needed
958 : return false;
959 : }
960 159011 : LinkDirection d2 = getDirection(otherFromE, otherToE);
961 159011 : if (d2 == LinkDirection::TURN) {
962 : return false;
963 : }
964 144167 : if (fromE == otherFromE && !thisRight) {
965 : // ignore same edge links except for right-turns
966 : return false;
967 : }
968 142703 : if (thisRight && d2 != LinkDirection::STRAIGHT) {
969 : return false;
970 : }
971 : }
972 157535 : if (c.tlID != "") {
973 : assert(myTrafficLights.size() > 0 || myType == SumoXMLNodeType::RAIL_CROSSING || myType == SumoXMLNodeType::RAIL_SIGNAL);
974 77180 : for (std::set<NBTrafficLightDefinition*>::const_iterator it = myTrafficLights.begin(); it != myTrafficLights.end(); ++it) {
975 47218 : if ((*it)->needsCont(fromE, toE, otherFromE, otherToE)) {
976 : return true;
977 : }
978 : }
979 : return false;
980 : }
981 110515 : if (fromE->getJunctionPriority(this) > 0 && otherFromE->getJunctionPriority(this) > 0) {
982 21869 : return mustBrake(fromE, toE, c.fromLane, c.toLane, false);
983 : }
984 : return false;
985 : }
986 :
987 : bool
988 1163961 : NBNode::tlsContConflict(const NBEdge* from, const NBEdge::Connection& c,
989 : const NBEdge* foeFrom, const NBEdge::Connection& foe) const {
990 167768 : return (foe.haveVia && isTLControlled() && c.tlLinkIndex >= 0 && foe.tlLinkIndex >= 0
991 67374 : && !foeFrom->isTurningDirectionAt(foe.toEdge)
992 37669 : && foes(from, c.toEdge, foeFrom, foe.toEdge)
993 1178902 : && !needsCont(foeFrom, from, foe, c, true));
994 : }
995 :
996 :
997 : void
998 14045 : NBNode::removeJoinedTrafficLights() {
999 : std::set<NBTrafficLightDefinition*> trafficLights = myTrafficLights; // make a copy because we will modify the original
1000 14116 : for (std::set<NBTrafficLightDefinition*>::const_iterator i = trafficLights.begin(); i != trafficLights.end(); ++i) {
1001 : // if this is the only controlled node we keep the tlDef as it is to generate a warning later
1002 71 : if ((*i)->getNodes().size() > 1) {
1003 : myTrafficLights.erase(*i);
1004 7 : (*i)->removeNode(this);
1005 7 : (*i)->setParticipantsInformation();
1006 7 : (*i)->setTLControllingInformation();
1007 : }
1008 : }
1009 14045 : }
1010 :
1011 :
1012 : void
1013 50758 : NBNode::computeLogic(const NBEdgeCont& ec) {
1014 50758 : delete myRequest; // possibly recomputation step
1015 50758 : myRequest = nullptr;
1016 50758 : if (myIncomingEdges.size() == 0 || myOutgoingEdges.size() == 0) {
1017 : // no logic if nothing happens here
1018 7841 : myType = SumoXMLNodeType::DEAD_END;
1019 7841 : removeJoinedTrafficLights();
1020 7841 : return;
1021 : }
1022 : // compute the logic if necessary or split the junction
1023 42917 : if (myType != SumoXMLNodeType::NOJUNCTION && myType != SumoXMLNodeType::DISTRICT && myType != SumoXMLNodeType::TRAFFIC_LIGHT_NOJUNCTION) {
1024 : // build the request
1025 42795 : myRequest = new NBRequest(ec, this, myAllEdges, myIncomingEdges, myOutgoingEdges, myBlockedConnections);
1026 : // check whether it is not too large
1027 42795 : int numConnections = numNormalConnections();
1028 42795 : if (numConnections >= SUMO_MAX_CONNECTIONS) {
1029 : // yep -> make it untcontrolled, warn
1030 0 : delete myRequest;
1031 0 : myRequest = nullptr;
1032 0 : if (myType == SumoXMLNodeType::TRAFFIC_LIGHT) {
1033 0 : myType = SumoXMLNodeType::TRAFFIC_LIGHT_NOJUNCTION;
1034 : } else {
1035 0 : myType = SumoXMLNodeType::NOJUNCTION;
1036 : }
1037 0 : WRITE_WARNINGF(TL("Junction '%' is too complicated (% connections, max %); will be set to %."),
1038 : getID(), numConnections, SUMO_MAX_CONNECTIONS, toString(myType));
1039 42795 : } else if (numConnections == 0) {
1040 6204 : delete myRequest;
1041 6204 : myRequest = nullptr;
1042 6204 : myType = SumoXMLNodeType::DEAD_END;
1043 6204 : removeJoinedTrafficLights();
1044 : } else {
1045 36591 : myRequest->buildBitfieldLogic();
1046 : }
1047 : }
1048 : }
1049 :
1050 :
1051 : void
1052 50758 : NBNode::computeLogic2(bool checkLaneFoes) {
1053 50758 : if (myRequest != nullptr) {
1054 36591 : myRequest->computeLogic(checkLaneFoes);
1055 : }
1056 50758 : }
1057 :
1058 : void
1059 50758 : NBNode::computeKeepClear() {
1060 50758 : if (hasConflict()) {
1061 16752 : if (!myKeepClear) {
1062 10 : for (NBEdge* incoming : myIncomingEdges) {
1063 : std::vector<NBEdge::Connection>& connections = incoming->getConnections();
1064 40 : for (NBEdge::Connection& c : connections) {
1065 32 : c.keepClear = KEEPCLEAR_FALSE;
1066 : }
1067 : }
1068 16750 : } else if (geometryLike() && myCrossings.size() == 0 && !isTLControlled()) {
1069 : int linkIndex = 0;
1070 777 : for (NBEdge* incoming : myIncomingEdges) {
1071 : std::vector<NBEdge::Connection>& connections = incoming->getConnections();
1072 1688 : for (NBEdge::Connection& c : connections) {
1073 1175 : if (c.keepClear == KEEPCLEAR_UNSPECIFIED && myRequest->hasConflictAtLink(linkIndex)) {
1074 574 : const LinkState linkState = getLinkState(incoming, c.toEdge, c.fromLane, c.toLane, c.mayDefinitelyPass, c.tlID);
1075 574 : if (linkState == LINKSTATE_MAJOR) {
1076 331 : c.keepClear = KEEPCLEAR_FALSE;
1077 : }
1078 : }
1079 : }
1080 513 : linkIndex++;
1081 : }
1082 : }
1083 : }
1084 50758 : }
1085 :
1086 :
1087 : bool
1088 35707 : NBNode::writeLogic(OutputDevice& into) const {
1089 35707 : if (myRequest) {
1090 35623 : myRequest->writeLogic(into);
1091 35623 : return true;
1092 : }
1093 : return false;
1094 : }
1095 :
1096 :
1097 : const std::string
1098 0 : NBNode::getFoes(int linkIndex) const {
1099 0 : if (myRequest == nullptr) {
1100 0 : return "";
1101 : } else {
1102 0 : return myRequest->getFoes(linkIndex);
1103 : }
1104 : }
1105 :
1106 :
1107 : const std::string
1108 0 : NBNode::getResponse(int linkIndex) const {
1109 0 : if (myRequest == nullptr) {
1110 0 : return "";
1111 : } else {
1112 0 : return myRequest->getResponse(linkIndex);
1113 : }
1114 : }
1115 :
1116 : bool
1117 50943 : NBNode::hasConflict() const {
1118 50943 : if (myRequest == nullptr) {
1119 : return false;
1120 : } else {
1121 36773 : return myRequest->hasConflict();
1122 : }
1123 : }
1124 :
1125 :
1126 : bool
1127 439 : NBNode::hasConflict(const NBEdge* e) const {
1128 439 : if (myRequest == nullptr) {
1129 : return false;
1130 : }
1131 507 : for (const auto& con : e->getConnections()) {
1132 505 : const int index = getConnectionIndex(e, con);
1133 505 : if (myRequest->hasConflictAtLink(index)) {
1134 : return true;
1135 : }
1136 : }
1137 : return false;
1138 : }
1139 :
1140 :
1141 : void
1142 55 : NBNode::updateSurroundingGeometry() {
1143 55 : NBTurningDirectionsComputer::computeTurnDirectionsForNode(this, false);
1144 55 : sortEdges(false);
1145 55 : computeNodeShape(-1);
1146 426 : for (NBEdge* edge : myAllEdges) {
1147 371 : edge->computeEdgeShape();
1148 : }
1149 55 : }
1150 :
1151 : void
1152 73742 : NBNode::computeNodeShape(double mismatchThreshold) {
1153 73742 : if (myHaveCustomPoly) {
1154 : return;
1155 : }
1156 73707 : if (myIncomingEdges.size() == 0 && myOutgoingEdges.size() == 0) {
1157 : // may be an intermediate step during network editing
1158 : myPoly.clear();
1159 2180 : myPoly.push_back(myPosition);
1160 2180 : return;
1161 : }
1162 143054 : if (OptionsCont::getOptions().getFloat("default.junctions.radius") < 0) {
1163 : // skip shape computation by option
1164 : return;
1165 : }
1166 : try {
1167 71522 : NBNodeShapeComputer computer(*this);
1168 143044 : myPoly = computer.compute(OptionsCont::getOptions().getBool("junctions.minimal-shape"));
1169 214407 : if (myRadius == UNSPECIFIED_RADIUS && !OptionsCont::getOptions().isDefault("default.junctions.radius")) {
1170 51 : myRadius = computer.getRadius();
1171 : }
1172 71522 : if (myPoly.size() > 0) {
1173 : PositionVector tmp = myPoly;
1174 71522 : tmp.push_back_noDoublePos(tmp[0]); // need closed shape
1175 : if (mismatchThreshold >= 0
1176 45266 : && !tmp.around(myPosition)
1177 86938 : && tmp.distance2D(myPosition) > mismatchThreshold) {
1178 171 : WRITE_WARNINGF(TL("Shape for junction '%' has distance % to its given position."), myID, tmp.distance2D(myPosition));
1179 : }
1180 71522 : }
1181 71522 : } catch (InvalidArgument&) {
1182 0 : WRITE_WARNINGF(TL("For junction '%': could not compute shape."), myID);
1183 : // make sure our shape is not empty because our XML schema forbids empty attributes
1184 : myPoly.clear();
1185 0 : myPoly.push_back(myPosition);
1186 0 : }
1187 : }
1188 :
1189 :
1190 : void
1191 50762 : NBNode::computeLanes2Lanes() {
1192 : // special case a):
1193 : // one in, one out, the outgoing has more lanes
1194 50762 : if (myIncomingEdges.size() == 1 && myOutgoingEdges.size() == 1) {
1195 14411 : NBEdge* in = myIncomingEdges[0];
1196 14411 : NBEdge* out = myOutgoingEdges[0];
1197 : // check if it's not the turnaround
1198 14411 : if (in->getTurnDestination() == out) {
1199 : // will be added later or not...
1200 9017 : return;
1201 : }
1202 : int inOffset, inEnd, outOffset, outEnd, addedLanes;
1203 5941 : getReduction(out, in, outOffset, outEnd, inOffset, inEnd, addedLanes);
1204 : if (in->getStep() <= NBEdge::EdgeBuildingStep::LANES2EDGES
1205 4056 : && addedLanes > 0
1206 6501 : && in->isConnectedTo(out)) {
1207 547 : const int addedRight = addedLanesRight(out, addedLanes);
1208 547 : const int addedLeft = addedLanes - addedRight;
1209 : #ifdef DEBUG_CONNECTION_GUESSING
1210 : if (DEBUGCOND) {
1211 : std::cout << "l2l node=" << getID() << " specialCase a. addedRight=" << addedRight << " addedLeft=" << addedLeft << " inOff=" << inOffset << " outOff=" << outOffset << " inEnd=" << inEnd << " outEnd=" << outEnd << "\n";
1212 : }
1213 : #endif
1214 : // "straight" connections
1215 1688 : for (int i = inOffset; i < inEnd; ++i) {
1216 2282 : in->setConnection(i, out, i - inOffset + outOffset + addedRight, NBEdge::Lane2LaneInfoType::COMPUTED);
1217 : }
1218 : // connect extra lane on the right
1219 602 : for (int i = 0; i < addedRight; ++i) {
1220 110 : in->setConnection(inOffset, out, outOffset + i, NBEdge::Lane2LaneInfoType::COMPUTED);
1221 : }
1222 : // connect extra lane on the left
1223 547 : const int inLeftMost = inEnd - 1;;
1224 547 : const int outOffset2 = outOffset + addedRight + inEnd - inOffset;
1225 1069 : for (int i = 0; i < addedLeft; ++i) {
1226 1044 : in->setConnection(inLeftMost, out, outOffset2 + i, NBEdge::Lane2LaneInfoType::COMPUTED);
1227 : }
1228 547 : if (out->getSpecialLane(SVC_BICYCLE) >= 0) {
1229 16 : recheckVClassConnections(out);
1230 : }
1231 547 : return;
1232 : }
1233 : }
1234 : // special case b):
1235 : // two in, one out, the outgoing has the same number of lanes as the sum of the incoming
1236 : // --> highway on-ramp
1237 41745 : if (myIncomingEdges.size() == 2 && myOutgoingEdges.size() == 1) {
1238 3037 : NBEdge* const out = myOutgoingEdges[0];
1239 3037 : NBEdge* in1 = myIncomingEdges[0];
1240 3037 : NBEdge* in2 = myIncomingEdges[1];
1241 3037 : const int outOffset = MAX2(0, out->getFirstNonPedestrianNonBicycleLaneIndex(FORWARD, true));
1242 3037 : int in1Offset = MAX2(0, in1->getFirstNonPedestrianNonBicycleLaneIndex(FORWARD, true));
1243 3037 : int in2Offset = MAX2(0, in2->getFirstNonPedestrianNonBicycleLaneIndex(FORWARD, true));
1244 3037 : if (in1->getNumLanes() + in2->getNumLanes() - in1Offset - in2Offset == out->getNumLanes() - outOffset
1245 130 : && (in1->getStep() <= NBEdge::EdgeBuildingStep::LANES2EDGES)
1246 45 : && (in2->getStep() <= NBEdge::EdgeBuildingStep::LANES2EDGES)
1247 45 : && in1 != out
1248 45 : && in2 != out
1249 45 : && in1->isConnectedTo(out)
1250 44 : && in2->isConnectedTo(out)
1251 44 : && in1->getSpecialLane(SVC_BICYCLE) == -1
1252 42 : && in2->getSpecialLane(SVC_BICYCLE) == -1
1253 42 : && out->getSpecialLane(SVC_BICYCLE) == -1
1254 42 : && in1->getSpecialLane(SVC_TRAM) == -1
1255 41 : && in2->getSpecialLane(SVC_TRAM) == -1
1256 41 : && out->getSpecialLane(SVC_TRAM) == -1
1257 3078 : && isLongEnough(out, MIN_WEAVE_LENGTH)) {
1258 : #ifdef DEBUG_CONNECTION_GUESSING
1259 : if (DEBUGCOND) {
1260 : std::cout << "l2l node=" << getID() << " specialCase b\n";
1261 : }
1262 : #endif
1263 : // for internal: check which one is the rightmost
1264 22 : double a1 = in1->getAngleAtNode(this);
1265 22 : double a2 = in2->getAngleAtNode(this);
1266 22 : double ccw = GeomHelper::getCCWAngleDiff(a1, a2);
1267 22 : double cw = GeomHelper::getCWAngleDiff(a1, a2);
1268 22 : if (ccw > cw) {
1269 : std::swap(in1, in2);
1270 : std::swap(in1Offset, in2Offset);
1271 : }
1272 22 : in1->addLane2LaneConnections(in1Offset, out, outOffset, in1->getNumLanes() - in1Offset, NBEdge::Lane2LaneInfoType::COMPUTED, true);
1273 22 : in2->addLane2LaneConnections(in2Offset, out, in1->getNumLanes() + outOffset - in1Offset, in2->getNumLanes() - in2Offset, NBEdge::Lane2LaneInfoType::COMPUTED, true);
1274 22 : if (out->getSpecialLane(SVC_BICYCLE) >= 0) {
1275 0 : recheckVClassConnections(out);
1276 : }
1277 : return;
1278 : }
1279 : }
1280 : // special case c):
1281 : // one in, two out, the incoming has the same number of lanes or only 1 lane less than the sum of the outgoing lanes
1282 : // --> highway off-ramp
1283 41723 : if (myIncomingEdges.size() == 1 && myOutgoingEdges.size() == 2) {
1284 3922 : NBEdge* in = myIncomingEdges[0];
1285 3922 : NBEdge* out1 = myOutgoingEdges[0];
1286 3922 : NBEdge* out2 = myOutgoingEdges[1];
1287 3922 : const int inOffset = MAX2(0, in->getFirstNonPedestrianNonBicycleLaneIndex(FORWARD, true));
1288 3922 : int out1Offset = MAX2(0, out1->getFirstNonPedestrianNonBicycleLaneIndex(FORWARD, true));
1289 3922 : int out2Offset = MAX2(0, out2->getFirstNonPedestrianNonBicycleLaneIndex(FORWARD, true));
1290 3922 : const int deltaLaneSum = (out2->getNumLanes() + out1->getNumLanes() - out1Offset - out2Offset) - (in->getNumLanes() - inOffset);
1291 10910 : if ((deltaLaneSum == 0 || (deltaLaneSum == 1 && in->getPermissionVariants(inOffset, in->getNumLanes()).size() == 1))
1292 3726 : && (in->getStep() <= NBEdge::EdgeBuildingStep::LANES2EDGES)
1293 2553 : && in != out1
1294 2553 : && in != out2
1295 2553 : && in->isConnectedTo(out1)
1296 946 : && in->isConnectedTo(out2)
1297 770 : && !in->isTurningDirectionAt(out1)
1298 4634 : && !in->isTurningDirectionAt(out2)
1299 : ) {
1300 : #ifdef DEBUG_CONNECTION_GUESSING
1301 : if (DEBUGCOND) {
1302 : std::cout << "l2l node=" << getID() << " specialCase c\n";
1303 : }
1304 : #endif
1305 : // for internal: check which one is the rightmost
1306 623 : if (NBContHelper::relative_outgoing_edge_sorter(in)(out2, out1)) {
1307 : std::swap(out1, out2);
1308 : std::swap(out1Offset, out2Offset);
1309 : }
1310 623 : in->addLane2LaneConnections(inOffset, out1, out1Offset, out1->getNumLanes() - out1Offset, NBEdge::Lane2LaneInfoType::COMPUTED, true);
1311 623 : in->addLane2LaneConnections(out1->getNumLanes() + inOffset - out1Offset - deltaLaneSum, out2, out2Offset, out2->getNumLanes() - out2Offset, NBEdge::Lane2LaneInfoType::COMPUTED, false);
1312 623 : if (in->getSpecialLane(SVC_BICYCLE) >= 0) {
1313 10 : recheckVClassConnections(out1);
1314 10 : recheckVClassConnections(out2);
1315 : }
1316 : return;
1317 : }
1318 : }
1319 : // special case d):
1320 : // one in, one out, the outgoing has one lane less and node has type 'zipper'
1321 41100 : if (myIncomingEdges.size() == 1 && myOutgoingEdges.size() == 1 && myType == SumoXMLNodeType::ZIPPER) {
1322 7 : NBEdge* in = myIncomingEdges[0];
1323 7 : NBEdge* out = myOutgoingEdges[0];
1324 : // check if it's not the turnaround
1325 7 : if (in->getTurnDestination() == out) {
1326 : // will be added later or not...
1327 : return;
1328 : }
1329 : #ifdef DEBUG_CONNECTION_GUESSING
1330 : if (DEBUGCOND) {
1331 : std::cout << "l2l node=" << getID() << " specialCase d\n";
1332 : }
1333 : #endif
1334 7 : const int inOffset = MAX2(0, in->getFirstNonPedestrianLaneIndex(FORWARD, true));
1335 7 : const int outOffset = MAX2(0, out->getFirstNonPedestrianLaneIndex(FORWARD, true));
1336 : if (in->getStep() <= NBEdge::EdgeBuildingStep::LANES2EDGES
1337 1 : && in->getNumLanes() - inOffset == out->getNumLanes() - outOffset + 1
1338 1 : && in != out
1339 8 : && in->isConnectedTo(out)) {
1340 3 : for (int i = inOffset; i < in->getNumLanes(); ++i) {
1341 4 : in->setConnection(i, out, MIN2(outOffset + i, out->getNumLanes() - 1), NBEdge::Lane2LaneInfoType::COMPUTED, true);
1342 : }
1343 : return;
1344 : }
1345 : }
1346 : // special case f):
1347 : // one in, one out, out has reduced or same number of lanes
1348 41099 : if (myIncomingEdges.size() == 1 && myOutgoingEdges.size() == 1) {
1349 5393 : NBEdge* in = myIncomingEdges[0];
1350 5393 : NBEdge* out = myOutgoingEdges[0];
1351 : // check if it's not the turnaround
1352 5393 : if (in->getTurnDestination() == out) {
1353 : // will be added later or not...
1354 2113 : return;
1355 : }
1356 : int inOffset, inEnd, outOffset, outEnd, reduction;
1357 5393 : getReduction(in, out, inOffset, inEnd, outOffset, outEnd, reduction);
1358 : if (in->getStep() <= NBEdge::EdgeBuildingStep::LANES2EDGES
1359 3508 : && reduction >= 0
1360 3495 : && in != out
1361 8888 : && in->isConnectedTo(out)) {
1362 : #ifdef DEBUG_CONNECTION_GUESSING
1363 : if (DEBUGCOND) {
1364 : std::cout << "l2l node=" << getID() << " specialCase f inOff=" << inOffset << " outOff=" << outOffset << " inEnd=" << inEnd << " outEnd=" << outEnd << " reduction=" << reduction << "\n";
1365 : }
1366 : #endif
1367 : // in case of reduced lane number, let the rightmost lanse end
1368 2113 : inOffset += reduction;
1369 5486 : for (int i = outOffset; i < outEnd; ++i) {
1370 6746 : in->setConnection(i + inOffset - outOffset, out, i, NBEdge::Lane2LaneInfoType::COMPUTED);
1371 : }
1372 : //std::cout << " special case f at node=" << getID() << " inOffset=" << inOffset << " outOffset=" << outOffset << "\n";
1373 2113 : recheckVClassConnections(out);
1374 2113 : return;
1375 : }
1376 : }
1377 :
1378 : // go through this node's outgoing edges
1379 : // for every outgoing edge, compute the distribution of the node's
1380 : // incoming edges on this edge when approaching this edge
1381 : // the incoming edges' steps will then also be marked as LANE2LANE_RECHECK...
1382 : EdgeVector approaching;
1383 117391 : for (NBEdge* currentOutgoing : myOutgoingEdges) {
1384 : // get the information about edges that do approach this edge
1385 78405 : getEdgesThatApproach(currentOutgoing, approaching);
1386 78405 : const int numApproaching = (int)approaching.size();
1387 78405 : if (numApproaching != 0) {
1388 62266 : ApproachingDivider divider(approaching, currentOutgoing);
1389 62266 : Bresenham::compute(÷r, numApproaching, divider.numAvailableLanes());
1390 62266 : }
1391 : #ifdef DEBUG_CONNECTION_GUESSING
1392 : if (DEBUGCOND) {
1393 : std::cout << "l2l node=" << getID() << " bresenham:\n";
1394 : for (NBEdge* e : myIncomingEdges) {
1395 : const std::vector<NBEdge::Connection>& elv = e->getConnections();
1396 : for (std::vector<NBEdge::Connection>::const_iterator k = elv.begin(); k != elv.end(); ++k) {
1397 : std::cout << " " << e->getID() << "_" << (*k).fromLane << " -> " << (*k).toEdge->getID() << "_" << (*k).toLane << "\n";
1398 : }
1399 : }
1400 : }
1401 : #endif
1402 78405 : recheckVClassConnections(currentOutgoing);
1403 :
1404 : // in case of lane change restrictions on the outgoing edge, ensure that
1405 : // all its lanes can be reached from each connected incoming edge
1406 : bool targetProhibitsChange = false;
1407 177746 : for (int i = 0; i < currentOutgoing->getNumLanes(); i++) {
1408 99360 : const NBEdge::Lane& lane = currentOutgoing->getLanes()[i];
1409 148 : if ((lane.changeLeft != SVCAll && lane.changeLeft != SVC_IGNORING && i + 1 < currentOutgoing->getNumLanes())
1410 99490 : || (lane.changeRight != SVCAll && lane.changeRight != SVC_IGNORING && i > 0)) {
1411 : targetProhibitsChange = true;
1412 : break;
1413 : }
1414 : }
1415 78405 : if (targetProhibitsChange) {
1416 : //std::cout << " node=" << getID() << " outgoing=" << currentOutgoing->getID() << " targetProhibitsChange\n";
1417 48 : for (NBEdge* incoming : myIncomingEdges) {
1418 29 : if (incoming->getStep() < NBEdge::EdgeBuildingStep::LANES2LANES_DONE) {
1419 : std::map<int, int> outToIn;
1420 111 : for (const NBEdge::Connection& c : incoming->getConnections()) {
1421 87 : if (c.toEdge == currentOutgoing) {
1422 23 : outToIn[c.toLane] = c.fromLane;
1423 : }
1424 : }
1425 77 : for (int toLane = 0; toLane < currentOutgoing->getNumLanes(); toLane++) {
1426 : if (outToIn.count(toLane) == 0) {
1427 : bool added = false;
1428 : // find incoming lane for neighboring outgoing
1429 42 : for (int i = 0; i < toLane; i++) {
1430 : if (outToIn.count(i) != 0) {
1431 8 : incoming->setConnection(outToIn[i], currentOutgoing, toLane, NBEdge::Lane2LaneInfoType::COMPUTED);
1432 : added = true;
1433 : break;
1434 : }
1435 : }
1436 : if (!added) {
1437 64 : for (int i = toLane; i < currentOutgoing->getNumLanes(); i++) {
1438 : if (outToIn.count(i) != 0) {
1439 10 : incoming->setConnection(outToIn[i], currentOutgoing, toLane, NBEdge::Lane2LaneInfoType::COMPUTED);
1440 : added = true;
1441 10 : break;
1442 : }
1443 : }
1444 : }
1445 : }
1446 : }
1447 : }
1448 : }
1449 : }
1450 : }
1451 : // special case e): rail_crossing
1452 : // there should only be straight connections here
1453 38986 : if (myType == SumoXMLNodeType::RAIL_CROSSING) {
1454 625 : for (EdgeVector::const_iterator i = myIncomingEdges.begin(); i != myIncomingEdges.end(); i++) {
1455 459 : const std::vector<NBEdge::Connection> cons = (*i)->getConnections();
1456 773 : for (std::vector<NBEdge::Connection>::const_iterator k = cons.begin(); k != cons.end(); ++k) {
1457 314 : if (getDirection(*i, (*k).toEdge) == LinkDirection::TURN) {
1458 0 : (*i)->removeFromConnections((*k).toEdge);
1459 : }
1460 : }
1461 459 : }
1462 : }
1463 :
1464 : // ... but we may have the case that there are no outgoing edges
1465 : // In this case, we have to mark the incoming edges as being in state
1466 : // LANE2LANE( not RECHECK) by hand
1467 38986 : if (myOutgoingEdges.size() == 0) {
1468 9330 : for (NBEdge* incoming : myIncomingEdges) {
1469 4994 : incoming->markAsInLane2LaneState();
1470 : }
1471 : }
1472 :
1473 : #ifdef DEBUG_CONNECTION_GUESSING
1474 : if (DEBUGCOND) {
1475 : std::cout << "final connections at " << getID() << "\n";
1476 : for (NBEdge* e : myIncomingEdges) {
1477 : const std::vector<NBEdge::Connection>& elv = e->getConnections();
1478 : for (std::vector<NBEdge::Connection>::const_iterator k = elv.begin(); k != elv.end(); ++k) {
1479 : std::cout << " " << e->getID() << "_" << (*k).fromLane << " -> " << (*k).toEdge->getID() << "_" << (*k).toLane << "\n";
1480 : }
1481 : }
1482 : }
1483 : #endif
1484 38986 : }
1485 :
1486 : void
1487 80554 : NBNode::recheckVClassConnections(NBEdge* currentOutgoing) {
1488 80554 : const int bikeLaneTarget = currentOutgoing->getSpecialLane(SVC_BICYCLE);
1489 :
1490 : // ensure that all modes have a connection if possible
1491 290172 : for (NBEdge* incoming : myIncomingEdges) {
1492 330170 : if (incoming->getConnectionLanes(currentOutgoing).size() > 0 && incoming->getStep() <= NBEdge::EdgeBuildingStep::LANES2LANES_DONE) {
1493 : // no connections are needed for pedestrians during this step
1494 : // no satisfaction is possible if the outgoing edge disallows
1495 89066 : SVCPermissions unsatisfied = incoming->getPermissions() & currentOutgoing->getPermissions() & ~SVC_PEDESTRIAN;
1496 : //std::cout << "initial unsatisfied modes from edge=" << incoming->getID() << " toEdge=" << currentOutgoing->getID() << " deadModes=" << getVehicleClassNames(unsatisfied) << "\n";
1497 : const std::vector<NBEdge::Connection>& elv = incoming->getConnections();
1498 321996 : for (std::vector<NBEdge::Connection>::const_iterator k = elv.begin(); k != elv.end(); ++k) {
1499 : const NBEdge::Connection& c = *k;
1500 232930 : if (c.toEdge == currentOutgoing && c.toLane >= 0) {
1501 99871 : const SVCPermissions satisfied = (incoming->getPermissions(c.fromLane) & c.toEdge->getPermissions(c.toLane));
1502 : //std::cout << " from=" << incoming->getID() << "_" << c.fromLane << " to=" << c.toEdge->getID() << "_" << c.toLane << " satisfied=" << getVehicleClassNames(satisfied) << "\n";
1503 99871 : unsatisfied &= ~satisfied;
1504 : }
1505 : }
1506 89066 : if (unsatisfied != 0) {
1507 : #ifdef DEBUG_CONNECTION_GUESSING
1508 : if (DEBUGCOND) {
1509 : std::cout << " unsatisfied modes from edge=" << incoming->getID() << " toEdge=" << currentOutgoing->getID() << " deadModes=" << getVehicleClassNames(unsatisfied) << "\n";
1510 : }
1511 : #endif
1512 : int fromLane = 0;
1513 3142 : while (unsatisfied != 0 && fromLane < incoming->getNumLanes()) {
1514 2001 : if ((incoming->getPermissions(fromLane) & unsatisfied) != 0) {
1515 4423 : for (int toLane = 0; toLane < currentOutgoing->getNumLanes(); ++toLane) {
1516 3282 : const SVCPermissions satisfied = incoming->getPermissions(fromLane) & currentOutgoing->getPermissions(toLane) & unsatisfied;
1517 3282 : if (satisfied != 0 && !incoming->getLaneStruct(fromLane).connectionsDone) {
1518 1141 : if (incoming->hasConnectionTo(currentOutgoing, toLane)
1519 282 : && unsatisfied == SVC_TRAM
1520 1147 : && incoming->getPermissions(fromLane) == currentOutgoing->getPermissions(toLane)) {
1521 : // avoid double tram connection by shifting an existing connection
1522 11 : for (auto con : incoming->getConnections()) {
1523 11 : if (con.toEdge == currentOutgoing && con.toLane == toLane) {
1524 : #ifdef DEBUG_CONNECTION_GUESSING
1525 : if (DEBUGCOND) {
1526 : std::cout << " shifting connection from=" << con.fromLane << " to=" << currentOutgoing->getID() << "_" << toLane << ": newFromLane=" << fromLane << " satisfies=" << getVehicleClassNames(satisfied) << "\n";
1527 : }
1528 : #endif
1529 5 : incoming->getConnectionRef(con.fromLane, con.toEdge, toLane).fromLane = fromLane;
1530 : unsatisfied &= ~satisfied;
1531 : break;
1532 : }
1533 11 : }
1534 : } else {
1535 : // other modes (i.e. bus) can fix lane permissions NBPTLineCont::fixPermissions but do not wish to create parallel tram tracks here
1536 1136 : bool mayUseSameDestination = unsatisfied == SVC_TRAM || (unsatisfied & SVC_PASSENGER) != 0;
1537 1136 : incoming->setConnection((int)fromLane, currentOutgoing, toLane, NBEdge::Lane2LaneInfoType::COMPUTED, mayUseSameDestination);
1538 : #ifdef DEBUG_CONNECTION_GUESSING
1539 : if (DEBUGCOND) {
1540 : std::cout << " new connection from=" << fromLane << " to=" << currentOutgoing->getID() << "_" << toLane << " satisfies=" << getVehicleClassNames(satisfied) << "\n";
1541 : }
1542 : #endif
1543 1136 : unsatisfied &= ~satisfied;
1544 : }
1545 : }
1546 : }
1547 : }
1548 2001 : fromLane++;
1549 : }
1550 : #ifdef DEBUG_CONNECTION_GUESSING
1551 : if (DEBUGCOND) {
1552 : if (unsatisfied != 0) {
1553 : std::cout << " still unsatisfied modes from edge=" << incoming->getID() << " toEdge=" << currentOutgoing->getID() << " deadModes=" << getVehicleClassNames(unsatisfied) << "\n";
1554 : }
1555 : }
1556 : #endif
1557 : }
1558 : }
1559 : // prevent dead-end bicycle lanes (they were excluded by the ApproachingDivider)
1560 : // and the bicycle mode might already be satisfied by other lanes
1561 : // assume that left-turns and turn-arounds are better satisfied from lanes to the left
1562 209618 : LinkDirection dir = getDirection(incoming, currentOutgoing);
1563 : if (incoming->getStep() <= NBEdge::EdgeBuildingStep::LANES2LANES_DONE
1564 209618 : && ((bikeLaneTarget >= 0 && dir != LinkDirection::TURN)
1565 158983 : || dir == LinkDirection::RIGHT || dir == LinkDirection::PARTRIGHT || dir == LinkDirection::STRAIGHT)) {
1566 : bool builtConnection = false;
1567 195473 : for (int i = 0; i < (int)incoming->getNumLanes(); i++) {
1568 110731 : if (incoming->getPermissions(i) == SVC_BICYCLE
1569 111169 : && incoming->getConnectionsFromLane(i, currentOutgoing).size() == 0) {
1570 : // find a dedicated bike lane as target
1571 438 : if (bikeLaneTarget >= 0) {
1572 154 : incoming->setConnection(i, currentOutgoing, bikeLaneTarget, NBEdge::Lane2LaneInfoType::COMPUTED);
1573 : builtConnection = true;
1574 : } else {
1575 : // use any lane that allows bicycles
1576 747 : for (int i2 = 0; i2 < (int)currentOutgoing->getNumLanes(); i2++) {
1577 499 : if ((currentOutgoing->getPermissions(i2) & SVC_BICYCLE) != 0) {
1578 : // possibly a double-connection
1579 113 : const bool allowDouble = (incoming->getPermissions(i) == SVC_BICYCLE
1580 113 : && (dir == LinkDirection::RIGHT || dir == LinkDirection::PARTRIGHT || dir == LinkDirection::STRAIGHT));
1581 113 : incoming->setConnection(i, currentOutgoing, i2, NBEdge::Lane2LaneInfoType::COMPUTED, allowDouble);
1582 : builtConnection = true;
1583 113 : break;
1584 : }
1585 : }
1586 : }
1587 : }
1588 : }
1589 169484 : if (!builtConnection && bikeLaneTarget >= 0
1590 85166 : && incoming->getConnectionsFromLane(-1, currentOutgoing, bikeLaneTarget).size() == 0) {
1591 : // find origin lane that allows bicycles
1592 : int start = 0;
1593 : int end = incoming->getNumLanes();
1594 : int inc = 1;
1595 424 : if (dir == LinkDirection::TURN || dir == LinkDirection::LEFT || dir == LinkDirection::PARTLEFT) {
1596 : std::swap(start, end);
1597 : inc = -1;
1598 : }
1599 767 : for (int i = start; i < end; i += inc) {
1600 346 : if ((incoming->getPermissions(i) & SVC_BICYCLE) != 0) {
1601 3 : incoming->setConnection(i, currentOutgoing, bikeLaneTarget, NBEdge::Lane2LaneInfoType::COMPUTED);
1602 3 : break;
1603 : }
1604 : }
1605 : }
1606 : }
1607 : }
1608 80554 : }
1609 :
1610 : void
1611 11378 : NBNode::getReduction(const NBEdge* in, const NBEdge* out, int& inOffset, int& inEnd, int& outOffset, int& outEnd, int& reduction) const {
1612 11378 : inOffset = MAX2(0, in->getFirstNonPedestrianNonBicycleLaneIndex(FORWARD, true));
1613 11378 : outOffset = MAX2(0, out->getFirstNonPedestrianNonBicycleLaneIndex(FORWARD, true));
1614 11378 : inEnd = in->getFirstNonPedestrianLaneIndex(BACKWARD, true) + 1;
1615 11378 : outEnd = out->getFirstNonPedestrianLaneIndex(BACKWARD, true) + 1;
1616 11378 : reduction = (inEnd - inOffset) - (outEnd - outOffset);
1617 11378 : }
1618 :
1619 :
1620 : int
1621 547 : NBNode::addedLanesRight(NBEdge* out, int addedLanes) const {
1622 547 : if (out->isOffRamp()) {
1623 : return addedLanes;
1624 : }
1625 : NBNode* to = out->getToNode();
1626 : // check whether a right lane ends
1627 : if (to->getIncomingEdges().size() == 1
1628 539 : && to->getOutgoingEdges().size() == 1) {
1629 : int inOffset, inEnd, outOffset, outEnd, reduction;
1630 44 : to->getReduction(out, to->getOutgoingEdges()[0], inOffset, inEnd, outOffset, outEnd, reduction);
1631 :
1632 44 : if (reduction > 0) {
1633 8 : return reduction;
1634 : }
1635 : }
1636 : // check for the presence of right and left turns at the next intersection
1637 : int outLanesRight = 0;
1638 : int outLanesLeft = 0;
1639 : int outLanesStraight = 0;
1640 2366 : for (NBEdge* succ : to->getOutgoingEdges()) {
1641 1835 : if (out->isConnectedTo(succ)) {
1642 1699 : const int outOffset = MAX2(0, succ->getFirstNonPedestrianNonBicycleLaneIndex(FORWARD, true));
1643 1699 : const int usableLanes = succ->getNumLanes() - outOffset;
1644 1699 : LinkDirection dir = to->getDirection(out, succ);
1645 1699 : if (dir == LinkDirection::STRAIGHT) {
1646 492 : outLanesStraight += usableLanes;
1647 1207 : } else if (dir == LinkDirection::RIGHT || dir == LinkDirection::PARTRIGHT) {
1648 424 : outLanesRight += usableLanes;
1649 : } else {
1650 783 : outLanesLeft += usableLanes;
1651 : }
1652 : }
1653 : }
1654 531 : const int outOffset = MAX2(0, out->getFirstNonPedestrianNonBicycleLaneIndex(FORWARD, true));
1655 531 : const int outEnd = out->getFirstNonPedestrianLaneIndex(BACKWARD, true) + 1;
1656 531 : const int usableLanes = outEnd - outOffset;
1657 531 : int addedTurnLanes = MIN3(
1658 : addedLanes,
1659 : MAX2(0, usableLanes - outLanesStraight),
1660 : outLanesRight + outLanesLeft);
1661 : #ifdef DEBUG_CONNECTION_GUESSING
1662 : if (DEBUGCOND) {
1663 : std::cout << "out=" << out->getID() << " usableLanes=" << usableLanes << " addedTurnLanes=" << addedTurnLanes << " addedLanes=" << addedLanes << " outLanesStraight=" << outLanesStraight << " outLanesLeft=" << outLanesLeft << " outLanesRight=" << outLanesRight << "\n";
1664 : }
1665 : #endif
1666 531 : if (outLanesLeft == 0) {
1667 : return addedTurnLanes;
1668 : } else {
1669 415 : return MIN2(addedTurnLanes / 2, outLanesRight);
1670 : }
1671 : }
1672 :
1673 :
1674 : bool
1675 41 : NBNode::isLongEnough(NBEdge* out, double minLength) {
1676 : double seen = out->getLoadedLength();
1677 42 : while (seen < minLength) {
1678 : // advance along trivial continuations
1679 : if (out->getToNode()->getOutgoingEdges().size() != 1
1680 20 : || out->getToNode()->getIncomingEdges().size() != 1) {
1681 : return false;
1682 : } else {
1683 1 : out = out->getToNode()->getOutgoingEdges()[0];
1684 1 : seen += out->getLoadedLength();
1685 : }
1686 : }
1687 : return true;
1688 : }
1689 :
1690 :
1691 : void
1692 78405 : NBNode::getEdgesThatApproach(NBEdge* currentOutgoing, EdgeVector& approaching) {
1693 : // get the position of the node to get the approaching nodes of
1694 78405 : EdgeVector::const_iterator i = std::find(myAllEdges.begin(),
1695 : myAllEdges.end(), currentOutgoing);
1696 : // get the first possible approaching edge
1697 78405 : NBContHelper::nextCW(myAllEdges, i);
1698 : // go through the list of edges clockwise and add the edges
1699 : approaching.clear();
1700 426896 : for (; *i != currentOutgoing;) {
1701 : // check only incoming edges
1702 348491 : if ((*i)->getToNode() == this && (*i)->getTurnDestination() != currentOutgoing) {
1703 163968 : std::vector<int> connLanes = (*i)->getConnectionLanes(currentOutgoing);
1704 163968 : if (connLanes.size() != 0) {
1705 121216 : approaching.push_back(*i);
1706 : }
1707 163968 : }
1708 348491 : NBContHelper::nextCW(myAllEdges, i);
1709 : }
1710 78405 : }
1711 :
1712 :
1713 : void
1714 628 : NBNode::replaceOutgoing(NBEdge* which, NBEdge* by, int laneOff) {
1715 : // replace the edge in the list of outgoing nodes
1716 628 : EdgeVector::iterator i = std::find(myOutgoingEdges.begin(), myOutgoingEdges.end(), which);
1717 628 : if (i != myOutgoingEdges.end()) {
1718 628 : (*i) = by;
1719 628 : i = std::find(myAllEdges.begin(), myAllEdges.end(), which);
1720 628 : (*i) = by;
1721 : }
1722 : // replace the edge in connections of incoming edges
1723 1543 : for (i = myIncomingEdges.begin(); i != myIncomingEdges.end(); ++i) {
1724 915 : (*i)->replaceInConnections(which, by, laneOff);
1725 : }
1726 : // replace within the connetion prohibition dependencies
1727 628 : replaceInConnectionProhibitions(which, by, 0, laneOff);
1728 628 : }
1729 :
1730 :
1731 : void
1732 11 : NBNode::replaceOutgoing(const EdgeVector& which, NBEdge* by) {
1733 : // replace edges
1734 : int laneOff = 0;
1735 33 : for (EdgeVector::const_iterator i = which.begin(); i != which.end(); i++) {
1736 22 : replaceOutgoing(*i, by, laneOff);
1737 22 : laneOff += (*i)->getNumLanes();
1738 : }
1739 : // removed double occurrences
1740 11 : removeDoubleEdges();
1741 : // check whether this node belongs to a district and the edges
1742 : // must here be also remapped
1743 11 : if (myDistrict != nullptr) {
1744 0 : myDistrict->replaceOutgoing(which, by);
1745 : }
1746 11 : }
1747 :
1748 :
1749 : void
1750 6044 : NBNode::replaceIncoming(NBEdge* which, NBEdge* by, int laneOff) {
1751 : // replace the edge in the list of incoming nodes
1752 6044 : EdgeVector::iterator i = std::find(myIncomingEdges.begin(), myIncomingEdges.end(), which);
1753 6044 : if (i != myIncomingEdges.end()) {
1754 6044 : (*i) = by;
1755 6044 : i = std::find(myAllEdges.begin(), myAllEdges.end(), which);
1756 6044 : (*i) = by;
1757 : }
1758 : // replace within the connetion prohibition dependencies
1759 6044 : replaceInConnectionProhibitions(which, by, laneOff, 0);
1760 6044 : }
1761 :
1762 :
1763 : void
1764 11 : NBNode::replaceIncoming(const EdgeVector& which, NBEdge* by) {
1765 : // replace edges
1766 : int laneOff = 0;
1767 33 : for (EdgeVector::const_iterator i = which.begin(); i != which.end(); i++) {
1768 22 : replaceIncoming(*i, by, laneOff);
1769 22 : laneOff += (*i)->getNumLanes();
1770 : }
1771 : // removed double occurrences
1772 11 : removeDoubleEdges();
1773 : // check whether this node belongs to a district and the edges
1774 : // must here be also remapped
1775 11 : if (myDistrict != nullptr) {
1776 0 : myDistrict->replaceIncoming(which, by);
1777 : }
1778 11 : }
1779 :
1780 :
1781 :
1782 : void
1783 6672 : NBNode::replaceInConnectionProhibitions(NBEdge* which, NBEdge* by,
1784 : int whichLaneOff, int byLaneOff) {
1785 : // replace in keys
1786 : NBConnectionProhibits::iterator j = myBlockedConnections.begin();
1787 6872 : while (j != myBlockedConnections.end()) {
1788 : bool changed = false;
1789 200 : NBConnection c = (*j).first;
1790 200 : if (c.replaceFrom(which, whichLaneOff, by, byLaneOff)) {
1791 : changed = true;
1792 : }
1793 200 : if (c.replaceTo(which, whichLaneOff, by, byLaneOff)) {
1794 : changed = true;
1795 : }
1796 200 : if (changed) {
1797 17 : myBlockedConnections[c] = (*j).second;
1798 : myBlockedConnections.erase(j);
1799 : j = myBlockedConnections.begin();
1800 : } else {
1801 : j++;
1802 : }
1803 200 : }
1804 : // replace in values
1805 6770 : for (j = myBlockedConnections.begin(); j != myBlockedConnections.end(); j++) {
1806 : NBConnectionVector& prohibiting = (*j).second;
1807 322 : for (NBConnectionVector::iterator k = prohibiting.begin(); k != prohibiting.end(); k++) {
1808 : NBConnection& sprohibiting = *k;
1809 224 : sprohibiting.replaceFrom(which, whichLaneOff, by, byLaneOff);
1810 224 : sprohibiting.replaceTo(which, whichLaneOff, by, byLaneOff);
1811 : }
1812 : }
1813 6672 : }
1814 :
1815 :
1816 :
1817 : void
1818 1234 : NBNode::removeDoubleEdges() {
1819 : // check incoming
1820 2616 : for (int i = 0; myIncomingEdges.size() > 0 && i < (int)myIncomingEdges.size() - 1; i++) {
1821 1382 : int j = i + 1;
1822 3895 : while (j < (int)myIncomingEdges.size()) {
1823 2513 : if (myIncomingEdges[i] == myIncomingEdges[j]) {
1824 628 : myIncomingEdges.erase(myIncomingEdges.begin() + j);
1825 : } else {
1826 1885 : j++;
1827 : }
1828 : }
1829 : }
1830 : // check outgoing
1831 2582 : for (int i = 0; myOutgoingEdges.size() > 0 && i < (int)myOutgoingEdges.size() - 1; i++) {
1832 1348 : int j = i + 1;
1833 3600 : while (j < (int)myOutgoingEdges.size()) {
1834 2252 : if (myOutgoingEdges[i] == myOutgoingEdges[j]) {
1835 628 : myOutgoingEdges.erase(myOutgoingEdges.begin() + j);
1836 : } else {
1837 1624 : j++;
1838 : }
1839 : }
1840 : }
1841 : // check all
1842 4636 : for (int i = 0; myAllEdges.size() > 0 && i < (int)myAllEdges.size() - 1; i++) {
1843 3402 : int j = i + 1;
1844 13767 : while (j < (int)myAllEdges.size()) {
1845 10365 : if (myAllEdges[i] == myAllEdges[j]) {
1846 1256 : myAllEdges.erase(myAllEdges.begin() + j);
1847 : } else {
1848 9109 : j++;
1849 : }
1850 : }
1851 : }
1852 1234 : }
1853 :
1854 :
1855 : bool
1856 100035 : NBNode::hasIncoming(const NBEdge* const e) const {
1857 100035 : return std::find(myIncomingEdges.begin(), myIncomingEdges.end(), e) != myIncomingEdges.end();
1858 : }
1859 :
1860 :
1861 : bool
1862 14746 : NBNode::hasOutgoing(const NBEdge* const e) const {
1863 14746 : return std::find(myOutgoingEdges.begin(), myOutgoingEdges.end(), e) != myOutgoingEdges.end();
1864 : }
1865 :
1866 :
1867 : NBEdge*
1868 19325 : NBNode::getOppositeIncoming(NBEdge* e) const {
1869 19325 : EdgeVector edges = myIncomingEdges;
1870 19325 : if (find(edges.begin(), edges.end(), e) != edges.end()) {
1871 19325 : edges.erase(find(edges.begin(), edges.end(), e));
1872 : }
1873 19325 : if (edges.size() == 0) {
1874 : return nullptr;
1875 : }
1876 19325 : if (e->getToNode() == this) {
1877 19325 : sort(edges.begin(), edges.end(), NBContHelper::edge_opposite_direction_sorter(e, this, false));
1878 : } else {
1879 0 : sort(edges.begin(), edges.end(), NBContHelper::edge_similar_direction_sorter(e));
1880 : }
1881 19325 : return edges[0];
1882 19325 : }
1883 :
1884 :
1885 : void
1886 199 : NBNode::addSortedLinkFoes(const NBConnection& mayDrive,
1887 : const NBConnection& mustStop) {
1888 398 : if (mayDrive.getFrom() == nullptr ||
1889 398 : mayDrive.getTo() == nullptr ||
1890 597 : mustStop.getFrom() == nullptr ||
1891 199 : mustStop.getTo() == nullptr) {
1892 :
1893 0 : WRITE_WARNING(TL("Something went wrong during the building of a connection..."));
1894 0 : return; // !!! mark to recompute connections
1895 : }
1896 199 : NBConnectionVector conn = myBlockedConnections[mustStop];
1897 199 : conn.push_back(mayDrive);
1898 199 : myBlockedConnections[mustStop] = conn;
1899 199 : }
1900 :
1901 :
1902 : NBEdge*
1903 266 : NBNode::getPossiblySplittedIncoming(const std::string& edgeid) {
1904 266 : int size = (int) edgeid.length();
1905 1042 : for (EdgeVector::iterator i = myIncomingEdges.begin(); i != myIncomingEdges.end(); i++) {
1906 1042 : std::string id = (*i)->getID();
1907 1042 : if (id.substr(0, size) == edgeid) {
1908 266 : return *i;
1909 : }
1910 : }
1911 : return nullptr;
1912 : }
1913 :
1914 :
1915 : NBEdge*
1916 266 : NBNode::getPossiblySplittedOutgoing(const std::string& edgeid) {
1917 266 : int size = (int) edgeid.length();
1918 605 : for (EdgeVector::iterator i = myOutgoingEdges.begin(); i != myOutgoingEdges.end(); i++) {
1919 549 : std::string id = (*i)->getID();
1920 549 : if (id.substr(0, size) == edgeid) {
1921 210 : return *i;
1922 : }
1923 : }
1924 : return nullptr;
1925 : }
1926 :
1927 :
1928 : void
1929 39180 : NBNode::removeEdge(NBEdge* edge, bool removeFromConnections) {
1930 39180 : EdgeVector::iterator i = std::find(myAllEdges.begin(), myAllEdges.end(), edge);
1931 39180 : if (i != myAllEdges.end()) {
1932 32478 : myAllEdges.erase(i);
1933 32478 : i = std::find(myOutgoingEdges.begin(), myOutgoingEdges.end(), edge);
1934 32478 : if (i != myOutgoingEdges.end()) {
1935 19030 : myOutgoingEdges.erase(i);
1936 : // potential self-loop
1937 19030 : i = std::find(myIncomingEdges.begin(), myIncomingEdges.end(), edge);
1938 19030 : if (i != myIncomingEdges.end()) {
1939 0 : myIncomingEdges.erase(i);
1940 : }
1941 : } else {
1942 13448 : i = std::find(myIncomingEdges.begin(), myIncomingEdges.end(), edge);
1943 13448 : if (i != myIncomingEdges.end()) {
1944 13448 : myIncomingEdges.erase(i);
1945 : } else {
1946 : // edge must have been either incoming or outgoing
1947 : assert(false);
1948 : }
1949 : }
1950 32478 : if (removeFromConnections) {
1951 60113 : for (i = myAllEdges.begin(); i != myAllEdges.end(); ++i) {
1952 34013 : (*i)->removeFromConnections(edge);
1953 : }
1954 : }
1955 : // invalidate controlled connections for loaded traffic light plans
1956 32478 : const bool incoming = edge->getToNode() == this;
1957 35998 : for (NBTrafficLightDefinition* const tld : myTrafficLights) {
1958 3520 : tld->replaceRemoved(edge, -1, nullptr, -1, incoming);
1959 : }
1960 : }
1961 39180 : }
1962 :
1963 :
1964 : Position
1965 0 : NBNode::getEmptyDir() const {
1966 : Position pos(0, 0);
1967 0 : for (const NBEdge* const in : myIncomingEdges) {
1968 0 : Position toAdd = in->getFromNode()->getPosition();
1969 : toAdd.sub(myPosition);
1970 0 : toAdd.norm2D();
1971 : pos.add(toAdd);
1972 : }
1973 0 : for (const NBEdge* const out : myOutgoingEdges) {
1974 0 : Position toAdd = out->getToNode()->getPosition();
1975 : toAdd.sub(myPosition);
1976 0 : toAdd.norm2D();
1977 : pos.add(toAdd);
1978 : }
1979 0 : pos.mul(-1. / (double)(myIncomingEdges.size() + myOutgoingEdges.size()));
1980 0 : if (pos.x() == 0. && pos.y() == 0.) {
1981 0 : pos = Position(1, 0);
1982 : }
1983 0 : pos.norm2D();
1984 0 : return pos;
1985 : }
1986 :
1987 :
1988 :
1989 : void
1990 0 : NBNode::invalidateIncomingConnections(bool reallowSetting) {
1991 0 : for (EdgeVector::const_iterator i = myIncomingEdges.begin(); i != myIncomingEdges.end(); i++) {
1992 0 : (*i)->invalidateConnections(reallowSetting);
1993 : }
1994 0 : }
1995 :
1996 :
1997 : void
1998 34 : NBNode::invalidateOutgoingConnections(bool reallowSetting) {
1999 119 : for (EdgeVector::const_iterator i = myOutgoingEdges.begin(); i != myOutgoingEdges.end(); i++) {
2000 85 : (*i)->invalidateConnections(reallowSetting);
2001 : }
2002 34 : }
2003 :
2004 :
2005 : bool
2006 205329 : NBNode::mustBrake(const NBEdge* const from, const NBEdge* const to, int fromLane, int toLane, bool includePedCrossings) const {
2007 : // unregulated->does not need to brake
2008 205329 : if (myRequest == nullptr) {
2009 : return false;
2010 : }
2011 : // vehicles which do not have a following lane must always decelerate to the end
2012 204441 : if (to == nullptr) {
2013 : return true;
2014 : }
2015 : // maybe we need to brake due to entering a bidi-edge
2016 204441 : if (to->isBidiEdge() && !from->isBidiEdge()) {
2017 : return true;
2018 : }
2019 : // check whether any other connection on this node prohibits this connection
2020 204391 : return myRequest->mustBrake(from, to, fromLane, toLane, includePedCrossings);
2021 : }
2022 :
2023 : bool
2024 6728 : NBNode::mustBrakeForCrossing(const NBEdge* const from, const NBEdge* const to, const NBNode::Crossing& crossing) const {
2025 6728 : return NBRequest::mustBrakeForCrossing(this, from, to, crossing);
2026 : }
2027 :
2028 : bool
2029 17179 : NBNode::brakeForCrossingOnExit(const NBEdge* to) const {
2030 : // code is called for connections exiting after an internal junction.
2031 : // Therefore we can assume that the connection is turning and do not check
2032 : // for direction or crossing priority anymore.
2033 19856 : for (auto& c : myCrossings) {
2034 4051 : if (std::find(c->edges.begin(), c->edges.end(), to) != c->edges.end()) {
2035 : return true;
2036 : }
2037 : }
2038 : return false;
2039 : }
2040 :
2041 :
2042 : bool
2043 3955820 : NBNode::rightTurnConflict(const NBEdge* from, const NBEdge* to, int fromLane,
2044 : const NBEdge* prohibitorFrom, const NBEdge* prohibitorTo, int prohibitorFromLane) {
2045 3955820 : if (from != prohibitorFrom) {
2046 : return false;
2047 : }
2048 1163372 : if (from->isTurningDirectionAt(to)
2049 1163372 : || prohibitorFrom->isTurningDirectionAt(prohibitorTo)) {
2050 : // XXX should warn if there are any non-turning connections left of this
2051 368029 : return false;
2052 : }
2053 : // conflict if to is between prohibitorTo and from when going clockwise
2054 795343 : if (to->getStartAngle() == prohibitorTo->getStartAngle()) {
2055 : // reduce rounding errors
2056 : return false;
2057 : }
2058 434144 : const LinkDirection d1 = from->getToNode()->getDirection(from, to);
2059 : // must be a right turn to qualify as rightTurnConflict
2060 434144 : if (d1 == LinkDirection::STRAIGHT) {
2061 : // no conflict for straight going connections
2062 : // XXX actually this should check the main direction (which could also
2063 : // be a turn)
2064 : return false;
2065 : } else {
2066 323255 : const LinkDirection d2 = prohibitorFrom->getToNode()->getDirection(prohibitorFrom, prohibitorTo);
2067 : /* std::cout
2068 : << "from=" << from->getID() << " to=" << to->getID() << " fromLane=" << fromLane
2069 : << " pFrom=" << prohibitorFrom->getID() << " pTo=" << prohibitorTo->getID() << " pFromLane=" << prohibitorFromLane
2070 : << " d1=" << toString(d1) << " d2=" << toString(d2)
2071 : << "\n"; */
2072 : bool flip = false;
2073 323255 : if (d1 == LinkDirection::LEFT || d1 == LinkDirection::PARTLEFT) {
2074 : // check for leftTurnConflicht
2075 : flip = !flip;
2076 153244 : if (d2 == LinkDirection::RIGHT || d2 == LinkDirection::PARTRIGHT) {
2077 : // assume that the left-turning bicycle goes straight at first
2078 : // and thus gets precedence over a right turning vehicle
2079 : return false;
2080 : }
2081 : }
2082 261339 : if ((!flip && fromLane <= prohibitorFromLane) ||
2083 94154 : (flip && fromLane >= prohibitorFromLane)) {
2084 : return false;
2085 : }
2086 4709 : const double toAngleAtNode = fmod(to->getStartAngle() + 180, (double)360.0);
2087 4709 : const double prohibitorToAngleAtNode = fmod(prohibitorTo->getStartAngle() + 180, (double)360.0);
2088 4709 : return (flip != (GeomHelper::getCWAngleDiff(from->getEndAngle(), toAngleAtNode) <
2089 4709 : GeomHelper::getCWAngleDiff(from->getEndAngle(), prohibitorToAngleAtNode)));
2090 : }
2091 : }
2092 :
2093 : bool
2094 281 : NBNode::mergeConflictYields(const NBEdge* from, int fromLane, int fromLaneFoe, NBEdge* to, int toLane) const {
2095 281 : if (myRequest == nullptr) {
2096 : return false;
2097 : }
2098 281 : const NBEdge::Connection& con = from->getConnection(fromLane, to, toLane);
2099 281 : const NBEdge::Connection& prohibitorCon = from->getConnection(fromLaneFoe, to, toLane);
2100 281 : return myRequest->mergeConflict(from, con, from, prohibitorCon, false);
2101 : }
2102 :
2103 :
2104 : bool
2105 1516092 : NBNode::mergeConflict(const NBEdge* from, const NBEdge::Connection& con,
2106 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon, bool foes) const {
2107 1516092 : if (myRequest == nullptr) {
2108 : return false;
2109 : }
2110 1467144 : return myRequest->mergeConflict(from, con, prohibitorFrom, prohibitorCon, foes);
2111 : }
2112 :
2113 : bool
2114 758046 : NBNode::bidiConflict(const NBEdge* from, const NBEdge::Connection& con,
2115 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon, bool foes) const {
2116 758046 : if (myRequest == nullptr) {
2117 : return false;
2118 : }
2119 733572 : return myRequest->bidiConflict(from, con, prohibitorFrom, prohibitorCon, foes);
2120 : }
2121 :
2122 : bool
2123 1338720 : NBNode::turnFoes(const NBEdge* from, const NBEdge* to, int fromLane,
2124 : const NBEdge* from2, const NBEdge* to2, int fromLane2,
2125 : bool lefthand) const {
2126 : UNUSED_PARAMETER(lefthand);
2127 1338720 : if (from != from2 || to == to2 || fromLane == fromLane2) {
2128 : return false;
2129 : }
2130 67403 : if (from->isTurningDirectionAt(to)
2131 67403 : || from2->isTurningDirectionAt(to2)) {
2132 : // XXX should warn if there are any non-turning connections left of this
2133 21930 : return false;
2134 : }
2135 : bool result = false;
2136 45473 : EdgeVector::const_iterator it = std::find(myAllEdges.begin(), myAllEdges.end(), from);
2137 45473 : if (fromLane < fromLane2) {
2138 : // conflict if 'to' comes before 'to2' going clockwise starting at 'from'
2139 97756 : while (*it != to2) {
2140 74974 : if (*it == to) {
2141 : result = true;
2142 : }
2143 74974 : NBContHelper::nextCW(myAllEdges, it);
2144 : }
2145 : } else {
2146 : // conflict if 'to' comes before 'to2' going counter-clockwise starting at 'from'
2147 62642 : while (*it != to2) {
2148 39951 : if (*it == to) {
2149 : result = true;
2150 : }
2151 39951 : NBContHelper::nextCCW(myAllEdges, it);
2152 : }
2153 : }
2154 : /*
2155 : if (result) {
2156 : std::cout << "turnFoes node=" << getID()
2157 : << " from=" << from->getLaneID(fromLane)
2158 : << " to=" << to->getID()
2159 : << " from2=" << from2->getLaneID(fromLane2)
2160 : << " to2=" << to2->getID()
2161 : << "\n";
2162 : }
2163 : */
2164 : return result;
2165 : }
2166 :
2167 :
2168 : bool
2169 4812 : NBNode::isLeftMover(const NBEdge* const from, const NBEdge* const to) const {
2170 : // when the junction has only one incoming edge, there are no
2171 : // problems caused by left blockings
2172 4812 : if (myIncomingEdges.size() == 1 || myOutgoingEdges.size() == 1) {
2173 : return false;
2174 : }
2175 4764 : double fromAngle = from->getAngleAtNode(this);
2176 4764 : double toAngle = to->getAngleAtNode(this);
2177 4764 : double cw = GeomHelper::getCWAngleDiff(fromAngle, toAngle);
2178 4764 : double ccw = GeomHelper::getCCWAngleDiff(fromAngle, toAngle);
2179 4764 : std::vector<NBEdge*>::const_iterator i = std::find(myAllEdges.begin(), myAllEdges.end(), from);
2180 : do {
2181 14292 : NBContHelper::nextCW(myAllEdges, i);
2182 19056 : } while ((!hasOutgoing(*i) || from->isTurningDirectionAt(*i)) && *i != from);
2183 4764 : return cw < ccw && (*i) == to && myOutgoingEdges.size() > 2;
2184 : }
2185 :
2186 :
2187 : bool
2188 1394177 : NBNode::forbids(const NBEdge* const possProhibitorFrom, const NBEdge* const possProhibitorTo,
2189 : const NBEdge* const possProhibitedFrom, const NBEdge* const possProhibitedTo,
2190 : bool regardNonSignalisedLowerPriority) const {
2191 1394177 : return myRequest != nullptr && myRequest->forbids(possProhibitorFrom, possProhibitorTo,
2192 : possProhibitedFrom, possProhibitedTo,
2193 1394177 : regardNonSignalisedLowerPriority);
2194 : }
2195 :
2196 :
2197 : bool
2198 1437710 : NBNode::foes(const NBEdge* const from1, const NBEdge* const to1,
2199 : const NBEdge* const from2, const NBEdge* const to2) const {
2200 1437710 : return myRequest != nullptr && myRequest->foes(from1, to1, from2, to2);
2201 : }
2202 :
2203 :
2204 : void
2205 0 : NBNode::remapRemoved(NBTrafficLightLogicCont& tc,
2206 : NBEdge* removed, const EdgeVector& incoming,
2207 : const EdgeVector& outgoing) {
2208 : assert(find(incoming.begin(), incoming.end(), removed) == incoming.end());
2209 : bool changed = true;
2210 0 : while (changed) {
2211 : changed = false;
2212 : NBConnectionProhibits blockedConnectionsTmp = myBlockedConnections;
2213 : NBConnectionProhibits blockedConnectionsNew;
2214 : // remap in connections
2215 0 : for (NBConnectionProhibits::iterator i = blockedConnectionsTmp.begin(); i != blockedConnectionsTmp.end(); i++) {
2216 0 : const NBConnection& blocker = (*i).first;
2217 0 : const NBConnectionVector& blocked = (*i).second;
2218 : // check the blocked connections first
2219 : // check whether any of the blocked must be changed
2220 : bool blockedChanged = false;
2221 : NBConnectionVector newBlocked;
2222 : NBConnectionVector::const_iterator j;
2223 0 : for (j = blocked.begin(); j != blocked.end(); j++) {
2224 : const NBConnection& sblocked = *j;
2225 0 : if (sblocked.getFrom() == removed || sblocked.getTo() == removed) {
2226 : blockedChanged = true;
2227 : }
2228 : }
2229 : // adapt changes if so
2230 0 : for (j = blocked.begin(); blockedChanged && j != blocked.end(); j++) {
2231 : const NBConnection& sblocked = *j;
2232 0 : if (sblocked.getFrom() == removed && sblocked.getTo() == removed) {
2233 : /* for(EdgeVector::const_iterator k=incoming.begin(); k!=incoming.end(); k++) {
2234 : !!! newBlocked.push_back(NBConnection(*k, *k));
2235 : }*/
2236 0 : } else if (sblocked.getFrom() == removed) {
2237 : assert(sblocked.getTo() != removed);
2238 0 : for (EdgeVector::const_iterator k = incoming.begin(); k != incoming.end(); k++) {
2239 0 : newBlocked.push_back(NBConnection(*k, sblocked.getTo()));
2240 : }
2241 0 : } else if (sblocked.getTo() == removed) {
2242 : assert(sblocked.getFrom() != removed);
2243 0 : for (EdgeVector::const_iterator k = outgoing.begin(); k != outgoing.end(); k++) {
2244 0 : newBlocked.push_back(NBConnection(sblocked.getFrom(), *k));
2245 : }
2246 : } else {
2247 0 : newBlocked.push_back(NBConnection(sblocked.getFrom(), sblocked.getTo()));
2248 : }
2249 : }
2250 0 : if (blockedChanged) {
2251 0 : blockedConnectionsNew[blocker] = newBlocked;
2252 : changed = true;
2253 : }
2254 : // if the blocked were kept
2255 : else {
2256 0 : if (blocker.getFrom() == removed && blocker.getTo() == removed) {
2257 : changed = true;
2258 : /* for(EdgeVector::const_iterator k=incoming.begin(); k!=incoming.end(); k++) {
2259 : !!! blockedConnectionsNew[NBConnection(*k, *k)] = blocked;
2260 : }*/
2261 0 : } else if (blocker.getFrom() == removed) {
2262 : assert(blocker.getTo() != removed);
2263 : changed = true;
2264 0 : for (EdgeVector::const_iterator k = incoming.begin(); k != incoming.end(); k++) {
2265 0 : blockedConnectionsNew[NBConnection(*k, blocker.getTo())] = blocked;
2266 : }
2267 0 : } else if (blocker.getTo() == removed) {
2268 : assert(blocker.getFrom() != removed);
2269 : changed = true;
2270 0 : for (EdgeVector::const_iterator k = outgoing.begin(); k != outgoing.end(); k++) {
2271 0 : blockedConnectionsNew[NBConnection(blocker.getFrom(), *k)] = blocked;
2272 : }
2273 : } else {
2274 0 : blockedConnectionsNew[blocker] = blocked;
2275 : }
2276 : }
2277 0 : }
2278 : myBlockedConnections = blockedConnectionsNew;
2279 : }
2280 : // remap in traffic lights
2281 0 : tc.remapRemoved(removed, incoming, outgoing);
2282 0 : }
2283 :
2284 :
2285 : NBEdge*
2286 3206946 : NBNode::getNextCompatibleOutgoing(const NBEdge* incoming, SVCPermissions vehPerm, EdgeVector::const_iterator itOut, bool clockwise) const {
2287 3206946 : EdgeVector::const_iterator i = itOut;
2288 6673352 : while (*i != incoming) {
2289 5300022 : if (clockwise) {
2290 2263175 : NBContHelper::nextCW(myAllEdges, i);
2291 : } else {
2292 3036847 : NBContHelper::nextCCW(myAllEdges, i);
2293 : }
2294 5300022 : if ((*i)->getFromNode() != this) {
2295 : // only look for outgoing edges
2296 : // @note we use myAllEdges to stop at the incoming edge
2297 3327723 : continue;
2298 : }
2299 1972299 : if (incoming->isTurningDirectionAt(*i)) {
2300 : return nullptr;
2301 : }
2302 985323 : if ((vehPerm & (*i)->getPermissions()) != 0 || vehPerm == 0) {
2303 846640 : return *i;
2304 : }
2305 : }
2306 : return nullptr;
2307 : }
2308 :
2309 :
2310 : bool
2311 914828 : NBNode::isStraighter(const NBEdge* const incoming, const double angle, const SVCPermissions vehPerm, const int modeLanes, const NBEdge* const candidate) const {
2312 914828 : if (candidate != nullptr) {
2313 634335 : const double candAngle = NBHelpers::normRelAngle(incoming->getAngleAtNode(this), candidate->getAngleAtNode(this));
2314 : // they are too similar it does not matter
2315 634335 : if (fabs(angle - candAngle) < 5.) {
2316 : return false;
2317 : }
2318 : // the other edge is at least 5 degree straighter
2319 617238 : if (fabs(candAngle) < fabs(angle) - 5.) {
2320 : return true;
2321 : }
2322 547766 : if (fabs(angle) < fabs(candAngle) - 5.) {
2323 : return false;
2324 : }
2325 24603 : if (fabs(candAngle) < 44.) {
2326 : // the lane count for the same modes is larger
2327 23441 : const int candModeLanes = candidate->getNumLanesThatAllow(vehPerm);
2328 23441 : if (candModeLanes > modeLanes) {
2329 : return true;
2330 : }
2331 21739 : if (candModeLanes < modeLanes) {
2332 : return false;
2333 : }
2334 : // we would create a left turn
2335 18331 : if (candAngle < 0 && angle > 0) {
2336 : return true;
2337 : }
2338 : if (angle < 0 && candAngle > 0) {
2339 : return false;
2340 : }
2341 : }
2342 : }
2343 : return false;
2344 : }
2345 :
2346 : EdgeVector
2347 8254 : NBNode::getPassengerEdges(bool incoming) const {
2348 : EdgeVector result;
2349 25526 : for (NBEdge* e : (incoming ? myIncomingEdges : myOutgoingEdges)) {
2350 17272 : if ((e->getPermissions() & SVC_PASSENGER) != 0) {
2351 12055 : result.push_back(e);
2352 : }
2353 : }
2354 8254 : return result;
2355 0 : }
2356 :
2357 : LinkDirection
2358 6903270 : NBNode::getDirection(const NBEdge* const incoming, const NBEdge* const outgoing, bool leftHand) const {
2359 : // ok, no connection at all -> dead end
2360 6903270 : if (outgoing == nullptr) {
2361 : return LinkDirection::NODIR;
2362 : }
2363 : assert(incoming->getToNode() == this);
2364 : assert(outgoing->getFromNode() == this);
2365 6903269 : if (incoming->getJunctionPriority(this) == NBEdge::JunctionPriority::ROUNDABOUT && outgoing->getJunctionPriority(this) == NBEdge::JunctionPriority::ROUNDABOUT) {
2366 : return LinkDirection::STRAIGHT;
2367 : }
2368 : // turning direction
2369 6894272 : if (incoming->isTurningDirectionAt(outgoing)) {
2370 1245786 : if (isExplicitRailNoBidi(incoming, outgoing)) {
2371 : return LinkDirection::STRAIGHT;
2372 : }
2373 2490417 : return leftHand ? LinkDirection::TURN_LEFTHAND : LinkDirection::TURN;
2374 : }
2375 : // get the angle between incoming/outgoing at the junction
2376 5648486 : const double angle = NBHelpers::normRelAngle(incoming->getAngleAtNode(this), outgoing->getAngleAtNode(this));
2377 : // ok, should be a straight connection
2378 5648486 : EdgeVector::const_iterator itOut = std::find(myAllEdges.begin(), myAllEdges.end(), outgoing);
2379 5648486 : SVCPermissions vehPerm = incoming->getPermissions() & outgoing->getPermissions();
2380 5648486 : if (vehPerm != SVC_PEDESTRIAN) {
2381 5585562 : vehPerm &= ~SVC_PEDESTRIAN;
2382 : }
2383 5648486 : const int modeLanes = outgoing->getNumLanesThatAllow(vehPerm);
2384 5648486 : if (fabs(angle) < 44.) {
2385 2106693 : if (fabs(angle) > 6.) {
2386 475301 : if (isStraighter(incoming, angle, vehPerm, modeLanes, getNextCompatibleOutgoing(incoming, vehPerm, itOut, true))) {
2387 70572 : return angle > 0 ? LinkDirection::PARTRIGHT : LinkDirection::PARTLEFT;
2388 : }
2389 439527 : if (isStraighter(incoming, angle, vehPerm, modeLanes, getNextCompatibleOutgoing(incoming, vehPerm, itOut, false))) {
2390 48054 : return angle > 0 ? LinkDirection::PARTRIGHT : LinkDirection::PARTLEFT;
2391 : }
2392 : }
2393 2024480 : if (angle > 0 && incoming->getJunctionPriority(this) == NBEdge::JunctionPriority::ROUNDABOUT) {
2394 2452 : return angle > 15 ? LinkDirection::RIGHT : LinkDirection::PARTRIGHT;
2395 : }
2396 2023177 : return LinkDirection::STRAIGHT;
2397 : }
2398 :
2399 3541793 : if (angle > 0) {
2400 : // check whether any other edge goes further to the right
2401 1908430 : if (angle > 90) {
2402 : return LinkDirection::RIGHT;
2403 : }
2404 1241999 : NBEdge* outCW = getNextCompatibleOutgoing(incoming, vehPerm, itOut, !leftHand);
2405 1241999 : if (outCW != nullptr) {
2406 : return LinkDirection::PARTRIGHT;
2407 : } else {
2408 : return LinkDirection::RIGHT;
2409 : }
2410 : } else {
2411 : // check whether any other edge goes further to the left
2412 1633363 : if (angle < -170 && incoming->getGeometry().reverse() == outgoing->getGeometry()) {
2413 1449 : if (isExplicitRailNoBidi(incoming, outgoing)) {
2414 : return LinkDirection::STRAIGHT;
2415 : }
2416 2890 : return leftHand ? LinkDirection::TURN_LEFTHAND : LinkDirection::TURN;
2417 1631914 : } else if (angle < -90) {
2418 : return LinkDirection::LEFT;
2419 : }
2420 1050119 : NBEdge* outCCW = getNextCompatibleOutgoing(incoming, vehPerm, itOut, leftHand);
2421 1050119 : if (outCCW != nullptr) {
2422 : return LinkDirection::PARTLEFT;
2423 : } else {
2424 : return LinkDirection::LEFT;
2425 : }
2426 : }
2427 : }
2428 :
2429 :
2430 : bool
2431 1247235 : NBNode::isExplicitRailNoBidi(const NBEdge* incoming, const NBEdge* outgoing) {
2432 : // assume explicit connections at sharp turn-arounds are either for reversal or due to a geometry glitch
2433 : // (but should not have been guessed)
2434 : // @note this function is also called from NBAlgorithms when there aren't any connections ready
2435 : return (incoming->getStep() >= NBEdge::EdgeBuildingStep::LANES2LANES_RECHECK
2436 1189163 : && isRailway(incoming->getPermissions())
2437 4061 : && isRailway(outgoing->getPermissions())
2438 1251110 : && incoming->getBidiEdge() != outgoing);
2439 : }
2440 :
2441 :
2442 : LinkState
2443 175904 : NBNode::getLinkState(const NBEdge* incoming, const NBEdge* outgoing, int fromLane, int toLane,
2444 : bool mayDefinitelyPass, const std::string& tlID) const {
2445 175904 : if (myType == SumoXMLNodeType::RAIL_CROSSING && isRailway(incoming->getPermissions())) {
2446 : return LINKSTATE_MAJOR; // the trains must run on time
2447 : }
2448 175624 : if (tlID != "") {
2449 21269 : if (getRightOfWay() == RightOfWay::ALLWAYSTOP) {
2450 : return LINKSTATE_ALLWAY_STOP;
2451 : }
2452 21094 : return mustBrake(incoming, outgoing, fromLane, toLane, true) ? LINKSTATE_TL_OFF_BLINKING : LINKSTATE_TL_OFF_NOSIGNAL;
2453 : }
2454 154355 : if (outgoing == nullptr) { // always off
2455 : return LINKSTATE_TL_OFF_NOSIGNAL;
2456 : }
2457 154355 : if ((myType == SumoXMLNodeType::RIGHT_BEFORE_LEFT || myType == SumoXMLNodeType::LEFT_BEFORE_RIGHT)
2458 154355 : && mustBrake(incoming, outgoing, fromLane, toLane, true)) {
2459 : return LINKSTATE_EQUAL; // all the same
2460 : }
2461 142040 : if (myType == SumoXMLNodeType::ALLWAY_STOP) {
2462 : return LINKSTATE_ALLWAY_STOP; // all drive, first one to arrive may drive first
2463 : }
2464 142024 : if (myType == SumoXMLNodeType::ZIPPER && zipperConflict(incoming, outgoing, fromLane, toLane)) {
2465 : return LINKSTATE_ZIPPER;
2466 : }
2467 : if (!mayDefinitelyPass
2468 141984 : && mustBrake(incoming, outgoing, fromLane, toLane, true)
2469 : // legacy mode
2470 65580 : && (!incoming->isInsideTLS() || getDirection(incoming, outgoing) != LinkDirection::STRAIGHT)
2471 : // avoid linkstate minor at pure railway nodes
2472 207571 : && !NBNodeTypeComputer::isRailwayNode(this)) {
2473 64646 : return myType == SumoXMLNodeType::PRIORITY_STOP && incoming->getJunctionPriority(this) == NBEdge::JunctionPriority::MINOR_ROAD ? LINKSTATE_STOP : LINKSTATE_MINOR; // minor road
2474 : }
2475 : // traffic lights are not regarded here
2476 : return LINKSTATE_MAJOR;
2477 : }
2478 :
2479 :
2480 : bool
2481 27 : NBNode::zipperConflict(const NBEdge* incoming, const NBEdge* outgoing, int fromLane, int toLane) const {
2482 27 : if (mustBrake(incoming, outgoing, fromLane, toLane, false)) {
2483 : // there should be another connection with the same target (not just some intersecting trajectories)
2484 33 : for (const NBEdge* in : getIncomingEdges()) {
2485 55 : for (const NBEdge::Connection& c : in->getConnections()) {
2486 43 : if ((in != incoming || c.fromLane != fromLane) && c.toEdge == outgoing && c.toLane == toLane) {
2487 : return true;
2488 : }
2489 : }
2490 : }
2491 : }
2492 : return false;
2493 : }
2494 :
2495 :
2496 : bool
2497 17227 : NBNode::checkIsRemovable() const {
2498 : std::string reason;
2499 34454 : return checkIsRemovableReporting(reason);
2500 : }
2501 :
2502 : bool
2503 17227 : NBNode::checkIsRemovableReporting(std::string& reason) const {
2504 17227 : if (getEdges().empty()) {
2505 : return true;
2506 : }
2507 : // check whether this node is included in a traffic light or crossing
2508 17227 : if (myTrafficLights.size() != 0) {
2509 : reason = "TLS";
2510 505 : return false;
2511 : }
2512 16722 : if (myType == SumoXMLNodeType::RAIL_SIGNAL) {
2513 : reason = "rail_signal";
2514 220 : return false;
2515 : }
2516 16502 : if (myCrossings.size() != 0) {
2517 : reason = "crossing";
2518 0 : return false;
2519 : }
2520 : EdgeVector::const_iterator i;
2521 : // one in, one out -> just a geometry ...
2522 16502 : if (myOutgoingEdges.size() == 1 && myIncomingEdges.size() == 1) {
2523 : // ... if types match ...
2524 4931 : if (!myIncomingEdges[0]->expandableBy(myOutgoingEdges[0], reason)) {
2525 2326 : reason = "edges incompatible: " + reason;
2526 2326 : return false;
2527 : }
2528 2605 : if (myIncomingEdges[0]->getTurnDestination(true) == myOutgoingEdges[0]) {
2529 : reason = "turnaround";
2530 30 : return false;
2531 : }
2532 : return true;
2533 : }
2534 : // two in, two out -> may be something else
2535 11571 : if (myOutgoingEdges.size() == 2 && myIncomingEdges.size() == 2) {
2536 : // check whether the origin nodes of the incoming edges differ
2537 : std::set<NBNode*> origSet;
2538 8508 : for (i = myIncomingEdges.begin(); i != myIncomingEdges.end(); i++) {
2539 5672 : origSet.insert((*i)->getFromNode());
2540 : }
2541 2836 : if (origSet.size() < 2) {
2542 : // overlapping case
2543 217 : if (myIncomingEdges[0]->getGeometry() == myIncomingEdges[1]->getGeometry() &&
2544 75 : myOutgoingEdges[0]->getGeometry() == myOutgoingEdges[1]->getGeometry()) {
2545 137 : return ((myIncomingEdges[0]->expandableBy(myOutgoingEdges[0], reason) &&
2546 67 : myIncomingEdges[1]->expandableBy(myOutgoingEdges[1], reason))
2547 71 : || (myIncomingEdges[0]->expandableBy(myOutgoingEdges[1], reason) &&
2548 1 : myIncomingEdges[1]->expandableBy(myOutgoingEdges[0], reason)));
2549 : }
2550 : }
2551 : // check whether this node is an intermediate node of
2552 : // a two-directional street
2553 5566 : for (i = myIncomingEdges.begin(); i != myIncomingEdges.end(); i++) {
2554 : // each of the edges must have an opposite direction edge
2555 4196 : NBEdge* opposite = (*i)->getTurnDestination(true);
2556 4196 : if (opposite != nullptr) {
2557 : // the other outgoing edges must be the continuation of the current
2558 3314 : NBEdge* continuation = opposite == myOutgoingEdges.front() ? myOutgoingEdges.back() : myOutgoingEdges.front();
2559 : // check whether the types allow joining
2560 3314 : if (!(*i)->expandableBy(continuation, reason)) {
2561 514 : reason = "edges incompatible: " + reason;
2562 514 : return false;
2563 : }
2564 : } else {
2565 : // ok, at least one outgoing edge is not an opposite
2566 : // of an incoming one
2567 : reason = "not opposites";
2568 : return false;
2569 : }
2570 : }
2571 : return true;
2572 : }
2573 : // ok, a real node
2574 : reason = "intersection";
2575 : return false;
2576 : }
2577 :
2578 :
2579 : std::vector<std::pair<NBEdge*, NBEdge*> >
2580 8521 : NBNode::getEdgesToJoin() const {
2581 : assert(checkIsRemovable());
2582 : std::vector<std::pair<NBEdge*, NBEdge*> > ret;
2583 : // one in, one out-case
2584 8521 : if (myOutgoingEdges.size() == 1 && myIncomingEdges.size() == 1) {
2585 2546 : ret.push_back(std::make_pair(myIncomingEdges[0], myOutgoingEdges[0]));
2586 2546 : return ret;
2587 : }
2588 5975 : if (myIncomingEdges.size() == 2 && myOutgoingEdges.size() == 2) {
2589 : // two in, two out-case
2590 1503 : if (myIncomingEdges[0]->getGeometry() == myIncomingEdges[1]->getGeometry() &&
2591 68 : myOutgoingEdges[0]->getGeometry() == myOutgoingEdges[1]->getGeometry()) {
2592 : // overlapping edges
2593 : std::string reason;
2594 68 : if (myIncomingEdges[0]->expandableBy(myOutgoingEdges[0], reason)) {
2595 67 : ret.push_back(std::make_pair(myIncomingEdges[0], myOutgoingEdges[0]));
2596 67 : ret.push_back(std::make_pair(myIncomingEdges[1], myOutgoingEdges[1]));
2597 : } else {
2598 1 : ret.push_back(std::make_pair(myIncomingEdges[0], myOutgoingEdges[1]));
2599 1 : ret.push_back(std::make_pair(myIncomingEdges[1], myOutgoingEdges[0]));
2600 : }
2601 : return ret;
2602 : }
2603 : }
2604 8641 : for (EdgeVector::const_iterator i = myIncomingEdges.begin(); i != myIncomingEdges.end(); i++) {
2605 : // join with the edge that is not a turning direction
2606 2734 : NBEdge* opposite = (*i)->getTurnDestination(true);
2607 : assert(opposite != 0);
2608 2734 : NBEdge* continuation = opposite == myOutgoingEdges.front() ? myOutgoingEdges.back() : myOutgoingEdges.front();
2609 2734 : ret.push_back(std::pair<NBEdge*, NBEdge*>(*i, continuation));
2610 : }
2611 : return ret;
2612 0 : }
2613 :
2614 :
2615 : const PositionVector&
2616 2375438 : NBNode::getShape() const {
2617 2375438 : return myPoly;
2618 : }
2619 :
2620 :
2621 : void
2622 35 : NBNode::setCustomShape(const PositionVector& shape) {
2623 : myPoly = shape;
2624 35 : myHaveCustomPoly = (myPoly.size() > 1);
2625 35 : if (myHaveCustomPoly) {
2626 34 : for (EdgeVector::iterator i = myAllEdges.begin(); i != myAllEdges.end(); i++) {
2627 0 : (*i)->resetNodeBorder(this);
2628 : }
2629 : }
2630 35 : }
2631 :
2632 :
2633 : NBEdge*
2634 136223 : NBNode::getConnectionTo(NBNode* n) const {
2635 347264 : for (NBEdge* e : myOutgoingEdges) {
2636 231948 : if (e->getToNode() == n && e->getPermissions() != 0) {
2637 : return e;
2638 : }
2639 : }
2640 : return nullptr;
2641 : }
2642 :
2643 :
2644 : bool
2645 0 : NBNode::isNearDistrict() const {
2646 0 : if (isDistrict()) {
2647 : return false;
2648 : }
2649 0 : for (const NBEdge* const t : getEdges()) {
2650 0 : const NBNode* const other = t->getToNode() == this ? t->getFromNode() : t->getToNode();
2651 0 : for (const NBEdge* const k : other->getEdges()) {
2652 0 : if (k->getFromNode()->isDistrict() || k->getToNode()->isDistrict()) {
2653 : return true;
2654 : }
2655 : }
2656 : }
2657 : return false;
2658 : }
2659 :
2660 :
2661 : bool
2662 0 : NBNode::isDistrict() const {
2663 0 : return myType == SumoXMLNodeType::DISTRICT;
2664 : }
2665 :
2666 :
2667 : int
2668 3373 : NBNode::guessCrossings() {
2669 : #ifdef DEBUG_PED_STRUCTURES
2670 : gDebugFlag1 = DEBUGCOND;
2671 : #endif
2672 : int numGuessed = 0;
2673 3373 : if (myCrossings.size() > 0 || myDiscardAllCrossings) {
2674 : // user supplied crossings, do not guess
2675 : return numGuessed;
2676 : }
2677 : DEBUGCOUT(gDebugFlag1, "guess crossings for " << getID() << "\n")
2678 3370 : EdgeVector allEdges = getEdgesSortedByAngleAtNodeCenter();
2679 : // check for pedestrial lanes going clockwise around the node
2680 : std::vector<std::pair<NBEdge*, bool> > normalizedLanes;
2681 15058 : for (EdgeVector::const_iterator it = allEdges.begin(); it != allEdges.end(); ++it) {
2682 11688 : NBEdge* edge = *it;
2683 : const std::vector<NBEdge::Lane>& lanes = edge->getLanes();
2684 11688 : if (edge->getFromNode() == this) {
2685 14349 : for (std::vector<NBEdge::Lane>::const_reverse_iterator it_l = lanes.rbegin(); it_l != lanes.rend(); ++it_l) {
2686 8505 : normalizedLanes.push_back(std::make_pair(edge, ((*it_l).permissions & SVC_PEDESTRIAN) != 0));
2687 : }
2688 : } else {
2689 14349 : for (std::vector<NBEdge::Lane>::const_iterator it_l = lanes.begin(); it_l != lanes.end(); ++it_l) {
2690 8505 : normalizedLanes.push_back(std::make_pair(edge, ((*it_l).permissions & SVC_PEDESTRIAN) != 0));
2691 : }
2692 : }
2693 : }
2694 : // do we even have a pedestrian lane?
2695 : int firstSidewalk = -1;
2696 5513 : for (int i = 0; i < (int)normalizedLanes.size(); ++i) {
2697 5159 : if (normalizedLanes[i].second) {
2698 : firstSidewalk = i;
2699 : break;
2700 : }
2701 : }
2702 : int hadCandidates = 0;
2703 : std::vector<int> connectedCandidates; // number of crossings that were built for each connected candidate
2704 3370 : if (firstSidewalk != -1) {
2705 : // rotate lanes to ensure that the first one allows pedestrians
2706 : std::vector<std::pair<NBEdge*, bool> > tmp;
2707 : copy(normalizedLanes.begin() + firstSidewalk, normalizedLanes.end(), std::back_inserter(tmp));
2708 : copy(normalizedLanes.begin(), normalizedLanes.begin() + firstSidewalk, std::back_inserter(tmp));
2709 3016 : normalizedLanes = tmp;
2710 : // find candidates
2711 : EdgeVector candidates;
2712 18802 : for (int i = 0; i < (int)normalizedLanes.size(); ++i) {
2713 15786 : NBEdge* edge = normalizedLanes[i].first;
2714 15786 : const bool allowsPed = normalizedLanes[i].second;
2715 : DEBUGCOUT(gDebugFlag1, " cands=" << toString(candidates) << " edge=" << edge->getID() << " allowsPed=" << allowsPed << "\n")
2716 15786 : if (!allowsPed && (candidates.size() == 0 || candidates.back() != edge)) {
2717 4118 : candidates.push_back(edge);
2718 11668 : } else if (allowsPed) {
2719 9813 : if (candidates.size() > 0) {
2720 1617 : if (hadCandidates > 0 || forbidsPedestriansAfter(normalizedLanes, i)) {
2721 1533 : hadCandidates++;
2722 1533 : const int n = checkCrossing(candidates);
2723 1533 : numGuessed += n;
2724 1533 : if (n > 0) {
2725 1327 : connectedCandidates.push_back(n);
2726 : }
2727 : }
2728 : candidates.clear();
2729 : }
2730 : }
2731 : }
2732 3016 : if (hadCandidates > 0 && candidates.size() > 0) {
2733 : // avoid wrapping around to the same sidewalk
2734 195 : hadCandidates++;
2735 195 : const int n = checkCrossing(candidates);
2736 195 : numGuessed += n;
2737 195 : if (n > 0) {
2738 154 : connectedCandidates.push_back(n);
2739 : }
2740 : }
2741 3016 : }
2742 : // Avoid duplicate crossing between the same pair of walkingareas
2743 : DEBUGCOUT(gDebugFlag1, " hadCandidates=" << hadCandidates << " connectedCandidates=" << toString(connectedCandidates) << "\n")
2744 3016 : if (hadCandidates == 2 && connectedCandidates.size() == 2) {
2745 : // One or both of them might be split: remove the one with less splits
2746 387 : if (connectedCandidates.back() <= connectedCandidates.front()) {
2747 378 : numGuessed -= connectedCandidates.back();
2748 378 : myCrossings.erase(myCrossings.end() - connectedCandidates.back(), myCrossings.end());
2749 : } else {
2750 9 : numGuessed -= connectedCandidates.front();
2751 9 : myCrossings.erase(myCrossings.begin(), myCrossings.begin() + connectedCandidates.front());
2752 : }
2753 : }
2754 3370 : std::sort(myCrossings.begin(), myCrossings.end(), NBNodesEdgesSorter::crossing_by_junction_angle_sorter(this, myAllEdges));
2755 : #ifdef DEBUG_PED_STRUCTURES
2756 : if (gDebugFlag1) {
2757 : std::cout << "guessedCrossings:\n";
2758 : for (auto& crossing : myCrossings) {
2759 : std::cout << " edges=" << toString(crossing->edges) << "\n";
2760 : }
2761 : }
2762 : #endif
2763 3370 : if (numGuessed > 0 && isSimpleContinuation(true, true)) {
2764 : // avoid narrow node shape when there is a crossing
2765 18 : computeNodeShape(-1);
2766 90 : for (NBEdge* e : myAllEdges) {
2767 72 : e->computeEdgeShape();
2768 : }
2769 : }
2770 : return numGuessed;
2771 3370 : }
2772 :
2773 :
2774 : int
2775 1920 : NBNode::checkCrossing(EdgeVector candidates, bool checkOnly) {
2776 : DEBUGCOUT(gDebugFlag1, "checkCrossing candidates=" << toString(candidates) << "\n")
2777 1920 : if (candidates.size() == 0) {
2778 : DEBUGCOUT(gDebugFlag1, "no crossing added (numCandidates=" << candidates.size() << ")\n")
2779 : return 0;
2780 : } else {
2781 : // check whether the edges may be part of a common crossing due to having similar angle
2782 : double prevAngle = -100000; // dummy
2783 5029 : for (int i = 0; i < (int)candidates.size(); ++i) {
2784 3356 : NBEdge* edge = candidates[i];
2785 3356 : double angle = edge->getCrossingAngle(this);
2786 : // edges should be sorted by angle but this only holds true approximately
2787 3356 : if (i > 0 && fabs(NBHelpers::relAngle(angle, prevAngle)) > EXTEND_CROSSING_ANGLE_THRESHOLD) {
2788 : DEBUGCOUT(gDebugFlag1, "no crossing added (found angle difference of " << fabs(NBHelpers::relAngle(angle, prevAngle)) << " at i=" << i << "\n")
2789 : return 0;
2790 : }
2791 8125 : if (!checkOnly && !isTLControlled() && myType != SumoXMLNodeType::RAIL_CROSSING && edge->getSpeed() > OptionsCont::getOptions().getFloat("crossings.guess.speed-threshold")) {
2792 : DEBUGCOUT(gDebugFlag1, "no crossing added (uncontrolled, edge with speed > " << edge->getSpeed() << ")\n")
2793 : return 0;
2794 : }
2795 : prevAngle = angle;
2796 : }
2797 1673 : if (candidates.size() == 1 || getType() == SumoXMLNodeType::RAIL_CROSSING) {
2798 540 : if (!checkOnly) {
2799 540 : addCrossing(candidates, NBEdge::UNSPECIFIED_WIDTH, isTLControlled());
2800 : DEBUGCOUT(gDebugFlag1, "adding crossing: " << toString(candidates) << "\n")
2801 : }
2802 540 : return 1;
2803 : } else {
2804 : // check for intermediate walking areas
2805 : prevAngle = -100000; // dummy
2806 3385 : for (EdgeVector::iterator it = candidates.begin(); it != candidates.end(); ++it) {
2807 2348 : double angle = (*it)->getCrossingAngle(this);
2808 2348 : if (it != candidates.begin()) {
2809 1215 : NBEdge* prev = *(it - 1);
2810 1215 : NBEdge* curr = *it;
2811 : Position prevPos, currPos;
2812 : int laneI;
2813 : // compute distance between candiate edges
2814 : double intermediateWidth = 0;
2815 1215 : if (prev->getToNode() == this) {
2816 1157 : laneI = prev->getNumLanes() - 1;
2817 1157 : prevPos = prev->getLanes()[laneI].shape[-1];
2818 : } else {
2819 : laneI = 0;
2820 58 : prevPos = prev->getLanes()[laneI].shape[0];
2821 : }
2822 1215 : intermediateWidth -= 0.5 * prev->getLaneWidth(laneI);
2823 1215 : if (curr->getFromNode() == this) {
2824 1151 : laneI = curr->getNumLanes() - 1;
2825 1151 : currPos = curr->getLanes()[laneI].shape[0];
2826 : } else {
2827 : laneI = 0;
2828 64 : currPos = curr->getLanes()[laneI].shape[-1];
2829 : }
2830 1215 : intermediateWidth -= 0.5 * curr->getLaneWidth(laneI);
2831 1215 : intermediateWidth += currPos.distanceTo2D(prevPos);
2832 : DEBUGCOUT(gDebugFlag1, " prevAngle=" << prevAngle << " angle=" << angle << " intermediateWidth=" << intermediateWidth << "\n")
2833 1215 : if (fabs(NBHelpers::relAngle(prevAngle, angle)) > SPLIT_CROSSING_ANGLE_THRESHOLD
2834 1215 : || (intermediateWidth > SPLIT_CROSSING_WIDTH_THRESHOLD)) {
2835 192 : return checkCrossing(EdgeVector(candidates.begin(), it), checkOnly)
2836 96 : + checkCrossing(EdgeVector(it, candidates.end()), checkOnly);
2837 : }
2838 : }
2839 : prevAngle = angle;
2840 : }
2841 1037 : if (!checkOnly) {
2842 1037 : addCrossing(candidates, NBEdge::UNSPECIFIED_WIDTH, isTLControlled());
2843 : DEBUGCOUT(gDebugFlag1, "adding crossing: " << toString(candidates) << "\n")
2844 : }
2845 1037 : return 1;
2846 : }
2847 : }
2848 : }
2849 :
2850 :
2851 : bool
2852 297 : NBNode::checkCrossingDuplicated(EdgeVector edges) {
2853 : // sort edge vector
2854 297 : std::sort(edges.begin(), edges.end());
2855 : // iterate over crossing to find a crossing with the same edges
2856 804 : for (auto& crossing : myCrossings) {
2857 : // sort edges of crossing before compare
2858 510 : EdgeVector edgesOfCrossing = crossing->edges;
2859 510 : std::sort(edgesOfCrossing.begin(), edgesOfCrossing.end());
2860 510 : if (edgesOfCrossing == edges) {
2861 : return true;
2862 : }
2863 510 : }
2864 : return false;
2865 : }
2866 :
2867 :
2868 : bool
2869 787 : NBNode::forbidsPedestriansAfter(std::vector<std::pair<NBEdge*, bool> > normalizedLanes, int startIndex) {
2870 2392 : for (int i = startIndex; i < (int)normalizedLanes.size(); ++i) {
2871 2308 : if (!normalizedLanes[i].second) {
2872 : return true;
2873 : }
2874 : }
2875 : return false;
2876 : }
2877 :
2878 :
2879 : void
2880 4130 : NBNode::buildCrossingsAndWalkingAreas() {
2881 4130 : buildCrossings();
2882 8260 : buildWalkingAreas(OptionsCont::getOptions().getInt("junctions.corner-detail"),
2883 4130 : OptionsCont::getOptions().getFloat("walkingareas.join-dist"));
2884 4130 : buildCrossingOutlines();
2885 : // ensure that all crossings are properly connected
2886 4130 : bool recheck = myCrossings.size() > 0;
2887 4936 : while (recheck) {
2888 : recheck = false;
2889 : std::set<std::string> waIDs;
2890 : int numSidewalks = 0;
2891 3052 : for (WalkingArea& wa : myWalkingAreas) {
2892 2246 : waIDs.insert(wa.id);
2893 2246 : numSidewalks += (int)(wa.prevSidewalks.size() + wa.nextSidewalks.size());
2894 : }
2895 806 : if (numSidewalks < 2) {
2896 : // all crossings are invalid if there are fewer than 2 sidewalks involved
2897 : waIDs.clear();
2898 : }
2899 2458 : for (auto& crossing : myCrossings) {
2900 1652 : if (waIDs.count(crossing->prevWalkingArea) == 0 || waIDs.count(crossing->nextWalkingArea) == 0 || !crossing->valid) {
2901 40 : if (crossing->valid) {
2902 30 : WRITE_WARNINGF(TL("Discarding invalid crossing '%' at junction '%' with edges [%] (no walkingarea found)."),
2903 : crossing->id, getID(), toString(crossing->edges));
2904 : recheck = true;
2905 : }
2906 151 : for (auto waIt = myWalkingAreas.begin(); waIt != myWalkingAreas.end();) {
2907 : WalkingArea& wa = *waIt;
2908 111 : std::vector<std::string>::iterator it_nc = std::find(wa.nextCrossings.begin(), wa.nextCrossings.end(), crossing->id);
2909 111 : if (it_nc != wa.nextCrossings.end()) {
2910 11 : wa.nextCrossings.erase(it_nc);
2911 : }
2912 111 : if (wa.prevSidewalks.size() + wa.nextSidewalks.size() + wa.nextCrossings.size() + wa.prevCrossings.size() < 2) {
2913 9 : waIt = myWalkingAreas.erase(waIt);
2914 : recheck = true;
2915 : } else {
2916 : waIt++;
2917 : }
2918 : }
2919 40 : crossing->valid = false;
2920 40 : crossing->prevWalkingArea = "";
2921 40 : crossing->nextWalkingArea = "";
2922 : }
2923 : }
2924 : }
2925 4130 : }
2926 :
2927 :
2928 : std::vector<NBNode::Crossing*>
2929 987075 : NBNode::getCrossings() const {
2930 : std::vector<Crossing*> result;
2931 1257547 : for (auto& c : myCrossings) {
2932 270472 : if (c->valid) {
2933 267434 : result.push_back(c.get());
2934 : }
2935 : }
2936 : //if (myCrossings.size() > 0) {
2937 : // std::cout << "valid crossings at " << getID() << "\n";
2938 : // for (std::vector<NBNode::Crossing*>::const_iterator it = result.begin(); it != result.end(); ++it) {
2939 : // std::cout << " " << toString((*it)->edges) << "\n";
2940 : // }
2941 : //}
2942 987075 : return result;
2943 0 : }
2944 :
2945 :
2946 : void
2947 23304 : NBNode::discardAllCrossings(bool rejectAll) {
2948 : myCrossings.clear();
2949 : // also discard all further crossings
2950 23304 : if (rejectAll) {
2951 1 : myDiscardAllCrossings = true;
2952 : }
2953 23304 : }
2954 :
2955 :
2956 : void
2957 46632 : NBNode::discardWalkingareas() {
2958 : myWalkingAreas.clear();
2959 46632 : }
2960 :
2961 :
2962 : double
2963 27468 : NBNode::buildInnerEdges() {
2964 : // myDisplacementError is computed during this operation. reset first
2965 27468 : myDisplacementError = 0.;
2966 : // build inner edges for vehicle movements across the junction
2967 : int noInternalNoSplits = 0;
2968 75575 : for (const NBEdge* const edge : myIncomingEdges) {
2969 143958 : for (const NBEdge::Connection& con : edge->getConnections()) {
2970 95851 : if (con.toEdge == nullptr) {
2971 0 : continue;
2972 : }
2973 95851 : noInternalNoSplits++;
2974 : }
2975 : }
2976 27468 : int lno = 0;
2977 27468 : int splitNo = 0;
2978 : double maxCrossingSeconds = 0.;
2979 75575 : for (NBEdge* const edge : myIncomingEdges) {
2980 48107 : maxCrossingSeconds = MAX2(maxCrossingSeconds, edge->buildInnerEdges(*this, noInternalNoSplits, lno, splitNo));
2981 : }
2982 27468 : return maxCrossingSeconds;
2983 : }
2984 :
2985 :
2986 : int
2987 4130 : NBNode::buildCrossings() {
2988 : #ifdef DEBUG_PED_STRUCTURES
2989 : gDebugFlag1 = DEBUGCOND;
2990 : #endif
2991 : DEBUGCOUT(gDebugFlag1, "build crossings for " << getID() << ":\n")
2992 4130 : if (myDiscardAllCrossings) {
2993 : myCrossings.clear();
2994 : }
2995 : int index = 0;
2996 8260 : const double defaultWidth = OptionsCont::getOptions().getFloat("default.crossing-width");
2997 5744 : for (auto& c : myCrossings) {
2998 1614 : c->valid = true;
2999 1614 : if (!isTLControlled()) {
3000 981 : c->tlID = ""; // reset for Netedit, set via setCrossingTLIndices()
3001 : }
3002 4842 : c->id = ":" + getID() + "_c" + toString(index++);
3003 1614 : c->width = (c->customWidth == NBEdge::UNSPECIFIED_WIDTH) ? defaultWidth : c->customWidth;
3004 : // reset fields, so repeated computation (Netedit) will successfully perform the checks
3005 : // in buildWalkingAreas (split crossings) and buildInnerEdges (sanity check)
3006 1614 : c->nextWalkingArea = "";
3007 1614 : c->prevWalkingArea = "";
3008 : EdgeVector& edges = c->edges;
3009 : DEBUGCOUT(gDebugFlag1, " crossing=" << c->id << " edges=" << toString(edges))
3010 : // sorting the edges in the right way is imperative. We want to sort
3011 : // them by getAngleAtNodeToCenter() but need to be extra carefull to avoid wrapping around 0 somewhere in between
3012 1614 : std::sort(edges.begin(), edges.end(), NBContHelper::edge_by_angle_to_nodeShapeCentroid_sorter(this));
3013 : DEBUGCOUT(gDebugFlag1, " sortedEdges=" << toString(edges) << "\n")
3014 : // rotate the edges so that the largest relative angle difference comes at the end
3015 : std::vector<double> rawAngleDiffs;
3016 : double maxAngleDiff = 0;
3017 : int maxAngleDiffIndex = 0; // index before maxDist
3018 4390 : for (int i = 0; i < (int) edges.size(); i++) {
3019 2776 : double diff = NBHelpers::relAngle(edges[i]->getAngleAtNodeToCenter(this),
3020 2776 : edges[(i + 1) % edges.size()]->getAngleAtNodeToCenter(this));
3021 2776 : if (diff < 0) {
3022 1061 : diff += 360;
3023 : }
3024 2776 : const double rawDiff = NBHelpers::relAngle(
3025 : edges[i]->getAngleAtNodeNormalized(this),
3026 2776 : edges[(i + 1) % edges.size()]->getAngleAtNodeNormalized(this));
3027 2776 : rawAngleDiffs.push_back(fabs(rawDiff));
3028 :
3029 : DEBUGCOUT(gDebugFlag1, " i=" << i << " a1=" << edges[i]->getAngleAtNodeToCenter(this) << " a2=" << edges[(i + 1) % edges.size()]->getAngleAtNodeToCenter(this) << " diff=" << diff << "\n")
3030 2776 : if (diff > maxAngleDiff) {
3031 : maxAngleDiff = diff;
3032 : maxAngleDiffIndex = i;
3033 : }
3034 : }
3035 1614 : if (maxAngleDiff > 2 && maxAngleDiff < 360 - 2) {
3036 : // if the angle differences is too small, we better not rotate
3037 1007 : std::rotate(edges.begin(), edges.begin() + (maxAngleDiffIndex + 1) % edges.size(), edges.end());
3038 : DEBUGCOUT(gDebugFlag1, " rotatedEdges=" << toString(edges))
3039 : }
3040 : bool diagonalCrossing = false;
3041 1614 : std::sort(rawAngleDiffs.begin(), rawAngleDiffs.end());
3042 1614 : if (rawAngleDiffs.size() >= 2 && rawAngleDiffs[rawAngleDiffs.size() - 2] > 30) {
3043 : diagonalCrossing = true;
3044 : #ifdef DEBUG_PED_STRUCTURES
3045 : if (gDebugFlag1) {
3046 : std::cout << " detected pedScramble " << c->id << " edges=" << toString(edges) << " rawDiffs=" << toString(rawAngleDiffs) << "\n";
3047 : for (auto e : edges) {
3048 : std::cout << " e=" << e->getID()
3049 : << " aC=" << e->getAngleAtNodeToCenter(this)
3050 : << " a=" << e->getAngleAtNode(this)
3051 : << " aN=" << e->getAngleAtNodeNormalized(this)
3052 : << "\n";
3053 : }
3054 : }
3055 : #endif
3056 : }
3057 : // reverse to get them in CCW order (walking direction around the node)
3058 : std::reverse(edges.begin(), edges.end());
3059 : // compute shape
3060 : c->shape.clear();
3061 1614 : const int begDir = (edges.front()->getFromNode() == this ? FORWARD : BACKWARD);
3062 1614 : const int endDir = (edges.back()->getToNode() == this ? FORWARD : BACKWARD);
3063 1614 : int firstNonPedLane = edges.front()->getFirstNonPedestrianLaneIndex(begDir);
3064 1614 : int lastNonPedLane = edges.back()->getFirstNonPedestrianLaneIndex(endDir);
3065 : DEBUGCOUT(gDebugFlag1, " finalEdges=" << toString(edges) << " firstNonPedLane=" << firstNonPedLane << " lastNonPedLane=" << lastNonPedLane << "\n")
3066 1614 : if (firstNonPedLane < 0 || lastNonPedLane < 0) {
3067 : // invalid crossing
3068 12 : WRITE_WARNINGF(TL("Discarding invalid crossing '%' at junction '%' with edges [%] (no vehicle lanes to cross)."), c->id, getID(), toString(c->edges));
3069 4 : c->valid = false;
3070 : // compute surrogate shape to make it visible in netedit
3071 4 : firstNonPedLane = begDir == FORWARD ? 0 : edges.front()->getNumLanes() - 1;
3072 4 : lastNonPedLane = endDir == FORWARD ? 0 : edges.back()->getNumLanes() - 1;
3073 : }
3074 1614 : if (c->customShape.size() != 0) {
3075 : c->shape = c->customShape;
3076 : } else {
3077 1595 : NBEdge::Lane crossingBeg = edges.front()->getLanes()[firstNonPedLane];
3078 1595 : NBEdge::Lane crossingEnd = edges.back()->getLanes()[lastNonPedLane];
3079 1595 : crossingBeg.width = (crossingBeg.width == NBEdge::UNSPECIFIED_WIDTH ? SUMO_const_laneWidth : crossingBeg.width);
3080 1595 : crossingEnd.width = (crossingEnd.width == NBEdge::UNSPECIFIED_WIDTH ? SUMO_const_laneWidth : crossingEnd.width);
3081 1595 : crossingBeg.shape.move2side(begDir * crossingBeg.width / 2);
3082 1595 : crossingEnd.shape.move2side(endDir * crossingEnd.width / 2);
3083 1595 : crossingBeg.shape.extrapolate(c->width / 2);
3084 1595 : crossingEnd.shape.extrapolate(c->width / 2);
3085 : // check if after all changes shape are NAN (in these case, discard)
3086 1595 : if (crossingBeg.shape.isNAN() || crossingEnd.shape.isNAN()) {
3087 0 : WRITE_WARNINGF(TL("Discarding invalid crossing '%' at junction '%' with edges [%] (invalid shape)."), c->id, getID(), toString(c->edges));
3088 0 : c->valid = false;
3089 : } else {
3090 1883 : c->shape.push_back(crossingBeg.shape[begDir == FORWARD ? 0 : -1]);
3091 1840 : c->shape.push_back(crossingEnd.shape[endDir == FORWARD ? -1 : 0]);
3092 : }
3093 1595 : if (diagonalCrossing) {
3094 7 : c->shape.move2side(-c->width);
3095 : }
3096 1595 : }
3097 1614 : }
3098 4130 : return index;
3099 : }
3100 :
3101 :
3102 : void
3103 4130 : NBNode::buildWalkingAreas(int cornerDetail, double joinMinDist) {
3104 : #ifdef DEBUG_PED_STRUCTURES
3105 : gDebugFlag1 = DEBUGCOND;
3106 : #endif
3107 : int index = 0;
3108 : myWalkingAreas.clear();
3109 : DEBUGCOUT(gDebugFlag1, "build walkingAreas for " << getID() << ":\n")
3110 4130 : if (myAllEdges.size() == 0) {
3111 0 : return;
3112 : }
3113 4130 : EdgeVector allEdges = getEdgesSortedByAngleAtNodeCenter();
3114 : // shapes are all pointing away from the intersection
3115 : std::vector<std::pair<NBEdge*, NBEdge::Lane> > normalizedLanes;
3116 18072 : for (EdgeVector::const_iterator it = allEdges.begin(); it != allEdges.end(); ++it) {
3117 13942 : NBEdge* edge = *it;
3118 : const std::vector<NBEdge::Lane>& lanes = edge->getLanes();
3119 : std::vector<NBEdge::Lane> tmp;
3120 : bool hadSidewalk = false;
3121 : bool hadNonSidewalk = false;
3122 37216 : for (int i = 0; i < (int)lanes.size(); i++) {
3123 23274 : NBEdge::Lane l = lanes[i];
3124 23274 : const bool sidewalk = (l.permissions & SVC_PEDESTRIAN) != 0;
3125 23274 : if (sidewalk) {
3126 11736 : if (hadSidewalk && hadNonSidewalk) {
3127 4 : if (edge->getFromNode() == this) {
3128 6 : WRITE_WARNINGF(TL("Ignoring additional sidewalk lane % on edge '%' for walkingareas."),
3129 : i, edge->getID());
3130 : }
3131 : continue;
3132 : }
3133 : hadSidewalk = true;
3134 : } else {
3135 : hadNonSidewalk = true;
3136 : }
3137 23270 : tmp.push_back(l);
3138 23274 : }
3139 13942 : if (edge->getFromNode() == this) {
3140 : std::reverse(tmp.begin(), tmp.end());
3141 : } else {
3142 18606 : for (NBEdge::Lane& l : tmp) {
3143 23270 : l.shape = l.shape.reverse();
3144 : }
3145 : }
3146 37212 : for (NBEdge::Lane& l : tmp) {
3147 46540 : l.shape = l.shape.getSubpartByIndex(0, 2);
3148 34880 : l.width = (l.width == NBEdge::UNSPECIFIED_WIDTH ? SUMO_const_laneWidth : l.width);
3149 23270 : normalizedLanes.push_back(std::make_pair(edge, l));
3150 : }
3151 13942 : }
3152 : //if (gDebugFlag1) std::cout << " normalizedLanes=" << normalizedLanes.size() << "\n";
3153 : // collect [start,count[ indices in normalizedLanes that belong to a walkingArea
3154 : std::vector<std::pair<int, int> > waIndices;
3155 : int start = -1;
3156 4130 : NBEdge* prevEdge = normalizedLanes.back().first;
3157 27400 : for (int i = 0; i < (int)normalizedLanes.size(); ++i) {
3158 23270 : NBEdge* edge = normalizedLanes[i].first;
3159 : NBEdge::Lane& l = normalizedLanes[i].second;
3160 23270 : if (start == -1) {
3161 14441 : if ((l.permissions & SVC_PEDESTRIAN) != 0) {
3162 : start = i;
3163 : }
3164 : } else {
3165 8829 : if ((l.permissions & SVC_PEDESTRIAN) == 0
3166 5950 : || crossingBetween(edge, prevEdge)
3167 5946 : || alreadyConnectedPaths(edge, prevEdge, joinMinDist)
3168 14704 : || crossesFringe(edge, prevEdge)
3169 : ) {
3170 2966 : waIndices.push_back(std::make_pair(start, i - start));
3171 2966 : if ((l.permissions & SVC_PEDESTRIAN) != 0) {
3172 : start = i;
3173 : } else {
3174 : start = -1;
3175 : }
3176 :
3177 : }
3178 : }
3179 : DEBUGCOUT(gDebugFlag1, " i=" << i << " edge=" << edge->getID() << " start=" << start << " ped=" << ((l.permissions & SVC_PEDESTRIAN) != 0)
3180 : << " waI=" << waIndices.size() << " crossingBetween=" << crossingBetween(edge, prevEdge) << "\n")
3181 : prevEdge = edge;
3182 : }
3183 : // deal with wrap-around issues
3184 4130 : if (start != - 1) {
3185 2903 : const int waNumLanes = (int)normalizedLanes.size() - start;
3186 2903 : if (waIndices.size() == 0) {
3187 2039 : waIndices.push_back(std::make_pair(start, waNumLanes));
3188 : DEBUGCOUT(gDebugFlag1, " single wa, end at wrap-around\n")
3189 : } else {
3190 864 : if (waIndices.front().first == 0) {
3191 772 : NBEdge* edge = normalizedLanes.front().first;
3192 772 : if (crossingBetween(edge, normalizedLanes.back().first)
3193 772 : || crossesFringe(edge, normalizedLanes.back().first)) {
3194 : // do not wrap-around (see above)
3195 7 : waIndices.push_back(std::make_pair(start, waNumLanes));
3196 : DEBUGCOUT(gDebugFlag1, " do not wrap around\n")
3197 : } else {
3198 : // first walkingArea wraps around
3199 765 : waIndices.front().first = start;
3200 765 : waIndices.front().second = waNumLanes + waIndices.front().second;
3201 : DEBUGCOUT(gDebugFlag1, " wrapping around\n")
3202 : }
3203 : } else {
3204 : // last walkingArea ends at the wrap-around
3205 92 : waIndices.push_back(std::make_pair(start, waNumLanes));
3206 : DEBUGCOUT(gDebugFlag1, " end at wrap-around\n")
3207 : }
3208 : }
3209 : }
3210 : #ifdef DEBUG_PED_STRUCTURES
3211 : if (gDebugFlag1) {
3212 : std::cout << " normalizedLanes=" << normalizedLanes.size() << " waIndices:\n";
3213 : for (int i = 0; i < (int)waIndices.size(); ++i) {
3214 : std::cout << " " << waIndices[i].first << ", " << waIndices[i].second << "\n";
3215 : }
3216 : }
3217 : #endif
3218 : // build walking areas connected to a sidewalk
3219 9234 : for (int i = 0; i < (int)waIndices.size(); ++i) {
3220 5104 : const bool buildExtensions = waIndices[i].second != (int)normalizedLanes.size();
3221 5104 : int startIdx = waIndices[i].first;
3222 5104 : const int prev = startIdx > 0 ? startIdx - 1 : (int)normalizedLanes.size() - 1;
3223 : const int count = waIndices[i].second;
3224 5104 : const int end = (startIdx + count) % normalizedLanes.size();
3225 5104 : int lastIdx = (startIdx + count - 1) % normalizedLanes.size();
3226 :
3227 15312 : WalkingArea wa(":" + getID() + "_w" + toString(index++), 1);
3228 : DEBUGCOUT(gDebugFlag1, "build walkingArea " << wa.id << " start=" << startIdx << " end=" << end << " count=" << count << " prev=" << prev << ":\n")
3229 : double endCrossingWidth = 0;
3230 : double startCrossingWidth = 0;
3231 5104 : PositionVector endCrossingShape;
3232 5104 : PositionVector startCrossingShape;
3233 : // check for connected crossings
3234 : bool connectsCrossing = false;
3235 : bool crossingNearSidewalk = false;
3236 : int numCrossings = 0;
3237 : std::vector<Position> connectedPoints;
3238 10480 : for (auto c : getCrossings()) {
3239 : DEBUGCOUT(gDebugFlag1, " crossing=" << c->id << " sortedEdges=" << toString(c->edges) << "\n")
3240 5376 : if (c->edges.back() == normalizedLanes[end].first
3241 5376 : && (normalizedLanes[end].second.permissions & SVC_PEDESTRIAN) == 0) {
3242 : // crossing ends
3243 1465 : if (c->nextWalkingArea != "") {
3244 3 : WRITE_WARNINGF(TL("Invalid pedestrian topology at junction '%'; crossing '%' targets '%' and '%'."),
3245 : getID(), c->id, c->nextWalkingArea, wa.id);
3246 1 : c->valid = false;
3247 : }
3248 : c->nextWalkingArea = wa.id;
3249 1465 : wa.prevCrossings.push_back(c->id);
3250 1465 : if ((int)c->edges.size() < wa.minPrevCrossingEdges) {
3251 : // if there are multiple crossings, use the shape of the one that crosses fewer edges
3252 1465 : endCrossingWidth = c->width;
3253 : endCrossingShape = c->shape;
3254 1465 : wa.width = MAX2(wa.width, endCrossingWidth);
3255 : connectsCrossing = true;
3256 1465 : connectedPoints.push_back(c->shape[-1]);
3257 1465 : wa.minPrevCrossingEdges = (int)c->edges.size();
3258 1465 : numCrossings++;
3259 1465 : if (normalizedLanes[lastIdx].second.shape[0].distanceTo2D(connectedPoints.back()) < endCrossingWidth) {
3260 : crossingNearSidewalk = true;
3261 : DEBUGCOUT(gDebugFlag1, " nearSidewalk\n")
3262 : }
3263 : }
3264 : DEBUGCOUT(gDebugFlag1, " crossing " << c->id << " ends\n")
3265 : }
3266 5376 : if (c->edges.front() == normalizedLanes[prev].first
3267 5376 : && (normalizedLanes[prev].second.permissions & SVC_PEDESTRIAN) == 0) {
3268 : // crossing starts
3269 1465 : if (c->prevWalkingArea != "") {
3270 0 : WRITE_WARNINGF(TL("Invalid pedestrian topology at junction '%'; crossing '%' is targeted by '%' and '%'."),
3271 : getID(), c->id, c->prevWalkingArea, wa.id);
3272 0 : c->valid = false;
3273 : }
3274 1465 : if (c->valid && std::find(wa.prevCrossings.begin(), wa.prevCrossings.end(), c->id) != wa.prevCrossings.end()) {
3275 9 : WRITE_WARNINGF(TL("Invalid pedestrian topology at junction '%'; crossing '%' starts and ends at walkingarea '%'."),
3276 : getID(), c->id, wa.id);
3277 3 : c->valid = false;
3278 : }
3279 : c->prevWalkingArea = wa.id;
3280 1465 : wa.nextCrossings.push_back(c->id);
3281 1465 : if ((int)c->edges.size() < wa.minNextCrossingEdges) {
3282 : // if there are multiple crossings, use the shape of the one that crosses fewer edges
3283 1465 : startCrossingWidth = c->width;
3284 : startCrossingShape = c->shape;
3285 1465 : wa.width = MAX2(wa.width, startCrossingWidth);
3286 : connectsCrossing = true;
3287 1465 : connectedPoints.push_back(c->shape[0]);
3288 1465 : wa.minNextCrossingEdges = (int)c->edges.size();
3289 1465 : numCrossings++;
3290 1465 : if (normalizedLanes[startIdx].second.shape[0].distanceTo2D(connectedPoints.back()) < startCrossingWidth) {
3291 : crossingNearSidewalk = true;
3292 : DEBUGCOUT(gDebugFlag1, " nearSidewalk\n")
3293 : }
3294 : }
3295 : DEBUGCOUT(gDebugFlag1, " crossing " << c->id << " starts\n")
3296 : }
3297 : DEBUGCOUT(gDebugFlag1, " check connections to crossing " << c->id
3298 : << " cFront=" << c->edges.front()->getID() << " cBack=" << c->edges.back()->getID()
3299 : << " wEnd=" << normalizedLanes[end].first->getID() << " wStart=" << normalizedLanes[startIdx].first->getID()
3300 : << " wStartPrev=" << normalizedLanes[prev].first->getID()
3301 : << "\n")
3302 5104 : }
3303 5104 : if (count < 2 && !connectsCrossing) {
3304 : // not relevant for walking
3305 : DEBUGCOUT(gDebugFlag1, " not relevant for walking: count=" << count << " connectsCrossing=" << connectsCrossing << "\n")
3306 709 : continue;
3307 : }
3308 : // build shape and connections
3309 : std::set<const NBEdge*, ComparatorIdLess>& connected = wa.refEdges;
3310 15418 : for (int j = 0; j < count; ++j) {
3311 11023 : const int nlI = (startIdx + j) % normalizedLanes.size();
3312 11023 : NBEdge* edge = normalizedLanes[nlI].first;
3313 11023 : NBEdge::Lane l = normalizedLanes[nlI].second;
3314 17578 : wa.width = MAX2(wa.width, l.width);
3315 : if (connected.count(edge) == 0) {
3316 10973 : if (edge->getFromNode() == this) {
3317 5516 : wa.nextSidewalks.push_back(edge->getSidewalkID());
3318 5516 : connectedPoints.push_back(edge->getLaneShape(0)[0]);
3319 : } else {
3320 5457 : wa.prevSidewalks.push_back(edge->getSidewalkID());
3321 5457 : connectedPoints.push_back(edge->getLaneShape(0)[-1]);
3322 : }
3323 : DEBUGCOUT(gDebugFlag1, " connectedEdge=" << edge->getID() << " connectedPoint=" << connectedPoints.back() << "\n")
3324 : connected.insert(edge);
3325 : }
3326 11023 : l.shape.move2side(-l.width / 2);
3327 11023 : wa.shape.push_back_noDoublePos(l.shape[0]);
3328 11023 : l.shape.move2side(l.width);
3329 11023 : wa.shape.push_back(l.shape[0]);
3330 11023 : }
3331 4395 : if (buildExtensions) {
3332 : // extension at starting crossing
3333 2862 : if (startCrossingShape.size() > 0) {
3334 1455 : startCrossingShape.move2side(startCrossingWidth / 2);
3335 1455 : wa.shape.push_front_noDoublePos(startCrossingShape[0]); // right corner
3336 1455 : startCrossingShape.move2side(-startCrossingWidth);
3337 1455 : wa.shape.push_front_noDoublePos(startCrossingShape[0]); // left corner goes first
3338 : DEBUGCOUT(gDebugFlag1, " extension at startCrossingShape=" << endCrossingShape << " waShape=" << wa.shape << "\n")
3339 : }
3340 : // extension at ending crossing
3341 2862 : if (endCrossingShape.size() > 0) {
3342 1455 : endCrossingShape.move2side(endCrossingWidth / 2);
3343 1455 : wa.shape.push_back_noDoublePos(endCrossingShape[-1]);
3344 1455 : endCrossingShape.move2side(-endCrossingWidth);
3345 1455 : wa.shape.push_back_noDoublePos(endCrossingShape[-1]);
3346 : DEBUGCOUT(gDebugFlag1, " extension at endCrossingShape=" << endCrossingShape << " waShape=" << wa.shape << "\n")
3347 : }
3348 : }
3349 2454 : if (connected.size() == 2 && !connectsCrossing && wa.nextSidewalks.size() == 1 && wa.prevSidewalks.size() == 1
3350 5502 : && normalizedLanes.size() == 2) {
3351 : // do not build a walkingArea since a normal connection exists
3352 430 : const NBEdge* e1 = *connected.begin();
3353 430 : const NBEdge* e2 = *(++connected.begin());
3354 430 : if (e1->hasConnectionTo(e2, 0, 0) || e2->hasConnectionTo(e1, 0, 0)) {
3355 : DEBUGCOUT(gDebugFlag1, " not building a walkingarea since normal connections exist\n")
3356 152 : continue;
3357 : }
3358 : }
3359 4243 : if (count == (int)normalizedLanes.size()) {
3360 : // junction is covered by the whole walkingarea
3361 : wa.shape = myPoly;
3362 : // increase walking width if the walkingare is wider than a single lane
3363 3680 : for (const NBEdge* in : myIncomingEdges) {
3364 6626 : for (const NBEdge* out : myOutgoingEdges) {
3365 5147 : if (in->getFromNode() == out->getToNode() && in->getInnerGeometry().reverse() == out->getInnerGeometry()
3366 820 : && (in->getPermissions() & SVC_PEDESTRIAN)
3367 5147 : && (out->getPermissions() & SVC_PEDESTRIAN)) {
3368 : // doesn't catch all cases but probably most
3369 1611 : wa.width = MAX2(wa.width, in->getTotalWidth() + out->getTotalWidth());
3370 : }
3371 : }
3372 : }
3373 2862 : } else if (cornerDetail > 0) {
3374 : // build smooth inner curve (optional)
3375 : int smoothEnd = end;
3376 : int smoothPrev = prev;
3377 : // extend to green verge
3378 2686 : if (endCrossingWidth > 0 && normalizedLanes[smoothEnd].second.permissions == 0) {
3379 142 : smoothEnd = (smoothEnd + 1) % normalizedLanes.size();
3380 : }
3381 2686 : if (startCrossingWidth > 0 && normalizedLanes[smoothPrev].second.permissions == 0) {
3382 138 : if (smoothPrev == 0) {
3383 0 : smoothPrev = (int)normalizedLanes.size() - 1;
3384 : } else {
3385 138 : smoothPrev--;
3386 : }
3387 : }
3388 2686 : PositionVector begShape = normalizedLanes[smoothEnd].second.shape;
3389 5372 : begShape = begShape.reverse();
3390 : double shiftBegExtra = 0;
3391 : double shiftEndExtra = 0;
3392 2686 : if (lastIdx == startIdx) {
3393 476 : lastIdx = (startIdx + 1) % normalizedLanes.size();
3394 : DEBUGCOUT(gDebugFlag1, " new lastIdx=" << lastIdx << " startEdge=" << normalizedLanes[startIdx].first->getID() << " lastEdge=" << normalizedLanes[lastIdx].first->getID() << "\n")
3395 476 : if (normalizedLanes[startIdx].first == normalizedLanes[lastIdx].first) {
3396 : lastIdx = startIdx;
3397 128 : startIdx--;
3398 128 : if (startIdx < 0) {
3399 33 : startIdx = (int)normalizedLanes.size() - 1;
3400 : }
3401 : DEBUGCOUT(gDebugFlag1, " new startIdx=" << startIdx << " startEdge=" << normalizedLanes[startIdx].first->getID() << " lastEdge=" << normalizedLanes[lastIdx].first->getID() << "\n")
3402 128 : shiftEndExtra += OptionsCont::getOptions().getFloat("default.sidewalk-width");
3403 : } else {
3404 348 : shiftBegExtra += OptionsCont::getOptions().getFloat("default.sidewalk-width");
3405 : }
3406 : }
3407 2686 : PositionVector begShapeOuter = normalizedLanes[lastIdx].second.shape;
3408 5372 : begShapeOuter = begShapeOuter.reverse();
3409 : //begShape.extrapolate(endCrossingWidth);
3410 2686 : begShape.move2side(normalizedLanes[smoothEnd].second.width / 2);
3411 2686 : begShapeOuter.move2side(normalizedLanes[lastIdx].second.width / 2 + shiftBegExtra);
3412 2686 : PositionVector endShape = normalizedLanes[smoothPrev].second.shape;
3413 2686 : PositionVector endShapeOuter = normalizedLanes[startIdx].second.shape;;
3414 2686 : endShape.move2side(normalizedLanes[smoothPrev].second.width / 2);
3415 2686 : endShapeOuter.move2side(normalizedLanes[startIdx].second.width / 2 + shiftEndExtra);
3416 : //endShape.extrapolate(startCrossingWidth);
3417 2686 : PositionVector curve;
3418 2686 : if (count != (int)normalizedLanes.size() || count == 2) {
3419 2686 : const double angle = GeomHelper::angleDiff(begShape.angleAt2D(-2), endShape.angleAt2D(0));
3420 2686 : if (count == 1 && angle > 0 && crossingNearSidewalk && numCrossings < 2) {
3421 : // do not build smooth shape for an unconnected left turn
3422 : // (the walkingArea would get bigger without a reason to
3423 : // walk there)
3424 2595 : } else if ((normalizedLanes[smoothEnd].first->getPermissions() & normalizedLanes[smoothPrev].first->getPermissions() &
3425 : ~(SVC_PEDESTRIAN | SVC_RAIL_CLASSES)) != 0) {
3426 : DEBUGCOUT(gDebugFlag1, " traffic curve\n")
3427 7167 : curve = computeSmoothShape(begShape, endShape, cornerDetail + 2, false, 25, 25, gDebugFlag1 ? this : nullptr);
3428 2389 : if (curve.length2D() - begShape.back().distanceTo2D(endShape.front()) > 5) {
3429 : DEBUGCOUT(gDebugFlag1, " reduceBulge directLength=" << begShape.back().distanceTo2D(endShape.front())
3430 : << " curveLength=" << curve.length2D()
3431 : << " delta=" << curve.length2D() - begShape.back().distanceTo2D(endShape.front())
3432 : << "\n")
3433 68 : curve = computeSmoothShape(begShape, endShape, cornerDetail + 2, false, 25, 25, nullptr, AVOID_WIDE_LEFT_TURN | AVOID_INTERSECTING_LEFT_TURNS);
3434 : }
3435 : } else {
3436 : DEBUGCOUT(gDebugFlag1, " nonTraffic curve\n")
3437 206 : const double extend = MIN2(10.0, begShape.back().distanceTo2D(endShape.front()) / 2);
3438 412 : curve = computeSmoothShape(begShape, endShape, cornerDetail + 2, false, extend, extend, nullptr, FOUR_CONTROL_POINTS);
3439 : }
3440 2686 : if (curve.size() > 2) {
3441 : curve.erase(curve.begin());
3442 : curve.pop_back();
3443 1206 : if (endCrossingWidth > 0) {
3444 : wa.shape.pop_back();
3445 : }
3446 1206 : if (startCrossingWidth > 0) {
3447 : wa.shape.erase(wa.shape.begin());
3448 : }
3449 1206 : if (count == (int)normalizedLanes.size()) {
3450 0 : curve = curve.reverse();
3451 : }
3452 1206 : wa.shape.append(curve, 0);
3453 : }
3454 : DEBUGCOUT(gDebugFlag1, " end=" << smoothEnd << " prev=" << smoothPrev
3455 : << " endCrossingWidth=" << endCrossingWidth << " startCrossingWidth=" << startCrossingWidth
3456 : << " begShape=" << begShape << " endShape=" << endShape << " smooth curve=" << curve
3457 : << " begShapeOuter=" << begShapeOuter << " endShapeOuter=" << endShapeOuter
3458 : << " waShape=" << wa.shape
3459 : << "\n")
3460 : }
3461 2686 : if (curve.size() > 2 && (count == 2 || (count == 1 && numCrossings > 0))) {
3462 1090 : const double innerDist = begShape.back().distanceTo2D(endShape[0]);
3463 1090 : const double outerDist = begShapeOuter.back().distanceTo2D(endShapeOuter[0]);
3464 : DEBUGCOUT(gDebugFlag1, " innerDist=" << innerDist << " outerDist=" << outerDist << "\n")
3465 1090 : if (outerDist > innerDist) {
3466 : // we also need a rounded outer curve (unless we have only a single walkingarea)
3467 102 : const double extend = MIN2(10.0, begShapeOuter.back().distanceTo2D(endShapeOuter.front()) / 2);
3468 204 : curve = computeSmoothShape(begShapeOuter, endShapeOuter, cornerDetail + 2, false, extend, extend, nullptr);
3469 102 : if (curve.length2D() - begShapeOuter.back().distanceTo2D(endShapeOuter.front()) > 5) {
3470 : DEBUGCOUT(gDebugFlag1, " reduceBulge directLength=" << begShapeOuter.back().distanceTo2D(endShapeOuter.front())
3471 : << " curveLength=" << curve.length2D()
3472 : << " delta=" << curve.length2D() - begShapeOuter.back().distanceTo2D(endShapeOuter.front())
3473 : << "\n")
3474 44 : curve = computeSmoothShape(begShapeOuter, endShapeOuter, cornerDetail + 2, false, 25, 25, nullptr, AVOID_WIDE_LEFT_TURN | AVOID_INTERSECTING_LEFT_TURNS);
3475 : }
3476 204 : curve = curve.reverse();
3477 : // keep the points in case of extraShift
3478 102 : if (shiftBegExtra != 0) {
3479 9 : curve.push_front_noDoublePos(wa.shape[1]);
3480 9 : curve.push_back_noDoublePos(wa.shape[2]);
3481 93 : } else if (shiftEndExtra != 0) {
3482 4 : curve.push_back_noDoublePos(wa.shape[1]);
3483 4 : curve.push_back_noDoublePos(wa.shape[2]);
3484 : }
3485 : DEBUGCOUT(gDebugFlag1, " outerCurveRaw=" << curve << " wa1=" << wa.shape[1] << " wa2=" << wa.shape[2] << "\n")
3486 : wa.shape.erase(wa.shape.begin() + 1, wa.shape.begin() + 3);
3487 102 : wa.shape.insert(wa.shape.begin() + 1, curve.begin(), curve.end());
3488 : DEBUGCOUT(gDebugFlag1, " outerCurve=" << curve << "\n")
3489 : }
3490 : }
3491 2686 : }
3492 : // apply custom shapes
3493 4243 : if (myWalkingAreaCustomShapes.size() > 0) {
3494 72 : for (auto wacs : myWalkingAreaCustomShapes) {
3495 : // every edge in wasc.edges must be part of connected
3496 44 : if ((wacs.shape.size() != 0 || wacs.width != NBEdge::UNSPECIFIED_WIDTH) && includes(connected, wacs.edges)) {
3497 5 : if (wacs.shape.size() != 0) {
3498 : wa.shape = wacs.shape;
3499 : }
3500 5 : if (wacs.width != NBEdge::UNSPECIFIED_WIDTH) {
3501 2 : wa.width = wacs.width;
3502 : }
3503 5 : wa.hasCustomShape = true;
3504 : }
3505 : }
3506 : }
3507 : // determine length (average of all possible connections)
3508 : double lengthSum = 0;
3509 : int combinations = 0;
3510 17842 : for (std::vector<Position>::const_iterator it1 = connectedPoints.begin(); it1 != connectedPoints.end(); ++it1) {
3511 63220 : for (std::vector<Position>::const_iterator it2 = connectedPoints.begin(); it2 != connectedPoints.end(); ++it2) {
3512 : const Position& p1 = *it1;
3513 : const Position& p2 = *it2;
3514 : if (p1 != p2) {
3515 35938 : lengthSum += p1.distanceTo2D(p2);
3516 35938 : combinations += 1;
3517 : }
3518 : }
3519 : }
3520 : DEBUGCOUT(gDebugFlag1, " combinations=" << combinations << " connectedPoints=" << connectedPoints << "\n")
3521 4243 : wa.length = POSITION_EPS;
3522 4243 : if (combinations > 0) {
3523 8407 : wa.length = MAX2(POSITION_EPS, lengthSum / combinations);
3524 : }
3525 4243 : myWalkingAreas.push_back(wa);
3526 5104 : }
3527 : // build walkingAreas between split crossings
3528 4130 : std::vector<Crossing*> validCrossings = getCrossings();
3529 5736 : for (std::vector<Crossing*>::iterator it = validCrossings.begin(); it != validCrossings.end(); ++it) {
3530 1606 : Crossing& prev = **it;
3531 1606 : Crossing& next = (it != validCrossings.begin() ? **(it - 1) :** (validCrossings.end() - 1));
3532 : DEBUGCOUT(gDebugFlag1, " checkIntermediate: prev=" << prev.id << " next=" << next.id << " prev.nextWA=" << prev.nextWalkingArea << " next.prevWA=" << next.prevWalkingArea << "\n")
3533 1606 : if (prev.nextWalkingArea == "") {
3534 146 : if (next.prevWalkingArea != "" || &prev == &next) {
3535 12 : WRITE_WARNINGF(TL("Invalid pedestrian topology: crossing '%' across [%] has no target."), prev.id, toString(prev.edges));
3536 4 : prev.valid = false;
3537 4 : continue;
3538 : }
3539 426 : WalkingArea wa(":" + getID() + "_w" + toString(index++), prev.width);
3540 : prev.nextWalkingArea = wa.id;
3541 142 : wa.nextCrossings.push_back(next.id);
3542 : next.prevWalkingArea = wa.id;
3543 : // back of previous crossing
3544 : PositionVector tmp = prev.shape;
3545 142 : tmp.move2side(-prev.width / 2);
3546 142 : wa.shape.push_back(tmp[-1]);
3547 142 : tmp.move2side(prev.width);
3548 142 : wa.shape.push_back(tmp[-1]);
3549 : // front of next crossing
3550 : tmp = next.shape;
3551 142 : tmp.move2side(prev.width / 2);
3552 142 : wa.shape.push_back(tmp[0]);
3553 142 : tmp.move2side(-prev.width);
3554 142 : wa.shape.push_back(tmp[0]);
3555 : wa.refEdges.insert(prev.edges.begin(), prev.edges.end());
3556 : wa.refEdges.insert(next.edges.begin(), next.edges.end());
3557 : // apply custom shapes
3558 142 : if (myWalkingAreaCustomShapes.size() > 0) {
3559 48 : for (auto wacs : myWalkingAreaCustomShapes) {
3560 : // every edge in wacs.edges must be part of crossed
3561 30 : if (wacs.shape.size() != 0 && wacs.edges.size() > 1 && includes(wa.refEdges, wacs.edges)) {
3562 : wa.shape = wacs.shape;
3563 6 : wa.hasCustomShape = true;
3564 : }
3565 : }
3566 : }
3567 : // length (special case)
3568 142 : wa.length = MAX2(POSITION_EPS, prev.shape.back().distanceTo2D(next.shape.front()));
3569 142 : myWalkingAreas.push_back(wa);
3570 : DEBUGCOUT(gDebugFlag1, " build wa=" << wa.id << "\n")
3571 142 : }
3572 : }
3573 4130 : }
3574 :
3575 :
3576 : void
3577 4130 : NBNode::buildCrossingOutlines() {
3578 : #ifdef DEBUG_CROSSING_OUTLINE
3579 : if (myCrossings.size() > 0) {
3580 : std::cerr << "<add>\n";
3581 : }
3582 : #endif
3583 : std::map<std::string, PositionVector> waShapes;
3584 8515 : for (auto wa : myWalkingAreas) {
3585 4385 : waShapes[wa.id] = wa.shape;
3586 4385 : }
3587 5732 : for (auto c : getCrossings()) {
3588 1602 : PositionVector wa1 = waShapes[c->prevWalkingArea];
3589 1602 : PositionVector wa2 = waShapes[c->nextWalkingArea];
3590 1602 : if (wa1.empty() || wa2.empty()) {
3591 : continue;
3592 : }
3593 1601 : wa1.closePolygon();
3594 1601 : wa2.closePolygon();
3595 : PositionVector side1 = c->shape;
3596 1601 : PositionVector side2 = c->shape.reverse();
3597 1601 : side1.move2side(c->width / 2);
3598 1601 : side2.move2side(c->width / 2);
3599 : PositionVector side1default = side1;
3600 : PositionVector side2default = side2;
3601 1601 : side1.extrapolate(POSITION_EPS);
3602 1601 : side2.extrapolate(c->width);
3603 3202 : side1 = cutAtShapes(side1, wa1, wa2, side1default);
3604 3202 : side2 = cutAtShapes(side2, wa1, wa2, side2default);
3605 : PositionVector side1ex = side1;
3606 : PositionVector side2ex = side2;
3607 1601 : side1ex.extrapolate(POSITION_EPS);
3608 1601 : side2ex.extrapolate(side2 == side2default ? c->width / 2 : POSITION_EPS);
3609 1601 : PositionVector side3 = cutAtShapes(wa2, side1ex, side2ex, PositionVector());
3610 1601 : PositionVector side4 = cutAtShapes(wa1, side1ex, side2ex, PositionVector());
3611 : c->outlineShape = side1;
3612 1601 : c->outlineShape.append(side3, POSITION_EPS);
3613 1601 : c->outlineShape.append(side2, POSITION_EPS);
3614 1601 : c->outlineShape.append(side4, POSITION_EPS);
3615 1601 : c->outlineShape.removeDoublePoints();
3616 1601 : if (c->outlineShape.back().almostSame(c->outlineShape.front())) {
3617 : c->outlineShape.pop_back();
3618 : }
3619 : // DEBUG
3620 : #ifdef DEBUG_CROSSING_OUTLINE
3621 : std::cout << " side1=" << side1 << "\n side2=" << side2 << "\n side3=" << side3 << "\n side4=" << side4 << "\n";
3622 : std::cerr << "<poly id=\"" << c->id << "\" shape=\"" << c->outlineShape << "\" color=\"blue\" lineWidth=\"0.2\" layer=\"100\"/>\n";
3623 : #endif
3624 5732 : }
3625 : #ifdef DEBUG_CROSSING_OUTLINE
3626 : if (myCrossings.size() > 0) {
3627 : std::cerr << "</add>\n";
3628 : }
3629 : #endif
3630 4130 : }
3631 :
3632 :
3633 : PositionVector
3634 6404 : NBNode::cutAtShapes(const PositionVector& cut, const PositionVector& border1, const PositionVector& border2, const PositionVector& def) {
3635 6404 : std::vector<double> is1 = cut.intersectsAtLengths2D(border1);
3636 6404 : std::vector<double> is2 = cut.intersectsAtLengths2D(border2);
3637 : #ifdef DEBUG_CROSSING_OUTLINE
3638 : std::cout << "is1=" << is1 << " is2=" << is2 << " cut=" << cut << " border1=" << border1 << " border2=" << border2 << "\n";
3639 : #endif
3640 6404 : if (is1.size() == 0 && border1.size() == 2) {
3641 1203 : const double d1 = cut.distance2D(border1.front());
3642 1203 : const double d2 = cut.distance2D(border1.back());
3643 1203 : Position closer = d1 < d2 ? border1.front() : border1.back();
3644 1203 : double nOp = cut.nearest_offset_to_point2D(closer, false);
3645 : #ifdef DEBUG_CROSSING_OUTLINE
3646 : std::cout << " closer=" << closer << " nOp=" << nOp << "\n";
3647 : #endif
3648 1203 : if (nOp <= 2 * POSITION_EPS && cut.back().distanceTo2D(closer) <= 2 * POSITION_EPS) {
3649 288 : is1.push_back(cut.length2D());
3650 : } else {
3651 915 : is1.push_back(nOp);
3652 : }
3653 : }
3654 6404 : if (is2.size() == 0 && border2.size() == 2) {
3655 826 : const double d1 = cut.distance2D(border2.front());
3656 826 : const double d2 = cut.distance2D(border2.back());
3657 826 : Position closer = d1 < d2 ? border2.front() : border2.back();
3658 826 : double nOp = cut.nearest_offset_to_point2D(closer, false);
3659 826 : if (nOp <= 2 * POSITION_EPS && cut.back().distanceTo2D(closer) <= 2 * POSITION_EPS) {
3660 10 : is2.push_back(cut.length2D());
3661 : } else {
3662 816 : is2.push_back(nOp);
3663 : }
3664 : }
3665 6404 : if (is1.size() > 0 && is2.size() > 0) {
3666 : double of1 = VectorHelper<double>::maxValue(is1);
3667 : double of2 = VectorHelper<double>::minValue(is2);
3668 : #ifdef DEBUG_CROSSING_OUTLINE
3669 : std::cout << " of1=" << of1 << " of2=" << of2 << "\n";
3670 : #endif
3671 4742 : if (of1 > of2) {
3672 : of1 = VectorHelper<double>::maxValue(is2);
3673 : of2 = VectorHelper<double>::minValue(is1);
3674 : #ifdef DEBUG_CROSSING_OUTLINE
3675 : std::cout << " of1=" << of1 << " of2=" << of2 << "\n";
3676 : #endif
3677 : }
3678 4742 : if (of1 > of2) {
3679 : of2 = VectorHelper<double>::maxValue(is1);
3680 : of1 = VectorHelper<double>::minValue(is2);
3681 : #ifdef DEBUG_CROSSING_OUTLINE
3682 : std::cout << " of1=" << of1 << " of2=" << of2 << "\n";
3683 : #endif
3684 : }
3685 : assert(of1 <= of2);
3686 4742 : return cut.getSubpart(of1, of2);
3687 : } else {
3688 : return def;
3689 : }
3690 6404 : }
3691 :
3692 :
3693 : bool
3694 62 : NBNode::includes(const std::set<const NBEdge*, ComparatorIdLess>& super,
3695 : const std::set<const NBEdge*, ComparatorIdLess>& sub) {
3696 : // for some reason std::include does not work reliably
3697 85 : for (const NBEdge* e : sub) {
3698 148 : if (super.count(const_cast<NBEdge*>(e)) == 0) {
3699 : return false;
3700 : }
3701 : }
3702 : return true;
3703 : }
3704 :
3705 :
3706 : bool
3707 6722 : NBNode::crossingBetween(const NBEdge* e1, const NBEdge* e2) const {
3708 6722 : if (e1 == e2) {
3709 : return false;
3710 : }
3711 6672 : if (myAllEdges.size() > 3) {
3712 : // pedestrian scramble
3713 : return false;
3714 : }
3715 2374 : for (auto c : getCrossings()) {
3716 : const EdgeVector& edges = c->edges;
3717 76 : EdgeVector::const_iterator it1 = std::find(edges.begin(), edges.end(), e1);
3718 76 : EdgeVector::const_iterator it2 = std::find(edges.begin(), edges.end(), e2);
3719 76 : if (it1 != edges.end() && it2 != edges.end()) {
3720 4 : return true;
3721 : }
3722 2302 : }
3723 2298 : return false;
3724 : }
3725 :
3726 :
3727 : bool
3728 5946 : NBNode::alreadyConnectedPaths(const NBEdge* e1, const NBEdge* e2, double dist) const {
3729 5946 : if (e1 == e2) {
3730 : return false;
3731 : }
3732 5896 : if (e1->getPermissions() != SVC_PEDESTRIAN
3733 5896 : || e2->getPermissions() != SVC_PEDESTRIAN) {
3734 : // no paths
3735 3938 : return false;
3736 : }
3737 2625 : if (e1->getFinalLength() > dist &&
3738 667 : e2->getFinalLength() > dist) {
3739 : // too long
3740 : return false;
3741 : }
3742 1589 : NBNode* other1 = e1->getFromNode() == this ? e1->getToNode() : e1->getFromNode();
3743 1589 : NBNode* other2 = e2->getFromNode() == this ? e2->getToNode() : e2->getFromNode();
3744 1589 : return other1 == other2;
3745 : }
3746 :
3747 :
3748 : bool
3749 6647 : NBNode::crossesFringe(const NBEdge* e1, const NBEdge* e2) const {
3750 6647 : return myFringeType != FringeType::DEFAULT
3751 19 : && myIncomingEdges.size() == 1 && myOutgoingEdges.size() == 1
3752 6666 : && (e1->isTurningDirectionAt(e2) || e2->isTurningDirectionAt(e1));
3753 : }
3754 :
3755 :
3756 : EdgeVector
3757 0 : NBNode::edgesBetween(const NBEdge* e1, const NBEdge* e2) const {
3758 : EdgeVector result;
3759 0 : EdgeVector::const_iterator it = std::find(myAllEdges.begin(), myAllEdges.end(), e1);
3760 : assert(it != myAllEdges.end());
3761 0 : NBContHelper::nextCW(myAllEdges, it);
3762 0 : EdgeVector::const_iterator it_end = std::find(myAllEdges.begin(), myAllEdges.end(), e2);
3763 : assert(it_end != myAllEdges.end());
3764 0 : while (it != it_end) {
3765 0 : result.push_back(*it);
3766 0 : NBContHelper::nextCW(myAllEdges, it);
3767 : }
3768 0 : return result;
3769 0 : }
3770 :
3771 :
3772 : void
3773 11 : NBNode::addWalkingAreaShape(EdgeVector edges, const PositionVector& shape, double width) {
3774 11 : WalkingAreaCustomShape wacs;
3775 : wacs.edges.insert(edges.begin(), edges.end());
3776 : wacs.shape = shape;
3777 11 : wacs.width = width;
3778 11 : myWalkingAreaCustomShapes.push_back(wacs);
3779 11 : }
3780 :
3781 :
3782 : bool
3783 265627 : NBNode::geometryLike() const {
3784 265627 : return geometryLike(myIncomingEdges, myOutgoingEdges);
3785 : }
3786 :
3787 : bool
3788 300099 : NBNode::geometryLike(const EdgeVector& incoming, const EdgeVector& outgoing) const {
3789 300099 : if (incoming.size() == 1 && outgoing.size() == 1) {
3790 : return true;
3791 : }
3792 241797 : if (incoming.size() == 2 && outgoing.size() == 2) {
3793 : // check whether the incoming and outgoing edges are pairwise (near) parallel and
3794 : // thus the only cross-connections could be turn-arounds
3795 48439 : NBEdge* in0 = incoming[0];
3796 48439 : NBEdge* in1 = incoming[1];
3797 48439 : NBEdge* out0 = outgoing[0];
3798 48439 : NBEdge* out1 = outgoing[1];
3799 84967 : if ((in0->isTurningDirectionAt(out0) || in0->isTurningDirectionAt(out1))
3800 49883 : && (in1->isTurningDirectionAt(out0) || in1->isTurningDirectionAt(out1))) {
3801 10823 : return true;
3802 : }
3803 37616 : if (in0->getGeometry() == in1->getGeometry() && out0->getGeometry() == out1->getGeometry()) {
3804 : // overlapping edges
3805 : return true;
3806 : }
3807 78274 : for (EdgeVector::const_iterator it = incoming.begin(); it != incoming.end(); ++it) {
3808 61242 : NBEdge* inEdge = *it;
3809 61242 : double angle0 = fabs(NBHelpers::relAngle(inEdge->getAngleAtNode(this), out0->getAngleAtNode(this)));
3810 61242 : double angle1 = fabs(NBHelpers::relAngle(inEdge->getAngleAtNode(this), out1->getAngleAtNode(this)));
3811 61242 : if (MAX2(angle0, angle1) <= 160) {
3812 : // neither of the outgoing edges is parallel to inEdge
3813 : return false;
3814 : }
3815 : }
3816 : return true;
3817 : }
3818 : return false;
3819 : }
3820 :
3821 : void
3822 342 : NBNode::setRoundabout() {
3823 342 : if (myType == SumoXMLNodeType::RIGHT_BEFORE_LEFT || myType == SumoXMLNodeType::LEFT_BEFORE_RIGHT) {
3824 6 : myType = SumoXMLNodeType::PRIORITY;
3825 : }
3826 342 : }
3827 :
3828 : bool
3829 168 : NBNode::isRoundabout() const {
3830 531 : for (NBEdge* out : myOutgoingEdges) {
3831 373 : if (out->getJunctionPriority(this) == NBEdge::JunctionPriority::ROUNDABOUT) {
3832 : return true;
3833 : }
3834 : }
3835 : return false;
3836 : }
3837 :
3838 : NBNode::Crossing*
3839 2012 : NBNode::addCrossing(EdgeVector edges, double width, bool priority, int tlIndex, int tlIndex2,
3840 : const PositionVector& customShape, bool fromSumoNet, const Parameterised* params) {
3841 2012 : Crossing* c = new Crossing(this, edges, width, priority, tlIndex, tlIndex2, customShape);
3842 2012 : if (params != nullptr) {
3843 140 : c->updateParameters(params->getParametersMap());
3844 : }
3845 2012 : myCrossings.push_back(std::unique_ptr<Crossing>(c));
3846 2012 : if (fromSumoNet) {
3847 140 : myCrossingsLoadedFromSumoNet += 1;
3848 : }
3849 2012 : return c;
3850 : }
3851 :
3852 :
3853 : void
3854 3 : NBNode::removeCrossing(const EdgeVector& edges) {
3855 3 : EdgeSet edgeSet(edges.begin(), edges.end());
3856 18 : for (auto it = myCrossings.begin(); it != myCrossings.end();) {
3857 15 : EdgeSet edgeSet2((*it)->edges.begin(), (*it)->edges.end());
3858 15 : if (edgeSet == edgeSet2) {
3859 3 : it = myCrossings.erase(it);
3860 : } else {
3861 : ++it;
3862 : }
3863 : }
3864 3 : }
3865 :
3866 :
3867 : NBNode::Crossing*
3868 1534 : NBNode::getCrossing(const std::string& id) const {
3869 3300 : for (auto& c : myCrossings) {
3870 3300 : if (c->id == id) {
3871 1534 : return c.get();
3872 : }
3873 : }
3874 0 : throw ProcessError(TLF("Request for unknown crossing '%'", id));
3875 : }
3876 :
3877 :
3878 : NBNode::Crossing*
3879 3 : NBNode::getCrossing(const EdgeVector& edges, bool hardFail) const {
3880 3 : const EdgeSet edgeSet(edges.begin(), edges.end());
3881 13 : for (auto& crossing : myCrossings) {
3882 13 : const EdgeSet edgeSet2(crossing->edges.begin(), crossing->edges.end());
3883 13 : if (edgeSet == edgeSet2) {
3884 : return crossing.get();
3885 : }
3886 : }
3887 0 : if (!hardFail) {
3888 : return nullptr;
3889 : }
3890 0 : throw ProcessError(TL("Request for unknown crossing for the given Edges"));
3891 : }
3892 :
3893 :
3894 : NBNode::WalkingArea&
3895 0 : NBNode::getWalkingArea(const std::string& id) {
3896 0 : for (auto& walkingArea : myWalkingAreas) {
3897 0 : if (walkingArea.id == id) {
3898 : return walkingArea;
3899 : }
3900 : }
3901 : // not found, maybe we need to rebuild
3902 0 : updateSurroundingGeometry();
3903 0 : sortEdges(true);
3904 0 : buildCrossingsAndWalkingAreas();
3905 0 : for (auto& walkingArea : myWalkingAreas) {
3906 0 : if (walkingArea.id == id) {
3907 : return walkingArea;
3908 : }
3909 : }
3910 0 : if (myWalkingAreas.size() > 0) {
3911 : // don't crash
3912 0 : WRITE_WARNINGF("Could not retrieve walkingarea '%' (edge ordering changed after recompute).", id);
3913 0 : return myWalkingAreas.front();
3914 : }
3915 0 : throw ProcessError(TLF("Request for unknown walkingarea '%'.", id));
3916 : }
3917 :
3918 :
3919 : bool
3920 4673 : NBNode::setCrossingTLIndices(const std::string& tlID, int startIndex) {
3921 : bool usedCustom = false;
3922 5878 : for (auto c : getCrossings()) {
3923 1205 : c->tlLinkIndex = startIndex++;
3924 1205 : c->tlID = tlID;
3925 1205 : if (c->customTLIndex != -1) {
3926 278 : usedCustom |= (c->tlLinkIndex != c->customTLIndex);
3927 278 : c->tlLinkIndex = c->customTLIndex;
3928 : }
3929 1205 : c->tlLinkIndex2 = c->customTLIndex2;
3930 4673 : }
3931 4673 : return usedCustom;
3932 : }
3933 :
3934 :
3935 : int
3936 43523 : NBNode::numNormalConnections() const {
3937 43523 : if (myRequest == nullptr) {
3938 : // could be an uncontrolled type
3939 : int result = 0;
3940 534 : for (const NBEdge* const edge : myIncomingEdges) {
3941 252 : result += (int)edge->getConnections().size();
3942 : }
3943 282 : return result;
3944 : } else {
3945 43241 : return myRequest->getSizes().second;
3946 : }
3947 : }
3948 :
3949 :
3950 : int
3951 204896 : NBNode::getConnectionIndex(const NBEdge* from, const NBEdge::Connection& con) const {
3952 : int result = 0;
3953 418058 : for (const NBEdge* const e : myIncomingEdges) {
3954 1417850 : for (const NBEdge::Connection& cand : e->getConnections()) {
3955 1204688 : if (e == from && cand.fromLane == con.fromLane && cand.toLane == con.toLane && cand.toEdge == con.toEdge) {
3956 : return result;
3957 : }
3958 999792 : result++;
3959 : }
3960 : }
3961 : return -1;
3962 : }
3963 :
3964 :
3965 : Position
3966 88992 : NBNode::getCenter() const {
3967 : /* Conceptually, the center point would be identical with myPosition.
3968 : * However, if the shape is influenced by custom geometry endpoints of the adjoining edges,
3969 : * myPosition may fall outside the shape. In this case it is better to use
3970 : * the center of the shape
3971 : **/
3972 : PositionVector tmp = myPoly;
3973 88992 : tmp.closePolygon();
3974 : //std::cout << getID() << " around=" << tmp.around(myPosition) << " dist=" << tmp.distance2D(myPosition) << "\n";
3975 88992 : if (tmp.size() < 3 || tmp.around(myPosition) || tmp.distance2D(myPosition) < POSITION_EPS) {
3976 86004 : return myPosition;
3977 : }
3978 2988 : return myPoly.getPolygonCenter();
3979 88992 : }
3980 :
3981 :
3982 : EdgeVector
3983 7500 : NBNode::getEdgesSortedByAngleAtNodeCenter() const {
3984 7500 : EdgeVector result = myAllEdges;
3985 : #ifdef DEBUG_PED_STRUCTURES
3986 : if (gDebugFlag1) {
3987 : std::cout << " angles:\n";
3988 : for (EdgeVector::const_iterator it = result.begin(); it != result.end(); ++it) {
3989 : std::cout << " edge=" << (*it)->getID() << " edgeAngle=" << (*it)->getAngleAtNode(this) << " angleToShape=" << (*it)->getAngleAtNodeToCenter(this) << "\n";
3990 : }
3991 : std::cout << " allEdges before: " << toString(result) << "\n";
3992 : }
3993 : #endif
3994 7500 : sort(result.begin(), result.end(), NBContHelper::edge_by_angle_to_nodeShapeCentroid_sorter(this));
3995 : // let the first edge in myAllEdges remain the first
3996 : DEBUGCOUT(gDebugFlag1, " allEdges sorted: " << toString(result) << "\n")
3997 7500 : rotate(result.begin(), std::find(result.begin(), result.end(), *myAllEdges.begin()), result.end());
3998 : DEBUGCOUT(gDebugFlag1, " allEdges rotated: " << toString(result) << "\n")
3999 7500 : return result;
4000 0 : }
4001 :
4002 :
4003 : void
4004 37763 : NBNode::avoidOverlap() {
4005 : // simple case: edges with LaneSpreadFunction::CENTER and a (possible) turndirection at the same node
4006 99318 : for (EdgeVector::iterator it = myIncomingEdges.begin(); it != myIncomingEdges.end(); it++) {
4007 61555 : NBEdge* edge = *it;
4008 61555 : NBEdge* turnDest = edge->getTurnDestination(true);
4009 61555 : if (turnDest != nullptr) {
4010 38753 : edge->shiftPositionAtNode(this, turnDest);
4011 38753 : turnDest->shiftPositionAtNode(this, edge);
4012 : }
4013 : }
4014 : // @todo: edges in the same direction with sharp angles starting/ending at the same position
4015 37763 : }
4016 :
4017 :
4018 : bool
4019 273308 : NBNode::isTrafficLight(SumoXMLNodeType type) {
4020 : return type == SumoXMLNodeType::TRAFFIC_LIGHT
4021 : || type == SumoXMLNodeType::TRAFFIC_LIGHT_NOJUNCTION
4022 273308 : || type == SumoXMLNodeType::TRAFFIC_LIGHT_RIGHT_ON_RED;
4023 : }
4024 :
4025 :
4026 : bool
4027 1163991 : NBNode::rightOnRedConflict(int index, int foeIndex) const {
4028 1369665 : for (NBTrafficLightDefinition* def : myTrafficLights) {
4029 205704 : if (def->rightOnRedConflict(index, foeIndex)) {
4030 : return true;
4031 : }
4032 : }
4033 : return false;
4034 : }
4035 :
4036 :
4037 : void
4038 169469 : NBNode::sortEdges(bool useNodeShape) {
4039 169469 : if (myAllEdges.size() == 0) {
4040 2180 : return;
4041 : }
4042 167289 : EdgeVector allEdgesOriginal = myAllEdges;
4043 : EdgeVector& allEdges = myAllEdges;
4044 : EdgeVector& incoming = myIncomingEdges;
4045 : EdgeVector& outgoing = myOutgoingEdges;
4046 :
4047 : // sort the edges by angle (this is the canonical sorting)
4048 167289 : std::sort(allEdges.begin(), allEdges.end(), NBNodesEdgesSorter::edge_by_junction_angle_sorter(this));
4049 167289 : std::sort(incoming.begin(), incoming.end(), NBNodesEdgesSorter::edge_by_junction_angle_sorter(this));
4050 167289 : std::sort(outgoing.begin(), outgoing.end(), NBNodesEdgesSorter::edge_by_junction_angle_sorter(this));
4051 : std::vector<NBEdge*>::iterator j;
4052 580307 : for (j = allEdges.begin(); j != allEdges.end() - 1 && j != allEdges.end(); ++j) {
4053 413018 : NBNodesEdgesSorter::swapWhenReversed(this, j, j + 1);
4054 : }
4055 167289 : if (allEdges.size() > 1 && j != allEdges.end()) {
4056 144258 : NBNodesEdgesSorter::swapWhenReversed(this, allEdges.end() - 1, allEdges.begin());
4057 : }
4058 :
4059 : // sort again using additional geometry information
4060 167289 : NBEdge* firstOfAll = allEdges.front();
4061 167289 : NBEdge* firstOfIncoming = incoming.size() > 0 ? incoming.front() : 0;
4062 167289 : NBEdge* firstOfOutgoing = outgoing.size() > 0 ? outgoing.front() : 0;
4063 : // sort by the angle between the node shape center and the point where the edge meets the node shape
4064 167289 : std::sort(allEdges.begin(), allEdges.end(), NBContHelper::edge_by_angle_to_nodeShapeCentroid_sorter(this));
4065 167289 : std::sort(incoming.begin(), incoming.end(), NBContHelper::edge_by_angle_to_nodeShapeCentroid_sorter(this));
4066 167289 : std::sort(outgoing.begin(), outgoing.end(), NBContHelper::edge_by_angle_to_nodeShapeCentroid_sorter(this));
4067 : // let the first edge remain the first
4068 167289 : rotate(allEdges.begin(), std::find(allEdges.begin(), allEdges.end(), firstOfAll), allEdges.end());
4069 167289 : if (firstOfIncoming != nullptr) {
4070 155453 : rotate(incoming.begin(), std::find(incoming.begin(), incoming.end(), firstOfIncoming), incoming.end());
4071 : }
4072 167289 : if (firstOfOutgoing != nullptr) {
4073 152741 : rotate(outgoing.begin(), std::find(outgoing.begin(), outgoing.end(), firstOfOutgoing), outgoing.end());
4074 : }
4075 : #ifdef DEBUG_EDGE_SORTING
4076 : if (DEBUGCOND) {
4077 : std::cout << "sortedEdges (useNodeShape=" << useNodeShape << "):\n";
4078 : for (NBEdge* e : allEdges) {
4079 : std::cout << " " << e->getID()
4080 : << " angleToCenter=" << e->getAngleAtNodeToCenter(this)
4081 : << " junctionAngle=" << e->getAngleAtNode(this) << "\n";
4082 : }
4083 : }
4084 : #endif
4085 :
4086 : // fixing some pathological all edges orderings
4087 : // if every of the edges a,b,c has a turning edge a',b',c' the all edges ordering should be a,a',b,b',c,c'
4088 167289 : if (incoming.size() == outgoing.size() && incoming.front() == allEdges.front()) {
4089 : std::vector<NBEdge*>::const_iterator in, out;
4090 : std::vector<NBEdge*> allTmp;
4091 176054 : for (in = incoming.begin(), out = outgoing.begin(); in != incoming.end(); ++in, ++out) {
4092 137276 : if ((*in)->isTurningDirectionAt(*out)) {
4093 117888 : allTmp.push_back(*in);
4094 117888 : allTmp.push_back(*out);
4095 : } else {
4096 : break;
4097 : }
4098 : }
4099 58166 : if (allTmp.size() == allEdges.size()) {
4100 38778 : allEdges = allTmp;
4101 : }
4102 58166 : }
4103 : // sort the crossings
4104 167289 : std::sort(myCrossings.begin(), myCrossings.end(), NBNodesEdgesSorter::crossing_by_junction_angle_sorter(this, allEdges));
4105 : //if (crossings.size() > 0) {
4106 : // std::cout << " crossings at " << getID() << "\n";
4107 : // for (std::vector<NBNode::Crossing*>::iterator it = crossings.begin(); it != crossings.end(); ++it) {
4108 : // std::cout << " " << toString((*it)->edges) << "\n";
4109 : // }
4110 : //}
4111 :
4112 167289 : if (useNodeShape && myAllEdges != allEdgesOriginal) {
4113 : // sorting order changed after node shape was computed.
4114 261 : computeNodeShape(-1);
4115 2177 : for (NBEdge* e : myAllEdges) {
4116 1916 : e->computeEdgeShape();
4117 : }
4118 : }
4119 167289 : }
4120 :
4121 : std::vector<std::pair<Position, std::string> >
4122 0 : NBNode::getEndPoints() const {
4123 : // using a set would be nicer but we want to have some slack in position identification
4124 : std::vector<std::pair<Position, std::string> >result;
4125 0 : for (NBEdge* e : myAllEdges) {
4126 0 : Position pos = this == e->getFromNode() ? e->getGeometry().front() : e->getGeometry().back();
4127 0 : const std::string origID = e->getParameter(this == e->getFromNode() ? "origFrom" : "origTo");
4128 : bool unique = true;
4129 0 : for (const auto& pair : result) {
4130 0 : if (pos.almostSame(pair.first) || (origID != "" && pair.second == origID)) {
4131 : unique = false;
4132 : break;
4133 : }
4134 : }
4135 0 : if (unique) {
4136 0 : result.push_back(std::make_pair(pos, origID));
4137 : }
4138 : }
4139 0 : return result;
4140 0 : }
4141 :
4142 :
4143 : /****************************************************************************/
|
