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