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