SUMO - Simulation of Urban MObility
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
NBAlgorithms.cpp
Go to the documentation of this file.
1 /****************************************************************************/
7 // Algorithms for network computation
8 /****************************************************************************/
9 // SUMO, Simulation of Urban MObility; see http://sumo-sim.org/
10 // Copyright (C) 2001-2013 DLR (http://www.dlr.de/) and contributors
11 /****************************************************************************/
12 //
13 // This file is part of SUMO.
14 // SUMO is free software: you can redistribute it and/or modify
15 // it under the terms of the GNU General Public License as published by
16 // the Free Software Foundation, either version 3 of the License, or
17 // (at your option) any later version.
18 //
19 /****************************************************************************/
20 
21 
22 // ===========================================================================
23 // included modules
24 // ===========================================================================
25 #ifdef _MSC_VER
26 #include <windows_config.h>
27 #else
28 #include <config.h>
29 #endif
30 
31 #include <sstream>
32 #include <iostream>
33 #include <cassert>
34 #include <algorithm>
36 #include "NBEdge.h"
37 #include "NBNodeCont.h"
38 #include "NBTypeCont.h"
39 #include "NBNode.h"
40 #include "NBAlgorithms.h"
41 
42 #ifdef CHECK_MEMORY_LEAKS
43 #include <foreign/nvwa/debug_new.h>
44 #endif // CHECK_MEMORY_LEAKS
45 
46 
47 // ===========================================================================
48 // method definitions
49 // ===========================================================================
50 // ---------------------------------------------------------------------------
51 // NBTurningDirectionsComputer
52 // ---------------------------------------------------------------------------
53 void
55  for (std::map<std::string, NBNode*>::const_iterator i = nc.begin(); i != nc.end(); ++i) {
57  }
58 }
59 
60 void
62  const std::vector<NBEdge*>& incoming = node->getIncomingEdges();
63  const std::vector<NBEdge*>& outgoing = node->getOutgoingEdges();
64  std::vector<Combination> combinations;
65  for (std::vector<NBEdge*>::const_iterator j = outgoing.begin(); j != outgoing.end(); ++j) {
66  NBEdge* outedge = *j;
67  for (std::vector<NBEdge*>::const_iterator k = incoming.begin(); k != incoming.end(); ++k) {
68  NBEdge* e = *k;
69  if (e->getConnections().size() != 0 && !e->isConnectedTo(outedge)) {
70  // has connections, but not to outedge; outedge will not be the turn direction
71  //
72  // @todo: this seems to be needed due to legacy issues; actually, we could regard
73  // such pairs, too, and it probably would increase the accuracy. But there is
74  // no mechanism implemented, yet, which would avoid adding them as turnarounds though
75  // no connection is specified.
76  continue;
77  }
78 
79  // @todo: check whether NBHelpers::relAngle is properly defined and whether it should really be used, here
80  SUMOReal angle = fabs(NBHelpers::relAngle(e->getAngleAtNode(node), outedge->getAngleAtNode(node)));
81  if (angle < 160) {
82  continue;
83  }
84  if (e->getFromNode() == outedge->getToNode()) {
85  // they connect the same nodes; should be the turnaround direction
86  // we'll assign a maximum number
87  //
88  // @todo: indeed, we have observed some pathological intersections
89  // see "294831560" in OSM/adlershof. Here, several edges are connecting
90  // same nodes. We have to do the angle check before...
91  //
92  // @todo: and well, there are some other as well, see plain import
93  // of delphi_muenchen (elmar), intersection "59534191". Not that it would
94  // be realistic in any means; we will warn, here.
95  angle += 360;
96  }
97  Combination c;
98  c.from = e;
99  c.to = outedge;
100  c.angle = angle;
101  combinations.push_back(c);
102  }
103  }
104  // sort combinations so that the ones with the highest angle are at the begin
105  std::sort(combinations.begin(), combinations.end(), combination_by_angle_sorter());
106  std::set<NBEdge*> seen;
107  bool haveWarned = false;
108  for (std::vector<Combination>::const_iterator j = combinations.begin(); j != combinations.end(); ++j) {
109  if (seen.find((*j).from) != seen.end() || seen.find((*j).to) != seen.end()) {
110  // do not regard already set edges
111  if ((*j).angle > 360 && !haveWarned) {
112  WRITE_WARNING("Ambiguity in turnarounds computation at node '" + node->getID() + "'.");
113  haveWarned = true;
114  }
115  continue;
116  }
117  // mark as seen
118  seen.insert((*j).from);
119  seen.insert((*j).to);
120  // set turnaround information
121  (*j).from->setTurningDestination((*j).to);
122  }
123 }
124 
125 
126 // ---------------------------------------------------------------------------
127 // NBNodesEdgesSorter
128 // ---------------------------------------------------------------------------
129 void
131  for (std::map<std::string, NBNode*>::const_iterator i = nc.begin(); i != nc.end(); ++i) {
132  NBNode* n = (*i).second;
133  if (n->myAllEdges.size() == 0) {
134  continue;
135  }
136  std::vector<NBEdge*>& allEdges = (*i).second->myAllEdges;
137  std::vector<NBEdge*>& incoming = (*i).second->myIncomingEdges;
138  std::vector<NBEdge*>& outgoing = (*i).second->myOutgoingEdges;
139  // sort the edges
140  std::sort(allEdges.begin(), allEdges.end(), edge_by_junction_angle_sorter(n));
141  std::sort(incoming.begin(), incoming.end(), edge_by_junction_angle_sorter(n));
142  std::sort(outgoing.begin(), outgoing.end(), edge_by_junction_angle_sorter(n));
143  std::vector<NBEdge*>::iterator j;
144  for (j = allEdges.begin(); j != allEdges.end() - 1 && j != allEdges.end(); ++j) {
145  swapWhenReversed(n, leftHand, j, j + 1);
146  }
147  if (allEdges.size() > 1 && j != allEdges.end()) {
148  swapWhenReversed(n, leftHand, allEdges.end() - 1, allEdges.begin());
149  }
150  }
151 }
152 
153 
154 void
155 NBNodesEdgesSorter::swapWhenReversed(const NBNode* const n, bool leftHand,
156  const std::vector<NBEdge*>::iterator& i1,
157  const std::vector<NBEdge*>::iterator& i2) {
158  NBEdge* e1 = *i1;
159  NBEdge* e2 = *i2;
160  if (leftHand) {
161  // @todo: check this; shouldn't it be "swap(*e1, *e2)"?
162  std::swap(e1, e2);
163  }
164  // @todo: The difference between "isTurningDirectionAt" and "isTurnaround"
165  // is not nice. Maybe we could get rid of it if we would always mark edges
166  // as turnarounds, even if they do not have to be added, as mentioned in
167  // notes on NBTurningDirectionsComputer::computeTurnDirectionsForNode
168  if (e2->getToNode() == n && e2->isTurningDirectionAt(n, e1)) {
169  std::swap(*i1, *i2);
170  }
171 }
172 
173 
174 // ---------------------------------------------------------------------------
175 // NBNodeTypeComputer
176 // ---------------------------------------------------------------------------
177 void
179  for (std::map<std::string, NBNode*>::const_iterator i = nc.begin(); i != nc.end(); ++i) {
180  NBNode* n = (*i).second;
181  // the type may already be set from the data
182  if (n->myType != NODETYPE_UNKNOWN) {
183  continue;
184  }
185  // check whether the junction is not a real junction
186  if (n->myIncomingEdges.size() == 1) {
188  continue;
189  }
190  // @todo "isSimpleContinuation" should be revalidated
191  if (n->isSimpleContinuation()) {
193  continue;
194  }
195  // determine the type
197  for (EdgeVector::const_iterator i = n->myIncomingEdges.begin(); i != n->myIncomingEdges.end(); i++) {
198  for (EdgeVector::const_iterator j = i + 1; j != n->myIncomingEdges.end(); j++) {
199  // @todo "getOppositeIncoming" should probably be refactored into something the edge knows
200  if (n->getOppositeIncoming(*j) == *i && n->myIncomingEdges.size() > 2) {
201  continue;
202  }
203  // @todo check against a legal document
204  // @todo figure out when NODETYPE_PRIORITY_STOP is appropriate
205  const SUMOReal s1 = (*i)->getSpeed() * (SUMOReal) 3.6;
206  const SUMOReal s2 = (*j)->getSpeed() * (SUMOReal) 3.6;
207  const int p1 = (*i)->getPriority();
208  const int p2 = (*j)->getPriority();
209  if (fabs(s1 - s2) > (SUMOReal) 9.5 || MAX2(s1, s2) >= (SUMOReal) 49. || p1 != p2) {
210  type = NODETYPE_PRIORITY;
211  break;
212  }
213  }
214  }
215  // save type
216  n->myType = type;
217  }
218 }
219 
220 
221 // ---------------------------------------------------------------------------
222 // NBEdgePriorityComputer
223 // ---------------------------------------------------------------------------
224 void
226  for (std::map<std::string, NBNode*>::const_iterator i = nc.begin(); i != nc.end(); ++i) {
227  NBNode* n = (*i).second;
228  // preset all junction's edge priorities to zero
229  for (EdgeVector::iterator j = n->myAllEdges.begin(); j != n->myAllEdges.end(); ++j) {
230  (*j)->setJunctionPriority(n, 0);
231  }
232  // check if the junction is not a real junction
233  if (n->myIncomingEdges.size() == 1 && n->myOutgoingEdges.size() == 1) {
234  continue;
235  }
236  // compute the priorities on junction when needed
239  }
240  }
241 }
242 
243 
244 void
246  if (n.myIncomingEdges.size() == 0 || n.myOutgoingEdges.size() == 0) {
247  return;
248  }
249  EdgeVector incoming = n.myIncomingEdges;
250  EdgeVector outgoing = n.myOutgoingEdges;
251  // what we do want to have is to extract the pair of roads that are
252  // the major roads for this junction
253  // let's get the list of incoming edges with the highest priority
254  std::sort(incoming.begin(), incoming.end(), NBContHelper::edge_by_priority_sorter());
255  EdgeVector bestIncoming;
256  NBEdge* best = incoming[0];
257  while (incoming.size() > 0 && samePriority(best, incoming[0])) {
258  bestIncoming.push_back(*incoming.begin());
259  incoming.erase(incoming.begin());
260  }
261  // now, let's get the list of best outgoing
262  assert(outgoing.size() != 0);
263  sort(outgoing.begin(), outgoing.end(), NBContHelper::edge_by_priority_sorter());
264  EdgeVector bestOutgoing;
265  best = outgoing[0];
266  while (outgoing.size() > 0 && samePriority(best, outgoing[0])) { //->getPriority()==best->getPriority()) {
267  bestOutgoing.push_back(*outgoing.begin());
268  outgoing.erase(outgoing.begin());
269  }
270  // now, let's compute for each of the best incoming edges
271  // the incoming which is most opposite
272  // the outgoing which is most opposite
273  EdgeVector::iterator i;
274  std::map<NBEdge*, NBEdge*> counterIncomingEdges;
275  std::map<NBEdge*, NBEdge*> counterOutgoingEdges;
276  incoming = n.myIncomingEdges;
277  outgoing = n.myOutgoingEdges;
278  for (i = bestIncoming.begin(); i != bestIncoming.end(); ++i) {
279  std::sort(incoming.begin(), incoming.end(), NBContHelper::edge_opposite_direction_sorter(*i, &n));
280  counterIncomingEdges[*i] = *incoming.begin();
281  std::sort(outgoing.begin(), outgoing.end(), NBContHelper::edge_opposite_direction_sorter(*i, &n));
282  counterOutgoingEdges[*i] = *outgoing.begin();
283  }
284  // ok, let's try
285  // 1) there is one best incoming road
286  if (bestIncoming.size() == 1) {
287  // let's mark this road as the best
288  NBEdge* best1 = extractAndMarkFirst(n, bestIncoming);
289  if (counterIncomingEdges.find(best1) != counterIncomingEdges.end()) {
290  // ok, look, what we want is the opposit of the straight continuation edge
291  // but, what if such an edge does not exist? By now, we'll determine it
292  // geometrically
293  NBEdge* s = counterIncomingEdges.find(best1)->second;
294  if (GeomHelper::getMinAngleDiff(best1->getAngleAtNode(&n), s->getAngleAtNode(&n)) > 180 - 45) {
295  s->setJunctionPriority(&n, 1);
296  }
297  }
298  if (bestOutgoing.size() != 0) {
299  // mark the best outgoing as the continuation
300  sort(bestOutgoing.begin(), bestOutgoing.end(), NBContHelper::edge_similar_direction_sorter(best1));
301  best1 = extractAndMarkFirst(n, bestOutgoing);
302  if (counterOutgoingEdges.find(best1) != counterOutgoingEdges.end()) {
303  NBEdge* s = counterOutgoingEdges.find(best1)->second;
304  if (GeomHelper::getMinAngleDiff(best1->getAngleAtNode(&n), s->getAngleAtNode(&n)) > 180 - 45) {
305  s->setJunctionPriority(&n, 1);
306  }
307  }
308  }
309  return;
310  }
311 
312  // ok, what we want to do in this case is to determine which incoming
313  // has the best continuation...
314  // This means, when several incoming roads have the same priority,
315  // we want a (any) straight connection to be more priorised than a turning
316  SUMOReal bestAngle = 0;
317  NBEdge* bestFirst = 0;
318  NBEdge* bestSecond = 0;
319  bool hadBest = false;
320  for (i = bestIncoming.begin(); i != bestIncoming.end(); ++i) {
321  EdgeVector::iterator j;
322  NBEdge* t1 = *i;
323  SUMOReal angle1 = t1->getTotalAngle() + 180;
324  if (angle1 >= 360) {
325  angle1 -= 360;
326  }
327  for (j = i + 1; j != bestIncoming.end(); ++j) {
328  NBEdge* t2 = *j;
329  SUMOReal angle2 = t2->getTotalAngle() + 180;
330  if (angle2 >= 360) {
331  angle2 -= 360;
332  }
333  SUMOReal angle = GeomHelper::getMinAngleDiff(angle1, angle2);
334  if (!hadBest || angle > bestAngle) {
335  bestAngle = angle;
336  bestFirst = *i;
337  bestSecond = *j;
338  hadBest = true;
339  }
340  }
341  }
342  bestFirst->setJunctionPriority(&n, 1);
343  sort(bestOutgoing.begin(), bestOutgoing.end(), NBContHelper::edge_similar_direction_sorter(bestFirst));
344  if (bestOutgoing.size() != 0) {
345  extractAndMarkFirst(n, bestOutgoing);
346  }
347  bestSecond->setJunctionPriority(&n, 1);
348  sort(bestOutgoing.begin(), bestOutgoing.end(), NBContHelper::edge_similar_direction_sorter(bestSecond));
349  if (bestOutgoing.size() != 0) {
350  extractAndMarkFirst(n, bestOutgoing);
351  }
352 }
353 
354 
355 NBEdge*
357  if (s.size() == 0) {
358  return 0;
359  }
360  NBEdge* ret = s.front();
361  s.erase(s.begin());
362  ret->setJunctionPriority(&n, 1);
363  return ret;
364 }
365 
366 
367 bool
368 NBEdgePriorityComputer::samePriority(const NBEdge* const e1, const NBEdge* const e2) {
369  if (e1 == e2) {
370  return true;
371  }
372  if (e1->getPriority() != e2->getPriority()) {
373  return false;
374  }
375  if ((int) e1->getSpeed() != (int) e2->getSpeed()) {
376  return false;
377  }
378  return (int) e1->getNumLanes() == (int) e2->getNumLanes();
379 }
380 
381 
382 /****************************************************************************/
383 
const EdgeVector & getIncomingEdges() const
Returns this node&#39;s incoming edges.
Definition: NBNode.h:177
Sorts incoming and outgoing edges clockwise around the given node.
Definition: NBAlgorithms.h:128
NBEdge * getOppositeIncoming(NBEdge *e) const
Definition: NBNode.cpp:916
SumoXMLNodeType myType
The type of the junction.
Definition: NBNode.h:504
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:63
bool isTurningDirectionAt(const NBNode *n, const NBEdge *const edge) const
Returns whether the given edge is the opposite direction to this edge.
Definition: NBEdge.cpp:1570
Stores the information about the angle between an incoming (&quot;from&quot;) and an outgoing (&quot;to&quot;) edge...
Definition: NBAlgorithms.h:72
#define WRITE_WARNING(msg)
Definition: MsgHandler.h:196
const EdgeVector & getOutgoingEdges() const
Returns this node&#39;s outgoing edges.
Definition: NBNode.h:185
const std::string & getID() const
Returns the id.
Definition: Named.h:60
EdgeVector myAllEdges
Vector of incoming and outgoing edges.
Definition: NBNode.h:501
bool isConnectedTo(NBEdge *e)
Returns the information whethe a connection to the given edge has been added (or computed) ...
Definition: NBEdge.cpp:729
int getPriority() const
Returns the priority of the edge.
Definition: NBEdge.h:346
bool isSimpleContinuation() const
Definition: NBNode.cpp:389
static void computeEdgePriorities(NBNodeCont &nc)
Computes edge priorities within a node.
unsigned int getNumLanes() const
Returns the number of lanes.
Definition: NBEdge.h:338
static void computeTurnDirections(NBNodeCont &nc)
Computes turnaround destinations for all edges (if exist)
std::map< std::string, NBNode * >::const_iterator end() const
Returns the pointer to the end of the stored nodes.
Definition: NBNodeCont.h:149
EdgeVector myIncomingEdges
Vector of incoming edges.
Definition: NBNode.h:495
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:498
NBNode * getToNode() const
Returns the destination node of the edge.
Definition: NBEdge.h:362
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:38
static SUMOReal getMinAngleDiff(SUMOReal angle1, SUMOReal angle2)
Returns the minimum distance (clockwise/counter-clockwise) between both angles.
Definition: GeomHelper.cpp:391
void setJunctionPriority(const NBNode *const node, int prio)
Sets the junction priority of the edge.
Definition: NBEdge.cpp:1106
SUMOReal getTotalAngle() const
get the angle as measure from the start to the end of this edge
Definition: NBEdge.h:390
Represents a single node (junction) during network building.
Definition: NBNode.h:74
static NBEdge * extractAndMarkFirst(NBNode &n, std::vector< NBEdge * > &s)
Sets the priorites in case of a priority junction.
#define SUMOReal
Definition: config.h:215
Sorts &quot;Combination&quot;s by decreasing angle.
Definition: NBAlgorithms.h:82
static SUMOReal relAngle(SUMOReal angle1, SUMOReal angle2)
Definition: NBHelpers.cpp:62
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:422
Container for nodes during the netbuilding process.
Definition: NBNodeCont.h:63
static void sortNodesEdges(NBNodeCont &nc, bool leftHand)
Sorts a node&#39;s edges clockwise regarding driving direction.
const std::vector< Connection > & getConnections() const
Returns the connections.
Definition: NBEdge.h:724
std::map< std::string, NBNode * >::const_iterator begin() const
Returns the pointer to the begin of the stored nodes.
Definition: NBNodeCont.h:141
SUMOReal getAngleAtNode(const NBNode *const node) const
Returns the angle of the edge&#39;s geometry at the given node.
Definition: NBEdge.cpp:1116
NBNode * getFromNode() const
Returns the origin node of the edge.
Definition: NBEdge.h:354