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.sourceforge.net/
10 // Copyright (C) 2001-2012 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  SUMOReal s1 = (*i)->getSpeed() * (SUMOReal) 3.6;
205  SUMOReal s2 = (*j)->getSpeed() * (SUMOReal) 3.6;
206  if(fabs(s1-s2)>(SUMOReal) 9.5 || s1>=(SUMOReal) 49. || s2>=(SUMOReal) 49.) {
208  break;
209  }
210  }
211  }
212  // save type
213  n->myType = type;
214  }
215 }
216 
217 
218 // ---------------------------------------------------------------------------
219 // NBEdgePriorityComputer
220 // ---------------------------------------------------------------------------
221 void
223  for(std::map<std::string, NBNode*>::const_iterator i=nc.begin(); i!=nc.end(); ++i) {
224  NBNode *n = (*i).second;
225  // preset all junction's edge priorities to zero
226  for (EdgeVector::iterator j = n->myAllEdges.begin(); j != n->myAllEdges.end(); ++j) {
227  (*j)->setJunctionPriority(n, 0);
228  }
229  // check if the junction is not a real junction
230  if (n->myIncomingEdges.size() == 1 && n->myOutgoingEdges.size() == 1) {
231  continue;
232  }
233  // compute the priorities on junction when needed
236  }
237  }
238 }
239 
240 
241 void
243  if (n.myIncomingEdges.size() == 0 || n.myOutgoingEdges.size() == 0) {
244  return;
245  }
246  EdgeVector incoming = n.myIncomingEdges;
247  EdgeVector outgoing = n.myOutgoingEdges;
248  // what we do want to have is to extract the pair of roads that are
249  // the major roads for this junction
250  // let's get the list of incoming edges with the highest priority
251  std::sort(incoming.begin(), incoming.end(), NBContHelper::edge_by_priority_sorter());
252  EdgeVector bestIncoming;
253  NBEdge* best = incoming[0];
254  while (incoming.size() > 0 && samePriority(best, incoming[0])) {
255  bestIncoming.push_back(*incoming.begin());
256  incoming.erase(incoming.begin());
257  }
258  // now, let's get the list of best outgoing
259  assert(outgoing.size() != 0);
260  sort(outgoing.begin(), outgoing.end(), NBContHelper::edge_by_priority_sorter());
261  EdgeVector bestOutgoing;
262  best = outgoing[0];
263  while (outgoing.size() > 0 && samePriority(best, outgoing[0])) { //->getPriority()==best->getPriority()) {
264  bestOutgoing.push_back(*outgoing.begin());
265  outgoing.erase(outgoing.begin());
266  }
267  // now, let's compute for each of the best incoming edges
268  // the incoming which is most opposite
269  // the outgoing which is most opposite
270  EdgeVector::iterator i;
271  std::map<NBEdge*, NBEdge*> counterIncomingEdges;
272  std::map<NBEdge*, NBEdge*> counterOutgoingEdges;
273  incoming = n.myIncomingEdges;
274  outgoing = n.myOutgoingEdges;
275  for (i = bestIncoming.begin(); i != bestIncoming.end(); ++i) {
276  std::sort(incoming.begin(), incoming.end(), NBContHelper::edge_opposite_direction_sorter(*i, &n));
277  counterIncomingEdges[*i] = *incoming.begin();
278  std::sort(outgoing.begin(), outgoing.end(), NBContHelper::edge_opposite_direction_sorter(*i, &n));
279  counterOutgoingEdges[*i] = *outgoing.begin();
280  }
281  // ok, let's try
282  // 1) there is one best incoming road
283  if (bestIncoming.size() == 1) {
284  // let's mark this road as the best
285  NBEdge* best1 = extractAndMarkFirst(n, bestIncoming);
286  if(counterIncomingEdges.find(best1)!=counterIncomingEdges.end()) {
287  // ok, look, what we want is the opposit of the straight continuation edge
288  // but, what if such an edge does not exist? By now, we'll determine it
289  // geometrically
290  NBEdge *s = counterIncomingEdges.find(best1)->second;
291  if(GeomHelper::getMinAngleDiff(best1->getAngleAtNode(&n), s->getAngleAtNode(&n))>180-45) {
292  s->setJunctionPriority(&n, 1);
293  }
294  }
295  if (bestOutgoing.size() != 0) {
296  // mark the best outgoing as the continuation
297  sort(bestOutgoing.begin(), bestOutgoing.end(), NBContHelper::edge_similar_direction_sorter(best1));
298  best1 = extractAndMarkFirst(n, bestOutgoing);
299  if(counterOutgoingEdges.find(best1)!=counterOutgoingEdges.end()) {
300  NBEdge *s = counterOutgoingEdges.find(best1)->second;
301  if(GeomHelper::getMinAngleDiff(best1->getAngleAtNode(&n), s->getAngleAtNode(&n))>180-45) {
302  s->setJunctionPriority(&n, 1);
303  }
304  }
305  }
306  return;
307  }
308 
309  // ok, what we want to do in this case is to determine which incoming
310  // has the best continuation...
311  // This means, when several incoming roads have the same priority,
312  // we want a (any) straight connection to be more priorised than a turning
313  SUMOReal bestAngle = 0;
314  NBEdge* bestFirst = 0;
315  NBEdge* bestSecond = 0;
316  bool hadBest = false;
317  for (i = bestIncoming.begin(); i != bestIncoming.end(); ++i) {
318  EdgeVector::iterator j;
319  NBEdge* t1 = *i;
320  SUMOReal angle1 = t1->getAngle() + 180;
321  if (angle1 >= 360) {
322  angle1 -= 360;
323  }
324  for (j = i + 1; j != bestIncoming.end(); ++j) {
325  NBEdge* t2 = *j;
326  SUMOReal angle2 = t2->getAngle() + 180;
327  if (angle2 >= 360) {
328  angle2 -= 360;
329  }
330  SUMOReal angle = GeomHelper::getMinAngleDiff(angle1, angle2);
331  if (!hadBest || angle > bestAngle) {
332  bestAngle = angle;
333  bestFirst = *i;
334  bestSecond = *j;
335  hadBest = true;
336  }
337  }
338  }
339  bestFirst->setJunctionPriority(&n, 1);
340  sort(bestOutgoing.begin(), bestOutgoing.end(), NBContHelper::edge_similar_direction_sorter(bestFirst));
341  if (bestOutgoing.size() != 0) {
342  extractAndMarkFirst(n, bestOutgoing);
343  }
344  bestSecond->setJunctionPriority(&n, 1);
345  sort(bestOutgoing.begin(), bestOutgoing.end(), NBContHelper::edge_similar_direction_sorter(bestSecond));
346  if (bestOutgoing.size() != 0) {
347  extractAndMarkFirst(n, bestOutgoing);
348  }
349 }
350 
351 
352 NBEdge*
354  if (s.size() == 0) {
355  return 0;
356  }
357  NBEdge* ret = s.front();
358  s.erase(s.begin());
359  ret->setJunctionPriority(&n, 1);
360  return ret;
361 }
362 
363 
364 bool
365 NBEdgePriorityComputer::samePriority(const NBEdge*const e1, const NBEdge*const e2) {
366  if (e1 == e2) {
367  return true;
368  }
369  if (e1->getPriority() != e2->getPriority()) {
370  return false;
371  }
372  if ((int) e1->getSpeed() != (int) e2->getSpeed()) {
373  return false;
374  }
375  return (int) e1->getNumLanes() == (int) e2->getNumLanes();
376 }
377 
378 
379 /****************************************************************************/
380