1 /****************************************************************************/
2 // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo
3 // Copyright (C) 2001-2019 German Aerospace Center (DLR) and others.
4 // This program and the accompanying materials
5 // are made available under the terms of the Eclipse Public License v2.0
6 // which accompanies this distribution, and is available at
7 // http://www.eclipse.org/legal/epl-v20.html
8 // SPDX-License-Identifier: EPL-2.0
9 /****************************************************************************/
10 /// @file NBNodeCont.cpp
11 /// @author Daniel Krajzewicz
12 /// @author Jakob Erdmann
13 /// @author Yun-Pang Floetteroed
14 /// @author Walter Bamberger
15 /// @author Laura Bieker
16 /// @author Michael Behrisch
17 /// @author Sascha Krieg
18 /// @date Tue, 20 Nov 2001
19 /// @version $Id$
20 ///
21 // Container for nodes during the netbuilding process
22 /****************************************************************************/
23
24
25 // ===========================================================================
26 // included modules
27 // ===========================================================================
28 #include <config.h>
29
30 #include <string>
31 #include <map>
32 #include <algorithm>
33 #include <cmath>
34 #include <utils/options/OptionsCont.h>
35 #include <utils/geom/Boundary.h>
36 #include <utils/geom/GeomHelper.h>
37 #include <utils/common/MsgHandler.h>
38 #include <utils/common/UtilExceptions.h>
39 #include <utils/common/StringTokenizer.h>
40 #include <utils/common/StringUtils.h>
41 #include <utils/common/StdDefs.h>
42 #include <utils/common/ToString.h>
43 #include <utils/common/StringUtils.h>
44 #include <utils/common/IDSupplier.h>
45 #include <utils/xml/SUMOXMLDefinitions.h>
46 #include <utils/geom/GeoConvHelper.h>
47 #include <utils/iodevices/OutputDevice.h>
48 #include "NBHelpers.h"
49 #include "NBAlgorithms.h"
50 #include "NBDistrict.h"
51 #include "NBEdgeCont.h"
52 #include "NBTrafficLightLogicCont.h"
53 #include "NBOwnTLDef.h"
54 #include "NBNodeCont.h"
55 #include "NBPTStopCont.h"
56 #include "NBPTLineCont.h"
57 #include "NBParking.h"
58
59 //#define DEBUG_JOINJUNCTIONS
60 #define DEBUGNODEID "C1"
61 //#define DEBUGNODEID "5548037023"
62 #define DEBUGCOND(obj) ((obj != 0 && (obj)->getID() == DEBUGNODEID))
63
64 // ===========================================================================
65 // method definitions
66 // ===========================================================================
NBNodeCont()67 NBNodeCont::NBNodeCont()
68 : myInternalID(1) {
69 }
70
71
~NBNodeCont()72 NBNodeCont::~NBNodeCont() {
73 clear();
74 }
75
76
77 // ----------- Insertion/removal/retrieval of nodes
78 bool
insert(const std::string & id,const Position & position,NBDistrict * district)79 NBNodeCont::insert(const std::string& id, const Position& position,
80 NBDistrict* district) {
81 NodeCont::iterator i = myNodes.find(id);
82 if (i != myNodes.end()) {
83 return false;
84 }
85 NBNode* node = new NBNode(id, position, district);
86 myNodes[id] = node;
87 const float pos[2] = {(float)position.x(), (float)position.y()};
88 myRTree.Insert(pos, pos, node);
89 return true;
90 }
91
92
93 bool
insert(NBNode * node)94 NBNodeCont::insert(NBNode* node) {
95 std::string id = node->getID();
96 NodeCont::iterator i = myNodes.find(id);
97 if (i != myNodes.end()) {
98 return false;
99 }
100 myNodes[id] = node;
101 const float pos[2] = {(float)node->getPosition().x(), (float)node->getPosition().y()};
102 myRTree.Insert(pos, pos, node);
103 return true;
104 }
105
106
107 NBNode*
retrieve(const std::string & id) const108 NBNodeCont::retrieve(const std::string& id) const {
109 NodeCont::const_iterator i = myNodes.find(id);
110 if (i == myNodes.end()) {
111 return nullptr;
112 }
113 return (*i).second;
114 }
115
116
117 NBNode*
retrieve(const Position & position,const double offset) const118 NBNodeCont::retrieve(const Position& position, const double offset) const {
119 const double extOffset = offset + POSITION_EPS;
120 const float cmin[2] = {(float)(position.x() - extOffset), (float)(position.y() - extOffset)};
121 const float cmax[2] = {(float)(position.x() + extOffset), (float)(position.y() + extOffset)};
122 std::set<std::string> into;
123 Named::StoringVisitor sv(into);
124 myRTree.Search(cmin, cmax, sv);
125 for (std::set<std::string>::const_iterator i = into.begin(); i != into.end(); i++) {
126 NBNode* const node = myNodes.find(*i)->second;
127 if (fabs(node->getPosition().x() - position.x()) <= offset
128 &&
129 fabs(node->getPosition().y() - position.y()) <= offset) {
130 return node;
131 }
132 }
133 return nullptr;
134 }
135
136
137 bool
erase(NBNode * node)138 NBNodeCont::erase(NBNode* node) {
139 if (extract(node)) {
140 delete node;
141 return true;
142 } else {
143 return false;
144 }
145 }
146
147
148 bool
extract(NBNode * node,bool remember)149 NBNodeCont::extract(NBNode* node, bool remember) {
150 NodeCont::iterator i = myNodes.find(node->getID());
151 if (i == myNodes.end()) {
152 return false;
153 }
154 myNodes.erase(i);
155 const float pos[2] = {(float)node->getPosition().x(), (float)node->getPosition().y()};
156 myRTree.Remove(pos, pos, node);
157 node->removeTrafficLights();
158 if (remember) {
159 myExtractedNodes[node->getID()] = node;
160 }
161 return true;
162 }
163
164
165 // ----------- Adapting the input
166 void
removeSelfLoops(NBDistrictCont & dc,NBEdgeCont & ec,NBTrafficLightLogicCont & tc)167 NBNodeCont::removeSelfLoops(NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tc) {
168 int no = 0;
169 for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
170 no += (*i).second->removeSelfLoops(dc, ec, tc);
171 }
172 if (no != 0) {
173 WRITE_WARNING(toString(no) + " self-looping edge(s) removed.");
174 }
175 }
176
177
178 void
joinSimilarEdges(NBDistrictCont & dc,NBEdgeCont & ec,NBTrafficLightLogicCont & tlc)179 NBNodeCont::joinSimilarEdges(NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc) {
180 // magic values
181 const double distanceThreshold = 7.; // don't merge edges further apart
182 const double lengthThreshold = 0.10; // don't merge edges with higher relative length-difference
183
184 for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
185 // count the edges to other nodes outgoing from the current node
186 std::map<NBNode*, EdgeVector> connectionCount;
187 const EdgeVector& outgoing = (*i).second->getOutgoingEdges();
188 for (EdgeVector::const_iterator j = outgoing.begin(); j != outgoing.end(); j++) {
189 connectionCount[(*j)->getToNode()].push_back(*j);
190 }
191 // check whether more than a single edge connect another node and join them
192 std::map<NBNode*, EdgeVector>::iterator k;
193 for (k = connectionCount.begin(); k != connectionCount.end(); k++) {
194 // possibly we do not have anything to join...
195 if ((*k).second.size() < 2) {
196 continue;
197 }
198 // for the edges that seem to be a single street,
199 // check whether the geometry is similar
200 const EdgeVector& ev = (*k).second;
201 const NBEdge* const first = ev.front();
202 EdgeVector::const_iterator jci; // join candidate iterator
203 for (jci = ev.begin() + 1; jci != ev.end(); ++jci) {
204 const double relativeLengthDifference = fabs(first->getLoadedLength() - (*jci)->getLoadedLength()) / first->getLoadedLength();
205 if ((!first->isNearEnough2BeJoined2(*jci, distanceThreshold)) ||
206 (relativeLengthDifference > lengthThreshold) ||
207 (fabs(first->getSpeed() - (*jci)->getSpeed()) >= 0.01) || // output accuracy
208 (first->getPermissions() != (*jci)->getPermissions())
209 ) {
210 break;
211 }
212 }
213 // @bug If there are 3 edges of which 2 can be joined, no joining will
214 // take place with the current implementation
215 if (jci == ev.end()) {
216 ec.joinSameNodeConnectingEdges(dc, tlc, ev);
217 }
218 }
219 }
220 }
221
222
223 void
removeIsolatedRoads(NBDistrictCont & dc,NBEdgeCont & ec)224 NBNodeCont::removeIsolatedRoads(NBDistrictCont& dc, NBEdgeCont& ec) {
225 // Warn of isolated edges, i.e. a single edge with no connection to another edge
226 const std::vector<std::string>& edgeNames = ec.getAllNames();
227 for (std::vector<std::string>::const_iterator it = edgeNames.begin(); it != edgeNames.end(); ++it) {
228 // Test whether this node starts at a dead end, i.e. it has only one adjacent node
229 // to which an edge exists and from which an edge may come.
230 NBEdge* e = ec.retrieve(*it);
231 if (e == nullptr) {
232 continue;
233 }
234 NBNode* from = e->getFromNode();
235 const EdgeVector& outgoingEdges = from->getOutgoingEdges();
236 if (outgoingEdges.size() != 1) {
237 // At this node, several edges or no edge start; so, this node is no dead end.
238 continue;
239 }
240 const EdgeVector& incomingEdges = from->getIncomingEdges();
241 if (incomingEdges.size() > 1) {
242 // At this node, several edges end; so, this node is no dead end.
243 continue;
244 } else if (incomingEdges.size() == 1) {
245 NBNode* fromNodeOfIncomingEdge = incomingEdges[0]->getFromNode();
246 NBNode* toNodeOfOutgoingEdge = outgoingEdges[0]->getToNode();
247 if (fromNodeOfIncomingEdge != toNodeOfOutgoingEdge) {
248 // At this node, an edge ends which is not the inverse direction of
249 // the starting node.
250 continue;
251 }
252 }
253 // Now we know that the edge e starts a dead end.
254 // Next we test if the dead end is isolated, i.e. does not lead to a junction
255 bool hasJunction = false;
256 EdgeVector road;
257 NBEdge* eOld = nullptr;
258 NBNode* to;
259 NodeSet adjacentNodes;
260 do {
261 road.push_back(e);
262 eOld = e;
263 from = e->getFromNode();
264 to = e->getToNode();
265 const EdgeVector& outgoingEdgesOfToNode = to->getOutgoingEdges();
266 const EdgeVector& incomingEdgesOfToNode = to->getIncomingEdges();
267 adjacentNodes.clear();
268 for (EdgeVector::const_iterator itOfOutgoings = outgoingEdgesOfToNode.begin(); itOfOutgoings != outgoingEdgesOfToNode.end(); ++itOfOutgoings) {
269 if ((*itOfOutgoings)->getToNode() != from // The back path
270 && (*itOfOutgoings)->getToNode() != to // A loop / dummy edge
271 ) {
272 e = *itOfOutgoings; // Probably the next edge
273 }
274 adjacentNodes.insert((*itOfOutgoings)->getToNode());
275 }
276 for (EdgeVector::const_iterator itOfIncomings = incomingEdgesOfToNode.begin(); itOfIncomings != incomingEdgesOfToNode.end(); ++itOfIncomings) {
277 adjacentNodes.insert((*itOfIncomings)->getFromNode());
278 }
279 adjacentNodes.erase(to); // Omit loops
280 if (adjacentNodes.size() > 2) {
281 hasJunction = true;
282 }
283 } while (!hasJunction && eOld != e);
284 if (!hasJunction) {
285 std::string warningString = "Removed a road without junctions: ";
286 for (EdgeVector::iterator roadIt = road.begin(); roadIt != road.end(); ++roadIt) {
287 if (roadIt == road.begin()) {
288 warningString += (*roadIt)->getID();
289 } else {
290 warningString += ", " + (*roadIt)->getID();
291 }
292
293 NBNode* fromNode = (*roadIt)->getFromNode();
294 NBNode* toNode = (*roadIt)->getToNode();
295 ec.erase(dc, *roadIt);
296 if (fromNode->getIncomingEdges().size() == 0 && fromNode->getOutgoingEdges().size() == 0) {
297 // Node is empty; can be removed
298 erase(fromNode);
299 }
300 if (toNode->getIncomingEdges().size() == 0 && toNode->getOutgoingEdges().size() == 0) {
301 // Node is empty; can be removed
302 erase(toNode);
303 }
304 }
305 WRITE_WARNING(warningString);
306 }
307 }
308 }
309
310
311 void
removeComponents(NBDistrictCont & dc,NBEdgeCont & ec,const int numKeep)312 NBNodeCont::removeComponents(NBDistrictCont& dc, NBEdgeCont& ec, const int numKeep) {
313 std::vector<std::set<NBEdge*> > components;
314 // need to use ids here to have the same ordering on all platforms
315 std::set<std::string> edgesLeft;
316 for (std::map<std::string, NBEdge*>::const_iterator edgeIt = ec.begin(); edgeIt != ec.end(); ++edgeIt) {
317 edgesLeft.insert(edgeIt->first);
318 }
319 EdgeVector queue;
320 std::set<NBEdge*> toRemove;
321 while (!edgesLeft.empty()) {
322 queue.push_back(ec.getByID(*edgesLeft.begin()));
323 std::set<NBEdge*> component;
324 while (!queue.empty()) {
325 NBEdge* const e = queue.back();
326 queue.pop_back();
327 component.insert(e);
328 std::vector<EdgeVector> edgeLists;
329 edgeLists.push_back(e->getFromNode()->getOutgoingEdges());
330 edgeLists.push_back(e->getFromNode()->getIncomingEdges());
331 edgeLists.push_back(e->getToNode()->getOutgoingEdges());
332 edgeLists.push_back(e->getToNode()->getIncomingEdges());
333 for (std::vector<EdgeVector>::const_iterator listIt = edgeLists.begin(); listIt != edgeLists.end(); ++listIt) {
334 for (EdgeVector::const_iterator edgeIt = listIt->begin(); edgeIt != listIt->end(); ++edgeIt) {
335 std::set<std::string>::iterator leftIt = edgesLeft.find((*edgeIt)->getID());
336 if (leftIt != edgesLeft.end()) {
337 queue.push_back(*edgeIt);
338 edgesLeft.erase(leftIt);
339 }
340 }
341 }
342 }
343 std::vector<std::set<NBEdge*> >::iterator cIt;
344 for (cIt = components.begin(); cIt != components.end(); ++cIt) {
345 if (cIt->size() < component.size()) {
346 break;
347 }
348 }
349 components.insert(cIt, component);
350 if ((int)components.size() > numKeep) {
351 toRemove.insert(components.back().begin(), components.back().end());
352 components.pop_back();
353 }
354 }
355 for (std::set<NBEdge*>::iterator edgeIt = toRemove.begin(); edgeIt != toRemove.end(); ++edgeIt) {
356 NBNode* const fromNode = (*edgeIt)->getFromNode();
357 NBNode* const toNode = (*edgeIt)->getToNode();
358 ec.erase(dc, *edgeIt);
359 if (fromNode->getIncomingEdges().size() == 0 && fromNode->getOutgoingEdges().size() == 0) {
360 erase(fromNode);
361 }
362 if (toNode->getIncomingEdges().size() == 0 && toNode->getOutgoingEdges().size() == 0) {
363 erase(toNode);
364 }
365 }
366 }
367
368
369 int
removeUnwishedNodes(NBDistrictCont & dc,NBEdgeCont & ec,NBTrafficLightLogicCont & tlc,NBPTStopCont & sc,NBPTLineCont & lc,NBParkingCont & pc,bool removeGeometryNodes)370 NBNodeCont::removeUnwishedNodes(NBDistrictCont& dc, NBEdgeCont& ec,
371 NBTrafficLightLogicCont& tlc, NBPTStopCont& sc, NBPTLineCont& lc,
372 NBParkingCont& pc,
373 bool removeGeometryNodes) {
374 // load edges that shall not be modified
375 std::set<std::string> edges2keep;
376 if (removeGeometryNodes) {
377 const OptionsCont& oc = OptionsCont::getOptions();
378 if (oc.isSet("geometry.remove.keep-edges.input-file")) {
379 NBHelpers::loadEdgesFromFile(oc.getString("geometry.remove.keep-edges.input-file"), edges2keep);
380 }
381 if (oc.isSet("geometry.remove.keep-edges.explicit")) {
382 const std::vector<std::string> edges = oc.getStringVector("geometry.remove.keep-edges.explicit");
383 edges2keep.insert(edges.begin(), edges.end());
384 }
385 sc.addEdges2Keep(oc, edges2keep);
386 lc.addEdges2Keep(oc, edges2keep);
387 pc.addEdges2Keep(oc, edges2keep);
388 }
389 int no = 0;
390 std::vector<NBNode*> toRemove;
391 for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
392 NBNode* current = (*i).second;
393 bool remove = false;
394 std::vector<std::pair<NBEdge*, NBEdge*> > toJoin;
395 // check for completely empty nodes
396 if (current->getOutgoingEdges().size() == 0 && current->getIncomingEdges().size() == 0) {
397 // remove if empty
398 remove = true;
399 }
400 // check for nodes which are only geometry nodes
401 if (removeGeometryNodes && mySplit.count(current) == 0) {
402 if ((current->getOutgoingEdges().size() == 1 && current->getIncomingEdges().size() == 1)
403 ||
404 (current->getOutgoingEdges().size() == 2 && current->getIncomingEdges().size() == 2)) {
405 // ok, one in, one out or two in, two out
406 // -> ask the node whether to join
407 remove = current->checkIsRemovable();
408 // check whether any of the edges must be kept
409 for (EdgeVector::const_iterator it_edge = current->getEdges().begin(); it_edge != current->getEdges().end(); ++it_edge) {
410 if (edges2keep.find((*it_edge)->getID()) != edges2keep.end()) {
411 remove = false;
412 break;
413 }
414 }
415 if (remove) {
416 toJoin = current->getEdgesToJoin();
417 }
418 }
419 }
420 // remove the node and join the geometries when wished
421 if (!remove) {
422 continue;
423 }
424 for (std::vector<std::pair<NBEdge*, NBEdge*> >::iterator j = toJoin.begin(); j != toJoin.end(); j++) {
425 NBEdge* begin = (*j).first;
426 NBEdge* continuation = (*j).second;
427 begin->append(continuation);
428 continuation->getToNode()->replaceIncoming(continuation, begin, 0);
429 tlc.replaceRemoved(continuation, -1, begin, -1);
430 ec.extract(dc, continuation, true);
431 }
432 toRemove.push_back(current);
433 no++;
434 }
435 // erase all
436 for (std::vector<NBNode*>::iterator j = toRemove.begin(); j != toRemove.end(); ++j) {
437 extract(*j, true);
438 }
439 return no;
440 }
441
442
443 void
avoidOverlap()444 NBNodeCont::avoidOverlap() {
445 for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
446 (*i).second->avoidOverlap();
447 }
448 }
449
450 // ----------- (Helper) methods for joining nodes
451 void
generateNodeClusters(double maxDist,NodeClusters & into) const452 NBNodeCont::generateNodeClusters(double maxDist, NodeClusters& into) const {
453 std::set<NBNode*> visited;
454 for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); i++) {
455 std::vector<NodeAndDist> toProc;
456 if (visited.find((*i).second) != visited.end()) {
457 continue;
458 }
459 toProc.push_back(std::make_pair((*i).second, 0));
460 NodeSet c;
461 while (!toProc.empty()) {
462 NodeAndDist nodeAndDist = toProc.back();
463 NBNode* n = nodeAndDist.first;
464 double dist = nodeAndDist.second;
465 toProc.pop_back();
466 if (visited.find(n) != visited.end()) {
467 continue;
468 }
469 visited.insert(n);
470 bool pureRail = true;
471 bool railAndPeds = true;
472 for (NBEdge* e : n->getEdges()) {
473 if ((e->getPermissions() & ~(SVC_RAIL_CLASSES | SVC_PEDESTRIAN)) != 0) {
474 railAndPeds = false;
475 pureRail = false;
476 break;
477 }
478 if ((e->getPermissions() & ~(SVC_RAIL_CLASSES)) != 0) {
479 pureRail = false;
480 }
481 }
482 if (pureRail) {
483 // do not join pure rail nodes
484 continue;
485 }
486 c.insert(n);
487 for (NBEdge* e : n->getEdges()) {
488 NBNode* s = n->hasIncoming(e) ? e->getFromNode() : e->getToNode();
489 const double length = e->getLoadedLength();
490 #ifdef DEBUG_JOINJUNCTIONS
491 if (DEBUGCOND(s)) {
492 std::cout << "generateNodeClusters: consider s=" << s->getID()
493 << " clusterNode=" << n->getID() << " edge=" << e->getID() << " length=" << length << " with cluster " << joinNamedToString(c, ' ') << "\n";
494 }
495 #endif
496 if (railAndPeds && n->getType() != NODETYPE_RAIL_CROSSING) {
497 bool railAndPeds2 = true;
498 for (NBEdge* e : n->getEdges()) {
499 if ((e->getPermissions() & ~(SVC_RAIL_CLASSES | SVC_PEDESTRIAN)) != 0) {
500 railAndPeds2 = false;
501 break;
502 }
503 }
504 if (railAndPeds2 && s->getType() != NODETYPE_RAIL_CROSSING) {
505 // do not join rail/ped nodes unless at a rail crossing
506 // (neither nodes nor the traffic lights)
507 continue;
508 }
509 }
510 const bool bothCrossing = n->getType() == NODETYPE_RAIL_CROSSING && s->getType() == NODETYPE_RAIL_CROSSING;
511 const bool joinPedCrossings = bothCrossing && e->getPermissions() == SVC_PEDESTRIAN;
512 if ( // never join pedestrian stuff (unless at a rail crossing
513 !joinPedCrossings && (
514 e->getPermissions() == SVC_PEDESTRIAN
515 // only join edges for regular passenger traffic or edges that are extremely short
516 || (length > 3 * POSITION_EPS
517 && (e->getPermissions() & (SVC_PASSENGER | SVC_TRAM)) == 0
518 && n->getPosition().distanceTo2D(s->getPosition()) > SUMO_const_laneWidth))) {
519 continue;
520 }
521 // never join rail_crossings with other node types unless the crossing is only for tram
522 if ((n->getType() == NODETYPE_RAIL_CROSSING && s->getType() != NODETYPE_RAIL_CROSSING)
523 || (n->getType() != NODETYPE_RAIL_CROSSING && s->getType() == NODETYPE_RAIL_CROSSING)) {
524 const SVCPermissions railNoTram = (SVC_RAIL_CLASSES & ~SVC_TRAM);
525 bool foundRail = false;
526 NBNode* crossingNode = n->getType() == NODETYPE_RAIL_CROSSING ? n : s;
527 for (NBEdge* e2 : crossingNode->getIncomingEdges()) {
528 if ((e2->getPermissions() & railNoTram) != 0) {
529 foundRail = true;
530 break;
531 }
532 }
533 if (foundRail) {
534 continue;
535 }
536 }
537 // never join rail_crossings via a rail edge
538 if (bothCrossing && (e->getPermissions() & ~SVC_RAIL_CLASSES) == 0) {
539 continue;
540 }
541 if (visited.find(s) != visited.end()) {
542 continue;
543 }
544 if (length + dist < maxDist) {
545 if (s->geometryLike()) {
546 toProc.push_back(std::make_pair(s, dist + length));
547 } else {
548 toProc.push_back(std::make_pair(s, 0));
549 }
550 }
551 }
552 }
553 if (c.size() < 2) {
554 continue;
555 }
556 #ifdef DEBUG_JOINJUNCTIONS
557 std::cout << " DEBUG: consider cluster " << joinNamedToString(c, ' ') << "\n";
558 #endif
559 into.push_back(c);
560 }
561 }
562
563
564 void
addJoinExclusion(const std::vector<std::string> & ids,bool check)565 NBNodeCont::addJoinExclusion(const std::vector<std::string>& ids, bool check) {
566 for (std::vector<std::string>::const_iterator it = ids.begin(); it != ids.end(); it++) {
567 // error handling has to take place here since joinExclusions could be
568 // loaded from multiple files / command line
569 if (myJoined.count(*it) > 0) {
570 WRITE_WARNING("Ignoring join exclusion for junction '" + *it + "' since it already occurred in a list of nodes to be joined");
571 } else if (check && retrieve(*it) == nullptr) {
572 WRITE_WARNING("Ignoring join exclusion for unknown junction '" + *it + "'");
573 } else {
574 myJoinExclusions.insert(*it);
575 }
576 }
577 }
578
579
580 void
addCluster2Join(std::set<std::string> cluster,NBNode * node)581 NBNodeCont::addCluster2Join(std::set<std::string> cluster, NBNode* node) {
582 // error handling has to take place here since joins could be loaded from multiple files
583 std::set<std::string> validCluster;
584 for (std::string nodeID : cluster) {
585 if (myJoinExclusions.count(nodeID) > 0) {
586 WRITE_WARNING("Ignoring join-cluster because junction '" + nodeID + "' was already excluded from joining");
587 return;
588 } else if (myJoined.count(nodeID) > 0) {
589 WRITE_WARNING("Ignoring join-cluster because junction '" + nodeID + "' already occurred in another join-cluster");
590 return;
591 } else {
592 NBNode* node = retrieve(nodeID);
593 if (node != nullptr) {
594 validCluster.insert(nodeID);
595 } else {
596 if (StringUtils::startsWith(nodeID, "cluster_")) {
597 // assume join directive came from a pre-processed network. try to use component IDs
598 std::set<std::string> subIDs;
599 for (std::string nID : StringTokenizer(nodeID.substr(8), "_").getVector()) {
600 NBNode* node = retrieve(nID);
601 if (node != nullptr) {
602 validCluster.insert(nID);
603 } else {
604 WRITE_ERROR("Unknown junction '" + nodeID + "' in join-cluster (componentID)");
605 }
606 }
607 } else {
608 WRITE_ERROR("Unknown junction '" + nodeID + "' in join-cluster");
609 }
610 }
611 }
612 }
613 for (std::string nodeID : validCluster) {
614 myJoined.insert(nodeID);
615 }
616 myClusters2Join.push_back(std::make_pair(validCluster, node));
617 }
618
619
620 int
joinLoadedClusters(NBDistrictCont & dc,NBEdgeCont & ec,NBTrafficLightLogicCont & tlc)621 NBNodeCont::joinLoadedClusters(NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc) {
622 int numJoined = 0;
623 for (auto& item : myClusters2Join) {
624 // verify loaded cluster
625 NodeSet cluster;
626 for (std::string nodeID : item.first) {
627 NBNode* node = retrieve(nodeID);
628 if (node == nullptr) {
629 WRITE_ERROR("unknown junction '" + nodeID + "' while joining");
630 } else {
631 cluster.insert(node);
632 }
633 }
634 if (cluster.size() > 1) {
635 joinNodeCluster(cluster, dc, ec, tlc, item.second);
636 numJoined++;
637 myJoinExclusions.insert(item.second->getID());
638 }
639 }
640 myClusters2Join.clear(); // make save for recompute
641 return numJoined;
642 }
643
644
645 int
joinJunctions(double maxDist,NBDistrictCont & dc,NBEdgeCont & ec,NBTrafficLightLogicCont & tlc,NBPTStopCont & sc)646 NBNodeCont::joinJunctions(double maxDist, NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc, NBPTStopCont& sc) {
647 #ifdef DEBUG_JOINJUNCTIONS
648 std::cout << "joinJunctions...\n";
649 #endif
650 NodeClusters cands;
651 NodeClusters clusters;
652 generateNodeClusters(maxDist, cands);
653 for (NodeClusters::iterator i = cands.begin(); i != cands.end(); ++i) {
654 NodeSet cluster = (*i);
655 // remove join exclusions
656 for (NodeSet::iterator j = cluster.begin(); j != cluster.end();) {
657 NodeSet::iterator check = j;
658 ++j;
659 if (myJoinExclusions.count((*check)->getID()) > 0) {
660 cluster.erase(check);
661 }
662 }
663 // remove nodes that can be eliminated by geometry.remove
664 pruneClusterFringe(cluster);
665 // avoid removal of long edges (must have been added via an alternative path).
666 std::set<NBNode*> toRemove;
667 for (NBNode* n : cluster) {
668 for (NBEdge* edge : n->getOutgoingEdges()) {
669 if (cluster.count(edge->getToNode()) != 0 && edge->getLoadedLength() > maxDist /*&& (edge->getPermissions() & SVC_PASSENGER) != 0*/) {
670 #ifdef DEBUG_JOINJUNCTIONS
671 if (DEBUGCOND(n) || DEBUGCOND(edge->getToNode())) {
672 std::cout << "long edge " << edge->getID() << " (" << edge->getLoadedLength() << ", max=" << maxDist << ")\n";
673 }
674 #endif
675 toRemove.insert(n);
676 toRemove.insert(edge->getToNode());
677 }
678 }
679 }
680 for (std::set<NBNode*>::iterator j = toRemove.begin(); j != toRemove.end(); ++j) {
681 cluster.erase(*j);
682 }
683 if (cluster.size() < 2) {
684 continue;
685 }
686 std::string reason;
687 bool feasible = feasibleCluster(cluster, ec, sc, reason);
688 //if (!feasible) std::cout << "\ntry to reduce cluster " << joinNamedToString(cluster, ',') << "\n";
689 if (!feasible) {
690 std::string origCluster = joinNamedToString(cluster, ',');
691 if (reduceToCircle(cluster, 4, cluster)) {
692 pruneClusterFringe(cluster);
693 feasible = feasibleCluster(cluster, ec, sc, reason);
694 if (feasible) {
695 WRITE_WARNING("Reducing junction cluster " + origCluster + " (" + reason + ")");
696 }
697 }
698 }
699 if (!feasible) {
700 std::string origCluster = joinNamedToString(cluster, ',');
701 if (reduceToCircle(cluster, 2, cluster)) {
702 pruneClusterFringe(cluster);
703 feasible = feasibleCluster(cluster, ec, sc, reason);
704 if (feasible) {
705 WRITE_WARNING("Reducing junction cluster " + origCluster + " (" + reason + ")");
706 }
707 }
708 }
709 if (!feasible) {
710 WRITE_WARNING("Not joining junctions " + joinNamedToString(cluster, ',') + " (" + reason + ")");
711 continue;
712 }
713 // compute all connected components of this cluster
714 // (may be more than 1 if intermediate nodes were removed)
715 NodeClusters components;
716 for (NBNode* current : cluster) {
717 // merge all connected components into newComp
718 NodeSet newComp;
719 //std::cout << "checking connectivity for " << current->getID() << "\n";
720 newComp.insert(current);
721 for (NodeClusters::iterator it_comp = components.begin(); it_comp != components.end();) {
722 NodeClusters::iterator check = it_comp;
723 //std::cout << " connected with " << toString(*check) << "?\n";
724 bool connected = false;
725 for (NBNode* k : *check) {
726 if (current->getConnectionTo(k) != nullptr || k->getConnectionTo(current) != nullptr) {
727 //std::cout << "joining with connected component " << toString(*check) << "\n";
728 newComp.insert((*check).begin(), (*check).end());
729 it_comp = components.erase(check);
730 connected = true;
731 break;
732 }
733 }
734 if (!connected) {
735 it_comp++;
736 }
737 }
738 //std::cout << "adding new component " << toString(newComp) << "\n";
739 components.push_back(newComp);
740 }
741 for (NodeClusters::iterator it_comp = components.begin(); it_comp != components.end(); ++it_comp) {
742 if ((*it_comp).size() > 1) {
743 //std::cout << "adding cluster " << toString(*it_comp) << "\n";
744 clusters.push_back(*it_comp);
745 }
746 }
747 }
748 joinNodeClusters(clusters, dc, ec, tlc);
749 return (int)clusters.size();
750 }
751
752
753 void
pruneClusterFringe(NodeSet & cluster) const754 NBNodeCont::pruneClusterFringe(NodeSet& cluster) const {
755 #ifdef DEBUG_JOINJUNCTIONS
756 if (true) {
757 std::cout << "pruning cluster=" << joinNamedToString(cluster, ' ') << "\n";
758 }
759 #endif
760 // iteratively remove the fringe
761 bool pruneFringe = true;
762 // collect nodes that shall be joined due to distance but are not connected
763 // to the cluster for passenger traffic
764 while (pruneFringe) {
765 pruneFringe = false;
766 for (NodeSet::iterator j = cluster.begin(); j != cluster.end();) {
767 NodeSet::iterator check = j;
768 NBNode* n = *check;
769 ++j;
770
771 // compute clusterDist for node (length of shortest edge which connects this node to the cluster)
772 double clusterDist = std::numeric_limits<double>::max();
773 bool touchingCluster = false;
774 for (EdgeVector::const_iterator it_edge = n->getOutgoingEdges().begin(); it_edge != n->getOutgoingEdges().end(); ++it_edge) {
775 NBNode* neighbor = (*it_edge)->getToNode();
776 if (cluster.count(neighbor) != 0) {
777 clusterDist = MIN2(clusterDist, (*it_edge)->getLoadedLength());
778 touchingCluster |= n->getPosition().distanceTo2D(neighbor->getPosition()) <= SUMO_const_laneWidth;
779 }
780 }
781 for (EdgeVector::const_iterator it_edge = n->getIncomingEdges().begin(); it_edge != n->getIncomingEdges().end(); ++it_edge) {
782 NBNode* neighbor = (*it_edge)->getFromNode();
783 if (cluster.count(neighbor) != 0) {
784 clusterDist = MIN2(clusterDist, (*it_edge)->getLoadedLength());
785 touchingCluster |= n->getPosition().distanceTo2D(neighbor->getPosition()) <= SUMO_const_laneWidth;
786 }
787 }
788 // remove geometry-like nodes at fringe of the cluster
789 // (they have 1 neighbor in the cluster and at most 1 neighbor outside the cluster)
790 std::set<NBNode*> outsideNeighbors;
791 std::set<NBNode*> clusterNeighbors;
792 const double pedestrianFringeThreshold = 0.3;
793 for (NBEdge* e : n->getEdges()) {
794 NBNode* neighbor = e->getFromNode() == n ? e->getToNode() : e->getFromNode();
795 if (cluster.count(neighbor) == 0) {
796 if ((e->getPermissions() & SVC_PASSENGER) != 0
797 || isRailway(e->getPermissions()) // join railway crossings
798 || clusterDist <= pedestrianFringeThreshold
799 || touchingCluster) {
800 outsideNeighbors.insert(neighbor);
801 }
802 } else {
803 clusterNeighbors.insert(neighbor);
804 }
805 }
806 #ifdef DEBUG_JOINJUNCTIONS
807 if (DEBUGCOND(n)) std::cout << " check n=" << n->getID()
808 << " clusterDist=" << clusterDist
809 << " cd<th=" << (clusterDist <= pedestrianFringeThreshold)
810 << " touching=" << touchingCluster
811 << " out=" << joinNamedToString(outsideNeighbors, ',')
812 << " in=" << joinNamedToString(clusterNeighbors, ',')
813 << "\n";
814 #endif
815 if (outsideNeighbors.size() <= 1
816 && clusterNeighbors.size() == 1
817 && !n->isTLControlled()) {
818 cluster.erase(check);
819 pruneFringe = true; // other nodes could belong to the fringe now
820 #ifdef DEBUG_JOINJUNCTIONS
821 if (DEBUGCOND(n)) {
822 std::cout << " pruned n=" << n->getID() << "\n";
823 }
824 #endif
825 }
826 }
827 }
828 }
829
830
831 bool
feasibleCluster(const NodeSet & cluster,const NBEdgeCont & ec,const NBPTStopCont & sc,std::string & reason) const832 NBNodeCont::feasibleCluster(const NodeSet& cluster, const NBEdgeCont& ec, const NBPTStopCont& sc, std::string& reason) const {
833 // check for clusters which are to complex and probably won't work very well
834 // we count the incoming edges of the final junction
835 std::map<std::string, double> finalIncomingAngles;
836 std::map<std::string, double> finalOutgoingAngles;
837 for (NodeSet::const_iterator j = cluster.begin(); j != cluster.end(); ++j) {
838 for (EdgeVector::const_iterator it_edge = (*j)->getIncomingEdges().begin(); it_edge != (*j)->getIncomingEdges().end(); ++it_edge) {
839 NBEdge* edge = *it_edge;
840 if (cluster.count(edge->getFromNode()) == 0 && (edge->getPermissions() & SVC_PASSENGER) != 0) {
841 // incoming edge, does not originate in the cluster
842 finalIncomingAngles[edge->getID()] = edge->getAngleAtNode(edge->getToNode());
843 }
844 }
845 for (EdgeVector::const_iterator it_edge = (*j)->getOutgoingEdges().begin(); it_edge != (*j)->getOutgoingEdges().end(); ++it_edge) {
846 NBEdge* edge = *it_edge;
847 if (cluster.count(edge->getToNode()) == 0 && (edge->getPermissions() & SVC_PASSENGER) != 0) {
848 // outgoing edge, does not end in the cluster
849 finalOutgoingAngles[edge->getID()] = edge->getAngleAtNode(edge->getFromNode());
850 }
851 }
852
853 }
854 #ifdef DEBUG_JOINJUNCTIONS
855 for (NBNode* n : cluster) {
856 if (DEBUGCOND(n)) {
857 std::cout << "feasibleCluster c=" << joinNamedToString(cluster, ',')
858 << "\n inAngles=" << joinToString(finalIncomingAngles, ' ', ':')
859 << "\n outAngles=" << joinToString(finalOutgoingAngles, ' ', ':')
860 << "\n";
861 }
862 }
863 #endif
864 if (finalIncomingAngles.size() > 4) {
865 reason = toString(finalIncomingAngles.size()) + " incoming edges";
866 return false;
867 }
868 // check for incoming parallel edges
869 const double PARALLEL_INCOMING_THRESHOLD = 10.0;
870 bool foundParallel = false;
871 for (std::map<std::string, double>::const_iterator j = finalIncomingAngles.begin(); j != finalIncomingAngles.end() && !foundParallel; ++j) {
872 std::map<std::string, double>::const_iterator k = j;
873 for (++k; k != finalIncomingAngles.end() && !foundParallel; ++k) {
874 if (fabs(j->second - k->second) < PARALLEL_INCOMING_THRESHOLD) {
875 reason = "parallel incoming " + j->first + "," + k->first;
876 return false;
877 }
878 }
879 }
880 // check for outgoing parallel edges
881 for (std::map<std::string, double>::const_iterator j = finalOutgoingAngles.begin(); j != finalOutgoingAngles.end() && !foundParallel; ++j) {
882 std::map<std::string, double>::const_iterator k = j;
883 for (++k; k != finalOutgoingAngles.end() && !foundParallel; ++k) {
884 if (fabs(j->second - k->second) < PARALLEL_INCOMING_THRESHOLD) {
885 reason = "parallel outgoing " + j->first + "," + k->first;
886 return false;
887 }
888 }
889 }
890 // check for stop edges within the cluster
891 if (OptionsCont::getOptions().isSet("ptstop-output")) {
892 for (auto it = sc.begin(); it != sc.end(); it++) {
893 NBEdge* edge = ec.retrieve(it->second->getEdgeId());
894 if (edge != nullptr && cluster.count(edge->getFromNode()) != 0 && cluster.count(edge->getToNode()) != 0) {
895 reason = "it contains stop '" + it->first + "'";
896 return false;
897 }
898 }
899 }
900 int numTLS = 0;
901 for (NBNode* n : cluster) {
902 if (n->isTLControlled()) {
903 numTLS++;
904 };
905 }
906 const bool hasTLS = numTLS > 0;
907 // prevent removal of long edges unless there is weak circle or a traffic light
908 if (cluster.size() > 2) {
909 // find the nodes with the biggests physical distance between them
910 double maxDist = -1;
911 NBEdge* maxEdge = nullptr;
912 for (NBNode* n1 : cluster) {
913 for (NBNode* n2 : cluster) {
914 NBEdge* e1 = n1->getConnectionTo(n2);
915 NBEdge* e2 = n2->getConnectionTo(n1);
916 if (e1 != nullptr && e1->getLoadedLength() > maxDist) {
917 maxDist = e1->getLoadedLength();
918 maxEdge = e1;
919 }
920 if (e2 != nullptr && e2->getLoadedLength() > maxDist) {
921 maxDist = e2->getLoadedLength();
922 maxEdge = e2;
923 }
924 }
925 }
926 #ifdef DEBUG_JOINJUNCTIONS
927 for (NBNode* n : cluster) {
928 if (DEBUGCOND(n)) {
929 std::cout << "feasible hasTLS=" << hasTLS << " maxDist=" << maxDist << " maxEdge=" << maxEdge->getID() << "\n";
930 }
931 }
932 #endif
933 if (!hasTLS && maxDist > 5) {
934 // find a weak circle within cluster that does not use maxEdge
935 std::vector<NBNode*> toCheck;
936 std::set<NBNode*> visited;
937 toCheck.push_back(maxEdge->getToNode());
938 bool foundCircle = false;
939 while (!toCheck.empty()) {
940 NBNode* n = toCheck.back();
941 if (n == maxEdge->getFromNode()) {
942 foundCircle = true;
943 break;
944 }
945 toCheck.pop_back();
946 visited.insert(n);
947 for (NBEdge* e : n->getEdges()) {
948 if (e != maxEdge) {
949 NBNode* cand = e->getFromNode() == n ? e->getToNode() : e->getFromNode();
950 if (visited.count(cand) == 0 && cluster.count(cand) != 0) {
951 toCheck.push_back(cand);
952 }
953 }
954 }
955 }
956 if (!foundCircle) {
957 reason = "not compact (maxEdge=" + maxEdge->getID() + " length=" + toString(maxDist) + ")";
958 return false;
959 }
960 }
961 }
962 // prevent joining of simple merging/spreading structures
963 if (!hasTLS && cluster.size() >= 2) {
964 int entryNodes = 0;
965 int exitNodes = 0;
966 int outsideIncoming = 0;
967 int outsideOutgoing = 0;
968 int edgesWithin = 0;
969 for (NBNode* n : cluster) {
970 bool foundOutsideIncoming = false;
971 for (NBEdge* e : n->getIncomingEdges()) {
972 if (cluster.count(e->getFromNode()) == 0) {
973 // edge entering from outside the cluster
974 outsideIncoming++;
975 foundOutsideIncoming = true;
976 } else {
977 edgesWithin++;
978 }
979 }
980 if (foundOutsideIncoming) {
981 entryNodes++;
982 }
983 bool foundOutsideOutgoing = false;
984 for (NBEdge* e : n->getOutgoingEdges()) {
985 if (cluster.count(e->getToNode()) == 0) {
986 // edge leaving cluster
987 outsideOutgoing++;
988 foundOutsideOutgoing = true;
989 }
990 }
991 if (foundOutsideOutgoing) {
992 exitNodes++;
993 }
994 }
995 if (entryNodes < 2) {
996 reason = "only 1 entry node";
997 return false;
998 }
999 if (exitNodes < 2) {
1000 reason = "only 1 exit node";
1001 return false;
1002 }
1003 if (cluster.size() == 2) {
1004 if (edgesWithin == 1 && outsideIncoming < 3 && outsideOutgoing < 3) {
1005 reason = "only 1 edge within and no cross-traffic";
1006 return false;
1007 }
1008 }
1009 }
1010 return true;
1011 }
1012
1013
1014 bool
reduceToCircle(NodeSet & cluster,int circleSize,NodeSet startNodes,std::vector<NBNode * > cands) const1015 NBNodeCont::reduceToCircle(NodeSet& cluster, int circleSize, NodeSet startNodes, std::vector<NBNode*> cands) const {
1016 //std::cout << " cs=" << circleSize << " cands=" << toString(cands) << " startNodes=" << toString(startNodes) << "\n";
1017 assert(circleSize >= 2);
1018 if ((int)cands.size() == circleSize) {
1019 if (cands.back()->getConnectionTo(cands.front()) != nullptr) {
1020 // cluster found
1021 cluster.clear();
1022 cluster.insert(cands.begin(), cands.end());
1023 return true;
1024 } else {
1025 return false;
1026 }
1027 }
1028 if ((int)cluster.size() <= circleSize || startNodes.size() == 0) {
1029 // no reduction possible
1030 return false;
1031 }
1032 if (cands.size() == 0) {
1033 // try to find a circle starting from another start node
1034 NBEdge* e = shortestEdge(cluster, startNodes, cands);
1035 if (e != nullptr) {
1036 cands.push_back(e->getFromNode());
1037 startNodes.erase(e->getFromNode());
1038 if (reduceToCircle(cluster, circleSize, startNodes, cands)) {
1039 return true;
1040 } else {
1041 // try another start node
1042 return reduceToCircle(cluster, circleSize, startNodes);
1043 }
1044 }
1045 } else {
1046 NodeSet singleStart;
1047 singleStart.insert(cands.back());
1048 NBEdge* e = shortestEdge(cluster, singleStart, cands);
1049 if (e != nullptr) {
1050 std::vector<NBNode*> cands2(cands);
1051 cands2.push_back(e->getToNode());
1052 if (reduceToCircle(cluster, circleSize, startNodes, cands2)) {
1053 return true;
1054 }
1055 }
1056 }
1057 return false;
1058 }
1059
1060
1061 NBEdge*
shortestEdge(const NodeSet & cluster,const NodeSet & startNodes,const std::vector<NBNode * > & exclude) const1062 NBNodeCont::shortestEdge(const NodeSet& cluster, const NodeSet& startNodes, const std::vector<NBNode*>& exclude) const {
1063 double minDist = std::numeric_limits<double>::max();
1064 NBEdge* result = nullptr;
1065 for (NBNode* n : startNodes) {
1066 for (NBEdge* e : n->getOutgoingEdges()) {
1067 NBNode* neigh = e->getToNode();
1068 if (cluster.count(neigh) != 0 && std::find(exclude.begin(), exclude.end(), neigh) == exclude.end()) {
1069 const double dist = n->getPosition().distanceTo2D(neigh->getPosition());
1070 //std::cout << " e=" << e->getID() << " dist=" << dist << " minD=" << minDist << "\n";
1071 if (dist < minDist) {
1072 minDist = dist;
1073 result = e;
1074 }
1075 }
1076 }
1077 }
1078 //std::cout << "closestNeighbor startNodes=" << toString(startNodes) << " result=" << Named::getIDSecure(result) << "\n";
1079 return result;
1080 }
1081
1082 void
joinNodeClusters(NodeClusters clusters,NBDistrictCont & dc,NBEdgeCont & ec,NBTrafficLightLogicCont & tlc)1083 NBNodeCont::joinNodeClusters(NodeClusters clusters,
1084 NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc) {
1085 for (NodeSet cluster : clusters) {
1086 joinNodeCluster(cluster, dc, ec, tlc);
1087 }
1088 }
1089
1090
1091 void
joinNodeCluster(NodeSet cluster,NBDistrictCont & dc,NBEdgeCont & ec,NBTrafficLightLogicCont & tlc,NBNode * predefined)1092 NBNodeCont::joinNodeCluster(NodeSet cluster, NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc, NBNode* predefined) {
1093 const bool origNames = OptionsCont::getOptions().getBool("output.original-names");
1094 assert(cluster.size() > 1);
1095 Position pos;
1096 bool setTL;
1097 std::string id = "cluster";
1098 TrafficLightType type;
1099 SumoXMLNodeType nodeType = NODETYPE_UNKNOWN;
1100 analyzeCluster(cluster, id, pos, setTL, type, nodeType);
1101 NBNode* newNode = nullptr;
1102 if (predefined != nullptr) {
1103 newNode = predefined;
1104 } else {
1105 if (!insert(id, pos)) {
1106 // should not fail
1107 WRITE_WARNING("Could not join junctions " + id);
1108 return;;
1109 }
1110 newNode = retrieve(id);
1111 }
1112 std::string tlID = id;
1113 if (predefined != nullptr) {
1114 if (predefined->getType() != NODETYPE_UNKNOWN) {
1115 nodeType = predefined->getType();
1116 }
1117 Position ppos = predefined->getPosition();
1118 if (ppos.x() != Position::INVALID.x()) {
1119 pos.setx(ppos.x());
1120 }
1121 if (ppos.y() != Position::INVALID.y()) {
1122 pos.sety(ppos.y());
1123 }
1124 if (ppos.z() != Position::INVALID.z()) {
1125 pos.setz(ppos.z());
1126 }
1127 }
1128 newNode->reinit(pos, nodeType);
1129 if (setTL && !newNode->isTLControlled()) {
1130 NBTrafficLightDefinition* tlDef = new NBOwnTLDef(tlID, newNode, 0, type);
1131 if (!tlc.insert(tlDef)) {
1132 // actually, nothing should fail here
1133 delete tlDef;
1134 throw ProcessError("Could not allocate tls '" + id + "'.");
1135 }
1136 }
1137 // collect edges
1138 EdgeSet allEdges;
1139 for (NBNode* n : cluster) {
1140 const EdgeVector& edges = n->getEdges();
1141 allEdges.insert(edges.begin(), edges.end());
1142 }
1143 // determine edges with are incoming or fully inside
1144 EdgeSet clusterIncoming;
1145 EdgeSet inside;
1146 for (NBEdge* e : allEdges) {
1147 if (cluster.count(e->getToNode()) > 0) {
1148 if (cluster.count(e->getFromNode()) > 0) {
1149 inside.insert(e);
1150 } else {
1151 clusterIncoming.insert(e);
1152 }
1153 }
1154 }
1155 #ifdef DEBUG_JOINJUNCTIONS
1156 std::cout << "joining cluster " << joinNamedToString(cluster, ' ') << "\n"
1157 << " incoming=" << toString(clusterIncoming) << "\n"
1158 << " inside=" << toString(inside) << "\n";
1159 #endif
1160
1161 // determine possible connectivity from outside edges
1162 std::map<NBEdge*, EdgeSet> reachable;
1163 for (NBEdge* e : clusterIncoming) {
1164 EdgeVector open;
1165 EdgeSet seen;
1166 open.push_back(e);
1167 while (open.size() > 0) {
1168 NBEdge* cur = open.back();
1169 //std::cout << " e=" << e->getID() << " cur=" << cur->getID() << " open=" << toString(open) << "\n";
1170 seen.insert(cur);
1171 open.pop_back();
1172 if (cluster.count(cur->getToNode()) == 0) {
1173 //std::cout << " continue\n";
1174 continue;
1175 }
1176 const auto& cons = cur->getConnections();
1177 if (cons.size() == 0 || ec.hasPostProcessConnection(cur->getID()) || cur->getStep() == NBEdge::INIT) {
1178 // check permissions to determine reachability
1179 for (NBEdge* out : cur->getToNode()->getOutgoingEdges()) {
1180 if (seen.count(out) == 0
1181 && allEdges.count(out) != 0
1182 && (out->getPermissions() & cur->getPermissions() & ~SVC_PEDESTRIAN) != 0) {
1183 open.push_back(out);
1184 }
1185 }
1186 } else {
1187 // check existing connections
1188 for (const auto& con : cons) {
1189 if (con.toEdge != nullptr
1190 && seen.count(con.toEdge) == 0
1191 && allEdges.count(con.toEdge) != 0) {
1192 open.push_back(con.toEdge);
1193 }
1194 }
1195 }
1196 }
1197 seen.erase(e);
1198 for (NBEdge* reached : seen) {
1199 // filter out inside edges from reached
1200 if (inside.count(reached) == 0) {
1201 reachable[e].insert(reached);
1202 }
1203 }
1204 #ifdef DEBUG_JOINJUNCTIONS
1205 std::cout << " reachable e=" << e->getID() << " seen=" << toString(seen) << " reachable=" << toString(reachable[e]) << "\n";
1206 #endif
1207 }
1208
1209 // remap and remove edges which are completely within the new intersection
1210 for (NBEdge* e : inside) {
1211 for (NBEdge* e2 : allEdges) {
1212 if (e != e2) {
1213 e2->replaceInConnections(e, e->getConnections());
1214 }
1215 }
1216 ec.extract(dc, e, true);
1217 allEdges.erase(e);
1218 }
1219
1220 // remap edges which are incoming / outgoing
1221 for (NBEdge* e : allEdges) {
1222 std::vector<NBEdge::Connection> conns = e->getConnections();
1223 const bool outgoing = cluster.count(e->getFromNode()) > 0;
1224 NBNode* from = outgoing ? newNode : e->getFromNode();
1225 NBNode* to = outgoing ? e->getToNode() : newNode;
1226 if (origNames) {
1227 if (outgoing) {
1228 e->setParameter("origFrom", e->getFromNode()->getID());
1229 } else {
1230 e->setParameter("origTo", e->getToNode()->getID());
1231 }
1232 }
1233 e->reinitNodes(from, to);
1234 // re-add connections which previously existed and may still valid.
1235 // connections to removed edges will be ignored
1236 for (std::vector<NBEdge::Connection>::iterator k = conns.begin(); k != conns.end(); ++k) {
1237 e->addLane2LaneConnection((*k).fromLane, (*k).toEdge, (*k).toLane, NBEdge::L2L_USER, false, (*k).mayDefinitelyPass);
1238 if ((*k).fromLane >= 0 && (*k).fromLane < e->getNumLanes() && e->getLaneStruct((*k).fromLane).connectionsDone) {
1239 // @note (see NIImporter_DlrNavteq::ConnectedLanesHandler)
1240 e->declareConnectionsAsLoaded(NBEdge::INIT);
1241 }
1242 }
1243 }
1244 // disable connections that were impossible with the old topology
1245 for (NBEdge* in : newNode->getIncomingEdges()) {
1246 for (NBEdge* out : newNode->getOutgoingEdges()) {
1247 if (reachable[in].count(out) == 0 && !ec.hasPostProcessConnection(in->getID(), out->getID())) {
1248 //std::cout << " removeUnreachable in=" << in->getID() << " out=" << out->getID() << "\n";
1249 in->removeFromConnections(out, -1, -1, true, false, true);
1250 }
1251 }
1252 }
1253
1254 // remove original nodes
1255 registerJoinedCluster(cluster);
1256 for (NBNode* n : cluster) {
1257 erase(n);
1258 }
1259 }
1260
1261
1262 void
registerJoinedCluster(const NodeSet & cluster)1263 NBNodeCont::registerJoinedCluster(const NodeSet& cluster) {
1264 std::set<std::string> ids;
1265 for (NBNode* n : cluster) {
1266 ids.insert(n->getID());
1267 }
1268 myJoinedClusters.push_back(ids);
1269 }
1270
1271
1272 void
analyzeCluster(NodeSet cluster,std::string & id,Position & pos,bool & hasTLS,TrafficLightType & type,SumoXMLNodeType & nodeType)1273 NBNodeCont::analyzeCluster(NodeSet cluster, std::string& id, Position& pos,
1274 bool& hasTLS, TrafficLightType& type, SumoXMLNodeType& nodeType) {
1275 id += "_" + joinNamedToString(cluster, '_');
1276 hasTLS = false;
1277 bool ambiguousType = false;
1278 for (NBNode* j : cluster) {
1279 pos.add(j->getPosition());
1280 // add a traffic light if any of the cluster members was controlled
1281 if (j->isTLControlled()) {
1282 if (!hasTLS) {
1283 // init type
1284 type = (*j->getControllingTLS().begin())->getType();
1285 } else if (type != (*j->getControllingTLS().begin())->getType()) {
1286 ambiguousType = true;
1287 }
1288 hasTLS = true;
1289 }
1290 SumoXMLNodeType otherType = j->getType();
1291 if (nodeType == NODETYPE_UNKNOWN) {
1292 nodeType = otherType;
1293 } else if (nodeType != otherType) {
1294 if (hasTLS) {
1295 nodeType = NODETYPE_TRAFFIC_LIGHT;;
1296 } else {
1297 if ((nodeType != NODETYPE_PRIORITY && (nodeType != NODETYPE_NOJUNCTION || otherType != NODETYPE_PRIORITY))
1298 || (otherType != NODETYPE_NOJUNCTION && otherType != NODETYPE_UNKNOWN && otherType != NODETYPE_PRIORITY)) {
1299 WRITE_WARNING("Ambiguous node type for node cluster '" + id + "' (" + toString(nodeType) + "," + toString(otherType) + ") set to '" + toString(NODETYPE_PRIORITY) + "'");
1300 }
1301 nodeType = NODETYPE_PRIORITY;
1302 }
1303 }
1304 }
1305 pos.mul(1.0 / cluster.size());
1306 if (ambiguousType) {
1307 type = SUMOXMLDefinitions::TrafficLightTypes.get(OptionsCont::getOptions().getString("tls.default-type"));
1308 WRITE_WARNING("Ambiguous traffic light type for node cluster '" + id + "' set to '" + toString(type) + "'");
1309 }
1310 }
1311
1312
1313 // ----------- (Helper) methods for guessing/computing traffic lights
1314 bool
shouldBeTLSControlled(const NodeSet & c,double laneSpeedThreshold) const1315 NBNodeCont::shouldBeTLSControlled(const NodeSet& c, double laneSpeedThreshold) const {
1316 int noIncoming = 0;
1317 int noOutgoing = 0;
1318 bool tooFast = false;
1319 double f = 0;
1320 std::set<NBEdge*> seen;
1321 for (NBNode* j : c) {
1322 const EdgeVector& edges = j->getEdges();
1323 for (EdgeVector::const_iterator k = edges.begin(); k != edges.end(); ++k) {
1324 if (c.find((*k)->getFromNode()) != c.end() && c.find((*k)->getToNode()) != c.end()) {
1325 continue;
1326 }
1327 if (j->hasIncoming(*k)) {
1328 ++noIncoming;
1329 f += (double)(*k)->getNumLanes() * (*k)->getLaneSpeed(0);
1330 } else {
1331 ++noOutgoing;
1332 }
1333 if ((*k)->getLaneSpeed(0) * 3.6 > 79) {
1334 tooFast = true;
1335 }
1336 }
1337 }
1338 return !tooFast && f >= laneSpeedThreshold && c.size() != 0;
1339 }
1340
1341 bool
onlyCrossings(const NodeSet & c) const1342 NBNodeCont::onlyCrossings(const NodeSet& c) const {
1343 // check whether all component nodes are solely pedestrian crossings
1344 // (these work fine without joining)
1345 for (NBNode* node : c) {
1346 EdgeVector nonPedIncoming;
1347 EdgeVector nonPedOutgoing;
1348 for (NBEdge* e : node->getIncomingEdges()) {
1349 if (e->getPermissions() != SVC_PEDESTRIAN) {
1350 nonPedIncoming.push_back(e);
1351 }
1352 }
1353 for (NBEdge* e : node->getOutgoingEdges()) {
1354 if (e->getPermissions() != SVC_PEDESTRIAN) {
1355 nonPedOutgoing.push_back(e);
1356 }
1357 }
1358 if (!node->geometryLike(nonPedIncoming, nonPedOutgoing)) {
1359 //for (NBNode* node : c) {
1360 // if (node->getID() == "2480337678") {
1361 // std::cout << " node=" << node->getID() << " nonPedIncoming=" << toString(nonPedIncoming) << " nonPedOutgoing=" << toString(nonPedOutgoing) << "\n";
1362 // }
1363 //}
1364 return false;
1365 }
1366 }
1367 return true;
1368 }
1369
1370
1371 bool
customTLID(const NodeSet & c) const1372 NBNodeCont::customTLID(const NodeSet& c) const {
1373 for (NBNode* node : c) {
1374 if (node->isTLControlled()) {
1375 const std::string tlID = (*node->getControllingTLS().begin())->getID();
1376 if (tlID != node->getID()
1377 && !StringUtils::startsWith(tlID, "joinedS_")
1378 && !StringUtils::startsWith(tlID, "joinedG_")
1379 && !StringUtils::startsWith(tlID, "GS")) {
1380 return true;
1381 }
1382 }
1383 }
1384 return false;
1385 }
1386
1387
1388 void
guessTLs(OptionsCont & oc,NBTrafficLightLogicCont & tlc)1389 NBNodeCont::guessTLs(OptionsCont& oc, NBTrafficLightLogicCont& tlc) {
1390 // build list of definitely not tls-controlled junctions
1391 const double laneSpeedThreshold = oc.getFloat("tls.guess.threshold");
1392 std::vector<NBNode*> ncontrolled;
1393 if (oc.isSet("tls.unset")) {
1394 std::vector<std::string> notTLControlledNodes = oc.getStringVector("tls.unset");
1395 for (std::vector<std::string>::const_iterator i = notTLControlledNodes.begin(); i != notTLControlledNodes.end(); ++i) {
1396 NBNode* n = NBNodeCont::retrieve(*i);
1397 if (n == nullptr) {
1398 throw ProcessError(" The junction '" + *i + "' to set as not-controlled is not known.");
1399 }
1400 std::set<NBTrafficLightDefinition*> tls = n->getControllingTLS();
1401 for (std::set<NBTrafficLightDefinition*>::const_iterator j = tls.begin(); j != tls.end(); ++j) {
1402 (*j)->removeNode(n);
1403 }
1404 n->removeTrafficLights();
1405 ncontrolled.push_back(n);
1406 }
1407 }
1408
1409 TrafficLightType type = SUMOXMLDefinitions::TrafficLightTypes.get(OptionsCont::getOptions().getString("tls.default-type"));
1410 // loop#1 checking whether the node shall be tls controlled,
1411 // because it is assigned to a district
1412 if (oc.exists("tls.taz-nodes") && oc.getBool("tls.taz-nodes")) {
1413 for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
1414 NBNode* cur = (*i).second;
1415 if (cur->isNearDistrict() && std::find(ncontrolled.begin(), ncontrolled.end(), cur) == ncontrolled.end()) {
1416 setAsTLControlled(cur, tlc, type);
1417 }
1418 }
1419 }
1420
1421 // figure out which nodes mark the locations of TLS signals
1422 // This assumes nodes are already joined
1423 if (oc.exists("tls.guess-signals") && oc.getBool("tls.guess-signals")) {
1424 // prepare candidate edges
1425 const double signalDist = oc.getFloat("tls.guess-signals.dist");
1426 for (std::map<std::string, NBNode*>::const_iterator i = myNodes.begin(); i != myNodes.end(); ++i) {
1427 NBNode* node = (*i).second;
1428 if (node->isTLControlled() && node->geometryLike()) {
1429 std::set<NBEdge*> seen;
1430 std::set<std::pair<NBEdge*, double> > check;
1431 for (NBEdge* edge : node->getOutgoingEdges()) {
1432 double offset = edge->getLength();
1433 edge->setSignalOffset(offset, node);
1434 seen.insert(edge);
1435 check.insert(std::make_pair(edge, offset));
1436 }
1437 // propagate signalOffset until the next real intersection
1438 while (check.size() > 0) {
1439 NBEdge* edge = check.begin()->first;
1440 const double offset = check.begin()->second;
1441 check.erase(check.begin());
1442 NBNode* nextNode = edge->getToNode();
1443 if (nextNode->geometryLike() && !nextNode->isTLControlled()) {
1444 for (NBEdge* edge : nextNode->getOutgoingEdges()) {
1445 if (seen.count(edge) == 0) {
1446 double offset2 = offset + edge->getLength();
1447 edge->setSignalOffset(offset2, node);
1448 seen.insert(edge);
1449 check.insert(std::make_pair(edge, offset2));
1450 }
1451 }
1452 }
1453 }
1454 }
1455 }
1456 // check which nodes should be controlled
1457 for (std::map<std::string, NBNode*>::const_iterator i = myNodes.begin(); i != myNodes.end(); ++i) {
1458 NBNode* node = i->second;
1459 if (find(ncontrolled.begin(), ncontrolled.end(), node) != ncontrolled.end()) {
1460 continue;
1461 }
1462 const EdgeVector& incoming = node->getIncomingEdges();
1463 const EdgeVector& outgoing = node->getOutgoingEdges();
1464 if (!node->isTLControlled() && incoming.size() > 1 && !node->geometryLike()
1465 && !NBNodeTypeComputer::isRailwayNode(node)
1466 && node->getType() != NODETYPE_RAIL_CROSSING) {
1467 std::vector<NBNode*> signals;
1468 bool isTLS = true;
1469 for (EdgeVector::const_iterator it_i = incoming.begin(); it_i != incoming.end(); ++it_i) {
1470 const NBEdge* inEdge = *it_i;
1471 if ((inEdge->getSignalOffset() == NBEdge::UNSPECIFIED_SIGNAL_OFFSET || inEdge->getSignalOffset() > signalDist)
1472 && inEdge->getPermissions() != SVC_TRAM) {
1473 //if (node->getID() == "cluster_2292787672_259083790") std::cout << " noTLS, edge=" << inEdge->getID() << " offset=" << inEdge->getSignalOffset() << "\n";
1474 isTLS = false;
1475 break;
1476 }
1477 NBNode* signal = inEdge->getSignalNode();
1478 if (signal != nullptr) {
1479 //if (true || node->getID() == "cluster_2648427269_3180391961_3180391964_736234762") std::cout << " edge=" << inEdge->getID() << " signalNode=" << signal->getID() << " offset=" << inEdge->getSignalOffset() << "\n";
1480 signals.push_back(signal);
1481 }
1482 }
1483 // outgoing edges may be tagged with pedestrian crossings. These
1484 // should also be merged into the main TLS
1485 for (EdgeVector::const_iterator it_i = outgoing.begin(); it_i != outgoing.end(); ++it_i) {
1486 const NBEdge* outEdge = *it_i;
1487 NBNode* cand = outEdge->getToNode();
1488 if (cand->isTLControlled() && cand->geometryLike() && outEdge->getLength() <= signalDist) {
1489 //if (true || node->getID() == "cluster_2648427269_3180391961_3180391964_736234762") std::cout << " node=" << node->getID() << " outEdge=" << outEdge->getID() << " signalNode=" << cand->getID() << " len=" << outEdge->getLength() << "\n";
1490 signals.push_back(cand);
1491 }
1492 }
1493 if (isTLS) {
1494 for (std::vector<NBNode*>::iterator j = signals.begin(); j != signals.end(); ++j) {
1495 std::set<NBTrafficLightDefinition*> tls = (*j)->getControllingTLS();
1496 (*j)->reinit((*j)->getPosition(), NODETYPE_PRIORITY);
1497 for (std::set<NBTrafficLightDefinition*>::iterator k = tls.begin(); k != tls.end(); ++k) {
1498 tlc.removeFully((*j)->getID());
1499 }
1500 }
1501 //if (true) std::cout << " node=" << node->getID() << " signals=" << toString(signals) << "\n";
1502 NBTrafficLightDefinition* tlDef = new NBOwnTLDef("GS_" + node->getID(), node, 0, type);
1503 // @todo patch endOffset for all incoming lanes according to the signal positions
1504 if (!tlc.insert(tlDef)) {
1505 // actually, nothing should fail here
1506 WRITE_WARNING("Could not build joined tls '" + node->getID() + "'.");
1507 delete tlDef;
1508 return;
1509 }
1510 }
1511 }
1512 }
1513 }
1514
1515 // maybe no tls shall be guessed
1516 if (!oc.getBool("tls.guess")) {
1517 return;
1518 }
1519
1520 // guess joined tls first, if wished
1521 if (oc.getBool("tls.join")) {
1522 // get node clusters
1523 NodeClusters cands;
1524 generateNodeClusters(oc.getFloat("tls.join-dist"), cands);
1525 // check these candidates (clusters) whether they should be controlled by a tls
1526 for (NodeClusters::iterator i = cands.begin(); i != cands.end();) {
1527 NodeSet& c = (*i);
1528 // regard only junctions which are not yet controlled and are not
1529 // forbidden to be controlled
1530 for (NodeSet::iterator j = c.begin(); j != c.end();) {
1531 if ((*j)->isTLControlled() || std::find(ncontrolled.begin(), ncontrolled.end(), *j) != ncontrolled.end()) {
1532 c.erase(j++);
1533 } else {
1534 ++j;
1535 }
1536 }
1537 // check whether the cluster should be controlled
1538 if (!shouldBeTLSControlled(c, laneSpeedThreshold)) {
1539 i = cands.erase(i);
1540 } else {
1541 ++i;
1542 }
1543 }
1544 // cands now only contain sets of junctions that shall be joined into being tls-controlled
1545 int index = 0;
1546 for (NodeClusters::iterator i = cands.begin(); i != cands.end(); ++i) {
1547 std::vector<NBNode*> nodes;
1548 for (NodeSet::iterator j = (*i).begin(); j != (*i).end(); j++) {
1549 nodes.push_back(*j);
1550 }
1551 std::string id = "joinedG_" + toString(index++);
1552 NBTrafficLightDefinition* tlDef = new NBOwnTLDef(id, nodes, 0, type);
1553 if (!tlc.insert(tlDef)) {
1554 // actually, nothing should fail here
1555 WRITE_WARNING("Could not build guessed, joined tls");
1556 delete tlDef;
1557 return;
1558 }
1559 }
1560 }
1561
1562 // guess tls
1563 for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
1564 NBNode* cur = (*i).second;
1565 // do nothing if already is tl-controlled
1566 if (cur->isTLControlled()) {
1567 continue;
1568 }
1569 // do nothing if in the list of explicit non-controlled junctions
1570 if (find(ncontrolled.begin(), ncontrolled.end(), cur) != ncontrolled.end()) {
1571 continue;
1572 }
1573 NodeSet c;
1574 c.insert(cur);
1575 if (!shouldBeTLSControlled(c, laneSpeedThreshold) || cur->getIncomingEdges().size() < 3) {
1576 continue;
1577 }
1578 setAsTLControlled((*i).second, tlc, type);
1579 }
1580 }
1581
1582
1583 void
joinTLS(NBTrafficLightLogicCont & tlc,double maxdist)1584 NBNodeCont::joinTLS(NBTrafficLightLogicCont& tlc, double maxdist) {
1585 NodeClusters cands;
1586 generateNodeClusters(maxdist, cands);
1587 IDSupplier idSupplier("joinedS_");
1588 for (NodeSet& c : cands) {
1589 for (NodeSet::iterator j = c.begin(); j != c.end();) {
1590 if (!(*j)->isTLControlled()) {
1591 c.erase(j++);
1592 } else {
1593 ++j;
1594 }
1595 }
1596 if (c.size() < 2 || onlyCrossings(c) || customTLID(c)) {
1597 continue;
1598 }
1599 // figure out type of the joined TLS
1600 Position dummyPos;
1601 bool dummySetTL;
1602 std::string id = "joined"; // prefix (see #3871)
1603 TrafficLightType type;
1604 SumoXMLNodeType nodeType = NODETYPE_UNKNOWN;
1605 analyzeCluster(c, id, dummyPos, dummySetTL, type, nodeType);
1606 for (NBNode* j : c) {
1607 std::set<NBTrafficLightDefinition*> tls = j->getControllingTLS();
1608 j->removeTrafficLights();
1609 for (std::set<NBTrafficLightDefinition*>::iterator k = tls.begin(); k != tls.end(); ++k) {
1610 tlc.removeFully(j->getID());
1611 }
1612 }
1613 std::vector<NBNode*> nodes;
1614 for (NBNode* j : c) {
1615 nodes.push_back(j);
1616 }
1617 id = idSupplier.getNext();
1618 while (tlc.getPrograms(id).size() > 0) {
1619 id = idSupplier.getNext();
1620 }
1621 NBTrafficLightDefinition* tlDef = new NBOwnTLDef(id, nodes, 0, type);
1622 if (!tlc.insert(tlDef)) {
1623 // actually, nothing should fail here
1624 WRITE_WARNING("Could not build a joined tls.");
1625 delete tlDef;
1626 return;
1627 }
1628 }
1629 }
1630
1631
1632 void
setAsTLControlled(NBNode * node,NBTrafficLightLogicCont & tlc,TrafficLightType type,std::string id)1633 NBNodeCont::setAsTLControlled(NBNode* node, NBTrafficLightLogicCont& tlc,
1634 TrafficLightType type, std::string id) {
1635 if (id == "") {
1636 id = node->getID();
1637 }
1638 NBTrafficLightDefinition* tlDef = new NBOwnTLDef(id, node, 0, type);
1639 if (!tlc.insert(tlDef)) {
1640 // actually, nothing should fail here
1641 WRITE_WARNING("Building a tl-logic for junction '" + id + "' twice is not possible.");
1642 delete tlDef;
1643 return;
1644 }
1645 }
1646
1647
1648 // -----------
1649 void
computeLanes2Lanes()1650 NBNodeCont::computeLanes2Lanes() {
1651 for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
1652 (*i).second->computeLanes2Lanes();
1653 }
1654 }
1655
1656
1657 // computes the "wheel" of incoming and outgoing edges for every node
1658 void
computeLogics(const NBEdgeCont & ec,OptionsCont & oc)1659 NBNodeCont::computeLogics(const NBEdgeCont& ec, OptionsCont& oc) {
1660 for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
1661 (*i).second->computeLogic(ec, oc);
1662 }
1663 }
1664
1665
1666 void
computeLogics2(const NBEdgeCont & ec,OptionsCont & oc)1667 NBNodeCont::computeLogics2(const NBEdgeCont& ec, OptionsCont& oc) {
1668 std::set<NBNode*> roundaboutNodes;
1669 const bool checkLaneFoesAll = oc.getBool("check-lane-foes.all");
1670 const bool checkLaneFoesRoundabout = !checkLaneFoesAll && oc.getBool("check-lane-foes.roundabout");
1671 if (checkLaneFoesRoundabout) {
1672 const std::set<EdgeSet>& roundabouts = ec.getRoundabouts();
1673 for (std::set<EdgeSet>::const_iterator i = roundabouts.begin(); i != roundabouts.end(); ++i) {
1674 for (EdgeSet::const_iterator j = (*i).begin(); j != (*i).end(); ++j) {
1675 roundaboutNodes.insert((*j)->getToNode());
1676 }
1677 }
1678 }
1679 for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
1680 const bool checkLaneFoes = checkLaneFoesAll || (checkLaneFoesRoundabout && roundaboutNodes.count((*i).second) > 0);
1681 (*i).second->computeLogic2(checkLaneFoes);
1682 }
1683 }
1684
1685
1686 void
clear()1687 NBNodeCont::clear() {
1688 for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
1689 delete ((*i).second);
1690 }
1691 myNodes.clear();
1692 for (auto& item : myExtractedNodes) {
1693 delete item.second;
1694 }
1695 myExtractedNodes.clear();
1696 }
1697
1698
1699 std::string
getFreeID()1700 NBNodeCont::getFreeID() {
1701 int counter = 0;
1702 std::string freeID = "SUMOGenerated" + toString<int>(counter);
1703 // While there is a node with id equal to freeID
1704 while (retrieve(freeID) != nullptr) {
1705 // update counter and generate a new freeID
1706 counter++;
1707 freeID = "SUMOGenerated" + toString<int>(counter);
1708 }
1709 return freeID;
1710 }
1711
1712
1713 void
computeNodeShapes(double mismatchThreshold)1714 NBNodeCont::computeNodeShapes(double mismatchThreshold) {
1715 for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
1716 (*i).second->computeNodeShape(mismatchThreshold);
1717 }
1718 }
1719
1720
1721 void
printBuiltNodesStatistics() const1722 NBNodeCont::printBuiltNodesStatistics() const {
1723 int numUnregulatedJunctions = 0;
1724 int numDeadEndJunctions = 0;
1725 int numPriorityJunctions = 0;
1726 int numRightBeforeLeftJunctions = 0;
1727 int numAllWayStopJunctions = 0;
1728 int numZipperJunctions = 0;
1729 int numRailSignals = 0;
1730 for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); i++) {
1731 switch ((*i).second->getType()) {
1732 case NODETYPE_NOJUNCTION:
1733 case NODETYPE_TRAFFIC_LIGHT_NOJUNCTION:
1734 ++numUnregulatedJunctions;
1735 break;
1736 case NODETYPE_DEAD_END:
1737 ++numDeadEndJunctions;
1738 break;
1739 case NODETYPE_PRIORITY:
1740 case NODETYPE_PRIORITY_STOP:
1741 case NODETYPE_TRAFFIC_LIGHT:
1742 case NODETYPE_TRAFFIC_LIGHT_RIGHT_ON_RED:
1743 case NODETYPE_RAIL_CROSSING:
1744 ++numPriorityJunctions;
1745 break;
1746 case NODETYPE_RIGHT_BEFORE_LEFT:
1747 ++numRightBeforeLeftJunctions;
1748 break;
1749 case NODETYPE_ALLWAY_STOP:
1750 ++numAllWayStopJunctions;
1751 break;
1752 case NODETYPE_ZIPPER:
1753 ++numZipperJunctions;
1754 break;
1755 case NODETYPE_DISTRICT:
1756 ++numRightBeforeLeftJunctions;
1757 break;
1758 case NODETYPE_UNKNOWN:
1759 break;
1760 case NODETYPE_RAIL_SIGNAL:
1761 ++numRailSignals;
1762 break;
1763 default:
1764 break;
1765 }
1766 }
1767 WRITE_MESSAGE(" Node type statistics:");
1768 WRITE_MESSAGE(" Unregulated junctions : " + toString(numUnregulatedJunctions));
1769 if (numDeadEndJunctions > 0) {
1770 WRITE_MESSAGE(" Dead-end junctions : " + toString(numDeadEndJunctions));
1771 }
1772 WRITE_MESSAGE(" Priority junctions : " + toString(numPriorityJunctions));
1773 WRITE_MESSAGE(" Right-before-left junctions : " + toString(numRightBeforeLeftJunctions));
1774 if (numAllWayStopJunctions > 0) {
1775 WRITE_MESSAGE(" All-way stop junctions : " + toString(numAllWayStopJunctions));
1776 }
1777 if (numZipperJunctions > 0) {
1778 WRITE_MESSAGE(" Zipper-merge junctions : " + toString(numZipperJunctions));
1779 }
1780 if (numRailSignals > 0) {
1781 WRITE_MESSAGE(" Rail signal junctions : " + toString(numRailSignals));
1782 }
1783 }
1784
1785
1786 std::vector<std::string>
getAllNames() const1787 NBNodeCont::getAllNames() const {
1788 std::vector<std::string> ret;
1789 for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); ++i) {
1790 ret.push_back((*i).first);
1791 }
1792 return ret;
1793 }
1794
1795
1796 void
rename(NBNode * node,const std::string & newID)1797 NBNodeCont::rename(NBNode* node, const std::string& newID) {
1798 if (myNodes.count(newID) != 0) {
1799 throw ProcessError("Attempt to rename node using existing id '" + newID + "'");
1800 }
1801 myNodes.erase(node->getID());
1802 node->setID(newID);
1803 myNodes[newID] = node;
1804 }
1805
1806
1807 void
discardTrafficLights(NBTrafficLightLogicCont & tlc,bool geometryLike,bool guessSignals)1808 NBNodeCont::discardTrafficLights(NBTrafficLightLogicCont& tlc, bool geometryLike, bool guessSignals) {
1809 for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); ++i) {
1810 NBNode* node = i->second;
1811 if (node->isTLControlled() && (!geometryLike || node->geometryLike())) {
1812 // make a copy of tldefs
1813 const std::set<NBTrafficLightDefinition*> tldefs = node->getControllingTLS();
1814 if (geometryLike && (*tldefs.begin())->getNodes().size() > 1) {
1815 // do not remove joined tls when only removing geometry-like tls
1816 continue;
1817 }
1818 if (guessSignals && node->isTLControlled() && node->geometryLike()) {
1819 // record signal location
1820 const EdgeVector& outgoing = node->getOutgoingEdges();
1821 for (EdgeVector::const_iterator it_o = outgoing.begin(); it_o != outgoing.end(); ++it_o) {
1822 (*it_o)->setSignalOffset((*it_o)->getLength(), nullptr);
1823 }
1824 }
1825 for (std::set<NBTrafficLightDefinition*>::const_iterator it = tldefs.begin(); it != tldefs.end(); ++it) {
1826 NBTrafficLightDefinition* tlDef = *it;
1827 node->removeTrafficLight(tlDef);
1828 tlc.extract(tlDef);
1829 }
1830 SumoXMLNodeType newType = NBNodeTypeComputer::isRailwayNode(node) ? NODETYPE_RAIL_SIGNAL : NODETYPE_UNKNOWN;
1831 node->reinit(node->getPosition(), newType);
1832 }
1833 }
1834 }
1835
1836
1837 void
discardRailSignals()1838 NBNodeCont::discardRailSignals() {
1839 for (auto& item : myNodes) {
1840 NBNode* node = item.second;
1841 if (node->getType() == NODETYPE_RAIL_SIGNAL) {
1842 node->reinit(node->getPosition(), NODETYPE_PRIORITY);
1843 }
1844 }
1845 }
1846
1847
1848 int
remapIDs(bool numericaIDs,bool reservedIDs,const std::string & prefix)1849 NBNodeCont::remapIDs(bool numericaIDs, bool reservedIDs, const std::string& prefix) {
1850 std::vector<std::string> avoid = getAllNames();
1851 std::set<std::string> reserve;
1852 if (reservedIDs) {
1853 NBHelpers::loadPrefixedIDsFomFile(OptionsCont::getOptions().getString("reserved-ids"), "node:", reserve); // backward compatibility
1854 NBHelpers::loadPrefixedIDsFomFile(OptionsCont::getOptions().getString("reserved-ids"), "junction:", reserve); // selection format
1855 avoid.insert(avoid.end(), reserve.begin(), reserve.end());
1856 }
1857 IDSupplier idSupplier("", avoid);
1858 NodeSet toChange;
1859 for (NodeCont::iterator it = myNodes.begin(); it != myNodes.end(); it++) {
1860 if (numericaIDs) {
1861 try {
1862 StringUtils::toLong(it->first);
1863 } catch (NumberFormatException&) {
1864 toChange.insert(it->second);
1865 }
1866 }
1867 if (reservedIDs && reserve.count(it->first) > 0) {
1868 toChange.insert(it->second);
1869 }
1870 }
1871 const bool origNames = OptionsCont::getOptions().getBool("output.original-names");
1872 for (NBNode* node : toChange) {
1873 myNodes.erase(node->getID());
1874 if (origNames) {
1875 node->setParameter(SUMO_PARAM_ORIGID, node->getID());
1876 }
1877 node->setID(idSupplier.getNext());
1878 myNodes[node->getID()] = node;
1879 }
1880 if (prefix.empty()) {
1881 return (int)toChange.size();
1882 } else {
1883 int renamed = 0;
1884 // make a copy because we will modify the map
1885 auto oldNodes = myNodes;
1886 for (auto item : oldNodes) {
1887 if (!StringUtils::startsWith(item.first, prefix)) {
1888 rename(item.second, prefix + item.first);
1889 renamed++;
1890 }
1891 }
1892 return renamed;
1893 }
1894 }
1895
1896 /****************************************************************************/
1897
1898