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