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 NBNodeCont.cpp
15 : /// @author Daniel Krajzewicz
16 : /// @author Jakob Erdmann
17 : /// @author Yun-Pang Floetteroed
18 : /// @author Walter Bamberger
19 : /// @author Laura Bieker
20 : /// @author Michael Behrisch
21 : /// @author Sascha Krieg
22 : /// @date Tue, 20 Nov 2001
23 : ///
24 : // Container for nodes during the netbuilding process
25 : /****************************************************************************/
26 : #include <config.h>
27 :
28 : #include <string>
29 : #include <map>
30 : #include <algorithm>
31 : #include <cmath>
32 : #include <utils/options/OptionsCont.h>
33 : #include <utils/geom/Boundary.h>
34 : #include <utils/geom/GeomHelper.h>
35 : #include <utils/common/MsgHandler.h>
36 : #include <utils/common/UtilExceptions.h>
37 : #include <utils/common/StringTokenizer.h>
38 : #include <utils/common/StringUtils.h>
39 : #include <utils/common/StdDefs.h>
40 : #include <utils/common/ToString.h>
41 : #include <utils/common/StringUtils.h>
42 : #include <utils/common/IDSupplier.h>
43 : #include <utils/xml/SUMOXMLDefinitions.h>
44 : #include <utils/geom/GeoConvHelper.h>
45 : #include <utils/iodevices/OutputDevice.h>
46 : #include "NBHelpers.h"
47 : #include "NBAlgorithms.h"
48 : #include "NBDistrict.h"
49 : #include "NBEdgeCont.h"
50 : #include "NBTrafficLightLogicCont.h"
51 : #include "NBOwnTLDef.h"
52 : #include "NBPTStop.h"
53 : #include "NBNodeCont.h"
54 : #include "NBPTStopCont.h"
55 : #include "NBPTLineCont.h"
56 : #include "NBParking.h"
57 :
58 : // ===========================================================================
59 : // Algorithm constants
60 : // ===========================================================================
61 : #define MAX_SLIPLANE_LENGTH 1000
62 :
63 : // ===========================================================================
64 : // Debug Flags
65 : // ===========================================================================
66 :
67 : //#define DEBUG_JOINJUNCTIONS
68 : //#define DEBUG_JOINJUNCTIONS_CONNECTIONS
69 : //#define DEBUG_GUESSSIGNALS
70 : #define DEBUGNODEID ""
71 : #define DEBUGNODEID2 ""
72 : //#define DEBUGNODEID "5548037023"
73 : #define DEBUGCOND(obj) ((obj) != 0 && ((obj)->getID() == DEBUGNODEID || (obj)->getID() == DEBUGNODEID2))
74 : //#define DEBUGCOND(obj) (true)
75 :
76 :
77 : // ===========================================================================
78 : // method definitions
79 : // ===========================================================================
80 2337 : NBNodeCont::~NBNodeCont() {
81 2337 : clear();
82 4674 : }
83 :
84 :
85 : // ----------- Insertion/removal/retrieval of nodes
86 : bool
87 1775 : NBNodeCont::insert(const std::string& id, const Position& position,
88 : NBDistrict* district) {
89 : NodeCont::iterator i = myNodes.find(id);
90 1775 : if (i != myNodes.end()) {
91 : return false;
92 : }
93 1733 : NBNode* node = new NBNode(id, position, district);
94 1733 : myNodes[id] = node;
95 1733 : const float pos[2] = {(float)position.x(), (float)position.y()};
96 1733 : myRTree.Insert(pos, pos, node);
97 1733 : return true;
98 : }
99 :
100 :
101 : bool
102 87666 : NBNodeCont::insert(NBNode* node) {
103 : std::string id = node->getID();
104 : NodeCont::iterator i = myNodes.find(id);
105 87666 : if (i != myNodes.end()) {
106 : return false;
107 : }
108 87458 : myNodes[id] = node;
109 87458 : const float pos[2] = {(float)node->getPosition().x(), (float)node->getPosition().y()};
110 87458 : myRTree.Insert(pos, pos, node);
111 87458 : return true;
112 : }
113 :
114 :
115 : NBNode*
116 514561 : NBNodeCont::retrieve(const std::string& id) const {
117 : NodeCont::const_iterator i = myNodes.find(id);
118 514561 : if (i == myNodes.end()) {
119 : return nullptr;
120 : }
121 455555 : return (*i).second;
122 : }
123 :
124 :
125 : NBNode*
126 236 : NBNodeCont::retrieve(const Position& position, const double offset) const {
127 236 : const double extOffset = offset + POSITION_EPS;
128 236 : const float cmin[2] = {(float)(position.x() - extOffset), (float)(position.y() - extOffset)};
129 236 : const float cmax[2] = {(float)(position.x() + extOffset), (float)(position.y() + extOffset)};
130 : std::set<const Named*> into;
131 : Named::StoringVisitor sv(into);
132 : myRTree.Search(cmin, cmax, sv);
133 236 : for (const Named* namedNode : into) {
134 78 : NBNode* node = const_cast<NBNode*>(dynamic_cast<const NBNode*>(namedNode));
135 78 : if (fabs(node->getPosition().x() - position.x()) <= offset
136 78 : &&
137 78 : fabs(node->getPosition().y() - position.y()) <= offset) {
138 : return node;
139 : }
140 : }
141 : return nullptr;
142 : }
143 :
144 :
145 : bool
146 4253 : NBNodeCont::erase(NBNode* node) {
147 4253 : if (extract(node)) {
148 4253 : delete node;
149 4253 : return true;
150 : } else {
151 : return false;
152 : }
153 : }
154 :
155 :
156 : bool
157 16332 : NBNodeCont::extract(NBNode* node, bool remember) {
158 : NodeCont::iterator i = myNodes.find(node->getID());
159 16332 : if (i == myNodes.end()) {
160 : return false;
161 : }
162 : myNodes.erase(i);
163 16332 : const float pos[2] = {(float)node->getPosition().x(), (float)node->getPosition().y()};
164 16332 : myRTree.Remove(pos, pos, node);
165 16332 : node->removeTrafficLights();
166 16332 : if (remember) {
167 12079 : myExtractedNodes[node->getID()] = node;
168 : }
169 : return true;
170 : }
171 :
172 :
173 : // ----------- Adapting the input
174 : void
175 1837 : NBNodeCont::removeSelfLoops(NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tc) {
176 1837 : int no = 0;
177 88650 : for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
178 86813 : no += (*i).second->removeSelfLoops(dc, ec, tc);
179 : }
180 1837 : if (no != 0) {
181 0 : WRITE_WARNING(toString(no) + " self-looping edge(s) removed.");
182 : }
183 1837 : }
184 :
185 :
186 : void
187 19 : NBNodeCont::joinSimilarEdges(NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc, bool removeDuplicates) {
188 : // magic values
189 : const double distanceThreshold = 7.; // don't merge edges further apart
190 : const double lengthThreshold = 0.10; // don't merge edges with higher relative length-difference
191 :
192 1408 : for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
193 : // count the edges to other nodes outgoing from the current node
194 : std::map<NBNode*, EdgeVector> connectionCount;
195 1389 : const EdgeVector& outgoing = (*i).second->getOutgoingEdges();
196 3069 : for (EdgeVector::const_iterator j = outgoing.begin(); j != outgoing.end(); j++) {
197 1680 : connectionCount[(*j)->getToNode()].push_back(*j);
198 : }
199 : // check whether more than a single edge connect another node and join them
200 : std::map<NBNode*, EdgeVector>::iterator k;
201 2995 : for (k = connectionCount.begin(); k != connectionCount.end(); k++) {
202 : // possibly we do not have anything to join...
203 1606 : if ((*k).second.size() < 2) {
204 : continue;
205 : }
206 : // for the edges that seem to be a single street,
207 : // check whether the geometry is similar
208 65 : const EdgeVector& ev = (*k).second;
209 65 : const NBEdge* const first = ev.front();
210 : EdgeVector::const_iterator jci; // join candidate iterator
211 87 : for (jci = ev.begin() + 1; jci != ev.end(); ++jci) {
212 65 : const double relativeLengthDifference = fabs(first->getLoadedLength() - (*jci)->getLoadedLength()) / first->getLoadedLength();
213 94 : if ((!first->isNearEnough2BeJoined2(*jci, distanceThreshold)) ||
214 23 : (relativeLengthDifference > lengthThreshold) ||
215 110 : (fabs(first->getSpeed() - (*jci)->getSpeed()) >= 0.01) || // output accuracy
216 22 : (first->getPermissions() != (*jci)->getPermissions())
217 : ) {
218 : break;
219 : }
220 : }
221 : // @bug If there are 3 edges of which 2 can be joined, no joining will
222 : // take place with the current implementation
223 65 : if (jci == ev.end()) {
224 22 : if (removeDuplicates) {
225 20 : for (int ei = 1; ei < (int)ev.size(); ei++) {
226 10 : ec.extract(dc, ev[ei], true);
227 : }
228 : } else {
229 24 : ec.joinSameNodeConnectingEdges(dc, tlc, ev);
230 : }
231 : }
232 : }
233 : }
234 19 : }
235 :
236 :
237 : void
238 4 : NBNodeCont::removeIsolatedRoads(NBDistrictCont& dc, NBEdgeCont& ec) {
239 : // Warn of isolated edges, i.e. a single edge with no connection to another edge
240 4 : const std::vector<std::string>& edgeNames = ec.getAllNames();
241 372 : for (std::vector<std::string>::const_iterator it = edgeNames.begin(); it != edgeNames.end(); ++it) {
242 : // Test whether this node starts at a dead end, i.e. it has only one adjacent node
243 : // to which an edge exists and from which an edge may come.
244 368 : NBEdge* e = ec.retrieve(*it);
245 368 : if (e == nullptr) {
246 315 : continue;
247 : }
248 : NBNode* from = e->getFromNode();
249 : const EdgeVector& outgoingEdges = from->getOutgoingEdges();
250 358 : if (outgoingEdges.size() != 1) {
251 : // At this node, several edges or no edge start; so, this node is no dead end.
252 266 : continue;
253 : }
254 : const EdgeVector& incomingEdges = from->getIncomingEdges();
255 92 : if (incomingEdges.size() > 1) {
256 : // At this node, several edges end; so, this node is no dead end.
257 10 : continue;
258 82 : } else if (incomingEdges.size() == 1) {
259 63 : NBNode* fromNodeOfIncomingEdge = incomingEdges[0]->getFromNode();
260 63 : NBNode* toNodeOfOutgoingEdge = outgoingEdges[0]->getToNode();
261 63 : if (fromNodeOfIncomingEdge != toNodeOfOutgoingEdge) {
262 : // At this node, an edge ends which is not the inverse direction of
263 : // the starting node.
264 29 : continue;
265 : }
266 : }
267 : // Now we know that the edge e starts a dead end.
268 : // Next we test if the dead end is isolated, i.e. does not lead to a junction
269 : bool hasJunction = false;
270 : EdgeVector road;
271 : NBEdge* eOld = nullptr;
272 : NBNode* to;
273 : NodeSet adjacentNodes;
274 : do {
275 86 : road.push_back(e);
276 86 : eOld = e;
277 : from = e->getFromNode();
278 86 : to = e->getToNode();
279 : const EdgeVector& outgoingEdgesOfToNode = to->getOutgoingEdges();
280 : const EdgeVector& incomingEdgesOfToNode = to->getIncomingEdges();
281 : adjacentNodes.clear();
282 245 : for (EdgeVector::const_iterator itOfOutgoings = outgoingEdgesOfToNode.begin(); itOfOutgoings != outgoingEdgesOfToNode.end(); ++itOfOutgoings) {
283 159 : if ((*itOfOutgoings)->getToNode() != from // The back path
284 159 : && (*itOfOutgoings)->getToNode() != to // A loop / dummy edge
285 : ) {
286 107 : e = *itOfOutgoings; // Probably the next edge
287 : }
288 159 : adjacentNodes.insert((*itOfOutgoings)->getToNode());
289 : }
290 268 : for (EdgeVector::const_iterator itOfIncomings = incomingEdgesOfToNode.begin(); itOfIncomings != incomingEdgesOfToNode.end(); ++itOfIncomings) {
291 182 : adjacentNodes.insert((*itOfIncomings)->getFromNode());
292 : }
293 : adjacentNodes.erase(to); // Omit loops
294 86 : if (adjacentNodes.size() > 2) {
295 : hasJunction = true;
296 : }
297 44 : } while (!hasJunction && eOld != e);
298 53 : if (!hasJunction) {
299 : std::string warningString;
300 38 : for (EdgeVector::iterator roadIt = road.begin(); roadIt != road.end(); ++roadIt) {
301 27 : if (roadIt == road.begin()) {
302 11 : warningString += (*roadIt)->getID();
303 : } else {
304 32 : warningString += "," + (*roadIt)->getID();
305 : }
306 :
307 27 : NBNode* fromNode = (*roadIt)->getFromNode();
308 : NBNode* toNode = (*roadIt)->getToNode();
309 27 : ec.erase(dc, *roadIt);
310 27 : if (fromNode->getIncomingEdges().size() == 0 && fromNode->getOutgoingEdges().size() == 0) {
311 : // Node is empty; can be removed
312 14 : erase(fromNode);
313 : }
314 27 : if (toNode->getIncomingEdges().size() == 0 && toNode->getOutgoingEdges().size() == 0) {
315 : // Node is empty; can be removed
316 5 : erase(toNode);
317 : }
318 : }
319 37 : WRITE_WARNINGF(TL("Removed a road without junctions: %."), warningString);
320 : }
321 : }
322 4 : }
323 :
324 :
325 : void
326 23 : NBNodeCont::removeComponents(NBDistrictCont& dc, NBEdgeCont& ec, const int numKeep, bool hasPTStops) {
327 23 : myRailComponents.clear();
328 : std::vector<std::set<NBEdge*> > components;
329 : // need to use ids here to have the same ordering on all platforms
330 : std::set<std::string> edgesLeft;
331 2293 : for (std::map<std::string, NBEdge*>::const_iterator edgeIt = ec.begin(); edgeIt != ec.end(); ++edgeIt) {
332 2270 : edgesLeft.insert(edgeIt->first);
333 : }
334 : EdgeVector queue;
335 : std::set<NBEdge*> toRemove;
336 23 : int foundComponents = 0;
337 23 : int numRemoved = 0;
338 104 : while (!edgesLeft.empty()) {
339 81 : queue.push_back(ec.getByID(*edgesLeft.begin()));
340 : std::set<NBEdge*> component;
341 2432 : while (!queue.empty()) {
342 2351 : NBEdge* const e = queue.back();
343 : queue.pop_back();
344 : component.insert(e);
345 : std::vector<EdgeVector> edgeLists;
346 2351 : edgeLists.push_back(e->getFromNode()->getOutgoingEdges());
347 2351 : edgeLists.push_back(e->getFromNode()->getIncomingEdges());
348 2351 : edgeLists.push_back(e->getToNode()->getOutgoingEdges());
349 2351 : edgeLists.push_back(e->getToNode()->getIncomingEdges());
350 11755 : for (std::vector<EdgeVector>::const_iterator listIt = edgeLists.begin(); listIt != edgeLists.end(); ++listIt) {
351 26000 : for (EdgeVector::const_iterator edgeIt = listIt->begin(); edgeIt != listIt->end(); ++edgeIt) {
352 16596 : std::set<std::string>::iterator leftIt = edgesLeft.find((*edgeIt)->getID());
353 16596 : if (leftIt != edgesLeft.end()) {
354 2270 : queue.push_back(*edgeIt);
355 : edgesLeft.erase(leftIt);
356 : }
357 : }
358 : }
359 2351 : }
360 81 : foundComponents++;
361 : std::vector<std::set<NBEdge*> >::iterator cIt;
362 154 : for (cIt = components.begin(); cIt != components.end(); ++cIt) {
363 81 : if (cIt->size() < component.size()) {
364 : break;
365 : }
366 : }
367 81 : components.insert(cIt, component);
368 81 : if ((int)components.size() > numKeep) {
369 : bool recheck = false;
370 56 : if (hasPTStops) {
371 134 : for (NBEdge* e : components.back()) {
372 118 : SVCPermissions permissions = e->getPermissions();
373 118 : if (isRailway(permissions) || isWaterway(permissions)) {
374 : // recheck for connection to other components via access definitions
375 : recheck = true;
376 : break;
377 : }
378 : }
379 : }
380 18 : if (!recheck) {
381 54 : toRemove.insert(components.back().begin(), components.back().end());
382 54 : numRemoved++;
383 : } else {
384 : std::vector<std::string> edgeIDs;
385 4 : for (NBEdge* e : components.back()) {
386 2 : edgeIDs.push_back(e->getID());
387 : }
388 2 : myRailComponents.push_back(edgeIDs);
389 2 : }
390 : components.pop_back();
391 : }
392 : }
393 23 : ec.removeRoundaboutEdges(toRemove);
394 344 : for (NBEdge* e : toRemove) {
395 : NBNode* const fromNode = e->getFromNode();
396 : NBNode* const toNode = e->getToNode();
397 321 : ec.erase(dc, e);
398 321 : if (fromNode->getIncomingEdges().size() == 0 && fromNode->getOutgoingEdges().size() == 0) {
399 153 : erase(fromNode);
400 : }
401 321 : if (toNode->getIncomingEdges().size() == 0 && toNode->getOutgoingEdges().size() == 0) {
402 115 : erase(toNode);
403 : }
404 : }
405 23 : if (foundComponents > 1) {
406 28 : WRITE_MESSAGEF(TL("Found % components and removed % (% edges)."), toString(foundComponents), toString(numRemoved), toString(toRemove.size()));
407 : }
408 23 : }
409 :
410 :
411 : void
412 23 : NBNodeCont::removeRailComponents(NBDistrictCont& dc, NBEdgeCont& ec, NBPTStopCont& sc) {
413 : std::set<std::string> stopEdges;
414 120 : for (const auto& item : sc.getStops()) {
415 97 : stopEdges.insert(item.second->getEdgeId());
416 : }
417 23 : int numRemoved = 0;
418 23 : int numRemovedEdges = 0;
419 25 : for (auto& component : myRailComponents) {
420 : bool keep = false;
421 3 : for (std::string edgeID : component) {
422 : if (stopEdges.count(edgeID) != 0) {
423 : keep = true;
424 : break;
425 : }
426 : }
427 : if (!keep) {
428 1 : numRemoved++;
429 1 : numRemovedEdges += (int)component.size();
430 2 : for (std::string edgeID : component) {
431 1 : NBEdge* e = ec.retrieve(edgeID);
432 1 : if (e != nullptr) {
433 : NBNode* const fromNode = e->getFromNode();
434 : NBNode* const toNode = e->getToNode();
435 1 : ec.erase(dc, e);
436 1 : if (fromNode->getIncomingEdges().size() == 0 && fromNode->getOutgoingEdges().size() == 0) {
437 1 : erase(fromNode);
438 : }
439 1 : if (toNode->getIncomingEdges().size() == 0 && toNode->getOutgoingEdges().size() == 0) {
440 1 : erase(toNode);
441 : }
442 : }
443 : }
444 : }
445 : }
446 23 : if (numRemoved > 0) {
447 2 : WRITE_MESSAGEF(TL("Removed % railway components (% edges)."), toString(numRemoved), toString(numRemovedEdges));
448 : }
449 23 : }
450 :
451 :
452 : int
453 1838 : NBNodeCont::removeUnwishedNodes(NBDistrictCont& dc, NBEdgeCont& ec,
454 : NBTrafficLightLogicCont& /*tlc*/, NBPTStopCont& sc,
455 : NBPTLineCont& lc,
456 : NBParkingCont& pc,
457 : bool removeGeometryNodes) {
458 : // load edges that shall not be modified
459 : std::set<std::string> edges2keep;
460 1838 : if (removeGeometryNodes) {
461 108 : const OptionsCont& oc = OptionsCont::getOptions();
462 216 : if (oc.isSet("geometry.remove.keep-edges.input-file")) {
463 3 : NBHelpers::loadEdgesFromFile(oc.getString("geometry.remove.keep-edges.input-file"), edges2keep);
464 : }
465 216 : if (oc.isSet("geometry.remove.keep-edges.explicit")) {
466 2 : const std::vector<std::string> edges = oc.getStringVector("geometry.remove.keep-edges.explicit");
467 : edges2keep.insert(edges.begin(), edges.end());
468 1 : }
469 : // no need to keep pt stop edges, they are remapped later
470 : // no need to keep all pt route edges. They are validated again before writing
471 108 : pc.addEdges2Keep(oc, edges2keep);
472 429 : if (oc.exists("geometry.remove.keep-ptstops") && oc.getBool("geometry.remove.keep-ptstops")) {
473 1 : sc.addEdges2Keep(oc, edges2keep);
474 : }
475 : }
476 :
477 : std::map<NBEdge*, std::set<NBTrafficLightDefinition*> > tlsLookup;
478 139219 : for (auto it = ec.begin(); it != ec.end(); it++) {
479 137381 : NBEdge* e = it->second;
480 : NBNode* to = e->getToNode();
481 137381 : if (to->isTLControlled()) {
482 8247 : tlsLookup[e] = to->getControllingTLS();
483 : }
484 : }
485 :
486 : std::vector<NBNode*> toRemove;
487 85610 : for (const auto& i : myNodes) {
488 83772 : NBNode* const current = i.second;
489 : bool remove = false;
490 : // check for completely empty nodes and check for nodes which are only geometry nodes and ask the node whether to join
491 114003 : if (current->getEdges().empty() || (removeGeometryNodes && mySplit.count(current) == 0 && current->checkIsRemovable())) {
492 : remove = true;
493 : // check whether any of the edges must be kept
494 30809 : for (NBEdge* const it_edge : current->getEdges()) {
495 18741 : if (edges2keep.find(it_edge->getID()) != edges2keep.end()) {
496 : remove = false;
497 : break;
498 : }
499 : }
500 : }
501 : // remove the node and join the geometries when wished
502 12100 : if (!remove) {
503 71704 : continue;
504 : }
505 21422 : for (const std::pair<NBEdge*, NBEdge*>& j : current->getEdgesToJoin()) {
506 9354 : NBEdge* const begin = j.first;
507 9354 : NBEdge* const continuation = j.second;
508 9354 : begin->append(continuation);
509 9354 : continuation->getToNode()->replaceIncoming(continuation, begin, 0);
510 : auto itTL = tlsLookup.find(continuation);
511 9354 : if (itTL != tlsLookup.end()) {
512 1764 : for (NBTrafficLightDefinition* tls : itTL->second) {
513 882 : tls->replaceRemoved(continuation, -1, begin, -1, true);
514 : }
515 882 : tlsLookup[begin] = itTL->second;
516 : }
517 9354 : sc.replaceEdge(continuation->getID(), { begin });
518 9354 : lc.replaceEdge(continuation->getID(), { begin });
519 9354 : ec.extract(dc, continuation, true);
520 : }
521 12068 : toRemove.push_back(current);
522 : }
523 : // erase all
524 13906 : for (NBNode* n : toRemove) {
525 12068 : extract(n, true);
526 : }
527 3676 : return (int)toRemove.size();
528 : }
529 :
530 :
531 : void
532 1719 : NBNodeCont::avoidOverlap() {
533 52871 : for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
534 51152 : (*i).second->avoidOverlap();
535 : }
536 1719 : }
537 :
538 :
539 : // ----------- (Helper) methods for joining nodes
540 : void
541 156 : NBNodeCont::generateNodeClusters(double maxDist, NodeClusters& into) const {
542 : std::set<NBNode*> visited;
543 57748 : for (const auto& i : myNodes) {
544 8099 : if (visited.count(i.second) > 0) {
545 53940 : continue;
546 : }
547 : std::vector<NodeAndDist> toProc;
548 49493 : toProc.emplace_back(i.second, 0.);
549 : NodeSet c;
550 111294 : while (!toProc.empty()) {
551 61801 : NBNode* const n = toProc.back().first;
552 61801 : const double dist = toProc.back().second;
553 : toProc.pop_back();
554 4209 : if (visited.count(n) > 0) {
555 11959 : continue;
556 : }
557 : visited.insert(n);
558 : bool pureRail = true;
559 : bool railAndPeds = true;
560 131119 : for (NBEdge* e : n->getEdges()) {
561 99295 : if ((e->getPermissions() & ~(SVC_RAIL_CLASSES | SVC_PEDESTRIAN)) != 0) {
562 : railAndPeds = false;
563 : pureRail = false;
564 : break;
565 : }
566 73527 : if ((e->getPermissions() & ~(SVC_RAIL_CLASSES)) != 0) {
567 : pureRail = false;
568 : }
569 : }
570 57592 : if (pureRail) {
571 : // do not join pure rail nodes
572 7750 : continue;
573 : }
574 : c.insert(n);
575 215720 : for (NBEdge* e : n->getEdges()) {
576 331756 : NBNode* s = n->hasIncoming(e) ? e->getFromNode() : e->getToNode();
577 : const double length = e->getLoadedLength();
578 : #ifdef DEBUG_JOINJUNCTIONS
579 : if (DEBUGCOND(s)) {
580 : std::cout << "generateNodeClusters: consider s=" << s->getID()
581 : << " clusterNode=" << n->getID() << " edge=" << e->getID() << " dist=" << dist << " length=" << length << " with cluster " << joinNamedToString(c, ' ') << "\n";
582 : }
583 : #endif
584 165878 : if (railAndPeds && n->getType() != SumoXMLNodeType::RAIL_CROSSING) {
585 : bool railAndPeds2 = true;
586 204380 : for (NBEdge* e2 : n->getEdges()) {
587 149827 : if ((e2->getPermissions() & ~(SVC_RAIL_CLASSES | SVC_PEDESTRIAN)) != 0) {
588 : railAndPeds2 = false;
589 : break;
590 : }
591 : }
592 54553 : if (railAndPeds2 && s->getType() != SumoXMLNodeType::RAIL_CROSSING) {
593 : // do not join rail/ped nodes unless at a rail crossing
594 : // (neither nodes nor the traffic lights)
595 132021 : continue;
596 : }
597 : }
598 111849 : const bool bothCrossing = n->getType() == SumoXMLNodeType::RAIL_CROSSING && s->getType() == SumoXMLNodeType::RAIL_CROSSING;
599 1228 : const bool joinPedCrossings = bothCrossing && e->getPermissions() == SVC_PEDESTRIAN;
600 42615 : if ( // never join pedestrian stuff (unless at a rail crossing
601 111539 : !joinPedCrossings && (
602 111539 : e->getPermissions() == SVC_PEDESTRIAN
603 : // only join edges for regular passenger traffic or edges that are extremely short
604 99008 : || (length > 3 * POSITION_EPS
605 89822 : && (e->getPermissions() & (SVC_PASSENGER | SVC_TRAM)) == 0
606 30128 : && n->getPosition().distanceTo2D(s->getPosition()) > SUMO_const_laneWidth))) {
607 : #ifdef DEBUG_JOINJUNCTIONS
608 : if (DEBUGCOND(s)) {
609 : std::cout << " ignored s=" << s->getID() << " pedestrian edge=" << e->getID() << " cd=" << n->getPosition().distanceTo2D(s->getPosition()) << "\n";
610 : }
611 : #endif
612 42615 : continue;
613 : }
614 : // never join rail_crossings with other node types unless the crossing is only for tram
615 69234 : if ((n->getType() == SumoXMLNodeType::RAIL_CROSSING && s->getType() != SumoXMLNodeType::RAIL_CROSSING)
616 70450 : || (n->getType() != SumoXMLNodeType::RAIL_CROSSING && s->getType() == SumoXMLNodeType::RAIL_CROSSING)) {
617 : const SVCPermissions railNoTram = (SVC_RAIL_CLASSES & ~SVC_TRAM);
618 : bool foundRail = false;
619 1461 : NBNode* crossingNode = n->getType() == SumoXMLNodeType::RAIL_CROSSING ? n : s;
620 5427 : for (NBEdge* e2 : crossingNode->getIncomingEdges()) {
621 3982 : if ((e2->getPermissions() & railNoTram) != 0) {
622 : foundRail = true;
623 : break;
624 : }
625 : }
626 1461 : if (foundRail) {
627 16 : continue;
628 : }
629 : }
630 : // never join rail_crossings via a rail edge
631 69218 : if (bothCrossing && (e->getPermissions() & ~SVC_RAIL_CLASSES) == 0) {
632 822 : continue;
633 : }
634 68396 : if (visited.find(s) != visited.end()) {
635 34539 : continue;
636 : }
637 33857 : if (length + dist < maxDist) {
638 : // don't add long "boring" appendages but always join the whole rail crossing or tls
639 12308 : const bool trueGeomLike = s->geometryLike();
640 12308 : if (trueGeomLike || geometryLikeForClass(s, SVC_WEAK | SVC_DELIVERY)) {
641 15467 : const bool hasTLS = n->isTrafficLight() || s->isTrafficLight();
642 8217 : const double fullLength = e->getGeometry().length2D();
643 8217 : const double length2 = bothCrossing || hasTLS || trueGeomLike ? length : fullLength;
644 8217 : toProc.emplace_back(s, dist + length2);
645 : } else {
646 4091 : toProc.emplace_back(s, 0.);
647 : }
648 : }
649 : }
650 : }
651 49493 : if (c.size() < 2) {
652 : continue;
653 : }
654 : #ifdef DEBUG_JOINJUNCTIONS
655 : std::cout << " DEBUG: consider cluster " << joinNamedToString(c, ' ') << "\n";
656 : #endif
657 3652 : into.push_back(c);
658 : }
659 156 : }
660 :
661 :
662 : bool
663 9015 : NBNodeCont::geometryLikeForClass(const NBNode* n, SVCPermissions ignored) {
664 : EdgeVector allowedIn;
665 : EdgeVector allowedOut;
666 33348 : for (NBEdge* e : n->getIncomingEdges()) {
667 24333 : if ((e->getPermissions() & ~ignored) != 0) {
668 18027 : allowedIn.push_back(e);
669 : }
670 : }
671 33253 : for (NBEdge* e : n->getOutgoingEdges()) {
672 24238 : if ((e->getPermissions() & ~ignored) != 0) {
673 17940 : allowedOut.push_back(e);
674 : }
675 : }
676 9015 : if (allowedIn.size() > 0 && allowedOut.size() > 0) {
677 : //std::cout << n->getID() << " geometryLikeForClass=" << n->geometryLike(allowedIn, allowedOut) << " in=" << toString(allowedIn) << " out=" << toString(allowedOut) << "\n";
678 8344 : return n->geometryLike(allowedIn, allowedOut);
679 : }
680 : return true;
681 : }
682 :
683 :
684 : void
685 16 : NBNodeCont::addJoinExclusion(const std::vector<std::string>& ids) {
686 116 : for (const std::string& nodeID : ids) {
687 : // error handling has to take place here since joinExclusions could be
688 : // loaded from multiple files / command line
689 : if (myJoined.count(nodeID) > 0) {
690 0 : WRITE_WARNINGF(TL("Ignoring join exclusion for junction '%' since it already occurred in a list of nodes to be joined."), nodeID);
691 : } else {
692 : myJoinExclusions.insert(nodeID);
693 : }
694 : }
695 16 : }
696 :
697 :
698 : std::string
699 1305 : NBNodeCont::createClusterId(const std::set<std::string>& cluster, const std::string& prefix) {
700 1305 : int maxIds = OptionsCont::getOptions().getInt("max-join-ids");
701 1305 : if (maxIds <= 0) {
702 0 : maxIds = (int)cluster.size();
703 : }
704 1305 : if ((int)cluster.size() > maxIds) {
705 : auto clusterIt = cluster.begin();
706 187 : std::string result = prefix + *clusterIt;
707 748 : for (int i = 1; i < maxIds; i++) {
708 : ++clusterIt;
709 1122 : result += "_" + *clusterIt;
710 : }
711 374 : return result + "_#" + toString((int)cluster.size() - maxIds) + "more";
712 : }
713 2236 : return prefix + joinToString(cluster, "_");
714 : }
715 :
716 :
717 : void
718 10 : NBNodeCont::addCluster2Join(const std::set<std::string>& cluster, NBNode* node) {
719 : // error handling has to take place here since joins could be loaded from multiple files
720 : std::set<std::string> validCluster;
721 92 : for (std::string nodeID : cluster) {
722 : if (myJoinExclusions.count(nodeID) > 0) {
723 0 : WRITE_WARNINGF(TL("Ignoring join-cluster because junction '%' was already excluded from joining."), nodeID);
724 0 : return;
725 : } else if (myJoined.count(nodeID) > 0) {
726 0 : WRITE_WARNINGF(TL("Ignoring join-cluster because junction '%' already occurred in another join-cluster."), nodeID);
727 0 : return;
728 : } else {
729 82 : if (retrieve(nodeID) != nullptr) {
730 : validCluster.insert(nodeID);
731 : } else {
732 0 : WRITE_ERRORF(TL("Unknown junction '%' in join-cluster."), nodeID);
733 : }
734 : }
735 : }
736 10 : if (validCluster.size() > 1) {
737 9 : myJoined.insert(validCluster.begin(), validCluster.end());
738 18 : myClusters2Join.push_back(std::make_pair(validCluster, node));
739 : } else {
740 4 : WRITE_WARNINGF(TL("Ignoring join-cluster '%' because it has size '%'."), node->getID(), validCluster.size());
741 : }
742 : }
743 :
744 :
745 : int
746 1837 : NBNodeCont::joinLoadedClusters(NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc) {
747 : int numJoined = 0;
748 1846 : for (auto& item : myClusters2Join) {
749 : // verify loaded cluster
750 : NodeSet cluster;
751 90 : for (std::string nodeID : item.first) {
752 81 : NBNode* node = retrieve(nodeID);
753 81 : if (node == nullptr) {
754 0 : WRITE_ERRORF(TL("unknown junction '%' while joining."), nodeID);
755 : } else {
756 : cluster.insert(node);
757 : }
758 : }
759 9 : if (cluster.size() > 1) {
760 9 : joinNodeCluster(cluster, dc, ec, tlc, item.second);
761 9 : numJoined++;
762 9 : myJoinExclusions.insert(item.second->getID());
763 : }
764 : }
765 1837 : myClusters2Join.clear(); // make save for recompute
766 1837 : return numJoined;
767 : }
768 :
769 :
770 : int
771 109 : NBNodeCont::joinJunctions(double maxDist, NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc, NBPTStopCont& sc) {
772 : #ifdef DEBUG_JOINJUNCTIONS
773 : std::cout << "joinJunctions...\n";
774 : #endif
775 : NodeClusters cands;
776 : NodeClusters clusters;
777 : std::map<const NBNode*, std::vector<NBNode*> > ptStopEnds;
778 : // check for stop edges within the cluster
779 1648 : for (const auto& stopIt : sc.getStops()) {
780 1539 : NBEdge* edge = ec.retrieve(stopIt.second->getEdgeId());
781 1539 : if (edge != nullptr) {
782 1539 : ptStopEnds[edge->getFromNode()].push_back(edge->getToNode());
783 : }
784 : }
785 109 : generateNodeClusters(maxDist, cands);
786 2552 : for (NodeSet& cluster : cands) {
787 : #ifdef DEBUG_JOINJUNCTIONS
788 : gDebugFlag1 = false;
789 : for (NBNode* n : cluster) {
790 : if (DEBUGCOND(n)) {
791 : gDebugFlag1 = true;
792 : }
793 : }
794 : #endif
795 : // remove join exclusions
796 10597 : for (NodeSet::iterator j = cluster.begin(); j != cluster.end();) {
797 : NodeSet::iterator check = j;
798 : ++j;
799 8154 : if (myJoinExclusions.count((*check)->getID()) > 0) {
800 : cluster.erase(check);
801 : }
802 : }
803 2443 : std::string origCluster = joinNamedToString(cluster, ',');
804 : // remove nodes that can be eliminated by geometry.remove
805 2443 : pruneClusterFringe(cluster, maxDist);
806 2443 : if (cluster.size() < 2) {
807 1198 : continue;
808 : }
809 : // remove nodes that are part of a bypass lane (typically for turning right without waiting at a traffic light)
810 1245 : pruneSlipLaneNodes(cluster, maxDist);
811 1245 : if (cluster.size() < 2) {
812 3 : WRITE_WARNINGF(TL("Not joining junctions % (%)."), origCluster, "slip lane");
813 1 : continue;
814 : }
815 : std::string reason;
816 : std::string origReason;
817 : // pruneLongEdges might remove too much, so we check first to have a fallback with the circles
818 1244 : bool feasible = feasibleCluster(cluster, ptStopEnds, maxDist, origReason);
819 1244 : if (feasible && ((int)cluster.size() - pruneLongEdges(cluster, maxDist, true) < 2)) {
820 : origReason = "long edge";
821 : feasible = false;
822 : }
823 1235 : if (!feasible) {
824 : #ifdef DEBUG_JOINJUNCTIONS
825 : if (gDebugFlag1) {
826 : std::cout << " try to reduce to 4-circle nodes=" << joinNamedToString(cluster, ',') << "\n";
827 : }
828 : #endif
829 209 : if (reduceToCircle(cluster, 4, cluster, maxDist)) {
830 1 : feasible = feasibleCluster(cluster, ptStopEnds, maxDist, reason);
831 1 : if (feasible) {
832 5 : WRITE_WARNINGF(TL("Reducing junction cluster % (%)."), origCluster, origReason);
833 : }
834 : }
835 : }
836 1244 : if (!feasible) {
837 : #ifdef DEBUG_JOINJUNCTIONS
838 : if (gDebugFlag1) {
839 : std::cout << " try to reduce to 2-circle nodes=" << joinNamedToString(cluster, ',') << "\n";
840 : }
841 : #endif
842 182 : origCluster = joinNamedToString(cluster, ',');
843 243 : if (reduceToCircle(cluster, 2, cluster, maxDist)) {
844 28 : feasible = feasibleCluster(cluster, ptStopEnds, maxDist, reason);
845 28 : if (feasible) {
846 121 : WRITE_WARNINGF(TL("Reducing junction cluster % (%)."), origCluster, origReason);
847 : }
848 : }
849 : }
850 : // avoid removal of long edges (must have been added via an alternative path).
851 1244 : const int numPruned = pruneLongEdges(cluster, maxDist);
852 1244 : if (cluster.size() < 2) {
853 0 : WRITE_WARNINGF(TL("Not joining junctions % (%)."), origCluster, "long edge");
854 0 : continue;
855 : }
856 : // after pruning long edges we have to recheck
857 1244 : if (numPruned > 0) {
858 6 : pruneClusterFringe(cluster, maxDist);
859 6 : if (cluster.size() < 2) {
860 0 : WRITE_WARNINGF(TL("Not joining junctions % (%)."), origCluster, "long edge");
861 0 : continue;
862 : }
863 6 : pruneSlipLaneNodes(cluster, maxDist);
864 6 : if (cluster.size() < 2) {
865 0 : WRITE_WARNINGF(TL("Not joining junctions % (%)."), origCluster, "slip lane");
866 0 : continue;
867 : }
868 : }
869 1244 : origCluster = joinNamedToString(cluster, ',');
870 1244 : feasible = feasibleCluster(cluster, ptStopEnds, maxDist, origReason);
871 1244 : if (!feasible) {
872 260 : WRITE_WARNINGF(TL("Not joining junctions % (%)."), origCluster, origReason);
873 66 : continue;
874 : }
875 : // compute all connected components of this cluster
876 : // (may be more than 1 if intermediate nodes were removed)
877 : NodeClusters components;
878 5023 : for (NBNode* current : cluster) {
879 : // merge all connected components into newComp
880 : NodeSet newComp;
881 : //std::cout << "checking connectivity for " << current->getID() << "\n";
882 : newComp.insert(current);
883 7601 : for (NodeClusters::iterator it_comp = components.begin(); it_comp != components.end();) {
884 : NodeClusters::iterator check = it_comp;
885 : //std::cout << " connected with " << toString(*check) << "?\n";
886 : bool connected = false;
887 6981 : for (NBNode* k : *check) {
888 5892 : if (current->getConnectionTo(k) != nullptr || k->getConnectionTo(current) != nullptr) {
889 : //std::cout << "joining with connected component " << toString(*check) << "\n";
890 2667 : newComp.insert((*check).begin(), (*check).end());
891 : it_comp = components.erase(check);
892 : connected = true;
893 : break;
894 : }
895 : }
896 : if (!connected) {
897 : it_comp++;
898 : }
899 : }
900 : //std::cout << "adding new component " << toString(newComp) << "\n";
901 3845 : components.push_back(newComp);
902 : }
903 2356 : for (NodeClusters::iterator it_comp = components.begin(); it_comp != components.end(); ++it_comp) {
904 1178 : if ((*it_comp).size() > 1) {
905 : //std::cout << "adding cluster " << toString(*it_comp) << "\n";
906 1178 : clusters.push_back(*it_comp);
907 : }
908 : }
909 : #ifdef DEBUG_JOINJUNCTIONS
910 : gDebugFlag1 = false;
911 : #endif
912 1178 : }
913 109 : joinNodeClusters(clusters, dc, ec, tlc);
914 218 : return (int)clusters.size();
915 109 : }
916 :
917 :
918 : int
919 11 : NBNodeCont::joinSameJunctions(NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc) {
920 : #ifdef DEBUG_JOINJUNCTIONS
921 : std::cout << "joinSameJunctions...\n";
922 : #endif
923 : std::map<std::string, NodeSet> positions;
924 950 : for (auto& item : myNodes) {
925 939 : Position pos = item.second->getPosition();
926 1878 : std::string rounded = (OutputDevice::realString(pos.x(), gPrecision)
927 3756 : + "_" + OutputDevice::realString(pos.y(), gPrecision)
928 2817 : + "_" + OutputDevice::realString(pos.z(), gPrecision));
929 939 : positions[rounded].insert(item.second);
930 : }
931 : NodeClusters clusters;
932 931 : for (auto& item : positions) {
933 920 : if (item.second.size() > 1) {
934 57 : for (NBNode* n : item.second) {
935 : if (myJoinExclusions.count(n->getID()) > 0) {
936 : item.second.erase(n);
937 : }
938 : }
939 19 : if (item.second.size() > 1) {
940 19 : clusters.push_back(item.second);
941 : }
942 : }
943 : }
944 11 : joinNodeClusters(clusters, dc, ec, tlc, true);
945 11 : return (int)clusters.size();
946 11 : }
947 :
948 : void
949 2500 : NBNodeCont::pruneClusterFringe(NodeSet& cluster, double maxDist) const {
950 : #ifdef DEBUG_JOINJUNCTIONS
951 : if (gDebugFlag1) {
952 : std::cout << "pruning cluster=" << joinNamedToString(cluster, ' ') << "\n";
953 : }
954 : #endif
955 : // iteratively remove the fringe
956 : bool pruneFringe = true;
957 : bool pruneNoisyFringe = false;
958 : // collect nodes that shall be joined due to distance but are not connected
959 : // to the cluster for passenger traffic
960 7281 : while (pruneFringe) {
961 : pruneFringe = false;
962 23463 : for (NodeSet::iterator j = cluster.begin(); j != cluster.end();) {
963 : NodeSet::iterator check = j;
964 16182 : NBNode* n = *check;
965 : ++j;
966 :
967 : // compute clusterDist for node (length of shortest edge which connects this node to the cluster)
968 : double clusterDist = std::numeric_limits<double>::max();
969 : bool touchingCluster = false;
970 51951 : for (EdgeVector::const_iterator it_edge = n->getOutgoingEdges().begin(); it_edge != n->getOutgoingEdges().end(); ++it_edge) {
971 35769 : NBNode* neighbor = (*it_edge)->getToNode();
972 : if (cluster.count(neighbor) != 0) {
973 : clusterDist = MIN2(clusterDist, (*it_edge)->getLoadedLength());
974 16775 : touchingCluster |= n->getPosition().distanceTo2D(neighbor->getPosition()) <= SUMO_const_laneWidth;
975 : }
976 : }
977 52147 : for (EdgeVector::const_iterator it_edge = n->getIncomingEdges().begin(); it_edge != n->getIncomingEdges().end(); ++it_edge) {
978 35965 : NBNode* neighbor = (*it_edge)->getFromNode();
979 : if (cluster.count(neighbor) != 0) {
980 : clusterDist = MIN2(clusterDist, (*it_edge)->getLoadedLength());
981 16567 : touchingCluster |= n->getPosition().distanceTo2D(neighbor->getPosition()) <= SUMO_const_laneWidth;
982 : }
983 : }
984 : // remove geometry-like nodes at fringe of the cluster
985 : // (they have 1 neighbor in the cluster and at most 1 neighbor outside the cluster)
986 : std::set<NBNode*> outsideNeighbors;
987 : std::set<NBNode*> clusterNeighbors;
988 : const double pedestrianFringeThreshold = 0.3;
989 87916 : for (NBEdge* e : n->getEdges()) {
990 107503 : NBNode* neighbor = e->getFromNode() == n ? e->getToNode() : e->getFromNode();
991 : if (cluster.count(neighbor) == 0) {
992 38392 : if ((e->getPermissions() & SVC_PASSENGER) != 0
993 16567 : || isRailway(e->getPermissions()) // join railway crossings
994 12421 : || (clusterDist <= pedestrianFringeThreshold
995 8361 : && (!pruneNoisyFringe
996 3177 : || ((e->getPermissions() & SVC_WEAK) != 0 &&
997 3170 : (e->getPermissions() & ~SVC_WEAK) == 0)
998 : // permit joining small opposite merges
999 1213 : || getDiameter(cluster) < maxDist
1000 277 : || cluster.size() == 2))
1001 42624 : || touchingCluster) {
1002 : outsideNeighbors.insert(neighbor);
1003 : }
1004 : } else {
1005 : clusterNeighbors.insert(neighbor);
1006 : }
1007 : }
1008 : #ifdef DEBUG_JOINJUNCTIONS
1009 : if (gDebugFlag1) std::cout << " check n=" << n->getID()
1010 : << " clusterDist=" << clusterDist
1011 : << " cd<th=" << (clusterDist <= pedestrianFringeThreshold)
1012 : << " touching=" << touchingCluster
1013 : << " out=" << joinNamedToString(outsideNeighbors, ',')
1014 : << " in=" << joinNamedToString(clusterNeighbors, ',')
1015 : << " dia=" << getDiameter(cluster)
1016 : << "\n";
1017 : #endif
1018 : if (clusterNeighbors.size() == 0
1019 16182 : || (outsideNeighbors.size() <= 1
1020 8104 : && clusterNeighbors.size() == 1
1021 3406 : && !n->isTLControlled())) {
1022 : cluster.erase(check);
1023 : pruneFringe = true; // other nodes could belong to the fringe now
1024 : #ifdef DEBUG_JOINJUNCTIONS
1025 : if (gDebugFlag1) {
1026 : std::cout << " pruned n=" << n->getID() << "\n";
1027 : }
1028 : #endif
1029 : }
1030 : }
1031 7281 : if (!pruneFringe && !pruneNoisyFringe) {
1032 : // run once more and prune more things (with a look at cluster size)
1033 : pruneFringe = true;
1034 : pruneNoisyFringe = true;
1035 :
1036 : }
1037 : }
1038 2500 : }
1039 :
1040 : double
1041 1213 : NBNodeCont::getDiameter(const NodeSet& cluster) {
1042 : double result = 0;
1043 4598 : for (const NBNode* n1 : cluster) {
1044 18454 : for (const NBNode* n2 : cluster) {
1045 : result = MAX2(result, n1->getPosition().distanceTo2D(n2->getPosition()));
1046 : }
1047 : }
1048 1213 : return result;
1049 : }
1050 :
1051 : int
1052 2405 : NBNodeCont::pruneLongEdges(NodeSet& cluster, double maxDist, const bool dryRun) {
1053 : std::set<NBNode*> toRemove;
1054 : int maxPassengerLanes = 0;
1055 10335 : for (NBNode* n : cluster) {
1056 45139 : for (NBEdge* edge : n->getEdges()) {
1057 37209 : maxPassengerLanes = MAX2(maxPassengerLanes, edge->getNumLanesThatAllow(SVC_PASSENGER));
1058 : }
1059 : }
1060 10335 : for (NBNode* n : cluster) {
1061 26489 : for (NBEdge* edge : n->getOutgoingEdges()) {
1062 : // we must track the edge length accross geometry like nodes
1063 : // Also, intersecions that are geometry-like
1064 : // from the perspective of passenger traffic should be tracked accross
1065 : std::vector<NBNode*> passed;
1066 : double length = 0;
1067 : NBEdge* cur = edge;
1068 18559 : NBNode* to = edge->getToNode();
1069 18559 : while (cluster.count(to) != 0) {
1070 10392 : length += cur->getLoadedLength();
1071 10392 : bool goStraight = (std::find(passed.begin(), passed.end(), to) == passed.end()
1072 10392 : && (edge->getPermissions() & SVC_PASSENGER) != 0
1073 26328 : && to->geometryLike(
1074 18360 : NBEdge::filterByPermissions(to->getIncomingEdges(), SVC_PASSENGER),
1075 18360 : NBEdge::filterByPermissions(to->getOutgoingEdges(), SVC_PASSENGER)));
1076 10392 : passed.push_back(to);
1077 10392 : if (goStraight) {
1078 4196 : cur = cur->getStraightContinuation(SVC_PASSENGER);
1079 4196 : if (cur != nullptr) {
1080 4164 : to = cur->getToNode();
1081 : } else {
1082 : break;
1083 : }
1084 : } else {
1085 : break;
1086 : }
1087 : }
1088 : // allow higher threshold at larger junctions
1089 18559 : double longThreshold = maxDist + SUMO_const_laneWidth * MAX2(0, maxPassengerLanes - 1);
1090 : #ifdef DEBUG_JOINJUNCTIONS
1091 : if (gDebugFlag1) {
1092 : std::cout << "check edge length " << edge->getID() << " (" << length << ", passed=" << passed.size() << ", max=" << longThreshold << ")\n";
1093 : }
1094 : #endif
1095 18559 : if (length > longThreshold) {
1096 : // we found an edge that should not be removed. Maybe we can
1097 : // still keep the start or end in the cluster
1098 : // (keep the start if the end can be removed and vice versa)
1099 49 : const bool keepStart = getClusterNeighbors(passed.back(), longThreshold, cluster).size() == 1;
1100 49 : const bool keepEnd = !keepStart && getClusterNeighbors(n, longThreshold, cluster).size() == 1;
1101 : #ifdef DEBUG_JOINJUNCTIONS
1102 : if (gDebugFlag1) {
1103 : std::cout << "node=" << n->getID() << " long edge " << edge->getID() << " (" << length << ", passed=" << toString(passed) << ", max=" << longThreshold << ") keepStart=" << keepStart << " keepEnd=" << keepEnd << "\n";
1104 : }
1105 : #endif
1106 49 : if (!keepStart) {
1107 : toRemove.insert(n);
1108 : }
1109 : toRemove.insert(passed.begin(), passed.end() - 1);
1110 49 : if (!keepEnd) {
1111 : toRemove.insert(passed.back());
1112 : }
1113 :
1114 : }
1115 : }
1116 : }
1117 2405 : if (!dryRun) {
1118 1257 : for (std::set<NBNode*>::iterator j = toRemove.begin(); j != toRemove.end(); ++j) {
1119 : cluster.erase(*j);
1120 : }
1121 : }
1122 2405 : return (int)toRemove.size();
1123 : }
1124 :
1125 :
1126 : NodeSet
1127 73 : NBNodeCont::getClusterNeighbors(const NBNode* n, double longThreshold, NodeSet& cluster) {
1128 : NodeSet result;
1129 479 : for (NBEdge* e : n->getEdges()) {
1130 406 : if (e->getLength() > longThreshold) {
1131 138 : continue;
1132 : }
1133 405 : NBNode* neighbor = e->getFromNode() == n ? e->getToNode() : e->getFromNode();
1134 : if (cluster.count(neighbor) != 0) {
1135 : result.insert(neighbor);
1136 : }
1137 : }
1138 73 : return result;
1139 : }
1140 :
1141 :
1142 : void
1143 1251 : NBNodeCont::pruneSlipLaneNodes(NodeSet& cluster, double maxDist) const {
1144 : #ifdef DEBUG_JOINJUNCTIONS
1145 : if (gDebugFlag1) {
1146 : std::cout << "pruning slip-lanes at cluster=" << joinNamedToString(cluster, ' ') << "\n";
1147 : }
1148 : #endif
1149 : // fringe has already been removed
1150 1251 : if (cluster.size() <= 2) {
1151 746 : return;
1152 : }
1153 : NodeSet toRemove;
1154 3278 : for (NBNode* n : cluster) {
1155 : EdgeVector outgoing;
1156 : double inAngle;
1157 : // find slip lanes where the start is part of the cluster
1158 2773 : if (maybeSlipLaneStart(n, outgoing, inAngle)) {
1159 : // potential slip lane start but we don't know which of the outgoing edges it is
1160 : #ifdef DEBUG_JOINJUNCTIONS
1161 : if (gDebugFlag1) {
1162 : std::cout << " candidate slip-lane start=" << n->getID() << " outgoing=" << toString(outgoing) << "\n";
1163 : }
1164 : #endif
1165 234 : for (NBEdge* contEdge : outgoing) {
1166 156 : if ((contEdge->getPermissions() & SVC_PASSENGER) == 0) {
1167 0 : continue;
1168 : }
1169 156 : double slipLength = contEdge->getLength();
1170 156 : NBNode* cont = contEdge->getToNode();
1171 : NodeSet cands;
1172 : cands.insert(n);
1173 305 : while (isSlipLaneContinuation(cont) && slipLength < MAX_SLIPLANE_LENGTH) {
1174 : if (cands.count(cont) != 0) {
1175 : break; // circle, should not happen
1176 : }
1177 : cands.insert(cont);
1178 : #ifdef DEBUG_JOINJUNCTIONS
1179 : if (gDebugFlag1) {
1180 : std::cout << " candidate slip-lane cont=" << cont->getID() << "\n";
1181 : }
1182 : #endif
1183 149 : NBEdge* next = cont->getOutgoingEdges().front();
1184 149 : slipLength += next->getLength();
1185 149 : cont = next->getToNode();
1186 : }
1187 : #ifdef DEBUG_JOINJUNCTIONS
1188 : if (gDebugFlag1) {
1189 : std::cout << " candidate slip-lane end=" << cont->getID() << " slipLength=" << slipLength << "\n";
1190 : }
1191 : #endif
1192 193 : if (cont->getIncomingEdges().size() >= 2 && cont->getOutgoingEdges().size() == 1 &&
1193 : // slip lanes are for turning so there needs to be a sufficient angle
1194 37 : abs(NBHelpers::relAngle(inAngle, cont->getOutgoingEdges().front()->getAngleAtNode(cont))) > 45) {
1195 : // check whether the other continuation at n is also connected to the sliplane end
1196 30 : const NBEdge* const otherEdge = (contEdge == outgoing.front() ? outgoing.back() : outgoing.front());
1197 : NodeSet visited;
1198 : visited.insert(n);
1199 : std::vector<NodeAndDist> toProc;
1200 30 : toProc.push_back(std::make_pair(otherEdge->getToNode(), otherEdge->getLength()));
1201 : bool found = false;
1202 135 : while (!toProc.empty()) {
1203 128 : NodeAndDist nodeAndDist = toProc.back();
1204 128 : NBNode* cont2 = nodeAndDist.first;
1205 : double dist = nodeAndDist.second;
1206 : #ifdef DEBUG_JOINJUNCTIONS
1207 : if (gDebugFlag1) {
1208 : std::cout << " search alternative cont2=" << cont2->getID() << " dist=" << dist << "\n";
1209 : }
1210 : #endif
1211 : toProc.pop_back();
1212 128 : if (visited.find(cont2) != visited.end()) {
1213 10 : continue;
1214 : }
1215 : visited.insert(cont2);
1216 118 : if (cont2 == cont) {
1217 : found = true;
1218 23 : break;
1219 : }
1220 228 : for (NBEdge* e : cont2->getOutgoingEdges()) {
1221 133 : const double dist2 = dist + e->getLength();
1222 133 : if (dist2 < slipLength * 2 && (e->getPermissions() & SVC_PASSENGER) != 0) {
1223 117 : toProc.push_back(std::make_pair(e->getToNode(), dist2));
1224 : }
1225 : }
1226 : }
1227 : if (found) {
1228 : // found slip lane
1229 : cands.insert(cont);
1230 23 : toRemove.insert(cands.begin(), cands.end());
1231 : #ifdef DEBUG_JOINJUNCTIONS
1232 : if (gDebugFlag1) {
1233 : std::cout << " found slip-lane with nodes=" << joinNamedToString(cands, ' ') << "\n";
1234 : }
1235 : #endif
1236 : }
1237 : }
1238 : }
1239 : }
1240 :
1241 : EdgeVector incoming;
1242 : double outAngle;
1243 : // find slip lanes where the end is part of the cluster
1244 2773 : if (maybeSlipLaneEnd(n, incoming, outAngle)) {
1245 : // potential slip lane end but we don't know which of the incoming edges it is
1246 : #ifdef DEBUG_JOINJUNCTIONS
1247 : if (gDebugFlag1) {
1248 : std::cout << " candidate slip-lane end=" << n->getID() << " incoming=" << toString(incoming) << "\n";
1249 : }
1250 : #endif
1251 312 : for (NBEdge* contEdge : incoming) {
1252 208 : if ((contEdge->getPermissions() & SVC_PASSENGER) == 0) {
1253 0 : continue;
1254 : }
1255 208 : double slipLength = contEdge->getLength();
1256 208 : NBNode* cont = contEdge->getFromNode();
1257 : NodeSet cands;
1258 : cands.insert(n);
1259 474 : while (isSlipLaneContinuation(cont) && slipLength < MAX_SLIPLANE_LENGTH) {
1260 : if (cands.count(cont) != 0) {
1261 : break; // circle, should not happen
1262 : }
1263 : cands.insert(cont);
1264 : #ifdef DEBUG_JOINJUNCTIONS
1265 : if (gDebugFlag1) {
1266 : std::cout << " candidate slip-lane cont=" << cont->getID() << "\n";
1267 : }
1268 : #endif
1269 266 : NBEdge* next = cont->getIncomingEdges().front();
1270 266 : slipLength += next->getLength();
1271 266 : cont = next->getFromNode();
1272 : }
1273 : #ifdef DEBUG_JOINJUNCTIONS
1274 : if (gDebugFlag1) {
1275 : std::cout << " candidate slip-lane start=" << cont->getID() << " slipLength=" << slipLength << "\n";
1276 : }
1277 : #endif
1278 268 : if (cont->getOutgoingEdges().size() >= 2 && cont->getIncomingEdges().size() == 1 &&
1279 : // slip lanes are for turning so there needs to be a sufficient angle
1280 60 : abs(NBHelpers::relAngle(outAngle, cont->getIncomingEdges().front()->getAngleAtNode(cont))) > 45) {
1281 : // check whether the other continuation at n is also connected to the sliplane end
1282 41 : const NBEdge* const otherEdge = (contEdge == incoming.front() ? incoming.back() : incoming.front());
1283 : NodeSet visited;
1284 : visited.insert(n);
1285 : std::vector<NodeAndDist> toProc;
1286 41 : toProc.push_back(std::make_pair(otherEdge->getFromNode(), otherEdge->getLength()));
1287 : bool found = false;
1288 446 : while (!toProc.empty()) {
1289 428 : NodeAndDist nodeAndDist = toProc.back();
1290 428 : NBNode* cont2 = nodeAndDist.first;
1291 : double dist = nodeAndDist.second;
1292 : #ifdef DEBUG_JOINJUNCTIONS
1293 : if (gDebugFlag1) {
1294 : std::cout << " search alternative cont2=" << cont2->getID() << " dist=" << dist << "\n";
1295 : }
1296 : #endif
1297 : toProc.pop_back();
1298 428 : if (visited.find(cont2) != visited.end()) {
1299 73 : continue;
1300 : }
1301 : visited.insert(cont2);
1302 355 : if (cont2 == cont) {
1303 : found = true;
1304 23 : break;
1305 : }
1306 855 : for (NBEdge* e : cont2->getIncomingEdges()) {
1307 523 : const double dist2 = dist + e->getLength();
1308 523 : if (dist2 < slipLength * 2 && (e->getPermissions() & SVC_PASSENGER) != 0) {
1309 406 : toProc.push_back(std::make_pair(e->getFromNode(), dist2));
1310 : }
1311 : }
1312 : }
1313 : if (found) {
1314 : // found slip lane
1315 : cands.insert(cont);
1316 23 : toRemove.insert(cands.begin(), cands.end());
1317 : #ifdef DEBUG_JOINJUNCTIONS
1318 : if (gDebugFlag1) {
1319 : std::cout << " found slip-lane start with nodes=" << joinNamedToString(cands, ' ') << "\n";
1320 : }
1321 : #endif
1322 : }
1323 : }
1324 : }
1325 : }
1326 :
1327 :
1328 :
1329 : }
1330 : int numRemoved = 0;
1331 599 : for (NBNode* n : toRemove) {
1332 94 : numRemoved += (int)cluster.erase(n);
1333 : }
1334 505 : if (numRemoved > 0) {
1335 : #ifdef DEBUG_JOINJUNCTIONS
1336 : if (gDebugFlag1) {
1337 : std::cout << " removed " << numRemoved << " nodes from cluster: " << joinNamedToString(toRemove, ' ') << "\n";
1338 : }
1339 : #endif
1340 19 : pruneClusterFringe(cluster, maxDist);
1341 : }
1342 : }
1343 :
1344 :
1345 : bool
1346 779 : NBNodeCont::isSlipLaneContinuation(const NBNode* cont) {
1347 1984 : return cont->getPassengerEdges(true).size() == 1 && cont->getPassengerEdges(false).size() == 1;
1348 : }
1349 :
1350 :
1351 : bool
1352 2773 : NBNodeCont::maybeSlipLaneStart(const NBNode* n, EdgeVector& outgoing, double& inAngle) const {
1353 2773 : EdgeVector inPE = n->getPassengerEdges(true);
1354 2773 : EdgeVector outPE = n->getPassengerEdges(false);
1355 2773 : if (inPE.size() == 1 && outPE.size() == 2) {
1356 72 : outgoing.insert(outgoing.begin(), outPE.begin(), outPE.end());
1357 72 : inAngle = inPE.front()->getAngleAtNode(n);
1358 72 : return true;
1359 2701 : } else if (inPE.size() >= 2 && outPE.size() == 3) {
1360 : // check if the incoming edges are going in opposite directions and then
1361 : // use the incoming edge that has 2 almost-straight outgoing edges
1362 239 : const double inRelAngle = fabs(NBHelpers::relAngle(inPE.front()->getAngleAtNode(n), inPE.back()->getAngleAtNode(n)));
1363 : //std::cout << "n=" << n->getID() << " inRelAngle=" << inRelAngle << "\n";
1364 239 : if (inRelAngle < 135) {
1365 : return false; // not opposite incoming
1366 : }
1367 450 : for (NBEdge* in : inPE) {
1368 : EdgeVector straight;
1369 : int numReverse = 0;
1370 1344 : for (NBEdge* out : outPE) {
1371 1008 : const double outRelAngle = fabs(NBHelpers::relAngle(in->getAngleAtNode(n), out->getAngleAtNode(n)));
1372 1008 : if (outRelAngle <= 45) {
1373 314 : straight.push_back(out);
1374 694 : } else if (outRelAngle >= 135) {
1375 273 : numReverse++;
1376 : }
1377 : }
1378 336 : if (straight.size() == 2 && numReverse == 1) {
1379 6 : outgoing.insert(outgoing.begin(), straight.begin(), straight.end());
1380 6 : inAngle = in->getAngleAtNode(n);
1381 : return true;
1382 : }
1383 : }
1384 : }
1385 : return false;
1386 : }
1387 :
1388 :
1389 : bool
1390 2773 : NBNodeCont::maybeSlipLaneEnd(const NBNode* n, EdgeVector& incoming, double& outAngle) const {
1391 2773 : EdgeVector inPE = n->getPassengerEdges(true);
1392 2773 : EdgeVector outPE = n->getPassengerEdges(false);
1393 2773 : if (inPE.size() == 2 && outPE.size() == 1) {
1394 99 : incoming.insert(incoming.begin(), inPE.begin(), inPE.end());
1395 99 : outAngle = outPE.front()->getAngleAtNode(n);
1396 99 : return true;
1397 2674 : } else if (inPE.size() == 3 && outPE.size() >= 2) {
1398 : // check if the outgoing edges are going in opposite directions and then
1399 : // use the outgoing edge that has 2 almost-straight incoming edges
1400 252 : const double outRelAngle = fabs(NBHelpers::relAngle(outPE.front()->getAngleAtNode(n), outPE.back()->getAngleAtNode(n)));
1401 : //std::cout << "n=" << n->getID() << " outRelAngle=" << outRelAngle << "\n";
1402 252 : if (outRelAngle < 135) {
1403 : return false; // not opposite outgoing
1404 : }
1405 566 : for (NBEdge* out : outPE) {
1406 : EdgeVector straight;
1407 : int numReverse = 0;
1408 1684 : for (NBEdge* in : inPE) {
1409 1263 : const double inRelAngle = fabs(NBHelpers::relAngle(in->getAngleAtNode(n), out->getAngleAtNode(n)));
1410 1263 : if (inRelAngle <= 45) {
1411 396 : straight.push_back(in);
1412 867 : } else if (inRelAngle >= 135) {
1413 336 : numReverse++;
1414 : }
1415 : }
1416 421 : if (straight.size() == 2 && numReverse == 1) {
1417 5 : incoming.insert(incoming.begin(), straight.begin(), straight.end());
1418 5 : outAngle = out->getAngleAtNode(n);
1419 : return true;
1420 : }
1421 : }
1422 : }
1423 : return false;
1424 : }
1425 :
1426 : bool
1427 2517 : NBNodeCont::feasibleCluster(const NodeSet& cluster, const std::map<const NBNode*, std::vector<NBNode*> >& ptStopEnds,
1428 : double maxDist, std::string& reason) const {
1429 : // check for clusters which are to complex and probably won't work very well
1430 : // we count the incoming edges of the final junction
1431 : std::map<NBEdge*, double, ComparatorIdLess> finalIncomingAngles;
1432 : std::map<NBEdge*, double, ComparatorIdLess> finalOutgoingAngles;
1433 10765 : for (NBNode* n : cluster) {
1434 27622 : for (EdgeVector::const_iterator it_edge = n->getIncomingEdges().begin(); it_edge != n->getIncomingEdges().end(); ++it_edge) {
1435 19374 : NBEdge* edge = *it_edge;
1436 28389 : if (cluster.count(edge->getFromNode()) == 0 && (edge->getPermissions() & SVC_PASSENGER) != 0) {
1437 : // incoming edge, does not originate in the cluster
1438 5195 : finalIncomingAngles[edge] = edge->getAngleAtNode(edge->getToNode());
1439 : }
1440 : }
1441 27486 : for (EdgeVector::const_iterator it_edge = n->getOutgoingEdges().begin(); it_edge != n->getOutgoingEdges().end(); ++it_edge) {
1442 19238 : NBEdge* edge = *it_edge;
1443 28253 : if (cluster.count(edge->getToNode()) == 0 && (edge->getPermissions() & SVC_PASSENGER) != 0) {
1444 : // outgoing edge, does not end in the cluster
1445 5207 : finalOutgoingAngles[edge] = edge->getAngleAtNode(edge->getFromNode());
1446 : }
1447 : }
1448 :
1449 : }
1450 : #ifdef DEBUG_JOINJUNCTIONS
1451 : for (NBNode* n : cluster) {
1452 : if (DEBUGCOND(n)) {
1453 : std::cout << "feasibleCluster c=" << joinNamedToString(cluster, ',')
1454 : << "\n inAngles=" << joinNamedToString(finalIncomingAngles, ' ', ':')
1455 : << "\n outAngles=" << joinNamedToString(finalOutgoingAngles, ' ', ':')
1456 : << "\n";
1457 : }
1458 : }
1459 : #endif
1460 2517 : if (finalIncomingAngles.size() > 5) {
1461 6 : reason = toString(finalIncomingAngles.size()) + " incoming edges";
1462 3 : return false;
1463 : }
1464 : // check for incoming parallel edges
1465 : const double PARALLEL_THRESHOLD_SAME_NODE = 10;
1466 : const double PARALLEL_THRESHOLD_DIFF_NODE = 30;
1467 : bool foundParallel = false;
1468 7569 : for (auto j = finalIncomingAngles.begin(); j != finalIncomingAngles.end() && !foundParallel; ++j) {
1469 : auto k = j;
1470 10020 : for (++k; k != finalIncomingAngles.end() && !foundParallel; ++k) {
1471 4965 : const double angleDiff = fabs(j->second - k->second);
1472 4965 : if (angleDiff < PARALLEL_THRESHOLD_DIFF_NODE) {
1473 : // for edge targeting the same node, permit a narrower angle
1474 41 : const double edgeDist = j->first->getLaneShape(0).back().distanceTo2D(k->first->getLaneShape(0).back());
1475 : #ifdef DEBUG_JOINJUNCTIONS
1476 : if (DEBUGCOND(j->first->getToNode())) {
1477 : std::cout << " angleDiff=" << angleDiff << " shapeDist=" << edgeDist << "\n";
1478 : }
1479 : #endif
1480 41 : if (angleDiff >= PARALLEL_THRESHOLD_SAME_NODE && (
1481 21 : (j->first->getToNode() == k->first->getToNode()
1482 15 : || (edgeDist < maxDist)))) {
1483 8 : continue;
1484 : }
1485 66 : reason = "parallel incoming " + j->first->getID() + "," + k->first->getID();
1486 : return false;
1487 : }
1488 : }
1489 : }
1490 : // check for outgoing parallel edges
1491 7479 : for (auto j = finalOutgoingAngles.begin(); j != finalOutgoingAngles.end() && !foundParallel; ++j) {
1492 : auto k = j;
1493 9906 : for (++k; k != finalOutgoingAngles.end() && !foundParallel; ++k) {
1494 4908 : const double angleDiff = fabs(j->second - k->second);
1495 4908 : if (angleDiff < PARALLEL_THRESHOLD_DIFF_NODE) {
1496 : // for edge leaving the same node, permit a narrower angle
1497 27 : const double edgeDist = j->first->getLaneShape(0).front().distanceTo2D(k->first->getLaneShape(0).front());
1498 : #ifdef DEBUG_JOINJUNCTIONS
1499 : if (DEBUGCOND(j->first->getFromNode())) {
1500 : std::cout << " angleDiff=" << angleDiff << " shapeDist=" << edgeDist << "\n";
1501 : }
1502 : #endif
1503 27 : if (angleDiff >= PARALLEL_THRESHOLD_SAME_NODE && (
1504 22 : (j->first->getFromNode() == k->first->getFromNode()
1505 18 : || (edgeDist < maxDist)))) {
1506 4 : continue;
1507 : }
1508 46 : reason = "parallel outgoing " + j->first->getID() + "," + k->first->getID();
1509 : return false;
1510 : }
1511 : }
1512 : }
1513 : // check for stop edges and tls within the cluster
1514 : bool hasTLS = false;
1515 10513 : for (NBNode* n : cluster) {
1516 8067 : if (n->isTLControlled()) {
1517 : hasTLS = true;
1518 : }
1519 : const auto& stopEnds = ptStopEnds.find(n);
1520 8067 : if (stopEnds != ptStopEnds.end()) {
1521 988 : for (NBNode* const to : stopEnds->second) {
1522 : if (cluster.count(to) != 0) {
1523 : reason = "it contains a pt stop edge";
1524 12 : return false;
1525 : }
1526 : }
1527 : }
1528 : }
1529 : // prevent removal of long edges unless there is weak circle or a traffic light
1530 2446 : if (cluster.size() > 2) {
1531 : // find the nodes with the biggests physical distance between them
1532 932 : double maxLength = -1;
1533 : NBEdge* maxEdge = nullptr;
1534 5911 : for (NBNode* n1 : cluster) {
1535 41482 : for (NBNode* n2 : cluster) {
1536 36503 : NBEdge* e1 = n1->getConnectionTo(n2);
1537 36503 : NBEdge* e2 = n2->getConnectionTo(n1);
1538 42665 : if (e1 != nullptr && e1->getLoadedLength() > maxLength) {
1539 1136 : maxLength = e1->getLoadedLength();
1540 : maxEdge = e1;
1541 : }
1542 42665 : if (e2 != nullptr && e2->getLoadedLength() > maxLength) {
1543 888 : maxLength = e2->getLoadedLength();
1544 : maxEdge = e2;
1545 : }
1546 : }
1547 : }
1548 : #ifdef DEBUG_JOINJUNCTIONS
1549 : for (NBNode* n : cluster) {
1550 : if (DEBUGCOND(n)) {
1551 : std::cout << "feasible hasTLS=" << hasTLS << " maxLength=" << maxLength << " maxEdge=" << maxEdge->getID() << "\n";
1552 : }
1553 : }
1554 : #endif
1555 932 : if (!hasTLS && maxLength > 5) {
1556 : // find a weak circle within cluster that does not use maxEdge
1557 : std::vector<NBNode*> toCheck;
1558 : std::set<NBNode*> visited;
1559 72 : toCheck.push_back(maxEdge->getToNode());
1560 : bool foundCircle = false;
1561 200 : while (!toCheck.empty()) {
1562 178 : NBNode* n = toCheck.back();
1563 178 : if (n == maxEdge->getFromNode()) {
1564 : foundCircle = true;
1565 50 : break;
1566 : }
1567 : toCheck.pop_back();
1568 : visited.insert(n);
1569 678 : for (NBEdge* e : n->getEdges()) {
1570 550 : if (e != maxEdge) {
1571 768 : NBNode* cand = e->getFromNode() == n ? e->getToNode() : e->getFromNode();
1572 : if (visited.count(cand) == 0 && cluster.count(cand) != 0) {
1573 200 : toCheck.push_back(cand);
1574 : }
1575 : }
1576 : }
1577 : }
1578 : if (!foundCircle) {
1579 44 : reason = "not compact (maxEdge=" + maxEdge->getID() + " length=" + toString(maxLength) + ")";
1580 : return false;
1581 : }
1582 : }
1583 : }
1584 : // prevent joining of simple merging/spreading structures
1585 2424 : if (!hasTLS && cluster.size() >= 2) {
1586 : int entryNodes = 0;
1587 : int exitNodes = 0;
1588 : int outsideIncoming = 0;
1589 : int outsideOutgoing = 0;
1590 : int edgesWithin = 0;
1591 5979 : for (NBNode* n : cluster) {
1592 : bool foundOutsideIncoming = false;
1593 14793 : for (NBEdge* e : n->getIncomingEdges()) {
1594 10560 : if (cluster.count(e->getFromNode()) == 0) {
1595 : // edge entering from outside the cluster
1596 6366 : outsideIncoming++;
1597 : foundOutsideIncoming = true;
1598 : } else {
1599 4194 : edgesWithin++;
1600 : }
1601 : }
1602 4233 : if (foundOutsideIncoming) {
1603 3929 : entryNodes++;
1604 : }
1605 : bool foundOutsideOutgoing = false;
1606 14837 : for (NBEdge* e : n->getOutgoingEdges()) {
1607 10604 : if (cluster.count(e->getToNode()) == 0) {
1608 : // edge leaving cluster
1609 6410 : outsideOutgoing++;
1610 : foundOutsideOutgoing = true;
1611 : }
1612 : }
1613 4233 : if (foundOutsideOutgoing) {
1614 3903 : exitNodes++;
1615 : }
1616 : }
1617 1746 : if (entryNodes < 2) {
1618 : reason = "only 1 entry node";
1619 : return false;
1620 : }
1621 1742 : if (exitNodes < 2) {
1622 : reason = "only 1 exit node";
1623 : return false;
1624 : }
1625 1706 : if (cluster.size() == 2) {
1626 1318 : if (edgesWithin == 1 && outsideIncoming < 3 && outsideOutgoing < 3) {
1627 : reason = "only 1 edge within and no cross-traffic";
1628 : return false;
1629 : }
1630 : }
1631 : }
1632 : return true;
1633 : }
1634 :
1635 :
1636 : bool
1637 1203 : NBNodeCont::reduceToCircle(NodeSet& cluster, int circleSize, NodeSet startNodes, double maxDist, std::vector<NBNode*> cands) const {
1638 : //std::cout << "reduceToCircle cs=" << circleSize << " cands=" << toString(cands, ',') << " startNodes=" << joinNamedToString(startNodes, ',') << "\n";
1639 : assert(circleSize >= 2);
1640 1203 : if ((int)cands.size() == circleSize) {
1641 222 : if (cands.back()->getConnectionTo(cands.front()) != nullptr) {
1642 : // cluster found
1643 : NodeSet candCluster;
1644 : candCluster.insert(cands.begin(), cands.end());
1645 32 : pruneClusterFringe(candCluster, maxDist);
1646 32 : const bool feasible = (int)candCluster.size() == circleSize;
1647 32 : if (feasible) {
1648 : cluster.clear();
1649 : cluster.insert(cands.begin(), cands.end());
1650 : }
1651 : return feasible;
1652 : } else {
1653 : return false;
1654 : }
1655 : }
1656 981 : if ((int)cluster.size() <= circleSize || startNodes.size() == 0) {
1657 : // no reduction possible
1658 : //std::cout << " abort\n";
1659 : return false;
1660 : }
1661 850 : if (cands.size() == 0) {
1662 : // try to find a circle starting from another start node
1663 337 : NBEdge* e = shortestEdge(cluster, startNodes, cands);
1664 337 : if (e != nullptr) {
1665 297 : cands.push_back(e->getFromNode());
1666 297 : startNodes.erase(e->getFromNode());
1667 1188 : if (reduceToCircle(cluster, circleSize, startNodes, maxDist, cands)) {
1668 : return true;
1669 : } else {
1670 : // try another start node
1671 747 : return reduceToCircle(cluster, circleSize, startNodes, maxDist);
1672 : }
1673 : }
1674 : } else {
1675 : NodeSet singleStart;
1676 : singleStart.insert(cands.back());
1677 513 : NBEdge* e = shortestEdge(cluster, singleStart, cands);
1678 513 : if (e != nullptr) {
1679 455 : std::vector<NBNode*> cands2(cands);
1680 455 : cands2.push_back(e->getToNode());
1681 1820 : if (reduceToCircle(cluster, circleSize, startNodes, maxDist, cands2)) {
1682 : return true;
1683 : }
1684 : }
1685 : }
1686 : //std::cout << " abort2\n";
1687 : return false;
1688 : }
1689 :
1690 :
1691 : NBEdge*
1692 850 : NBNodeCont::shortestEdge(const NodeSet& cluster, const NodeSet& startNodes, const std::vector<NBNode*>& exclude) const {
1693 : double minDist = std::numeric_limits<double>::max();
1694 : NBEdge* result = nullptr;
1695 2644 : for (NBNode* n : startNodes) {
1696 5484 : for (NBEdge* e : n->getOutgoingEdges()) {
1697 3690 : NBNode* neigh = e->getToNode();
1698 3690 : if (cluster.count(neigh) != 0 && std::find(exclude.begin(), exclude.end(), neigh) == exclude.end()) {
1699 : const double dist = n->getPosition().distanceTo2D(neigh->getPosition());
1700 : //std::cout << " e=" << e->getID() << " dist=" << dist << " minD=" << minDist << "\n";
1701 2235 : if (dist < minDist) {
1702 : minDist = dist;
1703 : result = e;
1704 : }
1705 : }
1706 : }
1707 : }
1708 : //std::cout << "closestNeighbor startNodes=" << toString(startNodes) << " result=" << Named::getIDSecure(result) << "\n";
1709 850 : return result;
1710 : }
1711 :
1712 : void
1713 120 : NBNodeCont::joinNodeClusters(NodeClusters clusters,
1714 : NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc, bool resetConnections) {
1715 1317 : for (NodeSet cluster : clusters) {
1716 2394 : joinNodeCluster(cluster, dc, ec, tlc, nullptr, resetConnections);
1717 : }
1718 120 : }
1719 :
1720 :
1721 : void
1722 1206 : NBNodeCont::joinNodeCluster(NodeSet cluster, NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc, NBNode* predefined, bool resetConnections) {
1723 1206 : const bool origNames = OptionsCont::getOptions().getBool("output.original-names");
1724 : assert(cluster.size() > 1);
1725 1206 : std::string id = "cluster_";
1726 : Position pos;
1727 1206 : bool setTL = false;
1728 1206 : SumoXMLNodeType nodeType = SumoXMLNodeType::UNKNOWN;
1729 2412 : TrafficLightType type = SUMOXMLDefinitions::TrafficLightTypes.get(OptionsCont::getOptions().getString("tls.default-type"));
1730 : // collect edges
1731 : std::set<NBEdge*, ComparatorIdLess> allEdges;
1732 5170 : for (NBNode* n : cluster) {
1733 : const EdgeVector& edges = n->getEdges();
1734 : allEdges.insert(edges.begin(), edges.end());
1735 : }
1736 : // determine edges with are incoming or fully inside
1737 : std::set<NBEdge*, ComparatorIdLess> clusterIncoming;
1738 : std::set<NBEdge*, ComparatorIdLess> inside;
1739 15443 : for (NBEdge* e : allEdges) {
1740 14237 : if (cluster.count(e->getToNode()) > 0) {
1741 9286 : if (cluster.count(e->getFromNode()) > 0) {
1742 : inside.insert(e);
1743 4314 : if (e->getSignalPosition() != Position::INVALID) {
1744 67 : setTL = true;
1745 67 : nodeType = SumoXMLNodeType::TRAFFIC_LIGHT;
1746 : }
1747 : } else {
1748 : clusterIncoming.insert(e);
1749 : }
1750 : }
1751 : }
1752 : #ifdef DEBUG_JOINJUNCTIONS_CONNECTIONS
1753 : std::cout << "joining cluster " << joinNamedToString(cluster, ' ')
1754 : << " resetConnections=" << resetConnections << "\n"
1755 : << " incoming=" << joinNamedToString(clusterIncoming, ' ') << "\n"
1756 : << " inside=" << joinNamedToString(inside, ' ') << "\n";
1757 : #endif
1758 1206 : analyzeCluster(cluster, id, pos, setTL, type, nodeType);
1759 : NBNode* newNode = nullptr;
1760 1206 : if (predefined != nullptr) {
1761 : newNode = predefined;
1762 : } else {
1763 1197 : if (!insert(id, pos)) {
1764 : // should not fail
1765 0 : WRITE_WARNINGF(TL("Could not join junctions %."), id);
1766 : return;
1767 : }
1768 1197 : newNode = retrieve(id);
1769 : }
1770 : std::string tlID = id;
1771 1206 : if (predefined != nullptr) {
1772 9 : if (predefined->getType() != SumoXMLNodeType::UNKNOWN) {
1773 1 : nodeType = predefined->getType();
1774 : }
1775 9 : Position ppos = predefined->getPosition();
1776 9 : if (ppos.x() != Position::INVALID.x()) {
1777 : pos.setx(ppos.x());
1778 : }
1779 9 : if (ppos.y() != Position::INVALID.y()) {
1780 : pos.sety(ppos.y());
1781 : }
1782 9 : if (ppos.z() != Position::INVALID.z()) {
1783 : pos.setz(ppos.z());
1784 : }
1785 : }
1786 1206 : newNode->reinit(pos, nodeType);
1787 1206 : if (origNames) {
1788 1852 : newNode->setParameter(SUMO_PARAM_ORIGID, joinNamedToString(cluster, ' '));
1789 : }
1790 1206 : if (setTL && !newNode->isTLControlled()) {
1791 341 : NBTrafficLightDefinition* tlDef = new NBOwnTLDef(tlID, newNode, 0, type);
1792 341 : if (!tlc.insert(tlDef)) {
1793 : // actually, nothing should fail here
1794 0 : delete tlDef;
1795 0 : throw ProcessError(TLF("Could not allocate tls '%'.", id));
1796 : }
1797 : }
1798 :
1799 : // determine possible connectivity from outside edges
1800 : std::map<NBEdge*, EdgeSet> reachable;
1801 : std::map<std::pair<NBEdge*, NBEdge*>, SVCPermissions> conPermissions;
1802 : EdgeSet specialPermissions;
1803 6178 : for (NBEdge* const e : clusterIncoming) {
1804 : EdgeVector open;
1805 : EdgeSet seen;
1806 4972 : open.push_back(e);
1807 37826 : while (open.size() > 0) {
1808 32854 : NBEdge* const cur = open.back();
1809 32854 : const SVCPermissions pCur = conPermissions.count({e, cur}) == 0 ? cur->getPermissions() : conPermissions[ {e, cur}];
1810 : #ifdef DEBUG_JOINJUNCTIONS_CONNECTIONS
1811 : std::cout << "e=" << e->getID() << " cur=" << cur->getID() << " open=" << toString(open) << "\n";
1812 : std::cout << "e=" << e->getID() << " cur=" << cur->getID() << " open=" << toString(open) << "\n";
1813 : #endif
1814 : seen.insert(cur);
1815 : open.pop_back();
1816 32854 : if (cluster.count(cur->getToNode()) == 0) {
1817 : //std::cout << " continue\n";
1818 14509 : continue;
1819 : }
1820 : const auto& cons = cur->getConnections();
1821 19460 : if (cons.size() == 0 || ec.hasPostProcessConnection(cur->getID()) || cur->getStep() == NBEdge::EdgeBuildingStep::INIT) {
1822 : // check permissions to determine reachability
1823 62543 : for (NBEdge* out : cur->getToNode()->getOutgoingEdges()) {
1824 : if (allEdges.count(out) != 0) {
1825 45270 : const SVCPermissions p = pCur & out->getPermissions();
1826 10301 : if (seen.count(out) == 0 || (~conPermissions[ {e, out}] & p) != 0) {
1827 35038 : if ((p & ~SVC_PEDESTRIAN) != 0) {
1828 25923 : open.push_back(out);
1829 25923 : conPermissions[ {e, out}] |= p;
1830 : #ifdef DEBUG_JOINJUNCTIONS_CONNECTIONS
1831 : std::cout << " e=" << e->getID() << " out=" << out->getID() << " pOut=" << getVehicleClassNames(out->getPermissions()) << "\n p=" << getVehicleClassNames(p) << "\n q=" << getVehicleClassNames(conPermissions[ {e, out}]) << "\n";
1832 : #endif
1833 : }
1834 : }
1835 : }
1836 : }
1837 : } else {
1838 : // check existing connections
1839 4405 : for (const auto& con : cons) {
1840 3333 : if (con.toEdge != nullptr && allEdges.count(con.toEdge) != 0) {
1841 3333 : SVCPermissions p = pCur & con.toEdge->getPermissions();
1842 3333 : if (con.permissions != SVC_UNSPECIFIED) {
1843 7 : p &= con.permissions;
1844 : }
1845 1374 : if (seen.count(con.toEdge) == 0 || (~conPermissions[ {e, con.toEdge}] & p) != 0) {
1846 1959 : open.push_back(con.toEdge);
1847 1959 : conPermissions[ {e, con.toEdge}] |= p;
1848 : //std::cout << " e=" << e->getID() << " con.toEdge=" << con.toEdge->getID() << " pSpecial=" << toString(con.permissions) << " pOut=" << getVehicleClassNames(con.toEdge->getPermissions()) << "\n p=" << getVehicleClassNames(p) << "\n q=" << getVehicleClassNames(conPermissions[{e, con.toEdge}]) << "\n";
1849 : }
1850 : }
1851 : }
1852 : }
1853 : }
1854 : seen.erase(e);
1855 28595 : for (NBEdge* reached : seen) {
1856 : // filter out inside edges from reached
1857 : if (inside.count(reached) == 0) {
1858 11791 : if (e->getStep() > NBEdge::EdgeBuildingStep::INIT && reached->getFromNode() == e->getToNode() && !e->isConnectedTo(reached)) {
1859 : // also filter out edges that are outgoing of the to-node of edge but aren't currently connected
1860 14 : continue;
1861 : }
1862 11777 : reachable[e].insert(reached);
1863 11777 : const SVCPermissions pDefault = e->getPermissions() & reached->getPermissions();
1864 11777 : if (conPermissions[ {e, reached}] != pDefault) {
1865 : specialPermissions.insert(e);
1866 : #ifdef DEBUG_JOINJUNCTIONS_CONNECTIONS
1867 : std::cout << "e=" << e->getID() << " out=" << reached->getID() << " special=" << getVehicleClassNames(conPermissions[ {e, reached}]) << "\n";
1868 : #endif
1869 : }
1870 : }
1871 : }
1872 : #ifdef DEBUG_JOINJUNCTIONS_CONNECTIONS
1873 : std::cout << " reachable e=" << e->getID() << " seen=" << toString(seen) << " reachable=" << toString(reachable[e]) << "\n";
1874 : #endif
1875 : }
1876 :
1877 : // remap and remove edges which are completely within the new intersection
1878 1206 : if (origNames) {
1879 2542 : newNode->setParameter("origEdgeIds", joinNamedToString(inside, ' '));
1880 : }
1881 5520 : for (NBEdge* e : inside) {
1882 76692 : for (NBEdge* e2 : allEdges) {
1883 72378 : if (e != e2) {
1884 68064 : e2->replaceInConnections(e, e->getConnections());
1885 : }
1886 : }
1887 4314 : ec.extract(dc, e, true);
1888 : allEdges.erase(e);
1889 : }
1890 :
1891 : // remap edges which are incoming / outgoing
1892 11129 : for (NBEdge* e : allEdges) {
1893 9923 : const bool outgoing = cluster.count(e->getFromNode()) > 0;
1894 : NBNode* from = outgoing ? newNode : e->getFromNode();
1895 9923 : NBNode* to = outgoing ? e->getToNode() : newNode;
1896 9923 : if (origNames) {
1897 7807 : if (outgoing) {
1898 7796 : e->setParameter("origFrom", e->getFromNode()->getID());
1899 : } else {
1900 7818 : e->setParameter("origTo", e->getToNode()->getID());
1901 : }
1902 : }
1903 9923 : if (e->getTurnSignTarget() != "") {
1904 39789 : for (NBNode* n : cluster) {
1905 33211 : if (e->getTurnSignTarget() == n->getID()) {
1906 : e->setTurnSignTarget(to->getID());
1907 : break;
1908 : }
1909 : }
1910 : }
1911 9923 : e->reinitNodes(from, to);
1912 : // re-add connections which previously existed and may still valid.
1913 : // connections to removed edges will be ignored
1914 9923 : std::vector<NBEdge::Connection> conns = e->getConnections();
1915 11553 : for (std::vector<NBEdge::Connection>::iterator k = conns.begin(); k != conns.end(); ++k) {
1916 1630 : if ((*k).toEdge == nullptr) {
1917 : // edge explicitly set to have no connections
1918 1 : continue;
1919 : }
1920 1629 : e->addLane2LaneConnection((*k).fromLane, (*k).toEdge, (*k).toLane, NBEdge::Lane2LaneInfoType::USER, false, (*k).mayDefinitelyPass);
1921 1629 : if ((*k).fromLane >= 0 && (*k).fromLane < e->getNumLanes() && e->getLaneStruct((*k).fromLane).connectionsDone) {
1922 : // @note (see NIImporter_DlrNavteq::ConnectedLanesHandler)
1923 : e->declareConnectionsAsLoaded(NBEdge::EdgeBuildingStep::INIT);
1924 : #ifdef DEBUG_JOINJUNCTIONS_CONNECTIONS
1925 : std::cout << " e=" << e->getID() << " declareConnectionsAsLoaded\n";
1926 : #endif
1927 : }
1928 : }
1929 9923 : }
1930 1206 : if (!resetConnections) {
1931 : // disable connections that were impossible with the old topology
1932 : // if connectivity has special permissions, set edge to edge connections explicitly
1933 6111 : for (NBEdge* in : newNode->getIncomingEdges()) {
1934 28600 : for (NBEdge* out : newNode->getOutgoingEdges()) {
1935 23676 : if (reachable[in].count(out) == 0) {
1936 11953 : if (!ec.hasPostProcessConnection(in->getID(), out->getID())) {
1937 : //std::cout << " removeUnreachable in=" << in->getID() << " out=" << out->getID() << "\n";
1938 11953 : in->removeFromConnections(out, -1, -1, true, false, true);
1939 : } else {
1940 : //std::cout << " hasPostProcessConnection in=" << in->getID() << " out=" << out->getID() << "\n";
1941 : }
1942 : } else if (specialPermissions.count(in) != 0) {
1943 649 : SVCPermissions pDefault = in->getPermissions() & out->getPermissions();
1944 649 : SVCPermissions p = conPermissions[ {in, out}] == 0 ? pDefault : conPermissions[ {in, out}];
1945 649 : in->addEdge2EdgeConnection(out, true, p == pDefault ? SVC_UNSPECIFIED : p);
1946 : //std::cout << " addEdge2Edge in=" << in->getID() << " out=" << out->getID() << "\n";
1947 : }
1948 : }
1949 : }
1950 : } else {
1951 67 : for (NBEdge* in : newNode->getIncomingEdges()) {
1952 48 : in->invalidateConnections(true);
1953 : }
1954 : }
1955 :
1956 : // remove original nodes
1957 1206 : registerJoinedCluster(cluster);
1958 5170 : for (NBNode* n : cluster) {
1959 3964 : erase(n);
1960 : }
1961 : }
1962 :
1963 :
1964 : void
1965 1206 : NBNodeCont::registerJoinedCluster(const NodeSet& cluster) {
1966 : std::set<std::string> ids;
1967 5170 : for (NBNode* n : cluster) {
1968 : ids.insert(n->getID());
1969 : }
1970 1206 : myJoinedClusters.push_back(ids);
1971 1206 : }
1972 :
1973 :
1974 : void
1975 1285 : NBNodeCont::analyzeCluster(NodeSet cluster, std::string& id, Position& pos,
1976 : bool& hasTLS, TrafficLightType& type, SumoXMLNodeType& nodeType) {
1977 2570 : id = createClusterId(cluster, id);
1978 : bool ambiguousType = false;
1979 5449 : for (NBNode* j : cluster) {
1980 : pos.add(j->getPosition());
1981 : // add a traffic light if any of the cluster members was controlled
1982 4164 : if (j->isTLControlled()) {
1983 1109 : if (!hasTLS) {
1984 : // init type
1985 358 : type = (*j->getControllingTLS().begin())->getType();
1986 751 : } else if (type != (*j->getControllingTLS().begin())->getType()) {
1987 : ambiguousType = true;
1988 : }
1989 1109 : hasTLS = true;
1990 : }
1991 4164 : SumoXMLNodeType otherType = j->getType();
1992 4164 : if (nodeType == SumoXMLNodeType::UNKNOWN) {
1993 2346 : nodeType = otherType;
1994 1818 : } else if (nodeType != otherType) {
1995 798 : if (hasTLS) {
1996 755 : nodeType = SumoXMLNodeType::TRAFFIC_LIGHT;
1997 43 : } else if (otherType != SumoXMLNodeType::UNKNOWN) {
1998 14 : if ((nodeType != SumoXMLNodeType::PRIORITY && (nodeType != SumoXMLNodeType::NOJUNCTION || otherType != SumoXMLNodeType::PRIORITY))
1999 12 : || (otherType != SumoXMLNodeType::NOJUNCTION && otherType != SumoXMLNodeType::UNKNOWN && otherType != SumoXMLNodeType::PRIORITY)) {
2000 30 : WRITE_WARNINGF("Ambiguous node type for node cluster '%' (%,%), setting to '" + toString(SumoXMLNodeType::PRIORITY) + "'.", id, toString(nodeType), toString(otherType));
2001 : }
2002 14 : nodeType = SumoXMLNodeType::PRIORITY;
2003 : }
2004 : }
2005 : }
2006 1285 : pos.mul(1. / (double)cluster.size());
2007 1285 : if (ambiguousType) {
2008 0 : type = SUMOXMLDefinitions::TrafficLightTypes.get(OptionsCont::getOptions().getString("tls.default-type"));
2009 0 : WRITE_WARNINGF(TL("Ambiguous traffic light type for node cluster '%', setting to '%'."), id, toString(type));
2010 : }
2011 1285 : }
2012 :
2013 :
2014 : // ----------- (Helper) methods for guessing/computing traffic lights
2015 : bool
2016 1067 : NBNodeCont::shouldBeTLSControlled(const NodeSet& c, double laneSpeedThreshold, bool recheck) const {
2017 : bool tooFast = false;
2018 : double laneSpeedSum = 0;
2019 : std::set<NBEdge*> seen;
2020 2299 : for (NBNode* j : c) {
2021 6695 : for (const NBEdge* e : j->getEdges()) {
2022 5463 : if (c.find(e->getFromNode()) != c.end() && c.find(e->getToNode()) != c.end()) {
2023 : // edges fully within the cluster do not count
2024 624 : continue;
2025 : }
2026 4839 : if (j->hasIncoming(e)) {
2027 2416 : if (recheck && !j->hasConflict(e)) {
2028 : // edges without conflict do not count
2029 : // we can only check this after connections have been computed
2030 2 : continue;
2031 : }
2032 2414 : laneSpeedSum += (double)e->getNumLanes() * e->getLaneSpeed(0);
2033 : }
2034 4837 : if (e->getLaneSpeed(0) * 3.6 > 79) {
2035 : tooFast = true;
2036 : }
2037 : }
2038 : }
2039 : //std::cout << " c=" << joinNamedToString(c, ' ') << " f=" << f << " size=" << c.size() << " thresh=" << laneSpeedThreshold << " tooFast=" << tooFast << "\n";
2040 2134 : return !tooFast && laneSpeedSum >= laneSpeedThreshold && c.size() != 0;
2041 : }
2042 :
2043 : bool
2044 91 : NBNodeCont::onlyCrossings(const NodeSet& c) const {
2045 : // check whether all component nodes are solely pedestrian crossings
2046 : // (these work fine without joining)
2047 172 : for (NBNode* node : c) {
2048 : EdgeVector nonPedIncoming;
2049 : EdgeVector nonPedOutgoing;
2050 654 : for (NBEdge* e : node->getIncomingEdges()) {
2051 492 : if (e->getPermissions() != SVC_PEDESTRIAN) {
2052 373 : nonPedIncoming.push_back(e);
2053 : }
2054 : }
2055 665 : for (NBEdge* e : node->getOutgoingEdges()) {
2056 503 : if (e->getPermissions() != SVC_PEDESTRIAN) {
2057 378 : nonPedOutgoing.push_back(e);
2058 : }
2059 : }
2060 162 : if (!node->geometryLike(nonPedIncoming, nonPedOutgoing)) {
2061 : //for (NBNode* node : c) {
2062 : // if (node->getID() == "2480337678") {
2063 : // std::cout << " node=" << node->getID() << " nonPedIncoming=" << toString(nonPedIncoming) << " nonPedOutgoing=" << toString(nonPedOutgoing) << "\n";
2064 : // }
2065 : //}
2066 : return false;
2067 : }
2068 : }
2069 : return true;
2070 : }
2071 :
2072 :
2073 : bool
2074 81 : NBNodeCont::customTLID(const NodeSet& c) const {
2075 281 : for (NBNode* node : c) {
2076 202 : if (node->isTLControlled()) {
2077 202 : NBTrafficLightDefinition* tl = (*node->getControllingTLS().begin());
2078 202 : if (tl->getNodes().size() > 1) {
2079 : // joined tls also imply a customID
2080 2 : return true;
2081 : }
2082 : const std::string tlID = tl->getID();
2083 200 : if (tlID != node->getID()
2084 202 : && !StringUtils::startsWith(tlID, "joinedS_")
2085 201 : && !StringUtils::startsWith(tlID, "joinedG_")
2086 204 : && !StringUtils::startsWith(tlID, "GS")) {
2087 : return true;
2088 : }
2089 : }
2090 : }
2091 : return false;
2092 : }
2093 :
2094 :
2095 : void
2096 1837 : NBNodeCont::guessTLs(OptionsCont& oc, NBTrafficLightLogicCont& tlc) {
2097 : myGuessedTLS.clear();
2098 : // build list of definitely not tls-controlled junctions
2099 1837 : const double laneSpeedThreshold = oc.getFloat("tls.guess.threshold");
2100 3674 : if (oc.isSet("tls.unset")) {
2101 2 : std::vector<std::string> notTLControlledNodes = oc.getStringVector("tls.unset");
2102 2 : for (std::vector<std::string>::const_iterator i = notTLControlledNodes.begin(); i != notTLControlledNodes.end(); ++i) {
2103 1 : NBNode* n = NBNodeCont::retrieve(*i);
2104 1 : if (n == nullptr) {
2105 0 : throw ProcessError(TLF(" The junction '%' to set as not-controlled is not known.", *i));
2106 : }
2107 : std::set<NBTrafficLightDefinition*> tls = n->getControllingTLS();
2108 1 : for (std::set<NBTrafficLightDefinition*>::const_iterator j = tls.begin(); j != tls.end(); ++j) {
2109 0 : (*j)->removeNode(n);
2110 : }
2111 1 : n->removeTrafficLights();
2112 : myUnsetTLS.insert(n);
2113 : }
2114 1 : }
2115 :
2116 3674 : TrafficLightType type = SUMOXMLDefinitions::TrafficLightTypes.get(OptionsCont::getOptions().getString("tls.default-type"));
2117 : // loop#1 checking whether the node shall be tls controlled,
2118 : // because it is assigned to a district
2119 5329 : if (oc.exists("tls.taz-nodes") && oc.getBool("tls.taz-nodes")) {
2120 0 : for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2121 0 : NBNode* cur = (*i).second;
2122 0 : if (cur->isNearDistrict() && myUnsetTLS.count(cur) == 0) {
2123 0 : setAsTLControlled(cur, tlc, type);
2124 : }
2125 : }
2126 : }
2127 :
2128 : // figure out which nodes mark the locations of TLS signals
2129 : // This assumes nodes are already joined
2130 7117 : if (oc.exists("tls.guess-signals") && oc.getBool("tls.guess-signals")) {
2131 : // prepare candidate edges
2132 98 : const double signalDist = oc.getFloat("tls.guess-signals.dist");
2133 22317 : for (const auto& item : myNodes) {
2134 22268 : const NBNode* node = item.second;
2135 22268 : if (node->isTLControlled() && (node->getIncomingEdges().size() == 1 || node->geometryLike())) {
2136 : #ifdef DEBUG_GUESSSIGNALS
2137 : if (DEBUGCOND(node) || true) {
2138 : std::cout << " propagate TLS from " << node->getID() << " downstream\n";
2139 : }
2140 : #endif
2141 249 : for (NBEdge* edge : node->getOutgoingEdges()) {
2142 : // do not overwrite closer signals
2143 161 : if (edge->getSignalOffset() == NBEdge::UNSPECIFIED_SIGNAL_OFFSET) {
2144 : edge->setSignalPosition(node->getPosition(), node);
2145 : }
2146 : }
2147 : }
2148 : }
2149 : std::set<NBEdge*> seen;
2150 : std::set<NBEdge*> check;
2151 22317 : for (const auto& item : myNodes) {
2152 59323 : for (NBEdge* edge : item.second->getOutgoingEdges()) {
2153 : if (edge->getSignalPosition() != Position::INVALID) {
2154 : check.insert(edge);
2155 : seen.insert(edge);
2156 : #ifdef DEBUG_GUESSSIGNALS
2157 : if (DEBUGCOND(edge->getSignalNode()) || true) {
2158 : std::cout << " primary signalPosition edge=" << edge->getID() << " pos=" << edge->getSignalPosition() << "\n";
2159 : }
2160 : #endif
2161 : }
2162 : }
2163 : }
2164 : // propagate signal position until the next real intersection
2165 1754 : while (check.size() > 0) {
2166 1705 : NBEdge* const edge = *check.begin();
2167 : check.erase(check.begin());
2168 : seen.insert(edge);
2169 1705 : NBNode* const nextNode = edge->getToNode();
2170 1705 : if (nextNode->geometryLike() && !nextNode->isTLControlled()) {
2171 734 : for (NBEdge* const outEdge : nextNode->getOutgoingEdges()) {
2172 : if (seen.count(outEdge) == 0) {
2173 143 : outEdge->setSignalPosition(edge->getSignalPosition(), edge->getSignalNode());
2174 : #ifdef DEBUG_GUESSSIGNALS
2175 : if (DEBUGCOND(edge->getSignalNode()) || true) {
2176 : std::cout << " setSignalPosition edge=" << outEdge->getID() << " pos=" << edge->getSignalPosition() << "\n";
2177 : }
2178 : #endif
2179 : check.insert(outEdge);
2180 : }
2181 : }
2182 : }
2183 : }
2184 :
2185 : // check which nodes should be controlled
2186 98 : const int slack = oc.getInt("tls.guess-signals.slack");
2187 22317 : for (std::map<std::string, NBNode*>::const_iterator i = myNodes.begin(); i != myNodes.end(); ++i) {
2188 22268 : NBNode* node = i->second;
2189 1 : if (myUnsetTLS.count(node) != 0) {
2190 : continue;
2191 : }
2192 : const EdgeVector& incoming = node->getIncomingEdges();
2193 : const EdgeVector& outgoing = node->getOutgoingEdges();
2194 21665 : if (!node->isTLControlled() && incoming.size() > 1 && !node->geometryLike()
2195 9587 : && !NBNodeTypeComputer::isRailwayNode(node)
2196 31426 : && node->getType() != SumoXMLNodeType::RAIL_CROSSING) {
2197 : std::vector<const NBNode*> signals;
2198 : int foundSignals = 0;
2199 : int missingSignals = 0;
2200 : // check if there is a signal at every incoming edge
2201 22002 : for (EdgeVector::const_iterator it_i = incoming.begin(); it_i != incoming.end(); ++it_i) {
2202 16855 : const NBEdge* inEdge = *it_i;
2203 16855 : if (inEdge->getSignalOffset() == NBEdge::UNSPECIFIED_SIGNAL_OFFSET) {
2204 16367 : if ((inEdge->getPermissions() & SVC_PASSENGER) != 0) {
2205 : #ifdef DEBUG_GUESSSIGNALS
2206 : if (DEBUGCOND(node)) {
2207 : std::cout << " noTLS, edge=" << inEdge->getID() << "\n";
2208 : }
2209 : #endif
2210 3777 : missingSignals++;
2211 3777 : if (missingSignals > slack) {
2212 : break;
2213 : }
2214 : }
2215 : } else {
2216 488 : foundSignals++;
2217 : }
2218 : }
2219 : missingSignals = 0;
2220 : int foundSignalsAtDist = 0;
2221 8920 : if (foundSignals > 1 && missingSignals <= slack && missingSignals < foundSignals) {
2222 77 : node->updateSurroundingGeometry();
2223 : // check if all signals are within the required distance
2224 : // (requires detailed geometry computation)
2225 315 : for (EdgeVector::const_iterator it_i = incoming.begin(); it_i != incoming.end(); ++it_i) {
2226 253 : const NBEdge* inEdge = *it_i;
2227 253 : if (inEdge->getSignalOffset() == NBEdge::UNSPECIFIED_SIGNAL_OFFSET || inEdge->getSignalOffset() > signalDist) {
2228 29 : if ((inEdge->getPermissions() & SVC_PASSENGER) != 0) {
2229 : #ifdef DEBUG_GUESSSIGNALS
2230 : if (DEBUGCOND(node)) {
2231 : std::cout << " noTLS, edge=" << inEdge->getID() << " offset=" << inEdge->getSignalOffset() << " tlsPos=" << inEdge->getSignalPosition() << "\n";
2232 : }
2233 : #endif
2234 15 : missingSignals++;
2235 15 : if (missingSignals > slack) {
2236 : break;
2237 : }
2238 : }
2239 : } else {
2240 224 : foundSignalsAtDist++;
2241 : }
2242 238 : const NBNode* signal = inEdge->getSignalNode();
2243 238 : if (signal != nullptr) {
2244 10 : signals.push_back(signal);
2245 : }
2246 : }
2247 : // outgoing edges may be tagged with pedestrian crossings. These
2248 : // should also be merged into the main TLS
2249 336 : for (const NBEdge* outEdge : outgoing) {
2250 259 : NBNode* cand = outEdge->getToNode();
2251 259 : if (cand->isTLControlled() && cand->geometryLike() && outEdge->getLength() <= signalDist) {
2252 : #ifdef DEBUG_GUESSSIGNALS
2253 : if (DEBUGCOND(node)) {
2254 : std::cout << " node=" << node->getID() << " outEdge=" << outEdge->getID() << " signalNode=" << cand->getID() << " len=" << outEdge->getLength() << "\n";
2255 : }
2256 : #endif
2257 1 : signals.push_back(cand);
2258 : }
2259 : }
2260 : }
2261 8920 : if (foundSignalsAtDist > 1 && missingSignals <= slack && missingSignals < foundSignalsAtDist) {
2262 73 : for (const NBNode* s : signals) {
2263 : std::set<NBTrafficLightDefinition*> tls = s->getControllingTLS();
2264 11 : const_cast<NBNode*>(s)->reinit(s->getPosition(), SumoXMLNodeType::PRIORITY);
2265 21 : for (std::set<NBTrafficLightDefinition*>::iterator k = tls.begin(); k != tls.end(); ++k) {
2266 20 : tlc.removeFully(s->getID());
2267 : }
2268 : }
2269 : //if (true) std::cout << " node=" << node->getID() << " signals=" << toString(signals) << "\n";
2270 62 : NBTrafficLightDefinition* tlDef = new NBOwnTLDef("GS_" + node->getID(), node, 0, type);
2271 : // @todo patch endOffset for all incoming lanes according to the signal positions
2272 62 : if (!tlc.insert(tlDef)) {
2273 : // actually, nothing should fail here
2274 0 : WRITE_WARNINGF(TL("Could not build joined tls '%'."), node->getID());
2275 0 : delete tlDef;
2276 : return;
2277 : }
2278 : }
2279 : }
2280 : }
2281 : }
2282 :
2283 : // guess joined tls first, if wished
2284 3674 : if (oc.getBool("tls.guess.joining")) {
2285 : // get node clusters
2286 : NodeClusters cands;
2287 8 : generateNodeClusters(oc.getFloat("tls.join-dist"), cands);
2288 : // check these candidates (clusters) whether they should be controlled by a tls
2289 38 : for (NodeClusters::iterator i = cands.begin(); i != cands.end();) {
2290 : NodeSet& c = (*i);
2291 : // regard only junctions which are not yet controlled and are not
2292 : // forbidden to be controlled
2293 245 : for (NodeSet::iterator j = c.begin(); j != c.end();) {
2294 211 : if ((*j)->isTLControlled() || myUnsetTLS.count(*j) != 0) {
2295 : c.erase(j++);
2296 : } else {
2297 : ++j;
2298 : }
2299 : }
2300 : // check whether the cluster should be controlled
2301 : // to avoid gigantic clusters, assume that at most 4 nodes should be needed for a guessed-joined-tls
2302 50 : if (c.size() == 0 || !shouldBeTLSControlled(c, laneSpeedThreshold * (double)c.size() / MIN2((double)c.size(), 4.))) {
2303 : i = cands.erase(i);
2304 : } else {
2305 : ++i;
2306 : }
2307 : }
2308 : // cands now only contain sets of junctions that shall be joined into being tls-controlled
2309 14 : for (auto nodeSet : cands) {
2310 : std::vector<NBNode*> nodes;
2311 53 : for (NBNode* node : nodeSet) {
2312 43 : nodes.push_back(node);
2313 : myGuessedTLS.insert(node);
2314 : }
2315 10 : const std::string& id = createClusterId(nodeSet, "joinedG_");
2316 10 : NBTrafficLightDefinition* tlDef = new NBOwnTLDef(id, nodes, 0, type);
2317 10 : if (!tlc.insert(tlDef)) {
2318 : // actually, nothing should fail here
2319 0 : WRITE_WARNING(TL("Could not build guessed, joined tls."));
2320 0 : delete tlDef;
2321 : return;
2322 : }
2323 : }
2324 4 : }
2325 :
2326 : // guess single tls
2327 3674 : if (oc.getBool("tls.guess")) {
2328 1002 : for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2329 981 : NBNode* cur = (*i).second;
2330 : // do nothing if already is tl-controlled
2331 981 : if (cur->isTLControlled()) {
2332 839 : continue;
2333 : }
2334 : // do nothing if in the list of explicit non-controlled junctions
2335 1 : if (myUnsetTLS.count(cur) != 0) {
2336 1 : continue;
2337 : }
2338 : NodeSet c;
2339 : c.insert(cur);
2340 907 : if (!shouldBeTLSControlled(c, laneSpeedThreshold) || cur->geometryLike()) {
2341 : continue;
2342 : }
2343 284 : setAsTLControlled(cur, tlc, type);
2344 : myGuessedTLS.insert(cur);
2345 : }
2346 : }
2347 : }
2348 :
2349 :
2350 : void
2351 1835 : NBNodeCont::recheckGuessedTLS(NBTrafficLightLogicCont& tlc) {
2352 : std::set<NBTrafficLightDefinition*> recompute;
2353 2020 : for (NBNode* node : myGuessedTLS) {
2354 185 : if (!node->hasConflict() || !recheckTLSThreshold(node)) {
2355 : const std::set<NBTrafficLightDefinition*>& tlDefs = node->getControllingTLS();
2356 21 : recompute.insert(tlDefs.begin(), tlDefs.end());
2357 21 : node->removeTrafficLights(true);
2358 49 : for (NBEdge* edge : node->getIncomingEdges()) {
2359 28 : edge->clearControllingTLInformation();
2360 : }
2361 : }
2362 : }
2363 1847 : for (NBTrafficLightDefinition* def : recompute) {
2364 12 : if (def->getNodes().size() == 0) {
2365 10 : tlc.removeFully(def->getID());
2366 : } else {
2367 7 : def->setParticipantsInformation();
2368 7 : def->setTLControllingInformation();
2369 7 : tlc.computeSingleLogic(OptionsCont::getOptions(), def);
2370 : }
2371 : }
2372 1835 : }
2373 :
2374 :
2375 : bool
2376 166 : NBNodeCont::recheckTLSThreshold(NBNode* node) {
2377 166 : if (!node->isTLControlled()) {
2378 : return false;
2379 : }
2380 166 : if ((*node->getControllingTLS().begin())->getNodes().size() != 1) {
2381 : // unable to perform check for a joined tls
2382 : return true;
2383 : }
2384 : NodeSet c;
2385 : c.insert(node);
2386 127 : const double laneSpeedThreshold = OptionsCont::getOptions().getFloat("tls.guess.threshold");
2387 127 : return shouldBeTLSControlled(c, laneSpeedThreshold, true);
2388 : }
2389 :
2390 :
2391 : void
2392 1835 : NBNodeCont::computeKeepClear() {
2393 73641 : for (const auto& item : myNodes) {
2394 71806 : item.second->computeKeepClear();
2395 : }
2396 1835 : }
2397 :
2398 :
2399 : void
2400 43 : NBNodeCont::joinTLS(NBTrafficLightLogicCont& tlc, double maxdist) {
2401 86 : const std::vector<std::string> excludeList = OptionsCont::getOptions().getStringVector("tls.join-exclude");
2402 45 : for (const std::string& tlsID : excludeList) {
2403 2 : if (!tlc.exist(tlsID, false)) {
2404 3 : WRITE_WARNINGF("Unknown tls ID '%' in option tls.join-exclude", tlsID);
2405 : }
2406 : }
2407 43 : std::set<std::string> exclude(excludeList.begin(), excludeList.end());
2408 : NodeClusters cands;
2409 43 : generateNodeClusters(maxdist, cands);
2410 1218 : for (NodeSet& c : cands) {
2411 4381 : for (NodeSet::iterator j = c.begin(); j != c.end();) {
2412 3206 : if (!(*j)->isTLControlled() || exclude.count((*(*j)->getControllingTLS().begin())->getID()) != 0) {
2413 : c.erase(j++);
2414 : } else {
2415 : ++j;
2416 : }
2417 : }
2418 1175 : if (c.size() < 2 || onlyCrossings(c) || customTLID(c)) {
2419 1096 : continue;
2420 : }
2421 : // figure out type of the joined TLS
2422 : Position dummyPos;
2423 79 : bool dummySetTL = false;
2424 79 : std::string id = "joinedS_"; // prefix (see #3871)
2425 : TrafficLightType type;
2426 79 : SumoXMLNodeType nodeType = SumoXMLNodeType::UNKNOWN;
2427 158 : analyzeCluster(c, id, dummyPos, dummySetTL, type, nodeType);
2428 279 : for (NBNode* j : c) {
2429 : std::set<NBTrafficLightDefinition*> tls = j->getControllingTLS();
2430 200 : j->removeTrafficLights();
2431 400 : for (NBTrafficLightDefinition* k : tls) {
2432 400 : tlc.removeFully(k->getID());
2433 : }
2434 : }
2435 : std::vector<NBNode*> nodes;
2436 279 : for (NBNode* j : c) {
2437 200 : nodes.push_back(j);
2438 : }
2439 79 : NBTrafficLightDefinition* tlDef = new NBOwnTLDef(id, nodes, 0, type);
2440 79 : if (!tlc.insert(tlDef)) {
2441 : // actually, nothing should fail here
2442 0 : WRITE_WARNING(TL("Could not build a joined tls."));
2443 0 : delete tlDef;
2444 : return;
2445 : }
2446 : }
2447 86 : }
2448 :
2449 :
2450 : void
2451 150 : NBNodeCont::setAsTLControlled(NBNode* node, NBTrafficLightLogicCont& tlc,
2452 : TrafficLightType type, std::string id) {
2453 150 : if (id == "") {
2454 : id = node->getID();
2455 : }
2456 150 : NBTrafficLightDefinition* tlDef = new NBOwnTLDef(id, node, 0, type);
2457 150 : if (!tlc.insert(tlDef)) {
2458 : // actually, nothing should fail here
2459 0 : WRITE_WARNINGF(TL("Building a tl-logic for junction '%' twice is not possible."), id);
2460 0 : delete tlDef;
2461 0 : return;
2462 : }
2463 : }
2464 :
2465 :
2466 : // -----------
2467 : void
2468 1837 : NBNodeCont::computeLanes2Lanes() {
2469 73651 : for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2470 71814 : (*i).second->computeLanes2Lanes();
2471 : }
2472 1837 : }
2473 :
2474 :
2475 : // computes the "wheel" of incoming and outgoing edges for every node
2476 : void
2477 1835 : NBNodeCont::computeLogics(const NBEdgeCont& ec) {
2478 73641 : for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2479 71806 : (*i).second->computeLogic(ec);
2480 : }
2481 1835 : }
2482 :
2483 :
2484 : void
2485 1835 : NBNodeCont::computeLogics2(const NBEdgeCont& ec, OptionsCont& oc) {
2486 : std::set<NBNode*> roundaboutNodes;
2487 1835 : const bool checkLaneFoesAll = oc.getBool("check-lane-foes.all");
2488 1835 : const bool checkLaneFoesRoundabout = !checkLaneFoesAll && oc.getBool("check-lane-foes.roundabout");
2489 1835 : if (checkLaneFoesRoundabout) {
2490 1830 : const std::set<EdgeSet>& roundabouts = ec.getRoundabouts();
2491 1928 : for (std::set<EdgeSet>::const_iterator i = roundabouts.begin(); i != roundabouts.end(); ++i) {
2492 568 : for (EdgeSet::const_iterator j = (*i).begin(); j != (*i).end(); ++j) {
2493 470 : roundaboutNodes.insert((*j)->getToNode());
2494 : }
2495 : }
2496 : }
2497 73641 : for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2498 71806 : const bool checkLaneFoes = checkLaneFoesAll || (checkLaneFoesRoundabout && roundaboutNodes.count((*i).second) > 0);
2499 71806 : (*i).second->computeLogic2(checkLaneFoes);
2500 : }
2501 1835 : }
2502 :
2503 :
2504 : void
2505 2337 : NBNodeCont::clear() {
2506 75196 : for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2507 72859 : delete ((*i).second);
2508 : }
2509 : myNodes.clear();
2510 14416 : for (auto& item : myExtractedNodes) {
2511 12079 : delete item.second;
2512 : }
2513 : myExtractedNodes.clear();
2514 2337 : }
2515 :
2516 :
2517 : std::string
2518 0 : NBNodeCont::getFreeID() {
2519 0 : int counter = 0;
2520 0 : std::string freeID = "SUMOGenerated" + toString<int>(counter);
2521 : // While there is a node with id equal to freeID
2522 0 : while (retrieve(freeID) != nullptr) {
2523 : // update counter and generate a new freeID
2524 0 : counter++;
2525 0 : freeID = "SUMOGenerated" + toString<int>(counter);
2526 : }
2527 0 : return freeID;
2528 : }
2529 :
2530 :
2531 : void
2532 1988 : NBNodeCont::computeNodeShapes(double mismatchThreshold) {
2533 110894 : for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2534 108906 : (*i).second->computeNodeShape(mismatchThreshold);
2535 : }
2536 1988 : }
2537 :
2538 :
2539 : void
2540 1833 : NBNodeCont::printBuiltNodesStatistics() const {
2541 1833 : WRITE_MESSAGE(TL("-----------------------------------------------------"));
2542 1833 : WRITE_MESSAGE(TL("Summary:"));
2543 :
2544 1833 : int numUnregulatedJunctions = 0;
2545 1833 : int numDeadEndJunctions = 0;
2546 1833 : int numTrafficLightJunctions = 0;
2547 1833 : int numPriorityJunctions = 0;
2548 1833 : int numRightBeforeLeftJunctions = 0;
2549 1833 : int numLeftBeforeRightJunctions = 0;
2550 1833 : int numAllWayStopJunctions = 0;
2551 1833 : int numZipperJunctions = 0;
2552 1833 : int numDistrictJunctions = 0;
2553 1833 : int numRailCrossing = 0;
2554 1833 : int numRailSignals = 0;
2555 73628 : for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2556 71795 : switch ((*i).second->getType()) {
2557 128 : case SumoXMLNodeType::NOJUNCTION:
2558 128 : ++numUnregulatedJunctions;
2559 128 : break;
2560 20296 : case SumoXMLNodeType::DEAD_END:
2561 20296 : ++numDeadEndJunctions;
2562 20296 : break;
2563 3121 : case SumoXMLNodeType::TRAFFIC_LIGHT:
2564 : case SumoXMLNodeType::TRAFFIC_LIGHT_RIGHT_ON_RED:
2565 : case SumoXMLNodeType::TRAFFIC_LIGHT_NOJUNCTION:
2566 3121 : ++numTrafficLightJunctions;
2567 3121 : break;
2568 41325 : case SumoXMLNodeType::PRIORITY:
2569 : case SumoXMLNodeType::PRIORITY_STOP:
2570 41325 : ++numPriorityJunctions;
2571 41325 : break;
2572 4981 : case SumoXMLNodeType::RIGHT_BEFORE_LEFT:
2573 4981 : ++numRightBeforeLeftJunctions;
2574 4981 : break;
2575 2 : case SumoXMLNodeType::LEFT_BEFORE_RIGHT:
2576 2 : ++numLeftBeforeRightJunctions;
2577 2 : break;
2578 1 : case SumoXMLNodeType::ALLWAY_STOP:
2579 1 : ++numAllWayStopJunctions;
2580 1 : break;
2581 13 : case SumoXMLNodeType::ZIPPER:
2582 13 : ++numZipperJunctions;
2583 13 : break;
2584 0 : case SumoXMLNodeType::DISTRICT:
2585 0 : ++numDistrictJunctions;
2586 0 : break;
2587 283 : case SumoXMLNodeType::RAIL_CROSSING:
2588 283 : ++numRailCrossing;
2589 283 : break;
2590 1645 : case SumoXMLNodeType::RAIL_SIGNAL:
2591 1645 : ++numRailSignals;
2592 1645 : break;
2593 : case SumoXMLNodeType::UNKNOWN:
2594 : // should not happen
2595 : break;
2596 : default:
2597 : break;
2598 : }
2599 : }
2600 1833 : WRITE_MESSAGE(TL(" Node type statistics:"));
2601 3666 : WRITE_MESSAGE(" Unregulated junctions : " + toString(numUnregulatedJunctions));
2602 1833 : if (numDeadEndJunctions > 0) {
2603 2442 : WRITE_MESSAGE(" Dead-end junctions : " + toString(numDeadEndJunctions));
2604 : }
2605 3666 : WRITE_MESSAGE(" Priority junctions : " + toString(numPriorityJunctions));
2606 3666 : WRITE_MESSAGE(" Right-before-left junctions : " + toString(numRightBeforeLeftJunctions));
2607 1833 : if (numLeftBeforeRightJunctions > 0) {
2608 4 : WRITE_MESSAGE(" Left-before-right junctions : " + toString(numLeftBeforeRightJunctions));
2609 : }
2610 1833 : if (numTrafficLightJunctions > 0) {
2611 1340 : WRITE_MESSAGE(" Traffic light junctions : " + toString(numTrafficLightJunctions));
2612 : }
2613 1833 : if (numAllWayStopJunctions > 0) {
2614 2 : WRITE_MESSAGE(" All-way stop junctions : " + toString(numAllWayStopJunctions));
2615 : }
2616 1833 : if (numZipperJunctions > 0) {
2617 20 : WRITE_MESSAGE(" Zipper-merge junctions : " + toString(numZipperJunctions));
2618 : }
2619 1833 : if (numRailCrossing > 0) {
2620 58 : WRITE_MESSAGE(" Rail crossing junctions : " + toString(numRailCrossing));
2621 : }
2622 1833 : if (numRailSignals > 0) {
2623 96 : WRITE_MESSAGE(" Rail signal junctions : " + toString(numRailSignals));
2624 : }
2625 1833 : if (numDistrictJunctions > 0) {
2626 0 : WRITE_MESSAGE(" District junctions : " + toString(numDistrictJunctions));
2627 : }
2628 : const GeoConvHelper& geoConvHelper = GeoConvHelper::getProcessing();
2629 1833 : WRITE_MESSAGE(TL(" Network boundaries:"));
2630 3666 : WRITE_MESSAGE(" Original boundary : " + toString(geoConvHelper.getOrigBoundary()));
2631 3666 : WRITE_MESSAGE(" Applied offset : " + toString(geoConvHelper.getOffsetBase()));
2632 3666 : WRITE_MESSAGE(" Converted boundary : " + toString(geoConvHelper.getConvBoundary()));
2633 1833 : WRITE_MESSAGE(TL("-----------------------------------------------------"));
2634 1833 : }
2635 :
2636 :
2637 : std::vector<std::string>
2638 53 : NBNodeCont::getAllNames() const {
2639 : std::vector<std::string> ret;
2640 16370 : for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); ++i) {
2641 16317 : ret.push_back((*i).first);
2642 : }
2643 53 : return ret;
2644 0 : }
2645 :
2646 :
2647 : void
2648 0 : NBNodeCont::addPrefix(const std::string& prefix) {
2649 : // make a copy of node containers
2650 : const auto nodeContainerCopy = myNodes;
2651 0 : myNodes.clear();
2652 0 : for (const auto& node : nodeContainerCopy) {
2653 0 : node.second->setID(prefix + node.second->getID());
2654 0 : myNodes[node.second->getID()] = node.second;
2655 : }
2656 0 : }
2657 :
2658 :
2659 : void
2660 74 : NBNodeCont::rename(NBNode* node, const std::string& newID) {
2661 : if (myNodes.count(newID) != 0) {
2662 0 : throw ProcessError(TLF("Attempt to rename node using existing id '%'", newID));
2663 : }
2664 : myNodes.erase(node->getID());
2665 74 : node->setID(newID);
2666 74 : myNodes[newID] = node;
2667 74 : }
2668 :
2669 :
2670 : void
2671 54 : NBNodeCont::discardTrafficLights(NBTrafficLightLogicCont& tlc, bool geometryLike, bool guessSignals) {
2672 33501 : for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); ++i) {
2673 33447 : NBNode* node = i->second;
2674 33447 : if (node->isTLControlled() && (!geometryLike || node->geometryLike())) {
2675 : // make a copy of tldefs
2676 : const std::set<NBTrafficLightDefinition*> tldefs = node->getControllingTLS();
2677 1473 : if (geometryLike && (*tldefs.begin())->getNodes().size() > 1) {
2678 : // do not remove joined tls when only removing geometry-like tls
2679 : continue;
2680 : }
2681 1472 : if (guessSignals && node->isTLControlled() && node->geometryLike()) {
2682 : // record signal location
2683 3470 : for (NBEdge* edge : node->getOutgoingEdges()) {
2684 : edge->setSignalPosition(node->getPosition(), nullptr);
2685 : #ifdef DEBUG_GUESSSIGNALS
2686 : std::cout << " discard-simple " << node->getID() << " edge=" << edge->getID() << " pos=" << edge->getSignalPosition() << "\n";
2687 : #endif
2688 : }
2689 : }
2690 2945 : for (std::set<NBTrafficLightDefinition*>::const_iterator it = tldefs.begin(); it != tldefs.end(); ++it) {
2691 1473 : NBTrafficLightDefinition* tlDef = *it;
2692 1473 : node->removeTrafficLight(tlDef);
2693 1473 : tlc.extract(tlDef);
2694 : }
2695 1472 : SumoXMLNodeType newType = NBNodeTypeComputer::isRailwayNode(node) ? SumoXMLNodeType::RAIL_SIGNAL : SumoXMLNodeType::UNKNOWN;
2696 1472 : node->reinit(node->getPosition(), newType);
2697 : }
2698 : }
2699 54 : }
2700 :
2701 :
2702 : void
2703 1 : NBNodeCont::discardRailSignals() {
2704 35 : for (auto& item : myNodes) {
2705 34 : NBNode* node = item.second;
2706 34 : if (node->getType() == SumoXMLNodeType::RAIL_SIGNAL) {
2707 5 : node->reinit(node->getPosition(), SumoXMLNodeType::PRIORITY);
2708 : }
2709 : }
2710 1 : }
2711 :
2712 :
2713 : int
2714 1837 : NBNodeCont::remapIDs(bool numericaIDs, bool reservedIDs, const std::string& prefix, NBTrafficLightLogicCont& tlc) {
2715 1837 : bool startGiven = !OptionsCont::getOptions().isDefault("numerical-ids.node-start");
2716 3638 : if (!numericaIDs && !reservedIDs && prefix == "" && !startGiven) {
2717 : return 0;
2718 : }
2719 : std::vector<std::string> avoid;
2720 46 : if (startGiven) {
2721 9 : avoid.push_back(toString(OptionsCont::getOptions().getInt("numerical-ids.node-start") - 1));
2722 : } else {
2723 43 : avoid = getAllNames();
2724 : }
2725 : std::set<std::string> reserve;
2726 46 : if (reservedIDs) {
2727 4 : NBHelpers::loadPrefixedIDsFomFile(OptionsCont::getOptions().getString("reserved-ids"), "node:", reserve); // backward compatibility
2728 4 : NBHelpers::loadPrefixedIDsFomFile(OptionsCont::getOptions().getString("reserved-ids"), "junction:", reserve); // selection format
2729 2 : avoid.insert(avoid.end(), reserve.begin(), reserve.end());
2730 : }
2731 92 : IDSupplier idSupplier("", avoid);
2732 : NodeSet toChange;
2733 15778 : for (NodeCont::iterator it = myNodes.begin(); it != myNodes.end(); it++) {
2734 15732 : if (startGiven) {
2735 36 : toChange.insert(it->second);
2736 36 : continue;
2737 : }
2738 15696 : if (numericaIDs) {
2739 : try {
2740 15626 : StringUtils::toLong(it->first);
2741 540 : } catch (NumberFormatException&) {
2742 540 : toChange.insert(it->second);
2743 540 : }
2744 : }
2745 15696 : if (reservedIDs && reserve.count(it->first) > 0) {
2746 2 : toChange.insert(it->second);
2747 : }
2748 : }
2749 92 : const bool origNames = OptionsCont::getOptions().getBool("output.original-names");
2750 624 : for (NBNode* node : toChange) {
2751 : myNodes.erase(node->getID());
2752 : }
2753 624 : for (NBNode* node : toChange) {
2754 2124 : if (origNames && node->getParameter(SUMO_PARAM_ORIGID) == "") {
2755 494 : node->setParameter(SUMO_PARAM_ORIGID, node->getID());
2756 : }
2757 1156 : node->setID(idSupplier.getNext());
2758 675 : for (NBTrafficLightDefinition* tlDef : node->getControllingTLS()) {
2759 97 : tlc.rename(tlDef, node->getID());
2760 : }
2761 578 : myNodes[node->getID()] = node;
2762 : }
2763 46 : if (prefix.empty()) {
2764 38 : return (int)toChange.size();
2765 : } else {
2766 : int renamed = 0;
2767 : // make a copy because we will modify the map
2768 : auto oldNodes = myNodes;
2769 83 : for (auto item : oldNodes) {
2770 150 : if (!StringUtils::startsWith(item.first, prefix)) {
2771 74 : rename(item.second, prefix + item.first);
2772 80 : for (NBTrafficLightDefinition* tlDef : item.second->getControllingTLS()) {
2773 12 : if (!StringUtils::startsWith(tlDef->getID(), prefix)) {
2774 8 : tlc.rename(tlDef, prefix + tlDef->getID());
2775 : }
2776 : }
2777 74 : renamed++;
2778 : }
2779 : }
2780 : return renamed;
2781 : }
2782 92 : }
2783 :
2784 :
2785 : int
2786 2 : NBNodeCont::guessFringe() {
2787 : // guess outer fringe by topology and being on the pareto-boundary
2788 : NodeSet topRightFront;
2789 : NodeSet topLeftFront;
2790 : NodeSet bottomRightFront;
2791 : NodeSet bottomLeftFront;
2792 67 : for (const auto& item : myNodes) {
2793 65 : paretoCheck(item.second, topRightFront, 1, 1);
2794 65 : paretoCheck(item.second, topLeftFront, -1, 1);
2795 65 : paretoCheck(item.second, bottomRightFront, 1, -1);
2796 65 : paretoCheck(item.second, bottomLeftFront, -1, -1);
2797 : }
2798 : NodeSet front;
2799 2 : front.insert(topRightFront.begin(), topRightFront.end());
2800 2 : front.insert(topLeftFront.begin(), topLeftFront.end());
2801 2 : front.insert(bottomRightFront.begin(), bottomRightFront.end());
2802 2 : front.insert(bottomLeftFront.begin(), bottomLeftFront.end());
2803 : int numFringe = 0;
2804 19 : for (NBNode* n : front) {
2805 17 : const int in = (int)n->getIncomingEdges().size();
2806 17 : const int out = (int)n->getOutgoingEdges().size();
2807 17 : if ((in <= 1 && out <= 1) &&
2808 12 : (in == 0 || out == 0
2809 8 : || n->getIncomingEdges().front()->isTurningDirectionAt(n->getOutgoingEdges().front()))) {
2810 : n->setFringeType(FringeType::OUTER);
2811 9 : numFringe++;
2812 : }
2813 : }
2814 : // guess outer fringe by topology and speed
2815 4 : const double speedThreshold = OptionsCont::getOptions().getFloat("fringe.guess.speed-threshold");
2816 67 : for (const auto& item : myNodes) {
2817 65 : NBNode* n = item.second;
2818 17 : if (front.count(n) != 0) {
2819 17 : continue;
2820 : }
2821 48 : if (n->getEdges().size() == 1 && n->getEdges().front()->getSpeed() > speedThreshold) {
2822 : n->setFringeType(FringeType::OUTER);
2823 2 : numFringe++;
2824 : }
2825 : }
2826 2 : return numFringe;
2827 : }
2828 :
2829 :
2830 : void
2831 260 : NBNodeCont::paretoCheck(NBNode* node, NodeSet& frontier, int xSign, int ySign) {
2832 260 : const double x = node->getPosition().x() * xSign;
2833 260 : const double y = node->getPosition().y() * ySign;
2834 : std::vector<NBNode*> dominated;
2835 556 : for (NBNode* fn : frontier) {
2836 484 : const double x2 = fn->getPosition().x() * xSign;
2837 484 : const double y2 = fn->getPosition().y() * ySign;
2838 484 : if (x2 >= x && y2 >= y) {
2839 188 : return;
2840 296 : } else if (x2 <= x && y2 <= y) {
2841 52 : dominated.push_back(fn);
2842 : }
2843 : }
2844 : frontier.insert(node);
2845 124 : for (NBNode* r : dominated) {
2846 : frontier.erase(r);
2847 : }
2848 : }
2849 :
2850 :
2851 : void
2852 1990 : NBNodeCont::applyConditionalDefaults() {
2853 83897 : for (const auto& item : myNodes) {
2854 81907 : NBNode* n = item.second;
2855 81907 : if (n->isTLControlled() && n->getRightOfWay() == RightOfWay::DEFAULT) {
2856 : bool hasNEMA = false;
2857 7288 : for (NBTrafficLightDefinition* tl : n->getControllingTLS()) {
2858 3657 : if (tl->getType() == TrafficLightType::NEMA) {
2859 : hasNEMA = true;
2860 : break;
2861 : }
2862 : }
2863 3643 : if (hasNEMA) {
2864 : // NEMA controller defaults to allway_stop behavior when switched off
2865 : n->setRightOfWay(RightOfWay::ALLWAYSTOP);
2866 : }
2867 : }
2868 : }
2869 1990 : }
2870 :
2871 :
2872 : bool
2873 1837 : NBNodeCont::resetNodeShapes() {
2874 : bool hadShapes = false;
2875 88650 : for (const auto& item : myNodes) {
2876 86813 : if (item.second->getShape().size() > 0 && !item.second->hasCustomShape()) {
2877 : hadShapes = true;
2878 : item.second->resetShape();
2879 : }
2880 : }
2881 1837 : return hadShapes;
2882 : }
2883 : /****************************************************************************/
|
