Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2024 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 60898 : NBRequest::NBRequest(const NBEdgeCont& ec,
57 : NBNode* junction,
58 : const EdgeVector& all,
59 : const EdgeVector& incoming,
60 : const EdgeVector& outgoing,
61 60898 : const NBConnectionProhibits& loadedProhibits) :
62 60898 : myJunction(junction),
63 60898 : myAll(all),
64 60898 : myIncoming(incoming),
65 60898 : myOutgoing(outgoing) {
66 60898 : const int variations = numLinks();
67 : // build maps with information which forbidding connection were
68 : // computed and what's in there
69 60898 : myForbids.reserve(variations);
70 60898 : myDone.reserve(variations);
71 368895 : for (int i = 0; i < variations; i++) {
72 307997 : myForbids.push_back(LinkInfoCont(variations, false));
73 615994 : myDone.push_back(LinkInfoCont(variations, false));
74 : }
75 : // insert loaded prohibits
76 61000 : 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 : 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 368895 : for (int s1 = 0; s1 < variations; s1++) {
125 2378098 : for (int s2 = s1 + 1; s2 < variations; s2++) {
126 : // not set, yet
127 2070101 : if (!myDone[s1][s2]) {
128 2069989 : 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 60898 : }
139 :
140 :
141 60898 : NBRequest::~NBRequest() {}
142 :
143 :
144 : void
145 51371 : NBRequest::buildBitfieldLogic() {
146 : EdgeVector::const_iterator i, j;
147 157883 : for (i = myIncoming.begin(); i != myIncoming.end(); i++) {
148 385689 : for (j = myOutgoing.begin(); j != myOutgoing.end(); j++) {
149 279177 : computeRightOutgoingLinkCrossings(*i, *j);
150 279177 : computeLeftOutgoingLinkCrossings(*i, *j);
151 : }
152 : }
153 : // reset signalised/non-signalised dependencies
154 51371 : resetSignalised();
155 : // reset foes it the number of lanes matches (or exceeds) the number of incoming connections
156 51371 : resetCooperating();
157 51371 : }
158 :
159 :
160 : void
161 279177 : NBRequest::computeRightOutgoingLinkCrossings(NBEdge* from, NBEdge* to) {
162 279177 : EdgeVector::const_iterator pfrom = std::find(myAll.begin(), myAll.end(), from);
163 1213410 : while (*pfrom != to) {
164 934233 : NBContHelper::nextCCW(myAll, pfrom);
165 934233 : if ((*pfrom)->getToNode() == myJunction) {
166 328345 : EdgeVector::const_iterator pto = std::find(myAll.begin(), myAll.end(), to);
167 1326679 : while (*pto != from) {
168 998334 : if (!((*pto)->getToNode() == myJunction)) {
169 667428 : setBlocking(from, to, *pfrom, *pto);
170 : }
171 998334 : NBContHelper::nextCCW(myAll, pto);
172 : }
173 : }
174 : }
175 279177 : }
176 :
177 :
178 : void
179 279177 : NBRequest::computeLeftOutgoingLinkCrossings(NBEdge* from, NBEdge* to) {
180 279177 : EdgeVector::const_iterator pfrom = std::find(myAll.begin(), myAll.end(), from);
181 1213410 : while (*pfrom != to) {
182 934233 : NBContHelper::nextCW(myAll, pfrom);
183 934233 : if ((*pfrom)->getToNode() == myJunction) {
184 328345 : EdgeVector::const_iterator pto = std::find(myAll.begin(), myAll.end(), to);
185 1326679 : while (*pto != from) {
186 998334 : if (!((*pto)->getToNode() == myJunction)) {
187 667428 : setBlocking(from, to, *pfrom, *pto);
188 : }
189 998334 : NBContHelper::nextCW(myAll, pto);
190 : }
191 : }
192 : }
193 279177 : }
194 :
195 :
196 : void
197 1334856 : NBRequest::setBlocking(NBEdge* from1, NBEdge* to1,
198 : NBEdge* from2, NBEdge* to2) {
199 : // check whether one of the links has a dead end
200 1334856 : if (to1 == nullptr || to2 == nullptr) {
201 1334856 : return;
202 : }
203 : // get the indices of both links
204 1334856 : int idx1 = getIndex(from1, to1);
205 1334856 : int idx2 = getIndex(from2, to2);
206 1334856 : 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 1334856 : if (myDone[idx1][idx2]) {
212 : return;
213 : }
214 : // mark the crossings as done
215 : myDone[idx1][idx2] = true;
216 : myDone[idx2][idx1] = true;
217 : // special case all-way stop
218 667338 : 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 667298 : if (from1->isTurningDirectionAt(to1)) {
227 : myForbids[idx2][idx1] = true;
228 84075 : return;
229 : }
230 583223 : if (from2->isTurningDirectionAt(to2)) {
231 : myForbids[idx1][idx2] = true;
232 78844 : return;
233 : }
234 : // if there are no connections, there are no prohibitions
235 504379 : if (from1->isConnectedTo(to1)) {
236 303573 : if (!from2->isConnectedTo(to2)) {
237 : myForbids[idx1][idx2] = true;
238 : myForbids[idx2][idx1] = false;
239 37679 : return;
240 : }
241 : } else {
242 200806 : if (!from2->isConnectedTo(to2)) {
243 : myForbids[idx1][idx2] = false;
244 : myForbids[idx2][idx1] = false;
245 160931 : return;
246 : } else {
247 : myForbids[idx1][idx2] = false;
248 : myForbids[idx2][idx1] = true;
249 39875 : 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 265894 : const bool typeEqual = myJunction->getType() == SumoXMLNodeType::RIGHT_BEFORE_LEFT || myJunction->getType() == SumoXMLNodeType::LEFT_BEFORE_RIGHT;
260 : if (!typeEqual) {
261 236387 : int from1p = from1->getJunctionPriority(myJunction);
262 236387 : 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 236387 : if (from1p > from2p) {
271 : myForbids[idx1][idx2] = true;
272 82495 : return;
273 : }
274 153892 : if (from2p > from1p) {
275 : myForbids[idx2][idx1] = true;
276 68563 : return;
277 : }
278 : }
279 : // straight connections prohibit turning connections if the priorities are equal
280 : // (unless the junction is a bent priority junction)
281 114836 : if (!typeEqual && !myJunction->isBentPriority()) {
282 56272 : LinkDirection ld1 = myJunction->getDirection(from1, to1);
283 56272 : LinkDirection ld2 = myJunction->getDirection(from2, to2);
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 56272 : if (ld1 == LinkDirection::STRAIGHT) {
291 14087 : if (ld2 != LinkDirection::STRAIGHT) {
292 : myForbids[idx1][idx2] = true;
293 : myForbids[idx2][idx1] = false;
294 13028 : return;
295 : }
296 : } else {
297 42185 : if (ld2 == LinkDirection::STRAIGHT) {
298 : myForbids[idx1][idx2] = false;
299 : myForbids[idx2][idx1] = true;
300 13581 : 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 :
325 : // compute the yielding due to the right-before-left rule
326 : // (or left-before-right rule)
327 : // get the position of the incoming lanes in the junction-wheel
328 88227 : EdgeVector::const_iterator c1 = std::find(myAll.begin(), myAll.end(), from1);
329 88227 : NBContHelper::nextCW(myAll, c1);
330 : // go through next edges clockwise...
331 270125 : while (*c1 != from1 && *c1 != from2) {
332 213008 : if (*c1 == to2) {
333 : // if we encounter to2 the second one prohibits the first
334 31110 : if (myJunction->getType() == SumoXMLNodeType::LEFT_BEFORE_RIGHT) {
335 : myForbids[idx1][idx2] = true;
336 : } else {
337 : myForbids[idx2][idx1] = true;
338 : }
339 31110 : return;
340 : }
341 181898 : NBContHelper::nextCW(myAll, c1);
342 : }
343 : // get the position of the incoming lanes in the junction-wheel
344 57117 : EdgeVector::const_iterator c2 = std::find(myAll.begin(), myAll.end(), from2);
345 57117 : NBContHelper::nextCW(myAll, c2);
346 : // go through next edges clockwise...
347 185995 : while (*c2 != from2 && *c2 != from1) {
348 185995 : if (*c2 == to1) {
349 : // if we encounter to1 the second one prohibits the first
350 57117 : if (myJunction->getType() == SumoXMLNodeType::LEFT_BEFORE_RIGHT) {
351 : myForbids[idx2][idx1] = true;
352 : } else {
353 : myForbids[idx1][idx2] = true;
354 : }
355 57117 : return;
356 : }
357 128878 : NBContHelper::nextCW(myAll, c2);
358 : }
359 : #ifdef DEBUG_SETBLOCKING
360 : if (DEBUGCOND) std::cout << "setBlocking"
361 : << " 1:" << from1->getID() << "->" << to1->getID()
362 : << " 2:" << from2->getID() << "->" << to2->getID()
363 : << " noDecision\n";
364 : #endif
365 : }
366 :
367 :
368 : int
369 0 : NBRequest::distanceCounterClockwise(NBEdge* from, NBEdge* to) {
370 0 : EdgeVector::const_iterator p = std::find(myAll.begin(), myAll.end(), from);
371 : int ret = 0;
372 : do {
373 0 : ret++;
374 0 : if (p == myAll.begin()) {
375 : p = myAll.end();
376 : }
377 : p--;
378 0 : } while (*p != to);
379 0 : return ret;
380 : }
381 :
382 : const std::string&
383 0 : NBRequest::getFoes(int linkIndex) const {
384 : assert(linkIndex >= 0);
385 : assert(linkIndex < (int)myFoes.size());
386 0 : return myFoes[linkIndex];
387 : }
388 :
389 :
390 : const std::string&
391 252059 : NBRequest::getResponse(int linkIndex) const {
392 : assert(linkIndex >= 0);
393 : assert(linkIndex < (int)myResponse.size());
394 252059 : return myResponse[linkIndex];
395 : }
396 :
397 :
398 : void
399 50087 : NBRequest::writeLogic(OutputDevice& into) const {
400 50087 : int numLinks = (int)myResponse.size();
401 : assert((int)myFoes.size() == numLinks);
402 : assert((int)myHaveVia.size() == numLinks);
403 : const bool padding = numLinks > 10;
404 292117 : for (int i = 0; i < numLinks; i++) {
405 242030 : into.openTag(SUMO_TAG_REQUEST);
406 : into.writeAttr(SUMO_ATTR_INDEX, i);
407 242030 : if (padding && i < 10) {
408 119780 : into.writePadding(" ");
409 : }
410 242030 : into.writeAttr(SUMO_ATTR_RESPONSE, myResponse[i]);
411 242030 : into.writeAttr(SUMO_ATTR_FOES, myFoes[i]);
412 484060 : if (!OptionsCont::getOptions().getBool("no-internal-links")) {
413 232590 : into.writeAttr(SUMO_ATTR_CONT, myHaveVia[i]);
414 : }
415 484060 : into.closeTag();
416 : }
417 50087 : }
418 :
419 :
420 : void
421 51371 : NBRequest::computeLogic(const bool checkLaneFoes) {
422 : myResponse.clear();
423 : myFoes.clear();
424 : myHaveVia.clear();
425 : int pos = 0;
426 : EdgeVector::const_iterator i;
427 : // normal connections
428 157883 : for (i = myIncoming.begin(); i != myIncoming.end(); i++) {
429 106512 : int noLanes = (*i)->getNumLanes();
430 246000 : for (int k = 0; k < noLanes; k++) {
431 139515 : pos = computeLaneResponse(*i, k, pos, checkLaneFoes || myJunction->getType() == SumoXMLNodeType::ZIPPER);
432 : }
433 : }
434 : // crossings
435 51371 : auto crossings = myJunction->getCrossings();
436 53763 : for (auto c : crossings) {
437 2392 : pos = computeCrossingResponse(*c, pos);
438 : }
439 51371 : }
440 :
441 : void
442 51371 : NBRequest::resetSignalised() {
443 : // go through possible prohibitions
444 157883 : for (EdgeVector::const_iterator i11 = myIncoming.begin(); i11 != myIncoming.end(); i11++) {
445 106512 : int noLanesEdge1 = (*i11)->getNumLanes();
446 246000 : for (int j1 = 0; j1 < noLanesEdge1; j1++) {
447 139488 : std::vector<NBEdge::Connection> el1 = (*i11)->getConnectionsFromLane(j1);
448 387947 : for (std::vector<NBEdge::Connection>::iterator i12 = el1.begin(); i12 != el1.end(); ++i12) {
449 248459 : int idx1 = getIndex((*i11), (*i12).toEdge);
450 248459 : if (idx1 < 0) {
451 0 : continue;
452 : }
453 : // go through possibly prohibited
454 1018632 : for (EdgeVector::const_iterator i21 = myIncoming.begin(); i21 != myIncoming.end(); i21++) {
455 770173 : int noLanesEdge2 = (*i21)->getNumLanes();
456 1841338 : for (int j2 = 0; j2 < noLanesEdge2; j2++) {
457 1071165 : std::vector<NBEdge::Connection> el2 = (*i21)->getConnectionsFromLane(j2);
458 3701044 : for (std::vector<NBEdge::Connection>::iterator i22 = el2.begin(); i22 != el2.end(); i22++) {
459 2629879 : int idx2 = getIndex((*i21), (*i22).toEdge);
460 2629879 : if (idx2 < 0) {
461 0 : continue;
462 : }
463 : // check
464 : // same incoming connections do not prohibit each other
465 2629879 : if ((*i11) == (*i21)) {
466 785145 : myForbids[idx1][idx2] = false;
467 : myForbids[idx2][idx1] = false;
468 785145 : continue;
469 : }
470 : // check other
471 : // if both are non-signalised or both are signalised
472 3404814 : if (((*i12).tlID == "" && (*i22).tlID == "")
473 2130472 : ||
474 284654 : ((*i12).tlID != "" && (*i22).tlID != "")) {
475 : // do nothing
476 1842566 : continue;
477 : }
478 : // supposing, we don not have to
479 : // brake if we are no foes
480 2168 : if (!foes(*i11, (*i12).toEdge, *i21, (*i22).toEdge)) {
481 1668 : continue;
482 : }
483 : // otherwise:
484 : // the non-signalised must break
485 500 : if ((*i12).tlID != "") {
486 250 : myForbids[idx1][idx2] = true;
487 : myForbids[idx2][idx1] = false;
488 : } else {
489 250 : myForbids[idx1][idx2] = false;
490 : myForbids[idx2][idx1] = true;
491 : }
492 : }
493 1071165 : }
494 : }
495 : }
496 139488 : }
497 : }
498 51371 : }
499 :
500 :
501 : std::pair<int, int>
502 61486 : NBRequest::getSizes() const {
503 : int numLanes = 0;
504 : int numLinks = 0;
505 183551 : for (const NBEdge* const e : myIncoming) {
506 : const int numLanesEdge = e->getNumLanes();
507 278876 : for (int j = 0; j < numLanesEdge; j++) {
508 156811 : int numConnections = (int)e->getConnectionsFromLane(j).size();
509 156811 : numLinks += numConnections;
510 156811 : if (numConnections > 0) {
511 130126 : numLanes++;
512 : }
513 : }
514 : }
515 61486 : return std::make_pair(numLanes, numLinks);
516 : }
517 :
518 :
519 : bool
520 4405343 : NBRequest::foes(const NBEdge* const from1, const NBEdge* const to1,
521 : const NBEdge* const from2, const NBEdge* const to2) const {
522 : // unconnected edges do not forbid other edges
523 4405343 : if (to1 == nullptr || to2 == nullptr) {
524 : return false;
525 : }
526 : // get the indices
527 4405343 : int idx1 = getIndex(from1, to1);
528 4405343 : int idx2 = getIndex(from2, to2);
529 4405343 : if (idx1 < 0 || idx2 < 0) {
530 : return false; // sure? (The connection does not exist within this junction)
531 : }
532 : assert(idx1 < (int)(myIncoming.size() * myOutgoing.size()));
533 : assert(idx2 < (int)(myIncoming.size()*myOutgoing.size()));
534 4283282 : return myForbids[idx1][idx2] || myForbids[idx2][idx1];
535 : }
536 :
537 :
538 : bool
539 1661999 : NBRequest::forbids(const NBEdge* const possProhibitorFrom, const NBEdge* const possProhibitorTo,
540 : const NBEdge* const possProhibitedFrom, const NBEdge* const possProhibitedTo,
541 : bool regardNonSignalisedLowerPriority) const {
542 : // unconnected edges do not forbid other edges
543 1661999 : if (possProhibitorTo == nullptr || possProhibitedTo == nullptr) {
544 : return false;
545 : }
546 : // get the indices
547 1661999 : int possProhibitorIdx = getIndex(possProhibitorFrom, possProhibitorTo);
548 1661999 : int possProhibitedIdx = getIndex(possProhibitedFrom, possProhibitedTo);
549 1661999 : if (possProhibitorIdx < 0 || possProhibitedIdx < 0) {
550 : return false; // sure? (The connection does not exist within this junction)
551 : }
552 : assert(possProhibitorIdx < (int)(myIncoming.size() * myOutgoing.size()));
553 : assert(possProhibitedIdx < (int)(myIncoming.size() * myOutgoing.size()));
554 : // check simple right-of-way-rules
555 1661999 : if (!regardNonSignalisedLowerPriority) {
556 705610 : return myForbids[possProhibitorIdx][possProhibitedIdx];
557 : }
558 : // if its not forbidden, report
559 956389 : if (!myForbids[possProhibitorIdx][possProhibitedIdx]) {
560 : return false;
561 : }
562 : // do not forbid a signalised stream by a non-signalised
563 174748 : if (!possProhibitorFrom->hasSignalisedConnectionTo(possProhibitorTo)) {
564 32 : return false;
565 : }
566 : return true;
567 : }
568 :
569 : int
570 139488 : NBRequest::computeLaneResponse(NBEdge* from, int fromLane, int pos, const bool checkLaneFoes) {
571 387947 : for (const NBEdge::Connection& c : from->getConnectionsFromLane(fromLane)) {
572 : assert(c.toEdge != 0);
573 248459 : pos++;
574 248459 : const std::string foes = getFoesString(from, c.toEdge, fromLane, c.toLane, checkLaneFoes);
575 248459 : const std::string response = getResponseString(from, c, checkLaneFoes);
576 248459 : myFoes.push_back(foes);
577 248459 : myResponse.push_back(response);
578 248459 : myHaveVia.push_back(c.haveVia);
579 139488 : }
580 139488 : return pos;
581 : }
582 :
583 :
584 : int
585 2392 : NBRequest::computeCrossingResponse(const NBNode::Crossing& crossing, int pos) {
586 2392 : std::string foes(myJunction->getCrossings().size(), '0');
587 2392 : std::string response(myJunction->getCrossings().size(), '0');
588 : // conflicts with normal connections
589 11869 : for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin(); i != myIncoming.rend(); i++) {
590 9477 : const NBEdge* from = *i;
591 29518 : for (int j = from->getNumLanes(); j-- > 0;) {
592 20041 : const std::vector<NBEdge::Connection>& connected = from->getConnectionsFromLane(j);
593 20041 : const int size = (int) connected.size();
594 46232 : for (int k = size; k-- > 0;) {
595 26191 : const NBEdge* to = connected[k].toEdge;
596 : bool foe = false;
597 54880 : for (const NBEdge* const e : crossing.edges) {
598 40278 : if (e == from || e == to) {
599 : foe = true;
600 : break;
601 : }
602 : }
603 26191 : foes += foe ? '1' : '0';
604 26191 : response += mustBrakeForCrossing(myJunction, from, to, crossing) || !foe ? '0' : '1';
605 : }
606 20041 : }
607 : }
608 2392 : pos++;
609 2392 : myResponse.push_back(response);
610 2392 : myFoes.push_back(foes);
611 2392 : myHaveVia.push_back(false);
612 2392 : return pos;
613 : }
614 :
615 :
616 : std::string
617 248459 : NBRequest::getResponseString(const NBEdge* const from, const NBEdge::Connection& c, const bool checkLaneFoes) const {
618 248459 : const NBEdge* const to = c.toEdge;
619 248459 : const int fromLane = c.fromLane;
620 248459 : const int toLane = c.toLane;
621 : int idx = 0;
622 248459 : if (to != nullptr) {
623 248459 : idx = getIndex(from, to);
624 : }
625 : std::string result;
626 248459 : const bool zipper = myJunction->getType() == SumoXMLNodeType::ZIPPER;
627 : // crossings
628 248459 : auto crossings = myJunction->getCrossings();
629 274650 : for (std::vector<NBNode::Crossing*>::const_reverse_iterator i = crossings.rbegin(); i != crossings.rend(); i++) {
630 26191 : result += mustBrakeForCrossing(myJunction, from, to, **i) ? '1' : '0';
631 : }
632 248459 : const NBEdge::Connection& queryCon = from->getConnection(fromLane, to, toLane);
633 : // normal connections
634 1018632 : for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin(); i != myIncoming.rend(); i++) {
635 : //const std::vector<NBEdge::Connection> &allConnections = (*i)->getConnections();
636 770173 : int noLanes = (*i)->getNumLanes();
637 1841338 : for (int j = noLanes; j-- > 0;) {
638 1071165 : std::vector<NBEdge::Connection> connected = (*i)->getConnectionsFromLane(j);
639 1071165 : int size = (int) connected.size();
640 3701044 : for (int k = size; k-- > 0;) {
641 2629879 : if (c.mayDefinitelyPass) {
642 : result += '0';
643 : #ifdef DEBUG_RESPONSE
644 : if (DEBUGCOND) {
645 : std::cout << " c=" << queryCon.getDescription(from) << " pass\n";
646 : }
647 : #endif
648 2629758 : } else if ((*i) == from && fromLane == j) {
649 : // do not prohibit a connection by others from same lane
650 : // except for indirect turns
651 : #ifdef DEBUG_RESPONSE
652 : if (DEBUGCOND) {
653 : std::cout << " c=" << queryCon.getDescription(from) << " prohibitC=" << connected[k].getDescription(*i)
654 : << " itc=" << indirectLeftTurnConflict(from, queryCon, *i, connected[k], false)
655 : << "\n";
656 : }
657 : #endif
658 635204 : if (indirectLeftTurnConflict(from, queryCon, *i, connected[k], false)) {
659 : result += '1';
660 : } else {
661 : result += '0';
662 : }
663 : } else {
664 : assert(connected[k].toEdge != 0);
665 1994554 : const int idx2 = getIndex(*i, connected[k].toEdge);
666 : assert(k < (int) connected.size());
667 : assert(idx < (int)(myIncoming.size() * myOutgoing.size()));
668 : assert(idx2 < (int)(myIncoming.size() * myOutgoing.size()));
669 : // check whether the connection is prohibited by another one
670 : #ifdef DEBUG_RESPONSE
671 : if (DEBUGCOND) {
672 : std::cout << " c=" << queryCon.getDescription(from) << " prohibitC=" << connected[k].getDescription(*i)
673 : << " f=" << myForbids[idx2][idx]
674 : << " clf=" << checkLaneFoes
675 : << " clfbc=" << checkLaneFoesByClass(queryCon, *i, connected[k])
676 : << " clfbcoop=" << checkLaneFoesByCooperation(from, queryCon, *i, connected[k])
677 : << " lc=" << laneConflict(from, to, toLane, *i, connected[k].toEdge, connected[k].toLane)
678 : << " rtc=" << NBNode::rightTurnConflict(from, to, fromLane, *i, connected[k].toEdge, connected[k].fromLane)
679 : << " rtc2=" << rightTurnConflict(from, queryCon, *i, connected[k])
680 : << " mc=" << mergeConflict(from, queryCon, *i, connected[k], false)
681 : << " oltc=" << oppositeLeftTurnConflict(from, queryCon, *i, connected[k], false)
682 : << " itc=" << indirectLeftTurnConflict(from, queryCon, *i, connected[k], zipper)
683 : << " bc=" << bidiConflict(from, queryCon, *i, connected[k], false)
684 : << " rorc=" << myJunction->rightOnRedConflict(c.tlLinkIndex, connected[k].tlLinkIndex)
685 : << " tlscc=" << myJunction->tlsContConflict(from, c, *i, connected[k])
686 : << "\n";
687 : }
688 : #endif
689 3934838 : const bool hasLaneConflict = (!(checkLaneFoes || checkLaneFoesByClass(queryCon, *i, connected[k])
690 1951738 : || checkLaneFoesByCooperation(from, queryCon, *i, connected[k]))
691 2047265 : || laneConflict(from, to, toLane, *i, connected[k].toEdge, connected[k].toLane));
692 3989148 : if (((myForbids[idx2][idx] || (zipper && myForbids[idx][idx2])) && hasLaneConflict && !bidiConflict(*i, connected[k], from, queryCon, false))
693 1587024 : || rightTurnConflict(from, queryCon, *i, connected[k])
694 1586311 : || mergeConflict(from, queryCon, *i, connected[k], zipper)
695 1586077 : || oppositeLeftTurnConflict(from, queryCon, *i, connected[k], zipper)
696 1582929 : || indirectLeftTurnConflict(from, queryCon, *i, connected[k], zipper)
697 1582929 : || bidiConflict(from, queryCon, *i, connected[k], false)
698 1582915 : || myJunction->rightOnRedConflict(c.tlLinkIndex, connected[k].tlLinkIndex)
699 3577439 : || (myJunction->tlsContConflict(from, c, *i, connected[k]) && hasLaneConflict
700 2013839 : && !OptionsCont::getOptions().getBool("tls.ignore-internal-junction-jam"))
701 : ) {
702 : result += '1';
703 : } else {
704 : result += '0';
705 : }
706 : }
707 : }
708 1071165 : }
709 : }
710 248459 : return result;
711 : }
712 :
713 :
714 : std::string
715 248459 : NBRequest::getFoesString(NBEdge* from, NBEdge* to, int fromLane, int toLane, const bool checkLaneFoes) const {
716 496918 : const bool lefthand = OptionsCont::getOptions().getBool("lefthand");
717 : // remember the case when the lane is a "dead end" in the meaning that
718 : // vehicles must choose another lane to move over the following
719 : // junction
720 : // !!! move to forbidden
721 : std::string result;
722 : // crossings
723 248459 : auto crossings = myJunction->getCrossings();
724 274650 : for (std::vector<NBNode::Crossing*>::const_reverse_iterator i = crossings.rbegin(); i != crossings.rend(); i++) {
725 : bool foes = false;
726 54880 : for (EdgeVector::const_iterator it_e = (**i).edges.begin(); it_e != (**i).edges.end(); ++it_e) {
727 40278 : if ((*it_e) == from || (*it_e) == to) {
728 : foes = true;
729 : break;
730 : }
731 : }
732 26191 : result += foes ? '1' : '0';
733 : }
734 248459 : const NBEdge::Connection& queryCon = from->getConnection(fromLane, to, toLane);
735 : // normal connections
736 1018632 : for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin(); i != myIncoming.rend(); i++) {
737 1841338 : for (int j = (*i)->getNumLanes() - 1; j >= 0; --j) {
738 1071165 : const std::vector<NBEdge::Connection>& connected = (*i)->getConnectionsFromLane(j);
739 1071165 : int size = (int) connected.size();
740 3701044 : for (int k = size; k-- > 0;) {
741 5186898 : const bool hasLaneConflict = (!(checkLaneFoes || checkLaneFoesByClass(queryCon, *i, connected[k])
742 2572176 : || checkLaneFoesByCooperation(from, queryCon, *i, connected[k]))
743 2693800 : || laneConflict(from, to, toLane, *i, connected[k].toEdge, connected[k].toLane));
744 3471105 : if ((foes(from, to, (*i), connected[k].toEdge) && hasLaneConflict)
745 1814957 : || rightTurnConflict(from, queryCon, *i, connected[k])
746 1814244 : || myJunction->turnFoes(from, to, fromLane, *i, connected[k].toEdge, connected[k].fromLane, lefthand)
747 1813467 : || mergeConflict(from, queryCon, *i, connected[k], true)
748 1813009 : || oppositeLeftTurnConflict(from, queryCon, *i, connected[k], true)
749 1806723 : || indirectLeftTurnConflict(from, queryCon, *i, connected[k], true)
750 4436580 : || bidiConflict(from, queryCon, *i, connected[k], true)
751 : ) {
752 : result += '1';
753 : } else {
754 : result += '0';
755 : }
756 : }
757 1071165 : }
758 : }
759 248459 : return result;
760 : }
761 :
762 :
763 : bool
764 3402634 : NBRequest::rightTurnConflict(const NBEdge* from, const NBEdge::Connection& con,
765 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon) const {
766 6805153 : return (!con.mayDefinitelyPass &&
767 3402519 : (NBNode::rightTurnConflict(from, con.toEdge, con.fromLane, prohibitorFrom, prohibitorCon.toEdge, prohibitorCon.fromLane)
768 : // reverse conflicht (override)
769 3401032 : || (prohibitorCon.mayDefinitelyPass &&
770 72 : NBNode::rightTurnConflict(prohibitorFrom, prohibitorCon.toEdge, prohibitorCon.fromLane, from, con.toEdge, con.fromLane))));
771 :
772 :
773 : }
774 :
775 :
776 : bool
777 5195842 : NBRequest::mergeConflict(const NBEdge* from, const NBEdge::Connection& con,
778 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon, bool foes) const {
779 : if (from == prohibitorFrom
780 1454219 : && con.toEdge == prohibitorCon.toEdge
781 542557 : && con.toLane == prohibitorCon.toLane
782 401073 : && con.fromLane != prohibitorCon.fromLane
783 5197716 : && !myJunction->isConstantWidthTransition()) {
784 1870 : if (foes) {
785 : return true;
786 : }
787 1150 : if (prohibitorCon.mayDefinitelyPass) {
788 : return true;
789 : }
790 1147 : if (con.mayDefinitelyPass) {
791 : return false;
792 : }
793 1147 : const bool bike = from->getPermissions(con.fromLane) == SVC_BICYCLE;
794 1147 : const bool prohibitorBike = prohibitorFrom->getPermissions(prohibitorCon.fromLane) == SVC_BICYCLE;
795 1147 : if (myOutgoing.size() == 1) {
796 : // at on-ramp like situations, right lane should yield
797 39 : return bike || (con.fromLane < prohibitorCon.fromLane && !prohibitorBike);
798 : } else {
799 : // priority depends on direction:
800 : // for right turns the rightmost lane gets priority
801 : // otherwise the left lane
802 1121 : LinkDirection dir = myJunction->getDirection(from, con.toEdge);
803 1121 : if (dir == LinkDirection::RIGHT || dir == LinkDirection::PARTRIGHT) {
804 747 : return con.fromLane > prohibitorCon.fromLane;
805 : } else {
806 374 : if (myIncoming.size() == 1) {
807 : // at off-ramp like situations, right lane should pass unless it's a bicycle lane
808 6 : return bike || (con.fromLane > prohibitorCon.fromLane && !prohibitorBike);
809 : } else {
810 370 : return con.fromLane < prohibitorCon.fromLane;
811 : }
812 : }
813 : }
814 :
815 : } else {
816 5193972 : return false;
817 : }
818 : }
819 :
820 :
821 : bool
822 3399086 : NBRequest::oppositeLeftTurnConflict(const NBEdge* from, const NBEdge::Connection& con,
823 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon, bool foes) const {
824 3399086 : LinkDirection dir = myJunction->getDirection(from, con.toEdge);
825 : // XXX lefthand issue (solve via #4256)
826 3399086 : if (dir != LinkDirection::LEFT && dir != LinkDirection::PARTLEFT) {
827 : return false;
828 : }
829 691796 : dir = myJunction->getDirection(prohibitorFrom, prohibitorCon.toEdge);
830 691796 : if (dir != LinkDirection::LEFT && dir != LinkDirection::PARTLEFT) {
831 : return false;
832 : }
833 189957 : if (from == prohibitorFrom || NBRequest::foes(from, con.toEdge, prohibitorFrom, prohibitorCon.toEdge)) {
834 : // not an opposite pair
835 106489 : return false;
836 : }
837 :
838 83468 : const double width1 = MIN2(from->getLaneWidth(con.fromLane) / 2, OptionsCont::getOptions().getFloat("internal-junctions.vehicle-width") / 2);
839 83468 : const double width2 = prohibitorCon.toEdge->getLaneWidth(prohibitorCon.toLane) / 2;
840 : PositionVector shape = con.shape;
841 83468 : shape.append(con.viaShape);
842 : PositionVector otherShape = prohibitorCon.shape;
843 83468 : otherShape.append(prohibitorCon.viaShape);
844 83468 : if (shape.size() == 0 || otherShape.size() == 0) {
845 : // no internal lanes built
846 : return false;
847 : }
848 25848 : const double minDV = NBEdge::firstIntersection(shape, otherShape, width1, width2);
849 25848 : if (minDV < shape.length() - POSITION_EPS && minDV > POSITION_EPS) {
850 : // break symmetry using edge id
851 12572 : return foes || from->getID() < prohibitorFrom->getID();
852 : }
853 : return false;
854 83468 : }
855 :
856 : bool
857 4540476 : NBRequest::indirectLeftTurnConflict(const NBEdge* from, const NBEdge::Connection& con,
858 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon, bool foes) const {
859 4540476 : if (from == prohibitorFrom) {
860 1714569 : if (con.toEdge == prohibitorCon.toEdge) {
861 : return false;
862 1032961 : } else if (con.indirectLeft) {
863 126 : LinkDirection dir = myJunction->getDirection(prohibitorFrom, prohibitorCon.toEdge);
864 126 : return (dir == LinkDirection::STRAIGHT);
865 1032835 : } else if (foes && prohibitorCon.indirectLeft) {
866 27 : LinkDirection dir = myJunction->getDirection(from, con.toEdge);
867 27 : return (dir == LinkDirection::STRAIGHT);
868 : }
869 : }
870 : return false;
871 : }
872 :
873 : bool
874 4692563 : NBRequest::bidiConflict(const NBEdge* from, const NBEdge::Connection& con,
875 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon, bool foes) const {
876 4692563 : if (from == prohibitorFrom) {
877 : return false;
878 : }
879 3502393 : if (isRailway(from->getPermissions())) {
880 : // railways manage right-of-way via signals
881 : return false;
882 : }
883 1648241 : if ((foes && (from->getBidiEdge() == prohibitorCon.toEdge))
884 5117788 : || prohibitorFrom->getBidiEdge() == con.toEdge) {
885 1168 : const bool fromBidi = from->getLaneShape(con.fromLane).reverse().almostSame(
886 584 : prohibitorCon.toEdge->getLaneShape(prohibitorCon.toLane), POSITION_EPS);
887 1168 : const bool prohibitorFromBidi = prohibitorFrom->getLaneShape(prohibitorCon.fromLane).reverse().almostSame(
888 584 : con.toEdge->getLaneShape(con.toLane), POSITION_EPS);
889 584 : if (!foes && fromBidi && prohibitorFromBidi) {
890 : // do not create a symmetrical conflict
891 : return false;
892 : }
893 717 : if (prohibitorFromBidi &&
894 876 : prohibitorFrom->getLaneShape(prohibitorCon.fromLane).reverse().almostSame(
895 159 : prohibitorCon.toEdge->getLaneShape(prohibitorCon.toLane), POSITION_EPS)) {
896 : // prohibitor has a bidi-turnaround
897 : return false;
898 : }
899 :
900 493 : return fromBidi || prohibitorFromBidi;
901 : }
902 : return false;
903 : }
904 :
905 : bool
906 4597822 : NBRequest::checkLaneFoesByClass(const NBEdge::Connection& con,
907 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon) const {
908 4597822 : if (con.toEdge != prohibitorCon.toEdge) {
909 : return false;
910 : }
911 1303316 : SVCPermissions svc = con.toEdge->getPermissions(con.toLane);
912 1303316 : SVCPermissions svc2 = prohibitorFrom->getPermissions(prohibitorCon.fromLane) & prohibitorCon.toEdge->getPermissions(prohibitorCon.toLane);
913 : // check for lane level conflict if the only common classes are bicycles or pedestrians
914 1303316 : return ((svc & svc2 & ~(SVC_BICYCLE | SVC_PEDESTRIAN)) == 0
915 : // or if the connection is to a dedicated lane whereas the prohibitor is a "general" lane
916 1303316 : || (((svc & SVC_PASSENGER) == 0) && ((svc2 & SVC_PASSENGER) != 0)));
917 : }
918 :
919 :
920 : bool
921 4523914 : NBRequest::checkLaneFoesByCooperation(const NBEdge* from, const NBEdge::Connection& con,
922 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon) const {
923 4523914 : if (con.toEdge != prohibitorCon.toEdge) {
924 : return false;
925 : }
926 : // if from and prohibitorFrom target distinct lanes for all their
927 : // connections to the common target edge, cooperation is possible
928 : // (and should always happen unless the connections cross for some byzantine reason)
929 :
930 : std::set<int> fromTargetLanes;
931 5972055 : for (const NBEdge::Connection& c : from->getConnections()) {
932 4742647 : if (c.toEdge == con.toEdge) {
933 1751093 : fromTargetLanes.insert(c.toLane);
934 : }
935 : }
936 2922602 : for (const NBEdge::Connection& c : prohibitorFrom->getConnections()) {
937 2879878 : if (c.toEdge == con.toEdge && fromTargetLanes.count(c.toLane) != 0) {
938 : //std::cout << " con=" << con->getDescription(from) << " foe=" << prohibitorCon.getDescription(prohibitorFrom)
939 : // << " no cooperation (targets=" << joinToString(fromTargetLanes, ' ') << " index=" << c.toLane << "\n";
940 : return false;
941 : }
942 : }
943 : return true;
944 : }
945 :
946 :
947 : bool
948 143243 : NBRequest::laneConflict(const NBEdge* from, const NBEdge* to, int toLane,
949 : const NBEdge* prohibitorFrom, const NBEdge* prohibitorTo, int prohibitorToLane) const {
950 143243 : if (to != prohibitorTo) {
951 : return true;
952 : }
953 : // since we know that the edge2edge connections are in conflict, the only
954 : // situation in which the lane2lane connections can be conflict-free is, if
955 : // they target the same edge but do not cross each other
956 129776 : double angle = NBHelpers::relAngle(
957 : from->getAngleAtNode(from->getToNode()), to->getAngleAtNode(to->getFromNode()));
958 129776 : if (angle == 180) {
959 : angle = -180; // turnarounds are left turns
960 : }
961 129776 : const double prohibitorAngle = NBHelpers::relAngle(
962 : prohibitorFrom->getAngleAtNode(prohibitorFrom->getToNode()), to->getAngleAtNode(to->getFromNode()));
963 129776 : const bool rightOfProhibitor = prohibitorFrom->isTurningDirectionAt(to)
964 129776 : || (angle > prohibitorAngle && !from->isTurningDirectionAt(to));
965 129776 : return rightOfProhibitor ? toLane >= prohibitorToLane : toLane <= prohibitorToLane;
966 : }
967 :
968 : int
969 20154804 : NBRequest::getIndex(const NBEdge* const from, const NBEdge* const to) const {
970 20154804 : EdgeVector::const_iterator fp = std::find(myIncoming.begin(), myIncoming.end(), from);
971 20154804 : EdgeVector::const_iterator tp = std::find(myOutgoing.begin(), myOutgoing.end(), to);
972 20154804 : if (fp == myIncoming.end() || tp == myOutgoing.end()) {
973 : return -1;
974 : }
975 : // compute the index
976 20032743 : return (int)(distance(myIncoming.begin(), fp) * myOutgoing.size() + distance(myOutgoing.begin(), tp));
977 : }
978 :
979 :
980 : std::ostream&
981 0 : operator<<(std::ostream& os, const NBRequest& r) {
982 0 : int variations = r.numLinks();
983 0 : for (int i = 0; i < variations; i++) {
984 0 : os << i << ' ';
985 0 : for (int j = 0; j < variations; j++) {
986 0 : if (r.myForbids[i][j]) {
987 0 : os << '1';
988 : } else {
989 0 : os << '0';
990 : }
991 : }
992 : os << std::endl;
993 : }
994 : os << std::endl;
995 0 : return os;
996 : }
997 :
998 :
999 : bool
1000 278026 : NBRequest::mustBrake(const NBEdge* const from, const NBEdge* const to, int fromLane, int toLane, bool includePedCrossings) const {
1001 278026 : NBEdge::Connection con(fromLane, const_cast<NBEdge*>(to), toLane);
1002 278026 : const int linkIndex = myJunction->getConnectionIndex(from, con);
1003 278026 : if (linkIndex >= 0 && (int)myResponse.size() > linkIndex) {
1004 252059 : std::string response = getResponse(linkIndex);
1005 252059 : if (!includePedCrossings) {
1006 54 : response = response.substr(0, response.size() - myJunction->getCrossings().size());
1007 : }
1008 252059 : if (response.find_first_of("1") == std::string::npos) {
1009 : return false;
1010 123172 : } else if (!myJunction->isTLControlled()) {
1011 : return true;
1012 : }
1013 : // if the link must respond it could also be due to a tlsConflict. This
1014 : // must not carry over the the off-state response so we continue with
1015 : // the regular check
1016 : }
1017 : // get the indices
1018 43784 : int idx2 = getIndex(from, to);
1019 43784 : if (idx2 == -1) {
1020 : return false;
1021 : }
1022 : // go through all (existing) connections;
1023 : // check whether any of these forbids the one to determine
1024 : assert(idx2 < (int)(myIncoming.size()*myOutgoing.size()));
1025 303926 : for (int idx1 = 0; idx1 < numLinks(); idx1++) {
1026 : //assert(myDone[idx1][idx2]);
1027 419714 : if (myDone[idx1][idx2] && myForbids[idx1][idx2]) {
1028 : return true;
1029 : }
1030 : }
1031 : // maybe we need to brake for a pedestrian crossing
1032 3528 : if (includePedCrossings) {
1033 3010 : auto crossings = myJunction->getCrossings();
1034 3855 : for (std::vector<NBNode::Crossing*>::const_reverse_iterator i = crossings.rbegin(); i != crossings.rend(); i++) {
1035 1879 : if (mustBrakeForCrossing(myJunction, from, to, **i)) {
1036 : return true;
1037 : }
1038 : }
1039 : }
1040 : // maybe we need to brake due to a right-turn conflict with straight-going
1041 : // bicycles
1042 2494 : const NBEdge::Connection& queryCon = from->getConnection(fromLane, to, toLane);
1043 2494 : LinkDirection dir = myJunction->getDirection(from, to);
1044 2494 : if (dir == LinkDirection::RIGHT || dir == LinkDirection::PARTRIGHT) {
1045 725 : for (const NBEdge::Connection& fromCon : from->getConnections()) {
1046 653 : if (rightTurnConflict(from, queryCon, from, fromCon)) {
1047 : return true;
1048 : }
1049 : }
1050 : }
1051 : // maybe we need to brake due to a merge conflict
1052 12649 : for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin(); i != myIncoming.rend(); i++) {
1053 10307 : int noLanes = (*i)->getNumLanes();
1054 29999 : for (int j = noLanes; j-- > 0;) {
1055 19705 : std::vector<NBEdge::Connection> connected = (*i)->getConnectionsFromLane(j);
1056 19705 : const int size = (int) connected.size();
1057 61147 : for (int k = size; k-- > 0;) {
1058 10666 : if ((*i) == from && fromLane != j
1059 46285 : && mergeConflict(from, queryCon, *i, connected[k], myJunction->getType() == SumoXMLNodeType::ZIPPER)) {
1060 : return true;
1061 : }
1062 : }
1063 19705 : }
1064 : }
1065 : // maybe we need to brake due to a zipper conflict
1066 2342 : if (myJunction->getType() == SumoXMLNodeType::ZIPPER) {
1067 0 : for (int idx1 = 0; idx1 < numLinks(); idx1++) {
1068 : //assert(myDone[idx1][idx2]);
1069 0 : if (myDone[idx1][idx2] && myForbids[idx2][idx1]) {
1070 : return true;
1071 : }
1072 : }
1073 : }
1074 : return false;
1075 278026 : }
1076 :
1077 :
1078 : bool
1079 64239 : NBRequest::mustBrakeForCrossing(const NBNode* node, const NBEdge* const from, const NBEdge* const to, const NBNode::Crossing& crossing) {
1080 64239 : const LinkDirection dir = node->getDirection(from, to);
1081 64239 : const bool mustYield = dir == LinkDirection::LEFT || dir == LinkDirection::RIGHT;
1082 64239 : if (crossing.priority || mustYield) {
1083 108218 : for (const NBEdge* const e : crossing.edges) {
1084 : // left and right turns must yield to unprioritized crossings only on their destination edge
1085 74285 : if ((e == from && crossing.priority) || e == to) {
1086 : return true;
1087 : }
1088 : }
1089 : }
1090 : return false;
1091 : }
1092 :
1093 :
1094 : bool
1095 0 : NBRequest::mustBrake(const NBEdge* const possProhibitorFrom, const NBEdge* const possProhibitorTo,
1096 : const NBEdge* const possProhibitedFrom, const NBEdge* const possProhibitedTo) const {
1097 : // get the indices
1098 0 : int idx1 = getIndex(possProhibitorFrom, possProhibitorTo);
1099 0 : int idx2 = getIndex(possProhibitedFrom, possProhibitedTo);
1100 0 : return (myForbids[idx2][idx1]);
1101 : }
1102 :
1103 :
1104 : void
1105 1835 : NBRequest::reportWarnings() {
1106 : // check if any errors occurred on build the link prohibitions
1107 1835 : if (myNotBuild != 0) {
1108 0 : WRITE_WARNING(toString(myNotBuild) + " of " + toString(myNotBuild + myGoodBuilds) + " prohibitions were not build.");
1109 : }
1110 1835 : }
1111 :
1112 :
1113 : void
1114 51371 : NBRequest::resetCooperating() {
1115 : // map from edge to number of incoming connections
1116 : std::map<const NBEdge*, int> incomingCount; // initialized to 0
1117 : // map from edge to indices of approached lanes
1118 : std::map<const NBEdge*, std::set<int> > approachedLanes;
1119 : // map from edge to list of incoming edges
1120 : std::map<const NBEdge*, std::vector<const NBEdge*> > incomingEdges;
1121 157883 : for (const NBEdge* const e : myIncoming) {
1122 354971 : for (const NBEdge::Connection& con : e->getConnections()) {
1123 248459 : incomingCount[con.toEdge]++;
1124 248459 : approachedLanes[con.toEdge].insert(con.toLane);
1125 248459 : incomingEdges[con.toEdge].push_back(e);
1126 : }
1127 : }
1128 154294 : for (std::map<const NBEdge*, int>::iterator it = incomingCount.begin(); it != incomingCount.end(); ++it) {
1129 102923 : const NBEdge* const to = it->first;
1130 : // we cannot test against to->getNumLanes() since not all lanes may be used
1131 102923 : if ((int)approachedLanes[to].size() >= it->second) {
1132 42384 : const std::vector<const NBEdge*>& incoming = incomingEdges[to];
1133 : // make these connections mutually unconflicting
1134 97082 : for (const NBEdge* const e1 : incoming) {
1135 147184 : for (const NBEdge* const e2 : incoming) {
1136 92486 : myForbids[getIndex(e1, to)][getIndex(e2, to)] = false;
1137 : }
1138 : }
1139 : }
1140 : }
1141 51371 : }
1142 :
1143 :
1144 : bool
1145 51553 : NBRequest::hasConflict() const {
1146 100015 : for (int i = 0; i < (int)myFoes.size(); i++) {
1147 72679 : if (hasConflictAtLink(i)) {
1148 : return true;
1149 : }
1150 : }
1151 : return false;
1152 : }
1153 :
1154 : bool
1155 74036 : NBRequest::hasConflictAtLink(int linkIndex) const {
1156 74036 : return myFoes[linkIndex].find_first_of("1") != std::string::npos;
1157 : }
1158 :
1159 : int
1160 364824 : NBRequest::numLinks() const {
1161 364824 : return (int)(myIncoming.size() * myOutgoing.size() + myJunction->getCrossings().size());
1162 : }
1163 :
1164 :
1165 : /****************************************************************************/
|