SUMO - Simulation of Urban MObility
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
NBRequest.cpp
Go to the documentation of this file.
1 /****************************************************************************/
10 // This class computes the logic of a junction
11 /****************************************************************************/
12 // SUMO, Simulation of Urban MObility; see http://sumo-sim.org/
13 // Copyright (C) 2001-2014 DLR (http://www.dlr.de/) and contributors
14 /****************************************************************************/
15 //
16 // This file is part of SUMO.
17 // SUMO is free software: you can redistribute it and/or modify
18 // it under the terms of the GNU General Public License as published by
19 // the Free Software Foundation, either version 3 of the License, or
20 // (at your option) any later version.
21 //
22 /****************************************************************************/
23 
24 
25 // ===========================================================================
26 // included modules
27 // ===========================================================================
28 #ifdef _MSC_VER
29 #include <windows_config.h>
30 #else
31 #include <config.h>
32 #endif
33 
34 #include <string>
35 #include <vector>
36 #include <set>
37 #include <algorithm>
38 #include <bitset>
39 #include <sstream>
40 #include <map>
41 #include <cassert>
43 #include <utils/common/ToString.h>
46 #include "NBEdge.h"
47 #include "NBContHelper.h"
48 #include "NBTrafficLightLogic.h"
50 #include "NBNode.h"
51 #include "NBRequest.h"
52 
53 #ifdef CHECK_MEMORY_LEAKS
54 #include <foreign/nvwa/debug_new.h>
55 #endif // CHECK_MEMORY_LEAKS
56 
57 
58 // ===========================================================================
59 // static member variables
60 // ===========================================================================
61 size_t NBRequest::myGoodBuilds = 0;
62 size_t NBRequest::myNotBuild = 0;
63 
64 
65 // ===========================================================================
66 // method definitions
67 // ===========================================================================
69  NBNode* junction,
70  const EdgeVector& all,
71  const EdgeVector& incoming,
72  const EdgeVector& outgoing,
73  const NBConnectionProhibits& loadedProhibits) :
74  myJunction(junction),
75  myAll(all),
76  myIncoming(incoming),
77  myOutgoing(outgoing),
78  myCrossings(junction->getCrossings()) {
79  const size_t variations = numLinks();
80  // build maps with information which forbidding connection were
81  // computed and what's in there
82  myForbids.reserve(variations);
83  myDone.reserve(variations);
84  for (size_t i = 0; i < variations; i++) {
85  myForbids.push_back(LinkInfoCont(variations, false));
86  myDone.push_back(LinkInfoCont(variations, false));
87  }
88  // insert loaded prohibits
89  for (NBConnectionProhibits::const_iterator j = loadedProhibits.begin(); j != loadedProhibits.end(); j++) {
90  NBConnection prohibited = (*j).first;
91  bool ok1 = prohibited.check(ec);
92  if (find(myIncoming.begin(), myIncoming.end(), prohibited.getFrom()) == myIncoming.end()) {
93  ok1 = false;
94  }
95  if (find(myOutgoing.begin(), myOutgoing.end(), prohibited.getTo()) == myOutgoing.end()) {
96  ok1 = false;
97  }
98  int idx1 = 0;
99  if (ok1) {
100  idx1 = getIndex(prohibited.getFrom(), prohibited.getTo());
101  if (idx1 < 0) {
102  ok1 = false;
103  }
104  }
105  const NBConnectionVector& prohibiting = (*j).second;
106  for (NBConnectionVector::const_iterator k = prohibiting.begin(); k != prohibiting.end(); k++) {
107  NBConnection sprohibiting = *k;
108  bool ok2 = sprohibiting.check(ec);
109  if (find(myIncoming.begin(), myIncoming.end(), sprohibiting.getFrom()) == myIncoming.end()) {
110  ok2 = false;
111  }
112  if (find(myOutgoing.begin(), myOutgoing.end(), sprohibiting.getTo()) == myOutgoing.end()) {
113  ok2 = false;
114  }
115  if (ok1 && ok2) {
116  int idx2 = getIndex(sprohibiting.getFrom(), sprohibiting.getTo());
117  if (idx2 < 0) {
118  ok2 = false;
119  } else {
120  myForbids[idx2][idx1] = true;
121  myDone[idx2][idx1] = true;
122  myDone[idx1][idx2] = true;
123  myGoodBuilds++;
124  }
125  } else {
126  std::string pfID = prohibited.getFrom() != 0 ? prohibited.getFrom()->getID() : "UNKNOWN";
127  std::string ptID = prohibited.getTo() != 0 ? prohibited.getTo()->getID() : "UNKNOWN";
128  std::string bfID = sprohibiting.getFrom() != 0 ? sprohibiting.getFrom()->getID() : "UNKNOWN";
129  std::string btID = sprohibiting.getTo() != 0 ? sprohibiting.getTo()->getID() : "UNKNOWN";
130  WRITE_WARNING("could not prohibit " + pfID + "->" + ptID + " by " + bfID + "->" + btID);
131  myNotBuild++;
132  }
133  }
134  }
135  // ok, check whether someone has prohibited two links vice versa
136  // (this happens also in some Vissim-networks, when edges are joined)
137  for (size_t s1 = 0; s1 < variations; s1++) {
138  for (size_t s2 = s1 + 1; s2 < variations; s2++) {
139  // not set, yet
140  if (!myDone[s1][s2]) {
141  continue;
142  }
143  // check whether both prohibit vice versa
144  if (myForbids[s1][s2] && myForbids[s2][s1]) {
145  // mark unset - let our algorithm fix it later
146  myDone[s1][s2] = false;
147  myDone[s2][s1] = false;
148  }
149  }
150  }
151 }
152 
153 
155 
156 
157 void
159  EdgeVector::const_iterator i, j;
160  for (i = myIncoming.begin(); i != myIncoming.end(); i++) {
161  for (j = myOutgoing.begin(); j != myOutgoing.end(); j++) {
162  computeRightOutgoingLinkCrossings(leftHanded, *i, *j);
163  computeLeftOutgoingLinkCrossings(leftHanded, *i, *j);
164  }
165  }
166  // reset signalised/non-signalised dependencies
167  resetSignalised();
168  // reset foes it the number of lanes matches (or exceeds) the number of incoming connections
170 }
171 
172 
173 void
175  EdgeVector::const_iterator pfrom = find(myAll.begin(), myAll.end(), from);
176  while (*pfrom != to) {
178  if ((*pfrom)->getToNode() == myJunction) {
179  EdgeVector::const_iterator pto = find(myAll.begin(), myAll.end(), to);
180  while (*pto != from) {
181  if (!((*pto)->getToNode() == myJunction)) {
182  setBlocking(leftHanded, from, to, *pfrom, *pto);
183  }
185  }
186  }
187  }
188 }
189 
190 
191 void
193  EdgeVector::const_iterator pfrom = find(myAll.begin(), myAll.end(), from);
194  while (*pfrom != to) {
195  NBContHelper::nextCW(myAll, pfrom);
196  if ((*pfrom)->getToNode() == myJunction) {
197  EdgeVector::const_iterator pto = find(myAll.begin(), myAll.end(), to);
198  while (*pto != from) {
199  if (!((*pto)->getToNode() == myJunction)) {
200  setBlocking(leftHanded, from, to, *pfrom, *pto);
201  }
203  }
204  }
205  }
206 }
207 
208 
209 void
210 NBRequest::setBlocking(bool leftHanded,
211  NBEdge* from1, NBEdge* to1,
212  NBEdge* from2, NBEdge* to2) {
213  // check whether one of the links has a dead end
214  if (to1 == 0 || to2 == 0) {
215  return;
216  }
217  // get the indices of both links
218  int idx1 = getIndex(from1, to1);
219  int idx2 = getIndex(from2, to2);
220  if (idx1 < 0 || idx2 < 0) {
221  return; // !!! error output? did not happend, yet
222  }
223  // check whether the link crossing has already been checked
224  assert((size_t) idx1 < myIncoming.size()*myOutgoing.size());
225  if (myDone[idx1][idx2]) {
226  return;
227  }
228  // mark the crossings as done
229  myDone[idx1][idx2] = true;
230  myDone[idx2][idx1] = true;
231  // special case all-way stop
233  // all ways forbid each other. Conflict resolution happens via arrival time
234  myForbids[idx1][idx2] = true;
235  myForbids[idx2][idx1] = true;
236  return;
237  }
238  // check if one of the links is a turn; this link is always not priorised
239  // true for right-before-left and priority
240  if (from1->isTurningDirectionAt(myJunction, to1)) {
241  myForbids[idx2][idx1] = true;
242  return;
243  }
244  if (from2->isTurningDirectionAt(myJunction, to2)) {
245  myForbids[idx1][idx2] = true;
246  return;
247  }
248  // check the priorities if required by node type
250  int from1p = from1->getJunctionPriority(myJunction);
251  int from2p = from2->getJunctionPriority(myJunction);
252  // check if one of the connections is higher priorised when incoming into
253  // the junction, the connection road will yield
254  if (from1p > from2p) {
255  myForbids[idx1][idx2] = true;
256  return;
257  }
258  if (from2p > from1p) {
259  myForbids[idx2][idx1] = true;
260  return;
261  }
262  }
263 
264  // check whether one of the connections is higher priorised on
265  // the outgoing edge when both roads are high priorised
266  // the connection with the lower priorised outgoing edge will lead
267  // should be valid for priority junctions only
268  /*
269  if (from1p > 0 && from2p > 0) {
270  assert(myJunction->getType() != NODETYPE_RIGHT_BEFORE_LEFT);
271  int to1p = to1->getJunctionPriority(myJunction);
272  int to2p = to2->getJunctionPriority(myJunction);
273  if (to1p > to2p) {
274  myForbids[idx1][idx2] = true;
275  return;
276  }
277  if (to2p > to1p) {
278  myForbids[idx2][idx1] = true;
279  return;
280  }
281  }
282  */
283 
284  // compute the yielding due to the right-before-left rule
285  // get the position of the incoming lanes in the junction-wheel
286  EdgeVector::const_iterator c1 = find(myAll.begin(), myAll.end(), from1);
288  // go through next edges clockwise...
289  while (*c1 != from1 && *c1 != from2) {
290  if (*c1 == to2) {
291  // if we encounter to2 the second one prohibits the first
292  if (!leftHanded) {
293  myForbids[idx2][idx1] = true;
294  } else {
295  myForbids[idx1][idx2] = true;
296  }
297  return;
298  }
299  NBContHelper::nextCW(myAll, c1);
300  }
301  // get the position of the incoming lanes in the junction-wheel
302  EdgeVector::const_iterator c2 = find(myAll.begin(), myAll.end(), from2);
303  NBContHelper::nextCW(myAll, c2);
304  // go through next edges clockwise...
305  while (*c2 != from2 && *c2 != from1) {
306  if (*c2 == to1) {
307  // if we encounter to1 the second one prohibits the first
308  if (!leftHanded) {
309  myForbids[idx1][idx2] = true;
310  } else {
311  myForbids[idx2][idx1] = true;
312  }
313  return;
314  }
315  NBContHelper::nextCW(myAll, c2);
316  }
317 }
318 
319 
320 size_t
322  EdgeVector::const_iterator p = find(myAll.begin(), myAll.end(), from);
323  size_t ret = 0;
324  do {
325  ret++;
326  if (p == myAll.begin()) {
327  p = myAll.end();
328  }
329  p--;
330  } while (*p != to);
331  return ret;
332 }
333 
334 
335 void
336 NBRequest::writeLogic(std::string /* key */, OutputDevice& into, const bool checkLaneFoes) const {
337  int pos = 0;
338  EdgeVector::const_iterator i;
339  // normal connections
340  for (i = myIncoming.begin(); i != myIncoming.end(); i++) {
341  unsigned int noLanes = (*i)->getNumLanes();
342  for (unsigned int k = 0; k < noLanes; k++) {
343  pos = writeLaneResponse(into, *i, k, pos, checkLaneFoes);
344  }
345  }
346  // crossings
347  for (std::vector<NBNode::Crossing>::const_iterator i = myCrossings.begin(); i != myCrossings.end(); i++) {
348  pos = writeCrossingResponse(into, *i, pos);
349  }
350 }
351 
352 
353 void
355  // go through possible prohibitions
356  for (EdgeVector::const_iterator i11 = myIncoming.begin(); i11 != myIncoming.end(); i11++) {
357  unsigned int noLanesEdge1 = (*i11)->getNumLanes();
358  for (unsigned int j1 = 0; j1 < noLanesEdge1; j1++) {
359  std::vector<NBEdge::Connection> el1 = (*i11)->getConnectionsFromLane(j1);
360  for (std::vector<NBEdge::Connection>::iterator i12 = el1.begin(); i12 != el1.end(); ++i12) {
361  int idx1 = getIndex((*i11), (*i12).toEdge);
362  if (idx1 < 0) {
363  continue;
364  }
365  // go through possibly prohibited
366  for (EdgeVector::const_iterator i21 = myIncoming.begin(); i21 != myIncoming.end(); i21++) {
367  unsigned int noLanesEdge2 = (*i21)->getNumLanes();
368  for (unsigned int j2 = 0; j2 < noLanesEdge2; j2++) {
369  std::vector<NBEdge::Connection> el2 = (*i21)->getConnectionsFromLane(j2);
370  for (std::vector<NBEdge::Connection>::iterator i22 = el2.begin(); i22 != el2.end(); i22++) {
371  int idx2 = getIndex((*i21), (*i22).toEdge);
372  if (idx2 < 0) {
373  continue;
374  }
375  // check
376  // same incoming connections do not prohibit each other
377  if ((*i11) == (*i21)) {
378  myForbids[idx1][idx2] = false;
379  myForbids[idx2][idx1] = false;
380  continue;
381  }
382  // check other
383  // if both are non-signalised or both are signalised
384  if (((*i12).tlID == "" && (*i22).tlID == "")
385  ||
386  ((*i12).tlID != "" && (*i22).tlID != "")) {
387  // do nothing
388  continue;
389  }
390  // supposing, we don not have to
391  // brake if we are no foes
392  if (!foes(*i11, (*i12).toEdge, *i21, (*i22).toEdge)) {
393  continue;
394  }
395  // otherwise:
396  // the non-signalised must break
397  if ((*i12).tlID != "") {
398  myForbids[idx1][idx2] = true;
399  myForbids[idx2][idx1] = false;
400  } else {
401  myForbids[idx1][idx2] = false;
402  myForbids[idx2][idx1] = true;
403  }
404  }
405  }
406  }
407  }
408  }
409  }
410 }
411 
412 
413 std::pair<unsigned int, unsigned int>
415  unsigned int noLanes = 0;
416  unsigned int noLinks = 0;
417  for (EdgeVector::const_iterator i = myIncoming.begin();
418  i != myIncoming.end(); i++) {
419  unsigned int noLanesEdge = (*i)->getNumLanes();
420  for (unsigned int j = 0; j < noLanesEdge; j++) {
421  unsigned int numConnections = (unsigned int)(*i)->getConnectionsFromLane(j).size();
422  noLinks += numConnections;
423  if (numConnections > 0) {
424  noLanes++;
425  }
426  }
427  }
428  return std::make_pair(noLanes, noLinks);
429 }
430 
431 
432 bool
433 NBRequest::foes(const NBEdge* const from1, const NBEdge* const to1,
434  const NBEdge* const from2, const NBEdge* const to2) const {
435  // unconnected edges do not forbid other edges
436  if (to1 == 0 || to2 == 0) {
437  return false;
438  }
439  // get the indices
440  int idx1 = getIndex(from1, to1);
441  int idx2 = getIndex(from2, to2);
442  if (idx1 < 0 || idx2 < 0) {
443  return false; // sure? (The connection does not exist within this junction)
444  }
445  assert((size_t) idx1 < myIncoming.size()*myOutgoing.size());
446  assert((size_t) idx2 < myIncoming.size()*myOutgoing.size());
447  return myForbids[idx1][idx2] || myForbids[idx2][idx1];
448 }
449 
450 
451 bool
452 NBRequest::forbids(const NBEdge* const possProhibitorFrom, const NBEdge* const possProhibitorTo,
453  const NBEdge* const possProhibitedFrom, const NBEdge* const possProhibitedTo,
454  bool regardNonSignalisedLowerPriority) const {
455  // unconnected edges do not forbid other edges
456  if (possProhibitorTo == 0 || possProhibitedTo == 0) {
457  return false;
458  }
459  // get the indices
460  int possProhibitorIdx = getIndex(possProhibitorFrom, possProhibitorTo);
461  int possProhibitedIdx = getIndex(possProhibitedFrom, possProhibitedTo);
462  if (possProhibitorIdx < 0 || possProhibitedIdx < 0) {
463  return false; // sure? (The connection does not exist within this junction)
464  }
465  assert((size_t) possProhibitorIdx < myIncoming.size()*myOutgoing.size());
466  assert((size_t) possProhibitedIdx < myIncoming.size()*myOutgoing.size());
467  // check simple right-of-way-rules
468  if (!regardNonSignalisedLowerPriority) {
469  return myForbids[possProhibitorIdx][possProhibitedIdx];
470  }
471  // if its not forbidden, report
472  if (!myForbids[possProhibitorIdx][possProhibitedIdx]) {
473  return false;
474  }
475  // do not forbid a signalised stream by a non-signalised
476  if (!possProhibitorFrom->hasSignalisedConnectionTo(possProhibitorTo)) {
477  return false;
478  }
479  return true;
480 }
481 
482 
483 int
485  int fromLane, int pos, const bool checkLaneFoes) const {
486  std::vector<NBEdge::Connection> connected = from->getConnectionsFromLane(fromLane);
487  for (std::vector<NBEdge::Connection>::iterator j = connected.begin(); j != connected.end(); j++) {
488  assert((*j).toEdge != 0);
490  od.writeAttr(SUMO_ATTR_INDEX, pos++);
491  od.writeAttr(SUMO_ATTR_RESPONSE, getResponseString(from, (*j).toEdge, fromLane, (*j).toLane, (*j).mayDefinitelyPass, checkLaneFoes));
492  od.writeAttr(SUMO_ATTR_FOES, getFoesString(from, (*j).toEdge, fromLane, (*j).toLane, checkLaneFoes));
493  if (!OptionsCont::getOptions().getBool("no-internal-links")) {
494  od.writeAttr(SUMO_ATTR_CONT, j->haveVia);
495  }
496  od.closeTag();
497  }
498  return pos;
499 }
500 
501 
502 int
503 NBRequest::writeCrossingResponse(OutputDevice& od, const NBNode::Crossing& crossing, int pos) const {
504  std::string foes(myCrossings.size(), '0');
505  std::string response(myCrossings.size(), '0');
506  // conflicts with normal connections
507  for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin(); i != myIncoming.rend(); i++) {
508  //const std::vector<NBEdge::Connection> &allConnections = (*i)->getConnections();
509  const NBEdge* from = *i;
510  unsigned int noLanes = from->getNumLanes();
511  for (int j = noLanes; j-- > 0;) {
512  std::vector<NBEdge::Connection> connected = from->getConnectionsFromLane(j);
513  int size = (int) connected.size();
514  for (int k = size; k-- > 0;) {
515  const NBEdge* to = connected[k].toEdge;
516  bool foe = false;
517  for (EdgeVector::const_iterator it_e = crossing.edges.begin(); it_e != crossing.edges.end(); ++it_e) {
518  if ((*it_e) == from || (*it_e) == to) {
519  foe = true;
520  break;
521  }
522  }
523  foes += foe ? '1' : '0';
524  response += mustBrakeForCrossing(from, to, crossing) || !foe ? '0' : '1';
525  }
526  }
527  }
529  od.writeAttr(SUMO_ATTR_INDEX, pos++);
530  od.writeAttr(SUMO_ATTR_RESPONSE, response);
532  od.writeAttr(SUMO_ATTR_CONT, false);
533  od.closeTag();
534  return pos;
535 }
536 
537 
538 std::string
539 NBRequest::getResponseString(const NBEdge* const from, const NBEdge* const to,
540  int fromLane, int toLane, bool mayDefinitelyPass, const bool checkLaneFoes) const {
541  int idx = 0;
542  if (to != 0) {
543  idx = getIndex(from, to);
544  }
545  std::string result;
546  // crossings
547  for (std::vector<NBNode::Crossing>::const_reverse_iterator i = myCrossings.rbegin(); i != myCrossings.rend(); i++) {
548  result += mustBrakeForCrossing(from, to, *i) ? '1' : '0';
549  }
550  // normal connections
551  for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin(); i != myIncoming.rend(); i++) {
552  //const std::vector<NBEdge::Connection> &allConnections = (*i)->getConnections();
553  unsigned int noLanes = (*i)->getNumLanes();
554  for (int j = noLanes; j-- > 0;) {
555  std::vector<NBEdge::Connection> connected = (*i)->getConnectionsFromLane(j);
556  int size = (int) connected.size();
557  for (int k = size; k-- > 0;) {
558  if (mayDefinitelyPass) {
559  result += '0';
560  } else if ((*i) == from && fromLane == j) {
561  // do not prohibit a connection by others from same lane
562  result += '0';
563  } else {
564  assert(k < (int) connected.size());
565  assert((size_t) idx < myIncoming.size()*myOutgoing.size());
566  assert(connected[k].toEdge != 0);
567  assert((size_t) getIndex(*i, connected[k].toEdge) < myIncoming.size()*myOutgoing.size());
568  // check whether the connection is prohibited by another one
569  if ((myForbids[getIndex(*i, connected[k].toEdge)][idx] &&
570  (!checkLaneFoes || laneConflict(from, to, toLane, *i, connected[k].toEdge, connected[k].toLane)))
571  || rightTurnConflict(from, to, fromLane, *i, connected[k].toEdge, connected[k].fromLane)) {
572  result += '1';
573  } else {
574  result += '0';
575  }
576  }
577  }
578  }
579  }
580  return result;
581 }
582 
583 
584 std::string
585 NBRequest::getFoesString(NBEdge* from, NBEdge* to, int fromLane, int toLane, const bool checkLaneFoes) const {
586  // remember the case when the lane is a "dead end" in the meaning that
587  // vehicles must choose another lane to move over the following
588  // junction
589  // !!! move to forbidden
590  std::string result;
591  // crossings
592  for (std::vector<NBNode::Crossing>::const_reverse_iterator i = myCrossings.rbegin(); i != myCrossings.rend(); i++) {
593  bool foes = false;
594  for (EdgeVector::const_iterator it_e = (*i).edges.begin(); it_e != (*i).edges.end(); ++it_e) {
595  if ((*it_e) == from || (*it_e) == to) {
596  foes = true;
597  break;
598  }
599  }
600  result += foes ? '1' : '0';
601  }
602  // normal connections
603  for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin();
604  i != myIncoming.rend(); i++) {
605 
606  for (int j = (int)(*i)->getNumLanes() - 1; j >= 0; --j) {
607  std::vector<NBEdge::Connection> connected = (*i)->getConnectionsFromLane(j);
608  int size = (int) connected.size();
609  for (int k = size; k-- > 0;) {
610  if ((foes(from, to, (*i), connected[k].toEdge) &&
611  (!checkLaneFoes || laneConflict(from, to, toLane, *i, connected[k].toEdge, connected[k].toLane)))
612  || rightTurnConflict(from, to, fromLane, *i, connected[k].toEdge, connected[k].fromLane)) {
613  result += '1';
614  } else {
615  result += '0';
616  }
617  }
618  }
619  }
620  return result;
621 }
622 
623 
624 bool
625 NBRequest::laneConflict(const NBEdge* from, const NBEdge* to, int toLane,
626  const NBEdge* prohibitorFrom, const NBEdge* prohibitorTo, int prohibitorToLane) const {
627  if (to != prohibitorTo) {
628  return true;
629  }
630  // since we know that the edge2edge connections are in conflict, the only
631  // situation in which the lane2lane connections can be conflict-free is, if
632  // they target the same edge but do not cross each other
634  from->getAngleAtNode(from->getToNode()), to->getAngleAtNode(to->getFromNode()));
635  if (angle == 180) {
636  angle = -180; // turnarounds are left turns
637  }
638  const SUMOReal prohibitorAngle = NBHelpers::relAngle(
639  prohibitorFrom->getAngleAtNode(prohibitorFrom->getToNode()), to->getAngleAtNode(to->getFromNode()));
640  const bool rightOfProhibitor = prohibitorFrom->isTurningDirectionAt(prohibitorFrom->getToNode(), to)
641  || (angle > prohibitorAngle && !from->isTurningDirectionAt(from->getToNode(), to));
642  return rightOfProhibitor ? toLane >= prohibitorToLane : toLane <= prohibitorToLane;
643 }
644 
645 
646 bool
647 NBRequest::rightTurnConflict(const NBEdge* from, const NBEdge* to, int fromLane,
648  const NBEdge* prohibitorFrom, const NBEdge* prohibitorTo, int prohibitorFromLane) const {
649  if (from != prohibitorFrom) {
650  return false;
651  }
652  if (from->isTurningDirectionAt(from->getToNode(), to)) {
653  // XXX should warn if there are any non-turning connections left of this
654  return false;
655  }
656  const bool lefthand = OptionsCont::getOptions().getBool("lefthand");
657  if ((!lefthand && fromLane <= prohibitorFromLane) ||
658  (lefthand && fromLane >= prohibitorFromLane)) {
659  return false;
660  }
661  // conflict if to is between prohibitorTo and from when going clockwise
662  const SUMOReal toAngleAtNode = fmod(to->getStartAngle() + 180, (SUMOReal)360.0);
663  const SUMOReal prohibitorToAngleAtNode = fmod(prohibitorTo->getStartAngle() + 180, (SUMOReal)360.0);
664  return (lefthand != (GeomHelper::getCWAngleDiff(from->getEndAngle(), toAngleAtNode) <
665  GeomHelper::getCWAngleDiff(from->getEndAngle(), prohibitorToAngleAtNode)));
666 }
667 
668 
669 int
670 NBRequest::getIndex(const NBEdge* const from, const NBEdge* const to) const {
671  EdgeVector::const_iterator fp = find(myIncoming.begin(), myIncoming.end(), from);
672  EdgeVector::const_iterator tp = find(myOutgoing.begin(), myOutgoing.end(), to);
673  if (fp == myIncoming.end() || tp == myOutgoing.end()) {
674  return -1;
675  }
676  // compute the index
677  return (int)(distance(myIncoming.begin(), fp) * myOutgoing.size() + distance(myOutgoing.begin(), tp));
678 }
679 
680 
681 std::ostream&
682 operator<<(std::ostream& os, const NBRequest& r) {
683  size_t variations = r.numLinks();
684  for (size_t i = 0; i < variations; i++) {
685  os << i << ' ';
686  for (size_t j = 0; j < variations; j++) {
687  if (r.myForbids[i][j]) {
688  os << '1';
689  } else {
690  os << '0';
691  }
692  }
693  os << std::endl;
694  }
695  os << std::endl;
696  return os;
697 }
698 
699 
700 bool
701 NBRequest::mustBrake(const NBEdge* const from, const NBEdge* const to) const {
702  // vehicles which do not have a following lane must always decelerate to the end
703  if (to == 0) {
704  return true;
705  }
706  // get the indices
707  int idx2 = getIndex(from, to);
708  if (idx2 == -1) {
709  return false;
710  }
711  // go through all (existing) connections;
712  // check whether any of these forbids the one to determine
713  assert((size_t) idx2 < myIncoming.size()*myOutgoing.size());
714  for (size_t idx1 = 0; idx1 < numLinks(); idx1++) {
715  //assert(myDone[idx1][idx2]);
716  if (myDone[idx1][idx2] && myForbids[idx1][idx2]) {
717  return true;
718  }
719  }
720  // maybe we need to brake for a pedestrian crossing
721  for (std::vector<NBNode::Crossing>::const_reverse_iterator i = myCrossings.rbegin(); i != myCrossings.rend(); i++) {
722  if (mustBrakeForCrossing(from, to, *i)) {
723  return true;
724  }
725  }
726  return false;
727 }
728 
729 bool
730 NBRequest::mustBrakeForCrossing(const NBEdge* const from, const NBEdge* const to, const NBNode::Crossing& crossing) const {
731  const LinkDirection dir = myJunction->getDirection(from, to);
732  const bool mustYield = dir == LINKDIR_LEFT || dir == LINKDIR_RIGHT;
733  if (crossing.priority || mustYield) {
734  for (EdgeVector::const_iterator it_e = crossing.edges.begin(); it_e != crossing.edges.end(); ++it_e) {
735  // left and right turns must yield to unprioritized crossings only on their destination edge
736  if (((*it_e) == from && crossing.priority) || (*it_e) == to) {
737  return true;
738  }
739  }
740  }
741  return false;
742 }
743 
744 
745 bool
746 NBRequest::mustBrake(const NBEdge* const possProhibitorFrom, const NBEdge* const possProhibitorTo,
747  const NBEdge* const possProhibitedFrom, const NBEdge* const possProhibitedTo) const {
748  // get the indices
749  int idx1 = getIndex(possProhibitorFrom, possProhibitorTo);
750  int idx2 = getIndex(possProhibitedFrom, possProhibitedTo);
751  return (myForbids[idx2][idx1]);
752 }
753 
754 
755 void
757  // check if any errors occured on build the link prohibitions
758  if (myNotBuild != 0) {
759  WRITE_WARNING(toString(myNotBuild) + " of " + toString(myNotBuild + myGoodBuilds) + " prohibitions were not build.");
760  }
761 }
762 
763 
764 void
766  // map from edge to number of incoming connections
767  std::map<NBEdge*, size_t> incomingCount; // initialized to 0
768  // map from edge to indices of approached lanes
769  std::map<NBEdge*, std::set<int> > approachedLanes;
770  // map from edge to list of incoming edges
771  std::map<NBEdge*, EdgeVector> incomingEdges;
772  for (EdgeVector::const_iterator it_e = myIncoming.begin(); it_e != myIncoming.end(); it_e++) {
773  const std::vector<NBEdge::Connection> connections = (*it_e)->getConnections();
774  for (std::vector<NBEdge::Connection>::const_iterator it_c = connections.begin(); it_c != connections.end(); ++it_c) {
775  incomingCount[it_c->toEdge]++;
776  approachedLanes[it_c->toEdge].insert(it_c->toLane);
777  incomingEdges[it_c->toEdge].push_back(*it_e);
778  }
779  }
780  for (std::map<NBEdge*, size_t>::iterator it = incomingCount.begin(); it != incomingCount.end(); ++it) {
781  NBEdge* to = it->first;
782  // we cannot test against to->getNumLanes() since not all lanes may be used
783  if (approachedLanes[to].size() >= it->second) {
784  EdgeVector& incoming = incomingEdges[to];
785  // make these connections mutually unconflicting
786  for (EdgeVector::iterator it_e1 = incoming.begin(); it_e1 != incoming.end(); ++it_e1) {
787  for (EdgeVector::iterator it_e2 = incoming.begin(); it_e2 != incoming.end(); ++it_e2) {
788  myForbids[getIndex(*it_e1, to)][getIndex(*it_e2, to)] = false;
789  }
790  }
791  }
792  }
793 }
794 
795 
796 size_t
798  return myIncoming.size() * myOutgoing.size() + myCrossings.size();
799 }
800 
801 /****************************************************************************/
802