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 50844 : NBRequest::NBRequest(const NBEdgeCont& ec,
57 : NBNode* junction,
58 : const EdgeVector& all,
59 : const EdgeVector& incoming,
60 : const EdgeVector& outgoing,
61 50844 : const NBConnectionProhibits& loadedProhibits) :
62 50844 : myJunction(junction),
63 50844 : myAll(all),
64 50844 : myIncoming(incoming),
65 50844 : myOutgoing(outgoing) {
66 50844 : const int variations = numLinks();
67 : // build maps with information which forbidding connection were
68 : // computed and what's in there
69 50844 : myForbids.reserve(variations);
70 50844 : myDone.reserve(variations);
71 306690 : for (int i = 0; i < variations; i++) {
72 255846 : myForbids.push_back(LinkInfoCont(variations, false));
73 511692 : myDone.push_back(LinkInfoCont(variations, false));
74 : }
75 : // insert loaded prohibits
76 50946 : 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 306690 : for (int s1 = 0; s1 < variations; s1++) {
125 1932918 : for (int s2 = s1 + 1; s2 < variations; s2++) {
126 : // not set, yet
127 1677072 : if (!myDone[s1][s2]) {
128 1676960 : 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 50844 : }
139 :
140 :
141 50844 : NBRequest::~NBRequest() {}
142 :
143 :
144 : void
145 44274 : NBRequest::buildBitfieldLogic() {
146 : EdgeVector::const_iterator i, j;
147 134844 : for (i = myIncoming.begin(); i != myIncoming.end(); i++) {
148 323703 : for (j = myOutgoing.begin(); j != myOutgoing.end(); j++) {
149 233133 : computeRightOutgoingLinkCrossings(*i, *j);
150 233133 : computeLeftOutgoingLinkCrossings(*i, *j);
151 : }
152 : }
153 : // reset signalised/non-signalised dependencies
154 44274 : resetSignalised();
155 : // reset foes it the number of lanes matches (or exceeds) the number of incoming connections
156 44274 : resetCooperating();
157 44274 : }
158 :
159 :
160 : void
161 233133 : NBRequest::computeRightOutgoingLinkCrossings(NBEdge* from, NBEdge* to) {
162 233133 : EdgeVector::const_iterator pfrom = std::find(myAll.begin(), myAll.end(), from);
163 996985 : while (*pfrom != to) {
164 763852 : NBContHelper::nextCCW(myAll, pfrom);
165 763852 : if ((*pfrom)->getToNode() == myJunction) {
166 265983 : EdgeVector::const_iterator pto = std::find(myAll.begin(), myAll.end(), to);
167 1066791 : while (*pto != from) {
168 800808 : if (!((*pto)->getToNode() == myJunction)) {
169 535991 : setBlocking(from, to, *pfrom, *pto);
170 : }
171 800808 : NBContHelper::nextCCW(myAll, pto);
172 : }
173 : }
174 : }
175 233133 : }
176 :
177 :
178 : void
179 233133 : NBRequest::computeLeftOutgoingLinkCrossings(NBEdge* from, NBEdge* to) {
180 233133 : EdgeVector::const_iterator pfrom = std::find(myAll.begin(), myAll.end(), from);
181 996985 : while (*pfrom != to) {
182 763852 : NBContHelper::nextCW(myAll, pfrom);
183 763852 : if ((*pfrom)->getToNode() == myJunction) {
184 265983 : EdgeVector::const_iterator pto = std::find(myAll.begin(), myAll.end(), to);
185 1066791 : while (*pto != from) {
186 800808 : if (!((*pto)->getToNode() == myJunction)) {
187 535991 : setBlocking(from, to, *pfrom, *pto);
188 : }
189 800808 : NBContHelper::nextCW(myAll, pto);
190 : }
191 : }
192 : }
193 233133 : }
194 :
195 :
196 : void
197 1071982 : NBRequest::setBlocking(NBEdge* from1, NBEdge* to1,
198 : NBEdge* from2, NBEdge* to2) {
199 : // check whether one of the links has a dead end
200 1071982 : if (to1 == nullptr || to2 == nullptr) {
201 1071982 : return;
202 : }
203 : // get the indices of both links
204 1071982 : int idx1 = getIndex(from1, to1);
205 1071982 : int idx2 = getIndex(from2, to2);
206 1071982 : 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 1071982 : if (myDone[idx1][idx2]) {
212 : return;
213 : }
214 : // mark the crossings as done
215 : myDone[idx1][idx2] = true;
216 535901 : myDone[idx2][idx1] = true;
217 : // special case all-way stop
218 535901 : 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 80 : 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 535821 : if (from1->isTurningDirectionAt(to1)) {
227 : myForbids[idx2][idx1] = true;
228 68948 : return;
229 : }
230 466873 : if (from2->isTurningDirectionAt(to2)) {
231 : myForbids[idx1][idx2] = true;
232 65169 : return;
233 : }
234 : // if there are no connections, there are no prohibitions
235 401704 : if (from1->isConnectedTo(to1)) {
236 250267 : if (!from2->isConnectedTo(to2)) {
237 : myForbids[idx1][idx2] = true;
238 : myForbids[idx2][idx1] = false;
239 27992 : return;
240 : }
241 : } else {
242 151437 : if (!from2->isConnectedTo(to2)) {
243 : myForbids[idx1][idx2] = false;
244 : myForbids[idx2][idx1] = false;
245 122728 : return;
246 : } else {
247 : myForbids[idx1][idx2] = false;
248 : myForbids[idx2][idx1] = true;
249 28709 : 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 222275 : const bool typeEqual = myJunction->getType() == SumoXMLNodeType::RIGHT_BEFORE_LEFT || myJunction->getType() == SumoXMLNodeType::LEFT_BEFORE_RIGHT;
260 : if (!typeEqual) {
261 197903 : int from1p = from1->getJunctionPriority(myJunction);
262 197903 : 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 197903 : if (from1p > from2p) {
271 : myForbids[idx1][idx2] = true;
272 68928 : return;
273 : }
274 128975 : if (from2p > from1p) {
275 : myForbids[idx2][idx1] = true;
276 56518 : return;
277 : }
278 : }
279 : // straight connections prohibit turning connections if the priorities are equal
280 : // (unless the junction is a bent priority junction)
281 96829 : LinkDirection ld1 = myJunction->getDirection(from1, to1);
282 96829 : LinkDirection ld2 = myJunction->getDirection(from2, to2);
283 96829 : 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 46153 : if (ld1 == LinkDirection::STRAIGHT) {
291 11431 : if (ld2 != LinkDirection::STRAIGHT) {
292 : myForbids[idx1][idx2] = true;
293 : myForbids[idx2][idx1] = false;
294 10478 : return;
295 : }
296 : } else {
297 34722 : if (ld2 == LinkDirection::STRAIGHT) {
298 : myForbids[idx1][idx2] = false;
299 : myForbids[idx2][idx1] = true;
300 11189 : 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 75162 : EdgeVector::const_iterator c1 = std::find(myAll.begin(), myAll.end(), from1);
335 75162 : NBContHelper::nextCW(myAll, c1);
336 : // go through next edges clockwise...
337 230950 : while (*c1 != from1 && *c1 != from2) {
338 181970 : if (*c1 == to2) {
339 : // if we encounter to2 the second one prohibits the first
340 26182 : if (myJunction->getType() == SumoXMLNodeType::LEFT_BEFORE_RIGHT
341 26182 : && (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 26182 : return;
361 : }
362 155788 : NBContHelper::nextCW(myAll, c1);
363 : }
364 : // get the position of the incoming lanes in the junction-wheel
365 48980 : EdgeVector::const_iterator c2 = std::find(myAll.begin(), myAll.end(), from2);
366 48980 : NBContHelper::nextCW(myAll, c2);
367 : // go through next edges clockwise...
368 161016 : while (*c2 != from2 && *c2 != from1) {
369 161016 : if (*c2 == to1) {
370 : // if we encounter to1 the second one prohibits the first
371 48980 : if (myJunction->getType() == SumoXMLNodeType::LEFT_BEFORE_RIGHT
372 48980 : && (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 48980 : return;
392 : }
393 112036 : 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 212600 : NBRequest::getResponse(int linkIndex) const {
427 : assert(linkIndex >= 0);
428 : assert(linkIndex < (int)myResponse.size());
429 212600 : return myResponse[linkIndex];
430 : }
431 :
432 :
433 : void
434 43282 : NBRequest::writeLogic(OutputDevice& into) const {
435 43282 : int numLinks = (int)myResponse.size();
436 : assert((int)myFoes.size() == numLinks);
437 : assert((int)myHaveVia.size() == numLinks);
438 : const bool padding = numLinks > 10;
439 247341 : for (int i = 0; i < numLinks; i++) {
440 204059 : into.openTag(SUMO_TAG_REQUEST);
441 204059 : into.writeAttr(SUMO_ATTR_INDEX, i);
442 204059 : if (padding && i < 10) {
443 95940 : into.writePadding(" ");
444 : }
445 204059 : into.writeAttr(SUMO_ATTR_RESPONSE, myResponse[i]);
446 204059 : into.writeAttr(SUMO_ATTR_FOES, myFoes[i]);
447 408118 : if (!OptionsCont::getOptions().getBool("no-internal-links")) {
448 93158 : into.writeAttr(SUMO_ATTR_CONT, myHaveVia[i]);
449 : }
450 408118 : into.closeTag();
451 : }
452 43282 : }
453 :
454 :
455 : void
456 44274 : 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 134844 : for (i = myIncoming.begin(); i != myIncoming.end(); i++) {
464 90570 : int noLanes = (*i)->getNumLanes();
465 209840 : for (int k = 0; k < noLanes; k++) {
466 121207 : pos = computeLaneResponse(*i, k, pos, checkLaneFoes || myJunction->getType() == SumoXMLNodeType::ZIPPER);
467 : }
468 : }
469 : // crossings
470 44274 : auto crossings = myJunction->getCrossings();
471 45889 : for (auto c : crossings) {
472 1615 : pos = computeCrossingResponse(*c, pos);
473 : }
474 44274 : }
475 :
476 : void
477 44274 : NBRequest::resetSignalised() {
478 : // go through possible prohibitions
479 134844 : for (EdgeVector::const_iterator i11 = myIncoming.begin(); i11 != myIncoming.end(); i11++) {
480 90570 : int noLanesEdge1 = (*i11)->getNumLanes();
481 209840 : for (int j1 = 0; j1 < noLanesEdge1; j1++) {
482 119270 : std::vector<NBEdge::Connection> el1 = (*i11)->getConnectionsFromLane(j1);
483 328462 : for (std::vector<NBEdge::Connection>::iterator i12 = el1.begin(); i12 != el1.end(); ++i12) {
484 209192 : int idx1 = getIndex((*i11), (*i12).toEdge);
485 209192 : if (idx1 < 0) {
486 0 : continue;
487 : }
488 : // go through possibly prohibited
489 848509 : for (EdgeVector::const_iterator i21 = myIncoming.begin(); i21 != myIncoming.end(); i21++) {
490 639317 : int noLanesEdge2 = (*i21)->getNumLanes();
491 1537636 : for (int j2 = 0; j2 < noLanesEdge2; j2++) {
492 898319 : std::vector<NBEdge::Connection> el2 = (*i21)->getConnectionsFromLane(j2);
493 3078219 : for (std::vector<NBEdge::Connection>::iterator i22 = el2.begin(); i22 != el2.end(); i22++) {
494 2179900 : int idx2 = getIndex((*i21), (*i22).toEdge);
495 2179900 : if (idx2 < 0) {
496 0 : continue;
497 : }
498 : // check
499 : // same incoming connections do not prohibit each other
500 2179900 : if ((*i11) == (*i21)) {
501 653636 : myForbids[idx1][idx2] = false;
502 653636 : 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 653636 : continue;
510 : }
511 : // check other
512 : // if both are non-signalised or both are signalised
513 1291767 : if (((*i12).tlID == "" && (*i22).tlID == "")
514 1527501 : ||
515 234497 : ((*i12).tlID != "" && (*i22).tlID != "")) {
516 : // do nothing
517 1523790 : continue;
518 : }
519 : // supposing, we don not have to
520 : // brake if we are no foes
521 2474 : if (!foes(*i11, (*i12).toEdge, *i21, (*i22).toEdge)) {
522 1936 : 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 898319 : }
545 : }
546 : }
547 119270 : }
548 : }
549 44274 : }
550 :
551 :
552 : std::pair<int, int>
553 51290 : NBRequest::getSizes() const {
554 : int numLanes = 0;
555 : int numLinks = 0;
556 153139 : for (const NBEdge* const e : myIncoming) {
557 : const int numLanesEdge = e->getNumLanes();
558 234323 : for (int j = 0; j < numLanesEdge; j++) {
559 132474 : int numConnections = (int)e->getConnectionsFromLane(j).size();
560 132474 : numLinks += numConnections;
561 132474 : if (numConnections > 0) {
562 111791 : numLanes++;
563 : }
564 : }
565 : }
566 51290 : return std::make_pair(numLanes, numLinks);
567 : }
568 :
569 :
570 : bool
571 3739009 : 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 3739009 : if (to1 == nullptr || to2 == nullptr) {
575 : return false;
576 : }
577 : // get the indices
578 3739009 : int idx1 = getIndex(from1, to1);
579 3739009 : int idx2 = getIndex(from2, to2);
580 3739009 : 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 3582191 : return myForbids[idx1][idx2] || myForbids[idx2][idx1];
586 : }
587 :
588 :
589 : bool
590 1466170 : 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 1466170 : if (possProhibitorTo == nullptr || possProhibitedTo == nullptr) {
595 : return false;
596 : }
597 : // get the indices
598 1466170 : int possProhibitorIdx = getIndex(possProhibitorFrom, possProhibitorTo);
599 1466170 : int possProhibitedIdx = getIndex(possProhibitedFrom, possProhibitedTo);
600 1466170 : 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 1466170 : if (!regardNonSignalisedLowerPriority) {
607 589773 : return myForbids[possProhibitorIdx][possProhibitedIdx];
608 : }
609 : // if its not forbidden, report
610 876397 : if (!myForbids[possProhibitorIdx][possProhibitedIdx]) {
611 : return false;
612 : }
613 : // do not forbid a signalised stream by a non-signalised
614 158146 : if (!possProhibitorFrom->hasSignalisedConnectionTo(possProhibitorTo)) {
615 : return false;
616 : }
617 : return true;
618 : }
619 :
620 : int
621 119270 : NBRequest::computeLaneResponse(NBEdge* from, int fromLane, int pos, const bool checkLaneFoes) {
622 328462 : for (const NBEdge::Connection& c : from->getConnectionsFromLane(fromLane)) {
623 : assert(c.toEdge != 0);
624 209192 : pos++;
625 209192 : const std::string foes = getFoesString(from, c, checkLaneFoes);
626 209192 : const std::string response = getResponseString(from, c, checkLaneFoes);
627 209192 : myFoes.push_back(foes);
628 209192 : myResponse.push_back(response);
629 209192 : myHaveVia.push_back(c.haveVia);
630 119270 : }
631 119270 : return pos;
632 : }
633 :
634 :
635 : int
636 1615 : NBRequest::computeCrossingResponse(const NBNode::Crossing& crossing, int pos) {
637 3230 : std::string foes(myJunction->getCrossings().size(), '0');
638 3230 : std::string response(myJunction->getCrossings().size(), '0');
639 : // conflicts with normal connections
640 7920 : for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin(); i != myIncoming.rend(); i++) {
641 6305 : const NBEdge* from = *i;
642 20561 : for (int j = from->getNumLanes(); j-- > 0;) {
643 14256 : const std::vector<NBEdge::Connection>& connected = from->getConnectionsFromLane(j);
644 14256 : const int size = (int) connected.size();
645 32444 : for (int k = size; k-- > 0;) {
646 18188 : const NBEdge* to = connected[k].toEdge;
647 : bool foe = false;
648 38129 : for (const NBEdge* const e : crossing.edges) {
649 27975 : if (e == from || e == to) {
650 : foe = true;
651 : break;
652 : }
653 : }
654 18188 : foes += foe ? '1' : '0';
655 18188 : response += mustBrakeForCrossing(myJunction, from, to, crossing) || !foe ? '0' : '1';
656 : }
657 14256 : }
658 : }
659 1615 : pos++;
660 1615 : myResponse.push_back(response);
661 1615 : myFoes.push_back(foes);
662 1615 : myHaveVia.push_back(false);
663 1615 : return pos;
664 : }
665 :
666 :
667 : std::string
668 209192 : NBRequest::getResponseString(const NBEdge* const from, const NBEdge::Connection& c, const bool checkLaneFoes) const {
669 209192 : const NBEdge* const to = c.toEdge;
670 209192 : const int fromLane = c.fromLane;
671 209192 : const int toLane = c.toLane;
672 : int idx = 0;
673 209192 : if (to != nullptr) {
674 209192 : idx = getIndex(from, to);
675 : }
676 : std::string result;
677 209192 : const bool zipper = myJunction->getType() == SumoXMLNodeType::ZIPPER;
678 : // crossings
679 209192 : auto crossings = myJunction->getCrossings();
680 227380 : for (std::vector<NBNode::Crossing*>::const_reverse_iterator i = crossings.rbegin(); i != crossings.rend(); i++) {
681 18188 : result += mustBrakeForCrossing(myJunction, from, to, **i) ? '1' : '0';
682 : }
683 : // normal connections
684 848509 : for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin(); i != myIncoming.rend(); i++) {
685 : //const std::vector<NBEdge::Connection> &allConnections = (*i)->getConnections();
686 639317 : int noLanes = (*i)->getNumLanes();
687 1537636 : for (int j = noLanes; j-- > 0;) {
688 898319 : std::vector<NBEdge::Connection> connected = (*i)->getConnectionsFromLane(j);
689 898319 : int size = (int) connected.size();
690 3078219 : for (int k = size; k-- > 0;) {
691 2179900 : 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 2179779 : } 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 525785 : 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 1653994 : 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 3261588 : const bool hasLaneConflict = (!(checkLaneFoes || checkLaneFoesByClass(c, *i, connected[k])
741 1618624 : || checkLaneFoesByCooperation(from, c, *i, connected[k]))
742 1695371 : || laneConflict(from, to, toLane, *i, connected[k].toEdge, connected[k].toLane));
743 3307988 : if (((myForbids[idx2][idx] || (zipper && myForbids[idx][idx2])) && hasLaneConflict && !bidiConflict(*i, connected[k], from, c, false))
744 1315746 : || rightTurnConflict(from, c, *i, connected[k])
745 1315148 : || mergeConflict(from, c, *i, connected[k], zipper)
746 1314944 : || oppositeLeftTurnConflict(from, c, *i, connected[k], zipper)
747 1312292 : || indirectLeftTurnConflict(from, c, *i, connected[k], zipper)
748 1312292 : || bidiConflict(from, c, *i, connected[k], false)
749 : // the extra conflict could be specific to another connection within the same signal group
750 1312317 : || (myJunction->extraConflict(c.tlLinkIndex, connected[k].tlLinkIndex) && (myForbids[idx2][idx] || myForbids[idx][idx2]))
751 2966230 : || (myJunction->tlsStrandedConflict(from, c, *i, connected[k])
752 8397 : && laneConflict(from, to, toLane, *i, connected[k].toEdge, connected[k].toLane)
753 1667592 : && !OptionsCont::getOptions().getBool("tls.ignore-internal-junction-jam"))
754 : ) {
755 : result += '1';
756 : } else {
757 : result += '0';
758 : }
759 : }
760 : }
761 898319 : }
762 : }
763 209192 : return result;
764 209192 : }
765 :
766 :
767 : std::string
768 209192 : NBRequest::getFoesString(NBEdge* from, const NBEdge::Connection& c, const bool checkLaneFoes) const {
769 418384 : 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 209192 : auto crossings = myJunction->getCrossings();
777 227380 : for (std::vector<NBNode::Crossing*>::const_reverse_iterator i = crossings.rbegin(); i != crossings.rend(); i++) {
778 : bool foes = false;
779 38129 : for (EdgeVector::const_iterator it_e = (**i).edges.begin(); it_e != (**i).edges.end(); ++it_e) {
780 27975 : if ((*it_e) == from || (*it_e) == c.toEdge) {
781 : foes = true;
782 : break;
783 : }
784 : }
785 18188 : result += foes ? '1' : '0';
786 : }
787 : // normal connections
788 848509 : for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin(); i != myIncoming.rend(); i++) {
789 1537636 : for (int j = (*i)->getNumLanes() - 1; j >= 0; --j) {
790 898319 : const std::vector<NBEdge::Connection>& connected = (*i)->getConnectionsFromLane(j);
791 898319 : int size = (int) connected.size();
792 3078219 : for (int k = size; k-- > 0;) {
793 4297495 : const bool hasLaneConflict = (!(checkLaneFoes || checkLaneFoesByClass(c, *i, connected[k])
794 2132361 : || checkLaneFoesByCooperation(from, c, *i, connected[k]))
795 2229736 : || laneConflict(from, c.toEdge, c.toLane, *i, connected[k].toEdge, connected[k].toLane));
796 2877676 : if ((foes(from, c.toEdge, (*i), connected[k].toEdge) && hasLaneConflict)
797 1503743 : || rightTurnConflict(from, c, *i, connected[k])
798 1503145 : || myJunction->turnFoes(from, c.toEdge, c.fromLane, *i, connected[k].toEdge, connected[k].fromLane, lefthand)
799 1502483 : || mergeConflict(from, c, *i, connected[k], true)
800 1502087 : || oppositeLeftTurnConflict(from, c, *i, connected[k], true)
801 1496781 : || indirectLeftTurnConflict(from, c, *i, connected[k], true)
802 3676659 : || bidiConflict(from, c, *i, connected[k], true)
803 : ) {
804 : result += '1';
805 : } else {
806 : result += '0';
807 : }
808 : }
809 898319 : }
810 : }
811 209192 : return result;
812 209192 : }
813 :
814 :
815 : bool
816 2820053 : NBRequest::rightTurnConflict(const NBEdge* from, const NBEdge::Connection& con,
817 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon) const {
818 5639991 : return (!con.mayDefinitelyPass &&
819 2819938 : (NBNode::rightTurnConflict(from, con.toEdge, con.fromLane, prohibitorFrom, prohibitorCon.toEdge, prohibitorCon.fromLane)
820 : // reverse conflicht (override)
821 2818713 : || (prohibitorCon.mayDefinitelyPass &&
822 72 : NBNode::rightTurnConflict(prohibitorFrom, prohibitorCon.toEdge, prohibitorCon.fromLane, from, con.toEdge, con.fromLane))));
823 :
824 :
825 : }
826 :
827 :
828 : bool
829 4298410 : 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 1205996 : && con.toEdge == prohibitorCon.toEdge
833 4753911 : && ((con.toLane == prohibitorCon.toLane
834 332691 : && con.fromLane != prohibitorCon.fromLane
835 1463 : && !myJunction->isConstantWidthTransition())
836 : // this is actually a crossing rather than a merger
837 454042 : || (con.fromLane > prohibitorCon.fromLane && con.toLane < prohibitorCon.toLane)
838 454034 : || (con.fromLane < prohibitorCon.fromLane && con.toLane > prohibitorCon.toLane))) {
839 1475 : if (foes) {
840 : return true;
841 : }
842 883 : if (prohibitorCon.mayDefinitelyPass) {
843 : return true;
844 : }
845 880 : if (con.mayDefinitelyPass) {
846 : return false;
847 : }
848 880 : const bool bike = from->getPermissions(con.fromLane) == SVC_BICYCLE;
849 880 : const bool prohibitorBike = prohibitorFrom->getPermissions(prohibitorCon.fromLane) == SVC_BICYCLE;
850 880 : 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 846 : LinkDirection dir = myJunction->getDirection(from, con.toEdge);
858 846 : if (dir == LinkDirection::RIGHT || dir == LinkDirection::PARTRIGHT) {
859 535 : 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 4296935 : return false;
872 : }
873 : }
874 :
875 :
876 : bool
877 2817031 : NBRequest::oppositeLeftTurnConflict(const NBEdge* from, const NBEdge::Connection& con,
878 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon, bool foes) const {
879 2817031 : LinkDirection dir = myJunction->getDirection(from, con.toEdge);
880 : // XXX lefthand issue (solve via #4256)
881 2817031 : if (dir != LinkDirection::LEFT && dir != LinkDirection::PARTLEFT) {
882 : return false;
883 : }
884 579383 : dir = myJunction->getDirection(prohibitorFrom, prohibitorCon.toEdge);
885 579383 : if (dir != LinkDirection::LEFT && dir != LinkDirection::PARTLEFT) {
886 : return false;
887 : }
888 161963 : if (from == prohibitorFrom || NBRequest::foes(from, con.toEdge, prohibitorFrom, prohibitorCon.toEdge)) {
889 : // not an opposite pair
890 90447 : return false;
891 : }
892 :
893 71516 : const double width1 = MIN2(from->getLaneWidth(con.fromLane) / 2, OptionsCont::getOptions().getFloat("internal-junctions.vehicle-width") / 2);
894 71516 : const double width2 = prohibitorCon.toEdge->getLaneWidth(prohibitorCon.toLane) / 2;
895 : PositionVector shape = con.shape;
896 71516 : shape.append(con.viaShape);
897 : PositionVector otherShape = prohibitorCon.shape;
898 71516 : otherShape.append(prohibitorCon.viaShape);
899 71516 : if (shape.size() == 0 || otherShape.size() == 0) {
900 : // no internal lanes built
901 : return false;
902 : }
903 21944 : const double minDV = NBEdge::firstIntersection(shape, otherShape, width1, width2);
904 21944 : if (minDV < shape.length() - POSITION_EPS && minDV > POSITION_EPS) {
905 : // break symmetry using edge id
906 10612 : return foes || from->getID() < prohibitorFrom->getID();
907 : }
908 : return false;
909 71516 : }
910 :
911 : bool
912 3771277 : NBRequest::indirectLeftTurnConflict(const NBEdge* from, const NBEdge::Connection& con,
913 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon, bool foes) const {
914 3771277 : if (from == prohibitorFrom) {
915 1428597 : if (con.toEdge == prohibitorCon.toEdge) {
916 : return false;
917 851185 : } else if (con.indirectLeft) {
918 126 : LinkDirection dir = myJunction->getDirection(prohibitorFrom, prohibitorCon.toEdge);
919 126 : return (dir == LinkDirection::STRAIGHT);
920 851059 : } 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 3885735 : NBRequest::bidiConflict(const NBEdge* from, const NBEdge::Connection& con,
930 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon, bool foes) const {
931 3885735 : if (from == prohibitorFrom) {
932 : return false;
933 : }
934 2895536 : if (isRailway(from->getPermissions())) {
935 : // railways manage right-of-way via signals
936 : return false;
937 : }
938 1361387 : if ((foes && (from->getBidiEdge() == prohibitorCon.toEdge))
939 4229736 : || 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 3808098 : NBRequest::checkLaneFoesByClass(const NBEdge::Connection& con,
962 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon) const {
963 3808098 : if (con.toEdge != prohibitorCon.toEdge) {
964 : return false;
965 : }
966 1079564 : SVCPermissions svc = con.toEdge->getPermissions(con.toLane);
967 1079564 : 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 1079564 : 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 1079564 : || (((svc & SVC_PASSENGER) == 0) && ((svc2 & SVC_PASSENGER) != 0)));
972 : }
973 :
974 :
975 : bool
976 3750985 : NBRequest::checkLaneFoesByCooperation(const NBEdge* from, const NBEdge::Connection& con,
977 : const NBEdge* prohibitorFrom, const NBEdge::Connection& prohibitorCon) const {
978 3750985 : 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 4968800 : for (const NBEdge::Connection& c : from->getConnections()) {
987 3946349 : if (c.toEdge == con.toEdge) {
988 1484874 : fromTargetLanes.insert(c.toLane);
989 : }
990 : }
991 2414074 : for (const NBEdge::Connection& c : prohibitorFrom->getConnections()) {
992 2379974 : 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 125406 : NBRequest::laneConflict(const NBEdge* from, const NBEdge* to, int toLane,
1004 : const NBEdge* prohibitorFrom, const NBEdge* prohibitorTo, int prohibitorToLane) const {
1005 125406 : 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 107531 : double angle = NBHelpers::relAngle(
1012 : from->getAngleAtNode(from->getToNode()), to->getAngleAtNode(to->getFromNode()));
1013 107531 : if (angle == 180) {
1014 : angle = -180; // turnarounds are left turns
1015 : }
1016 107531 : const double prohibitorAngle = NBHelpers::relAngle(
1017 : prohibitorFrom->getAngleAtNode(prohibitorFrom->getToNode()), to->getAngleAtNode(to->getFromNode()));
1018 107531 : const bool rightOfProhibitor = prohibitorFrom->isTurningDirectionAt(to)
1019 107531 : || (angle > prohibitorAngle && !from->isTurningDirectionAt(to));
1020 107531 : return rightOfProhibitor ? toLane >= prohibitorToLane : toLane <= prohibitorToLane;
1021 : }
1022 :
1023 : int
1024 17007943 : NBRequest::getIndex(const NBEdge* const from, const NBEdge* const to) const {
1025 17007943 : EdgeVector::const_iterator fp = std::find(myIncoming.begin(), myIncoming.end(), from);
1026 17007943 : EdgeVector::const_iterator tp = std::find(myOutgoing.begin(), myOutgoing.end(), to);
1027 17007943 : if (fp == myIncoming.end() || tp == myOutgoing.end()) {
1028 : return -1;
1029 : }
1030 : // compute the index
1031 16851125 : 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 234438 : NBRequest::mustBrake(const NBEdge* const from, const NBEdge* const to, int fromLane, int toLane, bool includePedCrossings) const {
1056 234438 : NBEdge::Connection con(fromLane, const_cast<NBEdge*>(to), toLane);
1057 234438 : const int linkIndex = myJunction->getConnectionIndex(from, con);
1058 234438 : if (linkIndex >= 0 && (int)myResponse.size() > linkIndex) {
1059 212600 : std::string response = getResponse(linkIndex);
1060 212600 : if (!includePedCrossings) {
1061 328 : response = response.substr(0, response.size() - myJunction->getCrossings().size());
1062 : }
1063 212600 : if (response.find_first_of("1") == std::string::npos) {
1064 : return false;
1065 101920 : } 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 36550 : int idx2 = getIndex(from, to);
1074 36550 : 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 239883 : for (int idx1 = 0; idx1 < numLinks(); idx1++) {
1081 : //assert(myDone[idx1][idx2]);
1082 331200 : if (myDone[idx1][idx2] && myForbids[idx1][idx2]) {
1083 : return true;
1084 : }
1085 : }
1086 : // maybe we need to brake for a pedestrian crossing
1087 2698 : if (includePedCrossings) {
1088 2306 : auto crossings = myJunction->getCrossings();
1089 2960 : for (std::vector<NBNode::Crossing*>::const_reverse_iterator i = crossings.rbegin(); i != crossings.rend(); i++) {
1090 1472 : 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 1880 : const NBEdge::Connection& queryCon = from->getConnection(fromLane, to, toLane);
1098 1880 : LinkDirection dir = myJunction->getDirection(from, to);
1099 1880 : 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 9387 : for (EdgeVector::const_reverse_iterator i = myIncoming.rbegin(); i != myIncoming.rend(); i++) {
1108 7627 : int noLanes = (*i)->getNumLanes();
1109 22408 : for (int j = noLanes; j-- > 0;) {
1110 14794 : std::vector<NBEdge::Connection> connected = (*i)->getConnectionsFromLane(j);
1111 14794 : const int size = (int) connected.size();
1112 46241 : for (int k = size; k-- > 0;) {
1113 39468 : if ((*i) == from && fromLane != j
1114 35073 : && mergeConflict(from, queryCon, *i, connected[k], myJunction->getType() == SumoXMLNodeType::ZIPPER)) {
1115 : return true;
1116 : }
1117 : }
1118 14794 : }
1119 : }
1120 : // maybe we need to brake due to a zipper conflict
1121 1760 : 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 234438 : }
1131 :
1132 :
1133 : bool
1134 44294 : NBRequest::mustBrakeForCrossing(const NBNode* node, const NBEdge* const from, const NBEdge* const to, const NBNode::Crossing& crossing) {
1135 44294 : const LinkDirection dir = node->getDirection(from, to);
1136 44294 : const bool mustYield = dir == LinkDirection::LEFT || dir == LinkDirection::RIGHT;
1137 44294 : if (crossing.priority || mustYield) {
1138 77123 : for (const NBEdge* const e : crossing.edges) {
1139 : // left and right turns must yield to unprioritized crossings only on their destination edge
1140 53650 : 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 2182 : NBRequest::reportWarnings() {
1161 : // check if any errors occurred on build the link prohibitions
1162 2182 : if (myNotBuild != 0) {
1163 0 : WRITE_WARNING(toString(myNotBuild) + " of " + toString(myNotBuild + myGoodBuilds) + " prohibitions were not build.");
1164 : }
1165 2182 : }
1166 :
1167 :
1168 : void
1169 44274 : 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 134844 : for (const NBEdge* const e : myIncoming) {
1177 299762 : for (const NBEdge::Connection& con : e->getConnections()) {
1178 209192 : incomingCount[con.toEdge]++;
1179 209192 : approachedLanes[con.toEdge].insert(con.toLane);
1180 209192 : incomingEdges[con.toEdge].push_back(e);
1181 : }
1182 : }
1183 132673 : for (std::map<const NBEdge*, int>::iterator it = incomingCount.begin(); it != incomingCount.end(); ++it) {
1184 88399 : const NBEdge* const to = it->first;
1185 : // we cannot test against to->getNumLanes() since not all lanes may be used
1186 88399 : if ((int)approachedLanes[to].size() >= it->second) {
1187 37871 : const std::vector<const NBEdge*>& incoming = incomingEdges[to];
1188 : // make these connections mutually unconflicting
1189 86609 : for (const NBEdge* const e1 : incoming) {
1190 130984 : for (const NBEdge* const e2 : incoming) {
1191 82246 : 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 44274 : }
1203 :
1204 :
1205 : bool
1206 44456 : NBRequest::hasConflict() const {
1207 87610 : for (int i = 0; i < (int)myFoes.size(); i++) {
1208 63726 : if (hasConflictAtLink(i)) {
1209 : return true;
1210 : }
1211 : }
1212 : return false;
1213 : }
1214 :
1215 : bool
1216 64945 : NBRequest::hasConflictAtLink(int linkIndex) const {
1217 64945 : return myFoes[linkIndex].find_first_of("1") != std::string::npos;
1218 : }
1219 :
1220 : int
1221 290727 : NBRequest::numLinks() const {
1222 290727 : return (int)(myIncoming.size() * myOutgoing.size() + myJunction->getCrossings().size());
1223 : }
1224 :
1225 :
1226 : /****************************************************************************/
|
