Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2026 German Aerospace Center (DLR) and others.
4 : // This program and the accompanying materials are made available under the
5 : // terms of the Eclipse Public License 2.0 which is available at
6 : // https://www.eclipse.org/legal/epl-2.0/
7 : // This Source Code may also be made available under the following Secondary
8 : // Licenses when the conditions for such availability set forth in the Eclipse
9 : // Public License 2.0 are satisfied: GNU General Public License, version 2
10 : // or later which is available at
11 : // https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
12 : // SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
13 : /****************************************************************************/
14 : /// @file NBRequest.cpp
15 : /// @author Daniel Krajzewicz
16 : /// @author Jakob Erdmann
17 : /// @author Michael Behrisch
18 : /// @author Laura Bieker
19 : /// @date Tue, 20 Nov 2001
20 : ///
21 : // This class computes the logic of a junction
22 : /****************************************************************************/
23 : #include <config.h>
24 :
25 : #include <string>
26 : #include <vector>
27 : #include <set>
28 : #include <algorithm>
29 : #include <bitset>
30 : #include <sstream>
31 : #include <map>
32 : #include <cassert>
33 : #include <utils/common/MsgHandler.h>
34 : #include <utils/common/ToString.h>
35 : #include <utils/options/OptionsCont.h>
36 : #include <utils/iodevices/OutputDevice.h>
37 : #include "NBEdge.h"
38 : #include "NBContHelper.h"
39 : #include "NBNode.h"
40 : #include "NBRequest.h"
41 :
42 : //#define DEBUG_RESPONSE
43 : //#define DEBUG_SETBLOCKING
44 : #define DEBUGCOND (myJunction->getID() == "C")
45 :
46 : // ===========================================================================
47 : // static member variables
48 : // ===========================================================================
49 : int NBRequest::myGoodBuilds = 0;
50 : int NBRequest::myNotBuild = 0;
51 :
52 :
53 : // ===========================================================================
54 : // method definitions
55 : // ===========================================================================
56 49076 : NBRequest::NBRequest(const NBEdgeCont& ec,
57 : NBNode* junction,
58 : const EdgeVector& all,
59 : const EdgeVector& incoming,
60 : const EdgeVector& outgoing,
61 49076 : const NBConnectionProhibits& loadedProhibits) :
62 49076 : myJunction(junction),
63 49076 : myAll(all),
64 49076 : myIncoming(incoming),
65 49076 : myOutgoing(outgoing) {
66 49076 : const int variations = numLinks();
67 : // build maps with information which forbidding connection were
68 : // computed and what's in there
69 49076 : myForbids.reserve(variations);
70 49076 : myDone.reserve(variations);
71 298560 : for (int i = 0; i < variations; i++) {
72 249484 : myForbids.push_back(LinkInfoCont(variations, false));
73 498968 : myDone.push_back(LinkInfoCont(variations, false));
74 : }
75 : // insert loaded prohibits
76 49178 : for (NBConnectionProhibits::const_iterator j = loadedProhibits.begin(); j != loadedProhibits.end(); j++) {
77 102 : NBConnection prohibited = (*j).first;
78 102 : bool ok1 = prohibited.check(ec);
79 102 : if (find(myIncoming.begin(), myIncoming.end(), prohibited.getFrom()) == myIncoming.end()) {
80 : ok1 = false;
81 : }
82 102 : if (find(myOutgoing.begin(), myOutgoing.end(), prohibited.getTo()) == myOutgoing.end()) {
83 : ok1 = false;
84 : }
85 : int idx1 = 0;
86 102 : if (ok1) {
87 102 : idx1 = getIndex(prohibited.getFrom(), prohibited.getTo());
88 102 : if (idx1 < 0) {
89 : ok1 = false;
90 : }
91 : }
92 : const NBConnectionVector& prohibiting = (*j).second;
93 301 : for (NBConnectionVector::const_iterator k = prohibiting.begin(); k != prohibiting.end(); k++) {
94 199 : NBConnection sprohibiting = *k;
95 199 : bool ok2 = sprohibiting.check(ec);
96 199 : if (find(myIncoming.begin(), myIncoming.end(), sprohibiting.getFrom()) == myIncoming.end()) {
97 : ok2 = false;
98 : }
99 199 : if (find(myOutgoing.begin(), myOutgoing.end(), sprohibiting.getTo()) == myOutgoing.end()) {
100 : ok2 = false;
101 : }
102 199 : if (ok1 && ok2) {
103 199 : int idx2 = getIndex(sprohibiting.getFrom(), sprohibiting.getTo());
104 199 : if (idx2 < 0) {
105 : ok2 = false;
106 : } else {
107 199 : myForbids[idx2][idx1] = true;
108 : myDone[idx2][idx1] = true;
109 199 : myDone[idx1][idx2] = true;
110 199 : myGoodBuilds++;
111 : }
112 : } else {
113 0 : std::string pfID = prohibited.getFrom() != nullptr ? prohibited.getFrom()->getID() : "UNKNOWN";
114 0 : std::string ptID = prohibited.getTo() != nullptr ? prohibited.getTo()->getID() : "UNKNOWN";
115 0 : std::string bfID = sprohibiting.getFrom() != nullptr ? sprohibiting.getFrom()->getID() : "UNKNOWN";
116 0 : std::string btID = sprohibiting.getTo() != nullptr ? sprohibiting.getTo()->getID() : "UNKNOWN";
117 0 : WRITE_WARNING("could not prohibit " + pfID + "->" + ptID + " by " + bfID + "->" + btID);
118 0 : myNotBuild++;
119 : }
120 199 : }
121 102 : }
122 : // ok, check whether someone has prohibited two links vice versa
123 : // (this happens also in some Vissim-networks, when edges are joined)
124 298560 : for (int s1 = 0; s1 < variations; s1++) {
125 1898159 : for (int s2 = s1 + 1; s2 < variations; s2++) {
126 : // not set, yet
127 1648675 : if (!myDone[s1][s2]) {
128 1648563 : continue;
129 : }
130 : // check whether both prohibit vice versa
131 112 : if (myForbids[s1][s2] && myForbids[s2][s1]) {
132 : // mark unset - let our algorithm fix it later
133 : myDone[s1][s2] = false;
134 : myDone[s2][s1] = false;
135 : }
136 : }
137 : }
138 49076 : }
139 :
140 :
141 49076 : NBRequest::~NBRequest() {}
142 :
143 :
144 : void
145 42632 : NBRequest::buildBitfieldLogic() {
146 : EdgeVector::const_iterator i, j;
147 130330 : for (i = myIncoming.begin(); i != myIncoming.end(); i++) {
148 314610 : for (j = myOutgoing.begin(); j != myOutgoing.end(); j++) {
149 226912 : computeRightOutgoingLinkCrossings(*i, *j);
150 226912 : computeLeftOutgoingLinkCrossings(*i, *j);
151 : }
152 : }
153 : // reset signalised/non-signalised dependencies
154 42632 : resetSignalised();
155 : // reset foes it the number of lanes matches (or exceeds) the number of incoming connections
156 42632 : resetCooperating();
157 42632 : }
158 :
159 :
160 : void
161 226912 : NBRequest::computeRightOutgoingLinkCrossings(NBEdge* from, NBEdge* to) {
162 226912 : EdgeVector::const_iterator pfrom = std::find(myAll.begin(), myAll.end(), from);
163 973367 : while (*pfrom != to) {
164 746455 : NBContHelper::nextCCW(myAll, pfrom);
165 746455 : if ((*pfrom)->getToNode() == myJunction) {
166 260353 : EdgeVector::const_iterator pto = std::find(myAll.begin(), myAll.end(), to);
167 1047036 : while (*pto != from) {
168 786683 : if (!((*pto)->getToNode() == myJunction)) {
169 525960 : setBlocking(from, to, *pfrom, *pto);
170 : }
171 786683 : NBContHelper::nextCCW(myAll, pto);
172 : }
173 : }
174 : }
175 226912 : }
176 :
177 :
178 : void
179 226912 : NBRequest::computeLeftOutgoingLinkCrossings(NBEdge* from, NBEdge* to) {
180 226912 : EdgeVector::const_iterator pfrom = std::find(myAll.begin(), myAll.end(), from);
181 973367 : while (*pfrom != to) {
182 746455 : NBContHelper::nextCW(myAll, pfrom);
183 746455 : if ((*pfrom)->getToNode() == myJunction) {
184 260353 : EdgeVector::const_iterator pto = std::find(myAll.begin(), myAll.end(), to);
185 1047036 : while (*pto != from) {
186 786683 : if (!((*pto)->getToNode() == myJunction)) {
187 525960 : setBlocking(from, to, *pfrom, *pto);
188 : }
189 786683 : NBContHelper::nextCW(myAll, pto);
190 : }
191 : }
192 : }
193 226912 : }
194 :
195 :
196 : void
197 1051920 : NBRequest::setBlocking(NBEdge* from1, NBEdge* to1,
198 : NBEdge* from2, NBEdge* to2) {
199 : // check whether one of the links has a dead end
200 1051920 : if (to1 == nullptr || to2 == nullptr) {
201 1051920 : return;
202 : }
203 : // get the indices of both links
204 1051920 : int idx1 = getIndex(from1, to1);
205 1051920 : int idx2 = getIndex(from2, to2);
206 1051920 : if (idx1 < 0 || idx2 < 0) {
207 : return; // !!! error output? did not happend, yet
208 : }
209 : // check whether the link crossing has already been checked
210 : assert(idx1 < (int)(myIncoming.size() * myOutgoing.size()));
211 1051920 : if (myDone[idx1][idx2]) {
212 : return;
213 : }
214 : // mark the crossings as done
215 : myDone[idx1][idx2] = true;
216 525870 : myDone[idx2][idx1] = true;
217 : // special case all-way stop
218 525870 : if (myJunction->getType() == SumoXMLNodeType::ALLWAY_STOP) {
219 : // all ways forbid each other. Conflict resolution happens via arrival time
220 : myForbids[idx1][idx2] = true;
221 : myForbids[idx2][idx1] = true;
222 40 : return;
223 : }
224 : // check if one of the links is a turn; this link is always not priorised
225 : // true for right-before-left and priority
226 525830 : if (from1->isTurningDirectionAt(to1)) {
227 : myForbids[idx2][idx1] = true;
228 67489 : return;
229 : }
230 458341 : if (from2->isTurningDirectionAt(to2)) {
231 : myForbids[idx1][idx2] = true;
232 63837 : return;
233 : }
234 : // if there are no connections, there are no prohibitions
235 394504 : if (from1->isConnectedTo(to1)) {
236 243144 : if (!from2->isConnectedTo(to2)) {
237 : myForbids[idx1][idx2] = true;
238 : myForbids[idx2][idx1] = false;
239 27776 : return;
240 : }
241 : } else {
242 151360 : if (!from2->isConnectedTo(to2)) {
243 : myForbids[idx1][idx2] = false;
244 : myForbids[idx2][idx1] = false;
245 122856 : return;
246 : } else {
247 : myForbids[idx1][idx2] = false;
248 : myForbids[idx2][idx1] = true;
249 28504 : return;
250 : }
251 : }
252 : #ifdef DEBUG_SETBLOCKING
253 : if (DEBUGCOND) std::cout << "setBlocking type=" << toString(myJunction->getType())
254 : << " bentPrio=" << myJunction->isBentPriority()
255 : << " 1:" << from1->getID() << "->" << to1->getID()
256 : << " 2:" << from2->getID() << "->" << to2->getID() << "\n";
257 : #endif
258 : // check the priorities if required by node type
259 215368 : const bool typeEqual = myJunction->getType() == SumoXMLNodeType::RIGHT_BEFORE_LEFT || myJunction->getType() == SumoXMLNodeType::LEFT_BEFORE_RIGHT;
260 : if (!typeEqual) {
261 191945 : int from1p = from1->getJunctionPriority(myJunction);
262 191945 : int from2p = from2->getJunctionPriority(myJunction);
263 : #ifdef DEBUG_SETBLOCKING
264 : if (DEBUGCOND) {
265 : std::cout << " p1=" << from1p << " p2=" << from2p << "\n";
266 : }
267 : #endif
268 : // check if one of the connections is higher priorised when incoming into
269 : // the junction, the connection road will yield
270 191945 : if (from1p > from2p) {
271 : myForbids[idx1][idx2] = true;
272 67394 : return;
273 : }
274 124551 : if (from2p > from1p) {
275 : myForbids[idx2][idx1] = true;
276 54964 : return;
277 : }
278 : }
279 : // straight connections prohibit turning connections if the priorities are equal
280 : // (unless the junction is a bent priority junction)
281 93010 : LinkDirection ld1 = myJunction->getDirection(from1, to1);
282 93010 : LinkDirection ld2 = myJunction->getDirection(from2, to2);
283 93010 : if (!typeEqual && !myJunction->isBentPriority()) {
284 : #ifdef DEBUG_SETBLOCKING
285 : if (DEBUGCOND) std::cout << "setBlocking"
286 : << " 1:" << from1->getID() << "->" << to1->getID()
287 : << " 2:" << from2->getID() << "->" << to2->getID()
288 : << " dir1=" << toString(ld1) << " dir2=" << toString(ld2) << "\n";
289 : #endif
290 45357 : if (ld1 == LinkDirection::STRAIGHT) {
291 11274 : if (ld2 != LinkDirection::STRAIGHT) {
292 : myForbids[idx1][idx2] = true;
293 : myForbids[idx2][idx1] = false;
294 10341 : return;
295 : }
296 : } else {
297 34083 : if (ld2 == LinkDirection::STRAIGHT) {
298 : myForbids[idx1][idx2] = false;
299 : myForbids[idx2][idx1] = true;
300 10990 : return;
301 : }
302 : }
303 : }
304 :
305 : // check whether one of the connections is higher priorised on
306 : // the outgoing edge when both roads are high priorised
307 : // the connection with the lower priorised outgoing edge will lead
308 : // should be valid for priority junctions only
309 : /*
310 : if (from1p > 0 && from2p > 0) {
311 : assert(myJunction->getType() != SumoXMLNodeType::RIGHT_BEFORE_LEFT);
312 : int to1p = to1->getJunctionPriority(myJunction);
313 : int to2p = to2->getJunctionPriority(myJunction);
314 : if (to1p > to2p) {
315 : myForbids[idx1][idx2] = true;
316 : return;
317 : }
318 : if (to2p > to1p) {
319 : myForbids[idx2][idx1] = true;
320 : return;
321 : }
322 : }
323 : */
324 : #ifdef DEBUG_SETBLOCKING
325 : if (DEBUGCOND) std::cout << "setBlocking1"
326 : << " 1:" << from1->getID() << "->" << to1->getID()
327 : << " 2:" << from2->getID() << "->" << to2->getID();
328 : << " relAngle=" << NBHelpers::relAngle(from1->getAngleAtNode(myJunction), from2->getAngleAtNode(myJunction))
329 : #endif
330 :
331 : // compute the yielding due to the right-before-left rule
332 : // (or left-before-right rule)
333 : // get the position of the incoming lanes in the junction-wheel
334 71679 : EdgeVector::const_iterator c1 = std::find(myAll.begin(), myAll.end(), from1);
335 71679 : NBContHelper::nextCW(myAll, c1);
336 : // go through next edges clockwise...
337 218973 : while (*c1 != from1 && *c1 != from2) {
338 172427 : if (*c1 == to2) {
339 : // if we encounter to2 the second one prohibits the first
340 25133 : if (myJunction->getType() == SumoXMLNodeType::LEFT_BEFORE_RIGHT
341 25133 : && (ld1 != LinkDirection::LEFT || ld2 == LinkDirection::LEFT || (from1->getTurnDestination(true) != to2 &&
342 7 : (ld2 != LinkDirection::RIGHT ||
343 7 : fabs(NBHelpers::relAngle(from1->getAngleAtNode(myJunction),
344 7 : from2->getAngleAtNode(myJunction))) < 150))
345 : )) {
346 : myForbids[idx1][idx2] = true;
347 : #ifdef DEBUG_SETBLOCKING
348 : if (DEBUGCOND) {
349 : std::cout << " case1: 2 yields\n";
350 : }
351 : #endif
352 : } else {
353 : myForbids[idx2][idx1] = true;
354 : #ifdef DEBUG_SETBLOCKING
355 : if (DEBUGCOND) {
356 : std::cout << " case1: 1 yields\n";
357 : }
358 : #endif
359 : }
360 25133 : return;
361 : }
362 147294 : NBContHelper::nextCW(myAll, c1);
363 : }
364 : // get the position of the incoming lanes in the junction-wheel
365 46546 : EdgeVector::const_iterator c2 = std::find(myAll.begin(), myAll.end(), from2);
366 46546 : NBContHelper::nextCW(myAll, c2);
367 : // go through next edges clockwise...
368 151639 : while (*c2 != from2 && *c2 != from1) {
369 151639 : if (*c2 == to1) {
370 : // if we encounter to1 the second one prohibits the first
371 46546 : if (myJunction->getType() == SumoXMLNodeType::LEFT_BEFORE_RIGHT
372 46546 : && (ld2 != LinkDirection::LEFT || ld1 == LinkDirection::LEFT || (from2->getTurnDestination(true) != to1 &&
373 9 : (ld1 != LinkDirection::RIGHT ||
374 9 : fabs(NBHelpers::relAngle(from1->getAngleAtNode(myJunction),
375 9 : from2->getAngleAtNode(myJunction))) < 150))
376 : )) {
377 : myForbids[idx2][idx1] = true;
378 : #ifdef DEBUG_SETBLOCKING
379 : if (DEBUGCOND) {
380 : std::cout << " case2: 1 yields\n";
381 : }
382 : #endif
383 : } else {
384 : myForbids[idx1][idx2] = true;
385 : #ifdef DEBUG_SETBLOCKING
386 : if (DEBUGCOND) {
387 : std::cout << " case2: 2 yields\n";
388 : }
389 : #endif
390 : }
391 46546 : return;
392 : }
393 105093 : NBContHelper::nextCW(myAll, c2);
394 : }
395 : #ifdef DEBUG_SETBLOCKING
396 : if (DEBUGCOND) {
397 : std::cout << " noDecision\n";
398 : }
399 : #endif
400 : }
401 :
402 :
403 : int
404 0 : NBRequest::distanceCounterClockwise(NBEdge* from, NBEdge* to) {
405 0 : EdgeVector::const_iterator p = std::find(myAll.begin(), myAll.end(), from);
406 : int ret = 0;
407 : do {
408 0 : ret++;
409 0 : if (p == myAll.begin()) {
410 : p = myAll.end();
411 : }
412 : p--;
413 0 : } while (*p != to);
414 0 : return ret;
415 : }
416 :
417 : const std::string&
418 0 : NBRequest::getFoes(int linkIndex) const {
419 : assert(linkIndex >= 0);
420 : assert(linkIndex < (int)myFoes.size());
421 0 : return myFoes[linkIndex];
422 : }
423 :
424 :
425 : const std::string&
426 206926 : NBRequest::getResponse(int linkIndex) const {
427 : assert(linkIndex >= 0);
428 : assert(linkIndex < (int)myResponse.size());
429 206926 : return myResponse[linkIndex];
430 : }
431 :
432 :
433 : void
434 41640 : NBRequest::writeLogic(OutputDevice& into) const {
435 41640 : int numLinks = (int)myResponse.size();
436 : assert((int)myFoes.size() == numLinks);
437 : assert((int)myHaveVia.size() == numLinks);
438 : const bool padding = numLinks > 10;
439 240406 : for (int i = 0; i < numLinks; i++) {
440 198766 : into.openTag(SUMO_TAG_REQUEST);
441 198766 : into.writeAttr(SUMO_ATTR_INDEX, i);
442 198766 : if (padding && i < 10) {
443 95220 : into.writePadding(" ");
444 : }
445 198766 : into.writeAttr(SUMO_ATTR_RESPONSE, myResponse[i]);
446 198766 : into.writeAttr(SUMO_ATTR_FOES, myFoes[i]);
447 397532 : if (!OptionsCont::getOptions().getBool("no-internal-links")) {
448 92753 : into.writeAttr(SUMO_ATTR_CONT, myHaveVia[i]);
449 : }
450 397532 : into.closeTag();
451 : }
452 41640 : }
453 :
454 :
455 : void
456 42632 : NBRequest::computeLogic(const bool checkLaneFoes) {
457 : myResponse.clear();
458 : myFoes.clear();
459 : myHaveVia.clear();
460 : int pos = 0;
461 : EdgeVector::const_iterator i;
462 : // normal connections
463 130330 : for (i = myIncoming.begin(); i != myIncoming.end(); i++) {
464 87698 : int noLanes = (*i)->getNumLanes();
465 203232 : for (int k = 0; k < noLanes; k++) {
466 117359 : pos = computeLaneResponse(*i, k, pos, checkLaneFoes || myJunction->getType() == SumoXMLNodeType::ZIPPER);
467 : }
468 : }
469 : // crossings
470 42632 : auto crossings = myJunction->getCrossings();
471 44245 : for (auto c : crossings) {
472 1613 : pos = computeCrossingResponse(*c, pos);
473 : }
474 42632 : }
475 :
476 : void
477 42632 : NBRequest::resetSignalised() {
478 : // go through possible prohibitions
479 130330 : for (EdgeVector::const_iterator i11 = myIncoming.begin(); i11 != myIncoming.end(); i11++) {
480 87698 : int noLanesEdge1 = (*i11)->getNumLanes();
481 203232 : for (int j1 = 0; j1 < noLanesEdge1; j1++) {
482 115534 : std::vector<NBEdge::Connection> el1 = (*i11)->getConnectionsFromLane(j1);
483 319435 : for (std::vector<NBEdge::Connection>::iterator i12 = el1.begin(); i12 != el1.end(); ++i12) {
484 203901 : int idx1 = getIndex((*i11), (*i12).toEdge);
485 203901 : if (idx1 < 0) {
486 0 : continue;
487 : }
488 : // go through possibly prohibited
489 829119 : for (EdgeVector::const_iterator i21 = myIncoming.begin(); i21 != myIncoming.end(); i21++) {
490 625218 : int noLanesEdge2 = (*i21)->getNumLanes();
491 1505268 : for (int j2 = 0; j2 < noLanesEdge2; j2++) {
492 880050 : std::vector<NBEdge::Connection> el2 = (*i21)->getConnectionsFromLane(j2);
493 3015209 : for (std::vector<NBEdge::Connection>::iterator i22 = el2.begin(); i22 != el2.end(); i22++) {
494 2135159 : int idx2 = getIndex((*i21), (*i22).toEdge);
495 2135159 : if (idx2 < 0) {
496 0 : continue;
497 : }
498 : // check
499 : // same incoming connections do not prohibit each other
500 2135159 : if ((*i11) == (*i21)) {
501 640403 : myForbids[idx1][idx2] = false;
502 640403 : myForbids[idx2][idx1] = false;
503 : #ifdef DEBUG_SETBLOCKING
504 : if (DEBUGCOND) std::cout << "resetSignalised both"
505 : << " 1:" << (*i11)->getID() << "->" << (*i12).toEdge->getID()
506 : << " 2:" << (*i21)->getID() << "->" << (*i22).toEdge->getID()
507 : << "\n";
508 : #endif
509 640403 : continue;
510 : }
511 : // check other
512 : // if both are non-signalised or both are signalised
513 1262708 : if (((*i12).tlID == "" && (*i22).tlID == "")
514 1495990 : ||
515 232048 : ((*i12).tlID != "" && (*i22).tlID != "")) {
516 : // do nothing
517 1492288 : continue;
518 : }
519 : // supposing, we don not have to
520 : // brake if we are no foes
521 2468 : if (!foes(*i11, (*i12).toEdge, *i21, (*i22).toEdge)) {
522 1930 : continue;
523 : }
524 : // otherwise:
525 : // the non-signalised must break
526 538 : if ((*i12).tlID != "") {
527 269 : myForbids[idx1][idx2] = true;
528 269 : myForbids[idx2][idx1] = false;
529 : #ifdef DEBUG_SETBLOCKING
530 : if (DEBUGCOND) std::cout << "resetSignalised:2 yields"
531 : << " 1:" << (*i11)->getID() << "->" << (*i12).toEdge->getID()
532 : << " 2:" << (*i21)->getID() << "->" << (*i22).toEdge->getID() << "\n";
533 : #endif
534 : } else {
535 269 : myForbids[idx1][idx2] = false;
536 269 : myForbids[idx2][idx1] = true;
537 : #ifdef DEBUG_SETBLOCKING
538 : if (DEBUGCOND) std::cout << "resetSignalised:1 yields"
539 : << " 1:" << (*i11)->getID() << "->" << (*i12).toEdge->getID()
540 : << " 2:" << (*i21)->getID() << "->" << (*i22).toEdge->getID() << "\n";
541 : #endif
542 : }
543 : }
544 880050 : }
545 : }
546 : }
547 115534 : }
548 : }
549 42632 : }
550 :
551 :
552 : std::pair<int, int>
553 49522 : NBRequest::getSizes() const {
554 : int numLanes = 0;
555 : int numLinks = 0;
556 148369 : for (const NBEdge* const e : myIncoming) {
557 : const int numLanesEdge = e->getNumLanes();
558 227345 : for (int j = 0; j < numLanesEdge; j++) {
559 128498 : int numConnections = (int)e->getConnectionsFromLane(j).size();
560 128498 : numLinks += numConnections;
561 128498 : if (numConnections > 0) {
562 108277 : numLanes++;
563 : }
564 : }
565 : }
566 49522 : return std::make_pair(numLanes, numLinks);
567 : }
568 :
569 :
570 : bool
571 3686956 : NBRequest::foes(const NBEdge* const from1, const NBEdge* const to1,
572 : const NBEdge* const from2, const NBEdge* const to2) const {
573 : // unconnected edges do not forbid other edges
574 3686956 : if (to1 == nullptr || to2 == nullptr) {
575 : return false;
576 : }
577 : // get the indices
578 3686956 : int idx1 = getIndex(from1, to1);
579 3686956 : int idx2 = getIndex(from2, to2);
580 3686956 : if (idx1 < 0 || idx2 < 0) {
581 : return false; // sure? (The connection does not exist within this junction)
582 : }
583 : assert(idx1 < (int)(myIncoming.size() * myOutgoing.size()));
584 : assert(idx2 < (int)(myIncoming.size()*myOutgoing.size()));
585 3531440 : return myForbids[idx1][idx2] || myForbids[idx2][idx1];
586 : }
587 :
588 :
589 : bool
590 1460006 : NBRequest::forbids(const NBEdge* const possProhibitorFrom, const NBEdge* const possProhibitorTo,
591 : const NBEdge* const possProhibitedFrom, const NBEdge* const possProhibitedTo,
592 : bool regardNonSignalisedLowerPriority) const {
593 : // unconnected edges do not forbid other edges
594 1460006 : if (possProhibitorTo == nullptr || possProhibitedTo == nullptr) {
595 : return false;
596 : }
597 : // get the indices
598 1460006 : int possProhibitorIdx = getIndex(possProhibitorFrom, possProhibitorTo);
599 1460006 : int possProhibitedIdx = getIndex(possProhibitedFrom, possProhibitedTo);
600 1460006 : if (possProhibitorIdx < 0 || possProhibitedIdx < 0) {
601 : return false; // sure? (The connection does not exist within this junction)
602 : }
603 : assert(possProhibitorIdx < (int)(myIncoming.size() * myOutgoing.size()));
604 : assert(possProhibitedIdx < (int)(myIncoming.size() * myOutgoing.size()));
605 : // check simple right-of-way-rules
606 1460006 : if (!regardNonSignalisedLowerPriority) {
607 589321 : return myForbids[possProhibitorIdx][possProhibitedIdx];
608 : }
609 : // if its not forbidden, report
610 870685 : if (!myForbids[possProhibitorIdx][possProhibitedIdx]) {
611 : return false;
612 : }
613 : // do not forbid a signalised stream by a non-signalised
614 157182 : if (!possProhibitorFrom->hasSignalisedConnectionTo(possProhibitorTo)) {
615 : return false;
616 : }
617 : return true;
618 : }
619 :
620 : int
621 115534 : NBRequest::computeLaneResponse(NBEdge* from, int fromLane, int pos, const bool checkLaneFoes) {
622 319435 : for (const NBEdge::Connection& c : from->getConnectionsFromLane(fromLane)) {
623 : assert(c.toEdge != 0);
624 203901 : pos++;
625 203901 : const std::string foes = getFoesString(from, c, checkLaneFoes);
626 203901 : const std::string response = getResponseString(from, c, checkLaneFoes);
627 203901 : myFoes.push_back(foes);
628 203901 : myResponse.push_back(response);
629 203901 : myHaveVia.push_back(c.haveVia);
630 115534 : }
631 115534 : return pos;
632 : }
633 :
634 :
635 : int
636 1613 : NBRequest::computeCrossingResponse(const NBNode::Crossing& crossing, int pos) {
637 3226 : std::string foes(myJunction->getCrossings().size(), '0');
638 3226 : std::string response(myJunction->getCrossings().size(), '0');
639 : // conflicts with normal connections
640 7936 : for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin(); i != myIncoming.rend(); i++) {
641 6323 : const NBEdge* from = *i;
642 20610 : for (int j = from->getNumLanes(); j-- > 0;) {
643 14287 : const std::vector<NBEdge::Connection>& connected = from->getConnectionsFromLane(j);
644 14287 : const int size = (int) connected.size();
645 32553 : for (int k = size; k-- > 0;) {
646 18266 : const NBEdge* to = connected[k].toEdge;
647 : bool foe = false;
648 38283 : for (const NBEdge* const e : crossing.edges) {
649 28050 : if (e == from || e == to) {
650 : foe = true;
651 : break;
652 : }
653 : }
654 18266 : foes += foe ? '1' : '0';
655 18266 : response += mustBrakeForCrossing(myJunction, from, to, crossing) || !foe ? '0' : '1';
656 : }
657 14287 : }
658 : }
659 1613 : pos++;
660 1613 : myResponse.push_back(response);
661 1613 : myFoes.push_back(foes);
662 1613 : myHaveVia.push_back(false);
663 1613 : return pos;
664 : }
665 :
666 :
667 : std::string
668 203901 : NBRequest::getResponseString(const NBEdge* const from, const NBEdge::Connection& c, const bool checkLaneFoes) const {
669 203901 : const NBEdge* const to = c.toEdge;
670 203901 : const int fromLane = c.fromLane;
671 203901 : const int toLane = c.toLane;
672 : int idx = 0;
673 203901 : if (to != nullptr) {
674 203901 : idx = getIndex(from, to);
675 : }
676 : std::string result;
677 203901 : const bool zipper = myJunction->getType() == SumoXMLNodeType::ZIPPER;
678 : // crossings
679 203901 : auto crossings = myJunction->getCrossings();
680 222167 : for (std::vector<NBNode::Crossing*>::const_reverse_iterator i = crossings.rbegin(); i != crossings.rend(); i++) {
681 18266 : result += mustBrakeForCrossing(myJunction, from, to, **i) ? '1' : '0';
682 : }
683 : // normal connections
684 829119 : for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin(); i != myIncoming.rend(); i++) {
685 : //const std::vector<NBEdge::Connection> &allConnections = (*i)->getConnections();
686 625218 : int noLanes = (*i)->getNumLanes();
687 1505268 : for (int j = noLanes; j-- > 0;) {
688 880050 : std::vector<NBEdge::Connection> connected = (*i)->getConnectionsFromLane(j);
689 880050 : int size = (int) connected.size();
690 3015209 : for (int k = size; k-- > 0;) {
691 2135159 : if (c.mayDefinitelyPass) {
692 : result += '0';
693 : #ifdef DEBUG_RESPONSE
694 : if (DEBUGCOND) {
695 : std::cout << " c=" << c.getDescription(from) << " pass\n";
696 : }
697 : #endif
698 2135038 : } else if ((*i) == from && fromLane == j) {
699 : // do not prohibit a connection by others from same lane
700 : // except for indirect turns
701 : #ifdef DEBUG_RESPONSE
702 : if (DEBUGCOND) {
703 : std::cout << " c=" << c.getDescription(from) << " prohibitC=" << connected[k].getDescription(*i)
704 : << " itc=" << indirectLeftTurnConflict(from, c, *i, connected[k], false)
705 : << "\n";
706 : }
707 : #endif
708 515246 : if (indirectLeftTurnConflict(from, c, *i, connected[k], false)) {
709 : result += '1';
710 : } else {
711 : result += '0';
712 : }
713 : } else {
714 : assert(connected[k].toEdge != 0);
715 1619792 : const int idx2 = getIndex(*i, connected[k].toEdge);
716 : assert(k < (int) connected.size());
717 : assert(idx < (int)(myIncoming.size() * myOutgoing.size()));
718 : assert(idx2 < (int)(myIncoming.size() * myOutgoing.size()));
719 : // check whether the connection is prohibited by another one
720 : #ifdef DEBUG_RESPONSE
721 : if (DEBUGCOND) {
722 : std::cout << " c=" << c.getDescription(from) << " prohibitC=" << connected[k].getDescription(*i)
723 : << " idx=" << idx << " idx2=" << idx2
724 : << " f=" << myForbids[idx2][idx]
725 : << " clf=" << checkLaneFoes
726 : << " clfbc=" << checkLaneFoesByClass(c, *i, connected[k])
727 : << " clfbcoop=" << checkLaneFoesByCooperation(from, c, *i, connected[k])
728 : << " lc=" << laneConflict(from, to, toLane, *i, connected[k].toEdge, connected[k].toLane)
729 : << " rtc=" << NBNode::rightTurnConflict(from, to, fromLane, *i, connected[k].toEdge, connected[k].fromLane)
730 : << " rtc2=" << rightTurnConflict(from, c, *i, connected[k])
731 : << " mc=" << mergeConflict(from, c, *i, connected[k], false)
732 : << " oltc=" << oppositeLeftTurnConflict(from, c, *i, connected[k], false)
733 : << " itc=" << indirectLeftTurnConflict(from, c, *i, connected[k], zipper)
734 : << " bc=" << bidiConflict(from, c, *i, connected[k], false)
735 : << " ec=" << (myJunction->extraConflict(c.tlLinkIndex, connected[k].tlLinkIndex) && (myForbids[idx2][idx] || myForbids[idx][idx2]))
736 : << " tlscc=" << myJunction->tlsStrandedConflict(from, c, *i, connected[k])
737 : << "\n";
738 : }
739 : #endif
740 3194418 : const bool hasLaneConflict = (!(checkLaneFoes || checkLaneFoesByClass(c, *i, connected[k])
741 1584926 : || checkLaneFoesByCooperation(from, c, *i, connected[k]))
742 1661087 : || laneConflict(from, to, toLane, *i, connected[k].toEdge, connected[k].toLane));
743 3239584 : if (((myForbids[idx2][idx] || (zipper && myForbids[idx][idx2])) && hasLaneConflict && !bidiConflict(*i, connected[k], from, c, false))
744 1289258 : || rightTurnConflict(from, c, *i, connected[k])
745 1288657 : || mergeConflict(from, c, *i, connected[k], zipper)
746 1288453 : || oppositeLeftTurnConflict(from, c, *i, connected[k], zipper)
747 1285796 : || indirectLeftTurnConflict(from, c, *i, connected[k], zipper)
748 1285796 : || bidiConflict(from, c, *i, connected[k], false)
749 : // the extra conflict could be specific to another connection within the same signal group
750 1285821 : || (myJunction->extraConflict(c.tlLinkIndex, connected[k].tlLinkIndex) && (myForbids[idx2][idx] || myForbids[idx][idx2]))
751 2905532 : || (myJunction->tlsStrandedConflict(from, c, *i, connected[k])
752 8382 : && laneConflict(from, to, toLane, *i, connected[k].toEdge, connected[k].toLane)
753 1633366 : && !OptionsCont::getOptions().getBool("tls.ignore-internal-junction-jam"))
754 : ) {
755 : result += '1';
756 : } else {
757 : result += '0';
758 : }
759 : }
760 : }
761 880050 : }
762 : }
763 203901 : return result;
764 203901 : }
765 :
766 :
767 : std::string
768 203901 : NBRequest::getFoesString(NBEdge* from, const NBEdge::Connection& c, const bool checkLaneFoes) const {
769 407802 : const bool lefthand = OptionsCont::getOptions().getBool("lefthand");
770 : // remember the case when the lane is a "dead end" in the meaning that
771 : // vehicles must choose another lane to move over the following
772 : // junction
773 : // !!! move to forbidden
774 : std::string result;
775 : // crossings
776 203901 : auto crossings = myJunction->getCrossings();
777 222167 : for (std::vector<NBNode::Crossing*>::const_reverse_iterator i = crossings.rbegin(); i != crossings.rend(); i++) {
778 : bool foes = false;
779 38283 : for (EdgeVector::const_iterator it_e = (**i).edges.begin(); it_e != (**i).edges.end(); ++it_e) {
780 28050 : if ((*it_e) == from || (*it_e) == c.toEdge) {
781 : foes = true;
782 : break;
783 : }
784 : }
785 18266 : result += foes ? '1' : '0';
786 : }
787 : // normal connections
788 829119 : for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin(); i != myIncoming.rend(); i++) {
789 1505268 : for (int j = (*i)->getNumLanes() - 1; j >= 0; --j) {
790 880050 : const std::vector<NBEdge::Connection>& connected = (*i)->getConnectionsFromLane(j);
791 880050 : int size = (int) connected.size();
792 3015209 : for (int k = size; k-- > 0;) {
793 4209563 : const bool hasLaneConflict = (!(checkLaneFoes || checkLaneFoesByClass(c, *i, connected[k])
794 2088238 : || checkLaneFoesByCooperation(from, c, *i, connected[k]))
795 2185001 : || laneConflict(from, c.toEdge, c.toLane, *i, connected[k].toEdge, connected[k].toLane));
796 2817357 : if ((foes(from, c.toEdge, (*i), connected[k].toEdge) && hasLaneConflict)
797 1474344 : || rightTurnConflict(from, c, *i, connected[k])
798 1473743 : || myJunction->turnFoes(from, c.toEdge, c.fromLane, *i, connected[k].toEdge, connected[k].fromLane, lefthand)
799 1473076 : || mergeConflict(from, c, *i, connected[k], true)
800 1472680 : || oppositeLeftTurnConflict(from, c, *i, connected[k], true)
801 1467365 : || indirectLeftTurnConflict(from, c, *i, connected[k], true)
802 3602502 : || bidiConflict(from, c, *i, connected[k], true)
803 : ) {
804 : result += '1';
805 : } else {
806 : result += '0';
807 : }
808 : }
809 880050 : }
810 : }
811 203901 : return result;
812 203901 : }
813 :
814 :
815 : bool
816 2764166 : NBRequest::rightTurnConflict(const NBEdge* from, const NBEdge::Connection& con,
817 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon) const {
818 5528217 : return (!con.mayDefinitelyPass &&
819 2764051 : (NBNode::rightTurnConflict(from, con.toEdge, con.fromLane, prohibitorFrom, prohibitorCon.toEdge, prohibitorCon.fromLane)
820 : // reverse conflicht (override)
821 2762820 : || (prohibitorCon.mayDefinitelyPass &&
822 72 : NBNode::rightTurnConflict(prohibitorFrom, prohibitorCon.toEdge, prohibitorCon.fromLane, from, con.toEdge, con.fromLane))));
823 :
824 :
825 : }
826 :
827 :
828 : bool
829 4241560 : NBRequest::mergeConflict(const NBEdge* from, const NBEdge::Connection& con,
830 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon, bool foes) const {
831 : if (from == prohibitorFrom
832 1189296 : && con.toEdge == prohibitorCon.toEdge
833 4688018 : && ((con.toLane == prohibitorCon.toLane
834 326698 : && con.fromLane != prohibitorCon.fromLane
835 1461 : && !myJunction->isConstantWidthTransition())
836 : // this is actually a crossing rather than a merger
837 445001 : || (con.fromLane > prohibitorCon.fromLane && con.toLane < prohibitorCon.toLane)
838 444993 : || (con.fromLane < prohibitorCon.fromLane && con.toLane > prohibitorCon.toLane))) {
839 1473 : if (foes) {
840 : return true;
841 : }
842 881 : if (prohibitorCon.mayDefinitelyPass) {
843 : return true;
844 : }
845 878 : if (con.mayDefinitelyPass) {
846 : return false;
847 : }
848 878 : const bool bike = from->getPermissions(con.fromLane) == SVC_BICYCLE;
849 878 : const bool prohibitorBike = prohibitorFrom->getPermissions(prohibitorCon.fromLane) == SVC_BICYCLE;
850 878 : if (myOutgoing.size() == 1) {
851 : // at on-ramp like situations, right lane should yield
852 51 : return bike || (con.fromLane < prohibitorCon.fromLane && !prohibitorBike);
853 : } else {
854 : // priority depends on direction:
855 : // for right turns the rightmost lane gets priority
856 : // otherwise the left lane
857 844 : LinkDirection dir = myJunction->getDirection(from, con.toEdge);
858 844 : if (dir == LinkDirection::RIGHT || dir == LinkDirection::PARTRIGHT) {
859 533 : return con.fromLane > prohibitorCon.fromLane;
860 : } else {
861 311 : if (myIncoming.size() == 1) {
862 : // at off-ramp like situations, right lane should pass unless it's a bicycle lane
863 6 : return bike || (con.fromLane > prohibitorCon.fromLane && !prohibitorBike);
864 : } else {
865 307 : return con.fromLane < prohibitorCon.fromLane;
866 : }
867 : }
868 : }
869 :
870 : } else {
871 4240087 : return false;
872 : }
873 : }
874 :
875 :
876 : bool
877 2761133 : NBRequest::oppositeLeftTurnConflict(const NBEdge* from, const NBEdge::Connection& con,
878 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon, bool foes) const {
879 2761133 : LinkDirection dir = myJunction->getDirection(from, con.toEdge);
880 : // XXX lefthand issue (solve via #4256)
881 2761133 : if (dir != LinkDirection::LEFT && dir != LinkDirection::PARTLEFT) {
882 : return false;
883 : }
884 563089 : dir = myJunction->getDirection(prohibitorFrom, prohibitorCon.toEdge);
885 563089 : if (dir != LinkDirection::LEFT && dir != LinkDirection::PARTLEFT) {
886 : return false;
887 : }
888 155656 : if (from == prohibitorFrom || NBRequest::foes(from, con.toEdge, prohibitorFrom, prohibitorCon.toEdge)) {
889 : // not an opposite pair
890 87564 : return false;
891 : }
892 :
893 68092 : const double width1 = MIN2(from->getLaneWidth(con.fromLane) / 2, OptionsCont::getOptions().getFloat("internal-junctions.vehicle-width") / 2);
894 68092 : const double width2 = prohibitorCon.toEdge->getLaneWidth(prohibitorCon.toLane) / 2;
895 : PositionVector shape = con.shape;
896 68092 : shape.append(con.viaShape);
897 : PositionVector otherShape = prohibitorCon.shape;
898 68092 : otherShape.append(prohibitorCon.viaShape);
899 68092 : if (shape.size() == 0 || otherShape.size() == 0) {
900 : // no internal lanes built
901 : return false;
902 : }
903 21980 : const double minDV = NBEdge::firstIntersection(shape, otherShape, width1, width2);
904 21980 : if (minDV < shape.length() - POSITION_EPS && minDV > POSITION_EPS) {
905 : // break symmetry using edge id
906 10630 : return foes || from->getID() < prohibitorFrom->getID();
907 : }
908 : return false;
909 68092 : }
910 :
911 : bool
912 3704642 : NBRequest::indirectLeftTurnConflict(const NBEdge* from, const NBEdge::Connection& con,
913 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon, bool foes) const {
914 3704642 : if (from == prohibitorFrom) {
915 1401831 : if (con.toEdge == prohibitorCon.toEdge) {
916 : return false;
917 838607 : } else if (con.indirectLeft) {
918 126 : LinkDirection dir = myJunction->getDirection(prohibitorFrom, prohibitorCon.toEdge);
919 126 : return (dir == LinkDirection::STRAIGHT);
920 838481 : } else if (foes && prohibitorCon.indirectLeft) {
921 27 : LinkDirection dir = myJunction->getDirection(from, con.toEdge);
922 27 : return (dir == LinkDirection::STRAIGHT);
923 : }
924 : }
925 : return false;
926 : }
927 :
928 : bool
929 3821634 : NBRequest::bidiConflict(const NBEdge* from, const NBEdge::Connection& con,
930 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon, bool foes) const {
931 3821634 : if (from == prohibitorFrom) {
932 : return false;
933 : }
934 2847753 : if (isRailway(from->getPermissions())) {
935 : // railways manage right-of-way via signals
936 : return false;
937 : }
938 1345411 : if ((foes && (from->getBidiEdge() == prohibitorCon.toEdge))
939 4166769 : || prohibitorFrom->getBidiEdge() == con.toEdge) {
940 1044 : const bool fromBidi = from->getLaneShape(con.fromLane).reverse().almostSame(
941 522 : prohibitorCon.toEdge->getLaneShape(prohibitorCon.toLane), POSITION_EPS);
942 1044 : const bool prohibitorFromBidi = prohibitorFrom->getLaneShape(prohibitorCon.fromLane).reverse().almostSame(
943 522 : con.toEdge->getLaneShape(con.toLane), POSITION_EPS);
944 522 : if (!foes && fromBidi && prohibitorFromBidi) {
945 : // do not create a symmetrical conflict
946 : return false;
947 : }
948 506 : if (prohibitorFromBidi &&
949 613 : prohibitorFrom->getLaneShape(prohibitorCon.fromLane).reverse().almostSame(
950 107 : prohibitorCon.toEdge->getLaneShape(prohibitorCon.toLane), POSITION_EPS)) {
951 : // prohibitor has a bidi-turnaround
952 : return false;
953 : }
954 :
955 461 : return fromBidi || prohibitorFromBidi;
956 : }
957 : return false;
958 : }
959 :
960 : bool
961 3730817 : NBRequest::checkLaneFoesByClass(const NBEdge::Connection& con,
962 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon) const {
963 3730817 : if (con.toEdge != prohibitorCon.toEdge) {
964 : return false;
965 : }
966 1059125 : SVCPermissions svc = con.toEdge->getPermissions(con.toLane);
967 1059125 : SVCPermissions svc2 = prohibitorFrom->getPermissions(prohibitorCon.fromLane) & prohibitorCon.toEdge->getPermissions(prohibitorCon.toLane);
968 : // check for lane level conflict if the only common classes are bicycles or pedestrians
969 1059125 : return ((svc & svc2 & ~(SVC_BICYCLE | SVC_PEDESTRIAN)) == 0
970 : // or if the connection is to a dedicated lane whereas the prohibitor is a "general" lane
971 1059125 : || (((svc & SVC_PASSENGER) == 0) && ((svc2 & SVC_PASSENGER) != 0)));
972 : }
973 :
974 :
975 : bool
976 3673164 : NBRequest::checkLaneFoesByCooperation(const NBEdge* from, const NBEdge::Connection& con,
977 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon) const {
978 3673164 : if (con.toEdge != prohibitorCon.toEdge) {
979 : return false;
980 : }
981 : // if from and prohibitorFrom target distinct lanes for all their
982 : // connections to the common target edge, cooperation is possible
983 : // (and should always happen unless the connections cross for some byzantine reason)
984 :
985 : std::set<int> fromTargetLanes;
986 4873334 : for (const NBEdge::Connection& c : from->getConnections()) {
987 3871862 : if (c.toEdge == con.toEdge) {
988 1455361 : fromTargetLanes.insert(c.toLane);
989 : }
990 : }
991 2368071 : for (const NBEdge::Connection& c : prohibitorFrom->getConnections()) {
992 2334587 : if (c.toEdge == con.toEdge && fromTargetLanes.count(c.toLane) != 0) {
993 : //std::cout << " con=" << con->getDescription(from) << " foe=" << prohibitorCon.getDescription(prohibitorFrom)
994 : // << " no cooperation (targets=" << joinToString(fromTargetLanes, ' ') << " index=" << c.toLane << "\n";
995 : return false;
996 : }
997 : }
998 : return true;
999 : }
1000 :
1001 :
1002 : bool
1003 123653 : NBRequest::laneConflict(const NBEdge* from, const NBEdge* to, int toLane,
1004 : const NBEdge* prohibitorFrom, const NBEdge* prohibitorTo, int prohibitorToLane) const {
1005 123653 : if (to != prohibitorTo) {
1006 : return true;
1007 : }
1008 : // since we know that the edge2edge connections are in conflict, the only
1009 : // situation in which the lane2lane connections can be conflict-free is, if
1010 : // they target the same edge but do not cross each other
1011 106655 : double angle = NBHelpers::relAngle(
1012 : from->getAngleAtNode(from->getToNode()), to->getAngleAtNode(to->getFromNode()));
1013 106655 : if (angle == 180) {
1014 : angle = -180; // turnarounds are left turns
1015 : }
1016 106655 : const double prohibitorAngle = NBHelpers::relAngle(
1017 : prohibitorFrom->getAngleAtNode(prohibitorFrom->getToNode()), to->getAngleAtNode(to->getFromNode()));
1018 106655 : const bool rightOfProhibitor = prohibitorFrom->isTurningDirectionAt(to)
1019 106655 : || (angle > prohibitorAngle && !from->isTurningDirectionAt(to));
1020 106655 : return rightOfProhibitor ? toLane >= prohibitorToLane : toLane <= prohibitorToLane;
1021 : }
1022 :
1023 : int
1024 16755521 : NBRequest::getIndex(const NBEdge* const from, const NBEdge* const to) const {
1025 16755521 : EdgeVector::const_iterator fp = std::find(myIncoming.begin(), myIncoming.end(), from);
1026 16755521 : EdgeVector::const_iterator tp = std::find(myOutgoing.begin(), myOutgoing.end(), to);
1027 16755521 : if (fp == myIncoming.end() || tp == myOutgoing.end()) {
1028 : return -1;
1029 : }
1030 : // compute the index
1031 16600005 : return (int)(distance(myIncoming.begin(), fp) * myOutgoing.size() + distance(myOutgoing.begin(), tp));
1032 : }
1033 :
1034 :
1035 : std::ostream&
1036 0 : operator<<(std::ostream& os, const NBRequest& r) {
1037 0 : int variations = r.numLinks();
1038 0 : for (int i = 0; i < variations; i++) {
1039 0 : os << i << ' ';
1040 0 : for (int j = 0; j < variations; j++) {
1041 0 : if (r.myForbids[i][j]) {
1042 0 : os << '1';
1043 : } else {
1044 0 : os << '0';
1045 : }
1046 : }
1047 : os << std::endl;
1048 : }
1049 : os << std::endl;
1050 0 : return os;
1051 : }
1052 :
1053 :
1054 : bool
1055 228767 : NBRequest::mustBrake(const NBEdge* const from, const NBEdge* const to, int fromLane, int toLane, bool includePedCrossings) const {
1056 228767 : NBEdge::Connection con(fromLane, const_cast<NBEdge*>(to), toLane);
1057 228767 : const int linkIndex = myJunction->getConnectionIndex(from, con);
1058 228767 : if (linkIndex >= 0 && (int)myResponse.size() > linkIndex) {
1059 206926 : std::string response = getResponse(linkIndex);
1060 206926 : if (!includePedCrossings) {
1061 304 : response = response.substr(0, response.size() - myJunction->getCrossings().size());
1062 : }
1063 206926 : if (response.find_first_of("1") == std::string::npos) {
1064 : return false;
1065 100052 : } else if (!myJunction->isTLControlled()) {
1066 : return true;
1067 : }
1068 : // if the link must respond it could also be due to a tlsConflict. This
1069 : // must not carry over the off-state response so we continue with
1070 : // the regular check
1071 : }
1072 : // get the indices
1073 36333 : int idx2 = getIndex(from, to);
1074 36333 : if (idx2 == -1) {
1075 : return false;
1076 : }
1077 : // go through all (existing) connections;
1078 : // check whether any of these forbids the one to determine
1079 : assert(idx2 < (int)(myIncoming.size()*myOutgoing.size()));
1080 239665 : for (int idx1 = 0; idx1 < numLinks(); idx1++) {
1081 : //assert(myDone[idx1][idx2]);
1082 330867 : if (myDone[idx1][idx2] && myForbids[idx1][idx2]) {
1083 : return true;
1084 : }
1085 : }
1086 : // maybe we need to brake for a pedestrian crossing
1087 2700 : if (includePedCrossings) {
1088 2306 : auto crossings = myJunction->getCrossings();
1089 2976 : for (std::vector<NBNode::Crossing*>::const_reverse_iterator i = crossings.rbegin(); i != crossings.rend(); i++) {
1090 1488 : if (mustBrakeForCrossing(myJunction, from, to, **i)) {
1091 : return true;
1092 : }
1093 : }
1094 2306 : }
1095 : // maybe we need to brake due to a right-turn conflict with straight-going
1096 : // bicycles
1097 1882 : const NBEdge::Connection& queryCon = from->getConnection(fromLane, to, toLane);
1098 1882 : LinkDirection dir = myJunction->getDirection(from, to);
1099 1882 : if (dir == LinkDirection::RIGHT || dir == LinkDirection::PARTRIGHT) {
1100 631 : for (const NBEdge::Connection& fromCon : from->getConnections()) {
1101 564 : if (rightTurnConflict(from, queryCon, from, fromCon)) {
1102 : return true;
1103 : }
1104 : }
1105 : }
1106 : // maybe we need to brake due to a merge conflict
1107 9397 : for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin(); i != myIncoming.rend(); i++) {
1108 7635 : int noLanes = (*i)->getNumLanes();
1109 22428 : for (int j = noLanes; j-- > 0;) {
1110 14806 : std::vector<NBEdge::Connection> connected = (*i)->getConnectionsFromLane(j);
1111 14806 : const int size = (int) connected.size();
1112 46273 : for (int k = size; k-- > 0;) {
1113 39496 : if ((*i) == from && fromLane != j
1114 35093 : && mergeConflict(from, queryCon, *i, connected[k], myJunction->getType() == SumoXMLNodeType::ZIPPER)) {
1115 : return true;
1116 : }
1117 : }
1118 14806 : }
1119 : }
1120 : // maybe we need to brake due to a zipper conflict
1121 1762 : if (myJunction->getType() == SumoXMLNodeType::ZIPPER) {
1122 0 : for (int idx1 = 0; idx1 < numLinks(); idx1++) {
1123 : //assert(myDone[idx1][idx2]);
1124 0 : if (myDone[idx1][idx2] && myForbids[idx2][idx1]) {
1125 : return true;
1126 : }
1127 : }
1128 : }
1129 : return false;
1130 228767 : }
1131 :
1132 :
1133 : bool
1134 44546 : NBRequest::mustBrakeForCrossing(const NBNode* node, const NBEdge* const from, const NBEdge* const to, const NBNode::Crossing& crossing) {
1135 44546 : const LinkDirection dir = node->getDirection(from, to);
1136 44546 : const bool mustYield = dir == LinkDirection::LEFT || dir == LinkDirection::RIGHT;
1137 44546 : if (crossing.priority || mustYield) {
1138 77424 : for (const NBEdge* const e : crossing.edges) {
1139 : // left and right turns must yield to unprioritized crossings only on their destination edge
1140 53777 : if ((e == from && crossing.priority) || e == to) {
1141 : return true;
1142 : }
1143 : }
1144 : }
1145 : return false;
1146 : }
1147 :
1148 :
1149 : bool
1150 0 : NBRequest::mustBrake(const NBEdge* const possProhibitorFrom, const NBEdge* const possProhibitorTo,
1151 : const NBEdge* const possProhibitedFrom, const NBEdge* const possProhibitedTo) const {
1152 : // get the indices
1153 0 : int idx1 = getIndex(possProhibitorFrom, possProhibitorTo);
1154 0 : int idx2 = getIndex(possProhibitedFrom, possProhibitedTo);
1155 0 : return (myForbids[idx2][idx1]);
1156 : }
1157 :
1158 :
1159 : void
1160 1840 : NBRequest::reportWarnings() {
1161 : // check if any errors occurred on build the link prohibitions
1162 1840 : if (myNotBuild != 0) {
1163 0 : WRITE_WARNING(toString(myNotBuild) + " of " + toString(myNotBuild + myGoodBuilds) + " prohibitions were not build.");
1164 : }
1165 1840 : }
1166 :
1167 :
1168 : void
1169 42632 : NBRequest::resetCooperating() {
1170 : // map from edge to number of incoming connections
1171 : std::map<const NBEdge*, int> incomingCount; // initialized to 0
1172 : // map from edge to indices of approached lanes
1173 : std::map<const NBEdge*, std::set<int> > approachedLanes;
1174 : // map from edge to list of incoming edges
1175 : std::map<const NBEdge*, std::vector<const NBEdge*> > incomingEdges;
1176 130330 : for (const NBEdge* const e : myIncoming) {
1177 291599 : for (const NBEdge::Connection& con : e->getConnections()) {
1178 203901 : incomingCount[con.toEdge]++;
1179 203901 : approachedLanes[con.toEdge].insert(con.toLane);
1180 203901 : incomingEdges[con.toEdge].push_back(e);
1181 : }
1182 : }
1183 128159 : for (std::map<const NBEdge*, int>::iterator it = incomingCount.begin(); it != incomingCount.end(); ++it) {
1184 85527 : const NBEdge* const to = it->first;
1185 : // we cannot test against to->getNumLanes() since not all lanes may be used
1186 85527 : if ((int)approachedLanes[to].size() >= it->second) {
1187 36279 : const std::vector<const NBEdge*>& incoming = incomingEdges[to];
1188 : // make these connections mutually unconflicting
1189 83042 : for (const NBEdge* const e1 : incoming) {
1190 125948 : for (const NBEdge* const e2 : incoming) {
1191 79185 : myForbids[getIndex(e1, to)][getIndex(e2, to)] = false;
1192 : #ifdef DEBUG_SETBLOCKING
1193 : if (DEBUGCOND) std::cout << "resetCooperating"
1194 : << " 1:" << e1->getID() << "->" << to->getID()
1195 : << " 2:" << e2->getID() << "->" << to->getID()
1196 : << "\n";
1197 : #endif
1198 : }
1199 : }
1200 : }
1201 : }
1202 42632 : }
1203 :
1204 :
1205 : bool
1206 42814 : NBRequest::hasConflict() const {
1207 84344 : for (int i = 0; i < (int)myFoes.size(); i++) {
1208 61426 : if (hasConflictAtLink(i)) {
1209 : return true;
1210 : }
1211 : }
1212 : return false;
1213 : }
1214 :
1215 : bool
1216 62645 : NBRequest::hasConflictAtLink(int linkIndex) const {
1217 62645 : return myFoes[linkIndex].find_first_of("1") != std::string::npos;
1218 : }
1219 :
1220 : int
1221 288741 : NBRequest::numLinks() const {
1222 288741 : return (int)(myIncoming.size() * myOutgoing.size() + myJunction->getCrossings().size());
1223 : }
1224 :
1225 :
1226 : /****************************************************************************/
|
