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