Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2026 German Aerospace Center (DLR) and others.
4 : // This program and the accompanying materials are made available under the
5 : // terms of the Eclipse Public License 2.0 which is available at
6 : // https://www.eclipse.org/legal/epl-2.0/
7 : // This Source Code may also be made available under the following Secondary
8 : // Licenses when the conditions for such availability set forth in the Eclipse
9 : // Public License 2.0 are satisfied: GNU General Public License, version 2
10 : // or later which is available at
11 : // https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
12 : // SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
13 : /****************************************************************************/
14 : /// @file NBNodeCont.cpp
15 : /// @author Daniel Krajzewicz
16 : /// @author Jakob Erdmann
17 : /// @author Yun-Pang Floetteroed
18 : /// @author Walter Bamberger
19 : /// @author Laura Bieker
20 : /// @author Michael Behrisch
21 : /// @author Sascha Krieg
22 : /// @date Tue, 20 Nov 2001
23 : ///
24 : // Container for nodes during the netbuilding process
25 : /****************************************************************************/
26 : #include <config.h>
27 :
28 : #include <string>
29 : #include <map>
30 : #include <algorithm>
31 : #include <cmath>
32 : #include <utils/options/OptionsCont.h>
33 : #include <utils/geom/Boundary.h>
34 : #include <utils/geom/GeomHelper.h>
35 : #include <utils/common/MsgHandler.h>
36 : #include <utils/common/UtilExceptions.h>
37 : #include <utils/common/StringTokenizer.h>
38 : #include <utils/common/StringUtils.h>
39 : #include <utils/common/StdDefs.h>
40 : #include <utils/common/ToString.h>
41 : #include <utils/common/StringUtils.h>
42 : #include <utils/common/IDSupplier.h>
43 : #include <utils/xml/SUMOXMLDefinitions.h>
44 : #include <utils/geom/GeoConvHelper.h>
45 : #include <utils/iodevices/OutputDevice.h>
46 : #include "NBHelpers.h"
47 : #include "NBAlgorithms.h"
48 : #include "NBDistrict.h"
49 : #include "NBEdgeCont.h"
50 : #include "NBTrafficLightLogicCont.h"
51 : #include "NBOwnTLDef.h"
52 : #include "NBPTStop.h"
53 : #include "NBNodeCont.h"
54 : #include "NBPTStopCont.h"
55 : #include "NBPTLineCont.h"
56 : #include "NBParking.h"
57 :
58 : // ===========================================================================
59 : // Algorithm constants
60 : // ===========================================================================
61 : #define MAX_SLIPLANE_LENGTH 1000
62 :
63 : // ===========================================================================
64 : // Debug Flags
65 : // ===========================================================================
66 :
67 : //#define DEBUG_JOINJUNCTIONS
68 : //#define DEBUG_REDUCE
69 : //#define DEBUG_JOINJUNCTIONS_CONNECTIONS
70 : //#define DEBUG_GUESSSIGNALS
71 : #define DEBUGNODEID ""
72 : #define DEBUGNODEID2 ""
73 : //#define DEBUGNODEID "5548037023"
74 : #define DEBUGCOND(obj) ((obj) != 0 && ((obj)->getID() == DEBUGNODEID || (obj)->getID() == DEBUGNODEID2))
75 : //#define DEBUGCOND(obj) (true)
76 :
77 :
78 : // ===========================================================================
79 : // method definitions
80 : // ===========================================================================
81 2483 : NBNodeCont::~NBNodeCont() {
82 2483 : clear();
83 4966 : }
84 :
85 :
86 : // ----------- Insertion/removal/retrieval of nodes
87 : bool
88 1504 : NBNodeCont::insert(const std::string& id, const Position& position,
89 : NBDistrict* district) {
90 : NodeCont::iterator i = myNodes.find(id);
91 1504 : if (i != myNodes.end()) {
92 : return false;
93 : }
94 1462 : NBNode* node = new NBNode(id, position, district);
95 1462 : myNodes[id] = node;
96 1462 : const float pos[2] = {(float)position.x(), (float)position.y()};
97 1462 : myRTree.Insert(pos, pos, node);
98 1462 : return true;
99 : }
100 :
101 :
102 : bool
103 71187 : NBNodeCont::insert(NBNode* node) {
104 : std::string id = node->getID();
105 : NodeCont::iterator i = myNodes.find(id);
106 71187 : if (i != myNodes.end()) {
107 : return false;
108 : }
109 70990 : myNodes[id] = node;
110 70990 : const float pos[2] = {(float)node->getPosition().x(), (float)node->getPosition().y()};
111 70990 : myRTree.Insert(pos, pos, node);
112 70990 : return true;
113 : }
114 :
115 :
116 : NBNode*
117 420670 : NBNodeCont::retrieve(const std::string& id) const {
118 : NodeCont::const_iterator i = myNodes.find(id);
119 420670 : if (i == myNodes.end()) {
120 : return nullptr;
121 : }
122 376998 : 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 3021 : NBNodeCont::erase(NBNode* node) {
149 3021 : if (extract(node)) {
150 3021 : delete node;
151 3021 : return true;
152 : } else {
153 : return false;
154 : }
155 : }
156 :
157 :
158 : bool
159 11985 : NBNodeCont::extract(NBNode* node, bool remember) {
160 : NodeCont::iterator i = myNodes.find(node->getID());
161 11985 : if (i == myNodes.end()) {
162 : return false;
163 : }
164 : myNodes.erase(i);
165 11985 : const float pos[2] = {(float)node->getPosition().x(), (float)node->getPosition().y()};
166 11985 : myRTree.Remove(pos, pos, node);
167 11985 : node->removeTrafficLights();
168 11985 : if (remember) {
169 8964 : myExtractedNodes[node->getID()] = node;
170 : }
171 : return true;
172 : }
173 :
174 :
175 : // ----------- Adapting the input
176 : int
177 2183 : NBNodeCont::removeSelfLoops(NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tc) {
178 2183 : int no = 0;
179 72824 : for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
180 70641 : no += (*i).second->removeSelfLoops(dc, ec, tc);
181 : }
182 2183 : if (no != 0) {
183 0 : WRITE_WARNING(toString(no) + " self-looping edge(s) removed.");
184 : }
185 2183 : 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 2184 : NBNodeCont::removeUnwishedNodes(NBDistrictCont& dc, NBEdgeCont& ec,
462 : NBTrafficLightLogicCont& /*tlc*/, NBPTStopCont& sc,
463 : NBPTLineCont& lc,
464 : NBParkingCont& pc,
465 : bool removeGeometryNodes) {
466 2184 : const OptionsCont& oc = OptionsCont::getOptions();
467 : // load edges that shall not be modified
468 : std::set<std::string> edges2keep;
469 2184 : if (removeGeometryNodes) {
470 224 : if (oc.isSet("geometry.remove.keep-edges.input-file")) {
471 2 : NBHelpers::loadEdgesFromFile(oc.getString("geometry.remove.keep-edges.input-file"), edges2keep);
472 : }
473 224 : 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 112 : pc.addEdges2Keep(oc, edges2keep);
480 223 : 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 114075 : for (auto it = ec.begin(); it != ec.end(); it++) {
487 111891 : NBEdge* e = it->second;
488 : NBNode* to = e->getToNode();
489 111891 : if (to->isTLControlled()) {
490 6889 : tlsLookup[e] = to->getControllingTLS();
491 : }
492 : }
493 4368 : const bool outputRemoved = oc.getBool("output.removed-nodes");
494 : std::vector<NBNode*> toRemove;
495 70685 : for (const auto& i : myNodes) {
496 68501 : 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 85901 : 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 20001 : for (NBEdge* const it_edge : current->getEdges()) {
503 11048 : 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 8992 : if (!remove) {
511 59548 : continue;
512 : }
513 14457 : for (const std::pair<NBEdge*, NBEdge*>& j : current->getEdgesToJoin()) {
514 5504 : NBEdge* const begin = j.first;
515 5504 : NBEdge* const continuation = j.second;
516 5504 : begin->append(continuation);
517 5504 : continuation->getToNode()->replaceIncoming(continuation, begin, 0);
518 : auto itTL = tlsLookup.find(continuation);
519 5504 : if (itTL != tlsLookup.end()) {
520 1026 : for (NBTrafficLightDefinition* tls : itTL->second) {
521 513 : tls->replaceRemoved(continuation, -1, begin, -1, true);
522 : }
523 513 : tlsLookup[begin] = itTL->second;
524 : }
525 5504 : sc.replaceEdge(continuation->getID(), { begin });
526 5504 : lc.replaceEdge(continuation->getID(), { begin });
527 5504 : ec.extract(dc, continuation, true);
528 5504 : if (outputRemoved) {
529 7 : begin->updateRemovedNodes(current->getID());
530 : }
531 8953 : }
532 8953 : toRemove.push_back(current);
533 : }
534 : // erase all
535 11137 : for (NBNode* n : toRemove) {
536 8953 : extract(n, true);
537 : }
538 2184 : return (int)toRemove.size();
539 2184 : }
540 :
541 :
542 : void
543 1590 : NBNodeCont::avoidOverlap() {
544 34795 : for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
545 33205 : (*i).second->avoidOverlap();
546 : }
547 1590 : }
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 33882 : for (const auto& i : myNodes) {
555 5140 : if (visited.count(i.second) > 0) {
556 31566 : continue;
557 : }
558 : std::vector<NodeAndDist> toProc;
559 28589 : toProc.emplace_back(i.second, 0.);
560 : NodeSet c;
561 64955 : while (!toProc.empty()) {
562 36366 : NBNode* const n = toProc.back().first;
563 36366 : const double dist = toProc.back().second;
564 : toProc.pop_back();
565 2637 : if (visited.count(n) > 0) {
566 7732 : continue;
567 : }
568 : visited.insert(n);
569 : bool pureRail = true;
570 : bool railAndPeds = true;
571 71872 : for (NBEdge* e : n->getEdges()) {
572 54258 : if ((e->getPermissions() & ~(SVC_RAIL_CLASSES | SVC_PEDESTRIAN)) != 0) {
573 : railAndPeds = false;
574 : pureRail = false;
575 : break;
576 : }
577 38143 : if ((e->getPermissions() & ~(SVC_RAIL_CLASSES)) != 0) {
578 : pureRail = false;
579 : }
580 : }
581 33729 : if (pureRail) {
582 : // do not join pure rail nodes
583 5095 : continue;
584 : }
585 : c.insert(n);
586 124230 : for (NBEdge* e : n->getEdges()) {
587 191192 : 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 95596 : if (railAndPeds && n->getType() != SumoXMLNodeType::RAIL_CROSSING) {
596 : bool railAndPeds2 = true;
597 105704 : for (NBEdge* e2 : n->getEdges()) {
598 77449 : if ((e2->getPermissions() & ~(SVC_RAIL_CLASSES | SVC_PEDESTRIAN)) != 0) {
599 : railAndPeds2 = false;
600 : break;
601 : }
602 : }
603 28255 : 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 74566 : continue;
607 : }
608 : }
609 67619 : const bool bothCrossing = n->getType() == SumoXMLNodeType::RAIL_CROSSING && s->getType() == SumoXMLNodeType::RAIL_CROSSING;
610 658 : const bool joinPedCrossings = bothCrossing && e->getPermissions() == SVC_PEDESTRIAN;
611 24817 : if ( // never join pedestrian stuff (unless at a rail crossing
612 67447 : !joinPedCrossings && (
613 67447 : e->getPermissions() == SVC_PEDESTRIAN
614 : // only join edges for regular passenger traffic or edges that are extremely short
615 60680 : || (length > 3 * POSITION_EPS
616 54689 : && (e->getPermissions() & (SVC_PASSENGER | SVC_TRAM)) == 0
617 18082 : && n->getPosition().distanceTo2D(s->getPosition()) > SUMO_const_laneWidth))) {
618 : #ifdef DEBUG_JOINJUNCTIONS
619 : if (DEBUGCOND(s)) {
620 : std::cout << " ignored s=" << s->getID() << " pedestrian edge=" << e->getID() << " cd=" << n->getPosition().distanceTo2D(s->getPosition()) << "\n";
621 : }
622 : #endif
623 24817 : continue;
624 : }
625 : // never join rail_crossings with other node types unless the crossing is only for tram
626 1215 : if ((n->getType() == SumoXMLNodeType::RAIL_CROSSING && s->getType() != SumoXMLNodeType::RAIL_CROSSING)
627 43448 : || (n->getType() != SumoXMLNodeType::RAIL_CROSSING && s->getType() == SumoXMLNodeType::RAIL_CROSSING)) {
628 : const SVCPermissions railNoTram = (SVC_RAIL_CLASSES & ~SVC_TRAM);
629 : bool foundRail = false;
630 776 : NBNode* crossingNode = n->getType() == SumoXMLNodeType::RAIL_CROSSING ? n : s;
631 2844 : for (NBEdge* e2 : crossingNode->getIncomingEdges()) {
632 2084 : if ((e2->getPermissions() & railNoTram) != 0) {
633 : foundRail = true;
634 : break;
635 : }
636 : }
637 776 : if (foundRail) {
638 16 : continue;
639 : }
640 : }
641 : // never join rail_crossings via a rail edge
642 42786 : if (bothCrossing && (e->getPermissions() & ~SVC_RAIL_CLASSES) == 0) {
643 418 : continue;
644 : }
645 42368 : if (visited.find(s) != visited.end()) {
646 21338 : 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 7777 : const bool trueGeomLike = s->geometryLike();
651 7777 : if (trueGeomLike || geometryLikeForClass(s, SVC_VULNERABLE | SVC_DELIVERY)) {
652 9497 : 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 2721 : toProc.emplace_back(s, 0.);
658 : }
659 : }
660 : }
661 : }
662 28589 : if (c.size() < 2) {
663 : continue;
664 : }
665 : #ifdef DEBUG_JOINJUNCTIONS
666 : std::cout << " DEBUG: consider cluster " << joinNamedToString(c, ' ') << "\n";
667 : #endif
668 2163 : into.push_back(c);
669 28589 : }
670 153 : }
671 :
672 :
673 : bool
674 5529 : NBNodeCont::geometryLikeForClass(const NBNode* n, SVCPermissions ignored) {
675 : EdgeVector allowedIn;
676 : EdgeVector allowedOut;
677 20302 : for (NBEdge* e : n->getIncomingEdges()) {
678 14773 : if ((e->getPermissions() & ~ignored) != 0) {
679 11131 : allowedIn.push_back(e);
680 : }
681 : }
682 20276 : for (NBEdge* e : n->getOutgoingEdges()) {
683 14747 : if ((e->getPermissions() & ~ignored) != 0) {
684 11119 : allowedOut.push_back(e);
685 : }
686 : }
687 5529 : 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 5115 : return n->geometryLike(allowedIn, allowedOut);
690 : }
691 : return true;
692 5529 : }
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 892 : NBNodeCont::createClusterId(const std::set<std::string>& cluster, const std::string& prefix) {
711 892 : int maxIds = OptionsCont::getOptions().getInt("max-join-ids");
712 892 : if (maxIds <= 0) {
713 0 : maxIds = (int)cluster.size();
714 : }
715 892 : if ((int)cluster.size() > maxIds) {
716 : auto clusterIt = cluster.begin();
717 : std::string result = prefix + *clusterIt;
718 512 : for (int i = 1; i < maxIds; i++) {
719 : ++clusterIt;
720 768 : result += "_" + *clusterIt;
721 : }
722 256 : return result + "_#" + toString((int)cluster.size() - maxIds) + "more";
723 : }
724 1528 : return prefix + joinToString(cluster, "_");
725 : }
726 :
727 :
728 : void
729 11 : NBNodeCont::addCluster2Join(const std::set<std::string>& cluster, NBNode* node, const bool resetConnections) {
730 : // error handling has to take place here since joins could be loaded from multiple files
731 11 : JoinCluster join{{}, node, resetConnections};
732 99 : 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 88 : if (retrieve(nodeID) != nullptr) {
741 : join.cluster.insert(nodeID);
742 : } else {
743 0 : WRITE_ERRORF(TL("Unknown junction '%' in join-cluster."), nodeID);
744 : }
745 : }
746 : }
747 11 : if (join.cluster.size() > 1) {
748 10 : myJoined.insert(join.cluster.begin(), join.cluster.end());
749 10 : myClusters2Join.emplace_back(join);
750 : } else {
751 3 : WRITE_WARNINGF(TL("Ignoring join-cluster '%' because it has size '%'."), node->getID(), join.cluster.size());
752 : }
753 : }
754 :
755 :
756 : int
757 2183 : NBNodeCont::joinLoadedClusters(NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc) {
758 : int numJoined = 0;
759 2193 : for (JoinCluster& item : myClusters2Join) {
760 : // verify loaded cluster
761 : NodeSet cluster;
762 97 : for (std::string nodeID : item.cluster) {
763 87 : NBNode* node = retrieve(nodeID);
764 87 : if (node == nullptr) {
765 0 : WRITE_ERRORF(TL("unknown junction '%' while joining."), nodeID);
766 : } else {
767 : cluster.insert(node);
768 : }
769 : }
770 10 : if (cluster.size() > 1) {
771 10 : joinNodeCluster(cluster, dc, ec, tlc, item.node, item.resetConnections);
772 10 : numJoined++;
773 10 : myJoinExclusions.insert(item.node->getID());
774 : }
775 : }
776 : myClusters2Join.clear(); // make save for recompute
777 2183 : 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 1158 : for (const auto& stopIt : sc.getStops()) {
791 1045 : NBEdge* edge = ec.retrieve(stopIt.second->getEdgeId());
792 1045 : if (edge != nullptr) {
793 971 : ptStopEnds[edge->getFromNode()].push_back(edge->getToNode());
794 : }
795 : }
796 113 : generateNodeClusters(maxDist, cands);
797 1622 : 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 6723 : for (NodeSet::iterator j = cluster.begin(); j != cluster.end();) {
808 : NodeSet::iterator check = j;
809 : ++j;
810 5214 : if (myJoinExclusions.count((*check)->getID()) > 0) {
811 : cluster.erase(check);
812 : }
813 : }
814 1509 : std::string origCluster = joinNamedToString(cluster, ',');
815 : // remove nodes that can be eliminated by geometry.remove
816 1509 : pruneClusterFringe(cluster, maxDist);
817 1509 : if (cluster.size() < 2) {
818 719 : 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 9 : WRITE_WARNINGF(TL("Not joining junctions % (%)."), origCluster, "slip lane");
824 3 : continue;
825 : }
826 787 : origCluster = joinNamedToString(cluster, ',');
827 787 : 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 787 : bool feasible = feasibleCluster(cluster, ptStopEnds, maxDist, origReason, tryRemove);
832 787 : if (feasible && ((int)cluster.size() - pruneLongEdges(cluster, maxDist, true) < 2)) {
833 : origReason = "long edge";
834 : feasible = false;
835 : }
836 782 : 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 794 : 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 787 : 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 786 : const int numPruned = pruneLongEdges(cluster, maxDist);
877 786 : 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 786 : 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 786 : feasible = feasibleCluster(cluster, ptStopEnds, maxDist, origReason, tryRemove);
895 786 : 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 3258 : 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 5078 : 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 4969 : for (NBNode* k : *check) {
912 4166 : if (current->getConnectionTo(k) != nullptr || k->getConnectionTo(current) != nullptr) {
913 : //std::cout << "joining with connected component " << toString(*check) << "\n";
914 1764 : 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 2511 : components.push_back(newComp);
926 : }
927 1494 : for (NodeClusters::iterator it_comp = components.begin(); it_comp != components.end(); ++it_comp) {
928 747 : if ((*it_comp).size() > 1) {
929 : //std::cout << "adding cluster " << toString(*it_comp) << "\n";
930 747 : clusters.push_back(*it_comp);
931 : }
932 : }
933 : #ifdef DEBUG_JOINJUNCTIONS
934 : gDebugFlag1 = false;
935 : #endif
936 747 : }
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 1576 : 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 6137 : while (pruneFringe) {
984 : pruneFringe = false;
985 15235 : for (NodeSet::iterator j = cluster.begin(); j != cluster.end();) {
986 : NodeSet::iterator check = j;
987 10674 : 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 33691 : for (EdgeVector::const_iterator it_edge = n->getOutgoingEdges().begin(); it_edge != n->getOutgoingEdges().end(); ++it_edge) {
994 23017 : NBNode* neighbor = (*it_edge)->getToNode();
995 : if (cluster.count(neighbor) != 0) {
996 : clusterDist = MIN2(clusterDist, (*it_edge)->getLoadedLength());
997 11149 : touchingCluster |= n->getPosition().distanceTo2D(neighbor->getPosition()) <= SUMO_const_laneWidth;
998 : }
999 : }
1000 33800 : for (EdgeVector::const_iterator it_edge = n->getIncomingEdges().begin(); it_edge != n->getIncomingEdges().end(); ++it_edge) {
1001 23126 : NBNode* neighbor = (*it_edge)->getFromNode();
1002 : if (cluster.count(neighbor) != 0) {
1003 : clusterDist = MIN2(clusterDist, (*it_edge)->getLoadedLength());
1004 11062 : 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 56817 : for (NBEdge* e : n->getEdges()) {
1013 69160 : NBNode* neighbor = e->getFromNode() == n ? e->getToNode() : e->getFromNode();
1014 : if (cluster.count(neighbor) == 0) {
1015 23932 : if ((e->getPermissions() & SVC_PASSENGER) != 0
1016 9558 : || isRailway(e->getPermissions()) // join railway crossings
1017 7334 : || (clusterDist <= pedestrianFringeThreshold
1018 5086 : && (!pruneNoisyFringe
1019 1971 : || isForVulnerableModes(e->getPermissions())
1020 : // permit joining small opposite merges
1021 797 : || getDiameter(cluster) < maxDist
1022 170 : || cluster.size() == 2))
1023 26286 : || 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 10674 : || (outsideNeighbors.size() <= 1
1042 5615 : && clusterNeighbors.size() == 1
1043 2268 : && !(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 8282 : } else if (outsideNeighbors.size() <= 1 && clusterNeighbors.size() == 1) {
1052 : geometryLikeTLS.insert(n);
1053 : }
1054 : }
1055 4561 : 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 1576 : if (remove2TLS && geometryLikeTLS.size() == cluster.size()) {
1063 : cluster.clear();
1064 : }
1065 1576 : }
1066 :
1067 : double
1068 797 : NBNodeCont::getDiameter(const NodeSet& cluster) {
1069 : double result = 0;
1070 3007 : for (const NBNode* n1 : cluster) {
1071 12308 : for (const NBNode* n2 : cluster) {
1072 : result = MAX2(result, n1->getPosition().distanceTo2D(n2->getPosition()));
1073 : }
1074 : }
1075 797 : return result;
1076 : }
1077 :
1078 : int
1079 1517 : NBNodeCont::pruneLongEdges(NodeSet& cluster, double maxDist, const bool dryRun) {
1080 : std::set<NBNode*> toRemove;
1081 : int maxPassengerLanes = 0;
1082 6631 : for (NBNode* n : cluster) {
1083 28763 : for (NBEdge* edge : n->getEdges()) {
1084 23649 : maxPassengerLanes = MAX2(maxPassengerLanes, edge->getNumLanesThatAllow(SVC_PASSENGER));
1085 : }
1086 : }
1087 6631 : for (NBNode* n : cluster) {
1088 16914 : 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 11800 : NBNode* to = edge->getToNode();
1096 11800 : while (cluster.count(to) != 0) {
1097 6825 : length += cur->getLoadedLength();
1098 6825 : bool goStraight = (std::find(passed.begin(), passed.end(), to) == passed.end()
1099 6825 : && (edge->getPermissions() & SVC_PASSENGER) != 0
1100 12134 : && to->geometryLike(
1101 12134 : NBEdge::filterByPermissions(to->getIncomingEdges(), SVC_PASSENGER),
1102 12134 : NBEdge::filterByPermissions(to->getOutgoingEdges(), SVC_PASSENGER)));
1103 6825 : passed.push_back(to);
1104 6825 : if (goStraight) {
1105 2730 : cur = cur->getStraightContinuation(SVC_PASSENGER);
1106 2730 : if (cur != nullptr) {
1107 2708 : to = cur->getToNode();
1108 : } else {
1109 : break;
1110 : }
1111 : } else {
1112 : break;
1113 : }
1114 : }
1115 : // allow higher threshold at larger junctions
1116 11800 : 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 11800 : 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 11800 : }
1143 : }
1144 1517 : if (!dryRun) {
1145 797 : for (std::set<NBNode*>::iterator j = toRemove.begin(); j != toRemove.end(); ++j) {
1146 : cluster.erase(*j);
1147 : }
1148 : }
1149 1517 : 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 469 : return;
1179 : }
1180 : NodeSet toRemove;
1181 2202 : for (NBNode* n : cluster) {
1182 : EdgeVector outgoing;
1183 : double inAngle;
1184 : // find slip lanes where the start is part of the cluster
1185 1876 : 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 213 : for (NBEdge* contEdge : outgoing) {
1193 142 : if ((contEdge->getPermissions() & SVC_PASSENGER) == 0) {
1194 0 : continue;
1195 : }
1196 142 : double slipLength = contEdge->getLength();
1197 142 : NBNode* cont = contEdge->getToNode();
1198 : NodeSet cands;
1199 : cands.insert(n);
1200 287 : 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 145 : NBEdge* next = cont->getOutgoingEdges().front();
1211 145 : slipLength += next->getLength();
1212 145 : 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 180 : if (cont->getIncomingEdges().size() >= 2 && cont->getOutgoingEdges().size() == 1 &&
1220 : // slip lanes are for turning so there needs to be a sufficient angle
1221 38 : 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 1876 : 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 273 : for (NBEdge* contEdge : incoming) {
1279 182 : if ((contEdge->getPermissions() & SVC_PASSENGER) == 0) {
1280 0 : continue;
1281 : }
1282 182 : double slipLength = contEdge->getLength();
1283 182 : NBNode* cont = contEdge->getFromNode();
1284 : NodeSet cands;
1285 : cands.insert(n);
1286 365 : 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 183 : NBEdge* next = cont->getIncomingEdges().front();
1297 183 : slipLength += next->getLength();
1298 183 : 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 235 : 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 1876 : }
1357 : int numRemoved = 0;
1358 420 : for (NBNode* n : toRemove) {
1359 94 : numRemoved += (int)cluster.erase(n);
1360 : }
1361 326 : 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 652 : NBNodeCont::isSlipLaneContinuation(const NBNode* cont) {
1374 980 : return cont->getPassengerEdges(true).size() == 1 && cont->getPassengerEdges(false).size() == 1;
1375 : }
1376 :
1377 :
1378 : bool
1379 1876 : NBNodeCont::maybeSlipLaneStart(const NBNode* n, EdgeVector& outgoing, double& inAngle) const {
1380 1876 : EdgeVector inPE = n->getPassengerEdges(true);
1381 1876 : EdgeVector outPE = n->getPassengerEdges(false);
1382 1876 : if (inPE.size() == 1 && outPE.size() == 2) {
1383 65 : outgoing.insert(outgoing.begin(), outPE.begin(), outPE.end());
1384 65 : inAngle = inPE.front()->getAngleAtNode(n);
1385 65 : return true;
1386 1811 : } 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 1876 : }
1414 :
1415 :
1416 : bool
1417 1876 : NBNodeCont::maybeSlipLaneEnd(const NBNode* n, EdgeVector& incoming, double& outAngle) const {
1418 1876 : EdgeVector inPE = n->getPassengerEdges(true);
1419 1876 : EdgeVector outPE = n->getPassengerEdges(false);
1420 1876 : if (inPE.size() == 2 && outPE.size() == 1) {
1421 86 : incoming.insert(incoming.begin(), inPE.begin(), inPE.end());
1422 86 : outAngle = outPE.front()->getAngleAtNode(n);
1423 86 : return true;
1424 1790 : } 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 1876 : }
1452 :
1453 : bool
1454 1601 : 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 7003 : for (NBNode* n : cluster) {
1461 17863 : for (EdgeVector::const_iterator it_edge = n->getIncomingEdges().begin(); it_edge != n->getIncomingEdges().end(); ++it_edge) {
1462 12461 : NBEdge* edge = *it_edge;
1463 18439 : if (cluster.count(edge->getFromNode()) == 0 && (edge->getPermissions() & SVC_PASSENGER) != 0) {
1464 : // incoming edge, does not originate in the cluster
1465 3452 : finalIncomingAngles[edge] = edge->getAngleAtNode(edge->getToNode());
1466 : }
1467 : }
1468 17792 : for (EdgeVector::const_iterator it_edge = n->getOutgoingEdges().begin(); it_edge != n->getOutgoingEdges().end(); ++it_edge) {
1469 12390 : NBEdge* edge = *it_edge;
1470 18368 : if (cluster.count(edge->getToNode()) == 0 && (edge->getPermissions() & SVC_PASSENGER) != 0) {
1471 : // outgoing edge, does not end in the cluster
1472 3459 : 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 1601 : if (finalIncomingAngles.size() > 5) {
1488 6 : reason = toString(finalIncomingAngles.size()) + " incoming edges";
1489 3 : return false;
1490 : }
1491 : // check for incoming parallel edges
1492 1598 : const double PARALLEL_THRESHOLD_DIFF_NODE = OptionsCont::getOptions().getFloat("junctions.join.parallel-threshold");
1493 1598 : const double PARALLEL_THRESHOLD_SAME_NODE = PARALLEL_THRESHOLD_DIFF_NODE / 3;
1494 : bool foundParallel = false;
1495 4915 : for (auto j = finalIncomingAngles.begin(); j != finalIncomingAngles.end() && !foundParallel; ++j) {
1496 : auto k = j;
1497 6701 : for (++k; k != finalIncomingAngles.end() && !foundParallel; ++k) {
1498 3384 : const double angleDiff = fabs(j->second - k->second);
1499 3384 : if (angleDiff < PARALLEL_THRESHOLD_DIFF_NODE) {
1500 38 : NBEdge* e1 = j->first;
1501 38 : NBEdge* e2 = k->first;
1502 : // for edge targeting the same node, permit a narrower angle
1503 38 : 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 38 : if (angleDiff >= PARALLEL_THRESHOLD_SAME_NODE && (
1510 : (e1->getToNode() == e2->getToNode()
1511 14 : || (edgeDist < maxDist)))) {
1512 6 : 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 4836 : for (auto j = finalOutgoingAngles.begin(); j != finalOutgoingAngles.end() && !foundParallel; ++j) {
1530 : auto k = j;
1531 6575 : for (++k; k != finalOutgoingAngles.end() && !foundParallel; ++k) {
1532 3305 : const double angleDiff = fabs(j->second - k->second);
1533 3305 : 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 6757 : for (NBNode* n : cluster) {
1565 5214 : if (n->isTLControlled() || n->hadSignal()) {
1566 : hasTLS = true;
1567 : }
1568 : const auto& stopEnds = ptStopEnds.find(n);
1569 5214 : 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 1543 : if (cluster.size() > 2) {
1580 : // find the nodes with the biggests physical distance between them
1581 589 : double maxLength = -1;
1582 : NBEdge* maxEdge = nullptr;
1583 3867 : for (NBNode* n1 : cluster) {
1584 29140 : for (NBNode* n2 : cluster) {
1585 25862 : NBEdge* e1 = n1->getConnectionTo(n2);
1586 25862 : NBEdge* e2 = n2->getConnectionTo(n1);
1587 29960 : if (e1 != nullptr && e1->getLoadedLength() > maxLength) {
1588 746 : maxLength = e1->getLoadedLength();
1589 : maxEdge = e1;
1590 : }
1591 29960 : if (e2 != nullptr && e2->getLoadedLength() > maxLength) {
1592 595 : 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 589 : 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 1541 : if (cluster.size() >= 2) {
1635 : int entryNodes = 0;
1636 : int exitNodes = 0;
1637 : EdgeVector outsideIncoming;
1638 : EdgeVector outsideOutgoing;
1639 : int edgesWithin = 0;
1640 6716 : for (NBNode* n : cluster) {
1641 : bool foundOutsideIncoming = false;
1642 17151 : for (NBEdge* e : n->getIncomingEdges()) {
1643 11975 : 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 5721 : edgesWithin++;
1649 : }
1650 : }
1651 5176 : if (foundOutsideIncoming) {
1652 4131 : entryNodes++;
1653 : }
1654 : bool foundOutsideOutgoing = false;
1655 17079 : for (NBEdge* e : n->getOutgoingEdges()) {
1656 11903 : if (cluster.count(e->getToNode()) == 0) {
1657 : // edge leaving cluster
1658 6182 : outsideOutgoing.push_back(e);
1659 : foundOutsideOutgoing = true;
1660 : }
1661 : }
1662 5176 : if (foundOutsideOutgoing) {
1663 4037 : exitNodes++;
1664 : }
1665 : }
1666 1540 : 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 755 : 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 1540 : }
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 939 : for (NodeSet cluster : clusters) {
1779 1626 : 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 3559 : 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 10182 : for (NBEdge* e : allEdges) {
1803 9359 : if (cluster.count(e->getToNode()) > 0) {
1804 6131 : if (cluster.count(e->getFromNode()) > 0) {
1805 : inside.insert(e);
1806 : if (e->getSignalPosition() != Position::INVALID) {
1807 41 : setTL = true;
1808 41 : 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 813 : if (!insert(id, pos)) {
1827 : // should not fail
1828 0 : WRITE_WARNINGF(TL("Could not join junctions %."), id);
1829 : return;
1830 : }
1831 813 : newNode = retrieve(id);
1832 : }
1833 : std::string tlID = id;
1834 823 : if (predefined != nullptr) {
1835 10 : if (predefined->getType() != SumoXMLNodeType::UNKNOWN) {
1836 1 : nodeType = predefined->getType();
1837 1 : setTL = predefined->isTLControlled();
1838 : }
1839 10 : Position ppos = predefined->getPosition();
1840 10 : if (ppos.x() != Position::INVALID.x()) {
1841 : pos.setx(ppos.x());
1842 : }
1843 10 : if (ppos.y() != Position::INVALID.y()) {
1844 : pos.sety(ppos.y());
1845 : }
1846 10 : if (ppos.z() != Position::INVALID.z()) {
1847 : pos.setz(ppos.z());
1848 : }
1849 : }
1850 823 : newNode->reinit(pos, nodeType);
1851 823 : if (origNames) {
1852 958 : newNode->setParameter(SUMO_PARAM_ORIGID, joinNamedToString(cluster, ' '));
1853 : }
1854 823 : if (setTL && !newNode->isTLControlled()) {
1855 224 : NBTrafficLightDefinition* tlDef = new NBOwnTLDef(tlID, newNode, 0, type);
1856 224 : if (!tlc.insert(tlDef)) {
1857 : // actually, nothing should fail here
1858 0 : delete tlDef;
1859 0 : throw ProcessError(TLF("Could not allocate tls '%'.", id));
1860 : }
1861 : }
1862 :
1863 : // determine possible connectivity from outside edges
1864 : std::map<NBEdge*, EdgeSet> reachable;
1865 : std::map<std::pair<NBEdge*, NBEdge*>, SVCPermissions> conPermissions;
1866 : EdgeSet specialPermissions;
1867 4065 : for (NBEdge* const e : clusterIncoming) {
1868 : EdgeVector open;
1869 : EdgeSet seen;
1870 3242 : open.push_back(e);
1871 25541 : while (open.size() > 0) {
1872 22299 : NBEdge* const cur = open.back();
1873 22299 : const SVCPermissions pCur = conPermissions.count({e, cur}) == 0 ? cur->getPermissions() : conPermissions[ {e, cur}];
1874 : #ifdef DEBUG_JOINJUNCTIONS_CONNECTIONS
1875 : std::cout << "e=" << e->getID() << " cur=" << cur->getID() << " open=" << toString(open) << "\n";
1876 : std::cout << "e=" << e->getID() << " cur=" << cur->getID() << " open=" << toString(open) << "\n";
1877 : #endif
1878 : seen.insert(cur);
1879 : open.pop_back();
1880 22299 : if (cluster.count(cur->getToNode()) == 0) {
1881 : //std::cout << " continue\n";
1882 9818 : continue;
1883 : }
1884 : const auto& cons = cur->getConnections();
1885 13745 : if (cons.size() == 0 || ec.hasPostProcessConnection(cur->getID()) || cur->getStep() == NBEdge::EdgeBuildingStep::INIT) {
1886 : // check permissions to determine reachability
1887 40349 : for (NBEdge* out : cur->getToNode()->getOutgoingEdges()) {
1888 : if (allEdges.count(out) != 0) {
1889 29089 : const SVCPermissions p = pCur & out->getPermissions();
1890 6990 : if (seen.count(out) == 0 || (~conPermissions[ {e, out}] & p) != 0) {
1891 22166 : if ((p & ~SVC_PEDESTRIAN) != 0) {
1892 16902 : open.push_back(out);
1893 16902 : conPermissions[ {e, out}] |= p;
1894 : #ifdef DEBUG_JOINJUNCTIONS_CONNECTIONS
1895 : std::cout << " e=" << e->getID() << " out=" << out->getID() << " pOut=" << getVehicleClassNames(out->getPermissions()) << "\n p=" << getVehicleClassNames(p) << "\n q=" << getVehicleClassNames(conPermissions[ {e, out}]) << "\n";
1896 : #endif
1897 : }
1898 : }
1899 : }
1900 : }
1901 : } else {
1902 : // check existing connections
1903 4798 : for (const auto& con : cons) {
1904 3577 : if (con.toEdge != nullptr && allEdges.count(con.toEdge) != 0) {
1905 3577 : SVCPermissions p = pCur & con.toEdge->getPermissions();
1906 3577 : if (con.permissions != SVC_UNSPECIFIED) {
1907 7 : p &= con.permissions;
1908 : }
1909 1422 : if (seen.count(con.toEdge) == 0 || (~conPermissions[ {e, con.toEdge}] & p) != 0) {
1910 2155 : open.push_back(con.toEdge);
1911 2155 : conPermissions[ {e, con.toEdge}] |= p;
1912 : //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";
1913 : }
1914 : }
1915 : }
1916 : }
1917 : }
1918 : seen.erase(e);
1919 19228 : for (NBEdge* reached : seen) {
1920 : // filter out inside edges from reached
1921 : if (inside.count(reached) == 0) {
1922 7924 : if (e->getStep() > NBEdge::EdgeBuildingStep::INIT && reached->getFromNode() == e->getToNode() && !e->isConnectedTo(reached)) {
1923 : // also filter out edges that are outgoing of the to-node of edge but aren't currently connected
1924 14 : continue;
1925 : }
1926 7910 : reachable[e].insert(reached);
1927 7910 : const SVCPermissions pDefault = e->getPermissions() & reached->getPermissions();
1928 7910 : if (conPermissions[ {e, reached}] != pDefault) {
1929 : specialPermissions.insert(e);
1930 : #ifdef DEBUG_JOINJUNCTIONS_CONNECTIONS
1931 : std::cout << "e=" << e->getID() << " out=" << reached->getID() << " special=" << getVehicleClassNames(conPermissions[ {e, reached}]) << "\n";
1932 : #endif
1933 : }
1934 : }
1935 : }
1936 : #ifdef DEBUG_JOINJUNCTIONS_CONNECTIONS
1937 : std::cout << " reachable e=" << e->getID() << " seen=" << toString(seen) << " reachable=" << toString(reachable[e]) << "\n";
1938 : #endif
1939 3242 : }
1940 :
1941 : // remap and remove edges which are completely within the new intersection
1942 823 : if (origNames) {
1943 958 : newNode->setParameter("origEdgeIds", joinNamedToString(inside, ' '));
1944 : }
1945 3712 : for (NBEdge* e : inside) {
1946 52343 : for (NBEdge* e2 : allEdges) {
1947 49454 : if (e != e2) {
1948 46565 : e2->replaceInConnections(e, e->getConnections());
1949 : }
1950 : }
1951 2889 : ec.extract(dc, e, true);
1952 : allEdges.erase(e);
1953 : }
1954 :
1955 : // remap edges which are incoming / outgoing
1956 7293 : for (NBEdge* e : allEdges) {
1957 6470 : const bool outgoing = cluster.count(e->getFromNode()) > 0;
1958 : NBNode* from = outgoing ? newNode : e->getFromNode();
1959 : NBNode* to = outgoing ? e->getToNode() : newNode;
1960 6470 : if (origNames) {
1961 4053 : if (outgoing) {
1962 4048 : e->setParameter("origFrom", e->getFromNode()->getID());
1963 : } else {
1964 4058 : e->setParameter("origTo", e->getToNode()->getID());
1965 : }
1966 : }
1967 6470 : if (e->getTurnSignTarget() != "") {
1968 25001 : for (NBNode* n : cluster) {
1969 21018 : if (e->getTurnSignTarget() == n->getID()) {
1970 : e->setTurnSignTarget(to->getID());
1971 : break;
1972 : }
1973 : }
1974 : }
1975 6470 : e->reinitNodes(from, to);
1976 : // re-add connections which previously existed and may still valid.
1977 : // connections to removed edges will be ignored
1978 6470 : std::vector<NBEdge::Connection> conns = e->getConnections();
1979 8359 : for (std::vector<NBEdge::Connection>::iterator k = conns.begin(); k != conns.end(); ++k) {
1980 1889 : if ((*k).toEdge == nullptr) {
1981 : // edge explicitly set to have no connections
1982 1 : continue;
1983 : }
1984 1888 : e->addLane2LaneConnection((*k).fromLane, (*k).toEdge, (*k).toLane, NBEdge::Lane2LaneInfoType::USER, false, (*k).mayDefinitelyPass);
1985 1888 : if ((*k).fromLane >= 0 && (*k).fromLane < e->getNumLanes() && e->getLaneStruct((*k).fromLane).connectionsDone) {
1986 : // @note (see NIImporter_DlrNavteq::ConnectedLanesHandler)
1987 : e->declareConnectionsAsLoaded(NBEdge::EdgeBuildingStep::INIT);
1988 : #ifdef DEBUG_JOINJUNCTIONS_CONNECTIONS
1989 : std::cout << " e=" << e->getID() << " declareConnectionsAsLoaded\n";
1990 : #endif
1991 : }
1992 : }
1993 6470 : }
1994 823 : if (!resetConnections) {
1995 : // disable connections that were impossible with the old topology
1996 : // if connectivity has special permissions, set edge to edge connections explicitly
1997 3843 : for (NBEdge* in : newNode->getIncomingEdges()) {
1998 17744 : for (NBEdge* out : newNode->getOutgoingEdges()) {
1999 14656 : if (reachable[in].count(out) == 0) {
2000 6918 : if (!ec.hasPostProcessConnection(in->getID(), out->getID())) {
2001 : //std::cout << " removeUnreachable in=" << in->getID() << " out=" << out->getID() << "\n";
2002 6918 : in->removeFromConnections(out, -1, -1, true, false, true);
2003 : } else {
2004 : //std::cout << " hasPostProcessConnection in=" << in->getID() << " out=" << out->getID() << "\n";
2005 : }
2006 : } else if (specialPermissions.count(in) != 0) {
2007 399 : SVCPermissions pDefault = in->getPermissions() & out->getPermissions();
2008 399 : SVCPermissions p = conPermissions[ {in, out}] == 0 ? pDefault : conPermissions[ {in, out}];
2009 399 : in->addEdge2EdgeConnection(out, true, p == pDefault ? SVC_UNSPECIFIED : p);
2010 : //std::cout << " addEdge2Edge in=" << in->getID() << " out=" << out->getID() << "\n";
2011 : }
2012 : }
2013 : }
2014 : } else {
2015 222 : for (NBEdge* in : newNode->getIncomingEdges()) {
2016 154 : in->invalidateConnections(true);
2017 : }
2018 : }
2019 :
2020 : // remove original nodes
2021 823 : registerJoinedCluster(cluster);
2022 3559 : for (NBNode* n : cluster) {
2023 2736 : erase(n);
2024 : }
2025 : }
2026 :
2027 :
2028 : void
2029 823 : NBNodeCont::registerJoinedCluster(const NodeSet& cluster) {
2030 : std::set<std::string> ids;
2031 3559 : for (NBNode* n : cluster) {
2032 : ids.insert(n->getID());
2033 : }
2034 823 : myJoinedClusters.push_back(ids);
2035 823 : }
2036 :
2037 : void
2038 0 : NBNodeCont::registerJoinedCluster(const std::set<std::string>& cluster) {
2039 0 : myJoinedClusters.push_back(cluster);
2040 0 : }
2041 :
2042 : void
2043 0 : NBNodeCont::unregisterJoinedCluster(const std::set<std::string>& cluster) {
2044 0 : auto it = std::find(myJoinedClusters.begin(), myJoinedClusters.end(), cluster);
2045 0 : if (it != myJoinedClusters.end()) {
2046 0 : myJoinedClusters.erase(it);
2047 : }
2048 0 : }
2049 :
2050 :
2051 : void
2052 871 : NBNodeCont::analyzeCluster(NodeSet cluster, std::string& id, Position& pos,
2053 : bool& hasTLS, TrafficLightType& type, SumoXMLNodeType& nodeType) {
2054 1742 : id = createClusterId(cluster, id);
2055 : bool ambiguousType = false;
2056 3734 : for (NBNode* j : cluster) {
2057 : pos.add(j->getPosition());
2058 : // add a traffic light if any of the cluster members was controlled
2059 2863 : if (j->isTLControlled()) {
2060 763 : if (!hasTLS) {
2061 : // init type
2062 237 : type = (*j->getControllingTLS().begin())->getType();
2063 526 : } else if (type != (*j->getControllingTLS().begin())->getType()) {
2064 : ambiguousType = true;
2065 : }
2066 763 : hasTLS = true;
2067 : }
2068 2863 : SumoXMLNodeType otherType = j->getType();
2069 2863 : if (nodeType == SumoXMLNodeType::UNKNOWN) {
2070 1601 : nodeType = otherType;
2071 1262 : } else if (nodeType != otherType) {
2072 533 : if (hasTLS) {
2073 486 : nodeType = SumoXMLNodeType::TRAFFIC_LIGHT;
2074 47 : } else if (otherType != SumoXMLNodeType::UNKNOWN) {
2075 14 : if ((nodeType != SumoXMLNodeType::PRIORITY && (nodeType != SumoXMLNodeType::NOJUNCTION || otherType != SumoXMLNodeType::PRIORITY))
2076 12 : || (otherType != SumoXMLNodeType::NOJUNCTION && otherType != SumoXMLNodeType::UNKNOWN && otherType != SumoXMLNodeType::PRIORITY)) {
2077 24 : WRITE_WARNINGF("Ambiguous node type for node cluster '%' (%,%), setting to '" + toString(SumoXMLNodeType::PRIORITY) + "'.", id, toString(nodeType), toString(otherType));
2078 : }
2079 14 : nodeType = SumoXMLNodeType::PRIORITY;
2080 : }
2081 : }
2082 : }
2083 871 : pos.mul(1. / (double)cluster.size());
2084 871 : if (ambiguousType) {
2085 0 : type = SUMOXMLDefinitions::TrafficLightTypes.get(OptionsCont::getOptions().getString("tls.default-type"));
2086 0 : WRITE_WARNINGF(TL("Ambiguous traffic light type for node cluster '%', setting to '%'."), id, toString(type));
2087 : }
2088 871 : }
2089 :
2090 :
2091 : // ----------- (Helper) methods for guessing/computing traffic lights
2092 : bool
2093 991 : NBNodeCont::shouldBeTLSControlled(const NodeSet& c, double laneSpeedThreshold, bool recheck) const {
2094 : bool tooFast = false;
2095 : double laneSpeedSum = 0;
2096 : std::set<NBEdge*> seen;
2097 2147 : for (NBNode* j : c) {
2098 6288 : for (const NBEdge* e : j->getEdges()) {
2099 5132 : if (c.find(e->getFromNode()) != c.end() && c.find(e->getToNode()) != c.end()) {
2100 : // edges fully within the cluster do not count
2101 624 : continue;
2102 : }
2103 4508 : if (j->hasIncoming(e)) {
2104 2250 : if (recheck && !j->hasConflict(e)) {
2105 : // edges without conflict do not count
2106 : // we can only check this after connections have been computed
2107 2 : continue;
2108 : }
2109 2248 : laneSpeedSum += (double)e->getNumLanes() * e->getLaneSpeed(0);
2110 : }
2111 4506 : if (e->getLaneSpeed(0) * 3.6 > 79) {
2112 : tooFast = true;
2113 : }
2114 : }
2115 : }
2116 : //std::cout << " c=" << joinNamedToString(c, ' ') << " size=" << c.size() << " laneSpeedSum=" << laneSpeedSum << " thresh=" << laneSpeedThreshold << " tooFast=" << tooFast << "\n";
2117 1982 : return !tooFast && laneSpeedSum >= laneSpeedThreshold && c.size() != 0;
2118 : }
2119 :
2120 : bool
2121 55 : NBNodeCont::onlyCrossings(const NodeSet& c) const {
2122 : // check whether all component nodes are solely pedestrian crossings
2123 : // (these work fine without joining)
2124 97 : for (NBNode* node : c) {
2125 : EdgeVector nonPedIncoming;
2126 : EdgeVector nonPedOutgoing;
2127 374 : for (NBEdge* e : node->getIncomingEdges()) {
2128 282 : if (e->getPermissions() != SVC_PEDESTRIAN) {
2129 216 : nonPedIncoming.push_back(e);
2130 : }
2131 : }
2132 375 : for (NBEdge* e : node->getOutgoingEdges()) {
2133 283 : if (e->getPermissions() != SVC_PEDESTRIAN) {
2134 215 : nonPedOutgoing.push_back(e);
2135 : }
2136 : }
2137 92 : if (!node->geometryLike(nonPedIncoming, nonPedOutgoing)) {
2138 : //for (NBNode* node : c) {
2139 : // if (node->getID() == "2480337678") {
2140 : // std::cout << " node=" << node->getID() << " nonPedIncoming=" << toString(nonPedIncoming) << " nonPedOutgoing=" << toString(nonPedOutgoing) << "\n";
2141 : // }
2142 : //}
2143 : return false;
2144 : }
2145 92 : }
2146 : return true;
2147 : }
2148 :
2149 :
2150 : bool
2151 50 : NBNodeCont::customTLID(const NodeSet& c) const {
2152 177 : for (NBNode* node : c) {
2153 129 : if (node->isTLControlled()) {
2154 129 : NBTrafficLightDefinition* tl = (*node->getControllingTLS().begin());
2155 129 : if (tl->getNodes().size() > 1) {
2156 : // joined tls also imply a customID
2157 2 : return true;
2158 : }
2159 : const std::string tlID = tl->getID();
2160 127 : if (tlID != node->getID()
2161 129 : && !StringUtils::startsWith(tlID, "joinedS_")
2162 128 : && !StringUtils::startsWith(tlID, "joinedG_")
2163 131 : && !StringUtils::startsWith(tlID, "GS")) {
2164 : return true;
2165 : }
2166 : }
2167 : }
2168 : return false;
2169 : }
2170 :
2171 :
2172 : void
2173 2183 : NBNodeCont::guessTLs(OptionsCont& oc, NBTrafficLightLogicCont& tlc) {
2174 : myGuessedTLS.clear();
2175 : // build list of definitely not tls-controlled junctions
2176 2183 : const double laneSpeedThreshold = oc.getFloat("tls.guess.threshold");
2177 4366 : if (oc.isSet("tls.unset")) {
2178 2 : std::vector<std::string> notTLControlledNodes = oc.getStringVector("tls.unset");
2179 2 : for (std::vector<std::string>::const_iterator i = notTLControlledNodes.begin(); i != notTLControlledNodes.end(); ++i) {
2180 1 : NBNode* n = NBNodeCont::retrieve(*i);
2181 1 : if (n == nullptr) {
2182 0 : throw ProcessError(TLF(" The junction '%' to set as not-controlled is not known.", *i));
2183 : }
2184 : std::set<NBTrafficLightDefinition*> tls = n->getControllingTLS();
2185 1 : for (std::set<NBTrafficLightDefinition*>::const_iterator j = tls.begin(); j != tls.end(); ++j) {
2186 0 : (*j)->removeNode(n);
2187 : }
2188 1 : n->removeTrafficLights();
2189 : myUnsetTLS.insert(n);
2190 : }
2191 1 : }
2192 :
2193 2183 : TrafficLightType type = SUMOXMLDefinitions::TrafficLightTypes.get(OptionsCont::getOptions().getString("tls.default-type"));
2194 : // loop#1 checking whether the node shall be tls controlled,
2195 : // because it is assigned to a district
2196 4278 : if (oc.exists("tls.taz-nodes") && oc.getBool("tls.taz-nodes")) {
2197 0 : for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2198 0 : NBNode* cur = (*i).second;
2199 0 : if (cur->isNearDistrict() && myUnsetTLS.count(cur) == 0) {
2200 0 : setAsTLControlled(cur, tlc, type);
2201 : }
2202 : }
2203 : }
2204 :
2205 : // figure out which nodes mark the locations of TLS signals
2206 : // This assumes nodes are already joined
2207 4278 : if (oc.exists("tls.guess-signals") && oc.getBool("tls.guess-signals")) {
2208 : // prepare candidate edges
2209 92 : const double signalDist = oc.getFloat("tls.guess-signals.dist");
2210 12348 : for (const auto& item : myNodes) {
2211 12302 : const NBNode* node = item.second;
2212 12302 : if (node->isTLControlled() && (node->getIncomingEdges().size() == 1 || node->geometryLike())) {
2213 : #ifdef DEBUG_GUESSSIGNALS
2214 : if (DEBUGCOND(node) || true) {
2215 : std::cout << " propagate TLS from " << node->getID() << " downstream\n";
2216 : }
2217 : #endif
2218 181 : for (NBEdge* edge : node->getOutgoingEdges()) {
2219 : // do not overwrite closer signals
2220 111 : if (edge->getSignalOffset() == NBEdge::UNSPECIFIED_SIGNAL_OFFSET) {
2221 : edge->setSignalPosition(node->getPosition(), node);
2222 : }
2223 : }
2224 : }
2225 : }
2226 : std::set<NBEdge*> seen;
2227 : std::set<NBEdge*> check;
2228 12348 : for (const auto& item : myNodes) {
2229 32956 : for (NBEdge* edge : item.second->getOutgoingEdges()) {
2230 : if (edge->getSignalPosition() != Position::INVALID) {
2231 : check.insert(edge);
2232 : seen.insert(edge);
2233 : #ifdef DEBUG_GUESSSIGNALS
2234 : if (DEBUGCOND(edge->getSignalNode()) || true) {
2235 : std::cout << " primary signalPosition edge=" << edge->getID() << " pos=" << edge->getSignalPosition() << "\n";
2236 : }
2237 : #endif
2238 : }
2239 : }
2240 : }
2241 : // propagate signal position until the next real intersection
2242 1137 : while (check.size() > 0) {
2243 1091 : NBEdge* const edge = *check.begin();
2244 : check.erase(check.begin());
2245 : seen.insert(edge);
2246 : NBNode* const nextNode = edge->getToNode();
2247 1091 : if (nextNode->geometryLike() && !nextNode->isTLControlled()) {
2248 523 : for (NBEdge* const outEdge : nextNode->getOutgoingEdges()) {
2249 : if (seen.count(outEdge) == 0) {
2250 : outEdge->setSignalPosition(edge->getSignalPosition(), edge->getSignalNode());
2251 : #ifdef DEBUG_GUESSSIGNALS
2252 : if (DEBUGCOND(edge->getSignalNode()) || true) {
2253 : std::cout << " setSignalPosition edge=" << outEdge->getID() << " pos=" << edge->getSignalPosition() << "\n";
2254 : }
2255 : #endif
2256 : check.insert(outEdge);
2257 : }
2258 : }
2259 : }
2260 : }
2261 :
2262 : // check which nodes should be controlled
2263 92 : const int slack = oc.getInt("tls.guess-signals.slack");
2264 12348 : for (std::map<std::string, NBNode*>::const_iterator i = myNodes.begin(); i != myNodes.end(); ++i) {
2265 12302 : NBNode* node = i->second;
2266 1 : if (myUnsetTLS.count(node) != 0) {
2267 : continue;
2268 : }
2269 : const EdgeVector& incoming = node->getIncomingEdges();
2270 : const EdgeVector& outgoing = node->getOutgoingEdges();
2271 11958 : if (!node->isTLControlled() && incoming.size() > 1 && !node->geometryLike()
2272 5292 : && !NBNodeTypeComputer::isRailwayNode(node)
2273 17379 : && node->getType() != SumoXMLNodeType::RAIL_CROSSING) {
2274 : std::vector<const NBNode*> signals;
2275 : int foundSignals = 0;
2276 : int missingSignals = 0;
2277 : // check if there is a signal at every incoming edge
2278 12151 : for (EdgeVector::const_iterator it_i = incoming.begin(); it_i != incoming.end(); ++it_i) {
2279 9371 : const NBEdge* inEdge = *it_i;
2280 9371 : if (inEdge->getSignalOffset() == NBEdge::UNSPECIFIED_SIGNAL_OFFSET) {
2281 9042 : if ((inEdge->getPermissions() & SVC_PASSENGER) != 0) {
2282 : #ifdef DEBUG_GUESSSIGNALS
2283 : if (DEBUGCOND(node)) {
2284 : std::cout << " noTLS, edge=" << inEdge->getID() << "\n";
2285 : }
2286 : #endif
2287 2182 : missingSignals++;
2288 2182 : if (missingSignals > slack) {
2289 : break;
2290 : }
2291 : }
2292 : } else {
2293 329 : foundSignals++;
2294 : }
2295 : }
2296 : missingSignals = 0;
2297 : int foundSignalsAtDist = 0;
2298 4958 : if (foundSignals > 1 && missingSignals <= slack && missingSignals < foundSignals) {
2299 57 : node->updateSurroundingGeometry();
2300 : // check if all signals are within the required distance
2301 : // (requires detailed geometry computation)
2302 237 : for (EdgeVector::const_iterator it_i = incoming.begin(); it_i != incoming.end(); ++it_i) {
2303 189 : const NBEdge* inEdge = *it_i;
2304 189 : if (inEdge->getSignalOffset() == NBEdge::UNSPECIFIED_SIGNAL_OFFSET || inEdge->getSignalOffset() > signalDist) {
2305 19 : if ((inEdge->getPermissions() & SVC_PASSENGER) != 0) {
2306 : #ifdef DEBUG_GUESSSIGNALS
2307 : if (DEBUGCOND(node)) {
2308 : std::cout << " noTLS, edge=" << inEdge->getID() << " offset=" << inEdge->getSignalOffset() << " tlsPos=" << inEdge->getSignalPosition() << "\n";
2309 : }
2310 : #endif
2311 9 : missingSignals++;
2312 9 : if (missingSignals > slack) {
2313 : break;
2314 : }
2315 : }
2316 : } else {
2317 170 : foundSignalsAtDist++;
2318 : }
2319 180 : const NBNode* signal = inEdge->getSignalNode();
2320 180 : if (signal != nullptr) {
2321 12 : signals.push_back(signal);
2322 : }
2323 : }
2324 : // outgoing edges may be tagged with pedestrian crossings. These
2325 : // should also be merged into the main TLS
2326 243 : for (const NBEdge* outEdge : outgoing) {
2327 186 : NBNode* cand = outEdge->getToNode();
2328 186 : if (cand->isTLControlled() && cand->geometryLike() && outEdge->getLength() <= signalDist) {
2329 : #ifdef DEBUG_GUESSSIGNALS
2330 : if (DEBUGCOND(node)) {
2331 : std::cout << " node=" << node->getID() << " outEdge=" << outEdge->getID() << " signalNode=" << cand->getID() << " len=" << outEdge->getLength() << "\n";
2332 : }
2333 : #endif
2334 1 : signals.push_back(cand);
2335 : }
2336 : }
2337 : }
2338 4958 : if (foundSignalsAtDist > 1 && missingSignals <= slack && missingSignals < foundSignalsAtDist) {
2339 61 : for (const NBNode* s : signals) {
2340 : std::set<NBTrafficLightDefinition*> tls = s->getControllingTLS();
2341 13 : const_cast<NBNode*>(s)->reinit(s->getPosition(), SumoXMLNodeType::PRIORITY);
2342 24 : for (std::set<NBTrafficLightDefinition*>::iterator k = tls.begin(); k != tls.end(); ++k) {
2343 22 : tlc.removeFully(s->getID());
2344 : }
2345 : }
2346 : //if (true) std::cout << " node=" << node->getID() << " signals=" << toString(signals) << "\n";
2347 48 : NBTrafficLightDefinition* tlDef = new NBOwnTLDef("GS_" + node->getID(), node, 0, type);
2348 : // @todo patch endOffset for all incoming lanes according to the signal positions
2349 48 : if (!tlc.insert(tlDef)) {
2350 : // actually, nothing should fail here
2351 0 : WRITE_WARNINGF(TL("Could not build joined tls '%'."), node->getID());
2352 0 : delete tlDef;
2353 : return;
2354 : }
2355 : }
2356 4958 : }
2357 : }
2358 : }
2359 :
2360 : // guess joined tls first, if wished
2361 4366 : if (oc.getBool("tls.guess.joining")) {
2362 : // get node clusters
2363 : NodeClusters cands;
2364 8 : generateNodeClusters(oc.getFloat("tls.join-dist"), cands);
2365 : // check these candidates (clusters) whether they should be controlled by a tls
2366 38 : for (NodeClusters::iterator i = cands.begin(); i != cands.end();) {
2367 : NodeSet& c = (*i);
2368 : // regard only junctions which are not yet controlled and are not
2369 : // forbidden to be controlled
2370 245 : for (NodeSet::iterator j = c.begin(); j != c.end();) {
2371 211 : if ((*j)->isTLControlled() || myUnsetTLS.count(*j) != 0) {
2372 : c.erase(j++);
2373 : } else {
2374 : ++j;
2375 : }
2376 : }
2377 : // check whether the cluster should be controlled
2378 : // to avoid gigantic clusters, assume that at most 4 nodes should be needed for a guessed-joined-tls
2379 50 : if (c.size() == 0 || !shouldBeTLSControlled(c, laneSpeedThreshold * (double)c.size() / MIN2((double)c.size(), 4.))) {
2380 : i = cands.erase(i);
2381 : } else {
2382 : ++i;
2383 : }
2384 : }
2385 : // cands now only contain sets of junctions that shall be joined into being tls-controlled
2386 14 : for (auto nodeSet : cands) {
2387 : std::vector<NBNode*> nodes;
2388 53 : for (NBNode* node : nodeSet) {
2389 43 : nodes.push_back(node);
2390 : myGuessedTLS.insert(node);
2391 : }
2392 10 : const std::string& id = createClusterId(nodeSet, "joinedG_");
2393 10 : NBTrafficLightDefinition* tlDef = new NBOwnTLDef(id, nodes, 0, type);
2394 10 : if (!tlc.insert(tlDef)) {
2395 : // actually, nothing should fail here
2396 0 : WRITE_WARNING(TL("Could not build guessed, joined tls."));
2397 0 : delete tlDef;
2398 : return;
2399 : }
2400 10 : }
2401 4 : }
2402 :
2403 : // guess single tls
2404 4366 : if (oc.getBool("tls.guess")) {
2405 922 : for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2406 902 : NBNode* cur = (*i).second;
2407 : // do nothing if already is tl-controlled
2408 902 : if (cur->isTLControlled()) {
2409 760 : continue;
2410 : }
2411 : // do nothing if in the list of explicit non-controlled junctions
2412 1 : if (myUnsetTLS.count(cur) != 0) {
2413 1 : continue;
2414 : }
2415 : NodeSet c;
2416 : c.insert(cur);
2417 831 : if (!shouldBeTLSControlled(c, laneSpeedThreshold) || cur->geometryLike()) {
2418 : continue;
2419 : }
2420 284 : setAsTLControlled(cur, tlc, type);
2421 : myGuessedTLS.insert(cur);
2422 : }
2423 : }
2424 : }
2425 :
2426 :
2427 : void
2428 2182 : NBNodeCont::recheckGuessedTLS(NBTrafficLightLogicCont& tlc) {
2429 : std::set<NBTrafficLightDefinition*> recompute;
2430 2367 : for (NBNode* node : myGuessedTLS) {
2431 185 : if (!node->hasConflict() || !recheckTLSThreshold(node)) {
2432 : const std::set<NBTrafficLightDefinition*>& tlDefs = node->getControllingTLS();
2433 21 : recompute.insert(tlDefs.begin(), tlDefs.end());
2434 21 : node->removeTrafficLights(true);
2435 49 : for (NBEdge* edge : node->getIncomingEdges()) {
2436 28 : edge->clearControllingTLInformation();
2437 : }
2438 : }
2439 : }
2440 2194 : for (NBTrafficLightDefinition* def : recompute) {
2441 12 : if (def->getNodes().size() == 0) {
2442 10 : tlc.removeFully(def->getID());
2443 : } else {
2444 7 : def->setParticipantsInformation();
2445 7 : def->setTLControllingInformation();
2446 7 : tlc.computeSingleLogic(OptionsCont::getOptions(), def);
2447 : }
2448 : }
2449 2182 : }
2450 :
2451 :
2452 : bool
2453 166 : NBNodeCont::recheckTLSThreshold(NBNode* node) {
2454 166 : if (!node->isTLControlled()) {
2455 : return false;
2456 : }
2457 166 : if ((*node->getControllingTLS().begin())->getNodes().size() != 1) {
2458 : // unable to perform check for a joined tls
2459 : return true;
2460 : }
2461 : NodeSet c;
2462 : c.insert(node);
2463 127 : const double laneSpeedThreshold = OptionsCont::getOptions().getFloat("tls.guess.threshold");
2464 127 : return shouldBeTLSControlled(c, laneSpeedThreshold, true);
2465 : }
2466 :
2467 :
2468 : void
2469 2182 : NBNodeCont::computeKeepClear() {
2470 61926 : for (const auto& item : myNodes) {
2471 59744 : item.second->computeKeepClear();
2472 : }
2473 2182 : }
2474 :
2475 :
2476 : void
2477 36 : NBNodeCont::joinTLS(NBTrafficLightLogicCont& tlc, double maxdist) {
2478 72 : const std::vector<std::string> excludeList = OptionsCont::getOptions().getStringVector("tls.join-exclude");
2479 38 : for (const std::string& tlsID : excludeList) {
2480 2 : if (!tlc.exist(tlsID, false)) {
2481 3 : WRITE_WARNINGF("Unknown tls ID '%' in option tls.join-exclude", tlsID);
2482 : }
2483 : }
2484 36 : std::set<std::string> exclude(excludeList.begin(), excludeList.end());
2485 : NodeClusters cands;
2486 36 : generateNodeClusters(maxdist, cands);
2487 656 : for (NodeSet& c : cands) {
2488 2392 : for (NodeSet::iterator j = c.begin(); j != c.end();) {
2489 1772 : if (!(*j)->isTLControlled() || exclude.count((*(*j)->getControllingTLS().begin())->getID()) != 0) {
2490 : c.erase(j++);
2491 : } else {
2492 : ++j;
2493 : }
2494 : }
2495 620 : if (c.size() < 2 || onlyCrossings(c) || customTLID(c)) {
2496 572 : continue;
2497 : }
2498 : // figure out type of the joined TLS
2499 : Position dummyPos;
2500 48 : bool dummySetTL = false;
2501 48 : std::string id = "joinedS_"; // prefix (see #3871)
2502 : TrafficLightType type;
2503 48 : SumoXMLNodeType nodeType = SumoXMLNodeType::UNKNOWN;
2504 96 : analyzeCluster(c, id, dummyPos, dummySetTL, type, nodeType);
2505 175 : for (NBNode* j : c) {
2506 : std::set<NBTrafficLightDefinition*> tls = j->getControllingTLS();
2507 127 : j->removeTrafficLights();
2508 254 : for (NBTrafficLightDefinition* k : tls) {
2509 254 : tlc.removeFully(k->getID());
2510 : }
2511 : }
2512 : std::vector<NBNode*> nodes;
2513 175 : for (NBNode* j : c) {
2514 127 : nodes.push_back(j);
2515 : }
2516 48 : NBTrafficLightDefinition* tlDef = new NBOwnTLDef(id, nodes, 0, type);
2517 48 : if (!tlc.insert(tlDef)) {
2518 : // actually, nothing should fail here
2519 0 : WRITE_WARNING(TL("Could not build a joined tls."));
2520 0 : delete tlDef;
2521 : return;
2522 : }
2523 48 : }
2524 72 : }
2525 :
2526 :
2527 : void
2528 150 : NBNodeCont::setAsTLControlled(NBNode* node, NBTrafficLightLogicCont& tlc,
2529 : TrafficLightType type, std::string id) {
2530 150 : if (id == "") {
2531 : id = node->getID();
2532 : }
2533 150 : NBTrafficLightDefinition* tlDef = new NBOwnTLDef(id, node, 0, type);
2534 150 : if (!tlc.insert(tlDef)) {
2535 : // actually, nothing should fail here
2536 0 : WRITE_WARNINGF(TL("Building a tl-logic for junction '%' twice is not possible."), id);
2537 0 : delete tlDef;
2538 0 : return;
2539 : }
2540 : }
2541 :
2542 :
2543 : // -----------
2544 : void
2545 2183 : NBNodeCont::computeLanes2Lanes() {
2546 61931 : for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2547 59748 : (*i).second->computeLanes2Lanes();
2548 : }
2549 2183 : }
2550 :
2551 :
2552 : // computes the "wheel" of incoming and outgoing edges for every node
2553 : void
2554 2182 : NBNodeCont::computeLogics(const NBEdgeCont& ec) {
2555 61926 : for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2556 59744 : (*i).second->computeLogic(ec);
2557 : }
2558 2182 : }
2559 :
2560 :
2561 : void
2562 2182 : NBNodeCont::computeLogics2(const NBEdgeCont& ec, OptionsCont& oc) {
2563 : std::set<NBNode*> roundaboutNodes;
2564 2182 : const bool checkLaneFoesAll = oc.getBool("check-lane-foes.all");
2565 2182 : const bool checkLaneFoesRoundabout = !checkLaneFoesAll && oc.getBool("check-lane-foes.roundabout");
2566 2182 : if (checkLaneFoesRoundabout) {
2567 2177 : const std::set<EdgeSet>& roundabouts = ec.getRoundabouts();
2568 2271 : for (std::set<EdgeSet>::const_iterator i = roundabouts.begin(); i != roundabouts.end(); ++i) {
2569 550 : for (EdgeSet::const_iterator j = (*i).begin(); j != (*i).end(); ++j) {
2570 456 : roundaboutNodes.insert((*j)->getToNode());
2571 : }
2572 : }
2573 : }
2574 61926 : for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2575 59744 : const bool checkLaneFoes = checkLaneFoesAll || (checkLaneFoesRoundabout && roundaboutNodes.count((*i).second) > 0);
2576 59744 : (*i).second->computeLogic2(checkLaneFoes);
2577 : }
2578 2182 : }
2579 :
2580 :
2581 : void
2582 2483 : NBNodeCont::clear() {
2583 62950 : for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2584 60467 : delete ((*i).second);
2585 : }
2586 : myNodes.clear();
2587 11447 : for (auto& item : myExtractedNodes) {
2588 8964 : delete item.second;
2589 : }
2590 : myExtractedNodes.clear();
2591 2483 : }
2592 :
2593 :
2594 : std::string
2595 0 : NBNodeCont::getFreeID() {
2596 0 : int counter = 0;
2597 0 : std::string freeID = "SUMOGenerated" + toString<int>(counter);
2598 : // While there is a node with id equal to freeID
2599 0 : while (retrieve(freeID) != nullptr) {
2600 : // update counter and generate a new freeID
2601 0 : counter++;
2602 0 : freeID = "SUMOGenerated" + toString<int>(counter);
2603 : }
2604 0 : return freeID;
2605 : }
2606 :
2607 :
2608 : void
2609 2341 : NBNodeCont::computeNodeShapes(double mismatchThreshold) {
2610 85335 : for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2611 82994 : (*i).second->computeNodeShape(mismatchThreshold);
2612 : }
2613 2341 : }
2614 :
2615 :
2616 : void
2617 2180 : NBNodeCont::printBuiltNodesStatistics() const {
2618 2180 : WRITE_MESSAGE(TL("-----------------------------------------------------"));
2619 2180 : WRITE_MESSAGE(TL("Summary:"));
2620 :
2621 2180 : int numUnregulatedJunctions = 0;
2622 2180 : int numDeadEndJunctions = 0;
2623 2180 : int numTrafficLightJunctions = 0;
2624 2180 : int numPriorityJunctions = 0;
2625 2180 : int numRightBeforeLeftJunctions = 0;
2626 2180 : int numLeftBeforeRightJunctions = 0;
2627 2180 : int numAllWayStopJunctions = 0;
2628 2180 : int numZipperJunctions = 0;
2629 2180 : int numDistrictJunctions = 0;
2630 2180 : int numRailCrossing = 0;
2631 2180 : int numRailSignals = 0;
2632 61913 : for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2633 59733 : switch ((*i).second->getType()) {
2634 113 : case SumoXMLNodeType::NOJUNCTION:
2635 113 : ++numUnregulatedJunctions;
2636 113 : break;
2637 15346 : case SumoXMLNodeType::DEAD_END:
2638 15346 : ++numDeadEndJunctions;
2639 15346 : break;
2640 2750 : case SumoXMLNodeType::TRAFFIC_LIGHT:
2641 : case SumoXMLNodeType::TRAFFIC_LIGHT_RIGHT_ON_RED:
2642 : case SumoXMLNodeType::TRAFFIC_LIGHT_NOJUNCTION:
2643 2750 : ++numTrafficLightJunctions;
2644 2750 : break;
2645 35710 : case SumoXMLNodeType::PRIORITY:
2646 : case SumoXMLNodeType::PRIORITY_STOP:
2647 35710 : ++numPriorityJunctions;
2648 35710 : break;
2649 4012 : case SumoXMLNodeType::RIGHT_BEFORE_LEFT:
2650 4012 : ++numRightBeforeLeftJunctions;
2651 4012 : break;
2652 13 : case SumoXMLNodeType::LEFT_BEFORE_RIGHT:
2653 13 : ++numLeftBeforeRightJunctions;
2654 13 : break;
2655 6 : case SumoXMLNodeType::ALLWAY_STOP:
2656 6 : ++numAllWayStopJunctions;
2657 6 : break;
2658 94 : case SumoXMLNodeType::ZIPPER:
2659 94 : ++numZipperJunctions;
2660 94 : break;
2661 0 : case SumoXMLNodeType::DISTRICT:
2662 0 : ++numDistrictJunctions;
2663 0 : break;
2664 167 : case SumoXMLNodeType::RAIL_CROSSING:
2665 167 : ++numRailCrossing;
2666 167 : break;
2667 1522 : case SumoXMLNodeType::RAIL_SIGNAL:
2668 1522 : ++numRailSignals;
2669 1522 : break;
2670 : case SumoXMLNodeType::UNKNOWN:
2671 : // should not happen
2672 : break;
2673 : default:
2674 : break;
2675 : }
2676 : }
2677 2180 : WRITE_MESSAGE(TL(" Node type statistics:"));
2678 4360 : WRITE_MESSAGE(" Unregulated junctions : " + toString(numUnregulatedJunctions));
2679 2180 : if (numDeadEndJunctions > 0) {
2680 4209 : WRITE_MESSAGE(" Dead-end junctions : " + toString(numDeadEndJunctions));
2681 : }
2682 4360 : WRITE_MESSAGE(" Priority junctions : " + toString(numPriorityJunctions));
2683 4360 : WRITE_MESSAGE(" Right-before-left junctions : " + toString(numRightBeforeLeftJunctions));
2684 2180 : if (numLeftBeforeRightJunctions > 0) {
2685 24 : WRITE_MESSAGE(" Left-before-right junctions : " + toString(numLeftBeforeRightJunctions));
2686 : }
2687 2180 : if (numTrafficLightJunctions > 0) {
2688 2034 : WRITE_MESSAGE(" Traffic light junctions : " + toString(numTrafficLightJunctions));
2689 : }
2690 2180 : if (numAllWayStopJunctions > 0) {
2691 6 : WRITE_MESSAGE(" All-way stop junctions : " + toString(numAllWayStopJunctions));
2692 : }
2693 2180 : if (numZipperJunctions > 0) {
2694 84 : WRITE_MESSAGE(" Zipper-merge junctions : " + toString(numZipperJunctions));
2695 : }
2696 2180 : if (numRailCrossing > 0) {
2697 78 : WRITE_MESSAGE(" Rail crossing junctions : " + toString(numRailCrossing));
2698 : }
2699 2180 : if (numRailSignals > 0) {
2700 189 : WRITE_MESSAGE(" Rail signal junctions : " + toString(numRailSignals));
2701 : }
2702 2180 : if (numDistrictJunctions > 0) {
2703 0 : WRITE_MESSAGE(" District junctions : " + toString(numDistrictJunctions));
2704 : }
2705 : const GeoConvHelper& geoConvHelper = GeoConvHelper::getProcessing();
2706 2180 : WRITE_MESSAGE(TL(" Network boundaries:"));
2707 4360 : WRITE_MESSAGE(" Original boundary : " + toString(geoConvHelper.getOrigBoundary()));
2708 4360 : WRITE_MESSAGE(" Applied offset : " + toString(geoConvHelper.getOffsetBase()));
2709 4360 : WRITE_MESSAGE(" Converted boundary : " + toString(geoConvHelper.getConvBoundary()));
2710 2180 : WRITE_MESSAGE(TL("-----------------------------------------------------"));
2711 2180 : }
2712 :
2713 :
2714 : std::vector<std::string>
2715 75 : NBNodeCont::getAllNames() const {
2716 : std::vector<std::string> ret;
2717 15452 : for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); ++i) {
2718 15377 : ret.push_back((*i).first);
2719 : }
2720 75 : return ret;
2721 0 : }
2722 :
2723 :
2724 : void
2725 0 : NBNodeCont::addPrefix(const std::string& prefix) {
2726 : // make a copy of node containers
2727 : const auto nodeContainerCopy = myNodes;
2728 : myNodes.clear();
2729 0 : for (const auto& node : nodeContainerCopy) {
2730 0 : node.second->setID(prefix + node.second->getID());
2731 0 : myNodes[node.second->getID()] = node.second;
2732 : }
2733 0 : }
2734 :
2735 :
2736 : void
2737 83 : NBNodeCont::rename(NBNode* node, const std::string& newID) {
2738 : if (myNodes.count(newID) != 0) {
2739 0 : throw ProcessError(TLF("Attempt to rename node using existing id '%'", newID));
2740 : }
2741 : myNodes.erase(node->getID());
2742 83 : node->setID(newID);
2743 83 : myNodes[newID] = node;
2744 83 : }
2745 :
2746 :
2747 : void
2748 56 : NBNodeCont::discardTrafficLights(NBTrafficLightLogicCont& tlc, bool geometryLike) {
2749 19135 : for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); ++i) {
2750 19079 : NBNode* node = i->second;
2751 19079 : if (node->isTLControlled() && (!geometryLike || node->geometryLike())) {
2752 : // make a copy of tldefs
2753 : const std::set<NBTrafficLightDefinition*> tldefs = node->getControllingTLS();
2754 958 : if (geometryLike && (*tldefs.begin())->getNodes().size() > 1) {
2755 : // do not remove joined tls when only removing geometry-like tls
2756 1 : continue;
2757 : }
2758 957 : if (node->getCrossings().size() > 0) {
2759 : // keep controlled pedestrian crossings
2760 5 : continue;
2761 : }
2762 : // record signal location
2763 2299 : for (NBEdge* edge : node->getOutgoingEdges()) {
2764 : edge->setSignalPosition(node->getPosition(), nullptr);
2765 : #ifdef DEBUG_GUESSSIGNALS
2766 : std::cout << " discard-simple " << node->getID() << " edge=" << edge->getID() << " pos=" << edge->getSignalPosition() << "\n";
2767 : #endif
2768 : }
2769 1905 : for (std::set<NBTrafficLightDefinition*>::const_iterator it = tldefs.begin(); it != tldefs.end(); ++it) {
2770 953 : NBTrafficLightDefinition* tlDef = *it;
2771 953 : node->removeTrafficLight(tlDef);
2772 953 : tlc.extract(tlDef);
2773 : }
2774 952 : SumoXMLNodeType newType = NBNodeTypeComputer::isRailwayNode(node) ? SumoXMLNodeType::RAIL_SIGNAL : SumoXMLNodeType::UNKNOWN;
2775 952 : node->reinit(node->getPosition(), newType);
2776 : }
2777 : }
2778 56 : }
2779 :
2780 :
2781 : void
2782 1 : NBNodeCont::discardRailSignals() {
2783 35 : for (auto& item : myNodes) {
2784 34 : NBNode* node = item.second;
2785 34 : if (node->getType() == SumoXMLNodeType::RAIL_SIGNAL) {
2786 5 : node->reinit(node->getPosition(), SumoXMLNodeType::PRIORITY);
2787 : }
2788 : }
2789 1 : }
2790 :
2791 :
2792 : int
2793 2183 : NBNodeCont::remapIDs(bool numericaIDs, bool reservedIDs, bool keptIDs, const std::string& prefix, NBTrafficLightLogicCont& tlc) {
2794 2183 : bool startGiven = !OptionsCont::getOptions().isDefault("numerical-ids.node-start");
2795 2183 : if (!numericaIDs && !reservedIDs && prefix == "" && !startGiven) {
2796 : return 0;
2797 : }
2798 : std::vector<std::string> avoid;
2799 72 : if (startGiven) {
2800 6 : avoid.push_back(toString(OptionsCont::getOptions().getInt("numerical-ids.node-start") - 1));
2801 : } else {
2802 69 : avoid = getAllNames();
2803 : }
2804 : std::set<std::string> reserve;
2805 72 : if (reservedIDs) {
2806 4 : NBHelpers::loadPrefixedIDsFomFile(OptionsCont::getOptions().getString("reserved-ids"), "node:", reserve); // backward compatibility
2807 4 : NBHelpers::loadPrefixedIDsFomFile(OptionsCont::getOptions().getString("reserved-ids"), "junction:", reserve); // selection format
2808 2 : avoid.insert(avoid.end(), reserve.begin(), reserve.end());
2809 : }
2810 144 : IDSupplier idSupplier("", avoid);
2811 : NodeSet toChange;
2812 15130 : for (NodeCont::iterator it = myNodes.begin(); it != myNodes.end(); it++) {
2813 15058 : if (startGiven) {
2814 36 : toChange.insert(it->second);
2815 36 : continue;
2816 : }
2817 15022 : if (numericaIDs) {
2818 : try {
2819 14942 : StringUtils::toLong(it->first);
2820 522 : } catch (NumberFormatException&) {
2821 522 : toChange.insert(it->second);
2822 522 : }
2823 : }
2824 15022 : if (reservedIDs && reserve.count(it->first) > 0) {
2825 2 : toChange.insert(it->second);
2826 : }
2827 : }
2828 : std::set<std::string> keep;
2829 72 : if (keptIDs) {
2830 4 : NBHelpers::loadPrefixedIDsFomFile(OptionsCont::getOptions().getString("kept-ids"), "node:", keep); // backward compatibility
2831 4 : NBHelpers::loadPrefixedIDsFomFile(OptionsCont::getOptions().getString("kept-ids"), "junction:", keep); // selection format
2832 7 : for (auto it = toChange.begin(); it != toChange.end();) {
2833 5 : if (keep.count((*it)->getID()) != 0) {
2834 : it = toChange.erase(it++);
2835 : } else {
2836 : it++;
2837 : }
2838 : }
2839 : }
2840 144 : const bool origNames = OptionsCont::getOptions().getBool("output.original-names");
2841 631 : for (NBNode* node : toChange) {
2842 : myNodes.erase(node->getID());
2843 : }
2844 631 : for (NBNode* node : toChange) {
2845 1551 : if (origNames && node->getParameter(SUMO_PARAM_ORIGID) == "") {
2846 480 : node->setParameter(SUMO_PARAM_ORIGID, node->getID());
2847 : }
2848 1118 : node->setID(idSupplier.getNext());
2849 651 : for (NBTrafficLightDefinition* tlDef : node->getControllingTLS()) {
2850 92 : tlc.rename(tlDef, node->getID());
2851 : }
2852 559 : myNodes[node->getID()] = node;
2853 : }
2854 72 : if (prefix.empty()) {
2855 62 : return (int)toChange.size();
2856 : } else {
2857 : int renamed = 0;
2858 : // make a copy because we will modify the map
2859 : auto oldNodes = myNodes;
2860 95 : for (auto item : oldNodes) {
2861 170 : if (!StringUtils::startsWith(item.first, prefix) && keep.count(item.first) == 0) {
2862 83 : rename(item.second, prefix + item.first);
2863 91 : for (NBTrafficLightDefinition* tlDef : item.second->getControllingTLS()) {
2864 16 : if (!StringUtils::startsWith(tlDef->getID(), prefix)) {
2865 12 : tlc.rename(tlDef, prefix + tlDef->getID());
2866 : }
2867 : }
2868 83 : renamed++;
2869 : }
2870 : }
2871 : return renamed;
2872 : }
2873 144 : }
2874 :
2875 :
2876 : int
2877 2 : NBNodeCont::guessFringe() {
2878 : // guess outer fringe by topology and being on the pareto-boundary
2879 : NodeSet topRightFront;
2880 : NodeSet topLeftFront;
2881 : NodeSet bottomRightFront;
2882 : NodeSet bottomLeftFront;
2883 67 : for (const auto& item : myNodes) {
2884 65 : paretoCheck(item.second, topRightFront, 1, 1);
2885 65 : paretoCheck(item.second, topLeftFront, -1, 1);
2886 65 : paretoCheck(item.second, bottomRightFront, 1, -1);
2887 65 : paretoCheck(item.second, bottomLeftFront, -1, -1);
2888 : }
2889 : NodeSet front;
2890 2 : front.insert(topRightFront.begin(), topRightFront.end());
2891 2 : front.insert(topLeftFront.begin(), topLeftFront.end());
2892 2 : front.insert(bottomRightFront.begin(), bottomRightFront.end());
2893 2 : front.insert(bottomLeftFront.begin(), bottomLeftFront.end());
2894 : int numFringe = 0;
2895 19 : for (NBNode* n : front) {
2896 17 : const int in = (int)n->getIncomingEdges().size();
2897 17 : const int out = (int)n->getOutgoingEdges().size();
2898 17 : if ((in <= 1 && out <= 1) &&
2899 12 : (in == 0 || out == 0
2900 8 : || n->getIncomingEdges().front()->isTurningDirectionAt(n->getOutgoingEdges().front()))) {
2901 : n->setFringeType(FringeType::OUTER);
2902 9 : numFringe++;
2903 : }
2904 : }
2905 : // guess outer fringe by topology and speed
2906 4 : const double speedThreshold = OptionsCont::getOptions().getFloat("fringe.guess.speed-threshold");
2907 67 : for (const auto& item : myNodes) {
2908 65 : NBNode* n = item.second;
2909 17 : if (front.count(n) != 0) {
2910 17 : continue;
2911 : }
2912 48 : if (n->getEdges().size() == 1 && n->getEdges().front()->getSpeed() > speedThreshold) {
2913 : n->setFringeType(FringeType::OUTER);
2914 2 : numFringe++;
2915 : }
2916 : }
2917 2 : return numFringe;
2918 : }
2919 :
2920 :
2921 : void
2922 260 : NBNodeCont::paretoCheck(NBNode* node, NodeSet& frontier, int xSign, int ySign) {
2923 260 : const double x = node->getPosition().x() * xSign;
2924 260 : const double y = node->getPosition().y() * ySign;
2925 : std::vector<NBNode*> dominated;
2926 556 : for (NBNode* fn : frontier) {
2927 484 : const double x2 = fn->getPosition().x() * xSign;
2928 484 : const double y2 = fn->getPosition().y() * ySign;
2929 484 : if (x2 >= x && y2 >= y) {
2930 188 : return;
2931 296 : } else if (x2 <= x && y2 <= y) {
2932 52 : dominated.push_back(fn);
2933 : }
2934 : }
2935 : frontier.insert(node);
2936 124 : for (NBNode* r : dominated) {
2937 : frontier.erase(r);
2938 : }
2939 260 : }
2940 :
2941 :
2942 : void
2943 2218 : NBNodeCont::applyConditionalDefaults() {
2944 67773 : for (const auto& item : myNodes) {
2945 65555 : NBNode* n = item.second;
2946 65555 : if (n->isTLControlled() && n->getRightOfWay() == RightOfWay::DEFAULT) {
2947 : bool hasNEMA = false;
2948 6328 : for (NBTrafficLightDefinition* tl : n->getControllingTLS()) {
2949 3178 : if (tl->getType() == TrafficLightType::NEMA) {
2950 : hasNEMA = true;
2951 : break;
2952 : }
2953 : }
2954 3164 : if (hasNEMA) {
2955 : // NEMA controller defaults to allway_stop behavior when switched off
2956 : n->setRightOfWay(RightOfWay::ALLWAYSTOP);
2957 : }
2958 : }
2959 : }
2960 2218 : }
2961 :
2962 :
2963 : bool
2964 2183 : NBNodeCont::resetNodeShapes() {
2965 : bool hadShapes = false;
2966 61729 : for (const auto& item : myNodes) {
2967 59546 : if (item.second->getShape().size() > 0 && !item.second->hasCustomShape()) {
2968 : hadShapes = true;
2969 : item.second->resetShape();
2970 : }
2971 : }
2972 2183 : return hadShapes;
2973 : }
2974 : /****************************************************************************/
|
