SUMO - Simulation of Urban MObility
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
NBAlgorithms.cpp
Go to the documentation of this file.
1 /****************************************************************************/
8 // Algorithms for network computation
9 /****************************************************************************/
10 // SUMO, Simulation of Urban MObility; see http://sumo.dlr.de/
11 // Copyright (C) 2012-2015 DLR (http://www.dlr.de/) and contributors
12 /****************************************************************************/
13 //
14 // This file is part of SUMO.
15 // SUMO is free software: you can redistribute it and/or modify
16 // it under the terms of the GNU General Public License as published by
17 // the Free Software Foundation, either version 3 of the License, or
18 // (at your option) any later version.
19 //
20 /****************************************************************************/
21 
22 
23 // ===========================================================================
24 // included modules
25 // ===========================================================================
26 #ifdef _MSC_VER
27 #include <windows_config.h>
28 #else
29 #include <config.h>
30 #endif
31 
32 #include <sstream>
33 #include <iostream>
34 #include <cassert>
35 #include <algorithm>
37 #include <utils/common/ToString.h>
38 #include "NBEdge.h"
39 #include "NBNodeCont.h"
40 #include "NBTypeCont.h"
41 #include "NBNode.h"
42 #include "NBAlgorithms.h"
43 
44 #ifdef CHECK_MEMORY_LEAKS
45 #include <foreign/nvwa/debug_new.h>
46 #endif // CHECK_MEMORY_LEAKS
47 
48 
49 // ===========================================================================
50 // method definitions
51 // ===========================================================================
52 // ---------------------------------------------------------------------------
53 // NBTurningDirectionsComputer
54 // ---------------------------------------------------------------------------
55 void
57  for (std::map<std::string, NBNode*>::const_iterator i = nc.begin(); i != nc.end(); ++i) {
59  }
60 }
61 
62 void
64  const std::vector<NBEdge*>& incoming = node->getIncomingEdges();
65  const std::vector<NBEdge*>& outgoing = node->getOutgoingEdges();
66  std::vector<Combination> combinations;
67  for (std::vector<NBEdge*>::const_iterator j = outgoing.begin(); j != outgoing.end(); ++j) {
68  NBEdge* outedge = *j;
69  for (std::vector<NBEdge*>::const_iterator k = incoming.begin(); k != incoming.end(); ++k) {
70  NBEdge* e = *k;
71  // @todo: check whether NBHelpers::relAngle is properly defined and whether it should really be used, here
72  const SUMOReal signedAngle = NBHelpers::normRelAngle(e->getAngleAtNode(node), outedge->getAngleAtNode(node));
73  if (signedAngle > 0 && signedAngle < 177 && e->getGeometry().back().distanceTo2D(outedge->getGeometry().front()) < POSITION_EPS) {
74  // backwards curving edges can only be turnaround when there are
75  // non-default endpoints
76  continue;
77  }
78  SUMOReal angle = fabs(signedAngle);
79  // std::cout << "incoming=" << e->getID() << " outgoing=" << outedge->getID() << " relAngle=" << NBHelpers::relAngle(e->getAngleAtNode(node), outedge->getAngleAtNode(node)) << "\n";
80  if (e->getFromNode() == outedge->getToNode() && angle > 120) {
81  // they connect the same nodes; should be the turnaround direction
82  // we'll assign a maximum number
83  //
84  // @todo: indeed, we have observed some pathological intersections
85  // see "294831560" in OSM/adlershof. Here, several edges are connecting
86  // same nodes. We have to do the angle check before...
87  //
88  // @todo: and well, there are some other as well, see plain import
89  // of delphi_muenchen (elmar), intersection "59534191". Not that it would
90  // be realistic in any means; we will warn, here.
91  angle += 360;
92  }
93  if (angle < 160) {
94  continue;
95  }
96  Combination c;
97  c.from = e;
98  c.to = outedge;
99  c.angle = angle;
100  combinations.push_back(c);
101  }
102  }
103  // sort combinations so that the ones with the highest angle are at the begin
104  std::sort(combinations.begin(), combinations.end(), combination_by_angle_sorter());
105  std::set<NBEdge*> seen;
106  bool haveWarned = false;
107  for (std::vector<Combination>::const_iterator j = combinations.begin(); j != combinations.end(); ++j) {
108  if (seen.find((*j).from) != seen.end() || seen.find((*j).to) != seen.end()) {
109  // do not regard already set edges
110  if ((*j).angle > 360 && !haveWarned) {
111  WRITE_WARNING("Ambiguity in turnarounds computation at node '" + node->getID() + "'.");
112  haveWarned = true;
113  }
114  continue;
115  }
116  // mark as seen
117  seen.insert((*j).from);
118  seen.insert((*j).to);
119  // set turnaround information
120  bool onlyPossible = (*j).from->getConnections().size() != 0 && !(*j).from->isConnectedTo((*j).to);
121  //std::cout << " setTurningDestination from=" << (*j).from->getID() << " to=" << (*j).to->getID() << " onlyPossible=" << onlyPossible << "\n";
122  (*j).from->setTurningDestination((*j).to, onlyPossible);
123  }
124 }
125 
126 
127 // ---------------------------------------------------------------------------
128 // NBNodesEdgesSorter
129 // ---------------------------------------------------------------------------
130 void
131 NBNodesEdgesSorter::sortNodesEdges(NBNodeCont& nc, bool leftHand, bool useNodeShape) {
132  for (std::map<std::string, NBNode*>::const_iterator i = nc.begin(); i != nc.end(); ++i) {
133  NBNode* n = (*i).second;
134  if (n->myAllEdges.size() == 0) {
135  continue;
136  }
137  EdgeVector& allEdges = (*i).second->myAllEdges;
138  EdgeVector& incoming = (*i).second->myIncomingEdges;
139  EdgeVector& outgoing = (*i).second->myOutgoingEdges;
140  std::vector<NBNode::Crossing>& crossings = (*i).second->myCrossings;
141 
142  if (!useNodeShape || n->getShape().area() < 1) {
143  // if the area is to small (i.e. for simple-continuation nodes) we better not use it
144  // sort by the angle of the adjoining line segment of the edge geometry
145  // sort the edges
146  std::sort(allEdges.begin(), allEdges.end(), edge_by_junction_angle_sorter(n));
147  std::sort(incoming.begin(), incoming.end(), edge_by_junction_angle_sorter(n));
148  std::sort(outgoing.begin(), outgoing.end(), edge_by_junction_angle_sorter(n));
149  std::vector<NBEdge*>::iterator j;
150  for (j = allEdges.begin(); j != allEdges.end() - 1 && j != allEdges.end(); ++j) {
151  swapWhenReversed(n, leftHand, j, j + 1);
152  }
153  if (allEdges.size() > 1 && j != allEdges.end()) {
154  swapWhenReversed(n, leftHand, allEdges.end() - 1, allEdges.begin());
155  }
156  } else {
157  NBEdge* firstOfAll = allEdges.front();
158  NBEdge* firstOfIncoming = incoming.size() > 0 ? incoming.front() : 0;
159  NBEdge* firstOfOutgoing = outgoing.size() > 0 ? outgoing.front() : 0;
160  // sort by the angle between the node shape center and the point where the edge meeds the node shape
161  sort(allEdges.begin(), allEdges.end(), NBContHelper::edge_by_angle_to_nodeShapeCentroid_sorter(n));
162  sort(incoming.begin(), incoming.end(), NBContHelper::edge_by_angle_to_nodeShapeCentroid_sorter(n));
163  sort(outgoing.begin(), outgoing.end(), NBContHelper::edge_by_angle_to_nodeShapeCentroid_sorter(n));
164  // let the first edge remain the first
165  rotate(allEdges.begin(), std::find(allEdges.begin(), allEdges.end(), firstOfAll), allEdges.end());
166  if (firstOfIncoming != 0) {
167  rotate(incoming.begin(), std::find(incoming.begin(), incoming.end(), firstOfIncoming), incoming.end());
168  }
169  if (firstOfOutgoing != 0) {
170  rotate(outgoing.begin(), std::find(outgoing.begin(), outgoing.end(), firstOfOutgoing), outgoing.end());
171  }
172  }
173 
174  // sort the crossings
175  std::sort(crossings.begin(), crossings.end(), crossing_by_junction_angle_sorter(n, allEdges));
176  // DEBUG
177  //if (n->getID() == "cluster_492462300_671564296") {
178  // if (crossings.size() > 0) {
179  // std::cout << " crossings at " << n->getID() << "\n";
180  // for (std::vector<NBNode::Crossing>::iterator it = crossings.begin(); it != crossings.end(); ++it) {
181  // std::cout << " " << toString((*it).edges) << "\n";
182  // }
183  // }
184  //}
185  }
186 }
187 
188 
189 void
190 NBNodesEdgesSorter::swapWhenReversed(const NBNode* const n, bool leftHand,
191  const std::vector<NBEdge*>::iterator& i1,
192  const std::vector<NBEdge*>::iterator& i2) {
193  NBEdge* e1 = *i1;
194  NBEdge* e2 = *i2;
195  if (leftHand) {
196  // @todo: check this; shouldn't it be "swap(*e1, *e2)"?
197  std::swap(e1, e2);
198  }
199  // @todo: The difference between "isTurningDirectionAt" and "isTurnaround"
200  // is not nice. Maybe we could get rid of it if we would always mark edges
201  // as turnarounds, even if they do not have to be added, as mentioned in
202  // notes on NBTurningDirectionsComputer::computeTurnDirectionsForNode
203  if (e2->getToNode() == n && e2->isTurningDirectionAt(e1)) {
204  std::swap(*i1, *i2);
205  }
206 }
207 
208 
209 // ---------------------------------------------------------------------------
210 // NBNodeTypeComputer
211 // ---------------------------------------------------------------------------
212 void
214  for (std::map<std::string, NBNode*>::const_iterator i = nc.begin(); i != nc.end(); ++i) {
215  NBNode* n = (*i).second;
216  // the type may already be set from the data
217  if (n->myType != NODETYPE_UNKNOWN) {
218  continue;
219  }
220  // check whether the junction is not a real junction
221  if (n->myIncomingEdges.size() == 1) {
223  continue;
224  }
225  // @todo "isSimpleContinuation" should be revalidated
226  if (n->isSimpleContinuation()) {
228  continue;
229  }
230  // determine the type
232  for (EdgeVector::const_iterator i = n->myIncomingEdges.begin(); i != n->myIncomingEdges.end(); i++) {
233  for (EdgeVector::const_iterator j = i + 1; j != n->myIncomingEdges.end(); j++) {
234  // @todo "getOppositeIncoming" should probably be refactored into something the edge knows
235  if (n->getOppositeIncoming(*j) == *i && n->myIncomingEdges.size() > 2) {
236  continue;
237  }
238  // @todo check against a legal document
239  // @todo figure out when NODETYPE_PRIORITY_STOP is appropriate
240  const SUMOReal s1 = (*i)->getSpeed() * (SUMOReal) 3.6;
241  const SUMOReal s2 = (*j)->getSpeed() * (SUMOReal) 3.6;
242  const int p1 = (*i)->getPriority();
243  const int p2 = (*j)->getPriority();
244  if (fabs(s1 - s2) > (SUMOReal) 9.5 || MAX2(s1, s2) >= (SUMOReal) 49. || p1 != p2) {
245  type = NODETYPE_PRIORITY;
246  break;
247  }
248  }
249  }
250  // save type
251  n->myType = type;
252  }
253 }
254 
255 
256 // ---------------------------------------------------------------------------
257 // NBEdgePriorityComputer
258 // ---------------------------------------------------------------------------
259 void
261  for (std::map<std::string, NBNode*>::const_iterator i = nc.begin(); i != nc.end(); ++i) {
262  NBNode* n = (*i).second;
263  // preset all junction's edge priorities to zero
264  for (EdgeVector::iterator j = n->myAllEdges.begin(); j != n->myAllEdges.end(); ++j) {
265  (*j)->setJunctionPriority(n, 0);
266  }
267  // check if the junction is not a real junction
268  if (n->myIncomingEdges.size() == 1 && n->myOutgoingEdges.size() == 1) {
269  continue;
270  }
271  // compute the priorities on junction when needed
274  }
275  }
276 }
277 
278 
279 void
281  if (n.myIncomingEdges.size() == 0 || n.myOutgoingEdges.size() == 0) {
282  return;
283  }
284  EdgeVector incoming = n.myIncomingEdges;
285  EdgeVector outgoing = n.myOutgoingEdges;
286  // what we do want to have is to extract the pair of roads that are
287  // the major roads for this junction
288  // let's get the list of incoming edges with the highest priority
289  std::sort(incoming.begin(), incoming.end(), NBContHelper::edge_by_priority_sorter());
290  EdgeVector bestIncoming;
291  NBEdge* best = incoming[0];
292  while (incoming.size() > 0 && samePriority(best, incoming[0])) {
293  bestIncoming.push_back(*incoming.begin());
294  incoming.erase(incoming.begin());
295  }
296  // now, let's get the list of best outgoing
297  assert(outgoing.size() != 0);
298  sort(outgoing.begin(), outgoing.end(), NBContHelper::edge_by_priority_sorter());
299  EdgeVector bestOutgoing;
300  best = outgoing[0];
301  while (outgoing.size() > 0 && samePriority(best, outgoing[0])) { //->getPriority()==best->getPriority()) {
302  bestOutgoing.push_back(*outgoing.begin());
303  outgoing.erase(outgoing.begin());
304  }
305  // special case: user input makes mainDirection unambiguous
306  const bool mainDirectionExplicit = (
307  bestIncoming.size() == 1 && n.myIncomingEdges.size() <= 2
308  && (incoming.size() == 0 || bestIncoming[0]->getPriority() > incoming[0]->getPriority())
309  && bestOutgoing.size() == 1 && n.myOutgoingEdges.size() <= 2
310  && (outgoing.size() == 0 || bestOutgoing[0]->getPriority() > outgoing[0]->getPriority())
311  && !bestIncoming[0]->isTurningDirectionAt(bestOutgoing[0]));
312  // now, let's compute for each of the best incoming edges
313  // the incoming which is most opposite
314  // the outgoing which is most opposite
315  EdgeVector::iterator i;
316  std::map<NBEdge*, NBEdge*> counterIncomingEdges;
317  std::map<NBEdge*, NBEdge*> counterOutgoingEdges;
318  incoming = n.myIncomingEdges;
319  outgoing = n.myOutgoingEdges;
320  for (i = bestIncoming.begin(); i != bestIncoming.end(); ++i) {
321  std::sort(incoming.begin(), incoming.end(), NBContHelper::edge_opposite_direction_sorter(*i, &n));
322  counterIncomingEdges[*i] = *incoming.begin();
323  std::sort(outgoing.begin(), outgoing.end(), NBContHelper::edge_opposite_direction_sorter(*i, &n));
324  counterOutgoingEdges[*i] = *outgoing.begin();
325  }
326  // ok, let's try
327  // 1) there is one best incoming road
328  if (bestIncoming.size() == 1) {
329  // let's mark this road as the best
330  NBEdge* best1 = extractAndMarkFirst(n, bestIncoming);
331  if (!mainDirectionExplicit && counterIncomingEdges.find(best1) != counterIncomingEdges.end()) {
332  // ok, look, what we want is the opposit of the straight continuation edge
333  // but, what if such an edge does not exist? By now, we'll determine it
334  // geometrically
335  NBEdge* s = counterIncomingEdges.find(best1)->second;
336  if (GeomHelper::getMinAngleDiff(best1->getAngleAtNode(&n), s->getAngleAtNode(&n)) > 180 - 45) {
337  s->setJunctionPriority(&n, 1);
338  }
339  }
340  assert(bestOutgoing.size() != 0);
341  // mark the best outgoing as the continuation
342  sort(bestOutgoing.begin(), bestOutgoing.end(), NBContHelper::edge_similar_direction_sorter(best1));
343  // assign extra priority if the priorities are unambiguous (regardless of geometry)
344  best1 = extractAndMarkFirst(n, bestOutgoing);
345  if (!mainDirectionExplicit && counterOutgoingEdges.find(best1) != counterOutgoingEdges.end()) {
346  NBEdge* s = counterOutgoingEdges.find(best1)->second;
347  if (GeomHelper::getMinAngleDiff(best1->getAngleAtNode(&n), s->getAngleAtNode(&n)) > 180 - 45) {
348  s->setJunctionPriority(&n, 1);
349  }
350  }
351  return;
352  }
353 
354  // ok, what we want to do in this case is to determine which incoming
355  // has the best continuation...
356  // This means, when several incoming roads have the same priority,
357  // we want a (any) straight connection to be more priorised than a turning
358  SUMOReal bestAngle = 0;
359  NBEdge* bestFirst = 0;
360  NBEdge* bestSecond = 0;
361  bool hadBest = false;
362  for (i = bestIncoming.begin(); i != bestIncoming.end(); ++i) {
363  EdgeVector::iterator j;
364  NBEdge* t1 = *i;
365  SUMOReal angle1 = t1->getAngleAtNode(&n) + 180;
366  if (angle1 >= 360) {
367  angle1 -= 360;
368  }
369  for (j = i + 1; j != bestIncoming.end(); ++j) {
370  NBEdge* t2 = *j;
371  SUMOReal angle2 = t2->getAngleAtNode(&n) + 180;
372  if (angle2 >= 360) {
373  angle2 -= 360;
374  }
375  SUMOReal angle = GeomHelper::getMinAngleDiff(angle1, angle2);
376  if (!hadBest || angle > bestAngle) {
377  bestAngle = angle;
378  bestFirst = *i;
379  bestSecond = *j;
380  hadBest = true;
381  }
382  }
383  }
384  bestFirst->setJunctionPriority(&n, 1);
385  sort(bestOutgoing.begin(), bestOutgoing.end(), NBContHelper::edge_similar_direction_sorter(bestFirst));
386  if (bestOutgoing.size() != 0) {
387  extractAndMarkFirst(n, bestOutgoing);
388  }
389  bestSecond->setJunctionPriority(&n, 1);
390  sort(bestOutgoing.begin(), bestOutgoing.end(), NBContHelper::edge_similar_direction_sorter(bestSecond));
391  if (bestOutgoing.size() != 0) {
392  extractAndMarkFirst(n, bestOutgoing);
393  }
394 }
395 
396 
397 NBEdge*
398 NBEdgePriorityComputer::extractAndMarkFirst(NBNode& n, std::vector<NBEdge*>& s, int prio) {
399  if (s.size() == 0) {
400  return 0;
401  }
402  NBEdge* ret = s.front();
403  s.erase(s.begin());
404  ret->setJunctionPriority(&n, prio);
405  return ret;
406 }
407 
408 
409 bool
410 NBEdgePriorityComputer::samePriority(const NBEdge* const e1, const NBEdge* const e2) {
411  if (e1 == e2) {
412  return true;
413  }
414  if (e1->getPriority() != e2->getPriority()) {
415  return false;
416  }
417  if ((int) e1->getSpeed() != (int) e2->getSpeed()) {
418  return false;
419  }
420  return (int) e1->getNumLanes() == (int) e2->getNumLanes();
421 }
422 
423 
425  // reorder based on getAngleAtNodeToCenter
426  myOrdering = ordering;
428  // let the first edge remain the first
429  rotate(myOrdering.begin(), std::find(myOrdering.begin(), myOrdering.end(), ordering.front()), myOrdering.end());
430 }
431 
432 
433 /****************************************************************************/
434 
const EdgeVector & getIncomingEdges() const
Returns this node's incoming edges.
Definition: NBNode.h:251
Sorts incoming and outgoing edges clockwise around the given node.
Definition: NBAlgorithms.h:161
Sorts crossings by minimum clockwise clockwise edge angle. Use the ordering found in myAllEdges of th...
Definition: NBAlgorithms.h:119
NBEdge * getOppositeIncoming(NBEdge *e) const
Definition: NBNode.cpp:1036
SumoXMLNodeType myType
The type of the junction.
Definition: NBNode.h:733
static SUMOReal normRelAngle(SUMOReal angle1, SUMOReal angle2)
ensure that reverse relAngles (>=179.999) always count as turnarounds (-180)
Definition: NBHelpers.cpp:76
The representation of a single edge during network building.
Definition: NBEdge.h:71
Class to sort edges by their angle in relation to the given edge.
Definition: NBContHelper.h:148
static void swapWhenReversed(const NBNode *const n, bool leftHand, const std::vector< NBEdge * >::iterator &i1, const std::vector< NBEdge * >::iterator &i2)
Assures correct order for same-angle opposite-direction edges.
static void computeTurnDirectionsForNode(NBNode *node)
Computes turnaround destinations for all incoming edges of the given nodes (if any) ...
T MAX2(T a, T b)
Definition: StdDefs.h:74
Stores the information about the angle between an incoming ("from") and an outgoing ("to") edge...
Definition: NBAlgorithms.h:73
#define WRITE_WARNING(msg)
Definition: MsgHandler.h:200
const EdgeVector & getOutgoingEdges() const
Returns this node's outgoing edges.
Definition: NBNode.h:259
const std::string & getID() const
Returns the id.
Definition: Named.h:60
EdgeVector myAllEdges
Vector of incoming and outgoing edges.
Definition: NBNode.h:724
int getPriority() const
Returns the priority of the edge.
Definition: NBEdge.h:355
bool isSimpleContinuation() const
Definition: NBNode.cpp:426
static void computeEdgePriorities(NBNodeCont &nc)
Computes edge priorities within a node.
unsigned int getNumLanes() const
Returns the number of lanes.
Definition: NBEdge.h:347
static NBEdge * extractAndMarkFirst(NBNode &n, std::vector< NBEdge * > &s, int prio=1)
Sets the priorites in case of a priority junction.
bool isTurningDirectionAt(const NBEdge *const edge) const
Returns whether the given edge is the opposite direction to this edge.
Definition: NBEdge.cpp:1756
static void computeTurnDirections(NBNodeCont &nc)
Computes turnaround destinations for all edges (if exist)
#define POSITION_EPS
Definition: config.h:189
std::map< std::string, NBNode * >::const_iterator end() const
Returns the pointer to the end of the stored nodes.
Definition: NBNodeCont.h:135
crossing_by_junction_angle_sorter(const NBNode *node, const EdgeVector &ordering)
const PositionVector & getShape() const
retrieve the junction shape
Definition: NBNode.cpp:1461
EdgeVector myIncomingEdges
Vector of incoming edges.
Definition: NBNode.h:718
static bool samePriority(const NBEdge *const e1, const NBEdge *const e2)
Returns whether both edges have the same priority.
EdgeVector myOutgoingEdges
Vector of outgoing edges.
Definition: NBNode.h:721
NBNode * getToNode() const
Returns the destination node of the edge.
Definition: NBEdge.h:371
static void computeNodeTypes(NBNodeCont &nc)
Computes node types.
SumoXMLNodeType
Numbers representing special SUMO-XML-attribute values for representing node- (junction-) types used ...
std::vector< NBEdge * > EdgeVector
Definition: NBCont.h:41
const PositionVector & getGeometry() const
Returns the geometry of the edge.
Definition: NBEdge.h:531
static SUMOReal getMinAngleDiff(SUMOReal angle1, SUMOReal angle2)
Returns the minimum distance (clockwise/counter-clockwise) between both angles.
Definition: GeomHelper.cpp:405
void setJunctionPriority(const NBNode *const node, int prio)
Sets the junction priority of the edge.
Definition: NBEdge.cpp:1235
Represents a single node (junction) during network building.
Definition: NBNode.h:75
#define SUMOReal
Definition: config.h:218
Sorts "Combination"s by decreasing angle.
Definition: NBAlgorithms.h:83
static void setPriorityJunctionPriorities(NBNode &n)
Sets the priorites in case of a priority junction.
SUMOReal getSpeed() const
Returns the speed allowed on this edge.
Definition: NBEdge.h:431
Container for nodes during the netbuilding process.
Definition: NBNodeCont.h:64
SUMOReal area() const
Returns the area (0 for non-closed)
std::map< std::string, NBNode * >::const_iterator begin() const
Returns the pointer to the begin of the stored nodes.
Definition: NBNodeCont.h:127
SUMOReal getAngleAtNode(const NBNode *const node) const
Returns the angle of the edge's geometry at the given node.
Definition: NBEdge.cpp:1245
NBNode * getFromNode() const
Returns the origin node of the edge.
Definition: NBEdge.h:363
static void sortNodesEdges(NBNodeCont &nc, bool leftHand, bool useNodeShape=false)
Sorts a node's edges clockwise regarding driving direction.