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 87291 : NBNode::ApproachingDivider::ApproachingDivider(
103 87291 : const EdgeVector& approaching, NBEdge* currentOutgoing) :
104 87291 : myApproaching(approaching),
105 87291 : myCurrentOutgoing(currentOutgoing),
106 87291 : myNumStraight(0),
107 87291 : myIsBikeEdge(currentOutgoing->getPermissions() == SVC_BICYCLE) {
108 : // collect lanes which are expliclity targeted
109 : std::set<int> approachedLanes;
110 256488 : for (const NBEdge* const approachingEdge : myApproaching) {
111 621884 : for (const NBEdge::Connection& con : approachingEdge->getConnections()) {
112 452687 : if (con.toEdge == myCurrentOutgoing) {
113 190586 : approachedLanes.insert(con.toLane);
114 : }
115 : }
116 169197 : myDirections.push_back(approachingEdge->getToNode()->getDirection(approachingEdge, currentOutgoing));
117 169197 : if (myDirections.back() == LinkDirection::STRAIGHT) {
118 71138 : 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 201359 : for (int i = 0; i < currentOutgoing->getNumLanes(); ++i) {
126 114068 : if ((currentOutgoing->getPermissions(i) == SVC_PEDESTRIAN
127 : // don't consider bicycle lanes as targets unless the target
128 : // edge is exclusively for bicycles
129 108481 : || (currentOutgoing->getPermissions(i) == SVC_BICYCLE && !myIsBikeEdge)
130 107793 : || isForbidden(currentOutgoing->getPermissions(i)))
131 114068 : && approachedLanes.count(i) == 0) {
132 4846 : continue;
133 : }
134 109222 : myAvailableLanes.push_back(i);
135 : }
136 87291 : }
137 :
138 :
139 87291 : NBNode::ApproachingDivider::~ApproachingDivider() {}
140 :
141 :
142 : void
143 179673 : NBNode::ApproachingDivider::execute(const int src, const int dest) {
144 : assert((int)myApproaching.size() > src);
145 : // get the origin edge
146 179673 : NBEdge* incomingEdge = myApproaching[src];
147 179673 : if (incomingEdge->getStep() == NBEdge::EdgeBuildingStep::LANES2LANES_DONE || incomingEdge->getStep() == NBEdge::EdgeBuildingStep::LANES2LANES_USER) {
148 66724 : return;
149 : }
150 113116 : if (myAvailableLanes.size() == 0) {
151 : return;
152 : }
153 113201 : std::vector<int> approachingLanes = incomingEdge->getConnectionLanes(myCurrentOutgoing, myIsBikeEdge || incomingEdge->getPermissions() == SVC_BICYCLE);
154 113011 : 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 112949 : int numConnections = (int)approachingLanes.size();
164 : double factor = 1;
165 : const bool rightOnRed = incomingEdge->getToNode()->getType() == SumoXMLNodeType::TRAFFIC_LIGHT_RIGHT_ON_RED;
166 112949 : 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 4759 : (incomingEdge->getToNode()->isTLControlled() && !rightOnRed)
171 : // - there are no incoming edges to the right
172 40605 : || src == 0
173 : // - a minor straight road is likely in conflict anyway
174 20697 : || (incomingEdge->getJunctionPriority(incomingEdge->getToNode()) == NBEdge::MINOR_ROAD && !rightOnRed))) {
175 33908 : numConnections = (int)myAvailableLanes.size();
176 33908 : factor = (double)approachingLanes.size() / (double)numConnections;
177 33908 : if (factor > 0.5) {
178 : factor = 1;
179 : }
180 : }
181 112949 : std::deque<int>* approachedLanes = spread(numConnections, dest);
182 : assert(approachedLanes->size() <= myAvailableLanes.size());
183 : // set lanes
184 112949 : const int maxFrom = (int)approachingLanes.size() - 1;
185 242187 : 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 129238 : int fromLane = approachingLanes[MIN2((int)(i * factor), maxFrom)];
189 129238 : int approached = myAvailableLanes[(*approachedLanes)[i]];
190 258476 : incomingEdge->setConnection(fromLane, myCurrentOutgoing, approached, NBEdge::Lane2LaneInfoType::COMPUTED);
191 : }
192 112949 : delete approachedLanes;
193 : }
194 :
195 :
196 : std::deque<int>*
197 112949 : NBNode::ApproachingDivider::spread(int numLanes, int dest) const {
198 112949 : 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 112949 : if (numLanes == 1) {
202 : ret->push_back(dest);
203 101178 : return ret;
204 : }
205 :
206 11771 : 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 16295 : 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 12213 : 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 12211 : if (dest + loffset >= numOutgoingLanes) {
228 6405 : loffset -= 1;
229 6405 : roffset += 1;
230 13232 : for (int i = 0; i < (int)ret->size(); i++) {
231 6827 : (*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 12211 : ret->push_back(dest + loffset);
237 12211 : noSet++;
238 12211 : loffset += 1;
239 :
240 : // as above
241 12211 : if (numOutgoingLanes == noSet) {
242 : return ret;
243 : }
244 :
245 : // now we try to append the next lane to the right side, when needed
246 4524 : 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 4078 : if (dest < roffset) {
250 977 : loffset += 1;
251 977 : roffset -= 1;
252 3003 : for (int i = 0; i < (int)ret->size(); i++) {
253 2026 : (*ret)[i] = (*ret)[i] + 1;
254 : }
255 : }
256 4078 : ret->push_front(dest - roffset);
257 4078 : noSet++;
258 4078 : roffset += 1;
259 : }
260 : }
261 : return ret;
262 : }
263 :
264 :
265 : /* -------------------------------------------------------------------------
266 : * NBNode::Crossing-methods
267 : * ----------------------------------------------------------------------- */
268 3122 : NBNode::Crossing::Crossing(const NBNode* _node, const EdgeVector& _edges, double _width, bool _priority, int _customTLIndex, int _customTLIndex2, const PositionVector& _customShape) :
269 : Parameterised(),
270 3122 : node(_node),
271 3122 : edges(_edges),
272 3122 : customWidth(_width),
273 3122 : width(_width),
274 3122 : priority(_priority),
275 : customShape(_customShape),
276 3122 : tlLinkIndex(_customTLIndex),
277 3122 : tlLinkIndex2(_customTLIndex2),
278 3122 : customTLIndex(_customTLIndex),
279 3122 : customTLIndex2(_customTLIndex2),
280 3122 : valid(true) {
281 3122 : }
282 :
283 :
284 : /* -------------------------------------------------------------------------
285 : * NBNode-methods
286 : * ----------------------------------------------------------------------- */
287 41382 : NBNode::NBNode(const std::string& id, const Position& position,
288 41382 : SumoXMLNodeType type) :
289 82764 : Named(StringUtils::convertUmlaute(id)),
290 41382 : myPosition(position),
291 41382 : myType(type),
292 41382 : myDistrict(nullptr),
293 41382 : myHaveCustomPoly(false),
294 41382 : myRequest(nullptr),
295 41382 : myRadius(UNSPECIFIED_RADIUS),
296 41382 : myKeepClear(OptionsCont::getOptions().getBool("default.junctions.keep-clear")),
297 41383 : myRightOfWay(SUMOXMLDefinitions::RightOfWayValues.get(OptionsCont::getOptions().getString("default.right-of-way"))),
298 41382 : myFringeType(FringeType::DEFAULT),
299 41382 : myDiscardAllCrossings(false),
300 41382 : myCrossingsLoadedFromSumoNet(0),
301 41382 : myDisplacementError(0),
302 41382 : myIsBentPriority(false),
303 41382 : myTypeWasGuessed(false) {
304 41382 : if (!SUMOXMLDefinitions::isValidNetID(myID)) {
305 4 : throw ProcessError(TLF("Invalid node id '%'.", myID));
306 : }
307 41386 : }
308 :
309 :
310 47839 : NBNode::NBNode(const std::string& id, const Position& position, NBDistrict* district) :
311 95678 : Named(StringUtils::convertUmlaute(id)),
312 47839 : myPosition(position),
313 47839 : myType(district == nullptr ? SumoXMLNodeType::UNKNOWN : SumoXMLNodeType::DISTRICT),
314 47839 : myDistrict(district),
315 47839 : myHaveCustomPoly(false),
316 47839 : myRequest(nullptr),
317 47839 : myRadius(UNSPECIFIED_RADIUS),
318 47839 : myKeepClear(OptionsCont::getOptions().getBool("default.junctions.keep-clear")),
319 47839 : myRightOfWay(SUMOXMLDefinitions::RightOfWayValues.get(OptionsCont::getOptions().getString("default.right-of-way"))),
320 47839 : myFringeType(FringeType::DEFAULT),
321 47839 : myDiscardAllCrossings(false),
322 47839 : myCrossingsLoadedFromSumoNet(0),
323 47839 : myDisplacementError(0),
324 47839 : myIsBentPriority(false),
325 47839 : myTypeWasGuessed(false) {
326 47839 : if (!SUMOXMLDefinitions::isValidNetID(myID)) {
327 0 : throw ProcessError(TLF("Invalid node id '%'.", myID));
328 : }
329 47839 : }
330 :
331 :
332 178440 : NBNode::~NBNode() {
333 89220 : delete myRequest;
334 356880 : }
335 :
336 :
337 : void
338 6266 : NBNode::reinit(const Position& position, SumoXMLNodeType type,
339 : bool updateEdgeGeometries) {
340 6266 : myPosition = position;
341 : // patch type
342 6266 : myType = type;
343 6266 : if (!isTrafficLight(myType)) {
344 5892 : removeTrafficLights();
345 : }
346 6266 : if (updateEdgeGeometries) {
347 2898 : for (EdgeVector::iterator i = myIncomingEdges.begin(); i != myIncomingEdges.end(); i++) {
348 1685 : PositionVector geom = (*i)->getGeometry();
349 1685 : geom[-1] = myPosition;
350 1685 : (*i)->setGeometry(geom);
351 1685 : }
352 2900 : for (EdgeVector::iterator i = myOutgoingEdges.begin(); i != myOutgoingEdges.end(); i++) {
353 1687 : PositionVector geom = (*i)->getGeometry();
354 1687 : geom[0] = myPosition;
355 1687 : (*i)->setGeometry(geom);
356 1687 : }
357 : }
358 6266 : }
359 :
360 :
361 :
362 : // ----------- Applying offset
363 : void
364 49952 : NBNode::reshiftPosition(double xoff, double yoff) {
365 : myPosition.add(xoff, yoff, 0);
366 49952 : myPoly.add(xoff, yoff, 0);
367 49959 : for (auto& wacs : myWalkingAreaCustomShapes) {
368 7 : wacs.shape.add(xoff, yoff, 0);
369 : }
370 50228 : for (auto& c : myCrossings) {
371 276 : c->customShape.add(xoff, yoff, 0);
372 : }
373 49952 : }
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 26294 : NBNode::addTrafficLight(NBTrafficLightDefinition* tlDef) {
397 : myTrafficLights.insert(tlDef);
398 : // rail signals receive a temporary traffic light in order to set connection tl-linkIndex
399 26294 : if (!isTrafficLight(myType) && myType != SumoXMLNodeType::RAIL_SIGNAL && myType != SumoXMLNodeType::RAIL_CROSSING) {
400 3657 : myType = SumoXMLNodeType::TRAFFIC_LIGHT;
401 : }
402 26294 : }
403 :
404 :
405 : void
406 6086 : NBNode::removeTrafficLight(NBTrafficLightDefinition* tlDef) {
407 6086 : tlDef->removeNode(this);
408 : myTrafficLights.erase(tlDef);
409 6086 : }
410 :
411 :
412 : void
413 22775 : NBNode::removeTrafficLights(bool setAsPriority) {
414 : std::set<NBTrafficLightDefinition*> trafficLights = myTrafficLights; // make a copy because we will modify the original
415 24116 : for (std::set<NBTrafficLightDefinition*>::const_iterator i = trafficLights.begin(); i != trafficLights.end(); ++i) {
416 1341 : removeTrafficLight(*i);
417 : }
418 22775 : if (setAsPriority) {
419 24 : myType = myRequest != nullptr ? SumoXMLNodeType::PRIORITY : (
420 3 : myType == SumoXMLNodeType::TRAFFIC_LIGHT_NOJUNCTION ? SumoXMLNodeType::NOJUNCTION : SumoXMLNodeType::DEAD_END);
421 : }
422 22775 : }
423 :
424 :
425 : void
426 1593 : NBNode::invalidateTLS(NBTrafficLightLogicCont& tlCont, bool removedConnections, bool addedConnections) {
427 1593 : if (isTLControlled()) {
428 : std::set<NBTrafficLightDefinition*> oldDefs(myTrafficLights);
429 1274 : for (std::set<NBTrafficLightDefinition*>::iterator it = oldDefs.begin(); it != oldDefs.end(); ++it) {
430 637 : NBTrafficLightDefinition* orig = *it;
431 637 : if (dynamic_cast<NBLoadedSUMOTLDef*>(orig) != nullptr) {
432 12 : dynamic_cast<NBLoadedSUMOTLDef*>(orig)->registerModifications(removedConnections, addedConnections);
433 625 : } 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 1593 : }
446 :
447 :
448 : void
449 11340 : NBNode::shiftTLConnectionLaneIndex(NBEdge* edge, int offset, int threshold) {
450 13861 : for (std::set<NBTrafficLightDefinition*>::iterator it = myTrafficLights.begin(); it != myTrafficLights.end(); ++it) {
451 2521 : (*it)->shiftTLConnectionLaneIndex(edge, offset, threshold);
452 : }
453 11340 : }
454 :
455 : // ----------- Prunning the input
456 : int
457 86813 : NBNode::removeSelfLoops(NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tc) {
458 : int ret = 0;
459 : int pos = 0;
460 : EdgeVector::const_iterator j = myIncomingEdges.begin();
461 227517 : while (j != myIncomingEdges.end()) {
462 : // skip edges which are only incoming and not outgoing
463 140704 : if (find(myOutgoingEdges.begin(), myOutgoingEdges.end(), *j) == myOutgoingEdges.end()) {
464 : ++j;
465 140704 : ++pos;
466 140704 : 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 : }
484 86813 : return ret;
485 : }
486 :
487 :
488 : // -----------
489 : void
490 158130 : NBNode::addIncomingEdge(NBEdge* edge) {
491 : assert(edge != 0);
492 158130 : if (find(myIncomingEdges.begin(), myIncomingEdges.end(), edge) == myIncomingEdges.end()) {
493 156263 : myIncomingEdges.push_back(edge);
494 156263 : myAllEdges.push_back(edge);
495 : }
496 158130 : }
497 :
498 :
499 : void
500 158290 : NBNode::addOutgoingEdge(NBEdge* edge) {
501 : assert(edge != 0);
502 158290 : if (find(myOutgoingEdges.begin(), myOutgoingEdges.end(), edge) == myOutgoingEdges.end()) {
503 156422 : myOutgoingEdges.push_back(edge);
504 156422 : myAllEdges.push_back(edge);
505 : }
506 158290 : }
507 :
508 :
509 : bool
510 100982 : NBNode::isSimpleContinuation(bool checkLaneNumbers, bool checkWidth) const {
511 : // one in, one out->continuation
512 100982 : if (myIncomingEdges.size() == 1 && myOutgoingEdges.size() == 1) {
513 15366 : NBEdge* in = myIncomingEdges.front();
514 15366 : NBEdge* out = myOutgoingEdges.front();
515 : // both must have the same number of lanes
516 15358 : return ((!checkLaneNumbers || in->getNumLanes() == out->getNumLanes())
517 28665 : && (!checkWidth || in->getTotalWidth() == out->getTotalWidth()));
518 : }
519 : // two in and two out and both in reverse direction
520 85616 : if (myIncomingEdges.size() == 2 && myOutgoingEdges.size() == 2) {
521 40688 : for (EdgeVector::const_iterator i = myIncomingEdges.begin(); i != myIncomingEdges.end(); i++) {
522 32326 : NBEdge* in = *i;
523 32326 : EdgeVector::const_iterator opposite = find_if(myOutgoingEdges.begin(), myOutgoingEdges.end(), NBContHelper::opposite_finder(in));
524 : // must have an opposite edge
525 32326 : if (opposite == myOutgoingEdges.end()) {
526 13124 : return false;
527 : }
528 : // both must have the same number of lanes
529 21768 : NBContHelper::nextCW(myOutgoingEdges, opposite);
530 21768 : if (checkLaneNumbers && in->getNumLanes() != (*opposite)->getNumLanes()) {
531 : return false;
532 : }
533 19576 : 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 347696 : 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 347696 : bool ok = true;
555 347696 : if ((shapeFlag & INDIRECT_LEFT) != 0) {
556 32 : return indirectLeftShape(begShape, endShape, numPoints);
557 : }
558 347664 : 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 347664 : if (init.size() == 0) {
565 112019 : PositionVector ret;
566 112019 : ret.push_back(begShape.back());
567 112019 : ret.push_back(endShape.front());
568 : return ret;
569 112019 : } else {
570 235645 : return init.bezier(numPoints).smoothedZFront();
571 : }
572 347664 : }
573 :
574 : PositionVector
575 350791 : 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 350791 : const Position beg = begShape.back();
587 350791 : const Position end = endShape.front();
588 : const double dist = beg.distanceTo2D(end);
589 350791 : PositionVector init;
590 350791 : 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 338239 : init.push_back(beg);
602 338239 : 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 28213 : Position center = PositionVector::positionAtOffset2D(beg, end, beg.distanceTo2D(end) / (double) 2.);
608 28213 : center.sub(beg.y() - end.y(), end.x() - beg.x());
609 28213 : init.push_back(center);
610 : } else {
611 : const double EXT = 100;
612 310026 : const double angle = GeomHelper::angleDiff(begShape.angleAt2D(-2), endShape.angleAt2D(0));
613 310026 : PositionVector endShapeBegLine(endShape[0], endShape[1]);
614 310026 : PositionVector begShapeEndLineRev(begShape[-1], begShape[-2]);
615 310026 : endShapeBegLine.extrapolate2D(EXT, true);
616 310026 : 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 310026 : if (fabs(angle) < M_PI / 4.) {
624 : // very low angle: could be an s-shape or a straight line
625 139908 : const double displacementAngle = GeomHelper::angleDiff(begShape.angleAt2D(-2), beg.angleTo2D(end));
626 139908 : const double bendDeg = RAD2DEG(fabs(displacementAngle - angle));
627 139908 : const double halfDistance = dist / 2;
628 139908 : 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 96411 : return PositionVector();
634 43497 : } 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 1809 : ok = false;
645 1809 : if (recordError != nullptr && (shapeFlag & SCURVE_IGNORE) == 0) {
646 1007 : recordError->myDisplacementError = MAX2(recordError->myDisplacementError, (double)fabs(sin(displacementAngle) * dist));
647 : }
648 1809 : return PositionVector();
649 : } else {
650 41688 : const double endLength = begShape[-2].distanceTo2D(begShape[-1]);
651 41688 : const double off1 = endLength + MIN2(extrapolateBeg, halfDistance);
652 83376 : init.push_back(PositionVector::positionAtOffset2D(begShapeEndLineRev[1], begShapeEndLineRev[0], off1));
653 41688 : const double off2 = EXT - MIN2(extrapolateEnd, halfDistance);
654 83376 : 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 170118 : 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 2042 : ok = false;
678 2042 : if (recordError != nullptr && (shapeFlag & SCURVE_IGNORE) == 0) {
679 : // it's unclear if this error can be solved via stretching the intersection.
680 641 : recordError->myDisplacementError = MAX2(recordError->myDisplacementError, (double)1.0);
681 : }
682 2042 : return PositionVector();
683 : }
684 168076 : const double begOffset = begShapeEndLineRev.nearest_offset_to_point2D(intersect);
685 168076 : 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 168076 : const double minControlLength = MIN2((double)1.0, dist / 2);
698 : const double distBeg = intersect.distanceTo2D(beg);
699 : const double distEnd = intersect.distanceTo2D(end);
700 168076 : const bool lengthenBeg = distBeg <= minControlLength;
701 168076 : 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 168076 : 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 168076 : } else if ((shapeFlag & FOUR_CONTROL_POINTS)) {
723 77 : init.push_back(begShapeEndLineRev.positionAtOffset2D(EXT - extrapolateBeg));
724 154 : init.push_back(endShapeBegLine.positionAtOffset2D(EXT - extrapolateEnd));
725 167999 : } else if (lengthenBeg || lengthenEnd) {
726 535 : init.push_back(begShapeEndLineRev.positionAtOffset2D(EXT - minControlLength));
727 1070 : init.push_back(endShapeBegLine.positionAtOffset2D(EXT - minControlLength));
728 167464 : } 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 127469 : && ((shapeFlag & AVOID_INTERSECTING_LEFT_TURNS) != 0
734 122790 : || (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 5998 : const double factor = ((shapeFlag & AVOID_INTERSECTING_LEFT_TURNS) == 0 ? 1
737 4679 : : MIN2(0.6, 16 / dist));
738 10799 : init.push_back(begShapeEndLineRev.positionAtOffset2D(EXT - MIN2(distBeg * factor / 1.2, dist * factor / 1.8)));
739 10663 : init.push_back(endShapeBegLine.positionAtOffset2D(EXT - MIN2(distEnd * factor / 1.2, dist * factor / 1.8)));
740 167464 : } 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 161466 : const double z1 = begShapeEndLineRev.positionAtOffset2D(begOffset).z();
747 161466 : const double z2 = endShapeBegLine.positionAtOffset2D(endOffset).z();
748 161466 : 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 161466 : if ((z1 <= z3 && z2 <= z3) || (z1 >= z3 && z2 >= z3)) {
753 161414 : z = 0.5 * (z1 + z2);
754 : } else {
755 : z = z3;
756 : }
757 : intersect.set(intersect.x(), intersect.y(), z);
758 161466 : init.push_back(intersect);
759 : }
760 : }
761 310026 : }
762 237977 : init.push_back(end);
763 : }
764 : return init;
765 350791 : }
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 183509 : NBNode::computeInternalLaneShape(const NBEdge* fromE, const NBEdge::Connection& con, int numPoints, NBNode* recordError, int shapeFlag) const {
794 183509 : if (con.fromLane >= fromE->getNumLanes()) {
795 0 : throw ProcessError(TLF("Connection '%' starts at a non-existant lane.", con.getDescription(fromE)));
796 : }
797 183509 : if (con.toLane >= con.toEdge->getNumLanes()) {
798 0 : throw ProcessError(TLF("Connection '%' targets a non-existant lane.", con.getDescription(fromE)));
799 : }
800 183509 : PositionVector fromShape = fromE->getLaneShape(con.fromLane);
801 183509 : PositionVector toShape = con.toEdge->getLaneShape(con.toLane);
802 183509 : PositionVector ret;
803 183509 : bool useCustomShape = con.customShape.size() > 0;
804 183509 : if (useCustomShape) {
805 : // ensure that the shape starts and ends at the intersection boundary
806 140 : PositionVector startBorder = fromE->getNodeBorder(this);
807 140 : if (startBorder.size() == 0) {
808 202 : startBorder = fromShape.getOrthogonal(fromShape.back(), 1, true);
809 : }
810 280 : PositionVector tmp = NBEdge::startShapeAt(con.customShape, this, startBorder);
811 140 : 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 140 : 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 60 : } else if (recordError != nullptr) {
819 15 : const double offset = tmp[0].distanceTo2D(fromShape.back());
820 15 : if (offset > fromE->getLaneWidth(con.fromLane) / 2) {
821 4 : WRITE_WARNINGF(TL("Custom shape has distance % to incoming lane for connection %."), offset, con.getDescription(fromE));
822 : }
823 : }
824 140 : PositionVector endBorder = con.toEdge->getNodeBorder(this);
825 140 : if (endBorder.size() == 0) {
826 202 : endBorder = toShape.getOrthogonal(toShape.front(), 1, false);
827 : }
828 280 : ret = NBEdge::startShapeAt(tmp.reverse(), this, endBorder).reverse();
829 140 : if (ret.size() < 2) {
830 0 : WRITE_WARNINGF(TL("Could not use custom shape for connection %."), con.getDescription(fromE));
831 : useCustomShape = false;
832 140 : } 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 90 : } else if (recordError != nullptr) {
836 19 : const double offset = ret[-1].distanceTo2D(toShape.front());
837 19 : if (offset > con.toEdge->getLaneWidth(con.toLane) / 2) {
838 0 : WRITE_WARNINGF(TL("Custom shape has distance % to outgoing lane for connection %."), offset, con.getDescription(fromE));
839 : }
840 : }
841 140 : }
842 140 : }
843 183509 : if (!useCustomShape) {
844 183369 : displaceShapeAtWidthChange(fromE, con, fromShape, toShape);
845 183369 : double extrapolateBeg = 5. * fromE->getNumLanes();
846 183369 : double extrapolateEnd = 5. * con.toEdge->getNumLanes();
847 183369 : LinkDirection dir = getDirection(fromE, con.toEdge);
848 183369 : if (dir == LinkDirection::LEFT || dir == LinkDirection::TURN) {
849 69695 : shapeFlag += AVOID_WIDE_LEFT_TURN;
850 : }
851 183369 : 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 183369 : ret = computeSmoothShape(fromShape, toShape,
860 183369 : numPoints, fromE->getTurnDestination() == con.toEdge,
861 : extrapolateBeg, extrapolateEnd, recordError, shapeFlag);
862 : }
863 183509 : const NBEdge::Lane& lane = fromE->getLaneStruct(con.fromLane);
864 183509 : if (lane.endOffset > 0) {
865 68 : PositionVector beg = lane.shape.getSubpart(lane.shape.length() - lane.endOffset, lane.shape.length());
866 68 : beg.append(ret);
867 : ret = beg;
868 68 : }
869 183509 : if (con.toEdge->isBidiRail() && con.toEdge->getTurnDestination(true)->getEndOffset() > 0) {
870 2 : PositionVector end = toShape.getSubpart(0, con.toEdge->getTurnDestination(true)->getEndOffset());
871 2 : ret.append(end);
872 2 : }
873 183509 : return ret;
874 183509 : }
875 :
876 :
877 : bool
878 303677 : NBNode::isConstantWidthTransition() const {
879 : return (myIncomingEdges.size() == 1
880 26555 : && myOutgoingEdges.size() == 1
881 19386 : && myIncomingEdges[0]->getNumLanes() != myOutgoingEdges[0]->getNumLanes()
882 312247 : && myIncomingEdges[0]->getTotalWidth() == myOutgoingEdges[0]->getTotalWidth());
883 : }
884 :
885 : void
886 183369 : NBNode::displaceShapeAtWidthChange(const NBEdge* from, const NBEdge::Connection& con,
887 : PositionVector& fromShape, PositionVector& toShape) const {
888 183369 : if (isConstantWidthTransition()) {
889 : // displace shapes
890 17 : NBEdge* in = myIncomingEdges[0];
891 17 : NBEdge* out = myOutgoingEdges[0];
892 17 : double outCenter = out->getLaneWidth(con.toLane) / 2;
893 33 : for (int i = 0; i < con.toLane; ++i) {
894 16 : outCenter += out->getLaneWidth(i);
895 : }
896 17 : double inCenter = in->getLaneWidth(con.fromLane) / 2;
897 30 : for (int i = 0; i < con.fromLane; ++i) {
898 13 : inCenter += in->getLaneWidth(i);
899 : }
900 : //std::cout << "displaceShapeAtWidthChange inCenter=" << inCenter << " outCenter=" << outCenter << "\n";
901 : try {
902 17 : 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 14 : fromShape.move2side(inCenter - outCenter);
908 :
909 : }
910 0 : } catch (InvalidArgument&) { }
911 : } else {
912 183352 : SVCPermissions fromP = from->getPermissions(con.fromLane);
913 183352 : SVCPermissions toP = con.toEdge->getPermissions(con.toLane);
914 183352 : if ((fromP & toP) == SVC_BICYCLE && (fromP | toP) != SVC_BICYCLE) {
915 2665 : double shift = (from->getLaneWidth(con.fromLane) - con.toEdge->getLaneWidth(con.toLane)) / 2;
916 2665 : 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 987 : LinkDirection dir = getDirection(from, con.toEdge);
921 987 : if ((dir == LinkDirection::LEFT) || (dir == LinkDirection::PARTLEFT) || (dir == LinkDirection::TURN)) {
922 439 : fromShape.move2side(-shift);
923 : } else {
924 548 : fromShape.move2side(shift);
925 : }
926 1678 : } else if (fromP == SVC_BICYCLE) {
927 : // let connection from dedicated bicycle end on the right side of a mixed lane
928 793 : toShape.move2side(-shift);
929 : }
930 : }
931 : }
932 183369 : }
933 :
934 : bool
935 936686 : NBNode::needsCont(const NBEdge* fromE, const NBEdge* otherFromE,
936 : const NBEdge::Connection& c, const NBEdge::Connection& otherC, bool checkOnlyTLS) const {
937 936686 : const NBEdge* toE = c.toEdge;
938 936686 : const NBEdge* otherToE = otherC.toEdge;
939 :
940 936686 : if (!checkOnlyTLS) {
941 917559 : if (myType == SumoXMLNodeType::RIGHT_BEFORE_LEFT
942 : || myType == SumoXMLNodeType::LEFT_BEFORE_RIGHT
943 917559 : || myType == SumoXMLNodeType::ALLWAY_STOP) {
944 : return false;
945 : }
946 816349 : LinkDirection d1 = getDirection(fromE, toE);
947 816349 : const bool thisRight = (d1 == LinkDirection::RIGHT || d1 == LinkDirection::PARTRIGHT);
948 1103595 : const bool rightTurnConflict = (thisRight &&
949 287246 : NBNode::rightTurnConflict(fromE, toE, c.fromLane, otherFromE, otherToE, otherC.fromLane));
950 816349 : if (thisRight && !rightTurnConflict) {
951 : return false;
952 : }
953 529468 : if (myRequest && myRequest->indirectLeftTurnConflict(fromE, c, otherFromE, otherC, false)) {
954 : return true;
955 : }
956 529436 : 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 187136 : LinkDirection d2 = getDirection(otherFromE, otherToE);
961 187136 : if (d2 == LinkDirection::TURN) {
962 : return false;
963 : }
964 169766 : if (fromE == otherFromE && !thisRight) {
965 : // ignore same edge links except for right-turns
966 : return false;
967 : }
968 168242 : if (thisRight && d2 != LinkDirection::STRAIGHT) {
969 : return false;
970 : }
971 : }
972 187247 : if (c.tlID != "") {
973 : assert(myTrafficLights.size() > 0 || myType == SumoXMLNodeType::RAIL_CROSSING || myType == SumoXMLNodeType::RAIL_SIGNAL);
974 98842 : for (std::set<NBTrafficLightDefinition*>::const_iterator it = myTrafficLights.begin(); it != myTrafficLights.end(); ++it) {
975 60438 : if ((*it)->needsCont(fromE, toE, otherFromE, otherToE)) {
976 : return true;
977 : }
978 : }
979 : return false;
980 : }
981 127007 : if (fromE->getJunctionPriority(this) > 0 && otherFromE->getJunctionPriority(this) > 0) {
982 25967 : return mustBrake(fromE, toE, c.fromLane, c.toLane, false);
983 : }
984 : return false;
985 : }
986 :
987 : bool
988 1582885 : NBNode::tlsContConflict(const NBEdge* from, const NBEdge::Connection& c,
989 : const NBEdge* foeFrom, const NBEdge::Connection& foe) const {
990 204007 : return (foe.haveVia && isTLControlled() && c.tlLinkIndex >= 0 && foe.tlLinkIndex >= 0
991 88323 : && !foeFrom->isTurningDirectionAt(foe.toEdge)
992 48153 : && foes(from, c.toEdge, foeFrom, foe.toEdge)
993 1602012 : && !needsCont(foeFrom, from, foe, c, true));
994 : }
995 :
996 :
997 : void
998 20298 : NBNode::removeJoinedTrafficLights() {
999 : std::set<NBTrafficLightDefinition*> trafficLights = myTrafficLights; // make a copy because we will modify the original
1000 20374 : 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 76 : 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 20298 : }
1010 :
1011 :
1012 : void
1013 71806 : NBNode::computeLogic(const NBEdgeCont& ec) {
1014 71806 : delete myRequest; // possibly recomputation step
1015 71806 : myRequest = nullptr;
1016 71806 : if (myIncomingEdges.size() == 0 || myOutgoingEdges.size() == 0) {
1017 : // no logic if nothing happens here
1018 10771 : myType = SumoXMLNodeType::DEAD_END;
1019 10771 : removeJoinedTrafficLights();
1020 10771 : return;
1021 : }
1022 : // compute the logic if necessary or split the junction
1023 61035 : if (myType != SumoXMLNodeType::NOJUNCTION && myType != SumoXMLNodeType::DISTRICT && myType != SumoXMLNodeType::TRAFFIC_LIGHT_NOJUNCTION) {
1024 : // build the request
1025 60898 : myRequest = new NBRequest(ec, this, myAllEdges, myIncomingEdges, myOutgoingEdges, myBlockedConnections);
1026 : // check whether it is not too large
1027 60898 : int numConnections = numNormalConnections();
1028 60898 : 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 60898 : } else if (numConnections == 0) {
1040 9527 : delete myRequest;
1041 9527 : myRequest = nullptr;
1042 9527 : myType = SumoXMLNodeType::DEAD_END;
1043 9527 : removeJoinedTrafficLights();
1044 : } else {
1045 51371 : myRequest->buildBitfieldLogic();
1046 : }
1047 : }
1048 : }
1049 :
1050 :
1051 : void
1052 71806 : NBNode::computeLogic2(bool checkLaneFoes) {
1053 71806 : if (myRequest != nullptr) {
1054 51371 : myRequest->computeLogic(checkLaneFoes);
1055 : }
1056 71806 : }
1057 :
1058 : void
1059 71806 : NBNode::computeKeepClear() {
1060 71806 : if (hasConflict()) {
1061 24051 : 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 24049 : } else if (geometryLike() && myCrossings.size() == 0 && !isTLControlled()) {
1069 : int linkIndex = 0;
1070 935 : for (NBEdge* incoming : myIncomingEdges) {
1071 : std::vector<NBEdge::Connection>& connections = incoming->getConnections();
1072 1956 : for (NBEdge::Connection& c : connections) {
1073 1337 : if (c.keepClear == KEEPCLEAR_UNSPECIFIED && myRequest->hasConflictAtLink(linkIndex)) {
1074 656 : const LinkState linkState = getLinkState(incoming, c.toEdge, c.fromLane, c.toLane, c.mayDefinitelyPass, c.tlID);
1075 656 : if (linkState == LINKSTATE_MAJOR) {
1076 397 : c.keepClear = KEEPCLEAR_FALSE;
1077 : }
1078 : }
1079 : }
1080 619 : linkIndex++;
1081 : }
1082 : }
1083 : }
1084 71806 : }
1085 :
1086 :
1087 : bool
1088 50186 : NBNode::writeLogic(OutputDevice& into) const {
1089 50186 : if (myRequest) {
1090 50087 : myRequest->writeLogic(into);
1091 50087 : 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 71991 : NBNode::hasConflict() const {
1118 71991 : if (myRequest == nullptr) {
1119 : return false;
1120 : } else {
1121 51553 : 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 77 : NBNode::updateSurroundingGeometry() {
1143 77 : NBTurningDirectionsComputer::computeTurnDirectionsForNode(this, false);
1144 77 : sortEdges(false);
1145 77 : computeNodeShape(-1);
1146 608 : for (NBEdge* edge : myAllEdges) {
1147 531 : edge->computeEdgeShape();
1148 : }
1149 77 : }
1150 :
1151 : void
1152 109431 : NBNode::computeNodeShape(double mismatchThreshold) {
1153 109431 : if (myHaveCustomPoly) {
1154 : return;
1155 : }
1156 109397 : if (myIncomingEdges.size() == 0 && myOutgoingEdges.size() == 0) {
1157 : // may be an intermediate step during network editing
1158 2794 : myPoly.clear();
1159 2794 : myPoly.push_back(myPosition);
1160 2794 : return;
1161 : }
1162 213206 : if (OptionsCont::getOptions().getFloat("default.junctions.radius") < 0) {
1163 : // skip shape computation by option
1164 : return;
1165 : }
1166 : try {
1167 106598 : NBNodeShapeComputer computer(*this);
1168 213196 : myPoly = computer.compute(OptionsCont::getOptions().getBool("junctions.minimal-shape"));
1169 319621 : if (myRadius == UNSPECIFIED_RADIUS && !OptionsCont::getOptions().isDefault("default.junctions.radius")) {
1170 63 : myRadius = computer.getRadius();
1171 : }
1172 106598 : if (myPoly.size() > 0) {
1173 : PositionVector tmp = myPoly;
1174 106598 : tmp.push_back_noDoublePos(tmp[0]); // need closed shape
1175 : if (mismatchThreshold >= 0
1176 66144 : && !tmp.around(myPosition)
1177 127126 : && tmp.distance2D(myPosition) > mismatchThreshold) {
1178 243 : WRITE_WARNINGF(TL("Shape for junction '%' has distance % to its given position."), myID, tmp.distance2D(myPosition));
1179 : }
1180 106598 : }
1181 106598 : } 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 0 : myPoly.clear();
1185 0 : myPoly.push_back(myPosition);
1186 0 : }
1187 : }
1188 :
1189 :
1190 : void
1191 71814 : NBNode::computeLanes2Lanes() {
1192 : // special case a):
1193 : // one in, one out, the outgoing has more lanes
1194 71814 : if (myIncomingEdges.size() == 1 && myOutgoingEdges.size() == 1) {
1195 19831 : NBEdge* in = myIncomingEdges[0];
1196 19831 : NBEdge* out = myOutgoingEdges[0];
1197 : // check if it's not the turnaround
1198 19831 : if (in->getTurnDestination() == out) {
1199 : // will be added later or not...
1200 12426 : return;
1201 : }
1202 : int inOffset, outOffset, addedLanes;
1203 8006 : getReduction(out, in, outOffset, inOffset, addedLanes);
1204 : if (in->getStep() <= NBEdge::EdgeBuildingStep::LANES2EDGES
1205 5329 : && addedLanes > 0
1206 8619 : && in->isConnectedTo(out)) {
1207 : #ifdef DEBUG_CONNECTION_GUESSING
1208 : if (DEBUGCOND) {
1209 : std::cout << "l2l node=" << getID() << " specialCase a\n";
1210 : }
1211 : #endif
1212 601 : const int addedRight = addedLanesRight(out, addedLanes);
1213 601 : const int addedLeft = addedLanes - addedRight;
1214 : // "straight" connections
1215 1889 : for (int i = inOffset; i < in->getNumLanes(); ++i) {
1216 2576 : in->setConnection(i, out, i - inOffset + outOffset + addedRight, NBEdge::Lane2LaneInfoType::COMPUTED);
1217 : }
1218 : // connect extra lane on the right
1219 667 : for (int i = 0; i < addedRight; ++i) {
1220 132 : in->setConnection(inOffset, out, outOffset + i, NBEdge::Lane2LaneInfoType::COMPUTED);
1221 : }
1222 : // connect extra lane on the left
1223 601 : const int inLeftMost = in->getNumLanes() - 1;
1224 601 : const int outOffset2 = outOffset + addedRight + in->getNumLanes() - inOffset;
1225 1175 : for (int i = 0; i < addedLeft; ++i) {
1226 1148 : in->setConnection(inLeftMost, out, outOffset2 + i, NBEdge::Lane2LaneInfoType::COMPUTED);
1227 : }
1228 601 : if (out->getSpecialLane(SVC_BICYCLE) >= 0) {
1229 26 : recheckVClassConnections(out);
1230 : }
1231 601 : 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 59388 : if (myIncomingEdges.size() == 2 && myOutgoingEdges.size() == 1) {
1238 4728 : NBEdge* const out = myOutgoingEdges[0];
1239 4728 : NBEdge* in1 = myIncomingEdges[0];
1240 4728 : NBEdge* in2 = myIncomingEdges[1];
1241 4728 : const int outOffset = MAX2(0, out->getFirstNonPedestrianNonBicycleLaneIndex(FORWARD, true));
1242 4728 : int in1Offset = MAX2(0, in1->getFirstNonPedestrianNonBicycleLaneIndex(FORWARD, true));
1243 4728 : int in2Offset = MAX2(0, in2->getFirstNonPedestrianNonBicycleLaneIndex(FORWARD, true));
1244 4728 : if (in1->getNumLanes() + in2->getNumLanes() - in1Offset - in2Offset == out->getNumLanes() - outOffset
1245 171 : && (in1->getStep() <= NBEdge::EdgeBuildingStep::LANES2EDGES)
1246 48 : && (in2->getStep() <= NBEdge::EdgeBuildingStep::LANES2EDGES)
1247 48 : && in1 != out
1248 48 : && in2 != out
1249 48 : && in1->isConnectedTo(out)
1250 47 : && in2->isConnectedTo(out)
1251 47 : && in1->getSpecialLane(SVC_BICYCLE) == -1
1252 45 : && in2->getSpecialLane(SVC_BICYCLE) == -1
1253 45 : && out->getSpecialLane(SVC_BICYCLE) == -1
1254 45 : && in1->getSpecialLane(SVC_TRAM) == -1
1255 44 : && in2->getSpecialLane(SVC_TRAM) == -1
1256 44 : && out->getSpecialLane(SVC_TRAM) == -1
1257 4772 : && 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 25 : double a1 = in1->getAngleAtNode(this);
1265 25 : double a2 = in2->getAngleAtNode(this);
1266 25 : double ccw = GeomHelper::getCCWAngleDiff(a1, a2);
1267 25 : double cw = GeomHelper::getCWAngleDiff(a1, a2);
1268 25 : if (ccw > cw) {
1269 : std::swap(in1, in2);
1270 : std::swap(in1Offset, in2Offset);
1271 : }
1272 25 : in1->addLane2LaneConnections(in1Offset, out, outOffset, in1->getNumLanes() - in1Offset, NBEdge::Lane2LaneInfoType::COMPUTED, true);
1273 25 : in2->addLane2LaneConnections(in2Offset, out, in1->getNumLanes() + outOffset - in1Offset, in2->getNumLanes() - in2Offset, NBEdge::Lane2LaneInfoType::COMPUTED, true);
1274 25 : 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 59363 : if (myIncomingEdges.size() == 1 && myOutgoingEdges.size() == 2) {
1284 6305 : NBEdge* in = myIncomingEdges[0];
1285 6305 : NBEdge* out1 = myOutgoingEdges[0];
1286 6305 : NBEdge* out2 = myOutgoingEdges[1];
1287 6305 : const int inOffset = MAX2(0, in->getFirstNonPedestrianNonBicycleLaneIndex(FORWARD, true));
1288 6305 : int out1Offset = MAX2(0, out1->getFirstNonPedestrianNonBicycleLaneIndex(FORWARD, true));
1289 6305 : int out2Offset = MAX2(0, out2->getFirstNonPedestrianNonBicycleLaneIndex(FORWARD, true));
1290 6305 : const int deltaLaneSum = (out2->getNumLanes() + out1->getNumLanes() - out1Offset - out2Offset) - (in->getNumLanes() - inOffset);
1291 17661 : if ((deltaLaneSum == 0 || (deltaLaneSum == 1 && in->getPermissionVariants(inOffset, in->getNumLanes()).size() == 1))
1292 6036 : && (in->getStep() <= NBEdge::EdgeBuildingStep::LANES2EDGES)
1293 4092 : && in != out1
1294 4092 : && in != out2
1295 4092 : && in->isConnectedTo(out1)
1296 1263 : && in->isConnectedTo(out2)
1297 983 : && !in->isTurningDirectionAt(out1)
1298 7212 : && !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 771 : if (NBContHelper::relative_outgoing_edge_sorter(in)(out2, out1)) {
1307 : std::swap(out1, out2);
1308 : std::swap(out1Offset, out2Offset);
1309 : }
1310 771 : in->addLane2LaneConnections(inOffset, out1, out1Offset, out1->getNumLanes() - out1Offset, NBEdge::Lane2LaneInfoType::COMPUTED, true);
1311 771 : in->addLane2LaneConnections(out1->getNumLanes() + inOffset - out1Offset - deltaLaneSum, out2, out2Offset, out2->getNumLanes() - out2Offset, NBEdge::Lane2LaneInfoType::COMPUTED, false);
1312 771 : if (in->getSpecialLane(SVC_BICYCLE) >= 0) {
1313 15 : recheckVClassConnections(out1);
1314 15 : 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 58592 : 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 58591 : if (myIncomingEdges.size() == 1 && myOutgoingEdges.size() == 1) {
1349 7404 : NBEdge* in = myIncomingEdges[0];
1350 7404 : NBEdge* out = myOutgoingEdges[0];
1351 : // check if it's not the turnaround
1352 7404 : if (in->getTurnDestination() == out) {
1353 : // will be added later or not...
1354 2388 : return;
1355 : }
1356 : int inOffset, outOffset, reduction;
1357 7404 : getReduction(in, out, inOffset, outOffset, reduction);
1358 : if (in->getStep() <= NBEdge::EdgeBuildingStep::LANES2EDGES
1359 4727 : && reduction >= 0
1360 4715 : && in != out
1361 12119 : && in->isConnectedTo(out)) {
1362 : #ifdef DEBUG_CONNECTION_GUESSING
1363 : if (DEBUGCOND) {
1364 : std::cout << "l2l node=" << getID() << " specialCase f\n";
1365 : }
1366 : #endif
1367 : // in case of reduced lane number, let the rightmost lanse end
1368 2388 : inOffset += reduction;
1369 6151 : for (int i = outOffset; i < out->getNumLanes(); ++i) {
1370 7526 : 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 2388 : recheckVClassConnections(out);
1374 2388 : 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 167948 : for (NBEdge* currentOutgoing : myOutgoingEdges) {
1384 : // get the information about edges that do approach this edge
1385 111745 : getEdgesThatApproach(currentOutgoing, approaching);
1386 111745 : const int numApproaching = (int)approaching.size();
1387 111745 : if (numApproaching != 0) {
1388 87291 : ApproachingDivider divider(approaching, currentOutgoing);
1389 87291 : Bresenham::compute(÷r, numApproaching, divider.numAvailableLanes());
1390 87291 : }
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 111745 : 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 252131 : for (int i = 0; i < currentOutgoing->getNumLanes(); i++) {
1408 140405 : const NBEdge::Lane& lane = currentOutgoing->getLanes()[i];
1409 196 : if ((lane.changeLeft != SVCAll && lane.changeLeft != SVC_IGNORING && i + 1 < currentOutgoing->getNumLanes())
1410 140583 : || (lane.changeRight != SVCAll && lane.changeRight != SVC_IGNORING && i > 0)) {
1411 : targetProhibitsChange = true;
1412 : break;
1413 : }
1414 : }
1415 111745 : 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 56203 : if (myType == SumoXMLNodeType::RAIL_CROSSING) {
1454 1072 : for (EdgeVector::const_iterator i = myIncomingEdges.begin(); i != myIncomingEdges.end(); i++) {
1455 788 : const std::vector<NBEdge::Connection> cons = (*i)->getConnections();
1456 1313 : for (std::vector<NBEdge::Connection>::const_iterator k = cons.begin(); k != cons.end(); ++k) {
1457 525 : if (getDirection(*i, (*k).toEdge) == LinkDirection::TURN) {
1458 0 : (*i)->removeFromConnections((*k).toEdge);
1459 : }
1460 : }
1461 788 : }
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 56203 : if (myOutgoingEdges.size() == 0) {
1468 13168 : for (NBEdge* incoming : myIncomingEdges) {
1469 7123 : 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 : }
1485 :
1486 : void
1487 114189 : NBNode::recheckVClassConnections(NBEdge* currentOutgoing) {
1488 114189 : const int bikeLaneTarget = currentOutgoing->getSpecialLane(SVC_BICYCLE);
1489 :
1490 : // ensure that all modes have a connection if possible
1491 406987 : for (NBEdge* incoming : myIncomingEdges) {
1492 585596 : 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 112598 : 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 406290 : for (std::vector<NBEdge::Connection>::const_iterator k = elv.begin(); k != elv.end(); ++k) {
1499 : const NBEdge::Connection& c = *k;
1500 293692 : if (c.toEdge == currentOutgoing && c.toLane >= 0) {
1501 125833 : 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 125833 : unsatisfied &= ~satisfied;
1504 : }
1505 : }
1506 112598 : 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 4210 : while (unsatisfied != 0 && fromLane < incoming->getNumLanes()) {
1514 2691 : if ((incoming->getPermissions(fromLane) & unsatisfied) != 0) {
1515 6000 : for (int toLane = 0; toLane < currentOutgoing->getNumLanes(); ++toLane) {
1516 4481 : const SVCPermissions satisfied = incoming->getPermissions(fromLane) & currentOutgoing->getPermissions(toLane) & unsatisfied;
1517 4481 : if (satisfied != 0 && !incoming->getLaneStruct(fromLane).connectionsDone) {
1518 1519 : if (incoming->hasConnectionTo(currentOutgoing, toLane)
1519 363 : && unsatisfied == SVC_TRAM
1520 1525 : && 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 5 : 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 1514 : bool mayUseSameDestination = unsatisfied == SVC_TRAM || (unsatisfied & SVC_PASSENGER) != 0;
1537 1514 : 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 1514 : unsatisfied &= ~satisfied;
1544 : }
1545 : }
1546 : }
1547 : }
1548 2691 : 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 292798 : LinkDirection dir = getDirection(incoming, currentOutgoing);
1563 : if (incoming->getStep() <= NBEdge::EdgeBuildingStep::LANES2LANES_DONE
1564 292798 : && ((bikeLaneTarget >= 0 && dir != LinkDirection::TURN)
1565 207842 : || dir == LinkDirection::RIGHT || dir == LinkDirection::PARTRIGHT || dir == LinkDirection::STRAIGHT)) {
1566 : bool builtConnection = false;
1567 257337 : for (int i = 0; i < (int)incoming->getNumLanes(); i++) {
1568 144893 : if (incoming->getPermissions(i) == SVC_BICYCLE
1569 144893 : && incoming->getConnectionsFromLane(i, currentOutgoing).size() == 0) {
1570 : // find a dedicated bike lane as target
1571 559 : if (bikeLaneTarget >= 0) {
1572 158 : incoming->setConnection(i, currentOutgoing, bikeLaneTarget, NBEdge::Lane2LaneInfoType::COMPUTED);
1573 : builtConnection = true;
1574 : } else {
1575 : // use any lane that allows bicycles
1576 970 : for (int i2 = 0; i2 < (int)currentOutgoing->getNumLanes(); i2++) {
1577 661 : if ((currentOutgoing->getPermissions(i2) & SVC_BICYCLE) != 0) {
1578 : // possibly a double-connection
1579 171 : const bool allowDouble = (incoming->getPermissions(i) == SVC_BICYCLE
1580 171 : && (dir == LinkDirection::RIGHT || dir == LinkDirection::PARTRIGHT || dir == LinkDirection::STRAIGHT));
1581 171 : incoming->setConnection(i, currentOutgoing, i2, NBEdge::Lane2LaneInfoType::COMPUTED, allowDouble);
1582 : builtConnection = true;
1583 171 : break;
1584 : }
1585 : }
1586 : }
1587 : }
1588 : }
1589 224888 : if (!builtConnection && bikeLaneTarget >= 0
1590 112444 : && 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 557 : if (dir == LinkDirection::TURN || dir == LinkDirection::LEFT || dir == LinkDirection::PARTLEFT) {
1596 : std::swap(start, end);
1597 : inc = -1;
1598 : }
1599 988 : for (int i = start; i < end; i += inc) {
1600 434 : 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 114189 : }
1609 :
1610 : void
1611 15458 : NBNode::getReduction(const NBEdge* in, const NBEdge* out, int& inOffset, int& outOffset, int& reduction) const {
1612 15458 : inOffset = MAX2(0, in->getFirstNonPedestrianNonBicycleLaneIndex(FORWARD, true));
1613 15458 : outOffset = MAX2(0, out->getFirstNonPedestrianNonBicycleLaneIndex(FORWARD, true));
1614 15458 : reduction = (in->getNumLanes() - inOffset) - (out->getNumLanes() - outOffset);
1615 15458 : }
1616 :
1617 :
1618 : int
1619 601 : NBNode::addedLanesRight(NBEdge* out, int addedLanes) const {
1620 601 : if (out->isOffRamp()) {
1621 : return addedLanes;
1622 : }
1623 : NBNode* to = out->getToNode();
1624 : // check whether a right lane ends
1625 : if (to->getIncomingEdges().size() == 1
1626 594 : && to->getOutgoingEdges().size() == 1) {
1627 : int inOffset, outOffset, reduction;
1628 48 : to->getReduction(out, to->getOutgoingEdges()[0], inOffset, outOffset, reduction);
1629 48 : if (reduction > 0) {
1630 12 : return reduction;
1631 : }
1632 : }
1633 : // check for the presence of right and left turns at the next intersection
1634 : int outLanesRight = 0;
1635 : int outLanesLeft = 0;
1636 : int outLanesStraight = 0;
1637 2580 : for (NBEdge* succ : to->getOutgoingEdges()) {
1638 1998 : if (out->isConnectedTo(succ)) {
1639 1806 : const int outOffset = MAX2(0, succ->getFirstNonPedestrianNonBicycleLaneIndex(FORWARD, true));
1640 1806 : const int usableLanes = succ->getNumLanes() - outOffset;
1641 1806 : LinkDirection dir = to->getDirection(out, succ);
1642 1806 : if (dir == LinkDirection::STRAIGHT) {
1643 536 : outLanesStraight += usableLanes;
1644 1270 : } else if (dir == LinkDirection::RIGHT || dir == LinkDirection::PARTRIGHT) {
1645 445 : outLanesRight += usableLanes;
1646 : } else {
1647 825 : outLanesLeft += usableLanes;
1648 : }
1649 : }
1650 : }
1651 582 : const int outOffset = MAX2(0, out->getFirstNonPedestrianNonBicycleLaneIndex(FORWARD, true));
1652 582 : const int usableLanes = out->getNumLanes() - outOffset;
1653 582 : int addedTurnLanes = MIN3(
1654 : addedLanes,
1655 : MAX2(0, usableLanes - outLanesStraight),
1656 : outLanesRight + outLanesLeft);
1657 582 : if (outLanesLeft == 0) {
1658 : return addedTurnLanes;
1659 : } else {
1660 440 : return MIN2(addedTurnLanes / 2, outLanesRight);
1661 : }
1662 : }
1663 :
1664 :
1665 : bool
1666 44 : NBNode::isLongEnough(NBEdge* out, double minLength) {
1667 : double seen = out->getLoadedLength();
1668 45 : while (seen < minLength) {
1669 : // advance along trivial continuations
1670 : if (out->getToNode()->getOutgoingEdges().size() != 1
1671 20 : || out->getToNode()->getIncomingEdges().size() != 1) {
1672 : return false;
1673 : } else {
1674 1 : out = out->getToNode()->getOutgoingEdges()[0];
1675 1 : seen += out->getLoadedLength();
1676 : }
1677 : }
1678 : return true;
1679 : }
1680 :
1681 :
1682 : void
1683 111745 : NBNode::getEdgesThatApproach(NBEdge* currentOutgoing, EdgeVector& approaching) {
1684 : // get the position of the node to get the approaching nodes of
1685 111745 : EdgeVector::const_iterator i = std::find(myAllEdges.begin(),
1686 : myAllEdges.end(), currentOutgoing);
1687 : // get the first possible approaching edge
1688 111745 : NBContHelper::nextCW(myAllEdges, i);
1689 : // go through the list of edges clockwise and add the edges
1690 : approaching.clear();
1691 598453 : for (; *i != currentOutgoing;) {
1692 : // check only incoming edges
1693 486708 : if ((*i)->getToNode() == this && (*i)->getTurnDestination() != currentOutgoing) {
1694 235226 : std::vector<int> connLanes = (*i)->getConnectionLanes(currentOutgoing);
1695 235226 : if (connLanes.size() != 0) {
1696 169197 : approaching.push_back(*i);
1697 : }
1698 : }
1699 486708 : NBContHelper::nextCW(myAllEdges, i);
1700 : }
1701 111745 : }
1702 :
1703 :
1704 : void
1705 652 : NBNode::replaceOutgoing(NBEdge* which, NBEdge* by, int laneOff) {
1706 : // replace the edge in the list of outgoing nodes
1707 652 : EdgeVector::iterator i = std::find(myOutgoingEdges.begin(), myOutgoingEdges.end(), which);
1708 652 : if (i != myOutgoingEdges.end()) {
1709 652 : (*i) = by;
1710 652 : i = std::find(myAllEdges.begin(), myAllEdges.end(), which);
1711 652 : (*i) = by;
1712 : }
1713 : // replace the edge in connections of incoming edges
1714 1601 : for (i = myIncomingEdges.begin(); i != myIncomingEdges.end(); ++i) {
1715 949 : (*i)->replaceInConnections(which, by, laneOff);
1716 : }
1717 : // replace within the connetion prohibition dependencies
1718 652 : replaceInConnectionProhibitions(which, by, 0, laneOff);
1719 652 : }
1720 :
1721 :
1722 : void
1723 11 : NBNode::replaceOutgoing(const EdgeVector& which, NBEdge* by) {
1724 : // replace edges
1725 : int laneOff = 0;
1726 33 : for (EdgeVector::const_iterator i = which.begin(); i != which.end(); i++) {
1727 22 : replaceOutgoing(*i, by, laneOff);
1728 22 : laneOff += (*i)->getNumLanes();
1729 : }
1730 : // removed double occurrences
1731 11 : removeDoubleEdges();
1732 : // check whether this node belongs to a district and the edges
1733 : // must here be also remapped
1734 11 : if (myDistrict != nullptr) {
1735 0 : myDistrict->replaceOutgoing(which, by);
1736 : }
1737 11 : }
1738 :
1739 :
1740 : void
1741 10006 : NBNode::replaceIncoming(NBEdge* which, NBEdge* by, int laneOff) {
1742 : // replace the edge in the list of incoming nodes
1743 10006 : EdgeVector::iterator i = std::find(myIncomingEdges.begin(), myIncomingEdges.end(), which);
1744 10006 : if (i != myIncomingEdges.end()) {
1745 10006 : (*i) = by;
1746 10006 : i = std::find(myAllEdges.begin(), myAllEdges.end(), which);
1747 10006 : (*i) = by;
1748 : }
1749 : // replace within the connetion prohibition dependencies
1750 10006 : replaceInConnectionProhibitions(which, by, laneOff, 0);
1751 10006 : }
1752 :
1753 :
1754 : void
1755 11 : NBNode::replaceIncoming(const EdgeVector& which, NBEdge* by) {
1756 : // replace edges
1757 : int laneOff = 0;
1758 33 : for (EdgeVector::const_iterator i = which.begin(); i != which.end(); i++) {
1759 22 : replaceIncoming(*i, by, laneOff);
1760 22 : laneOff += (*i)->getNumLanes();
1761 : }
1762 : // removed double occurrences
1763 11 : removeDoubleEdges();
1764 : // check whether this node belongs to a district and the edges
1765 : // must here be also remapped
1766 11 : if (myDistrict != nullptr) {
1767 0 : myDistrict->replaceIncoming(which, by);
1768 : }
1769 11 : }
1770 :
1771 :
1772 :
1773 : void
1774 10658 : NBNode::replaceInConnectionProhibitions(NBEdge* which, NBEdge* by,
1775 : int whichLaneOff, int byLaneOff) {
1776 : // replace in keys
1777 : NBConnectionProhibits::iterator j = myBlockedConnections.begin();
1778 10858 : while (j != myBlockedConnections.end()) {
1779 : bool changed = false;
1780 200 : NBConnection c = (*j).first;
1781 200 : if (c.replaceFrom(which, whichLaneOff, by, byLaneOff)) {
1782 : changed = true;
1783 : }
1784 200 : if (c.replaceTo(which, whichLaneOff, by, byLaneOff)) {
1785 : changed = true;
1786 : }
1787 200 : if (changed) {
1788 17 : myBlockedConnections[c] = (*j).second;
1789 : myBlockedConnections.erase(j);
1790 : j = myBlockedConnections.begin();
1791 : } else {
1792 : j++;
1793 : }
1794 200 : }
1795 : // replace in values
1796 10756 : for (j = myBlockedConnections.begin(); j != myBlockedConnections.end(); j++) {
1797 : NBConnectionVector& prohibiting = (*j).second;
1798 322 : for (NBConnectionVector::iterator k = prohibiting.begin(); k != prohibiting.end(); k++) {
1799 : NBConnection& sprohibiting = *k;
1800 224 : sprohibiting.replaceFrom(which, whichLaneOff, by, byLaneOff);
1801 224 : sprohibiting.replaceTo(which, whichLaneOff, by, byLaneOff);
1802 : }
1803 : }
1804 10658 : }
1805 :
1806 :
1807 :
1808 : void
1809 1282 : NBNode::removeDoubleEdges() {
1810 : // check incoming
1811 2719 : for (int i = 0; myIncomingEdges.size() > 0 && i < (int)myIncomingEdges.size() - 1; i++) {
1812 1437 : int j = i + 1;
1813 4039 : while (j < (int)myIncomingEdges.size()) {
1814 2602 : if (myIncomingEdges[i] == myIncomingEdges[j]) {
1815 652 : myIncomingEdges.erase(myIncomingEdges.begin() + j);
1816 : } else {
1817 1950 : j++;
1818 : }
1819 : }
1820 : }
1821 : // check outgoing
1822 2682 : for (int i = 0; myOutgoingEdges.size() > 0 && i < (int)myOutgoingEdges.size() - 1; i++) {
1823 1400 : int j = i + 1;
1824 3739 : while (j < (int)myOutgoingEdges.size()) {
1825 2339 : if (myOutgoingEdges[i] == myOutgoingEdges[j]) {
1826 652 : myOutgoingEdges.erase(myOutgoingEdges.begin() + j);
1827 : } else {
1828 1687 : j++;
1829 : }
1830 : }
1831 : }
1832 : // check all
1833 4823 : for (int i = 0; myAllEdges.size() > 0 && i < (int)myAllEdges.size() - 1; i++) {
1834 3541 : int j = i + 1;
1835 14293 : while (j < (int)myAllEdges.size()) {
1836 10752 : if (myAllEdges[i] == myAllEdges[j]) {
1837 1304 : myAllEdges.erase(myAllEdges.begin() + j);
1838 : } else {
1839 9448 : j++;
1840 : }
1841 : }
1842 : }
1843 1282 : }
1844 :
1845 :
1846 : bool
1847 171215 : NBNode::hasIncoming(const NBEdge* const e) const {
1848 171215 : return std::find(myIncomingEdges.begin(), myIncomingEdges.end(), e) != myIncomingEdges.end();
1849 : }
1850 :
1851 :
1852 : bool
1853 14746 : NBNode::hasOutgoing(const NBEdge* const e) const {
1854 14746 : return std::find(myOutgoingEdges.begin(), myOutgoingEdges.end(), e) != myOutgoingEdges.end();
1855 : }
1856 :
1857 :
1858 : NBEdge*
1859 28882 : NBNode::getOppositeIncoming(NBEdge* e) const {
1860 28882 : EdgeVector edges = myIncomingEdges;
1861 28882 : if (find(edges.begin(), edges.end(), e) != edges.end()) {
1862 28882 : edges.erase(find(edges.begin(), edges.end(), e));
1863 : }
1864 28882 : if (edges.size() == 0) {
1865 : return nullptr;
1866 : }
1867 28882 : if (e->getToNode() == this) {
1868 28882 : sort(edges.begin(), edges.end(), NBContHelper::edge_opposite_direction_sorter(e, this, false));
1869 : } else {
1870 0 : sort(edges.begin(), edges.end(), NBContHelper::edge_similar_direction_sorter(e));
1871 : }
1872 28882 : return edges[0];
1873 : }
1874 :
1875 :
1876 : void
1877 199 : NBNode::addSortedLinkFoes(const NBConnection& mayDrive,
1878 : const NBConnection& mustStop) {
1879 398 : if (mayDrive.getFrom() == nullptr ||
1880 398 : mayDrive.getTo() == nullptr ||
1881 597 : mustStop.getFrom() == nullptr ||
1882 199 : mustStop.getTo() == nullptr) {
1883 :
1884 0 : WRITE_WARNING(TL("Something went wrong during the building of a connection..."));
1885 0 : return; // !!! mark to recompute connections
1886 : }
1887 199 : NBConnectionVector conn = myBlockedConnections[mustStop];
1888 199 : conn.push_back(mayDrive);
1889 199 : myBlockedConnections[mustStop] = conn;
1890 199 : }
1891 :
1892 :
1893 : NBEdge*
1894 266 : NBNode::getPossiblySplittedIncoming(const std::string& edgeid) {
1895 266 : int size = (int) edgeid.length();
1896 1042 : for (EdgeVector::iterator i = myIncomingEdges.begin(); i != myIncomingEdges.end(); i++) {
1897 1042 : std::string id = (*i)->getID();
1898 1042 : if (id.substr(0, size) == edgeid) {
1899 266 : return *i;
1900 : }
1901 : }
1902 : return nullptr;
1903 : }
1904 :
1905 :
1906 : NBEdge*
1907 266 : NBNode::getPossiblySplittedOutgoing(const std::string& edgeid) {
1908 266 : int size = (int) edgeid.length();
1909 605 : for (EdgeVector::iterator i = myOutgoingEdges.begin(); i != myOutgoingEdges.end(); i++) {
1910 549 : std::string id = (*i)->getID();
1911 549 : if (id.substr(0, size) == edgeid) {
1912 210 : return *i;
1913 : }
1914 : }
1915 : return nullptr;
1916 : }
1917 :
1918 :
1919 : void
1920 55209 : NBNode::removeEdge(NBEdge* edge, bool removeFromConnections) {
1921 55209 : EdgeVector::iterator i = std::find(myAllEdges.begin(), myAllEdges.end(), edge);
1922 55209 : if (i != myAllEdges.end()) {
1923 44521 : myAllEdges.erase(i);
1924 44521 : i = std::find(myOutgoingEdges.begin(), myOutgoingEdges.end(), edge);
1925 44521 : if (i != myOutgoingEdges.end()) {
1926 27017 : myOutgoingEdges.erase(i);
1927 : // potential self-loop
1928 27017 : i = std::find(myIncomingEdges.begin(), myIncomingEdges.end(), edge);
1929 27017 : if (i != myIncomingEdges.end()) {
1930 0 : myIncomingEdges.erase(i);
1931 : }
1932 : } else {
1933 17504 : i = std::find(myIncomingEdges.begin(), myIncomingEdges.end(), edge);
1934 17504 : if (i != myIncomingEdges.end()) {
1935 17504 : myIncomingEdges.erase(i);
1936 : } else {
1937 : // edge must have been either incoming or outgoing
1938 : assert(false);
1939 : }
1940 : }
1941 44521 : if (removeFromConnections) {
1942 85598 : for (i = myAllEdges.begin(); i != myAllEdges.end(); ++i) {
1943 51310 : (*i)->removeFromConnections(edge);
1944 : }
1945 : }
1946 : // invalidate controlled connections for loaded traffic light plans
1947 44521 : const bool incoming = edge->getToNode() == this;
1948 49406 : for (NBTrafficLightDefinition* const tld : myTrafficLights) {
1949 4885 : tld->replaceRemoved(edge, -1, nullptr, -1, incoming);
1950 : }
1951 : }
1952 55209 : }
1953 :
1954 :
1955 : Position
1956 0 : NBNode::getEmptyDir() const {
1957 : Position pos(0, 0);
1958 0 : for (const NBEdge* const in : myIncomingEdges) {
1959 0 : Position toAdd = in->getFromNode()->getPosition();
1960 : toAdd.sub(myPosition);
1961 0 : toAdd.norm2D();
1962 : pos.add(toAdd);
1963 : }
1964 0 : for (const NBEdge* const out : myOutgoingEdges) {
1965 0 : Position toAdd = out->getToNode()->getPosition();
1966 : toAdd.sub(myPosition);
1967 0 : toAdd.norm2D();
1968 : pos.add(toAdd);
1969 : }
1970 0 : pos.mul(-1. / (double)(myIncomingEdges.size() + myOutgoingEdges.size()));
1971 0 : if (pos.x() == 0. && pos.y() == 0.) {
1972 0 : pos = Position(1, 0);
1973 : }
1974 0 : pos.norm2D();
1975 0 : return pos;
1976 : }
1977 :
1978 :
1979 :
1980 : void
1981 0 : NBNode::invalidateIncomingConnections(bool reallowSetting) {
1982 0 : for (EdgeVector::const_iterator i = myIncomingEdges.begin(); i != myIncomingEdges.end(); i++) {
1983 0 : (*i)->invalidateConnections(reallowSetting);
1984 : }
1985 0 : }
1986 :
1987 :
1988 : void
1989 34 : NBNode::invalidateOutgoingConnections(bool reallowSetting) {
1990 119 : for (EdgeVector::const_iterator i = myOutgoingEdges.begin(); i != myOutgoingEdges.end(); i++) {
1991 85 : (*i)->invalidateConnections(reallowSetting);
1992 : }
1993 34 : }
1994 :
1995 :
1996 : bool
1997 279045 : NBNode::mustBrake(const NBEdge* const from, const NBEdge* const to, int fromLane, int toLane, bool includePedCrossings) const {
1998 : // unregulated->does not need to brake
1999 279045 : if (myRequest == nullptr) {
2000 : return false;
2001 : }
2002 : // vehicles which do not have a following lane must always decelerate to the end
2003 278087 : if (to == nullptr) {
2004 : return true;
2005 : }
2006 : // maybe we need to brake due to entering a bidi-edge
2007 278087 : if (to->isBidiEdge() && !from->isBidiEdge()) {
2008 : return true;
2009 : }
2010 : // check whether any other connection on this node prohibits this connection
2011 278026 : return myRequest->mustBrake(from, to, fromLane, toLane, includePedCrossings);
2012 : }
2013 :
2014 : bool
2015 9978 : NBNode::mustBrakeForCrossing(const NBEdge* const from, const NBEdge* const to, const NBNode::Crossing& crossing) const {
2016 9978 : return NBRequest::mustBrakeForCrossing(this, from, to, crossing);
2017 : }
2018 :
2019 : bool
2020 20863 : NBNode::brakeForCrossingOnExit(const NBEdge* to) const {
2021 : // code is called for connections exiting after an internal junction.
2022 : // Therefore we can assume that the connection is turning and do not check
2023 : // for direction or crossing priority anymore.
2024 24772 : for (auto& c : myCrossings) {
2025 5888 : if (std::find(c->edges.begin(), c->edges.end(), to) != c->edges.end()) {
2026 : return true;
2027 : }
2028 : }
2029 : return false;
2030 : }
2031 :
2032 :
2033 : bool
2034 5123064 : NBNode::rightTurnConflict(const NBEdge* from, const NBEdge* to, int fromLane,
2035 : const NBEdge* prohibitorFrom, const NBEdge* prohibitorTo, int prohibitorFromLane) {
2036 5123064 : if (from != prohibitorFrom) {
2037 : return false;
2038 : }
2039 1504691 : if (from->isTurningDirectionAt(to)
2040 1504691 : || prohibitorFrom->isTurningDirectionAt(prohibitorTo)) {
2041 : // XXX should warn if there are any non-turning connections left of this
2042 466612 : return false;
2043 : }
2044 : // conflict if to is between prohibitorTo and from when going clockwise
2045 1038079 : if (to->getStartAngle() == prohibitorTo->getStartAngle()) {
2046 : // reduce rounding errors
2047 : return false;
2048 : }
2049 561927 : const LinkDirection d1 = from->getToNode()->getDirection(from, to);
2050 : // must be a right turn to qualify as rightTurnConflict
2051 561927 : if (d1 == LinkDirection::STRAIGHT) {
2052 : // no conflict for straight going connections
2053 : // XXX actually this should check the main direction (which could also
2054 : // be a turn)
2055 : return false;
2056 : } else {
2057 413137 : const LinkDirection d2 = prohibitorFrom->getToNode()->getDirection(prohibitorFrom, prohibitorTo);
2058 : /* std::cout
2059 : << "from=" << from->getID() << " to=" << to->getID() << " fromLane=" << fromLane
2060 : << " pFrom=" << prohibitorFrom->getID() << " pTo=" << prohibitorTo->getID() << " pFromLane=" << prohibitorFromLane
2061 : << " d1=" << toString(d1) << " d2=" << toString(d2)
2062 : << "\n"; */
2063 : bool flip = false;
2064 413137 : if (d1 == LinkDirection::LEFT || d1 == LinkDirection::PARTLEFT) {
2065 : // check for leftTurnConflicht
2066 : flip = !flip;
2067 194284 : if (d2 == LinkDirection::RIGHT || d2 == LinkDirection::PARTRIGHT) {
2068 : // assume that the left-turning bicycle goes straight at first
2069 : // and thus gets precedence over a right turning vehicle
2070 : return false;
2071 : }
2072 : }
2073 335332 : if ((!flip && fromLane <= prohibitorFromLane) ||
2074 119357 : (flip && fromLane >= prohibitorFromLane)) {
2075 : return false;
2076 : }
2077 5126 : const double toAngleAtNode = fmod(to->getStartAngle() + 180, (double)360.0);
2078 5126 : const double prohibitorToAngleAtNode = fmod(prohibitorTo->getStartAngle() + 180, (double)360.0);
2079 5126 : return (flip != (GeomHelper::getCWAngleDiff(from->getEndAngle(), toAngleAtNode) <
2080 5126 : GeomHelper::getCWAngleDiff(from->getEndAngle(), prohibitorToAngleAtNode)));
2081 : }
2082 : }
2083 :
2084 : bool
2085 442 : NBNode::mergeConflictYields(const NBEdge* from, int fromLane, int fromLaneFoe, NBEdge* to, int toLane) const {
2086 442 : if (myRequest == nullptr) {
2087 : return false;
2088 : }
2089 442 : const NBEdge::Connection& con = from->getConnection(fromLane, to, toLane);
2090 442 : const NBEdge::Connection& prohibitorCon = from->getConnection(fromLaneFoe, to, toLane);
2091 442 : return myRequest->mergeConflict(from, con, from, prohibitorCon, false);
2092 : }
2093 :
2094 :
2095 : bool
2096 1840542 : NBNode::mergeConflict(const NBEdge* from, const NBEdge::Connection& con,
2097 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon, bool foes) const {
2098 1840542 : if (myRequest == nullptr) {
2099 : return false;
2100 : }
2101 1790792 : return myRequest->mergeConflict(from, con, prohibitorFrom, prohibitorCon, foes);
2102 : }
2103 :
2104 : bool
2105 920271 : NBNode::bidiConflict(const NBEdge* from, const NBEdge::Connection& con,
2106 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon, bool foes) const {
2107 920271 : if (myRequest == nullptr) {
2108 : return false;
2109 : }
2110 895396 : return myRequest->bidiConflict(from, con, prohibitorFrom, prohibitorCon, foes);
2111 : }
2112 :
2113 : bool
2114 1814244 : NBNode::turnFoes(const NBEdge* from, const NBEdge* to, int fromLane,
2115 : const NBEdge* from2, const NBEdge* to2, int fromLane2,
2116 : bool lefthand) const {
2117 : UNUSED_PARAMETER(lefthand);
2118 1814244 : if (from != from2 || to == to2 || fromLane == fromLane2) {
2119 : return false;
2120 : }
2121 88539 : if (from->isTurningDirectionAt(to)
2122 88539 : || from2->isTurningDirectionAt(to2)) {
2123 : // XXX should warn if there are any non-turning connections left of this
2124 27840 : return false;
2125 : }
2126 : bool result = false;
2127 60699 : EdgeVector::const_iterator it = std::find(myAllEdges.begin(), myAllEdges.end(), from);
2128 60699 : if (fromLane < fromLane2) {
2129 : // conflict if 'to' comes before 'to2' going clockwise starting at 'from'
2130 127264 : while (*it != to2) {
2131 96860 : if (*it == to) {
2132 : result = true;
2133 : }
2134 96860 : NBContHelper::nextCW(myAllEdges, it);
2135 : }
2136 : } else {
2137 : // conflict if 'to' comes before 'to2' going counter-clockwise starting at 'from'
2138 82956 : while (*it != to2) {
2139 52661 : if (*it == to) {
2140 : result = true;
2141 : }
2142 52661 : NBContHelper::nextCCW(myAllEdges, it);
2143 : }
2144 : }
2145 : /*
2146 : if (result) {
2147 : std::cout << "turnFoes node=" << getID()
2148 : << " from=" << from->getLaneID(fromLane)
2149 : << " to=" << to->getID()
2150 : << " from2=" << from2->getLaneID(fromLane2)
2151 : << " to2=" << to2->getID()
2152 : << "\n";
2153 : }
2154 : */
2155 : return result;
2156 : }
2157 :
2158 :
2159 : bool
2160 4812 : NBNode::isLeftMover(const NBEdge* const from, const NBEdge* const to) const {
2161 : // when the junction has only one incoming edge, there are no
2162 : // problems caused by left blockings
2163 4812 : if (myIncomingEdges.size() == 1 || myOutgoingEdges.size() == 1) {
2164 : return false;
2165 : }
2166 4764 : double fromAngle = from->getAngleAtNode(this);
2167 4764 : double toAngle = to->getAngleAtNode(this);
2168 4764 : double cw = GeomHelper::getCWAngleDiff(fromAngle, toAngle);
2169 4764 : double ccw = GeomHelper::getCCWAngleDiff(fromAngle, toAngle);
2170 4764 : std::vector<NBEdge*>::const_iterator i = std::find(myAllEdges.begin(), myAllEdges.end(), from);
2171 : do {
2172 14292 : NBContHelper::nextCW(myAllEdges, i);
2173 14292 : } while ((!hasOutgoing(*i) || from->isTurningDirectionAt(*i)) && *i != from);
2174 4764 : return cw < ccw && (*i) == to && myOutgoingEdges.size() > 2;
2175 : }
2176 :
2177 :
2178 : bool
2179 1688690 : NBNode::forbids(const NBEdge* const possProhibitorFrom, const NBEdge* const possProhibitorTo,
2180 : const NBEdge* const possProhibitedFrom, const NBEdge* const possProhibitedTo,
2181 : bool regardNonSignalisedLowerPriority) const {
2182 1688690 : return myRequest != nullptr && myRequest->forbids(possProhibitorFrom, possProhibitorTo,
2183 : possProhibitedFrom, possProhibitedTo,
2184 1688690 : regardNonSignalisedLowerPriority);
2185 : }
2186 :
2187 :
2188 : bool
2189 1685169 : NBNode::foes(const NBEdge* const from1, const NBEdge* const to1,
2190 : const NBEdge* const from2, const NBEdge* const to2) const {
2191 1685169 : return myRequest != nullptr && myRequest->foes(from1, to1, from2, to2);
2192 : }
2193 :
2194 :
2195 : void
2196 0 : NBNode::remapRemoved(NBTrafficLightLogicCont& tc,
2197 : NBEdge* removed, const EdgeVector& incoming,
2198 : const EdgeVector& outgoing) {
2199 : assert(find(incoming.begin(), incoming.end(), removed) == incoming.end());
2200 : bool changed = true;
2201 0 : while (changed) {
2202 : changed = false;
2203 : NBConnectionProhibits blockedConnectionsTmp = myBlockedConnections;
2204 : NBConnectionProhibits blockedConnectionsNew;
2205 : // remap in connections
2206 0 : for (NBConnectionProhibits::iterator i = blockedConnectionsTmp.begin(); i != blockedConnectionsTmp.end(); i++) {
2207 0 : const NBConnection& blocker = (*i).first;
2208 0 : const NBConnectionVector& blocked = (*i).second;
2209 : // check the blocked connections first
2210 : // check whether any of the blocked must be changed
2211 : bool blockedChanged = false;
2212 : NBConnectionVector newBlocked;
2213 : NBConnectionVector::const_iterator j;
2214 0 : for (j = blocked.begin(); j != blocked.end(); j++) {
2215 : const NBConnection& sblocked = *j;
2216 0 : if (sblocked.getFrom() == removed || sblocked.getTo() == removed) {
2217 : blockedChanged = true;
2218 : }
2219 : }
2220 : // adapt changes if so
2221 0 : for (j = blocked.begin(); blockedChanged && j != blocked.end(); j++) {
2222 : const NBConnection& sblocked = *j;
2223 0 : if (sblocked.getFrom() == removed && sblocked.getTo() == removed) {
2224 : /* for(EdgeVector::const_iterator k=incoming.begin(); k!=incoming.end(); k++) {
2225 : !!! newBlocked.push_back(NBConnection(*k, *k));
2226 : }*/
2227 0 : } else if (sblocked.getFrom() == removed) {
2228 : assert(sblocked.getTo() != removed);
2229 0 : for (EdgeVector::const_iterator k = incoming.begin(); k != incoming.end(); k++) {
2230 0 : newBlocked.push_back(NBConnection(*k, sblocked.getTo()));
2231 : }
2232 0 : } else if (sblocked.getTo() == removed) {
2233 : assert(sblocked.getFrom() != removed);
2234 0 : for (EdgeVector::const_iterator k = outgoing.begin(); k != outgoing.end(); k++) {
2235 0 : newBlocked.push_back(NBConnection(sblocked.getFrom(), *k));
2236 : }
2237 : } else {
2238 0 : newBlocked.push_back(NBConnection(sblocked.getFrom(), sblocked.getTo()));
2239 : }
2240 : }
2241 0 : if (blockedChanged) {
2242 0 : blockedConnectionsNew[blocker] = newBlocked;
2243 : changed = true;
2244 : }
2245 : // if the blocked were kept
2246 : else {
2247 0 : if (blocker.getFrom() == removed && blocker.getTo() == removed) {
2248 : changed = true;
2249 : /* for(EdgeVector::const_iterator k=incoming.begin(); k!=incoming.end(); k++) {
2250 : !!! blockedConnectionsNew[NBConnection(*k, *k)] = blocked;
2251 : }*/
2252 0 : } else if (blocker.getFrom() == removed) {
2253 : assert(blocker.getTo() != removed);
2254 : changed = true;
2255 0 : for (EdgeVector::const_iterator k = incoming.begin(); k != incoming.end(); k++) {
2256 0 : blockedConnectionsNew[NBConnection(*k, blocker.getTo())] = blocked;
2257 : }
2258 0 : } else if (blocker.getTo() == removed) {
2259 : assert(blocker.getFrom() != removed);
2260 : changed = true;
2261 0 : for (EdgeVector::const_iterator k = outgoing.begin(); k != outgoing.end(); k++) {
2262 0 : blockedConnectionsNew[NBConnection(blocker.getFrom(), *k)] = blocked;
2263 : }
2264 : } else {
2265 0 : blockedConnectionsNew[blocker] = blocked;
2266 : }
2267 : }
2268 0 : }
2269 : myBlockedConnections = blockedConnectionsNew;
2270 : }
2271 : // remap in traffic lights
2272 0 : tc.remapRemoved(removed, incoming, outgoing);
2273 0 : }
2274 :
2275 :
2276 : NBEdge*
2277 4059601 : NBNode::getNextCompatibleOutgoing(const NBEdge* incoming, SVCPermissions vehPerm, EdgeVector::const_iterator itOut, bool clockwise) const {
2278 4059601 : EdgeVector::const_iterator i = itOut;
2279 8520565 : while (*i != incoming) {
2280 6768950 : if (clockwise) {
2281 2918425 : NBContHelper::nextCW(myAllEdges, i);
2282 : } else {
2283 3850525 : NBContHelper::nextCCW(myAllEdges, i);
2284 : }
2285 6768950 : if ((*i)->getFromNode() != this) {
2286 : // only look for outgoing edges
2287 : // @note we use myAllEdges to stop at the incoming edge
2288 4249105 : continue;
2289 : }
2290 2519845 : if (incoming->isTurningDirectionAt(*i)) {
2291 : return nullptr;
2292 : }
2293 1298182 : if ((vehPerm & (*i)->getPermissions()) != 0 || vehPerm == 0) {
2294 1086323 : return *i;
2295 : }
2296 : }
2297 : return nullptr;
2298 : }
2299 :
2300 :
2301 : bool
2302 1175670 : NBNode::isStraighter(const NBEdge* const incoming, const double angle, const SVCPermissions vehPerm, const int modeLanes, const NBEdge* const candidate) const {
2303 1175670 : if (candidate != nullptr) {
2304 794916 : const double candAngle = NBHelpers::normRelAngle(incoming->getAngleAtNode(this), candidate->getAngleAtNode(this));
2305 : // they are too similar it does not matter
2306 794916 : if (fabs(angle - candAngle) < 5.) {
2307 : return false;
2308 : }
2309 : // the other edge is at least 5 degree straighter
2310 771921 : if (fabs(candAngle) < fabs(angle) - 5.) {
2311 : return true;
2312 : }
2313 681249 : if (fabs(angle) < fabs(candAngle) - 5.) {
2314 : return false;
2315 : }
2316 29218 : if (fabs(candAngle) < 44.) {
2317 : // the lane count for the same modes is larger
2318 27907 : const int candModeLanes = candidate->getNumLanesThatAllow(vehPerm);
2319 27907 : if (candModeLanes > modeLanes) {
2320 : return true;
2321 : }
2322 25905 : if (candModeLanes < modeLanes) {
2323 : return false;
2324 : }
2325 : // we would create a left turn
2326 21377 : if (candAngle < 0 && angle > 0) {
2327 : return true;
2328 : }
2329 : if (angle < 0 && candAngle > 0) {
2330 : return false;
2331 : }
2332 : }
2333 : }
2334 : return false;
2335 : }
2336 :
2337 : EdgeVector
2338 12362 : NBNode::getPassengerEdges(bool incoming) const {
2339 : EdgeVector result;
2340 38927 : for (NBEdge* e : (incoming ? myIncomingEdges : myOutgoingEdges)) {
2341 26565 : if ((e->getPermissions() & SVC_PASSENGER) != 0) {
2342 17845 : result.push_back(e);
2343 : }
2344 : }
2345 12362 : return result;
2346 : }
2347 :
2348 : LinkDirection
2349 9049972 : NBNode::getDirection(const NBEdge* const incoming, const NBEdge* const outgoing, bool leftHand) const {
2350 : // ok, no connection at all -> dead end
2351 9049972 : if (outgoing == nullptr) {
2352 : return LinkDirection::NODIR;
2353 : }
2354 9049971 : if (incoming->getJunctionPriority(this) == NBEdge::JunctionPriority::ROUNDABOUT && outgoing->getJunctionPriority(this) == NBEdge::JunctionPriority::ROUNDABOUT) {
2355 : return LinkDirection::STRAIGHT;
2356 : }
2357 : // turning direction
2358 9036898 : if (incoming->isTurningDirectionAt(outgoing)) {
2359 1575509 : if (isExplicitRailNoBidi(incoming, outgoing)) {
2360 : return LinkDirection::STRAIGHT;
2361 : }
2362 3149611 : return leftHand ? LinkDirection::TURN_LEFTHAND : LinkDirection::TURN;
2363 : }
2364 : // get the angle between incoming/outgoing at the junction
2365 7461389 : const double angle = NBHelpers::normRelAngle(incoming->getAngleAtNode(this), outgoing->getAngleAtNode(this));
2366 : // ok, should be a straight connection
2367 7461389 : EdgeVector::const_iterator itOut = std::find(myAllEdges.begin(), myAllEdges.end(), outgoing);
2368 7461389 : SVCPermissions vehPerm = incoming->getPermissions() & outgoing->getPermissions();
2369 7461389 : if (vehPerm != SVC_PEDESTRIAN) {
2370 7360005 : vehPerm &= ~SVC_PEDESTRIAN;
2371 : }
2372 7461389 : const int modeLanes = outgoing->getNumLanesThatAllow(vehPerm);
2373 7461389 : if (fabs(angle) < 44.) {
2374 2798492 : if (fabs(angle) > 6.) {
2375 612202 : if (isStraighter(incoming, angle, vehPerm, modeLanes, getNextCompatibleOutgoing(incoming, vehPerm, itOut, true))) {
2376 96075 : return angle > 0 ? LinkDirection::PARTRIGHT : LinkDirection::PARTLEFT;
2377 : }
2378 563468 : if (isStraighter(incoming, angle, vehPerm, modeLanes, getNextCompatibleOutgoing(incoming, vehPerm, itOut, false))) {
2379 59259 : return angle > 0 ? LinkDirection::PARTRIGHT : LinkDirection::PARTLEFT;
2380 : }
2381 : }
2382 2692656 : if (angle > 0 && incoming->getJunctionPriority(this) == NBEdge::JunctionPriority::ROUNDABOUT) {
2383 4132 : return angle > 15 ? LinkDirection::RIGHT : LinkDirection::PARTRIGHT;
2384 : }
2385 2690513 : return LinkDirection::STRAIGHT;
2386 : }
2387 :
2388 4662897 : if (angle > 0) {
2389 : // check whether any other edge goes further to the right
2390 2518722 : if (angle > 90) {
2391 : return LinkDirection::RIGHT;
2392 : }
2393 1571692 : NBEdge* outCW = getNextCompatibleOutgoing(incoming, vehPerm, itOut, !leftHand);
2394 1571692 : if (outCW != nullptr) {
2395 : return LinkDirection::PARTRIGHT;
2396 : } else {
2397 1425550 : return LinkDirection::RIGHT;
2398 : }
2399 : } else {
2400 : // check whether any other edge goes further to the left
2401 2144175 : if (angle < -170 && incoming->getGeometry().reverse() == outgoing->getGeometry()) {
2402 2382 : if (isExplicitRailNoBidi(incoming, outgoing)) {
2403 : return LinkDirection::STRAIGHT;
2404 : }
2405 4764 : return leftHand ? LinkDirection::TURN_LEFTHAND : LinkDirection::TURN;
2406 2141793 : } else if (angle < -90) {
2407 : return LinkDirection::LEFT;
2408 : }
2409 1312239 : NBEdge* outCCW = getNextCompatibleOutgoing(incoming, vehPerm, itOut, leftHand);
2410 1312239 : if (outCCW != nullptr) {
2411 : return LinkDirection::PARTLEFT;
2412 : } else {
2413 1166974 : return LinkDirection::LEFT;
2414 : }
2415 : }
2416 : }
2417 :
2418 :
2419 : bool
2420 1577891 : NBNode::isExplicitRailNoBidi(const NBEdge* incoming, const NBEdge* outgoing) {
2421 : // assume explicit connections at sharp turn-arounds are either for reversal or due to a geometry glitch
2422 : // (but should not have been guessed)
2423 : // @note this function is also called from NBAlgorithms when there aren't any connections ready
2424 : return (incoming->getStep() >= NBEdge::EdgeBuildingStep::LANES2LANES_RECHECK
2425 1499216 : && isRailway(incoming->getPermissions())
2426 4846 : && isRailway(outgoing->getPermissions())
2427 1582402 : && incoming->getBidiEdge() != outgoing);
2428 : }
2429 :
2430 :
2431 : LinkState
2432 241312 : NBNode::getLinkState(const NBEdge* incoming, const NBEdge* outgoing, int fromLane, int toLane,
2433 : bool mayDefinitelyPass, const std::string& tlID) const {
2434 241312 : if (myType == SumoXMLNodeType::RAIL_CROSSING && isRailway(incoming->getPermissions())) {
2435 : return LINKSTATE_MAJOR; // the trains must run on time
2436 : }
2437 240821 : if (tlID != "") {
2438 28184 : if (getRightOfWay() == RightOfWay::ALLWAYSTOP) {
2439 : return LINKSTATE_ALLWAY_STOP;
2440 : }
2441 28017 : return mustBrake(incoming, outgoing, fromLane, toLane, true) ? LINKSTATE_TL_OFF_BLINKING : LINKSTATE_TL_OFF_NOSIGNAL;
2442 : }
2443 212637 : if (outgoing == nullptr) { // always off
2444 : return LINKSTATE_TL_OFF_NOSIGNAL;
2445 : }
2446 212637 : if ((myType == SumoXMLNodeType::RIGHT_BEFORE_LEFT || myType == SumoXMLNodeType::LEFT_BEFORE_RIGHT)
2447 212637 : && mustBrake(incoming, outgoing, fromLane, toLane, true)) {
2448 : return LINKSTATE_EQUAL; // all the same
2449 : }
2450 194712 : if (myType == SumoXMLNodeType::ALLWAY_STOP) {
2451 : return LINKSTATE_ALLWAY_STOP; // all drive, first one to arrive may drive first
2452 : }
2453 194696 : if (myType == SumoXMLNodeType::ZIPPER && zipperConflict(incoming, outgoing, fromLane, toLane)) {
2454 : return LINKSTATE_ZIPPER;
2455 : }
2456 : if (!mayDefinitelyPass
2457 194656 : && mustBrake(incoming, outgoing, fromLane, toLane, true)
2458 : // legacy mode
2459 87509 : && (!incoming->isInsideTLS() || getDirection(incoming, outgoing) != LinkDirection::STRAIGHT)
2460 : // avoid linkstate minor at pure railway nodes
2461 282172 : && !NBNodeTypeComputer::isRailwayNode(this)) {
2462 172612 : return myType == SumoXMLNodeType::PRIORITY_STOP ? LINKSTATE_STOP : LINKSTATE_MINOR; // minor road
2463 : }
2464 : // traffic lights are not regarded here
2465 : return LINKSTATE_MAJOR;
2466 : }
2467 :
2468 :
2469 : bool
2470 27 : NBNode::zipperConflict(const NBEdge* incoming, const NBEdge* outgoing, int fromLane, int toLane) const {
2471 27 : if (mustBrake(incoming, outgoing, fromLane, toLane, false)) {
2472 : // there should be another connection with the same target (not just some intersecting trajectories)
2473 33 : for (const NBEdge* in : getIncomingEdges()) {
2474 55 : for (const NBEdge::Connection& c : in->getConnections()) {
2475 43 : if ((in != incoming || c.fromLane != fromLane) && c.toEdge == outgoing && c.toLane == toLane) {
2476 : return true;
2477 : }
2478 : }
2479 : }
2480 : }
2481 : return false;
2482 : }
2483 :
2484 :
2485 : bool
2486 30231 : NBNode::checkIsRemovable() const {
2487 : std::string reason;
2488 60462 : return checkIsRemovableReporting(reason);
2489 : }
2490 :
2491 : bool
2492 30231 : NBNode::checkIsRemovableReporting(std::string& reason) const {
2493 30231 : if (getEdges().empty()) {
2494 : return true;
2495 : }
2496 : // check whether this node is included in a traffic light or crossing
2497 30231 : if (myTrafficLights.size() != 0) {
2498 : reason = "TLS";
2499 780 : return false;
2500 : }
2501 29451 : if (myType == SumoXMLNodeType::RAIL_SIGNAL) {
2502 : reason = "rail_signal";
2503 424 : return false;
2504 : }
2505 29027 : if (myCrossings.size() != 0) {
2506 : reason = "crossing";
2507 0 : return false;
2508 : }
2509 : EdgeVector::const_iterator i;
2510 : // one in, one out -> just a geometry ...
2511 29027 : if (myOutgoingEdges.size() == 1 && myIncomingEdges.size() == 1) {
2512 : // ... if types match ...
2513 8521 : if (!myIncomingEdges[0]->expandableBy(myOutgoingEdges[0], reason)) {
2514 4005 : reason = "edges incompatible: " + reason;
2515 4005 : return false;
2516 : }
2517 4516 : if (myIncomingEdges[0]->getTurnDestination(true) == myOutgoingEdges[0]) {
2518 : reason = "turnaround";
2519 57 : return false;
2520 : }
2521 : return true;
2522 : }
2523 : // two in, two out -> may be something else
2524 20506 : if (myOutgoingEdges.size() == 2 && myIncomingEdges.size() == 2) {
2525 : // check whether the origin nodes of the incoming edges differ
2526 : std::set<NBNode*> origSet;
2527 14859 : for (i = myIncomingEdges.begin(); i != myIncomingEdges.end(); i++) {
2528 9906 : origSet.insert((*i)->getFromNode());
2529 : }
2530 4953 : if (origSet.size() < 2) {
2531 : // overlapping case
2532 407 : if (myIncomingEdges[0]->getGeometry() == myIncomingEdges[1]->getGeometry() &&
2533 145 : myOutgoingEdges[0]->getGeometry() == myOutgoingEdges[1]->getGeometry()) {
2534 270 : return ((myIncomingEdges[0]->expandableBy(myOutgoingEdges[0], reason) &&
2535 133 : myIncomingEdges[1]->expandableBy(myOutgoingEdges[1], reason))
2536 139 : || (myIncomingEdges[0]->expandableBy(myOutgoingEdges[1], reason) &&
2537 2 : myIncomingEdges[1]->expandableBy(myOutgoingEdges[0], reason)));
2538 : }
2539 : }
2540 : // check whether this node is an intermediate node of
2541 : // a two-directional street
2542 9574 : for (i = myIncomingEdges.begin(); i != myIncomingEdges.end(); i++) {
2543 : // each of the edges must have an opposite direction edge
2544 7244 : NBEdge* opposite = (*i)->getTurnDestination(true);
2545 7244 : if (opposite != nullptr) {
2546 : // the other outgoing edges must be the continuation of the current
2547 5582 : NBEdge* continuation = opposite == myOutgoingEdges.front() ? myOutgoingEdges.back() : myOutgoingEdges.front();
2548 : // check whether the types allow joining
2549 5582 : if (!(*i)->expandableBy(continuation, reason)) {
2550 824 : reason = "edges incompatible: " + reason;
2551 824 : return false;
2552 : }
2553 : } else {
2554 : // ok, at least one outgoing edge is not an opposite
2555 : // of an incoming one
2556 : reason = "not opposites";
2557 : return false;
2558 : }
2559 : }
2560 : return true;
2561 : }
2562 : // ok, a real node
2563 : reason = "intersection";
2564 : return false;
2565 : }
2566 :
2567 :
2568 : std::vector<std::pair<NBEdge*, NBEdge*> >
2569 12068 : NBNode::getEdgesToJoin() const {
2570 : assert(checkIsRemovable());
2571 : std::vector<std::pair<NBEdge*, NBEdge*> > ret;
2572 : // one in, one out-case
2573 12068 : if (myOutgoingEdges.size() == 1 && myIncomingEdges.size() == 1) {
2574 4430 : ret.push_back(std::make_pair(myIncomingEdges[0], myOutgoingEdges[0]));
2575 4430 : return ret;
2576 : }
2577 7638 : if (myIncomingEdges.size() == 2 && myOutgoingEdges.size() == 2) {
2578 : // two in, two out-case
2579 2597 : if (myIncomingEdges[0]->getGeometry() == myIncomingEdges[1]->getGeometry() &&
2580 135 : myOutgoingEdges[0]->getGeometry() == myOutgoingEdges[1]->getGeometry()) {
2581 : // overlapping edges
2582 : std::string reason;
2583 135 : if (myIncomingEdges[0]->expandableBy(myOutgoingEdges[0], reason)) {
2584 133 : ret.push_back(std::make_pair(myIncomingEdges[0], myOutgoingEdges[0]));
2585 133 : ret.push_back(std::make_pair(myIncomingEdges[1], myOutgoingEdges[1]));
2586 : } else {
2587 2 : ret.push_back(std::make_pair(myIncomingEdges[0], myOutgoingEdges[1]));
2588 2 : ret.push_back(std::make_pair(myIncomingEdges[1], myOutgoingEdges[0]));
2589 : }
2590 : return ret;
2591 : }
2592 : }
2593 12157 : for (EdgeVector::const_iterator i = myIncomingEdges.begin(); i != myIncomingEdges.end(); i++) {
2594 : // join with the edge that is not a turning direction
2595 4654 : NBEdge* opposite = (*i)->getTurnDestination(true);
2596 : assert(opposite != 0);
2597 4654 : NBEdge* continuation = opposite == myOutgoingEdges.front() ? myOutgoingEdges.back() : myOutgoingEdges.front();
2598 4654 : ret.push_back(std::pair<NBEdge*, NBEdge*>(*i, continuation));
2599 : }
2600 : return ret;
2601 : }
2602 :
2603 :
2604 : const PositionVector&
2605 3463358 : NBNode::getShape() const {
2606 3463358 : return myPoly;
2607 : }
2608 :
2609 :
2610 : void
2611 34 : NBNode::setCustomShape(const PositionVector& shape) {
2612 : myPoly = shape;
2613 34 : myHaveCustomPoly = (myPoly.size() > 1);
2614 34 : if (myHaveCustomPoly) {
2615 33 : for (EdgeVector::iterator i = myAllEdges.begin(); i != myAllEdges.end(); i++) {
2616 0 : (*i)->resetNodeBorder(this);
2617 : }
2618 : }
2619 34 : }
2620 :
2621 :
2622 : NBEdge*
2623 209646 : NBNode::getConnectionTo(NBNode* n) const {
2624 537190 : for (NBEdge* e : myOutgoingEdges) {
2625 361297 : if (e->getToNode() == n && e->getPermissions() != 0) {
2626 : return e;
2627 : }
2628 : }
2629 : return nullptr;
2630 : }
2631 :
2632 :
2633 : bool
2634 0 : NBNode::isNearDistrict() const {
2635 0 : if (isDistrict()) {
2636 : return false;
2637 : }
2638 0 : for (const NBEdge* const t : getEdges()) {
2639 0 : const NBNode* const other = t->getToNode() == this ? t->getFromNode() : t->getToNode();
2640 0 : for (const NBEdge* const k : other->getEdges()) {
2641 0 : if (k->getFromNode()->isDistrict() || k->getToNode()->isDistrict()) {
2642 : return true;
2643 : }
2644 : }
2645 : }
2646 : return false;
2647 : }
2648 :
2649 :
2650 : bool
2651 0 : NBNode::isDistrict() const {
2652 0 : return myType == SumoXMLNodeType::DISTRICT;
2653 : }
2654 :
2655 :
2656 : int
2657 5819 : NBNode::guessCrossings() {
2658 : #ifdef DEBUG_PED_STRUCTURES
2659 : gDebugFlag1 = DEBUGCOND;
2660 : #endif
2661 : int numGuessed = 0;
2662 5819 : if (myCrossings.size() > 0 || myDiscardAllCrossings) {
2663 : // user supplied crossings, do not guess
2664 : return numGuessed;
2665 : }
2666 : DEBUGCOUT(gDebugFlag1, "guess crossings for " << getID() << "\n")
2667 5816 : EdgeVector allEdges = getEdgesSortedByAngleAtNodeCenter();
2668 : // check for pedestrial lanes going clockwise around the node
2669 : std::vector<std::pair<NBEdge*, bool> > normalizedLanes;
2670 26164 : for (EdgeVector::const_iterator it = allEdges.begin(); it != allEdges.end(); ++it) {
2671 20348 : NBEdge* edge = *it;
2672 : const std::vector<NBEdge::Lane>& lanes = edge->getLanes();
2673 20348 : if (edge->getFromNode() == this) {
2674 24450 : for (std::vector<NBEdge::Lane>::const_reverse_iterator it_l = lanes.rbegin(); it_l != lanes.rend(); ++it_l) {
2675 14276 : normalizedLanes.push_back(std::make_pair(edge, ((*it_l).permissions & SVC_PEDESTRIAN) != 0));
2676 : }
2677 : } else {
2678 24450 : for (std::vector<NBEdge::Lane>::const_iterator it_l = lanes.begin(); it_l != lanes.end(); ++it_l) {
2679 14276 : normalizedLanes.push_back(std::make_pair(edge, ((*it_l).permissions & SVC_PEDESTRIAN) != 0));
2680 : }
2681 : }
2682 : }
2683 : // do we even have a pedestrian lane?
2684 : int firstSidewalk = -1;
2685 9374 : for (int i = 0; i < (int)normalizedLanes.size(); ++i) {
2686 8768 : if (normalizedLanes[i].second) {
2687 : firstSidewalk = i;
2688 : break;
2689 : }
2690 : }
2691 : int hadCandidates = 0;
2692 : std::vector<int> connectedCandidates; // number of crossings that were built for each connected candidate
2693 5816 : if (firstSidewalk != -1) {
2694 : // rotate lanes to ensure that the first one allows pedestrians
2695 : std::vector<std::pair<NBEdge*, bool> > tmp;
2696 : copy(normalizedLanes.begin() + firstSidewalk, normalizedLanes.end(), std::back_inserter(tmp));
2697 : copy(normalizedLanes.begin(), normalizedLanes.begin() + firstSidewalk, std::back_inserter(tmp));
2698 5210 : normalizedLanes = tmp;
2699 : // find candidates
2700 : EdgeVector candidates;
2701 31619 : for (int i = 0; i < (int)normalizedLanes.size(); ++i) {
2702 26409 : NBEdge* edge = normalizedLanes[i].first;
2703 26409 : const bool allowsPed = normalizedLanes[i].second;
2704 : DEBUGCOUT(gDebugFlag1, " cands=" << toString(candidates) << " edge=" << edge->getID() << " allowsPed=" << allowsPed << "\n")
2705 26409 : if (!allowsPed && (candidates.size() == 0 || candidates.back() != edge)) {
2706 6697 : candidates.push_back(edge);
2707 19712 : } else if (allowsPed) {
2708 16885 : if (candidates.size() > 0) {
2709 3926 : if (hadCandidates > 0 || forbidsPedestriansAfter(normalizedLanes, i)) {
2710 2499 : hadCandidates++;
2711 2499 : const int n = checkCrossing(candidates);
2712 2499 : numGuessed += n;
2713 2499 : if (n > 0) {
2714 2275 : connectedCandidates.push_back(n);
2715 : }
2716 : }
2717 : candidates.clear();
2718 : }
2719 : }
2720 : }
2721 5210 : if (hadCandidates > 0 && candidates.size() > 0) {
2722 : // avoid wrapping around to the same sidewalk
2723 324 : hadCandidates++;
2724 324 : const int n = checkCrossing(candidates);
2725 324 : numGuessed += n;
2726 324 : if (n > 0) {
2727 266 : connectedCandidates.push_back(n);
2728 : }
2729 : }
2730 : }
2731 : // Avoid duplicate crossing between the same pair of walkingareas
2732 : DEBUGCOUT(gDebugFlag1, " hadCandidates=" << hadCandidates << " connectedCandidates=" << toString(connectedCandidates) << "\n")
2733 5210 : if (hadCandidates == 2 && connectedCandidates.size() == 2) {
2734 : // One or both of them might be split: remove the one with less splits
2735 679 : if (connectedCandidates.back() <= connectedCandidates.front()) {
2736 663 : numGuessed -= connectedCandidates.back();
2737 663 : myCrossings.erase(myCrossings.end() - connectedCandidates.back(), myCrossings.end());
2738 : } else {
2739 16 : numGuessed -= connectedCandidates.front();
2740 16 : myCrossings.erase(myCrossings.begin(), myCrossings.begin() + connectedCandidates.front());
2741 : }
2742 : }
2743 5816 : std::sort(myCrossings.begin(), myCrossings.end(), NBNodesEdgesSorter::crossing_by_junction_angle_sorter(this, myAllEdges));
2744 : #ifdef DEBUG_PED_STRUCTURES
2745 : if (gDebugFlag1) {
2746 : std::cout << "guessedCrossings:\n";
2747 : for (auto& crossing : myCrossings) {
2748 : std::cout << " edges=" << toString(crossing->edges) << "\n";
2749 : }
2750 : }
2751 : #endif
2752 5816 : if (numGuessed > 0 && isSimpleContinuation(true, true)) {
2753 : // avoid narrow node shape when there is a crossing
2754 25 : computeNodeShape(-1);
2755 125 : for (NBEdge* e : myAllEdges) {
2756 100 : e->computeEdgeShape();
2757 : }
2758 : }
2759 : return numGuessed;
2760 : }
2761 :
2762 :
2763 : int
2764 3143 : NBNode::checkCrossing(EdgeVector candidates, bool checkOnly) {
2765 : DEBUGCOUT(gDebugFlag1, "checkCrossing candidates=" << toString(candidates) << "\n")
2766 3143 : if (candidates.size() == 0) {
2767 : DEBUGCOUT(gDebugFlag1, "no crossing added (numCandidates=" << candidates.size() << ")\n")
2768 : return 0;
2769 : } else {
2770 : // check whether the edges may be part of a common crossing due to having similar angle
2771 : double prevAngle = -100000; // dummy
2772 8513 : for (int i = 0; i < (int)candidates.size(); ++i) {
2773 5652 : NBEdge* edge = candidates[i];
2774 5652 : double angle = edge->getCrossingAngle(this);
2775 : // edges should be sorted by angle but this only holds true approximately
2776 5652 : if (i > 0 && fabs(NBHelpers::relAngle(angle, prevAngle)) > EXTEND_CROSSING_ANGLE_THRESHOLD) {
2777 : DEBUGCOUT(gDebugFlag1, "no crossing added (found angle difference of " << fabs(NBHelpers::relAngle(angle, prevAngle)) << " at i=" << i << "\n")
2778 : return 0;
2779 : }
2780 13800 : if (!checkOnly && !isTLControlled() && myType != SumoXMLNodeType::RAIL_CROSSING && edge->getSpeed() > OptionsCont::getOptions().getFloat("crossings.guess.speed-threshold")) {
2781 : DEBUGCOUT(gDebugFlag1, "no crossing added (uncontrolled, edge with speed > " << edge->getSpeed() << ")\n")
2782 : return 0;
2783 : }
2784 : prevAngle = angle;
2785 : }
2786 2861 : if (candidates.size() == 1 || getType() == SumoXMLNodeType::RAIL_CROSSING) {
2787 893 : if (!checkOnly) {
2788 1786 : addCrossing(candidates, NBEdge::UNSPECIFIED_WIDTH, isTLControlled());
2789 : DEBUGCOUT(gDebugFlag1, "adding crossing: " << toString(candidates) << "\n")
2790 : }
2791 893 : return 1;
2792 : } else {
2793 : // check for intermediate walking areas
2794 : prevAngle = -100000; // dummy
2795 5900 : for (EdgeVector::iterator it = candidates.begin(); it != candidates.end(); ++it) {
2796 4092 : double angle = (*it)->getCrossingAngle(this);
2797 4092 : if (it != candidates.begin()) {
2798 2124 : NBEdge* prev = *(it - 1);
2799 2124 : NBEdge* curr = *it;
2800 : Position prevPos, currPos;
2801 : int laneI;
2802 : // compute distance between candiate edges
2803 : double intermediateWidth = 0;
2804 2124 : if (prev->getToNode() == this) {
2805 2015 : laneI = prev->getNumLanes() - 1;
2806 2015 : prevPos = prev->getLanes()[laneI].shape[-1];
2807 : } else {
2808 : laneI = 0;
2809 109 : prevPos = prev->getLanes()[laneI].shape[0];
2810 : }
2811 2124 : intermediateWidth -= 0.5 * prev->getLaneWidth(laneI);
2812 2124 : if (curr->getFromNode() == this) {
2813 2001 : laneI = curr->getNumLanes() - 1;
2814 2001 : currPos = curr->getLanes()[laneI].shape[0];
2815 : } else {
2816 : laneI = 0;
2817 123 : currPos = curr->getLanes()[laneI].shape[-1];
2818 : }
2819 2124 : intermediateWidth -= 0.5 * curr->getLaneWidth(laneI);
2820 2124 : intermediateWidth += currPos.distanceTo2D(prevPos);
2821 : DEBUGCOUT(gDebugFlag1, " prevAngle=" << prevAngle << " angle=" << angle << " intermediateWidth=" << intermediateWidth << "\n")
2822 2124 : if (fabs(NBHelpers::relAngle(prevAngle, angle)) > SPLIT_CROSSING_ANGLE_THRESHOLD
2823 2124 : || (intermediateWidth > SPLIT_CROSSING_WIDTH_THRESHOLD)) {
2824 320 : return checkCrossing(EdgeVector(candidates.begin(), it), checkOnly)
2825 320 : + checkCrossing(EdgeVector(it, candidates.end()), checkOnly);
2826 : }
2827 : }
2828 : prevAngle = angle;
2829 : }
2830 1808 : if (!checkOnly) {
2831 3616 : addCrossing(candidates, NBEdge::UNSPECIFIED_WIDTH, isTLControlled());
2832 : DEBUGCOUT(gDebugFlag1, "adding crossing: " << toString(candidates) << "\n")
2833 : }
2834 1808 : return 1;
2835 : }
2836 : }
2837 : }
2838 :
2839 :
2840 : bool
2841 288 : NBNode::checkCrossingDuplicated(EdgeVector edges) {
2842 : // sort edge vector
2843 288 : std::sort(edges.begin(), edges.end());
2844 : // iterate over crossing to find a crossing with the same edges
2845 794 : for (auto& crossing : myCrossings) {
2846 : // sort edges of crossing before compare
2847 509 : EdgeVector edgesOfCrossing = crossing->edges;
2848 509 : std::sort(edgesOfCrossing.begin(), edgesOfCrossing.end());
2849 509 : if (edgesOfCrossing == edges) {
2850 : return true;
2851 : }
2852 : }
2853 : return false;
2854 : }
2855 :
2856 :
2857 : bool
2858 1288 : NBNode::forbidsPedestriansAfter(std::vector<std::pair<NBEdge*, bool> > normalizedLanes, int startIndex) {
2859 3929 : for (int i = startIndex; i < (int)normalizedLanes.size(); ++i) {
2860 3790 : if (!normalizedLanes[i].second) {
2861 : return true;
2862 : }
2863 : }
2864 : return false;
2865 : }
2866 :
2867 :
2868 : void
2869 6500 : NBNode::buildCrossingsAndWalkingAreas() {
2870 6500 : buildCrossings();
2871 13000 : buildWalkingAreas(OptionsCont::getOptions().getInt("junctions.corner-detail"),
2872 6500 : OptionsCont::getOptions().getFloat("walkingareas.join-dist"));
2873 6500 : buildCrossingOutlines();
2874 : // ensure that all crossings are properly connected
2875 6500 : bool recheck = myCrossings.size() > 0;
2876 7739 : while (recheck) {
2877 : recheck = false;
2878 : std::set<std::string> waIDs;
2879 : int numSidewalks = 0;
2880 4630 : for (WalkingArea& wa : myWalkingAreas) {
2881 3391 : waIDs.insert(wa.id);
2882 3391 : numSidewalks += (int)(wa.prevSidewalks.size() + wa.nextSidewalks.size());
2883 : }
2884 1239 : if (numSidewalks < 2) {
2885 : // all crossings are invalid if there are fewer than 2 sidewalks involved
2886 : waIDs.clear();
2887 : }
2888 3715 : for (auto& crossing : myCrossings) {
2889 2476 : if (waIDs.count(crossing->prevWalkingArea) == 0 || waIDs.count(crossing->nextWalkingArea) == 0 || !crossing->valid) {
2890 47 : if (crossing->valid) {
2891 46 : WRITE_WARNINGF(TL("Discarding invalid crossing '%' at junction '%' with edges [%] (no walkingarea found)."),
2892 : crossing->id, getID(), toString(crossing->edges));
2893 : recheck = true;
2894 : }
2895 180 : for (auto waIt = myWalkingAreas.begin(); waIt != myWalkingAreas.end();) {
2896 : WalkingArea& wa = *waIt;
2897 133 : std::vector<std::string>::iterator it_nc = std::find(wa.nextCrossings.begin(), wa.nextCrossings.end(), crossing->id);
2898 133 : if (it_nc != wa.nextCrossings.end()) {
2899 12 : wa.nextCrossings.erase(it_nc);
2900 : }
2901 133 : if (wa.prevSidewalks.size() + wa.nextSidewalks.size() + wa.nextCrossings.size() + wa.prevCrossings.size() < 2) {
2902 10 : waIt = myWalkingAreas.erase(waIt);
2903 : recheck = true;
2904 : } else {
2905 : waIt++;
2906 : }
2907 : }
2908 47 : crossing->valid = false;
2909 47 : crossing->prevWalkingArea = "";
2910 47 : crossing->nextWalkingArea = "";
2911 : }
2912 : }
2913 : }
2914 6500 : }
2915 :
2916 :
2917 : std::vector<NBNode::Crossing*>
2918 1340591 : NBNode::getCrossings() const {
2919 : std::vector<Crossing*> result;
2920 1751612 : for (auto& c : myCrossings) {
2921 411021 : if (c->valid) {
2922 407829 : result.push_back(c.get());
2923 : }
2924 : }
2925 : //if (myCrossings.size() > 0) {
2926 : // std::cout << "valid crossings at " << getID() << "\n";
2927 : // for (std::vector<NBNode::Crossing*>::const_iterator it = result.begin(); it != result.end(); ++it) {
2928 : // std::cout << " " << toString((*it)->edges) << "\n";
2929 : // }
2930 : //}
2931 1340591 : return result;
2932 : }
2933 :
2934 :
2935 : void
2936 33402 : NBNode::discardAllCrossings(bool rejectAll) {
2937 : myCrossings.clear();
2938 : // also discard all further crossings
2939 33402 : if (rejectAll) {
2940 1 : myDiscardAllCrossings = true;
2941 : }
2942 33402 : }
2943 :
2944 :
2945 : void
2946 65310 : NBNode::discardWalkingareas() {
2947 : myWalkingAreas.clear();
2948 65310 : }
2949 :
2950 :
2951 : double
2952 38418 : NBNode::buildInnerEdges() {
2953 : // myDisplacementError is computed during this operation. reset first
2954 38418 : myDisplacementError = 0.;
2955 : // build inner edges for vehicle movements across the junction
2956 : int noInternalNoSplits = 0;
2957 105080 : for (const NBEdge* const edge : myIncomingEdges) {
2958 187977 : for (const NBEdge::Connection& con : edge->getConnections()) {
2959 121315 : if (con.toEdge == nullptr) {
2960 0 : continue;
2961 : }
2962 121315 : noInternalNoSplits++;
2963 : }
2964 : }
2965 38418 : int lno = 0;
2966 38418 : int splitNo = 0;
2967 : double maxCrossingSeconds = 0.;
2968 105080 : for (NBEdge* const edge : myIncomingEdges) {
2969 66662 : maxCrossingSeconds = MAX2(maxCrossingSeconds, edge->buildInnerEdges(*this, noInternalNoSplits, lno, splitNo));
2970 : }
2971 38418 : return maxCrossingSeconds;
2972 : }
2973 :
2974 :
2975 : int
2976 6500 : NBNode::buildCrossings() {
2977 : #ifdef DEBUG_PED_STRUCTURES
2978 : gDebugFlag1 = DEBUGCOND;
2979 : #endif
2980 : DEBUGCOUT(gDebugFlag1, "build crossings for " << getID() << ":\n")
2981 6500 : if (myDiscardAllCrossings) {
2982 : myCrossings.clear();
2983 : }
2984 : int index = 0;
2985 13000 : const double defaultWidth = OptionsCont::getOptions().getFloat("default.crossing-width");
2986 8930 : for (auto& c : myCrossings) {
2987 2430 : c->valid = true;
2988 2430 : if (!isTLControlled()) {
2989 1603 : c->tlID = ""; // reset for Netedit, set via setCrossingTLIndices()
2990 : }
2991 4860 : c->id = ":" + getID() + "_c" + toString(index++);
2992 2430 : c->width = (c->customWidth == NBEdge::UNSPECIFIED_WIDTH) ? defaultWidth : c->customWidth;
2993 : // reset fields, so repeated computation (Netedit) will successfully perform the checks
2994 : // in buildWalkingAreas (split crossings) and buildInnerEdges (sanity check)
2995 2430 : c->nextWalkingArea = "";
2996 2430 : c->prevWalkingArea = "";
2997 : EdgeVector& edges = c->edges;
2998 : DEBUGCOUT(gDebugFlag1, " crossing=" << c->id << " edges=" << toString(edges))
2999 : // sorting the edges in the right way is imperative. We want to sort
3000 : // them by getAngleAtNodeToCenter() but need to be extra carefull to avoid wrapping around 0 somewhere in between
3001 2430 : std::sort(edges.begin(), edges.end(), NBContHelper::edge_by_angle_to_nodeShapeCentroid_sorter(this));
3002 : DEBUGCOUT(gDebugFlag1, " sortedEdges=" << toString(edges) << "\n")
3003 : // rotate the edges so that the largest relative angle difference comes at the end
3004 : std::vector<double> rawAngleDiffs;
3005 : double maxAngleDiff = 0;
3006 : int maxAngleDiffIndex = 0; // index before maxDist
3007 6650 : for (int i = 0; i < (int) edges.size(); i++) {
3008 4220 : double diff = NBHelpers::relAngle(edges[i]->getAngleAtNodeToCenter(this),
3009 4220 : edges[(i + 1) % edges.size()]->getAngleAtNodeToCenter(this));
3010 4220 : if (diff < 0) {
3011 1619 : diff += 360;
3012 : }
3013 4220 : const double rawDiff = NBHelpers::relAngle(
3014 : edges[i]->getAngleAtNodeNormalized(this),
3015 4220 : edges[(i + 1) % edges.size()]->getAngleAtNodeNormalized(this));
3016 4220 : rawAngleDiffs.push_back(fabs(rawDiff));
3017 :
3018 : DEBUGCOUT(gDebugFlag1, " i=" << i << " a1=" << edges[i]->getAngleAtNodeToCenter(this) << " a2=" << edges[(i + 1) % edges.size()]->getAngleAtNodeToCenter(this) << " diff=" << diff << "\n")
3019 4220 : if (diff > maxAngleDiff) {
3020 : maxAngleDiff = diff;
3021 : maxAngleDiffIndex = i;
3022 : }
3023 : }
3024 2430 : if (maxAngleDiff > 2 && maxAngleDiff < 360 - 2) {
3025 : // if the angle differences is too small, we better not rotate
3026 1518 : std::rotate(edges.begin(), edges.begin() + (maxAngleDiffIndex + 1) % edges.size(), edges.end());
3027 : DEBUGCOUT(gDebugFlag1, " rotatedEdges=" << toString(edges))
3028 : }
3029 : bool diagonalCrossing = false;
3030 2430 : std::sort(rawAngleDiffs.begin(), rawAngleDiffs.end());
3031 2430 : if (rawAngleDiffs.size() >= 2 && rawAngleDiffs[rawAngleDiffs.size() - 2] > 30) {
3032 : diagonalCrossing = true;
3033 : #ifdef DEBUG_PED_STRUCTURES
3034 : if (gDebugFlag1) {
3035 : std::cout << " detected pedScramble " << c->id << " edges=" << toString(edges) << " rawDiffs=" << toString(rawAngleDiffs) << "\n";
3036 : for (auto e : edges) {
3037 : std::cout << " e=" << e->getID()
3038 : << " aC=" << e->getAngleAtNodeToCenter(this)
3039 : << " a=" << e->getAngleAtNode(this)
3040 : << " aN=" << e->getAngleAtNodeNormalized(this)
3041 : << "\n";
3042 : }
3043 : }
3044 : #endif
3045 : }
3046 : // reverse to get them in CCW order (walking direction around the node)
3047 : std::reverse(edges.begin(), edges.end());
3048 : // compute shape
3049 : c->shape.clear();
3050 2430 : const int begDir = (edges.front()->getFromNode() == this ? FORWARD : BACKWARD);
3051 2430 : const int endDir = (edges.back()->getToNode() == this ? FORWARD : BACKWARD);
3052 2430 : int firstNonPedLane = edges.front()->getFirstNonPedestrianLaneIndex(begDir);
3053 2430 : int lastNonPedLane = edges.back()->getFirstNonPedestrianLaneIndex(endDir);
3054 : DEBUGCOUT(gDebugFlag1, " finalEdges=" << toString(edges) << " firstNonPedLane=" << firstNonPedLane << " lastNonPedLane=" << lastNonPedLane << "\n")
3055 2430 : if (firstNonPedLane < 0 || lastNonPedLane < 0) {
3056 : // invalid crossing
3057 12 : WRITE_WARNINGF(TL("Discarding invalid crossing '%' at junction '%' with edges [%] (no vehicle lanes to cross)."), c->id, getID(), toString(c->edges));
3058 4 : c->valid = false;
3059 : // compute surrogate shape to make it visible in netedit
3060 4 : firstNonPedLane = begDir == FORWARD ? 0 : edges.front()->getNumLanes() - 1;
3061 4 : lastNonPedLane = endDir == FORWARD ? 0 : edges.back()->getNumLanes() - 1;
3062 : }
3063 2430 : if (c->customShape.size() != 0) {
3064 : c->shape = c->customShape;
3065 : } else {
3066 2412 : NBEdge::Lane crossingBeg = edges.front()->getLanes()[firstNonPedLane];
3067 2412 : NBEdge::Lane crossingEnd = edges.back()->getLanes()[lastNonPedLane];
3068 2412 : crossingBeg.width = (crossingBeg.width == NBEdge::UNSPECIFIED_WIDTH ? SUMO_const_laneWidth : crossingBeg.width);
3069 2412 : crossingEnd.width = (crossingEnd.width == NBEdge::UNSPECIFIED_WIDTH ? SUMO_const_laneWidth : crossingEnd.width);
3070 2412 : crossingBeg.shape.move2side(begDir * crossingBeg.width / 2);
3071 2412 : crossingEnd.shape.move2side(endDir * crossingEnd.width / 2);
3072 2412 : crossingBeg.shape.extrapolate(c->width / 2);
3073 2412 : crossingEnd.shape.extrapolate(c->width / 2);
3074 : // check if after all changes shape are NAN (in these case, discard)
3075 2412 : if (crossingBeg.shape.isNAN() || crossingEnd.shape.isNAN()) {
3076 0 : WRITE_WARNINGF(TL("Discarding invalid crossing '%' at junction '%' with edges [%] (invalid shape)."), c->id, getID(), toString(c->edges));
3077 0 : c->valid = false;
3078 : } else {
3079 2836 : c->shape.push_back(crossingBeg.shape[begDir == FORWARD ? 0 : -1]);
3080 2771 : c->shape.push_back(crossingEnd.shape[endDir == FORWARD ? -1 : 0]);
3081 : }
3082 2412 : if (diagonalCrossing) {
3083 7 : c->shape.move2side(-c->width);
3084 : }
3085 2412 : }
3086 : }
3087 6500 : return index;
3088 : }
3089 :
3090 :
3091 : void
3092 6500 : NBNode::buildWalkingAreas(int cornerDetail, double joinMinDist) {
3093 : #ifdef DEBUG_PED_STRUCTURES
3094 : gDebugFlag1 = DEBUGCOND;
3095 : #endif
3096 : int index = 0;
3097 6500 : myWalkingAreas.clear();
3098 : DEBUGCOUT(gDebugFlag1, "build walkingAreas for " << getID() << ":\n")
3099 6500 : if (myAllEdges.size() == 0) {
3100 0 : return;
3101 : }
3102 6500 : EdgeVector allEdges = getEdgesSortedByAngleAtNodeCenter();
3103 : // shapes are all pointing away from the intersection
3104 : std::vector<std::pair<NBEdge*, NBEdge::Lane> > normalizedLanes;
3105 28864 : for (EdgeVector::const_iterator it = allEdges.begin(); it != allEdges.end(); ++it) {
3106 22364 : NBEdge* edge = *it;
3107 : const std::vector<NBEdge::Lane>& lanes = edge->getLanes();
3108 22364 : if (edge->getFromNode() == this) {
3109 28440 : for (std::vector<NBEdge::Lane>::const_reverse_iterator it_l = lanes.rbegin(); it_l != lanes.rend(); ++it_l) {
3110 17258 : NBEdge::Lane l = *it_l;
3111 34516 : l.shape = l.shape.getSubpartByIndex(0, 2);
3112 26337 : l.width = (l.width == NBEdge::UNSPECIFIED_WIDTH ? SUMO_const_laneWidth : l.width);
3113 17258 : normalizedLanes.push_back(std::make_pair(edge, l));
3114 17258 : }
3115 : } else {
3116 28440 : for (std::vector<NBEdge::Lane>::const_iterator it_l = lanes.begin(); it_l != lanes.end(); ++it_l) {
3117 17258 : NBEdge::Lane l = *it_l;
3118 34516 : l.shape = l.shape.reverse();
3119 34516 : l.shape = l.shape.getSubpartByIndex(0, 2);
3120 26337 : l.width = (l.width == NBEdge::UNSPECIFIED_WIDTH ? SUMO_const_laneWidth : l.width);
3121 17258 : normalizedLanes.push_back(std::make_pair(edge, l));
3122 17258 : }
3123 : }
3124 : }
3125 : //if (gDebugFlag1) std::cout << " normalizedLanes=" << normalizedLanes.size() << "\n";
3126 : // collect [start,count[ indices in normalizedLanes that belong to a walkingArea
3127 : std::vector<std::pair<int, int> > waIndices;
3128 : int start = -1;
3129 6500 : NBEdge* prevEdge = normalizedLanes.back().first;
3130 41016 : for (int i = 0; i < (int)normalizedLanes.size(); ++i) {
3131 34516 : NBEdge* edge = normalizedLanes[i].first;
3132 : NBEdge::Lane& l = normalizedLanes[i].second;
3133 34516 : if (start == -1) {
3134 20717 : if ((l.permissions & SVC_PEDESTRIAN) != 0) {
3135 : start = i;
3136 : }
3137 : } else {
3138 13799 : if ((l.permissions & SVC_PEDESTRIAN) == 0
3139 9769 : || crossingBetween(edge, prevEdge)
3140 9765 : || alreadyConnectedPaths(edge, prevEdge, joinMinDist)
3141 23441 : || crossesFringe(edge, prevEdge)
3142 : ) {
3143 4161 : waIndices.push_back(std::make_pair(start, i - start));
3144 4161 : if ((l.permissions & SVC_PEDESTRIAN) != 0) {
3145 : start = i;
3146 : } else {
3147 : start = -1;
3148 : }
3149 :
3150 : }
3151 : }
3152 : DEBUGCOUT(gDebugFlag1, " i=" << i << " edge=" << edge->getID() << " start=" << start << " ped=" << ((l.permissions & SVC_PEDESTRIAN) != 0)
3153 : << " waI=" << waIndices.size() << " crossingBetween=" << crossingBetween(edge, prevEdge) << "\n")
3154 : prevEdge = edge;
3155 : }
3156 : // deal with wrap-around issues
3157 6500 : if (start != - 1) {
3158 4881 : const int waNumLanes = (int)normalizedLanes.size() - start;
3159 4881 : if (waIndices.size() == 0) {
3160 3579 : waIndices.push_back(std::make_pair(start, waNumLanes));
3161 : DEBUGCOUT(gDebugFlag1, " single wa, end at wrap-around\n")
3162 : } else {
3163 1302 : if (waIndices.front().first == 0) {
3164 1148 : NBEdge* edge = normalizedLanes.front().first;
3165 1148 : if (crossingBetween(edge, normalizedLanes.back().first)
3166 1148 : || crossesFringe(edge, normalizedLanes.back().first)) {
3167 : // do not wrap-around (see above)
3168 0 : waIndices.push_back(std::make_pair(start, waNumLanes));
3169 : DEBUGCOUT(gDebugFlag1, " do not wrap around\n")
3170 : } else {
3171 : // first walkingArea wraps around
3172 1148 : waIndices.front().first = start;
3173 1148 : waIndices.front().second = waNumLanes + waIndices.front().second;
3174 : DEBUGCOUT(gDebugFlag1, " wrapping around\n")
3175 : }
3176 : } else {
3177 : // last walkingArea ends at the wrap-around
3178 154 : waIndices.push_back(std::make_pair(start, waNumLanes));
3179 : DEBUGCOUT(gDebugFlag1, " end at wrap-around\n")
3180 : }
3181 : }
3182 : }
3183 : #ifdef DEBUG_PED_STRUCTURES
3184 : if (gDebugFlag1) {
3185 : std::cout << " normalizedLanes=" << normalizedLanes.size() << " waIndices:\n";
3186 : for (int i = 0; i < (int)waIndices.size(); ++i) {
3187 : std::cout << " " << waIndices[i].first << ", " << waIndices[i].second << "\n";
3188 : }
3189 : }
3190 : #endif
3191 : // build walking areas connected to a sidewalk
3192 14394 : for (int i = 0; i < (int)waIndices.size(); ++i) {
3193 7894 : const bool buildExtensions = waIndices[i].second != (int)normalizedLanes.size();
3194 7894 : int startIdx = waIndices[i].first;
3195 7894 : const int prev = startIdx > 0 ? startIdx - 1 : (int)normalizedLanes.size() - 1;
3196 : const int count = waIndices[i].second;
3197 7894 : const int end = (startIdx + count) % normalizedLanes.size();
3198 7894 : int lastIdx = (startIdx + count - 1) % normalizedLanes.size();
3199 :
3200 15788 : WalkingArea wa(":" + getID() + "_w" + toString(index++), 1);
3201 : DEBUGCOUT(gDebugFlag1, "build walkingArea " << wa.id << " start=" << startIdx << " end=" << end << " count=" << count << " prev=" << prev << ":\n")
3202 : double endCrossingWidth = 0;
3203 : double startCrossingWidth = 0;
3204 7894 : PositionVector endCrossingShape;
3205 7894 : PositionVector startCrossingShape;
3206 : // check for connected crossings
3207 : bool connectsCrossing = false;
3208 : bool crossingNearSidewalk = false;
3209 : int numCrossings = 0;
3210 : std::vector<Position> connectedPoints;
3211 15917 : for (auto c : getCrossings()) {
3212 : DEBUGCOUT(gDebugFlag1, " crossing=" << c->id << " sortedEdges=" << toString(c->edges) << "\n")
3213 8023 : if (c->edges.back() == normalizedLanes[end].first
3214 8023 : && (normalizedLanes[end].second.permissions & SVC_PEDESTRIAN) == 0) {
3215 : // crossing ends
3216 2218 : if (c->nextWalkingArea != "") {
3217 3 : WRITE_WARNINGF(TL("Invalid pedestrian topology at junction '%'; crossing '%' targets '%' and '%'."),
3218 : getID(), c->id, c->nextWalkingArea, wa.id);
3219 1 : c->valid = false;
3220 : }
3221 : c->nextWalkingArea = wa.id;
3222 2218 : wa.prevCrossings.push_back(c->id);
3223 2218 : if ((int)c->edges.size() < wa.minPrevCrossingEdges) {
3224 : // if there are multiple crossings, use the shape of the one that crosses fewer edges
3225 2218 : endCrossingWidth = c->width;
3226 : endCrossingShape = c->shape;
3227 2218 : wa.width = MAX2(wa.width, endCrossingWidth);
3228 : connectsCrossing = true;
3229 2218 : connectedPoints.push_back(c->shape[-1]);
3230 2218 : wa.minPrevCrossingEdges = (int)c->edges.size();
3231 2218 : numCrossings++;
3232 2218 : if (normalizedLanes[lastIdx].second.shape[0].distanceTo2D(connectedPoints.back()) < endCrossingWidth) {
3233 : crossingNearSidewalk = true;
3234 : DEBUGCOUT(gDebugFlag1, " nearSidewalk\n")
3235 : }
3236 : }
3237 : DEBUGCOUT(gDebugFlag1, " crossing " << c->id << " ends\n")
3238 : }
3239 8023 : if (c->edges.front() == normalizedLanes[prev].first
3240 8023 : && (normalizedLanes[prev].second.permissions & SVC_PEDESTRIAN) == 0) {
3241 : // crossing starts
3242 2218 : if (c->prevWalkingArea != "") {
3243 0 : WRITE_WARNINGF(TL("Invalid pedestrian topology at junction '%'; crossing '%' is targeted by '%' and '%'."),
3244 : getID(), c->id, c->prevWalkingArea, wa.id);
3245 0 : c->valid = false;
3246 : }
3247 2218 : if (c->valid && std::find(wa.prevCrossings.begin(), wa.prevCrossings.end(), c->id) != wa.prevCrossings.end()) {
3248 9 : WRITE_WARNINGF(TL("Invalid pedestrian topology at junction '%'; crossing '%' starts and ends at walkingarea '%'."),
3249 : getID(), c->id, wa.id);
3250 3 : c->valid = false;
3251 : }
3252 : c->prevWalkingArea = wa.id;
3253 2218 : wa.nextCrossings.push_back(c->id);
3254 2218 : if ((int)c->edges.size() < wa.minNextCrossingEdges) {
3255 : // if there are multiple crossings, use the shape of the one that crosses fewer edges
3256 2218 : startCrossingWidth = c->width;
3257 : startCrossingShape = c->shape;
3258 2218 : wa.width = MAX2(wa.width, startCrossingWidth);
3259 : connectsCrossing = true;
3260 2218 : connectedPoints.push_back(c->shape[0]);
3261 2218 : wa.minNextCrossingEdges = (int)c->edges.size();
3262 2218 : numCrossings++;
3263 2218 : if (normalizedLanes[startIdx].second.shape[0].distanceTo2D(connectedPoints.back()) < startCrossingWidth) {
3264 : crossingNearSidewalk = true;
3265 : DEBUGCOUT(gDebugFlag1, " nearSidewalk\n")
3266 : }
3267 : }
3268 : DEBUGCOUT(gDebugFlag1, " crossing " << c->id << " starts\n")
3269 : }
3270 : DEBUGCOUT(gDebugFlag1, " check connections to crossing " << c->id
3271 : << " cFront=" << c->edges.front()->getID() << " cBack=" << c->edges.back()->getID()
3272 : << " wEnd=" << normalizedLanes[end].first->getID() << " wStart=" << normalizedLanes[startIdx].first->getID()
3273 : << " wStartPrev=" << normalizedLanes[prev].first->getID()
3274 : << "\n")
3275 : }
3276 7894 : if (count < 2 && !connectsCrossing) {
3277 : // not relevant for walking
3278 : DEBUGCOUT(gDebugFlag1, " not relevant for walking: count=" << count << " connectsCrossing=" << connectsCrossing << "\n")
3279 1031 : continue;
3280 : }
3281 : // build shape and connections
3282 : std::set<const NBEdge*, ComparatorIdLess>& connected = wa.refEdges;
3283 24512 : for (int j = 0; j < count; ++j) {
3284 17649 : const int nlI = (startIdx + j) % normalizedLanes.size();
3285 17649 : NBEdge* edge = normalizedLanes[nlI].first;
3286 17649 : NBEdge::Lane l = normalizedLanes[nlI].second;
3287 28308 : wa.width = MAX2(wa.width, l.width);
3288 : if (connected.count(edge) == 0) {
3289 17599 : if (edge->getFromNode() == this) {
3290 8858 : wa.nextSidewalks.push_back(edge->getSidewalkID());
3291 8858 : connectedPoints.push_back(edge->getLaneShape(0)[0]);
3292 : } else {
3293 8741 : wa.prevSidewalks.push_back(edge->getSidewalkID());
3294 8741 : connectedPoints.push_back(edge->getLaneShape(0)[-1]);
3295 : }
3296 : DEBUGCOUT(gDebugFlag1, " connectedEdge=" << edge->getID() << " connectedPoint=" << connectedPoints.back() << "\n")
3297 : connected.insert(edge);
3298 : }
3299 17649 : l.shape.move2side(-l.width / 2);
3300 17649 : wa.shape.push_back_noDoublePos(l.shape[0]);
3301 17649 : l.shape.move2side(l.width);
3302 17649 : wa.shape.push_back(l.shape[0]);
3303 17649 : }
3304 6863 : if (buildExtensions) {
3305 : // extension at starting crossing
3306 4087 : if (startCrossingShape.size() > 0) {
3307 2208 : startCrossingShape.move2side(startCrossingWidth / 2);
3308 2208 : wa.shape.push_front_noDoublePos(startCrossingShape[0]); // right corner
3309 2208 : startCrossingShape.move2side(-startCrossingWidth);
3310 2208 : wa.shape.push_front_noDoublePos(startCrossingShape[0]); // left corner goes first
3311 : DEBUGCOUT(gDebugFlag1, " extension at startCrossingShape=" << endCrossingShape << " waShape=" << wa.shape << "\n")
3312 : }
3313 : // extension at ending crossing
3314 4087 : if (endCrossingShape.size() > 0) {
3315 2208 : endCrossingShape.move2side(endCrossingWidth / 2);
3316 2208 : wa.shape.push_back_noDoublePos(endCrossingShape[-1]);
3317 2208 : endCrossingShape.move2side(-endCrossingWidth);
3318 2208 : wa.shape.push_back_noDoublePos(endCrossingShape[-1]);
3319 : DEBUGCOUT(gDebugFlag1, " extension at endCrossingShape=" << endCrossingShape << " waShape=" << wa.shape << "\n")
3320 : }
3321 : }
3322 3557 : if (connected.size() == 2 && !connectsCrossing && wa.nextSidewalks.size() == 1 && wa.prevSidewalks.size() == 1
3323 8384 : && normalizedLanes.size() == 2) {
3324 : // do not build a walkingArea since a normal connection exists
3325 767 : const NBEdge* e1 = *connected.begin();
3326 767 : const NBEdge* e2 = *(++connected.begin());
3327 767 : if (e1->hasConnectionTo(e2, 0, 0) || e2->hasConnectionTo(e1, 0, 0)) {
3328 : DEBUGCOUT(gDebugFlag1, " not building a walkingarea since normal connections exist\n")
3329 251 : continue;
3330 : }
3331 : }
3332 6612 : if (count == (int)normalizedLanes.size()) {
3333 : // junction is covered by the whole walkingarea
3334 : wa.shape = myPoly;
3335 : // increase walking width if the walkingare is wider than a single lane
3336 6662 : for (const NBEdge* in : myIncomingEdges) {
3337 11722 : for (const NBEdge* out : myOutgoingEdges) {
3338 8934 : if (in->getFromNode() == out->getToNode() && in->getInnerGeometry().reverse() == out->getInnerGeometry()
3339 1349 : && (in->getPermissions() & SVC_PEDESTRIAN)
3340 8934 : && (out->getPermissions() & SVC_PEDESTRIAN)) {
3341 : // doesn't catch all cases but probably most
3342 2640 : wa.width = MAX2(wa.width, in->getTotalWidth() + out->getTotalWidth());
3343 : }
3344 : }
3345 : }
3346 4087 : } else if (cornerDetail > 0) {
3347 : // build smooth inner curve (optional)
3348 : int smoothEnd = end;
3349 : int smoothPrev = prev;
3350 : // extend to green verge
3351 3899 : if (endCrossingWidth > 0 && normalizedLanes[smoothEnd].second.permissions == 0) {
3352 141 : smoothEnd = (smoothEnd + 1) % normalizedLanes.size();
3353 : }
3354 3899 : if (startCrossingWidth > 0 && normalizedLanes[smoothPrev].second.permissions == 0) {
3355 137 : if (smoothPrev == 0) {
3356 0 : smoothPrev = (int)normalizedLanes.size() - 1;
3357 : } else {
3358 137 : smoothPrev--;
3359 : }
3360 : }
3361 3899 : PositionVector begShape = normalizedLanes[smoothEnd].second.shape;
3362 7798 : begShape = begShape.reverse();
3363 : double shiftBegExtra = 0;
3364 : double shiftEndExtra = 0;
3365 3899 : if (lastIdx == startIdx) {
3366 734 : lastIdx = (startIdx + 1) % normalizedLanes.size();
3367 : DEBUGCOUT(gDebugFlag1, " new lastIdx=" << lastIdx << " startEdge=" << normalizedLanes[startIdx].first->getID() << " lastEdge=" << normalizedLanes[lastIdx].first->getID() << "\n")
3368 734 : if (normalizedLanes[startIdx].first == normalizedLanes[lastIdx].first) {
3369 : lastIdx = startIdx;
3370 179 : startIdx--;
3371 179 : if (startIdx < 0) {
3372 45 : startIdx = (int)normalizedLanes.size() - 1;
3373 : }
3374 : DEBUGCOUT(gDebugFlag1, " new startIdx=" << startIdx << " startEdge=" << normalizedLanes[startIdx].first->getID() << " lastEdge=" << normalizedLanes[lastIdx].first->getID() << "\n")
3375 358 : shiftEndExtra += OptionsCont::getOptions().getFloat("default.sidewalk-width");
3376 : } else {
3377 1110 : shiftBegExtra += OptionsCont::getOptions().getFloat("default.sidewalk-width");
3378 : }
3379 : }
3380 3899 : PositionVector begShapeOuter = normalizedLanes[lastIdx].second.shape;
3381 7798 : begShapeOuter = begShapeOuter.reverse();
3382 : //begShape.extrapolate(endCrossingWidth);
3383 3899 : begShape.move2side(normalizedLanes[smoothEnd].second.width / 2);
3384 3899 : begShapeOuter.move2side(normalizedLanes[lastIdx].second.width / 2 + shiftBegExtra);
3385 3899 : PositionVector endShape = normalizedLanes[smoothPrev].second.shape;
3386 3899 : PositionVector endShapeOuter = normalizedLanes[startIdx].second.shape;;
3387 3899 : endShape.move2side(normalizedLanes[smoothPrev].second.width / 2);
3388 3899 : endShapeOuter.move2side(normalizedLanes[startIdx].second.width / 2 + shiftEndExtra);
3389 : //endShape.extrapolate(startCrossingWidth);
3390 3899 : PositionVector curve;
3391 3899 : if (count != (int)normalizedLanes.size() || count == 2) {
3392 3899 : const double angle = GeomHelper::angleDiff(begShape.angleAt2D(-2), endShape.angleAt2D(0));
3393 3899 : if (count == 1 && angle > 0 && crossingNearSidewalk && numCrossings < 2) {
3394 : // do not build smooth shape for an unconnected left turn
3395 : // (the walkingArea would get bigger without a reason to
3396 : // walk there)
3397 3755 : } else if ((normalizedLanes[smoothEnd].first->getPermissions() & normalizedLanes[smoothPrev].first->getPermissions() &
3398 : ~(SVC_PEDESTRIAN | SVC_RAIL_CLASSES)) != 0) {
3399 : DEBUGCOUT(gDebugFlag1, " traffic curve\n")
3400 10191 : curve = computeSmoothShape(begShape, endShape, cornerDetail + 2, false, 25, 25, gDebugFlag1 ? this : nullptr);
3401 3397 : if (curve.length2D() - begShape.back().distanceTo2D(endShape.front()) > 5) {
3402 : DEBUGCOUT(gDebugFlag1, " reduceBulge directLength=" << begShape.back().distanceTo2D(endShape.front())
3403 : << " curveLength=" << curve.length2D()
3404 : << " delta=" << curve.length2D() - begShape.back().distanceTo2D(endShape.front())
3405 : << "\n")
3406 74 : curve = computeSmoothShape(begShape, endShape, cornerDetail + 2, false, 25, 25, nullptr, AVOID_WIDE_LEFT_TURN | AVOID_INTERSECTING_LEFT_TURNS);
3407 : }
3408 : } else {
3409 : DEBUGCOUT(gDebugFlag1, " nonTraffic curve\n")
3410 358 : const double extend = MIN2(10.0, begShape.back().distanceTo2D(endShape.front()) / 2);
3411 716 : curve = computeSmoothShape(begShape, endShape, cornerDetail + 2, false, extend, extend, nullptr, FOUR_CONTROL_POINTS);
3412 : }
3413 3899 : if (curve.size() > 2) {
3414 : curve.erase(curve.begin());
3415 : curve.pop_back();
3416 1738 : if (endCrossingWidth > 0) {
3417 : wa.shape.pop_back();
3418 : }
3419 1738 : if (startCrossingWidth > 0) {
3420 : wa.shape.erase(wa.shape.begin());
3421 : }
3422 1738 : if (count == (int)normalizedLanes.size()) {
3423 0 : curve = curve.reverse();
3424 : }
3425 1738 : wa.shape.append(curve, 0);
3426 : }
3427 : DEBUGCOUT(gDebugFlag1, " end=" << smoothEnd << " prev=" << smoothPrev
3428 : << " endCrossingWidth=" << endCrossingWidth << " startCrossingWidth=" << startCrossingWidth
3429 : << " begShape=" << begShape << " endShape=" << endShape << " smooth curve=" << curve
3430 : << " begShapeOuter=" << begShapeOuter << " endShapeOuter=" << endShapeOuter
3431 : << " waShape=" << wa.shape
3432 : << "\n")
3433 : }
3434 3899 : if (curve.size() > 2 && (count == 2 || (count == 1 && numCrossings > 0))) {
3435 1538 : const double innerDist = begShape.back().distanceTo2D(endShape[0]);
3436 1538 : const double outerDist = begShapeOuter.back().distanceTo2D(endShapeOuter[0]);
3437 : DEBUGCOUT(gDebugFlag1, " innerDist=" << innerDist << " outerDist=" << outerDist << "\n")
3438 1538 : if (outerDist > innerDist) {
3439 : // we also need a rounded outer curve (unless we have only a single walkingarea)
3440 148 : const double extend = MIN2(10.0, begShapeOuter.back().distanceTo2D(endShapeOuter.front()) / 2);
3441 296 : curve = computeSmoothShape(begShapeOuter, endShapeOuter, cornerDetail + 2, false, extend, extend, nullptr);
3442 148 : if (curve.length2D() - begShapeOuter.back().distanceTo2D(endShapeOuter.front()) > 5) {
3443 : DEBUGCOUT(gDebugFlag1, " reduceBulge directLength=" << begShapeOuter.back().distanceTo2D(endShapeOuter.front())
3444 : << " curveLength=" << curve.length2D()
3445 : << " delta=" << curve.length2D() - begShapeOuter.back().distanceTo2D(endShapeOuter.front())
3446 : << "\n")
3447 44 : curve = computeSmoothShape(begShapeOuter, endShapeOuter, cornerDetail + 2, false, 25, 25, nullptr, AVOID_WIDE_LEFT_TURN | AVOID_INTERSECTING_LEFT_TURNS);
3448 : }
3449 296 : curve = curve.reverse();
3450 : // keep the points in case of extraShift
3451 148 : if (shiftBegExtra != 0) {
3452 14 : curve.push_front_noDoublePos(wa.shape[1]);
3453 14 : curve.push_back_noDoublePos(wa.shape[2]);
3454 134 : } else if (shiftEndExtra != 0) {
3455 5 : curve.push_back_noDoublePos(wa.shape[1]);
3456 5 : curve.push_back_noDoublePos(wa.shape[2]);
3457 : }
3458 : DEBUGCOUT(gDebugFlag1, " outerCurveRaw=" << curve << " wa1=" << wa.shape[1] << " wa2=" << wa.shape[2] << "\n")
3459 : wa.shape.erase(wa.shape.begin() + 1, wa.shape.begin() + 3);
3460 148 : wa.shape.insert(wa.shape.begin() + 1, curve.begin(), curve.end());
3461 : DEBUGCOUT(gDebugFlag1, " outerCurve=" << curve << "\n")
3462 : }
3463 : }
3464 3899 : }
3465 : // apply custom shapes
3466 6612 : if (myWalkingAreaCustomShapes.size() > 0) {
3467 72 : for (auto wacs : myWalkingAreaCustomShapes) {
3468 : // every edge in wasc.edges must be part of connected
3469 44 : if ((wacs.shape.size() != 0 || wacs.width != NBEdge::UNSPECIFIED_WIDTH) && includes(connected, wacs.edges)) {
3470 5 : if (wacs.shape.size() != 0) {
3471 : wa.shape = wacs.shape;
3472 : }
3473 5 : if (wacs.width != NBEdge::UNSPECIFIED_WIDTH) {
3474 2 : wa.width = wacs.width;
3475 : }
3476 5 : wa.hasCustomShape = true;
3477 : }
3478 : }
3479 : }
3480 : // determine length (average of all possible connections)
3481 : double lengthSum = 0;
3482 : int combinations = 0;
3483 28145 : for (std::vector<Position>::const_iterator it1 = connectedPoints.begin(); it1 != connectedPoints.end(); ++it1) {
3484 101160 : for (std::vector<Position>::const_iterator it2 = connectedPoints.begin(); it2 != connectedPoints.end(); ++it2) {
3485 : const Position& p1 = *it1;
3486 : const Position& p2 = *it2;
3487 : if (p1 != p2) {
3488 57950 : lengthSum += p1.distanceTo2D(p2);
3489 57950 : combinations += 1;
3490 : }
3491 : }
3492 : }
3493 : DEBUGCOUT(gDebugFlag1, " combinations=" << combinations << " connectedPoints=" << connectedPoints << "\n")
3494 6612 : wa.length = POSITION_EPS;
3495 6612 : if (combinations > 0) {
3496 13089 : wa.length = MAX2(POSITION_EPS, lengthSum / combinations);
3497 : }
3498 6612 : myWalkingAreas.push_back(wa);
3499 7894 : }
3500 : // build walkingAreas between split crossings
3501 6500 : std::vector<Crossing*> validCrossings = getCrossings();
3502 8922 : for (std::vector<Crossing*>::iterator it = validCrossings.begin(); it != validCrossings.end(); ++it) {
3503 2422 : Crossing& prev = **it;
3504 2422 : Crossing& next = (it != validCrossings.begin() ? **(it - 1) :** (validCrossings.end() - 1));
3505 : DEBUGCOUT(gDebugFlag1, " checkIntermediate: prev=" << prev.id << " next=" << next.id << " prev.nextWA=" << prev.nextWalkingArea << " next.prevWA=" << next.prevWalkingArea << "\n")
3506 2422 : if (prev.nextWalkingArea == "") {
3507 209 : if (next.prevWalkingArea != "" || &prev == &next) {
3508 17 : WRITE_WARNINGF(TL("Invalid pedestrian topology: crossing '%' across [%] has no target."), prev.id, toString(prev.edges));
3509 5 : prev.valid = false;
3510 5 : continue;
3511 : }
3512 408 : WalkingArea wa(":" + getID() + "_w" + toString(index++), prev.width);
3513 : prev.nextWalkingArea = wa.id;
3514 204 : wa.nextCrossings.push_back(next.id);
3515 : next.prevWalkingArea = wa.id;
3516 : // back of previous crossing
3517 : PositionVector tmp = prev.shape;
3518 204 : tmp.move2side(-prev.width / 2);
3519 204 : wa.shape.push_back(tmp[-1]);
3520 204 : tmp.move2side(prev.width);
3521 204 : wa.shape.push_back(tmp[-1]);
3522 : // front of next crossing
3523 : tmp = next.shape;
3524 204 : tmp.move2side(prev.width / 2);
3525 204 : wa.shape.push_back(tmp[0]);
3526 204 : tmp.move2side(-prev.width);
3527 204 : wa.shape.push_back(tmp[0]);
3528 : wa.refEdges.insert(prev.edges.begin(), prev.edges.end());
3529 : wa.refEdges.insert(next.edges.begin(), next.edges.end());
3530 : // apply custom shapes
3531 204 : if (myWalkingAreaCustomShapes.size() > 0) {
3532 48 : for (auto wacs : myWalkingAreaCustomShapes) {
3533 : // every edge in wacs.edges must be part of crossed
3534 30 : if (wacs.shape.size() != 0 && wacs.edges.size() > 1 && includes(wa.refEdges, wacs.edges)) {
3535 : wa.shape = wacs.shape;
3536 6 : wa.hasCustomShape = true;
3537 : }
3538 : }
3539 : }
3540 : // length (special case)
3541 204 : wa.length = MAX2(POSITION_EPS, prev.shape.back().distanceTo2D(next.shape.front()));
3542 204 : myWalkingAreas.push_back(wa);
3543 : DEBUGCOUT(gDebugFlag1, " build wa=" << wa.id << "\n")
3544 204 : }
3545 : }
3546 6500 : }
3547 :
3548 :
3549 : void
3550 6500 : NBNode::buildCrossingOutlines() {
3551 : #ifdef DEBUG_CROSSING_OUTLINE
3552 : if (myCrossings.size() > 0) {
3553 : std::cerr << "<add>\n";
3554 : }
3555 : #endif
3556 : std::map<std::string, PositionVector> waShapes;
3557 13316 : for (auto wa : myWalkingAreas) {
3558 6816 : waShapes[wa.id] = wa.shape;
3559 6816 : }
3560 8917 : for (auto c : getCrossings()) {
3561 2417 : PositionVector wa1 = waShapes[c->prevWalkingArea];
3562 2417 : PositionVector wa2 = waShapes[c->nextWalkingArea];
3563 2417 : if (wa1.empty() || wa2.empty()) {
3564 : continue;
3565 : }
3566 2416 : wa1.closePolygon();
3567 2416 : wa2.closePolygon();
3568 : PositionVector side1 = c->shape;
3569 2416 : PositionVector side2 = c->shape.reverse();
3570 2416 : side1.move2side(c->width / 2);
3571 2416 : side2.move2side(c->width / 2);
3572 : PositionVector side1default = side1;
3573 : PositionVector side2default = side2;
3574 2416 : side1.extrapolate(POSITION_EPS);
3575 2416 : side2.extrapolate(c->width);
3576 4832 : side1 = cutAtShapes(side1, wa1, wa2, side1default);
3577 4832 : side2 = cutAtShapes(side2, wa1, wa2, side2default);
3578 : PositionVector side1ex = side1;
3579 : PositionVector side2ex = side2;
3580 2416 : side1ex.extrapolate(POSITION_EPS);
3581 2416 : side2ex.extrapolate(side2 == side2default ? c->width / 2 : POSITION_EPS);
3582 2416 : PositionVector side3 = cutAtShapes(wa2, side1ex, side2ex, PositionVector());
3583 4832 : PositionVector side4 = cutAtShapes(wa1, side1ex, side2ex, PositionVector());
3584 : c->outlineShape = side1;
3585 2416 : c->outlineShape.append(side3, POSITION_EPS);
3586 2416 : c->outlineShape.append(side2, POSITION_EPS);
3587 2416 : c->outlineShape.append(side4, POSITION_EPS);
3588 2416 : c->outlineShape.removeDoublePoints();
3589 : // DEBUG
3590 : #ifdef DEBUG_CROSSING_OUTLINE
3591 : std::cout << " side1=" << side1 << "\n side2=" << side2 << "\n side3=" << side3 << "\n side4=" << side4 << "\n";
3592 : std::cerr << "<poly id=\"" << c->id << "\" shape=\"" << c->outlineShape << "\" color=\"blue\" lineWidth=\"0.2\" layer=\"100\"/>\n";
3593 : #endif
3594 2417 : }
3595 : #ifdef DEBUG_CROSSING_OUTLINE
3596 : if (myCrossings.size() > 0) {
3597 : std::cerr << "</add>\n";
3598 : }
3599 : #endif
3600 6500 : }
3601 :
3602 :
3603 : PositionVector
3604 9664 : NBNode::cutAtShapes(const PositionVector& cut, const PositionVector& border1, const PositionVector& border2, const PositionVector& def) {
3605 9664 : std::vector<double> is1 = cut.intersectsAtLengths2D(border1);
3606 9664 : std::vector<double> is2 = cut.intersectsAtLengths2D(border2);
3607 : #ifdef DEBUG_CROSSING_OUTLINE
3608 : std::cout << "is1=" << is1 << " is2=" << is2 << " cut=" << cut << " border1=" << border1 << " border2=" << border2 << "\n";
3609 : #endif
3610 9664 : if (is1.size() == 0 && border1.size() == 2) {
3611 1983 : const double d1 = cut.distance2D(border1.front());
3612 1983 : const double d2 = cut.distance2D(border1.back());
3613 1983 : Position closer = d1 < d2 ? border1.front() : border1.back();
3614 1983 : double nOp = cut.nearest_offset_to_point2D(closer, false);
3615 : #ifdef DEBUG_CROSSING_OUTLINE
3616 : std::cout << " closer=" << closer << " nOp=" << nOp << "\n";
3617 : #endif
3618 1983 : if (nOp <= 2 * POSITION_EPS && cut.back().distanceTo2D(closer) <= 2 * POSITION_EPS) {
3619 454 : is1.push_back(cut.length2D());
3620 : } else {
3621 1529 : is1.push_back(nOp);
3622 : }
3623 : }
3624 9664 : if (is2.size() == 0 && border2.size() == 2) {
3625 1295 : const double d1 = cut.distance2D(border2.front());
3626 1295 : const double d2 = cut.distance2D(border2.back());
3627 1295 : Position closer = d1 < d2 ? border2.front() : border2.back();
3628 1295 : double nOp = cut.nearest_offset_to_point2D(closer, false);
3629 1295 : if (nOp <= 2 * POSITION_EPS && cut.back().distanceTo2D(closer) <= 2 * POSITION_EPS) {
3630 16 : is2.push_back(cut.length2D());
3631 : } else {
3632 1279 : is2.push_back(nOp);
3633 : }
3634 : }
3635 9664 : if (is1.size() > 0 && is2.size() > 0) {
3636 : double of1 = VectorHelper<double>::maxValue(is1);
3637 : double of2 = VectorHelper<double>::minValue(is2);
3638 : #ifdef DEBUG_CROSSING_OUTLINE
3639 : std::cout << " of1=" << of1 << " of2=" << of2 << "\n";
3640 : #endif
3641 6984 : if (of1 > of2) {
3642 : of1 = VectorHelper<double>::maxValue(is2);
3643 : of2 = VectorHelper<double>::minValue(is1);
3644 : #ifdef DEBUG_CROSSING_OUTLINE
3645 : std::cout << " of1=" << of1 << " of2=" << of2 << "\n";
3646 : #endif
3647 : }
3648 6984 : if (of1 > of2) {
3649 : of2 = VectorHelper<double>::maxValue(is1);
3650 : of1 = VectorHelper<double>::minValue(is2);
3651 : #ifdef DEBUG_CROSSING_OUTLINE
3652 : std::cout << " of1=" << of1 << " of2=" << of2 << "\n";
3653 : #endif
3654 : }
3655 : assert(of1 <= of2);
3656 6984 : return cut.getSubpart(of1, of2);
3657 : } else {
3658 : return def;
3659 : }
3660 : }
3661 :
3662 :
3663 : bool
3664 62 : NBNode::includes(const std::set<const NBEdge*, ComparatorIdLess>& super,
3665 : const std::set<const NBEdge*, ComparatorIdLess>& sub) {
3666 : // for some reason std::include does not work reliably
3667 85 : for (const NBEdge* e : sub) {
3668 148 : if (super.count(const_cast<NBEdge*>(e)) == 0) {
3669 : return false;
3670 : }
3671 : }
3672 : return true;
3673 : }
3674 :
3675 :
3676 : bool
3677 10917 : NBNode::crossingBetween(const NBEdge* e1, const NBEdge* e2) const {
3678 10917 : if (e1 == e2) {
3679 : return false;
3680 : }
3681 10867 : if (myAllEdges.size() > 3) {
3682 : // pedestrian scramble
3683 : return false;
3684 : }
3685 3901 : for (auto c : getCrossings()) {
3686 : const EdgeVector& edges = c->edges;
3687 103 : EdgeVector::const_iterator it1 = std::find(edges.begin(), edges.end(), e1);
3688 103 : EdgeVector::const_iterator it2 = std::find(edges.begin(), edges.end(), e2);
3689 103 : if (it1 != edges.end() && it2 != edges.end()) {
3690 4 : return true;
3691 : }
3692 : }
3693 3798 : return false;
3694 : }
3695 :
3696 :
3697 : bool
3698 9765 : NBNode::alreadyConnectedPaths(const NBEdge* e1, const NBEdge* e2, double dist) const {
3699 9765 : if (e1 == e2) {
3700 : return false;
3701 : }
3702 9715 : if (e1->getPermissions() != SVC_PEDESTRIAN
3703 9715 : || e2->getPermissions() != SVC_PEDESTRIAN) {
3704 : // no paths
3705 6058 : return false;
3706 : }
3707 4833 : if (e1->getFinalLength() > dist &&
3708 1176 : e2->getFinalLength() > dist) {
3709 : // too long
3710 : return false;
3711 : }
3712 3034 : NBNode* other1 = e1->getFromNode() == this ? e1->getToNode() : e1->getFromNode();
3713 3034 : NBNode* other2 = e2->getFromNode() == this ? e2->getToNode() : e2->getFromNode();
3714 3034 : return other1 == other2;
3715 : }
3716 :
3717 :
3718 : bool
3719 10790 : NBNode::crossesFringe(const NBEdge* e1, const NBEdge* e2) const {
3720 10790 : return myFringeType != FringeType::DEFAULT
3721 4 : && myIncomingEdges.size() == 1 && myOutgoingEdges.size() == 1
3722 10794 : && (e1->isTurningDirectionAt(e2) || e2->isTurningDirectionAt(e1));
3723 : }
3724 :
3725 :
3726 : EdgeVector
3727 0 : NBNode::edgesBetween(const NBEdge* e1, const NBEdge* e2) const {
3728 : EdgeVector result;
3729 0 : EdgeVector::const_iterator it = std::find(myAllEdges.begin(), myAllEdges.end(), e1);
3730 : assert(it != myAllEdges.end());
3731 0 : NBContHelper::nextCW(myAllEdges, it);
3732 0 : EdgeVector::const_iterator it_end = std::find(myAllEdges.begin(), myAllEdges.end(), e2);
3733 : assert(it_end != myAllEdges.end());
3734 0 : while (it != it_end) {
3735 0 : result.push_back(*it);
3736 0 : NBContHelper::nextCW(myAllEdges, it);
3737 : }
3738 0 : return result;
3739 : }
3740 :
3741 :
3742 : void
3743 11 : NBNode::addWalkingAreaShape(EdgeVector edges, const PositionVector& shape, double width) {
3744 11 : WalkingAreaCustomShape wacs;
3745 : wacs.edges.insert(edges.begin(), edges.end());
3746 : wacs.shape = shape;
3747 11 : wacs.width = width;
3748 11 : myWalkingAreaCustomShapes.push_back(wacs);
3749 11 : }
3750 :
3751 :
3752 : bool
3753 378883 : NBNode::geometryLike() const {
3754 378883 : return geometryLike(myIncomingEdges, myOutgoingEdges);
3755 : }
3756 :
3757 : bool
3758 425921 : NBNode::geometryLike(const EdgeVector& incoming, const EdgeVector& outgoing) const {
3759 425921 : if (incoming.size() == 1 && outgoing.size() == 1) {
3760 : return true;
3761 : }
3762 342238 : if (incoming.size() == 2 && outgoing.size() == 2) {
3763 : // check whether the incoming and outgoing edges are pairwise (near) parallel and
3764 : // thus the only cross-connections could be turn-arounds
3765 71963 : NBEdge* in0 = incoming[0];
3766 71963 : NBEdge* in1 = incoming[1];
3767 71963 : NBEdge* out0 = outgoing[0];
3768 71963 : NBEdge* out1 = outgoing[1];
3769 126771 : if ((in0->isTurningDirectionAt(out0) || in0->isTurningDirectionAt(out1))
3770 74388 : && (in1->isTurningDirectionAt(out0) || in1->isTurningDirectionAt(out1))) {
3771 15437 : return true;
3772 : }
3773 56526 : if (in0->getGeometry() == in1->getGeometry() && out0->getGeometry() == out1->getGeometry()) {
3774 : // overlapping edges
3775 : return true;
3776 : }
3777 112488 : for (EdgeVector::const_iterator it = incoming.begin(); it != incoming.end(); ++it) {
3778 90016 : NBEdge* inEdge = *it;
3779 90016 : double angle0 = fabs(NBHelpers::relAngle(inEdge->getAngleAtNode(this), out0->getAngleAtNode(this)));
3780 90016 : double angle1 = fabs(NBHelpers::relAngle(inEdge->getAngleAtNode(this), out1->getAngleAtNode(this)));
3781 90016 : if (MAX2(angle0, angle1) <= 160) {
3782 : // neither of the outgoing edges is parallel to inEdge
3783 : return false;
3784 : }
3785 : }
3786 : return true;
3787 : }
3788 : return false;
3789 : }
3790 :
3791 : void
3792 470 : NBNode::setRoundabout() {
3793 470 : if (myType == SumoXMLNodeType::RIGHT_BEFORE_LEFT || myType == SumoXMLNodeType::LEFT_BEFORE_RIGHT) {
3794 6 : myType = SumoXMLNodeType::PRIORITY;
3795 : }
3796 470 : }
3797 :
3798 : bool
3799 0 : NBNode::isRoundabout() const {
3800 0 : for (NBEdge* out : myOutgoingEdges) {
3801 0 : if (out->getJunctionPriority(this) == NBEdge::JunctionPriority::ROUNDABOUT) {
3802 : return true;
3803 : }
3804 : }
3805 : return false;
3806 : }
3807 :
3808 : NBNode::Crossing*
3809 3122 : NBNode::addCrossing(EdgeVector edges, double width, bool priority, int tlIndex, int tlIndex2,
3810 : const PositionVector& customShape, bool fromSumoNet, const Parameterised* params) {
3811 3122 : Crossing* c = new Crossing(this, edges, width, priority, tlIndex, tlIndex2, customShape);
3812 3122 : if (params != nullptr) {
3813 135 : c->updateParameters(params->getParametersMap());
3814 : }
3815 3122 : myCrossings.push_back(std::unique_ptr<Crossing>(c));
3816 3122 : if (fromSumoNet) {
3817 135 : myCrossingsLoadedFromSumoNet += 1;
3818 : }
3819 3122 : return c;
3820 : }
3821 :
3822 :
3823 : void
3824 3 : NBNode::removeCrossing(const EdgeVector& edges) {
3825 3 : EdgeSet edgeSet(edges.begin(), edges.end());
3826 18 : for (auto it = myCrossings.begin(); it != myCrossings.end();) {
3827 15 : EdgeSet edgeSet2((*it)->edges.begin(), (*it)->edges.end());
3828 15 : if (edgeSet == edgeSet2) {
3829 3 : it = myCrossings.erase(it);
3830 : } else {
3831 : ++it;
3832 : }
3833 : }
3834 3 : }
3835 :
3836 :
3837 : NBNode::Crossing*
3838 2343 : NBNode::getCrossing(const std::string& id) const {
3839 4983 : for (auto& c : myCrossings) {
3840 4983 : if (c->id == id) {
3841 2343 : return c.get();
3842 : }
3843 : }
3844 0 : throw ProcessError(TLF("Request for unknown crossing '%'", id));
3845 : }
3846 :
3847 :
3848 : NBNode::Crossing*
3849 3 : NBNode::getCrossing(const EdgeVector& edges, bool hardFail) const {
3850 3 : const EdgeSet edgeSet(edges.begin(), edges.end());
3851 13 : for (auto& crossing : myCrossings) {
3852 13 : const EdgeSet edgeSet2(crossing->edges.begin(), crossing->edges.end());
3853 13 : if (edgeSet == edgeSet2) {
3854 : return crossing.get();
3855 : }
3856 : }
3857 0 : if (!hardFail) {
3858 : return nullptr;
3859 : }
3860 0 : throw ProcessError(TL("Request for unknown crossing for the given Edges"));
3861 : }
3862 :
3863 :
3864 : NBNode::WalkingArea&
3865 0 : NBNode::getWalkingArea(const std::string& id) {
3866 0 : for (auto& walkingArea : myWalkingAreas) {
3867 0 : if (walkingArea.id == id) {
3868 : return walkingArea;
3869 : }
3870 : }
3871 : // not found, maybe we need to rebuild
3872 0 : updateSurroundingGeometry();
3873 0 : sortEdges(true);
3874 0 : buildCrossingsAndWalkingAreas();
3875 0 : for (auto& walkingArea : myWalkingAreas) {
3876 0 : if (walkingArea.id == id) {
3877 : return walkingArea;
3878 : }
3879 : }
3880 0 : if (myWalkingAreas.size() > 0) {
3881 : // don't crash
3882 0 : WRITE_WARNINGF("Could not retrieve walkingarea '%' (edge ordering changed after recompute).", id);
3883 0 : return myWalkingAreas.front();
3884 : }
3885 0 : throw ProcessError(TLF("Request for unknown walkingarea '%'.", id));
3886 : }
3887 :
3888 :
3889 : bool
3890 6085 : NBNode::setCrossingTLIndices(const std::string& tlID, int startIndex) {
3891 : bool usedCustom = false;
3892 7687 : for (auto c : getCrossings()) {
3893 1602 : c->tlLinkIndex = startIndex++;
3894 1602 : c->tlID = tlID;
3895 1602 : if (c->customTLIndex != -1) {
3896 278 : usedCustom |= (c->tlLinkIndex != c->customTLIndex);
3897 278 : c->tlLinkIndex = c->customTLIndex;
3898 : }
3899 1602 : c->tlLinkIndex2 = c->customTLIndex2;
3900 : }
3901 6085 : return usedCustom;
3902 : }
3903 :
3904 :
3905 : int
3906 61776 : NBNode::numNormalConnections() const {
3907 61776 : if (myRequest == nullptr) {
3908 : // could be an uncontrolled type
3909 : int result = 0;
3910 546 : for (const NBEdge* const edge : myIncomingEdges) {
3911 256 : result += (int)edge->getConnections().size();
3912 : }
3913 290 : return result;
3914 : } else {
3915 61486 : return myRequest->getSizes().second;
3916 : }
3917 : }
3918 :
3919 :
3920 : int
3921 278531 : NBNode::getConnectionIndex(const NBEdge* from, const NBEdge::Connection& con) const {
3922 : int result = 0;
3923 568243 : for (const NBEdge* const e : myIncomingEdges) {
3924 1904119 : for (const NBEdge::Connection& cand : e->getConnections()) {
3925 1614407 : if (e == from && cand.fromLane == con.fromLane && cand.toLane == con.toLane && cand.toEdge == con.toEdge) {
3926 : return result;
3927 : }
3928 1335876 : result++;
3929 : }
3930 : }
3931 : return -1;
3932 : }
3933 :
3934 :
3935 : Position
3936 126654 : NBNode::getCenter() const {
3937 : /* Conceptually, the center point would be identical with myPosition.
3938 : * However, if the shape is influenced by custom geometry endpoints of the adjoining edges,
3939 : * myPosition may fall outside the shape. In this case it is better to use
3940 : * the center of the shape
3941 : **/
3942 : PositionVector tmp = myPoly;
3943 126654 : tmp.closePolygon();
3944 : //std::cout << getID() << " around=" << tmp.around(myPosition) << " dist=" << tmp.distance2D(myPosition) << "\n";
3945 126654 : if (tmp.size() < 3 || tmp.around(myPosition) || tmp.distance2D(myPosition) < POSITION_EPS) {
3946 121968 : return myPosition;
3947 : }
3948 4686 : return myPoly.getPolygonCenter();
3949 126654 : }
3950 :
3951 :
3952 : EdgeVector
3953 12316 : NBNode::getEdgesSortedByAngleAtNodeCenter() const {
3954 12316 : EdgeVector result = myAllEdges;
3955 : #ifdef DEBUG_PED_STRUCTURES
3956 : if (gDebugFlag1) {
3957 : std::cout << " angles:\n";
3958 : for (EdgeVector::const_iterator it = result.begin(); it != result.end(); ++it) {
3959 : std::cout << " edge=" << (*it)->getID() << " edgeAngle=" << (*it)->getAngleAtNode(this) << " angleToShape=" << (*it)->getAngleAtNodeToCenter(this) << "\n";
3960 : }
3961 : std::cout << " allEdges before: " << toString(result) << "\n";
3962 : }
3963 : #endif
3964 12316 : sort(result.begin(), result.end(), NBContHelper::edge_by_angle_to_nodeShapeCentroid_sorter(this));
3965 : // let the first edge in myAllEdges remain the first
3966 : DEBUGCOUT(gDebugFlag1, " allEdges sorted: " << toString(result) << "\n")
3967 12316 : rotate(result.begin(), std::find(result.begin(), result.end(), *myAllEdges.begin()), result.end());
3968 : DEBUGCOUT(gDebugFlag1, " allEdges rotated: " << toString(result) << "\n")
3969 12316 : return result;
3970 : }
3971 :
3972 :
3973 : void
3974 51152 : NBNode::avoidOverlap() {
3975 : // simple case: edges with LaneSpreadFunction::CENTER and a (possible) turndirection at the same node
3976 135510 : for (EdgeVector::iterator it = myIncomingEdges.begin(); it != myIncomingEdges.end(); it++) {
3977 84358 : NBEdge* edge = *it;
3978 84358 : NBEdge* turnDest = edge->getTurnDestination(true);
3979 84358 : if (turnDest != nullptr) {
3980 51562 : edge->shiftPositionAtNode(this, turnDest);
3981 51562 : turnDest->shiftPositionAtNode(this, edge);
3982 : }
3983 : }
3984 : // @todo: edges in the same direction with sharp angles starting/ending at the same position
3985 51152 : }
3986 :
3987 :
3988 : bool
3989 372316 : NBNode::isTrafficLight(SumoXMLNodeType type) {
3990 : return type == SumoXMLNodeType::TRAFFIC_LIGHT
3991 : || type == SumoXMLNodeType::TRAFFIC_LIGHT_NOJUNCTION
3992 372316 : || type == SumoXMLNodeType::TRAFFIC_LIGHT_RIGHT_ON_RED;
3993 : }
3994 :
3995 :
3996 : bool
3997 1582915 : NBNode::rightOnRedConflict(int index, int foeIndex) const {
3998 1852572 : for (NBTrafficLightDefinition* def : myTrafficLights) {
3999 269687 : if (def->rightOnRedConflict(index, foeIndex)) {
4000 : return true;
4001 : }
4002 : }
4003 : return false;
4004 : }
4005 :
4006 :
4007 : void
4008 246918 : NBNode::sortEdges(bool useNodeShape) {
4009 246918 : if (myAllEdges.size() == 0) {
4010 2794 : return;
4011 : }
4012 244124 : EdgeVector allEdgesOriginal = myAllEdges;
4013 : EdgeVector& allEdges = myAllEdges;
4014 : EdgeVector& incoming = myIncomingEdges;
4015 : EdgeVector& outgoing = myOutgoingEdges;
4016 :
4017 : // sort the edges by angle (this is the canonical sorting)
4018 244124 : std::sort(allEdges.begin(), allEdges.end(), NBNodesEdgesSorter::edge_by_junction_angle_sorter(this));
4019 244124 : std::sort(incoming.begin(), incoming.end(), NBNodesEdgesSorter::edge_by_junction_angle_sorter(this));
4020 244124 : std::sort(outgoing.begin(), outgoing.end(), NBNodesEdgesSorter::edge_by_junction_angle_sorter(this));
4021 : std::vector<NBEdge*>::iterator j;
4022 847023 : for (j = allEdges.begin(); j != allEdges.end() - 1 && j != allEdges.end(); ++j) {
4023 602899 : NBNodesEdgesSorter::swapWhenReversed(this, j, j + 1);
4024 : }
4025 244124 : if (allEdges.size() > 1 && j != allEdges.end()) {
4026 212630 : NBNodesEdgesSorter::swapWhenReversed(this, allEdges.end() - 1, allEdges.begin());
4027 : }
4028 :
4029 : // sort again using additional geometry information
4030 244124 : NBEdge* firstOfAll = allEdges.front();
4031 244124 : NBEdge* firstOfIncoming = incoming.size() > 0 ? incoming.front() : 0;
4032 244124 : NBEdge* firstOfOutgoing = outgoing.size() > 0 ? outgoing.front() : 0;
4033 : // sort by the angle between the node shape center and the point where the edge meets the node shape
4034 244124 : std::sort(allEdges.begin(), allEdges.end(), NBContHelper::edge_by_angle_to_nodeShapeCentroid_sorter(this));
4035 244124 : std::sort(incoming.begin(), incoming.end(), NBContHelper::edge_by_angle_to_nodeShapeCentroid_sorter(this));
4036 244124 : std::sort(outgoing.begin(), outgoing.end(), NBContHelper::edge_by_angle_to_nodeShapeCentroid_sorter(this));
4037 : // let the first edge remain the first
4038 244124 : rotate(allEdges.begin(), std::find(allEdges.begin(), allEdges.end(), firstOfAll), allEdges.end());
4039 244124 : if (firstOfIncoming != nullptr) {
4040 227770 : rotate(incoming.begin(), std::find(incoming.begin(), incoming.end(), firstOfIncoming), incoming.end());
4041 : }
4042 244124 : if (firstOfOutgoing != nullptr) {
4043 223154 : rotate(outgoing.begin(), std::find(outgoing.begin(), outgoing.end(), firstOfOutgoing), outgoing.end());
4044 : }
4045 : #ifdef DEBUG_EDGE_SORTING
4046 : if (DEBUGCOND) {
4047 : std::cout << "sortedEdges (useNodeShape=" << useNodeShape << "):\n";
4048 : for (NBEdge* e : allEdges) {
4049 : std::cout << " " << e->getID()
4050 : << " angleToCenter=" << e->getAngleAtNodeToCenter(this)
4051 : << " junctionAngle=" << e->getAngleAtNode(this) << "\n";
4052 : }
4053 : }
4054 : #endif
4055 :
4056 : // fixing some pathological all edges orderings
4057 : // 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'
4058 244124 : if (incoming.size() == outgoing.size() && incoming.front() == allEdges.front()) {
4059 : std::vector<NBEdge*>::const_iterator in, out;
4060 : std::vector<NBEdge*> allTmp;
4061 235638 : for (in = incoming.begin(), out = outgoing.begin(); in != incoming.end(); ++in, ++out) {
4062 184848 : if ((*in)->isTurningDirectionAt(*out)) {
4063 155246 : allTmp.push_back(*in);
4064 155246 : allTmp.push_back(*out);
4065 : } else {
4066 : break;
4067 : }
4068 : }
4069 80392 : if (allTmp.size() == allEdges.size()) {
4070 50790 : allEdges = allTmp;
4071 : }
4072 : }
4073 : // sort the crossings
4074 244124 : std::sort(myCrossings.begin(), myCrossings.end(), NBNodesEdgesSorter::crossing_by_junction_angle_sorter(this, allEdges));
4075 : //if (crossings.size() > 0) {
4076 : // std::cout << " crossings at " << getID() << "\n";
4077 : // for (std::vector<NBNode::Crossing*>::iterator it = crossings.begin(); it != crossings.end(); ++it) {
4078 : // std::cout << " " << toString((*it)->edges) << "\n";
4079 : // }
4080 : //}
4081 :
4082 244124 : if (useNodeShape && myAllEdges != allEdgesOriginal) {
4083 : // sorting order changed after node shape was computed.
4084 423 : computeNodeShape(-1);
4085 3511 : for (NBEdge* e : myAllEdges) {
4086 3088 : e->computeEdgeShape();
4087 : }
4088 : }
4089 : }
4090 :
4091 : std::vector<std::pair<Position, std::string> >
4092 0 : NBNode::getEndPoints() const {
4093 : // using a set would be nicer but we want to have some slack in position identification
4094 : std::vector<std::pair<Position, std::string> >result;
4095 0 : for (NBEdge* e : myAllEdges) {
4096 0 : Position pos = this == e->getFromNode() ? e->getGeometry().front() : e->getGeometry().back();
4097 0 : const std::string origID = e->getParameter(this == e->getFromNode() ? "origFrom" : "origTo");
4098 : bool unique = true;
4099 0 : for (const auto& pair : result) {
4100 0 : if (pos.almostSame(pair.first) || (origID != "" && pair.second == origID)) {
4101 : unique = false;
4102 : break;
4103 : }
4104 : }
4105 0 : if (unique) {
4106 0 : result.push_back(std::make_pair(pos, origID));
4107 : }
4108 : }
4109 0 : return result;
4110 0 : }
4111 :
4112 :
4113 : /****************************************************************************/
|