Eclipse SUMO - Simulation of Urban MObility
NBNodeCont.cpp
Go to the documentation of this file.
1 /****************************************************************************/
2 // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo
3 // Copyright (C) 2001-2020 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 /****************************************************************************/
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>
33 #include <utils/geom/Boundary.h>
34 #include <utils/geom/GeomHelper.h>
39 #include <utils/common/StdDefs.h>
40 #include <utils/common/ToString.h>
46 #include "NBHelpers.h"
47 #include "NBAlgorithms.h"
48 #include "NBDistrict.h"
49 #include "NBEdgeCont.h"
51 #include "NBOwnTLDef.h"
52 #include "NBNodeCont.h"
53 #include "NBPTStopCont.h"
54 #include "NBPTLineCont.h"
55 #include "NBParking.h"
56 
57 // ===========================================================================
58 // Algorithm constants
59 // ===========================================================================
60 #define MAX_SLIPLANE_LENGTH 1000
61 
62 // ===========================================================================
63 // Debug Flags
64 // ===========================================================================
65 
66 //#define DEBUG_JOINJUNCTIONS
67 //#define DEBUG_GUESSSIGNALS
68 #define DEBUGNODEID "3513423881"
69 #define DEBUGNODEID2 ""
70 //#define DEBUGNODEID "5548037023"
71 #define DEBUGCOND(obj) ((obj) != 0 && ((obj)->getID() == DEBUGNODEID || (obj)->getID() == DEBUGNODEID2))
72 //#define DEBUGCOND(obj) (true)
73 
74 
75 // ===========================================================================
76 // method definitions
77 // ===========================================================================
79  : myInternalID(1) {
80 }
81 
82 
84  clear();
85 }
86 
87 
88 // ----------- Insertion/removal/retrieval of nodes
89 bool
90 NBNodeCont::insert(const std::string& id, const Position& position,
91  NBDistrict* district) {
92  NodeCont::iterator i = myNodes.find(id);
93  if (i != myNodes.end()) {
94  return false;
95  }
96  NBNode* node = new NBNode(id, position, district);
97  myNodes[id] = node;
98  const float pos[2] = {(float)position.x(), (float)position.y()};
99  myRTree.Insert(pos, pos, node);
100  return true;
101 }
102 
103 
104 bool
106  std::string id = node->getID();
107  NodeCont::iterator i = myNodes.find(id);
108  if (i != myNodes.end()) {
109  return false;
110  }
111  myNodes[id] = node;
112  const float pos[2] = {(float)node->getPosition().x(), (float)node->getPosition().y()};
113  myRTree.Insert(pos, pos, node);
114  return true;
115 }
116 
117 
118 NBNode*
119 NBNodeCont::retrieve(const std::string& id) const {
120  NodeCont::const_iterator i = myNodes.find(id);
121  if (i == myNodes.end()) {
122  return nullptr;
123  }
124  return (*i).second;
125 }
126 
127 
128 NBNode*
129 NBNodeCont::retrieve(const Position& position, const double offset) const {
130  const double extOffset = offset + POSITION_EPS;
131  const float cmin[2] = {(float)(position.x() - extOffset), (float)(position.y() - extOffset)};
132  const float cmax[2] = {(float)(position.x() + extOffset), (float)(position.y() + extOffset)};
133  std::set<const Named*> into;
134  Named::StoringVisitor sv(into);
135  myRTree.Search(cmin, cmax, sv);
136  for (const Named* namedNode : into) {
137  NBNode* node = const_cast<NBNode*>(dynamic_cast<const NBNode*>(namedNode));
138  if (fabs(node->getPosition().x() - position.x()) <= offset
139  &&
140  fabs(node->getPosition().y() - position.y()) <= offset) {
141  return node;
142  }
143  }
144  return nullptr;
145 }
146 
147 
148 bool
150  if (extract(node)) {
151  delete node;
152  return true;
153  } else {
154  return false;
155  }
156 }
157 
158 
159 bool
160 NBNodeCont::extract(NBNode* node, bool remember) {
161  NodeCont::iterator i = myNodes.find(node->getID());
162  if (i == myNodes.end()) {
163  return false;
164  }
165  myNodes.erase(i);
166  const float pos[2] = {(float)node->getPosition().x(), (float)node->getPosition().y()};
167  myRTree.Remove(pos, pos, node);
168  node->removeTrafficLights();
169  if (remember) {
170  myExtractedNodes[node->getID()] = node;
171  }
172  return true;
173 }
174 
175 
176 // ----------- Adapting the input
177 void
179  int no = 0;
180  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
181  no += (*i).second->removeSelfLoops(dc, ec, tc);
182  }
183  if (no != 0) {
184  WRITE_WARNING(toString(no) + " self-looping edge(s) removed.");
185  }
186 }
187 
188 
189 void
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  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  const EdgeVector& outgoing = (*i).second->getOutgoingEdges();
199  for (EdgeVector::const_iterator j = outgoing.begin(); j != outgoing.end(); j++) {
200  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  for (k = connectionCount.begin(); k != connectionCount.end(); k++) {
205  // possibly we do not have anything to join...
206  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  const EdgeVector& ev = (*k).second;
212  const NBEdge* const first = ev.front();
213  EdgeVector::const_iterator jci; // join candidate iterator
214  for (jci = ev.begin() + 1; jci != ev.end(); ++jci) {
215  const double relativeLengthDifference = fabs(first->getLoadedLength() - (*jci)->getLoadedLength()) / first->getLoadedLength();
216  if ((!first->isNearEnough2BeJoined2(*jci, distanceThreshold)) ||
217  (relativeLengthDifference > lengthThreshold) ||
218  (fabs(first->getSpeed() - (*jci)->getSpeed()) >= 0.01) || // output accuracy
219  (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  if (jci == ev.end()) {
227  ec.joinSameNodeConnectingEdges(dc, tlc, ev);
228  }
229  }
230  }
231 }
232 
233 
234 void
236  // Warn of isolated edges, i.e. a single edge with no connection to another edge
237  const std::vector<std::string>& edgeNames = ec.getAllNames();
238  for (std::vector<std::string>::const_iterator it = edgeNames.begin(); it != edgeNames.end(); ++it) {
239  // Test whether this node starts at a dead end, i.e. it has only one adjacent node
240  // to which an edge exists and from which an edge may come.
241  NBEdge* e = ec.retrieve(*it);
242  if (e == nullptr) {
243  continue;
244  }
245  NBNode* from = e->getFromNode();
246  const EdgeVector& outgoingEdges = from->getOutgoingEdges();
247  if (outgoingEdges.size() != 1) {
248  // At this node, several edges or no edge start; so, this node is no dead end.
249  continue;
250  }
251  const EdgeVector& incomingEdges = from->getIncomingEdges();
252  if (incomingEdges.size() > 1) {
253  // At this node, several edges end; so, this node is no dead end.
254  continue;
255  } else if (incomingEdges.size() == 1) {
256  NBNode* fromNodeOfIncomingEdge = incomingEdges[0]->getFromNode();
257  NBNode* toNodeOfOutgoingEdge = outgoingEdges[0]->getToNode();
258  if (fromNodeOfIncomingEdge != toNodeOfOutgoingEdge) {
259  // At this node, an edge ends which is not the inverse direction of
260  // the starting node.
261  continue;
262  }
263  }
264  // Now we know that the edge e starts a dead end.
265  // Next we test if the dead end is isolated, i.e. does not lead to a junction
266  bool hasJunction = false;
267  EdgeVector road;
268  NBEdge* eOld = nullptr;
269  NBNode* to;
270  NodeSet adjacentNodes;
271  do {
272  road.push_back(e);
273  eOld = e;
274  from = e->getFromNode();
275  to = e->getToNode();
276  const EdgeVector& outgoingEdgesOfToNode = to->getOutgoingEdges();
277  const EdgeVector& incomingEdgesOfToNode = to->getIncomingEdges();
278  adjacentNodes.clear();
279  for (EdgeVector::const_iterator itOfOutgoings = outgoingEdgesOfToNode.begin(); itOfOutgoings != outgoingEdgesOfToNode.end(); ++itOfOutgoings) {
280  if ((*itOfOutgoings)->getToNode() != from // The back path
281  && (*itOfOutgoings)->getToNode() != to // A loop / dummy edge
282  ) {
283  e = *itOfOutgoings; // Probably the next edge
284  }
285  adjacentNodes.insert((*itOfOutgoings)->getToNode());
286  }
287  for (EdgeVector::const_iterator itOfIncomings = incomingEdgesOfToNode.begin(); itOfIncomings != incomingEdgesOfToNode.end(); ++itOfIncomings) {
288  adjacentNodes.insert((*itOfIncomings)->getFromNode());
289  }
290  adjacentNodes.erase(to); // Omit loops
291  if (adjacentNodes.size() > 2) {
292  hasJunction = true;
293  }
294  } while (!hasJunction && eOld != e);
295  if (!hasJunction) {
296  std::string warningString;
297  for (EdgeVector::iterator roadIt = road.begin(); roadIt != road.end(); ++roadIt) {
298  if (roadIt == road.begin()) {
299  warningString += (*roadIt)->getID();
300  } else {
301  warningString += "," + (*roadIt)->getID();
302  }
303 
304  NBNode* fromNode = (*roadIt)->getFromNode();
305  NBNode* toNode = (*roadIt)->getToNode();
306  ec.erase(dc, *roadIt);
307  if (fromNode->getIncomingEdges().size() == 0 && fromNode->getOutgoingEdges().size() == 0) {
308  // Node is empty; can be removed
309  erase(fromNode);
310  }
311  if (toNode->getIncomingEdges().size() == 0 && toNode->getOutgoingEdges().size() == 0) {
312  // Node is empty; can be removed
313  erase(toNode);
314  }
315  }
316  WRITE_WARNINGF("Removed a road without junctions: %.", warningString);
317  }
318  }
319 }
320 
321 
322 void
324  std::vector<std::set<NBEdge*> > components;
325  // need to use ids here to have the same ordering on all platforms
326  std::set<std::string> edgesLeft;
327  for (std::map<std::string, NBEdge*>::const_iterator edgeIt = ec.begin(); edgeIt != ec.end(); ++edgeIt) {
328  edgesLeft.insert(edgeIt->first);
329  }
330  EdgeVector queue;
331  std::set<NBEdge*> toRemove;
332  while (!edgesLeft.empty()) {
333  queue.push_back(ec.getByID(*edgesLeft.begin()));
334  std::set<NBEdge*> component;
335  while (!queue.empty()) {
336  NBEdge* const e = queue.back();
337  queue.pop_back();
338  component.insert(e);
339  std::vector<EdgeVector> edgeLists;
340  edgeLists.push_back(e->getFromNode()->getOutgoingEdges());
341  edgeLists.push_back(e->getFromNode()->getIncomingEdges());
342  edgeLists.push_back(e->getToNode()->getOutgoingEdges());
343  edgeLists.push_back(e->getToNode()->getIncomingEdges());
344  for (std::vector<EdgeVector>::const_iterator listIt = edgeLists.begin(); listIt != edgeLists.end(); ++listIt) {
345  for (EdgeVector::const_iterator edgeIt = listIt->begin(); edgeIt != listIt->end(); ++edgeIt) {
346  std::set<std::string>::iterator leftIt = edgesLeft.find((*edgeIt)->getID());
347  if (leftIt != edgesLeft.end()) {
348  queue.push_back(*edgeIt);
349  edgesLeft.erase(leftIt);
350  }
351  }
352  }
353  }
354  std::vector<std::set<NBEdge*> >::iterator cIt;
355  for (cIt = components.begin(); cIt != components.end(); ++cIt) {
356  if (cIt->size() < component.size()) {
357  break;
358  }
359  }
360  components.insert(cIt, component);
361  if ((int)components.size() > numKeep) {
362  toRemove.insert(components.back().begin(), components.back().end());
363  components.pop_back();
364  }
365  }
366  for (std::set<NBEdge*>::iterator edgeIt = toRemove.begin(); edgeIt != toRemove.end(); ++edgeIt) {
367  NBNode* const fromNode = (*edgeIt)->getFromNode();
368  NBNode* const toNode = (*edgeIt)->getToNode();
369  ec.erase(dc, *edgeIt);
370  if (fromNode->getIncomingEdges().size() == 0 && fromNode->getOutgoingEdges().size() == 0) {
371  erase(fromNode);
372  }
373  if (toNode->getIncomingEdges().size() == 0 && toNode->getOutgoingEdges().size() == 0) {
374  erase(toNode);
375  }
376  }
377 }
378 
379 
380 int
383  NBParkingCont& pc,
384  bool removeGeometryNodes) {
385  // load edges that shall not be modified
386  std::set<std::string> edges2keep;
387  if (removeGeometryNodes) {
388  const OptionsCont& oc = OptionsCont::getOptions();
389  if (oc.isSet("geometry.remove.keep-edges.input-file")) {
390  NBHelpers::loadEdgesFromFile(oc.getString("geometry.remove.keep-edges.input-file"), edges2keep);
391  }
392  if (oc.isSet("geometry.remove.keep-edges.explicit")) {
393  const std::vector<std::string> edges = oc.getStringVector("geometry.remove.keep-edges.explicit");
394  edges2keep.insert(edges.begin(), edges.end());
395  }
396  sc.addEdges2Keep(oc, edges2keep);
397  UNUSED_PARAMETER(lc); // no need to keep all route edges. They are validated again before writing
398  pc.addEdges2Keep(oc, edges2keep);
399  }
400  int no = 0;
401  std::vector<NBNode*> toRemove;
402  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
403  NBNode* current = (*i).second;
404  bool remove = false;
405  std::vector<std::pair<NBEdge*, NBEdge*> > toJoin;
406  // check for completely empty nodes
407  if (current->getOutgoingEdges().size() == 0 && current->getIncomingEdges().size() == 0) {
408  // remove if empty
409  remove = true;
410  }
411  // check for nodes which are only geometry nodes
412  if (removeGeometryNodes && mySplit.count(current) == 0) {
413  if ((current->getOutgoingEdges().size() == 1 && current->getIncomingEdges().size() == 1)
414  ||
415  (current->getOutgoingEdges().size() == 2 && current->getIncomingEdges().size() == 2)) {
416  // ok, one in, one out or two in, two out
417  // -> ask the node whether to join
418  remove = current->checkIsRemovable();
419  // check whether any of the edges must be kept
420  for (EdgeVector::const_iterator it_edge = current->getEdges().begin(); it_edge != current->getEdges().end(); ++it_edge) {
421  if (edges2keep.find((*it_edge)->getID()) != edges2keep.end()) {
422  remove = false;
423  break;
424  }
425  }
426  if (remove) {
427  toJoin = current->getEdgesToJoin();
428  }
429  }
430  }
431  // remove the node and join the geometries when wished
432  if (!remove) {
433  continue;
434  }
435  for (std::vector<std::pair<NBEdge*, NBEdge*> >::iterator j = toJoin.begin(); j != toJoin.end(); j++) {
436  NBEdge* begin = (*j).first;
437  NBEdge* continuation = (*j).second;
438  begin->append(continuation);
439  continuation->getToNode()->replaceIncoming(continuation, begin, 0);
440  tlc.replaceRemoved(continuation, -1, begin, -1, true);
441  ec.extract(dc, continuation, true);
442  }
443  toRemove.push_back(current);
444  no++;
445  }
446  // erase all
447  for (std::vector<NBNode*>::iterator j = toRemove.begin(); j != toRemove.end(); ++j) {
448  extract(*j, true);
449  }
450  return no;
451 }
452 
453 
454 void
456  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
457  (*i).second->avoidOverlap();
458  }
459 }
460 
461 // ----------- (Helper) methods for joining nodes
462 void
463 NBNodeCont::generateNodeClusters(double maxDist, NodeClusters& into) const {
464  std::set<NBNode*> visited;
465  for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); i++) {
466  std::vector<NodeAndDist> toProc;
467  if (visited.find((*i).second) != visited.end()) {
468  continue;
469  }
470  toProc.push_back(std::make_pair((*i).second, 0));
471  NodeSet c;
472  while (!toProc.empty()) {
473  NodeAndDist nodeAndDist = toProc.back();
474  NBNode* n = nodeAndDist.first;
475  double dist = nodeAndDist.second;
476  toProc.pop_back();
477  if (visited.find(n) != visited.end()) {
478  continue;
479  }
480  visited.insert(n);
481  bool pureRail = true;
482  bool railAndPeds = true;
483  for (NBEdge* e : n->getEdges()) {
484  if ((e->getPermissions() & ~(SVC_RAIL_CLASSES | SVC_PEDESTRIAN)) != 0) {
485  railAndPeds = false;
486  pureRail = false;
487  break;
488  }
489  if ((e->getPermissions() & ~(SVC_RAIL_CLASSES)) != 0) {
490  pureRail = false;
491  }
492  }
493  if (pureRail) {
494  // do not join pure rail nodes
495  continue;
496  }
497  c.insert(n);
498  for (NBEdge* e : n->getEdges()) {
499  NBNode* s = n->hasIncoming(e) ? e->getFromNode() : e->getToNode();
500  const double length = e->getLoadedLength();
501 #ifdef DEBUG_JOINJUNCTIONS
502  if (DEBUGCOND(s)) {
503  std::cout << "generateNodeClusters: consider s=" << s->getID()
504  << " clusterNode=" << n->getID() << " edge=" << e->getID() << " length=" << length << " with cluster " << joinNamedToString(c, ' ') << "\n";
505  }
506 #endif
507  if (railAndPeds && n->getType() != SumoXMLNodeType::RAIL_CROSSING) {
508  bool railAndPeds2 = true;
509  for (NBEdge* e : n->getEdges()) {
510  if ((e->getPermissions() & ~(SVC_RAIL_CLASSES | SVC_PEDESTRIAN)) != 0) {
511  railAndPeds2 = false;
512  break;
513  }
514  }
515  if (railAndPeds2 && s->getType() != SumoXMLNodeType::RAIL_CROSSING) {
516  // do not join rail/ped nodes unless at a rail crossing
517  // (neither nodes nor the traffic lights)
518  continue;
519  }
520  }
521  const bool bothCrossing = n->getType() == SumoXMLNodeType::RAIL_CROSSING && s->getType() == SumoXMLNodeType::RAIL_CROSSING;
522  const bool joinPedCrossings = bothCrossing && e->getPermissions() == SVC_PEDESTRIAN;
523  if ( // never join pedestrian stuff (unless at a rail crossing
524  !joinPedCrossings && (
525  e->getPermissions() == SVC_PEDESTRIAN
526  // only join edges for regular passenger traffic or edges that are extremely short
527  || (length > 3 * POSITION_EPS
528  && (e->getPermissions() & (SVC_PASSENGER | SVC_TRAM)) == 0
530  continue;
531  }
532  // never join rail_crossings with other node types unless the crossing is only for tram
535  const SVCPermissions railNoTram = (SVC_RAIL_CLASSES & ~SVC_TRAM);
536  bool foundRail = false;
537  NBNode* crossingNode = n->getType() == SumoXMLNodeType::RAIL_CROSSING ? n : s;
538  for (NBEdge* e2 : crossingNode->getIncomingEdges()) {
539  if ((e2->getPermissions() & railNoTram) != 0) {
540  foundRail = true;
541  break;
542  }
543  }
544  if (foundRail) {
545  continue;
546  }
547  }
548  // never join rail_crossings via a rail edge
549  if (bothCrossing && (e->getPermissions() & ~SVC_RAIL_CLASSES) == 0) {
550  continue;
551  }
552  if (visited.find(s) != visited.end()) {
553  continue;
554  }
555  if (length + dist < maxDist) {
556  if (s->geometryLike()) {
557  toProc.push_back(std::make_pair(s, dist + length));
558  } else {
559  toProc.push_back(std::make_pair(s, 0));
560  }
561  }
562  }
563  }
564  if (c.size() < 2) {
565  continue;
566  }
567 #ifdef DEBUG_JOINJUNCTIONS
568  std::cout << " DEBUG: consider cluster " << joinNamedToString(c, ' ') << "\n";
569 #endif
570  into.push_back(c);
571  }
572 }
573 
574 
575 void
576 NBNodeCont::addJoinExclusion(const std::vector<std::string>& ids, bool check) {
577  for (std::vector<std::string>::const_iterator it = ids.begin(); it != ids.end(); it++) {
578  // error handling has to take place here since joinExclusions could be
579  // loaded from multiple files / command line
580  if (myJoined.count(*it) > 0) {
581  WRITE_WARNINGF("Ignoring join exclusion for junction '%' since it already occurred in a list of nodes to be joined.", *it);
582  } else if (check && retrieve(*it) == nullptr) {
583  WRITE_WARNINGF("Ignoring join exclusion for unknown junction '%'.", *it);
584  } else {
585  myJoinExclusions.insert(*it);
586  }
587  }
588 }
589 
590 
591 void
592 NBNodeCont::addCluster2Join(std::set<std::string> cluster, NBNode* node) {
593  // error handling has to take place here since joins could be loaded from multiple files
594  std::set<std::string> validCluster;
595  for (std::string nodeID : cluster) {
596  if (myJoinExclusions.count(nodeID) > 0) {
597  WRITE_WARNINGF("Ignoring join-cluster because junction '%' was already excluded from joining.", nodeID);
598  return;
599  } else if (myJoined.count(nodeID) > 0) {
600  WRITE_WARNINGF("Ignoring join-cluster because junction '%' already occurred in another join-cluster.", nodeID);
601  return;
602  } else {
603  NBNode* const node = retrieve(nodeID);
604  if (node != nullptr) {
605  validCluster.insert(nodeID);
606  } else {
607  if (StringUtils::startsWith(nodeID, "cluster_")) {
608  // assume join directive came from a pre-processed network. try to use component IDs
609  std::set<std::string> subIDs;
610  for (std::string nID : StringTokenizer(nodeID.substr(8), "_").getVector()) {
611  if (retrieve(nID) != nullptr) {
612  validCluster.insert(nID);
613  } else {
614  WRITE_ERROR("Unknown junction '" + nodeID + "' in join-cluster (componentID).");
615  }
616  }
617  } else {
618  WRITE_ERROR("Unknown junction '" + nodeID + "' in join-cluster.");
619  }
620  }
621  }
622  }
623  if (validCluster.size() > 1) {
624  myJoined.insert(validCluster.begin(), validCluster.end());
625  myClusters2Join.push_back(std::make_pair(validCluster, node));
626  } else {
627  WRITE_WARNINGF("Ignoring join-cluster '%s' because it has size '%'.", node->getID(), validCluster.size());
628  }
629 }
630 
631 
632 int
634  int numJoined = 0;
635  for (auto& item : myClusters2Join) {
636  // verify loaded cluster
637  NodeSet cluster;
638  for (std::string nodeID : item.first) {
639  NBNode* node = retrieve(nodeID);
640  if (node == nullptr) {
641  WRITE_ERROR("unknown junction '" + nodeID + "' while joining.");
642  } else {
643  cluster.insert(node);
644  }
645  }
646  if (cluster.size() > 1) {
647  joinNodeCluster(cluster, dc, ec, tlc, item.second);
648  numJoined++;
649  myJoinExclusions.insert(item.second->getID());
650  }
651  }
652  myClusters2Join.clear(); // make save for recompute
653  return numJoined;
654 }
655 
656 
657 int
659 #ifdef DEBUG_JOINJUNCTIONS
660  std::cout << "joinJunctions...\n";
661 #endif
662  NodeClusters cands;
663  NodeClusters clusters;
664  generateNodeClusters(maxDist, cands);
665  for (NodeClusters::iterator i = cands.begin(); i != cands.end(); ++i) {
666  NodeSet cluster = (*i);
667 #ifdef DEBUG_JOINJUNCTIONS
668  gDebugFlag1 = false;
669  for (NBNode* n : cluster) {
670  if (DEBUGCOND(n)) {
671  gDebugFlag1 = true;
672  }
673  }
674 #endif
675  // remove join exclusions
676  for (NodeSet::iterator j = cluster.begin(); j != cluster.end();) {
677  NodeSet::iterator check = j;
678  ++j;
679  if (myJoinExclusions.count((*check)->getID()) > 0) {
680  cluster.erase(check);
681  }
682  }
683  // remove nodes that can be eliminated by geometry.remove
684  pruneClusterFringe(cluster);
685  // avoid removal of long edges (must have been added via an alternative path).
686  pruneLongEdges(cluster, maxDist);
687  // remove nodes that are part of a bypass lane (typically for turning right without waiting at a traffic light)
688  pruneSlipLaneNodes(cluster);
689  if (cluster.size() < 2) {
690  continue;
691  }
692  std::string reason;
693  std::string origReason;
694  std::string origCluster;
695  bool feasible = feasibleCluster(cluster, ec, sc, origReason);
696  if (!feasible) {
697 #ifdef DEBUG_JOINJUNCTIONS
698  if (gDebugFlag1) {
699  std::cout << " try to reduce to 4-circle nodes=" << joinNamedToString(cluster, ',') << "\n";
700  }
701 #endif
702  origCluster = joinNamedToString(cluster, ',');
703  if (reduceToCircle(cluster, 4, cluster)) {
704  feasible = feasibleCluster(cluster, ec, sc, reason);
705  if (feasible) {
706  WRITE_WARNINGF("Reducing junction cluster % (%).", origCluster, origReason);
707  }
708  }
709  }
710  if (!feasible) {
711 #ifdef DEBUG_JOINJUNCTIONS
712  if (gDebugFlag1) {
713  std::cout << " try to reduce to 2-circle nodes=" << joinNamedToString(cluster, ',') << "\n";
714  }
715 #endif
716  origCluster = joinNamedToString(cluster, ',');
717  if (reduceToCircle(cluster, 2, cluster)) {
718  feasible = feasibleCluster(cluster, ec, sc, reason);
719  if (feasible) {
720  WRITE_WARNINGF("Reducing junction cluster % (%).", origCluster, origReason);
721  }
722  }
723  }
724  if (!feasible) {
725  WRITE_WARNINGF("Not joining junctions % (%).", origCluster, origReason);
726  continue;
727  }
728  // compute all connected components of this cluster
729  // (may be more than 1 if intermediate nodes were removed)
730  NodeClusters components;
731  for (NBNode* current : cluster) {
732  // merge all connected components into newComp
733  NodeSet newComp;
734  //std::cout << "checking connectivity for " << current->getID() << "\n";
735  newComp.insert(current);
736  for (NodeClusters::iterator it_comp = components.begin(); it_comp != components.end();) {
737  NodeClusters::iterator check = it_comp;
738  //std::cout << " connected with " << toString(*check) << "?\n";
739  bool connected = false;
740  for (NBNode* k : *check) {
741  if (current->getConnectionTo(k) != nullptr || k->getConnectionTo(current) != nullptr) {
742  //std::cout << "joining with connected component " << toString(*check) << "\n";
743  newComp.insert((*check).begin(), (*check).end());
744  it_comp = components.erase(check);
745  connected = true;
746  break;
747  }
748  }
749  if (!connected) {
750  it_comp++;
751  }
752  }
753  //std::cout << "adding new component " << toString(newComp) << "\n";
754  components.push_back(newComp);
755  }
756  for (NodeClusters::iterator it_comp = components.begin(); it_comp != components.end(); ++it_comp) {
757  if ((*it_comp).size() > 1) {
758  //std::cout << "adding cluster " << toString(*it_comp) << "\n";
759  clusters.push_back(*it_comp);
760  }
761  }
762 #ifdef DEBUG_JOINJUNCTIONS
763  gDebugFlag1 = false;
764 #endif
765  }
766  joinNodeClusters(clusters, dc, ec, tlc);
767  return (int)clusters.size();
768 }
769 
770 int
772 #ifdef DEBUG_JOINJUNCTIONS
773  std::cout << "joinSameJunctions...\n";
774 #endif
775  std::map<Position, NodeSet> positions;
776  for (auto& item : myNodes) {
777  positions[item.second->getPosition()].insert(item.second);
778  }
779  NodeClusters clusters;
780  for (auto& item : positions) {
781  if (item.second.size() > 1) {
782  for (NBNode* n : item.second) {
783  if (myJoinExclusions.count(n->getID()) > 0) {
784  item.second.erase(n);
785  }
786  }
787  if (item.second.size() > 1) {
788  clusters.push_back(item.second);
789  }
790  }
791  }
792  joinNodeClusters(clusters, dc, ec, tlc, true);
793  return (int)clusters.size();
794 }
795 
796 void
798 #ifdef DEBUG_JOINJUNCTIONS
799  if (gDebugFlag1) {
800  std::cout << "pruning cluster=" << joinNamedToString(cluster, ' ') << "\n";
801  }
802 #endif
803  // iteratively remove the fringe
804  bool pruneFringe = true;
805  // collect nodes that shall be joined due to distance but are not connected
806  // to the cluster for passenger traffic
807  while (pruneFringe) {
808  pruneFringe = false;
809  for (NodeSet::iterator j = cluster.begin(); j != cluster.end();) {
810  NodeSet::iterator check = j;
811  NBNode* n = *check;
812  ++j;
813 
814  // compute clusterDist for node (length of shortest edge which connects this node to the cluster)
815  double clusterDist = std::numeric_limits<double>::max();
816  bool touchingCluster = false;
817  for (EdgeVector::const_iterator it_edge = n->getOutgoingEdges().begin(); it_edge != n->getOutgoingEdges().end(); ++it_edge) {
818  NBNode* neighbor = (*it_edge)->getToNode();
819  if (cluster.count(neighbor) != 0) {
820  clusterDist = MIN2(clusterDist, (*it_edge)->getLoadedLength());
821  touchingCluster |= n->getPosition().distanceTo2D(neighbor->getPosition()) <= SUMO_const_laneWidth;
822  }
823  }
824  for (EdgeVector::const_iterator it_edge = n->getIncomingEdges().begin(); it_edge != n->getIncomingEdges().end(); ++it_edge) {
825  NBNode* neighbor = (*it_edge)->getFromNode();
826  if (cluster.count(neighbor) != 0) {
827  clusterDist = MIN2(clusterDist, (*it_edge)->getLoadedLength());
828  touchingCluster |= n->getPosition().distanceTo2D(neighbor->getPosition()) <= SUMO_const_laneWidth;
829  }
830  }
831  // remove geometry-like nodes at fringe of the cluster
832  // (they have 1 neighbor in the cluster and at most 1 neighbor outside the cluster)
833  std::set<NBNode*> outsideNeighbors;
834  std::set<NBNode*> clusterNeighbors;
835  const double pedestrianFringeThreshold = 0.3;
836  for (NBEdge* e : n->getEdges()) {
837  NBNode* neighbor = e->getFromNode() == n ? e->getToNode() : e->getFromNode();
838  if (cluster.count(neighbor) == 0) {
839  if ((e->getPermissions() & SVC_PASSENGER) != 0
840  || isRailway(e->getPermissions()) // join railway crossings
841  || clusterDist <= pedestrianFringeThreshold
842  || touchingCluster) {
843  outsideNeighbors.insert(neighbor);
844  }
845  } else {
846  clusterNeighbors.insert(neighbor);
847  }
848  }
849 #ifdef DEBUG_JOINJUNCTIONS
850  if (gDebugFlag1) std::cout << " check n=" << n->getID()
851  << " clusterDist=" << clusterDist
852  << " cd<th=" << (clusterDist <= pedestrianFringeThreshold)
853  << " touching=" << touchingCluster
854  << " out=" << joinNamedToString(outsideNeighbors, ',')
855  << " in=" << joinNamedToString(clusterNeighbors, ',')
856  << "\n";
857 #endif
858  if (clusterNeighbors.size() == 0
859  || (outsideNeighbors.size() <= 1
860  && clusterNeighbors.size() == 1
861  && !n->isTLControlled())) {
862  cluster.erase(check);
863  pruneFringe = true; // other nodes could belong to the fringe now
864 #ifdef DEBUG_JOINJUNCTIONS
865  if (gDebugFlag1) {
866  std::cout << " pruned n=" << n->getID() << "\n";
867  }
868 #endif
869  }
870  }
871  }
872 }
873 
874 
875 void
876 NBNodeCont::pruneLongEdges(NodeSet& cluster, double maxDist) {
877  std::set<NBNode*> toRemove;
878  int maxPassengerLanes = 0;
879  for (NBNode* n : cluster) {
880  for (NBEdge* edge : n->getEdges()) {
881  maxPassengerLanes = MAX2(maxPassengerLanes, edge->getNumLanesThatAllow(SVC_PASSENGER));
882  }
883  }
884  for (NBNode* n : cluster) {
885  for (NBEdge* edge : n->getOutgoingEdges()) {
886  // we must track the edge length accross geometry like nodes
887  // Also, intersecions that are geometry-like
888  // from the perspective of passenger traffic should be tracked accross
889  std::vector<NBNode*> passed;
890  double length = 0;
891  NBEdge* cur = edge;
892  NBNode* to = edge->getToNode();
893  while (cluster.count(to) != 0) {
894  length += cur->getLoadedLength();
895  bool goStraight = (std::find(passed.begin(), passed.end(), to) == passed.end()
896  && (edge->getPermissions() & SVC_PASSENGER) != 0
897  && to->geometryLike(
900  passed.push_back(to);
901  if (goStraight) {
903  if (cur != nullptr) {
904  to = cur->getToNode();
905  } else {
906  break;
907  }
908  } else {
909  break;
910  }
911  }
912  // allow higher threshold at larger junctions
913  double longThreshold = maxDist + SUMO_const_laneWidth * MAX2(0, maxPassengerLanes - 1);
914 #ifdef DEBUG_JOINJUNCTIONS
915  if (gDebugFlag1) {
916  std::cout << "check edge length " << edge->getID() << " (" << length << ", passed=" << passed.size() << ", max=" << longThreshold << ")\n";
917  }
918 #endif
919  if (length > longThreshold) {
920  // we found an edge that should not be removed. Maybe we can
921  // still keep the start or end in the cluster
922  // (keep the start if the end can be removed and vice versa)
923  const bool keepStart = getClusterNeighbors(passed.back(), cluster).size() == 1;
924  const bool keepEnd = !keepStart && getClusterNeighbors(n, cluster).size() == 1;
925 #ifdef DEBUG_JOINJUNCTIONS
926  if (gDebugFlag1) {
927  std::cout << "node=" << n->getID() << " long edge " << edge->getID() << " (" << length << ", passed=" << toString(passed) << ", max=" << longThreshold << ") keepStart=" << keepStart << " keepEnd=" << keepEnd << "\n";
928  }
929 #endif
930  if (!keepStart) {
931  toRemove.insert(n);
932  }
933  toRemove.insert(passed.begin(), passed.end() - 1);
934  if (!keepEnd) {
935  toRemove.insert(passed.back());
936  }
937 
938  }
939  }
940  }
941  for (std::set<NBNode*>::iterator j = toRemove.begin(); j != toRemove.end(); ++j) {
942  cluster.erase(*j);
943  }
944 }
945 
946 
947 NodeSet
949  NodeSet result;
950  for (NBEdge* e : n->getEdges()) {
951  NBNode* neighbor = e->getFromNode() == n ? e->getToNode() : e->getFromNode();
952  if (cluster.count(neighbor) != 0) {
953  result.insert(neighbor);
954  }
955  }
956  return result;
957 }
958 
959 
960 void
962 #ifdef DEBUG_JOINJUNCTIONS
963  if (gDebugFlag1) {
964  std::cout << "pruning slip-lanes at cluster=" << joinNamedToString(cluster, ' ') << "\n";
965  }
966 #endif
967  // fringe has already been removed
968  if (cluster.size() <= 2) {
969  return;
970  }
971  NodeSet toRemove;
972  for (NBNode* n : cluster) {
973  EdgeVector outgoing;
974  double inAngle;
975  // find slip lanes where the start is part of the cluster
976  if (maybeSlipLaneStart(n, outgoing, inAngle)) {
977  // potential slip lane start but we don't know which of the outgoing edges it is
978 #ifdef DEBUG_JOINJUNCTIONS
979  if (gDebugFlag1) {
980  std::cout << " candidate slip-lane start=" << n->getID() << " outgoing=" << toString(outgoing) << "\n";
981  }
982 #endif
983  for (NBEdge* contEdge : outgoing) {
984  if ((contEdge->getPermissions() & SVC_PASSENGER) == 0) {
985  continue;
986  }
987  double slipLength = contEdge->getLength();
988  NBNode* cont = contEdge->getToNode();
989  NodeSet cands;
990  cands.insert(n);
991  while (cont->getIncomingEdges().size() == 1 && cont->getOutgoingEdges().size() == 1 && slipLength < MAX_SLIPLANE_LENGTH) {
992  if (cands.count(cont) != 0) {
993  break; // circle, should not happen
994  }
995  cands.insert(cont);
996 #ifdef DEBUG_JOINJUNCTIONS
997  if (gDebugFlag1) {
998  std::cout << " candidate slip-lane cont=" << cont->getID() << "\n";
999  }
1000 #endif
1001  NBEdge* next = cont->getOutgoingEdges().front();
1002  slipLength += next->getLength();
1003  cont = next->getToNode();
1004  }
1005 #ifdef DEBUG_JOINJUNCTIONS
1006  if (gDebugFlag1) {
1007  std::cout << " candidate slip-lane end=" << cont->getID() << " slipLength=" << slipLength << "\n";
1008  }
1009 #endif
1010  if (cont->getIncomingEdges().size() >= 2 && cont->getOutgoingEdges().size() == 1 &&
1011  // slip lanes are for turning so there needs to be a sufficient angle
1012  abs(NBHelpers::relAngle(inAngle, cont->getOutgoingEdges().front()->getAngleAtNode(cont))) > 45) {
1013  // check whether the other continuation at n is also connected to the sliplane end
1014  NBEdge* otherEdge = (contEdge == outgoing.front() ? outgoing.back() : outgoing.front());
1015  double otherLength = otherEdge->getLength();
1016  NBNode* cont2 = otherEdge->getToNode();
1017 
1018  NodeSet visited;
1019  visited.insert(n);
1020  std::vector<NodeAndDist> toProc;
1021  toProc.push_back(std::make_pair(cont2, otherLength));
1022  bool found = false;
1023  while (!toProc.empty()) {
1024  NodeAndDist nodeAndDist = toProc.back();
1025  NBNode* cont2 = nodeAndDist.first;
1026  double dist = nodeAndDist.second;
1027 #ifdef DEBUG_JOINJUNCTIONS
1028  if (gDebugFlag1) {
1029  std::cout << " search alternative cont2=" << cont2->getID() << " dist=" << dist << "\n";
1030  }
1031 #endif
1032  toProc.pop_back();
1033  if (visited.find(cont2) != visited.end()) {
1034  continue;
1035  }
1036  visited.insert(cont2);
1037  if (cont2 == cont) {
1038  found = true;
1039  break;
1040  }
1041  for (NBEdge* e : cont2->getOutgoingEdges()) {
1042  const double dist2 = dist + e->getLength();
1043  if (dist2 < slipLength * 2 && (e->getPermissions() & SVC_PASSENGER) != 0) {
1044  toProc.push_back(std::make_pair(e->getToNode(), dist2));
1045  }
1046  }
1047  }
1048  if (found) {
1049  // found slip lane
1050  cands.insert(cont);
1051  toRemove.insert(cands.begin(), cands.end());
1052 #ifdef DEBUG_JOINJUNCTIONS
1053  if (gDebugFlag1) {
1054  std::cout << " found slip-lane with nodes=" << joinNamedToString(cands, ' ') << "\n";
1055  }
1056 #endif
1057  }
1058  }
1059  }
1060  }
1061 
1062  EdgeVector incoming;
1063  double outAngle;
1064  // find slip lanes where the end is part of the cluster
1065  if (maybeSlipLaneEnd(n, incoming, outAngle)) {
1066  // potential slip lane end but we don't know which of the incoming edges it is
1067 #ifdef DEBUG_JOINJUNCTIONS
1068  if (gDebugFlag1) {
1069  std::cout << " candidate slip-lane end=" << n->getID() << " incoming=" << toString(incoming) << "\n";
1070  }
1071 #endif
1072  for (NBEdge* contEdge : incoming) {
1073  if ((contEdge->getPermissions() & SVC_PASSENGER) == 0) {
1074  continue;
1075  }
1076  double slipLength = contEdge->getLength();
1077  NBNode* cont = contEdge->getFromNode();
1078  NodeSet cands;
1079  cands.insert(n);
1080  while (cont->getIncomingEdges().size() == 1 && cont->getOutgoingEdges().size() == 1 && slipLength < MAX_SLIPLANE_LENGTH) {
1081  if (cands.count(cont) != 0) {
1082  break; // circle, should not happen
1083  }
1084  cands.insert(cont);
1085 #ifdef DEBUG_JOINJUNCTIONS
1086  if (gDebugFlag1) {
1087  std::cout << " candidate slip-lane cont=" << cont->getID() << "\n";
1088  }
1089 #endif
1090  NBEdge* next = cont->getIncomingEdges().front();
1091  slipLength += next->getLength();
1092  cont = next->getFromNode();
1093  }
1094 #ifdef DEBUG_JOINJUNCTIONS
1095  if (gDebugFlag1) {
1096  std::cout << " candidate slip-lane start=" << cont->getID() << " slipLength=" << slipLength << "\n";
1097  }
1098 #endif
1099  if (cont->getOutgoingEdges().size() >= 2 && cont->getIncomingEdges().size() == 1 &&
1100  // slip lanes are for turning so there needs to be a sufficient angle
1101  abs(NBHelpers::relAngle(outAngle, cont->getIncomingEdges().front()->getAngleAtNode(cont))) > 45) {
1102  // check whether the other continuation at n is also connected to the sliplane end
1103  NBEdge* otherEdge = (contEdge == incoming.front() ? incoming.back() : incoming.front());
1104  double otherLength = otherEdge->getLength();
1105  NBNode* cont2 = otherEdge->getFromNode();
1106 
1107  NodeSet visited;
1108  visited.insert(n);
1109  std::vector<NodeAndDist> toProc;
1110  toProc.push_back(std::make_pair(cont2, otherLength));
1111  bool found = false;
1112  while (!toProc.empty()) {
1113  NodeAndDist nodeAndDist = toProc.back();
1114  NBNode* cont2 = nodeAndDist.first;
1115  double dist = nodeAndDist.second;
1116 #ifdef DEBUG_JOINJUNCTIONS
1117  if (gDebugFlag1) {
1118  std::cout << " search alternative cont2=" << cont2->getID() << " dist=" << dist << "\n";
1119  }
1120 #endif
1121  toProc.pop_back();
1122  if (visited.find(cont2) != visited.end()) {
1123  continue;
1124  }
1125  visited.insert(cont2);
1126  if (cont2 == cont) {
1127  found = true;
1128  break;
1129  }
1130  for (NBEdge* e : cont2->getIncomingEdges()) {
1131  const double dist2 = dist + e->getLength();
1132  if (dist2 < slipLength * 2 && (e->getPermissions() & SVC_PASSENGER) != 0) {
1133  toProc.push_back(std::make_pair(e->getFromNode(), dist2));
1134  }
1135  }
1136  }
1137  if (found) {
1138  // found slip lane
1139  cands.insert(cont);
1140  toRemove.insert(cands.begin(), cands.end());
1141 #ifdef DEBUG_JOINJUNCTIONS
1142  if (gDebugFlag1) {
1143  std::cout << " found slip-lane start with nodes=" << joinNamedToString(cands, ' ') << "\n";
1144  }
1145 #endif
1146  }
1147  }
1148  }
1149  }
1150 
1151 
1152 
1153  }
1154  int numRemoved = 0;
1155  for (NBNode* n : toRemove) {
1156  numRemoved += (int)cluster.erase(n);
1157  }
1158  if (numRemoved > 0) {
1159 #ifdef DEBUG_JOINJUNCTIONS
1160  if (gDebugFlag1) {
1161  std::cout << " removed " << numRemoved << " nodes from cluster: " << joinNamedToString(toRemove, ' ') << "\n";
1162  }
1163 #endif
1164  pruneClusterFringe(cluster);
1165  }
1166 }
1167 
1168 
1169 bool
1170 NBNodeCont::maybeSlipLaneStart(const NBNode* n, EdgeVector& outgoing, double& inAngle) const {
1171  if (n->getIncomingEdges().size() == 1 && n->getOutgoingEdges().size() == 2) {
1172  outgoing.insert(outgoing.begin(), n->getOutgoingEdges().begin(), n->getOutgoingEdges().end());
1173  inAngle = n->getIncomingEdges().front()->getAngleAtNode(n);
1174  return true;
1175  } else if (n->getIncomingEdges().size() >= 2 && n->getOutgoingEdges().size() == 3) {
1176  // check if the incoming edges are going in opposite directions and then
1177  // use the incoming edge that has 2 almost-straight outgoing edges
1178  const double inRelAngle = fabs(NBHelpers::relAngle(n->getIncomingEdges().front()->getAngleAtNode(n), n->getIncomingEdges().back()->getAngleAtNode(n)));
1179  //std::cout << "n=" << n->getID() << " inRelAngle=" << inRelAngle << "\n";
1180  if (inRelAngle < 135) {
1181  return false; // not opposite incoming
1182  }
1183  for (NBEdge* in : n->getIncomingEdges()) {
1184  EdgeVector straight;
1185  int numReverse = 0;
1186  for (NBEdge* out : n->getOutgoingEdges()) {
1187  const double outRelAngle = fabs(NBHelpers::relAngle(in->getAngleAtNode(n), out->getAngleAtNode(n)));
1188  if (outRelAngle <= 45) {
1189  straight.push_back(out);
1190  } else if (outRelAngle >= 135) {
1191  numReverse++;
1192  }
1193  }
1194  if (straight.size() == 2 && numReverse == 1) {
1195  outgoing.insert(outgoing.begin(), straight.begin(), straight.end());
1196  inAngle = in->getAngleAtNode(n);
1197  return true;
1198  }
1199  }
1200  }
1201  return false;
1202 }
1203 
1204 
1205 bool
1206 NBNodeCont::maybeSlipLaneEnd(const NBNode* n, EdgeVector& incoming, double& outAngle) const {
1207  if (n->getIncomingEdges().size() == 2 && n->getOutgoingEdges().size() == 1) {
1208  incoming.insert(incoming.begin(), n->getIncomingEdges().begin(), n->getIncomingEdges().end());
1209  outAngle = n->getOutgoingEdges().front()->getAngleAtNode(n);
1210  return true;
1211  } else if (n->getIncomingEdges().size() == 3 && n->getOutgoingEdges().size() >= 2) {
1212  // check if the outgoing edges are going in opposite directions and then
1213  // use the outgoing edge that has 2 almost-straight incoming edges
1214  const double outRelAngle = fabs(NBHelpers::relAngle(n->getOutgoingEdges().front()->getAngleAtNode(n), n->getOutgoingEdges().back()->getAngleAtNode(n)));
1215  //std::cout << "n=" << n->getID() << " outRelAngle=" << outRelAngle << "\n";
1216  if (outRelAngle < 135) {
1217  return false; // not opposite outgoing
1218  }
1219  for (NBEdge* out : n->getOutgoingEdges()) {
1220  EdgeVector straight;
1221  int numReverse = 0;
1222  for (NBEdge* in : n->getIncomingEdges()) {
1223  const double inRelAngle = fabs(NBHelpers::relAngle(in->getAngleAtNode(n), out->getAngleAtNode(n)));
1224  if (inRelAngle <= 45) {
1225  straight.push_back(in);
1226  } else if (inRelAngle >= 135) {
1227  numReverse++;
1228  }
1229  }
1230  if (straight.size() == 2 && numReverse == 1) {
1231  incoming.insert(incoming.begin(), straight.begin(), straight.end());
1232  outAngle = out->getAngleAtNode(n);
1233  return true;
1234  }
1235  }
1236  }
1237  return false;
1238 }
1239 
1240 bool
1241 NBNodeCont::feasibleCluster(const NodeSet& cluster, const NBEdgeCont& ec, const NBPTStopCont& sc, std::string& reason) const {
1242  // check for clusters which are to complex and probably won't work very well
1243  // we count the incoming edges of the final junction
1244  std::map<std::string, double> finalIncomingAngles;
1245  std::map<std::string, double> finalOutgoingAngles;
1246  for (NodeSet::const_iterator j = cluster.begin(); j != cluster.end(); ++j) {
1247  for (EdgeVector::const_iterator it_edge = (*j)->getIncomingEdges().begin(); it_edge != (*j)->getIncomingEdges().end(); ++it_edge) {
1248  NBEdge* edge = *it_edge;
1249  if (cluster.count(edge->getFromNode()) == 0 && (edge->getPermissions() & SVC_PASSENGER) != 0) {
1250  // incoming edge, does not originate in the cluster
1251  finalIncomingAngles[edge->getID()] = edge->getAngleAtNode(edge->getToNode());
1252  }
1253  }
1254  for (EdgeVector::const_iterator it_edge = (*j)->getOutgoingEdges().begin(); it_edge != (*j)->getOutgoingEdges().end(); ++it_edge) {
1255  NBEdge* edge = *it_edge;
1256  if (cluster.count(edge->getToNode()) == 0 && (edge->getPermissions() & SVC_PASSENGER) != 0) {
1257  // outgoing edge, does not end in the cluster
1258  finalOutgoingAngles[edge->getID()] = edge->getAngleAtNode(edge->getFromNode());
1259  }
1260  }
1261 
1262  }
1263 #ifdef DEBUG_JOINJUNCTIONS
1264  for (NBNode* n : cluster) {
1265  if (DEBUGCOND(n)) {
1266  std::cout << "feasibleCluster c=" << joinNamedToString(cluster, ',')
1267  << "\n inAngles=" << joinToString(finalIncomingAngles, ' ', ':')
1268  << "\n outAngles=" << joinToString(finalOutgoingAngles, ' ', ':')
1269  << "\n";
1270  }
1271  }
1272 #endif
1273  if (finalIncomingAngles.size() > 4) {
1274  reason = toString(finalIncomingAngles.size()) + " incoming edges";
1275  return false;
1276  }
1277  // check for incoming parallel edges
1278  const double PARALLEL_INCOMING_THRESHOLD = 10.0;
1279  bool foundParallel = false;
1280  for (std::map<std::string, double>::const_iterator j = finalIncomingAngles.begin(); j != finalIncomingAngles.end() && !foundParallel; ++j) {
1281  std::map<std::string, double>::const_iterator k = j;
1282  for (++k; k != finalIncomingAngles.end() && !foundParallel; ++k) {
1283  if (fabs(j->second - k->second) < PARALLEL_INCOMING_THRESHOLD) {
1284  reason = "parallel incoming " + j->first + "," + k->first;
1285  return false;
1286  }
1287  }
1288  }
1289  // check for outgoing parallel edges
1290  for (std::map<std::string, double>::const_iterator j = finalOutgoingAngles.begin(); j != finalOutgoingAngles.end() && !foundParallel; ++j) {
1291  std::map<std::string, double>::const_iterator k = j;
1292  for (++k; k != finalOutgoingAngles.end() && !foundParallel; ++k) {
1293  if (fabs(j->second - k->second) < PARALLEL_INCOMING_THRESHOLD) {
1294  reason = "parallel outgoing " + j->first + "," + k->first;
1295  return false;
1296  }
1297  }
1298  }
1299  // check for stop edges within the cluster
1300  if (OptionsCont::getOptions().isSet("ptstop-output")) {
1301  for (auto it = sc.begin(); it != sc.end(); it++) {
1302  NBEdge* edge = ec.retrieve(it->second->getEdgeId());
1303  if (edge != nullptr && cluster.count(edge->getFromNode()) != 0 && cluster.count(edge->getToNode()) != 0) {
1304  reason = "it contains stop '" + it->first + "'";
1305  return false;
1306  }
1307  }
1308  }
1309  int numTLS = 0;
1310  for (NBNode* n : cluster) {
1311  if (n->isTLControlled()) {
1312  numTLS++;
1313  };
1314  }
1315  const bool hasTLS = numTLS > 0;
1316  // prevent removal of long edges unless there is weak circle or a traffic light
1317  if (cluster.size() > 2) {
1318  // find the nodes with the biggests physical distance between them
1319  double maxDist = -1;
1320  NBEdge* maxEdge = nullptr;
1321  for (NBNode* n1 : cluster) {
1322  for (NBNode* n2 : cluster) {
1323  NBEdge* e1 = n1->getConnectionTo(n2);
1324  NBEdge* e2 = n2->getConnectionTo(n1);
1325  if (e1 != nullptr && e1->getLoadedLength() > maxDist) {
1326  maxDist = e1->getLoadedLength();
1327  maxEdge = e1;
1328  }
1329  if (e2 != nullptr && e2->getLoadedLength() > maxDist) {
1330  maxDist = e2->getLoadedLength();
1331  maxEdge = e2;
1332  }
1333  }
1334  }
1335 #ifdef DEBUG_JOINJUNCTIONS
1336  for (NBNode* n : cluster) {
1337  if (DEBUGCOND(n)) {
1338  std::cout << "feasible hasTLS=" << hasTLS << " maxDist=" << maxDist << " maxEdge=" << maxEdge->getID() << "\n";
1339  }
1340  }
1341 #endif
1342  if (!hasTLS && maxDist > 5) {
1343  // find a weak circle within cluster that does not use maxEdge
1344  std::vector<NBNode*> toCheck;
1345  std::set<NBNode*> visited;
1346  toCheck.push_back(maxEdge->getToNode());
1347  bool foundCircle = false;
1348  while (!toCheck.empty()) {
1349  NBNode* n = toCheck.back();
1350  if (n == maxEdge->getFromNode()) {
1351  foundCircle = true;
1352  break;
1353  }
1354  toCheck.pop_back();
1355  visited.insert(n);
1356  for (NBEdge* e : n->getEdges()) {
1357  if (e != maxEdge) {
1358  NBNode* cand = e->getFromNode() == n ? e->getToNode() : e->getFromNode();
1359  if (visited.count(cand) == 0 && cluster.count(cand) != 0) {
1360  toCheck.push_back(cand);
1361  }
1362  }
1363  }
1364  }
1365  if (!foundCircle) {
1366  reason = "not compact (maxEdge=" + maxEdge->getID() + " length=" + toString(maxDist) + ")";
1367  return false;
1368  }
1369  }
1370  }
1371  // prevent joining of simple merging/spreading structures
1372  if (!hasTLS && cluster.size() >= 2) {
1373  int entryNodes = 0;
1374  int exitNodes = 0;
1375  int outsideIncoming = 0;
1376  int outsideOutgoing = 0;
1377  int edgesWithin = 0;
1378  for (NBNode* n : cluster) {
1379  bool foundOutsideIncoming = false;
1380  for (NBEdge* e : n->getIncomingEdges()) {
1381  if (cluster.count(e->getFromNode()) == 0) {
1382  // edge entering from outside the cluster
1383  outsideIncoming++;
1384  foundOutsideIncoming = true;
1385  } else {
1386  edgesWithin++;
1387  }
1388  }
1389  if (foundOutsideIncoming) {
1390  entryNodes++;
1391  }
1392  bool foundOutsideOutgoing = false;
1393  for (NBEdge* e : n->getOutgoingEdges()) {
1394  if (cluster.count(e->getToNode()) == 0) {
1395  // edge leaving cluster
1396  outsideOutgoing++;
1397  foundOutsideOutgoing = true;
1398  }
1399  }
1400  if (foundOutsideOutgoing) {
1401  exitNodes++;
1402  }
1403  }
1404  if (entryNodes < 2) {
1405  reason = "only 1 entry node";
1406  return false;
1407  }
1408  if (exitNodes < 2) {
1409  reason = "only 1 exit node";
1410  return false;
1411  }
1412  if (cluster.size() == 2) {
1413  if (edgesWithin == 1 && outsideIncoming < 3 && outsideOutgoing < 3) {
1414  reason = "only 1 edge within and no cross-traffic";
1415  return false;
1416  }
1417  }
1418  }
1419  return true;
1420 }
1421 
1422 
1423 bool
1424 NBNodeCont::reduceToCircle(NodeSet& cluster, int circleSize, NodeSet startNodes, std::vector<NBNode*> cands) const {
1425  //std::cout << "reduceToCircle cs=" << circleSize << " cands=" << toString(cands, ',') << " startNodes=" << joinNamedToString(startNodes, ',') << "\n";
1426  assert(circleSize >= 2);
1427  if ((int)cands.size() == circleSize) {
1428  if (cands.back()->getConnectionTo(cands.front()) != nullptr) {
1429  // cluster found
1430  NodeSet candCluster;
1431  candCluster.insert(cands.begin(), cands.end());
1432  pruneClusterFringe(candCluster);
1433  const bool feasible = (int)candCluster.size() == circleSize;
1434  if (feasible) {
1435  cluster.clear();
1436  cluster.insert(cands.begin(), cands.end());
1437  }
1438  return feasible;
1439  } else {
1440  return false;
1441  }
1442  }
1443  if ((int)cluster.size() <= circleSize || startNodes.size() == 0) {
1444  // no reduction possible
1445  //std::cout << " abort\n";
1446  return false;
1447  }
1448  if (cands.size() == 0) {
1449  // try to find a circle starting from another start node
1450  NBEdge* e = shortestEdge(cluster, startNodes, cands);
1451  if (e != nullptr) {
1452  cands.push_back(e->getFromNode());
1453  startNodes.erase(e->getFromNode());
1454  if (reduceToCircle(cluster, circleSize, startNodes, cands)) {
1455  return true;
1456  } else {
1457  // try another start node
1458  return reduceToCircle(cluster, circleSize, startNodes);
1459  }
1460  }
1461  } else {
1462  NodeSet singleStart;
1463  singleStart.insert(cands.back());
1464  NBEdge* e = shortestEdge(cluster, singleStart, cands);
1465  if (e != nullptr) {
1466  std::vector<NBNode*> cands2(cands);
1467  cands2.push_back(e->getToNode());
1468  if (reduceToCircle(cluster, circleSize, startNodes, cands2)) {
1469  return true;
1470  }
1471  }
1472  }
1473  //std::cout << " abort2\n";
1474  return false;
1475 }
1476 
1477 
1478 NBEdge*
1479 NBNodeCont::shortestEdge(const NodeSet& cluster, const NodeSet& startNodes, const std::vector<NBNode*>& exclude) const {
1480  double minDist = std::numeric_limits<double>::max();
1481  NBEdge* result = nullptr;
1482  for (NBNode* n : startNodes) {
1483  for (NBEdge* e : n->getOutgoingEdges()) {
1484  NBNode* neigh = e->getToNode();
1485  if (cluster.count(neigh) != 0 && std::find(exclude.begin(), exclude.end(), neigh) == exclude.end()) {
1486  const double dist = n->getPosition().distanceTo2D(neigh->getPosition());
1487  //std::cout << " e=" << e->getID() << " dist=" << dist << " minD=" << minDist << "\n";
1488  if (dist < minDist) {
1489  minDist = dist;
1490  result = e;
1491  }
1492  }
1493  }
1494  }
1495  //std::cout << "closestNeighbor startNodes=" << toString(startNodes) << " result=" << Named::getIDSecure(result) << "\n";
1496  return result;
1497 }
1498 
1499 void
1501  NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc, bool resetConnections) {
1502  for (NodeSet cluster : clusters) {
1503  joinNodeCluster(cluster, dc, ec, tlc, nullptr, resetConnections);
1504  }
1505 }
1506 
1507 
1508 void
1509 NBNodeCont::joinNodeCluster(NodeSet cluster, NBDistrictCont& dc, NBEdgeCont& ec, NBTrafficLightLogicCont& tlc, NBNode* predefined, bool resetConnections) {
1510  const bool origNames = OptionsCont::getOptions().getBool("output.original-names");
1511  assert(cluster.size() > 1);
1512  Position pos;
1513  bool setTL;
1514  std::string id = "cluster";
1515  TrafficLightType type;
1517  analyzeCluster(cluster, id, pos, setTL, type, nodeType);
1518  NBNode* newNode = nullptr;
1519  if (predefined != nullptr) {
1520  newNode = predefined;
1521  } else {
1522  if (!insert(id, pos)) {
1523  // should not fail
1524  WRITE_WARNINGF("Could not join junctions %.", id);
1525  return;
1526  }
1527  newNode = retrieve(id);
1528  }
1529  std::string tlID = id;
1530  if (predefined != nullptr) {
1531  if (predefined->getType() != SumoXMLNodeType::UNKNOWN) {
1532  nodeType = predefined->getType();
1533  }
1534  Position ppos = predefined->getPosition();
1535  if (ppos.x() != Position::INVALID.x()) {
1536  pos.setx(ppos.x());
1537  }
1538  if (ppos.y() != Position::INVALID.y()) {
1539  pos.sety(ppos.y());
1540  }
1541  if (ppos.z() != Position::INVALID.z()) {
1542  pos.setz(ppos.z());
1543  }
1544  }
1545  newNode->reinit(pos, nodeType);
1546  if (setTL && !newNode->isTLControlled()) {
1547  NBTrafficLightDefinition* tlDef = new NBOwnTLDef(tlID, newNode, 0, type);
1548  if (!tlc.insert(tlDef)) {
1549  // actually, nothing should fail here
1550  delete tlDef;
1551  throw ProcessError("Could not allocate tls '" + id + "'.");
1552  }
1553  }
1554  // collect edges
1555  std::set<NBEdge*, ComparatorIdLess> allEdges;
1556  for (NBNode* n : cluster) {
1557  const EdgeVector& edges = n->getEdges();
1558  allEdges.insert(edges.begin(), edges.end());
1559  }
1560  // determine edges with are incoming or fully inside
1561  std::set<NBEdge*, ComparatorIdLess> clusterIncoming;
1562  std::set<NBEdge*, ComparatorIdLess> inside;
1563  for (NBEdge* e : allEdges) {
1564  if (cluster.count(e->getToNode()) > 0) {
1565  if (cluster.count(e->getFromNode()) > 0) {
1566  inside.insert(e);
1567  } else {
1568  clusterIncoming.insert(e);
1569  }
1570  }
1571  }
1572 #ifdef DEBUG_JOINJUNCTIONS
1573  std::cout << "joining cluster " << joinNamedToString(cluster, ' ') << "\n"
1574  << " incoming=" << toString(clusterIncoming) << "\n"
1575  << " inside=" << toString(inside) << "\n";
1576 #endif
1577 
1578  // determine possible connectivity from outside edges
1579  std::map<NBEdge*, EdgeSet> reachable;
1580  for (NBEdge* e : clusterIncoming) {
1581  EdgeVector open;
1582  EdgeSet seen;
1583  open.push_back(e);
1584  while (open.size() > 0) {
1585  NBEdge* cur = open.back();
1586  //std::cout << " e=" << e->getID() << " cur=" << cur->getID() << " open=" << toString(open) << "\n";
1587  seen.insert(cur);
1588  open.pop_back();
1589  if (cluster.count(cur->getToNode()) == 0) {
1590  //std::cout << " continue\n";
1591  continue;
1592  }
1593  const auto& cons = cur->getConnections();
1594  if (cons.size() == 0 || ec.hasPostProcessConnection(cur->getID()) || cur->getStep() == NBEdge::EdgeBuildingStep::INIT) {
1595  // check permissions to determine reachability
1596  for (NBEdge* out : cur->getToNode()->getOutgoingEdges()) {
1597  if (seen.count(out) == 0
1598  && allEdges.count(out) != 0
1599  && (out->getPermissions() & cur->getPermissions() & ~SVC_PEDESTRIAN) != 0) {
1600  open.push_back(out);
1601  }
1602  }
1603  } else {
1604  // check existing connections
1605  for (const auto& con : cons) {
1606  if (con.toEdge != nullptr
1607  && seen.count(con.toEdge) == 0
1608  && allEdges.count(con.toEdge) != 0) {
1609  open.push_back(con.toEdge);
1610  }
1611  }
1612  }
1613  }
1614  seen.erase(e);
1615  for (NBEdge* reached : seen) {
1616  // filter out inside edges from reached
1617  if (inside.count(reached) == 0) {
1618  reachable[e].insert(reached);
1619  }
1620  }
1621 #ifdef DEBUG_JOINJUNCTIONS
1622  std::cout << " reachable e=" << e->getID() << " seen=" << toString(seen) << " reachable=" << toString(reachable[e]) << "\n";
1623 #endif
1624  }
1625 
1626  // remap and remove edges which are completely within the new intersection
1627  for (NBEdge* e : inside) {
1628  for (NBEdge* e2 : allEdges) {
1629  if (e != e2) {
1630  e2->replaceInConnections(e, e->getConnections());
1631  }
1632  }
1633  ec.extract(dc, e, true);
1634  allEdges.erase(e);
1635  }
1636 
1637  // remap edges which are incoming / outgoing
1638  for (NBEdge* e : allEdges) {
1639  std::vector<NBEdge::Connection> conns = e->getConnections();
1640  const bool outgoing = cluster.count(e->getFromNode()) > 0;
1641  NBNode* from = outgoing ? newNode : e->getFromNode();
1642  NBNode* to = outgoing ? e->getToNode() : newNode;
1643  if (origNames) {
1644  if (outgoing) {
1645  e->setParameter("origFrom", e->getFromNode()->getID());
1646  } else {
1647  e->setParameter("origTo", e->getToNode()->getID());
1648  }
1649  }
1650  e->reinitNodes(from, to);
1651  // re-add connections which previously existed and may still valid.
1652  // connections to removed edges will be ignored
1653  for (std::vector<NBEdge::Connection>::iterator k = conns.begin(); k != conns.end(); ++k) {
1654  e->addLane2LaneConnection((*k).fromLane, (*k).toEdge, (*k).toLane, NBEdge::Lane2LaneInfoType::USER, false, (*k).mayDefinitelyPass);
1655  if ((*k).fromLane >= 0 && (*k).fromLane < e->getNumLanes() && e->getLaneStruct((*k).fromLane).connectionsDone) {
1656  // @note (see NIImporter_DlrNavteq::ConnectedLanesHandler)
1657  e->declareConnectionsAsLoaded(NBEdge::EdgeBuildingStep::INIT);
1658  }
1659  }
1660  }
1661  if (!resetConnections) {
1662  // disable connections that were impossible with the old topology
1663  for (NBEdge* in : newNode->getIncomingEdges()) {
1664  for (NBEdge* out : newNode->getOutgoingEdges()) {
1665  if (reachable[in].count(out) == 0 && !ec.hasPostProcessConnection(in->getID(), out->getID())) {
1666  //std::cout << " removeUnreachable in=" << in->getID() << " out=" << out->getID() << "\n";
1667  in->removeFromConnections(out, -1, -1, true, false, true);
1668  }
1669  }
1670  }
1671  } else {
1672  for (NBEdge* in : newNode->getIncomingEdges()) {
1673  in->invalidateConnections(true);
1674  }
1675  }
1676 
1677  // remove original nodes
1678  registerJoinedCluster(cluster);
1679  for (NBNode* n : cluster) {
1680  erase(n);
1681  }
1682 }
1683 
1684 
1685 void
1687  std::set<std::string> ids;
1688  for (NBNode* n : cluster) {
1689  ids.insert(n->getID());
1690  }
1691  myJoinedClusters.push_back(ids);
1692 }
1693 
1694 
1695 void
1696 NBNodeCont::analyzeCluster(NodeSet cluster, std::string& id, Position& pos,
1697  bool& hasTLS, TrafficLightType& type, SumoXMLNodeType& nodeType) {
1698  id += "_" + joinNamedToString(cluster, '_');
1699  hasTLS = false;
1700  bool ambiguousType = false;
1701  for (NBNode* j : cluster) {
1702  pos.add(j->getPosition());
1703  // add a traffic light if any of the cluster members was controlled
1704  if (j->isTLControlled()) {
1705  if (!hasTLS) {
1706  // init type
1707  type = (*j->getControllingTLS().begin())->getType();
1708  } else if (type != (*j->getControllingTLS().begin())->getType()) {
1709  ambiguousType = true;
1710  }
1711  hasTLS = true;
1712  }
1713  SumoXMLNodeType otherType = j->getType();
1714  if (nodeType == SumoXMLNodeType::UNKNOWN) {
1715  nodeType = otherType;
1716  } else if (nodeType != otherType) {
1717  if (hasTLS) {
1718  nodeType = SumoXMLNodeType::TRAFFIC_LIGHT;
1719  } else {
1720  if ((nodeType != SumoXMLNodeType::PRIORITY && (nodeType != SumoXMLNodeType::NOJUNCTION || otherType != SumoXMLNodeType::PRIORITY))
1721  || (otherType != SumoXMLNodeType::NOJUNCTION && otherType != SumoXMLNodeType::UNKNOWN && otherType != SumoXMLNodeType::PRIORITY)) {
1722  WRITE_WARNINGF("Ambiguous node type for node cluster '%' (%,%), setting to '" + toString(SumoXMLNodeType::PRIORITY) + "'.", id, toString(nodeType), toString(otherType));
1723  }
1724  nodeType = SumoXMLNodeType::PRIORITY;
1725  }
1726  }
1727  }
1728  pos.mul(1.0 / cluster.size());
1729  if (ambiguousType) {
1730  type = SUMOXMLDefinitions::TrafficLightTypes.get(OptionsCont::getOptions().getString("tls.default-type"));
1731  WRITE_WARNINGF("Ambiguous traffic light type for node cluster '%', setting to '%'.", id, toString(type));
1732  }
1733 }
1734 
1735 
1736 // ----------- (Helper) methods for guessing/computing traffic lights
1737 bool
1738 NBNodeCont::shouldBeTLSControlled(const NodeSet& c, double laneSpeedThreshold) const {
1739  bool tooFast = false;
1740  double laneSpeedSum = 0;
1741  std::set<NBEdge*> seen;
1742  for (NBNode* j : c) {
1743  const EdgeVector& edges = j->getEdges();
1744  for (EdgeVector::const_iterator k = edges.begin(); k != edges.end(); ++k) {
1745  if (c.find((*k)->getFromNode()) != c.end() && c.find((*k)->getToNode()) != c.end()) {
1746  continue;
1747  }
1748  if (j->hasIncoming(*k)) {
1749  laneSpeedSum += (double)(*k)->getNumLanes() * (*k)->getLaneSpeed(0);
1750  }
1751  if ((*k)->getLaneSpeed(0) * 3.6 > 79) {
1752  tooFast = true;
1753  }
1754  }
1755  }
1756  //std::cout << " c=" << joinNamedToString(c, ' ') << " f=" << f << " size=" << c.size() << " thresh=" << laneSpeedThreshold << " tooFast=" << tooFast << "\n";
1757  return !tooFast && laneSpeedSum >= laneSpeedThreshold && c.size() != 0;
1758 }
1759 
1760 bool
1762  // check whether all component nodes are solely pedestrian crossings
1763  // (these work fine without joining)
1764  for (NBNode* node : c) {
1765  EdgeVector nonPedIncoming;
1766  EdgeVector nonPedOutgoing;
1767  for (NBEdge* e : node->getIncomingEdges()) {
1768  if (e->getPermissions() != SVC_PEDESTRIAN) {
1769  nonPedIncoming.push_back(e);
1770  }
1771  }
1772  for (NBEdge* e : node->getOutgoingEdges()) {
1773  if (e->getPermissions() != SVC_PEDESTRIAN) {
1774  nonPedOutgoing.push_back(e);
1775  }
1776  }
1777  if (!node->geometryLike(nonPedIncoming, nonPedOutgoing)) {
1778  //for (NBNode* node : c) {
1779  // if (node->getID() == "2480337678") {
1780  // std::cout << " node=" << node->getID() << " nonPedIncoming=" << toString(nonPedIncoming) << " nonPedOutgoing=" << toString(nonPedOutgoing) << "\n";
1781  // }
1782  //}
1783  return false;
1784  }
1785  }
1786  return true;
1787 }
1788 
1789 
1790 bool
1792  for (NBNode* node : c) {
1793  if (node->isTLControlled()) {
1794  const std::string tlID = (*node->getControllingTLS().begin())->getID();
1795  if (tlID != node->getID()
1796  && !StringUtils::startsWith(tlID, "joinedS_")
1797  && !StringUtils::startsWith(tlID, "joinedG_")
1798  && !StringUtils::startsWith(tlID, "GS")) {
1799  return true;
1800  }
1801  }
1802  }
1803  return false;
1804 }
1805 
1806 
1807 void
1809  myGuessedTLS.clear();
1810  // build list of definitely not tls-controlled junctions
1811  const double laneSpeedThreshold = oc.getFloat("tls.guess.threshold");
1812  std::vector<NBNode*> ncontrolled;
1813  if (oc.isSet("tls.unset")) {
1814  std::vector<std::string> notTLControlledNodes = oc.getStringVector("tls.unset");
1815  for (std::vector<std::string>::const_iterator i = notTLControlledNodes.begin(); i != notTLControlledNodes.end(); ++i) {
1816  NBNode* n = NBNodeCont::retrieve(*i);
1817  if (n == nullptr) {
1818  throw ProcessError(" The junction '" + *i + "' to set as not-controlled is not known.");
1819  }
1820  std::set<NBTrafficLightDefinition*> tls = n->getControllingTLS();
1821  for (std::set<NBTrafficLightDefinition*>::const_iterator j = tls.begin(); j != tls.end(); ++j) {
1822  (*j)->removeNode(n);
1823  }
1824  n->removeTrafficLights();
1825  ncontrolled.push_back(n);
1826  }
1827  }
1828 
1830  // loop#1 checking whether the node shall be tls controlled,
1831  // because it is assigned to a district
1832  if (oc.exists("tls.taz-nodes") && oc.getBool("tls.taz-nodes")) {
1833  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
1834  NBNode* cur = (*i).second;
1835  if (cur->isNearDistrict() && std::find(ncontrolled.begin(), ncontrolled.end(), cur) == ncontrolled.end()) {
1836  setAsTLControlled(cur, tlc, type);
1837  }
1838  }
1839  }
1840 
1841  // figure out which nodes mark the locations of TLS signals
1842  // This assumes nodes are already joined
1843  if (oc.exists("tls.guess-signals") && oc.getBool("tls.guess-signals")) {
1844  // prepare candidate edges
1845  const double signalDist = oc.getFloat("tls.guess-signals.dist");
1846  for (const auto& item : myNodes) {
1847  const NBNode* node = item.second;
1848  if (node->isTLControlled() && (node->getIncomingEdges().size() == 1 || node->geometryLike())) {
1849 #ifdef DEBUG_GUESSSIGNALS
1850  if (DEBUGCOND(node) || true) {
1851  std::cout << " propagate TLS from " << node->getID() << " downstream\n";
1852  }
1853 #endif
1854  for (NBEdge* edge : node->getOutgoingEdges()) {
1855  // do not overwrite closer signals
1856  if (edge->getSignalOffset() == NBEdge::UNSPECIFIED_SIGNAL_OFFSET) {
1857  edge->setSignalPosition(node->getPosition(), node);
1858  }
1859  }
1860  }
1861  }
1862  std::set<NBEdge*> seen;
1863  std::set<NBEdge*> check;
1864  for (const auto& item : myNodes) {
1865  for (NBEdge* edge : item.second->getOutgoingEdges()) {
1866  if (edge->getSignalPosition() != Position::INVALID) {
1867  check.insert(edge);
1868  seen.insert(edge);
1869 #ifdef DEBUG_GUESSSIGNALS
1870  if (DEBUGCOND(edge->getSignalNode()) || true) {
1871  std::cout << " primary signalPosition edge=" << edge->getID() << " pos=" << edge->getSignalPosition() << "\n";
1872  }
1873 #endif
1874  }
1875  }
1876  }
1877  // propagate signal position until the next real intersection
1878  while (check.size() > 0) {
1879  NBEdge* const edge = *check.begin();
1880  check.erase(check.begin());
1881  seen.insert(edge);
1882  NBNode* const nextNode = edge->getToNode();
1883  if (nextNode->geometryLike() && !nextNode->isTLControlled()) {
1884  for (NBEdge* const outEdge : nextNode->getOutgoingEdges()) {
1885  if (seen.count(outEdge) == 0) {
1886  outEdge->setSignalPosition(edge->getSignalPosition(), edge->getSignalNode());
1887 #ifdef DEBUG_GUESSSIGNALS
1888  if (DEBUGCOND(edge->getSignalNode()) || true) {
1889  std::cout << " setSignalPosition edge=" << outEdge->getID() << " pos=" << edge->getSignalPosition() << "\n";
1890  }
1891 #endif
1892  check.insert(outEdge);
1893  }
1894  }
1895  }
1896  }
1897 
1898  // check which nodes should be controlled
1899  for (std::map<std::string, NBNode*>::const_iterator i = myNodes.begin(); i != myNodes.end(); ++i) {
1900  NBNode* node = i->second;
1901  if (find(ncontrolled.begin(), ncontrolled.end(), node) != ncontrolled.end()) {
1902  continue;
1903  }
1904  const EdgeVector& incoming = node->getIncomingEdges();
1905  const EdgeVector& outgoing = node->getOutgoingEdges();
1906  if (!node->isTLControlled() && incoming.size() > 1 && !node->geometryLike()
1908  && node->getType() != SumoXMLNodeType::RAIL_CROSSING) {
1909  std::vector<const NBNode*> signals;
1910  bool isTLS = true;
1911  // check if there is a signal at every incoming edge
1912  for (EdgeVector::const_iterator it_i = incoming.begin(); it_i != incoming.end(); ++it_i) {
1913  const NBEdge* inEdge = *it_i;
1914  if (inEdge->getSignalOffset() == NBEdge::UNSPECIFIED_SIGNAL_OFFSET && inEdge->getPermissions() != SVC_TRAM) {
1915 #ifdef DEBUG_GUESSSIGNALS
1916  if (DEBUGCOND(node)) {
1917  std::cout << " noTLS, edge=" << inEdge->getID() << "\n";
1918  }
1919 #endif
1920  isTLS = false;
1921  break;
1922  }
1923  }
1924  if (isTLS) {
1925  node->updateSurroundingGeometry();
1926  // check if all signals are within the required distance
1927  // (requires detailed geometry computation)
1928  for (EdgeVector::const_iterator it_i = incoming.begin(); it_i != incoming.end(); ++it_i) {
1929  const NBEdge* inEdge = *it_i;
1930  if ((inEdge->getSignalOffset() == NBEdge::UNSPECIFIED_SIGNAL_OFFSET || inEdge->getSignalOffset() > signalDist)
1931  && inEdge->getPermissions() != SVC_TRAM) {
1932 #ifdef DEBUG_GUESSSIGNALS
1933  if (DEBUGCOND(node)) {
1934  std::cout << " noTLS, edge=" << inEdge->getID() << " offset=" << inEdge->getSignalOffset() << " tlsPos=" << inEdge->getSignalPosition() << "\n";
1935  }
1936 #endif
1937  isTLS = false;
1938  break;
1939  }
1940  const NBNode* signal = inEdge->getSignalNode();
1941  if (signal != nullptr) {
1942  signals.push_back(signal);
1943  }
1944  }
1945  // outgoing edges may be tagged with pedestrian crossings. These
1946  // should also be merged into the main TLS
1947  for (const NBEdge* outEdge : outgoing) {
1948  NBNode* cand = outEdge->getToNode();
1949  if (cand->isTLControlled() && cand->geometryLike() && outEdge->getLength() <= signalDist) {
1950 #ifdef DEBUG_GUESSSIGNALS
1951  if (DEBUGCOND(node)) {
1952  std::cout << " node=" << node->getID() << " outEdge=" << outEdge->getID() << " signalNode=" << cand->getID() << " len=" << outEdge->getLength() << "\n";
1953  }
1954 #endif
1955  signals.push_back(cand);
1956  }
1957  }
1958  }
1959  if (isTLS) {
1960  for (const NBNode* s : signals) {
1961  std::set<NBTrafficLightDefinition*> tls = s->getControllingTLS();
1962  const_cast<NBNode*>(s)->reinit(s->getPosition(), SumoXMLNodeType::PRIORITY);
1963  for (std::set<NBTrafficLightDefinition*>::iterator k = tls.begin(); k != tls.end(); ++k) {
1964  tlc.removeFully(s->getID());
1965  }
1966  }
1967  //if (true) std::cout << " node=" << node->getID() << " signals=" << toString(signals) << "\n";
1968  NBTrafficLightDefinition* tlDef = new NBOwnTLDef("GS_" + node->getID(), node, 0, type);
1969  // @todo patch endOffset for all incoming lanes according to the signal positions
1970  if (!tlc.insert(tlDef)) {
1971  // actually, nothing should fail here
1972  WRITE_WARNINGF("Could not build joined tls '%'.", node->getID());
1973  delete tlDef;
1974  return;
1975  }
1976  }
1977  }
1978  }
1979  }
1980 
1981  // guess joined tls first, if wished
1982  if (oc.getBool("tls.guess.joining")) {
1983  // get node clusters
1984  NodeClusters cands;
1985  generateNodeClusters(oc.getFloat("tls.join-dist"), cands);
1986  // check these candidates (clusters) whether they should be controlled by a tls
1987  for (NodeClusters::iterator i = cands.begin(); i != cands.end();) {
1988  NodeSet& c = (*i);
1989  // regard only junctions which are not yet controlled and are not
1990  // forbidden to be controlled
1991  for (NodeSet::iterator j = c.begin(); j != c.end();) {
1992  if ((*j)->isTLControlled() || std::find(ncontrolled.begin(), ncontrolled.end(), *j) != ncontrolled.end()) {
1993  c.erase(j++);
1994  } else {
1995  ++j;
1996  }
1997  }
1998  // check whether the cluster should be controlled
1999  // to avoid gigantic clusters, assume that at most 4 nodes should be needed for a guessed-joined-tls
2000  if (c.size() == 0 || !shouldBeTLSControlled(c, laneSpeedThreshold * c.size() / MIN2((int)c.size(), 4))) {
2001  i = cands.erase(i);
2002  } else {
2003  ++i;
2004  }
2005  }
2006  // cands now only contain sets of junctions that shall be joined into being tls-controlled
2007  int index = 0;
2008  for (auto nodeSet : cands) {
2009  std::vector<NBNode*> nodes;
2010  for (NBNode* node : nodeSet) {
2011  nodes.push_back(node);
2012  myGuessedTLS.insert(node);
2013  }
2014  std::string id = "joinedG_" + toString(index++);
2015  NBTrafficLightDefinition* tlDef = new NBOwnTLDef(id, nodes, 0, type);
2016  if (!tlc.insert(tlDef)) {
2017  // actually, nothing should fail here
2018  WRITE_WARNING("Could not build guessed, joined tls.");
2019  delete tlDef;
2020  return;
2021  }
2022  }
2023  }
2024 
2025  // guess single tls
2026  if (oc.getBool("tls.guess")) {
2027  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2028  NBNode* cur = (*i).second;
2029  // do nothing if already is tl-controlled
2030  if (cur->isTLControlled()) {
2031  continue;
2032  }
2033  // do nothing if in the list of explicit non-controlled junctions
2034  if (find(ncontrolled.begin(), ncontrolled.end(), cur) != ncontrolled.end()) {
2035  continue;
2036  }
2037  NodeSet c;
2038  c.insert(cur);
2039  if (!shouldBeTLSControlled(c, laneSpeedThreshold) || cur->geometryLike()) {
2040  continue;
2041  }
2042  setAsTLControlled(cur, tlc, type);
2043  myGuessedTLS.insert(cur);
2044  }
2045  }
2046 }
2047 
2049  std::set<NBTrafficLightDefinition*> recompute;
2050  for (NBNode* node : myGuessedTLS) {
2051  if (!node->hasConflict()) {
2052  const std::set<NBTrafficLightDefinition*>& tlDefs = node->getControllingTLS();
2053  recompute.insert(tlDefs.begin(), tlDefs.end());
2054  node->removeTrafficLights(true);
2055  for (NBEdge* edge : node->getIncomingEdges()) {
2056  edge->clearControllingTLInformation();
2057  }
2058  }
2059  }
2060  for (NBTrafficLightDefinition* def : recompute) {
2061  if (def->getNodes().size() == 0) {
2062  tlc.removeFully(def->getID());
2063  } else {
2064  def->setParticipantsInformation();
2065  def->setTLControllingInformation();
2067  }
2068  }
2069 }
2070 
2071 
2072 void
2074  for (const auto& item : myNodes) {
2075  item.second->computeKeepClear();
2076  }
2077 }
2078 
2079 
2080 void
2082  NodeClusters cands;
2083  generateNodeClusters(maxdist, cands);
2084  IDSupplier idSupplier("joinedS_");
2085  for (NodeSet& c : cands) {
2086  for (NodeSet::iterator j = c.begin(); j != c.end();) {
2087  if (!(*j)->isTLControlled()) {
2088  c.erase(j++);
2089  } else {
2090  ++j;
2091  }
2092  }
2093  if (c.size() < 2 || onlyCrossings(c) || customTLID(c)) {
2094  continue;
2095  }
2096  // figure out type of the joined TLS
2097  Position dummyPos;
2098  bool dummySetTL;
2099  std::string id = "joined"; // prefix (see #3871)
2100  TrafficLightType type;
2102  analyzeCluster(c, id, dummyPos, dummySetTL, type, nodeType);
2103  for (NBNode* j : c) {
2104  std::set<NBTrafficLightDefinition*> tls = j->getControllingTLS();
2105  j->removeTrafficLights();
2106  for (std::set<NBTrafficLightDefinition*>::iterator k = tls.begin(); k != tls.end(); ++k) {
2107  tlc.removeFully(j->getID());
2108  }
2109  }
2110  std::vector<NBNode*> nodes;
2111  for (NBNode* j : c) {
2112  nodes.push_back(j);
2113  }
2114  id = idSupplier.getNext();
2115  while (tlc.getPrograms(id).size() > 0) {
2116  id = idSupplier.getNext();
2117  }
2118  NBTrafficLightDefinition* tlDef = new NBOwnTLDef(id, nodes, 0, type);
2119  if (!tlc.insert(tlDef)) {
2120  // actually, nothing should fail here
2121  WRITE_WARNING("Could not build a joined tls.");
2122  delete tlDef;
2123  return;
2124  }
2125  }
2126 }
2127 
2128 
2129 void
2131  TrafficLightType type, std::string id) {
2132  if (id == "") {
2133  id = node->getID();
2134  }
2135  NBTrafficLightDefinition* tlDef = new NBOwnTLDef(id, node, 0, type);
2136  if (!tlc.insert(tlDef)) {
2137  // actually, nothing should fail here
2138  WRITE_WARNINGF("Building a tl-logic for junction '%' twice is not possible.", id);
2139  delete tlDef;
2140  return;
2141  }
2142 }
2143 
2144 
2145 // -----------
2146 void
2148  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2149  (*i).second->computeLanes2Lanes();
2150  }
2151 }
2152 
2153 
2154 // computes the "wheel" of incoming and outgoing edges for every node
2155 void
2157  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2158  (*i).second->computeLogic(ec);
2159  }
2160 }
2161 
2162 
2163 void
2165  std::set<NBNode*> roundaboutNodes;
2166  const bool checkLaneFoesAll = oc.getBool("check-lane-foes.all");
2167  const bool checkLaneFoesRoundabout = !checkLaneFoesAll && oc.getBool("check-lane-foes.roundabout");
2168  if (checkLaneFoesRoundabout) {
2169  const std::set<EdgeSet>& roundabouts = ec.getRoundabouts();
2170  for (std::set<EdgeSet>::const_iterator i = roundabouts.begin(); i != roundabouts.end(); ++i) {
2171  for (EdgeSet::const_iterator j = (*i).begin(); j != (*i).end(); ++j) {
2172  roundaboutNodes.insert((*j)->getToNode());
2173  }
2174  }
2175  }
2176  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2177  const bool checkLaneFoes = checkLaneFoesAll || (checkLaneFoesRoundabout && roundaboutNodes.count((*i).second) > 0);
2178  (*i).second->computeLogic2(checkLaneFoes);
2179  }
2180 }
2181 
2182 
2183 void
2185  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2186  delete ((*i).second);
2187  }
2188  myNodes.clear();
2189  for (auto& item : myExtractedNodes) {
2190  delete item.second;
2191  }
2192  myExtractedNodes.clear();
2193 }
2194 
2195 
2196 std::string
2198  int counter = 0;
2199  std::string freeID = "SUMOGenerated" + toString<int>(counter);
2200  // While there is a node with id equal to freeID
2201  while (retrieve(freeID) != nullptr) {
2202  // update counter and generate a new freeID
2203  counter++;
2204  freeID = "SUMOGenerated" + toString<int>(counter);
2205  }
2206  return freeID;
2207 }
2208 
2209 
2210 void
2211 NBNodeCont::computeNodeShapes(double mismatchThreshold) {
2212  for (NodeCont::iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2213  (*i).second->computeNodeShape(mismatchThreshold);
2214  }
2215 }
2216 
2217 
2218 void
2220  int numUnregulatedJunctions = 0;
2221  int numDeadEndJunctions = 0;
2222  int numTrafficLightJunctions = 0;
2223  int numPriorityJunctions = 0;
2224  int numRightBeforeLeftJunctions = 0;
2225  int numAllWayStopJunctions = 0;
2226  int numZipperJunctions = 0;
2227  int numDistrictJunctions = 0;
2228  int numRailCrossing = 0;
2229  int numRailSignals = 0;
2230  for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); i++) {
2231  switch ((*i).second->getType()) {
2233  ++numUnregulatedJunctions;
2234  break;
2236  ++numDeadEndJunctions;
2237  break;
2241  ++numTrafficLightJunctions;
2242  break;
2245  ++numPriorityJunctions;
2246  break;
2248  ++numRightBeforeLeftJunctions;
2249  break;
2251  ++numAllWayStopJunctions;
2252  break;
2254  ++numZipperJunctions;
2255  break;
2257  ++numDistrictJunctions;
2258  break;
2260  ++numRailCrossing;
2261  break;
2263  ++numRailSignals;
2264  break;
2266  // should not happen
2267  break;
2268  default:
2269  break;
2270  }
2271  }
2272  WRITE_MESSAGE(" Node type statistics:");
2273  WRITE_MESSAGE(" Unregulated junctions : " + toString(numUnregulatedJunctions));
2274  if (numDeadEndJunctions > 0) {
2275  WRITE_MESSAGE(" Dead-end junctions : " + toString(numDeadEndJunctions));
2276  }
2277  WRITE_MESSAGE(" Priority junctions : " + toString(numPriorityJunctions));
2278  WRITE_MESSAGE(" Right-before-left junctions : " + toString(numRightBeforeLeftJunctions));
2279  if (numTrafficLightJunctions > 0) {
2280  WRITE_MESSAGE(" Traffic light junctions : " + toString(numTrafficLightJunctions));
2281  }
2282  if (numAllWayStopJunctions > 0) {
2283  WRITE_MESSAGE(" All-way stop junctions : " + toString(numAllWayStopJunctions));
2284  }
2285  if (numZipperJunctions > 0) {
2286  WRITE_MESSAGE(" Zipper-merge junctions : " + toString(numZipperJunctions));
2287  }
2288  if (numRailCrossing > 0) {
2289  WRITE_MESSAGE(" Rail crossing junctions : " + toString(numRailCrossing));
2290  }
2291  if (numRailSignals > 0) {
2292  WRITE_MESSAGE(" Rail signal junctions : " + toString(numRailSignals));
2293  }
2294  if (numDistrictJunctions > 0) {
2295  WRITE_MESSAGE(" District junctions : " + toString(numDistrictJunctions));
2296  }
2297 }
2298 
2299 
2300 std::vector<std::string>
2302  std::vector<std::string> ret;
2303  for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); ++i) {
2304  ret.push_back((*i).first);
2305  }
2306  return ret;
2307 }
2308 
2309 
2310 void
2311 NBNodeCont::rename(NBNode* node, const std::string& newID) {
2312  if (myNodes.count(newID) != 0) {
2313  throw ProcessError("Attempt to rename node using existing id '" + newID + "'");
2314  }
2315  myNodes.erase(node->getID());
2316  node->setID(newID);
2317  myNodes[newID] = node;
2318 }
2319 
2320 
2321 void
2322 NBNodeCont::discardTrafficLights(NBTrafficLightLogicCont& tlc, bool geometryLike, bool guessSignals) {
2323  for (NodeCont::const_iterator i = myNodes.begin(); i != myNodes.end(); ++i) {
2324  NBNode* node = i->second;
2325  if (node->isTLControlled() && (!geometryLike || node->geometryLike())) {
2326  // make a copy of tldefs
2327  const std::set<NBTrafficLightDefinition*> tldefs = node->getControllingTLS();
2328  if (geometryLike && (*tldefs.begin())->getNodes().size() > 1) {
2329  // do not remove joined tls when only removing geometry-like tls
2330  continue;
2331  }
2332  if (guessSignals && node->isTLControlled() && node->geometryLike()) {
2333  // record signal location
2334  for (NBEdge* edge : node->getOutgoingEdges()) {
2335  edge->setSignalPosition(node->getPosition(), nullptr);
2336 #ifdef DEBUG_GUESSSIGNALS
2337  std::cout << " discard-simple " << node->getID() << " edge=" << edge->getID() << " pos=" << edge->getSignalPosition() << "\n";
2338 #endif
2339  }
2340  }
2341  for (std::set<NBTrafficLightDefinition*>::const_iterator it = tldefs.begin(); it != tldefs.end(); ++it) {
2342  NBTrafficLightDefinition* tlDef = *it;
2343  node->removeTrafficLight(tlDef);
2344  tlc.extract(tlDef);
2345  }
2347  node->reinit(node->getPosition(), newType);
2348  }
2349  }
2350 }
2351 
2352 
2353 void
2355  for (auto& item : myNodes) {
2356  NBNode* node = item.second;
2357  if (node->getType() == SumoXMLNodeType::RAIL_SIGNAL) {
2359  }
2360  }
2361 }
2362 
2363 
2364 int
2365 NBNodeCont::remapIDs(bool numericaIDs, bool reservedIDs, const std::string& prefix) {
2366  bool startGiven = !OptionsCont::getOptions().isDefault("numerical-ids.node-start");
2367  std::vector<std::string> avoid;
2368  if (startGiven) {
2369  avoid.push_back(toString(OptionsCont::getOptions().getInt("numerical-ids.node-start") - 1));
2370  } else {
2371  avoid = getAllNames();
2372  }
2373  std::set<std::string> reserve;
2374  if (reservedIDs) {
2375  NBHelpers::loadPrefixedIDsFomFile(OptionsCont::getOptions().getString("reserved-ids"), "node:", reserve); // backward compatibility
2376  NBHelpers::loadPrefixedIDsFomFile(OptionsCont::getOptions().getString("reserved-ids"), "junction:", reserve); // selection format
2377  avoid.insert(avoid.end(), reserve.begin(), reserve.end());
2378  }
2379  IDSupplier idSupplier("", avoid);
2380  NodeSet toChange;
2381  for (NodeCont::iterator it = myNodes.begin(); it != myNodes.end(); it++) {
2382  if (startGiven) {
2383  toChange.insert(it->second);
2384  continue;
2385  }
2386  if (numericaIDs) {
2387  try {
2388  StringUtils::toLong(it->first);
2389  } catch (NumberFormatException&) {
2390  toChange.insert(it->second);
2391  }
2392  }
2393  if (reservedIDs && reserve.count(it->first) > 0) {
2394  toChange.insert(it->second);
2395  }
2396  }
2397  const bool origNames = OptionsCont::getOptions().getBool("output.original-names");
2398  for (NBNode* node : toChange) {
2399  myNodes.erase(node->getID());
2400  }
2401  for (NBNode* node : toChange) {
2402  if (origNames) {
2403  node->setParameter(SUMO_PARAM_ORIGID, node->getID());
2404  }
2405  node->setID(idSupplier.getNext());
2406  myNodes[node->getID()] = node;
2407  }
2408  if (prefix.empty()) {
2409  return (int)toChange.size();
2410  } else {
2411  int renamed = 0;
2412  // make a copy because we will modify the map
2413  auto oldNodes = myNodes;
2414  for (auto item : oldNodes) {
2415  if (!StringUtils::startsWith(item.first, prefix)) {
2416  rename(item.second, prefix + item.first);
2417  renamed++;
2418  }
2419  }
2420  return renamed;
2421  }
2422 }
2423 
2424 
2425 int
2427  NodeSet topRightFront;
2428  NodeSet topLeftFront;
2429  NodeSet bottomRightFront;
2430  NodeSet bottomLeftFront;
2431  for (const auto& item : myNodes) {
2432  paretoCheck(item.second, topRightFront, 1, 1);
2433  paretoCheck(item.second, topLeftFront, -1, 1);
2434  paretoCheck(item.second, bottomRightFront, 1, -1);
2435  paretoCheck(item.second, bottomLeftFront, -1, -1);
2436  }
2437  NodeSet front;
2438  front.insert(topRightFront.begin(), topRightFront.end());
2439  front.insert(topLeftFront.begin(), topLeftFront.end());
2440  front.insert(bottomRightFront.begin(), bottomRightFront.end());
2441  front.insert(bottomLeftFront.begin(), bottomLeftFront.end());
2442  int numFringe = 0;
2443  for (NBNode* n : front) {
2444  const int in = (int)n->getIncomingEdges().size();
2445  const int out = (int)n->getOutgoingEdges().size();
2446  if ((in <= 1 && out <= 1) &&
2447  (in == 0 || out == 0
2448  || n->getIncomingEdges().front()->isTurningDirectionAt(n->getOutgoingEdges().front()))) {
2449  n->setFringeType(FringeType::OUTER);
2450  numFringe++;
2451  }
2452  }
2453  return numFringe;
2454 }
2455 
2456 
2457 void
2458 NBNodeCont::paretoCheck(NBNode* node, NodeSet& frontier, int xSign, int ySign) {
2459  const double x = node->getPosition().x() * xSign;
2460  const double y = node->getPosition().y() * ySign;
2461  std::vector<NBNode*> dominated;
2462  for (NBNode* fn : frontier) {
2463  const double x2 = fn->getPosition().x() * xSign;
2464  const double y2 = fn->getPosition().y() * ySign;
2465  if (x2 >= x && y2 >= y) {
2466  return;
2467  } else if (x2 <= x && y2 <= y) {
2468  dominated.push_back(fn);
2469  }
2470  }
2471  frontier.insert(node);
2472  for (NBNode* r : dominated) {
2473  frontier.erase(r);
2474  }
2475 }
2476 
2477 
2478 /****************************************************************************/
#define WRITE_WARNINGF(...)
Definition: MsgHandler.h:277
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:278
#define WRITE_ERROR(msg)
Definition: MsgHandler.h:284
#define WRITE_WARNING(msg)
Definition: MsgHandler.h:276
std::set< NBNode *, ComparatorIdLess > NodeSet
Definition: NBCont.h:51
std::set< NBEdge * > EdgeSet
container for unique edges
Definition: NBCont.h:49
std::vector< NBEdge * > EdgeVector
container for (sorted) edges
Definition: NBCont.h:34
#define DEBUGCOND(obj)
Definition: NBNodeCont.cpp:71
#define MAX_SLIPLANE_LENGTH
Definition: NBNodeCont.cpp:60
bool isRailway(SVCPermissions permissions)
Returns whether an edge with the given permission is a railway edge.
@ SVC_RAIL_CLASSES
classes which drive on tracks
@ SVC_PASSENGER
vehicle is a passenger car (a "normal" car)
@ SVC_TRAM
vehicle is a light rail
@ SVC_PEDESTRIAN
pedestrian
int SVCPermissions
bitset where each bit declares whether a certain SVC may use this edge/lane
TrafficLightType
const std::string SUMO_PARAM_ORIGID
SumoXMLNodeType
Numbers representing special SUMO-XML-attribute values for representing node- (junction-) types used ...
bool gDebugFlag1
global utility flags for debugging
Definition: StdDefs.cpp:31
const double SUMO_const_laneWidth
Definition: StdDefs.h:47
#define UNUSED_PARAMETER(x)
Definition: StdDefs.h:29
T MIN2(T a, T b)
Definition: StdDefs.h:73
T MAX2(T a, T b)
Definition: StdDefs.h:79
std::string joinNamedToString(const std::set< T *, C > &ns, const T_BETWEEN &between)
Definition: ToString.h:284
std::string joinToString(const std::vector< T > &v, const T_BETWEEN &between, std::streamsize accuracy=gPrecision)
Definition: ToString.h:250
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:44
std::string getNext()
Returns the next id.
Definition: IDSupplier.cpp:51
A container for districts.
A class representing a single district.
Definition: NBDistrict.h:62
Storage for edges, including some functionality operating on multiple edges.
Definition: NBEdgeCont.h:59
std::map< std::string, NBEdge * >::const_iterator begin() const
Returns the pointer to the begin of the stored edges.
Definition: NBEdgeCont.h:183
NBEdge * getByID(const std::string &edgeID) const
Returns the edge with id if it exists.
const std::set< EdgeSet > getRoundabouts() const
Returns the determined roundabouts.
std::map< std::string, NBEdge * >::const_iterator end() const
Returns the pointer to the end of the stored edges.
Definition: NBEdgeCont.h:191
void extract(NBDistrictCont &dc, NBEdge *edge, bool remember=false)
Removes the given edge from the container like erase but does not delete it.
Definition: NBEdgeCont.cpp:416
void erase(NBDistrictCont &dc, NBEdge *edge)
Removes the given edge from the container (deleting it)
Definition: NBEdgeCont.cpp:409
NBEdge * retrieve(const std::string &id, bool retrieveExtracted=false) const
Returns the edge that has the given id.
Definition: NBEdgeCont.cpp:275
bool hasPostProcessConnection(const std::string &from, const std::string &to="")
void joinSameNodeConnectingEdges(NBDistrictCont &dc, NBTrafficLightLogicCont &tlc, EdgeVector edges)
Joins the given edges because they connect the same nodes.
Definition: NBEdgeCont.cpp:956
std::vector< std::string > getAllNames() const
Returns all ids of known edges.
Definition: NBEdgeCont.cpp:718
The representation of a single edge during network building.
Definition: NBEdge.h:91
double getLength() const
Returns the computed length of the edge.
Definition: NBEdge.h:563
SVCPermissions getPermissions(int lane=-1) const
get the union of allowed classes over all lanes or for a specific lane
Definition: NBEdge.cpp:3655
double getLoadedLength() const
Returns the length was set explicitly or the computed length if it wasn't set.
Definition: NBEdge.h:572
static EdgeVector filterByPermissions(const EdgeVector &edges, SVCPermissions permissions)
return only those edges that permit at least one of the give permissions
Definition: NBEdge.cpp:4075
const Position & getSignalPosition() const
Returns the position of a traffic signal on this edge.
Definition: NBEdge.h:659
EdgeBuildingStep getStep() const
The building step of this edge.
Definition: NBEdge.h:598
NBEdge * getStraightContinuation(SVCPermissions permissions) const
return the straightest follower edge for the given permissions or nullptr (never returns turn-arounds...
Definition: NBEdge.cpp:4086
const NBNode * getSignalNode() const
Returns the node that (possibly) represents a traffic signal controlling at the end of this edge.
Definition: NBEdge.h:664
const std::string & getID() const
Definition: NBEdge.h:1423
bool isNearEnough2BeJoined2(NBEdge *e, double threshold) const
Check if edge is near enought to be joined to another edge.
Definition: NBEdge.cpp:3351
NBNode * getToNode() const
Returns the destination node of the edge.
Definition: NBEdge.h:516
@ INIT
The edge has been loaded, nothing is computed yet.
double getSpeed() const
Returns the speed allowed on this edge.
Definition: NBEdge.h:589
static const double UNSPECIFIED_SIGNAL_OFFSET
unspecified signal offset
Definition: NBEdge.h:342
@ USER
The connection was given by the user.
double getAngleAtNode(const NBNode *const node) const
Returns the angle of the edge's geometry at the given node.
Definition: NBEdge.cpp:1946
double getSignalOffset() const
Returns the offset of a traffic signal from the end of this edge.
Definition: NBEdge.cpp:3701
const std::vector< Connection > & getConnections() const
Returns the connections.
Definition: NBEdge.h:964
NBNode * getFromNode() const
Returns the origin node of the edge.
Definition: NBEdge.h:509
EdgeVector getIncomingEdges() const
Returns the list of incoming edges unsorted.
Definition: NBEdge.cpp:1263
static void loadPrefixedIDsFomFile(const std::string &file, const std::string prefix, std::set< std::string > &into)
Add prefixed ids defined in file.
Definition: NBHelpers.cpp:104
static double relAngle(double angle1, double angle2)
computes the relative angle between the two angles
Definition: NBHelpers.cpp:45
static void loadEdgesFromFile(const std::string &file, std::set< std::string > &into)
Add edge ids defined in file (either ID or edge:ID per line) into the given set.
Definition: NBHelpers.cpp:86
void clear()
deletes all nodes
std::set< std::string > myJoinExclusions
set of node ids which should not be joined
Definition: NBNodeCont.h:400
NamedRTree myRTree
node positions for faster lookup
Definition: NBNodeCont.h:418
std::map< std::string, NBNode * >::const_iterator begin() const
Returns the pointer to the begin of the stored nodes.
Definition: NBNodeCont.h:113
void avoidOverlap()
fix overlap
Definition: NBNodeCont.cpp:455
bool onlyCrossings(const NodeSet &c) const
check wheter the set of nodes only contains pedestrian crossings
std::vector< std::pair< std::set< std::string >, NBNode * > > myClusters2Join
loaded sets of node ids to join (cleared after use)
Definition: NBNodeCont.h:403
void addCluster2Join(std::set< std::string > cluster, NBNode *node)
add ids of nodes which shall be joined into a single node
Definition: NBNodeCont.cpp:592
void recheckGuessedTLS(NBTrafficLightLogicCont &tlc)
recheck myGuessedTLS after node logics are computed
std::vector< NodeSet > NodeClusters
Definition of a node cluster container.
Definition: NBNodeCont.h:61
void computeKeepClear()
compute keepClear status for all connections
NodeCont myNodes
The map of names to nodes.
Definition: NBNodeCont.h:394
static void pruneLongEdges(NodeSet &cluster, double maxDist)
avoid removal of long edges when joinining junction clusters
Definition: NBNodeCont.cpp:876
void registerJoinedCluster(const NodeSet &cluster)
gets all joined clusters (see doc for myClusters2Join)
std::string getFreeID()
generates a new node ID
void addJoinExclusion(const std::vector< std::string > &ids, bool check=false)
Definition: NBNodeCont.cpp:576
void paretoCheck(NBNode *node, NodeSet &frontier, int xSign, int ySign)
update pareto frontier with the given node
bool maybeSlipLaneStart(const NBNode *n, EdgeVector &outgoing, double &inAngle) const
check whether the given node maybe the start of a slip lane
bool erase(NBNode *node)
Removes the given node, deleting it.
Definition: NBNodeCont.cpp:149
int joinLoadedClusters(NBDistrictCont &dc, NBEdgeCont &ec, NBTrafficLightLogicCont &tlc)
Joins loaded junction clusters (see NIXMLNodesHandler)
Definition: NBNodeCont.cpp:633
bool insert(const std::string &id, const Position &position, NBDistrict *district=0)
Inserts a node into the map.
Definition: NBNodeCont.cpp:90
NBNode * retrieve(const std::string &id) const
Returns the node with the given name.
Definition: NBNodeCont.cpp:119
NodeCont myExtractedNodes
The extracted nodes which are kept for reference.
Definition: NBNodeCont.h:397
void joinTLS(NBTrafficLightLogicCont &tlc, double maxdist)
Builds clusters of tls-controlled junctions and joins the control if possible.
int removeUnwishedNodes(NBDistrictCont &dc, NBEdgeCont &ec, NBTrafficLightLogicCont &tlc, NBPTStopCont &sc, NBPTLineCont &lc, NBParkingCont &pc, bool removeGeometryNodes)
Removes "unwished" nodes.
Definition: NBNodeCont.cpp:381
~NBNodeCont()
Destructor.
Definition: NBNodeCont.cpp:83
bool reduceToCircle(NodeSet &cluster, int circleSize, NodeSet startNodes, std::vector< NBNode * > cands=std::vector< NBNode * >()) const
try to find a joinable subset (recursively)
bool extract(NBNode *node, bool remember=false)
Removes the given node but does not delete it.
Definition: NBNodeCont.cpp:160
void removeComponents(NBDistrictCont &dc, NBEdgeCont &ec, const int numKeep)
Checks the network for weak connectivity and removes all but the largest components....
Definition: NBNodeCont.cpp:323
NBNodeCont()
Constructor.
Definition: NBNodeCont.cpp:78
std::vector< std::string > getAllNames() const
get all node names
void computeLogics2(const NBEdgeCont &ec, OptionsCont &oc)
compute right-of-way logic for all lane-to-lane connections
void rename(NBNode *node, const std::string &newID)
Renames the node. Throws exception if newID already exists.
void joinNodeClusters(NodeClusters clusters, NBDistrictCont &dc, NBEdgeCont &ec, NBTrafficLightLogicCont &tlc, bool resetConnections=false)
joins the given node clusters
void discardRailSignals()
void printBuiltNodesStatistics() const
Prints statistics about built nodes.
void removeIsolatedRoads(NBDistrictCont &dc, NBEdgeCont &ec)
Removes sequences of edges that are not connected with a junction. Simple roads without junctions som...
Definition: NBNodeCont.cpp:235
void setAsTLControlled(NBNode *node, NBTrafficLightLogicCont &tlc, TrafficLightType type, std::string id="")
Sets the given node as being controlled by a tls.
std::set< const NBNode * > mySplit
nodes that were created when splitting an edge
Definition: NBNodeCont.h:412
void joinSimilarEdges(NBDistrictCont &dc, NBEdgeCont &ec, NBTrafficLightLogicCont &tlc)
Joins edges connecting the same nodes.
Definition: NBNodeCont.cpp:190
void computeLogics(const NBEdgeCont &ec)
build the list of outgoing edges and lanes
void joinNodeCluster(NodeSet clusters, NBDistrictCont &dc, NBEdgeCont &ec, NBTrafficLightLogicCont &tlc, NBNode *predefined=nullptr, bool resetConnections=false)
void generateNodeClusters(double maxDist, NodeClusters &into) const
Builds node clusters.
Definition: NBNodeCont.cpp:463
void computeNodeShapes(double mismatchThreshold=-1)
Compute the junction shape for this node.
std::vector< std::set< std::string > > myJoinedClusters
sets of node ids which were joined
Definition: NBNodeCont.h:406
void pruneClusterFringe(NodeSet &cluster) const
remove geometry-like fringe nodes from cluster
Definition: NBNodeCont.cpp:797
NBEdge * shortestEdge(const NodeSet &cluster, const NodeSet &startNodes, const std::vector< NBNode * > &exclude) const
find closest neighbor for building circle
std::pair< NBNode *, double > NodeAndDist
Definition: NBNodeCont.h:62
void guessTLs(OptionsCont &oc, NBTrafficLightLogicCont &tlc)
Guesses which junctions or junction clusters shall be controlled by tls.
int guessFringe()
guess and mark fringe nodes
std::set< NBNode * > myGuessedTLS
nodes that received a traffic light due to guessing (–tls.guess)
Definition: NBNodeCont.h:415
int joinJunctions(double maxDist, NBDistrictCont &dc, NBEdgeCont &ec, NBTrafficLightLogicCont &tlc, NBPTStopCont &sc)
Joins junctions that are very close together.
Definition: NBNodeCont.cpp:658
void computeLanes2Lanes()
divides the incoming lanes on outgoing lanes
void discardTrafficLights(NBTrafficLightLogicCont &tlc, bool geometryLike, bool guessSignals)
bool feasibleCluster(const NodeSet &cluster, const NBEdgeCont &ec, const NBPTStopCont &sc, std::string &reason) const
determine wether the cluster is not too complex for joining
static NodeSet getClusterNeighbors(const NBNode *n, NodeSet &cluster)
return all cluster neighbors for the given node
Definition: NBNodeCont.cpp:948
void removeSelfLoops(NBDistrictCont &dc, NBEdgeCont &ec, NBTrafficLightLogicCont &tc)
Removes self-loop edges (edges where the source and the destination node are the same)
Definition: NBNodeCont.cpp:178
std::set< std::string > myJoined
ids found in loaded join clusters used for error checking
Definition: NBNodeCont.h:409
bool shouldBeTLSControlled(const NodeSet &c, double laneSpeedThreshold) const
Returns whethe the given node cluster should be controlled by a tls.
int joinSameJunctions(NBDistrictCont &dc, NBEdgeCont &ec, NBTrafficLightLogicCont &tlc)
Joins junctions with the same coordinates regardless of topology.
Definition: NBNodeCont.cpp:771
void analyzeCluster(NodeSet cluster, std::string &id, Position &pos, bool &hasTLS, TrafficLightType &type, SumoXMLNodeType &nodeType)
bool customTLID(const NodeSet &c) const
check wheter the set of nodes contains traffic lights with custom id
int remapIDs(bool numericaIDs, bool reservedIDs, const std::string &prefix)
remap node IDs accoring to options –numerical-ids and –reserved-ids
bool maybeSlipLaneEnd(const NBNode *n, EdgeVector &incoming, double &outAngle) const
check whether the given node maybe the end of a slip lane
void pruneSlipLaneNodes(NodeSet &cluster) const
remove nodes that form a slip lane from cluster
Definition: NBNodeCont.cpp:961
Represents a single node (junction) during network building.
Definition: NBNode.h:66
bool hasIncoming(const NBEdge *const e) const
Returns whether the given edge ends at this node.
Definition: NBNode.cpp:1651
void reinit(const Position &position, SumoXMLNodeType type, bool updateEdgeGeometries=false)
Resets initial values.
Definition: NBNode.cpp:306
SumoXMLNodeType getType() const
Returns the type of this node.
Definition: NBNode.h:271
std::vector< std::pair< NBEdge *, NBEdge * > > getEdgesToJoin() const
get edges to join
Definition: NBNode.cpp:2262
void removeTrafficLights(bool setAsPriority=false)
Removes all references to traffic lights that control this tls.
Definition: NBNode.cpp:381
const EdgeVector & getOutgoingEdges() const
Returns this node's outgoing edges (The edges which start at this node)
Definition: NBNode.h:259
const EdgeVector & getEdges() const
Returns all edges which participate in this node (Edges that start or end at this node)
Definition: NBNode.h:264
const EdgeVector & getIncomingEdges() const
Returns this node's incoming edges (The edges which yield in this node)
Definition: NBNode.h:254
void replaceIncoming(NBEdge *which, NBEdge *by, int laneOff)
Replaces occurences of the first edge within the list of incoming by the second Connections are remap...
Definition: NBNode.cpp:1545
const std::set< NBTrafficLightDefinition * > & getControllingTLS() const
Returns the traffic lights that were assigned to this node (The set of tls that control this node)
Definition: NBNode.h:322
void removeTrafficLight(NBTrafficLightDefinition *tlDef)
Removes the given traffic light from this node.
Definition: NBNode.cpp:374
void updateSurroundingGeometry()
update geometry of node and surrounding edges
Definition: NBNode.cpp:1031
const Position & getPosition() const
Definition: NBNode.h:246
bool checkIsRemovable() const
check if node is removable
Definition: NBNode.cpp:2189
bool geometryLike() const
whether this is structurally similar to a geometry node
Definition: NBNode.cpp:3192
bool isNearDistrict() const
@chech if node is near district
Definition: NBNode.cpp:2314
bool isTLControlled() const
Returns whether this node is controlled by any tls.
Definition: NBNode.h:317
static bool isRailwayNode(const NBNode *n)
whether the given node only has rail edges
A traffic light logics which must be computed (only nodes/edges are given)
Definition: NBOwnTLDef.h:44
void addEdges2Keep(const OptionsCont &oc, std::set< std::string > &into)
add edges that must be kept
std::map< std::string, NBPTStop * >::const_iterator begin() const
Returns the pointer to the begin of the stored pt stops.
Definition: NBPTStopCont.h:53
std::map< std::string, NBPTStop * >::const_iterator end() const
Returns the pointer to the end of the stored pt stops.
Definition: NBPTStopCont.h:60
void addEdges2Keep(const OptionsCont &oc, std::set< std::string > &into)
add edges that must be kept
Definition: NBParking.cpp:78
The base class for traffic light logic definitions.
A container for traffic light definitions and built programs.
void replaceRemoved(NBEdge *removed, int removedLane, NBEdge *by, int byLane, bool incoming)
Replaces occurences of the removed edge/lane in all definitions by the given edge.
bool computeSingleLogic(OptionsCont &oc, NBTrafficLightDefinition *def)
Computes a specific traffic light logic (using by NETEDIT)
const std::map< std::string, NBTrafficLightDefinition * > & getPrograms(const std::string &id) const
Returns all programs for the given tl-id.
bool removeFully(const std::string id)
Removes a logic definition (and all programs) from the dictionary.
bool insert(NBTrafficLightDefinition *logic, bool forceInsert=false)
Adds a logic definition to the dictionary.
void extract(NBTrafficLightDefinition *definition)
Extracts a traffic light definition from myDefinitions but keeps it in myExtracted for eventual * del...
Allows to store the object; used as context while traveling the rtree in TraCI.
Definition: Named.h:89
Base class for objects which have an id.
Definition: Named.h:53
virtual void setID(const std::string &newID)
resets the id
Definition: Named.h:81
const std::string & getID() const
Returns the id.
Definition: Named.h:73
void Remove(const float a_min[2], const float a_max[2], Named *const &a_data)
Remove entry.
Definition: NamedRTree.h:89
void Insert(const float a_min[2], const float a_max[2], Named *const &a_data)
Insert entry.
Definition: NamedRTree.h:78
int Search(const float a_min[2], const float a_max[2], const Named::StoringVisitor &c) const
Find all within search rectangle.
Definition: NamedRTree.h:111
A storage for options typed value containers)
Definition: OptionsCont.h:89
bool isSet(const std::string &name, bool failOnNonExistant=true) const
Returns the information whether the named option is set.
double getFloat(const std::string &name) const
Returns the double-value of the named option (only for Option_Float)
std::string getString(const std::string &name) const
Returns the string-value of the named option (only for Option_String)
bool isDefault(const std::string &name) const
Returns the information whether the named option has still the default value.
bool exists(const std::string &name) const
Returns the information whether the named option is known.
bool getBool(const std::string &name) const
Returns the boolean-value of the named option (only for Option_Bool)
const StringVector & getStringVector(const std::string &name) const
Returns the list of string-value of the named option (only for Option_StringVector)
static OptionsCont & getOptions()
Retrieves the options.
Definition: OptionsCont.cpp:58
virtual void setParameter(const std::string &key, const std::string &value)
Sets a parameter.
A point in 2D or 3D with translation and scaling methods.
Definition: Position.h:36
void setx(double x)
set position x
Definition: Position.h:69
static const Position INVALID
used to indicate that a position is valid
Definition: Position.h:282
double distanceTo2D(const Position &p2) const
returns the euclidean distance in the x-y-plane
Definition: Position.h:241
double x() const
Returns the x-position.
Definition: Position.h:54
void add(const Position &pos)
Adds the given position to this one.
Definition: Position.h:124
void setz(double z)
set position z
Definition: Position.h:79
void mul(double val)
Multiplies both positions with the given value.
Definition: Position.h:104
double z() const
Returns the z-position.
Definition: Position.h:64
void sety(double y)
set position y
Definition: Position.h:74
double y() const
Returns the y-position.
Definition: Position.h:59
static StringBijection< TrafficLightType > TrafficLightTypes
traffic light types
T get(const std::string &str) const
std::vector< std::string > getVector()
return vector of strings
static long long int toLong(const std::string &sData)
converts a string into the long value described by it by calling the char-type converter,...
static bool startsWith(const std::string &str, const std::string prefix)
Checks whether a given string starts with the prefix.
static double fn[10]
Definition: odrSpiral.cpp:82