1 package org.opentrafficsim.road.network.lane.conflict;
2
3 import java.util.ArrayList;
4 import java.util.Iterator;
5 import java.util.LinkedHashMap;
6 import java.util.List;
7 import java.util.Map;
8 import java.util.Set;
9 import java.util.SortedSet;
10 import java.util.TreeSet;
11 import java.util.concurrent.Executors;
12 import java.util.concurrent.ThreadPoolExecutor;
13 import java.util.concurrent.atomic.AtomicInteger;
14
15 import org.djunits.value.vdouble.scalar.Length;
16 import org.djutils.draw.line.Polygon2d;
17 import org.djutils.draw.point.Point2d;
18 import org.djutils.exceptions.Throw;
19 import org.djutils.immutablecollections.ImmutableMap;
20 import org.opentrafficsim.core.definitions.DefaultsNl;
21 import org.opentrafficsim.core.dsol.OtsSimulatorInterface;
22 import org.opentrafficsim.core.geometry.OtsGeometryException;
23 import org.opentrafficsim.core.geometry.OtsLine2d;
24 import org.opentrafficsim.core.network.Link;
25 import org.opentrafficsim.core.network.NetworkException;
26 import org.opentrafficsim.road.network.RoadNetwork;
27 import org.opentrafficsim.road.network.lane.CrossSectionElement;
28 import org.opentrafficsim.road.network.lane.CrossSectionLink;
29 import org.opentrafficsim.road.network.lane.Lane;
30 import org.opentrafficsim.road.network.lane.Shoulder;
31 import org.pmw.tinylog.Level;
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 public final class ConflictBuilder
52 {
53
54 private static AtomicInteger numberMergeConflicts = new AtomicInteger(0);
55
56
57 private static AtomicInteger numberSplitConflicts = new AtomicInteger(0);
58
59
60 private static AtomicInteger numberCrossConflicts = new AtomicInteger(0);
61
62
63 public static final WidthGenerator DEFAULT_WIDTH_GENERATOR = new RelativeWidthGenerator(0.8);
64
65
66
67
68 private ConflictBuilder()
69 {
70
71 }
72
73
74
75
76
77
78
79
80 public static void buildConflicts(final RoadNetwork network, final OtsSimulatorInterface simulator,
81 final WidthGenerator widthGenerator) throws OtsGeometryException
82 {
83 buildConflicts(network, simulator, widthGenerator, new LaneCombinationList(), new LaneCombinationList());
84 }
85
86
87
88
89
90
91
92
93
94
95 public static void buildConflicts(final RoadNetwork network, final OtsSimulatorInterface simulator,
96 final WidthGenerator widthGenerator, final LaneCombinationList ignoreList, final LaneCombinationList permittedList)
97 throws OtsGeometryException
98 {
99 buildConflicts(getLanes(network), simulator, widthGenerator, ignoreList, permittedList, null);
100 }
101
102
103
104
105
106
107 private static List<Lane> getLanes(final RoadNetwork network)
108 {
109 ImmutableMap<String, Link> links = network.getLinkMap();
110 List<Lane> lanes = new ArrayList<>();
111 for (String linkId : links.keySet())
112 {
113 Link link = links.get(linkId);
114 if (link instanceof CrossSectionLink)
115 {
116 for (CrossSectionElement element : ((CrossSectionLink) link).getCrossSectionElementList())
117 {
118 if (element instanceof Lane lane && !(element instanceof Shoulder))
119 {
120 lanes.add((Lane) element);
121 }
122 }
123 }
124 }
125 return lanes;
126 }
127
128
129
130
131
132
133
134
135 public static void buildConflicts(final List<Lane> lanes, final OtsSimulatorInterface simulator,
136 final WidthGenerator widthGenerator) throws OtsGeometryException
137 {
138 buildConflicts(lanes, simulator, widthGenerator, new LaneCombinationList(), new LaneCombinationList(), null);
139 }
140
141
142
143
144
145
146
147
148
149
150
151 public static void buildConflicts(final List<Lane> lanes, final OtsSimulatorInterface simulator,
152 final WidthGenerator widthGenerator, final LaneCombinationList ignoreList, final LaneCombinationList permittedList,
153 final String conflictId) throws OtsGeometryException
154 {
155 long totalCombinations = ((long) lanes.size()) * ((long) lanes.size() - 1) / 2;
156 simulator.getLogger().always().trace("GENERATING CONFLICTS (NON-PARALLEL MODE). {} COMBINATIONS", totalCombinations);
157 long lastReported = 0;
158 Map<Lane, OtsLine2d> leftEdges = new LinkedHashMap<>();
159 Map<Lane, OtsLine2d> rightEdges = new LinkedHashMap<>();
160
161 for (int i = 0; i < lanes.size(); i++)
162 {
163 long combinationsDone = totalCombinations - ((long) (lanes.size() - i)) * ((long) (lanes.size() - i)) / 2;
164 if (combinationsDone / 100000000 > lastReported)
165 {
166 simulator.getLogger().always()
167 .debug(String.format(
168 "generating conflicts at %.0f%% (generated %d merge conflicts, %d split "
169 + "conflicts, %d crossing conflicts)",
170 100.0 * combinationsDone / totalCombinations, numberMergeConflicts.get(),
171 numberSplitConflicts.get(), numberCrossConflicts.get()));
172 lastReported = combinationsDone / 100000000;
173 }
174 Lane lane1 = lanes.get(i);
175 Set<Lane> down1 = lane1.nextLanes(null);
176 Set<Lane> up1 = lane1.prevLanes(null);
177
178 for (int j = i + 1; j < lanes.size(); j++)
179 {
180 Lane lane2 = lanes.get(j);
181 if (ignoreList.contains(lane1, lane2))
182 {
183 continue;
184 }
185 boolean permitted = permittedList.contains(lane1, lane2);
186
187 Set<Lane> down2 = lane2.nextLanes(null);
188 Set<Lane> up2 = lane2.prevLanes(null);
189
190 try
191 {
192 buildConflicts(lane1, down1, up1, lane2, down2, up2, permitted, simulator, widthGenerator, leftEdges,
193 rightEdges, true, conflictId);
194 }
195 catch (NetworkException ne)
196 {
197 throw new RuntimeException("Conflict build with bad combination of types / rules.", ne);
198 }
199 }
200 }
201 simulator.getLogger().always()
202 .trace(String.format(
203 "generating conflicts complete (generated %d merge conflicts, %d split "
204 + "conflicts, %d crossing conflicts)",
205 numberMergeConflicts.get(), numberSplitConflicts.get(), numberCrossConflicts.get()));
206 }
207
208
209
210
211
212
213
214
215
216 @SuppressWarnings("checkstyle:parameternumber")
217 public static void buildConflicts(final Lane lane1, final Lane lane2, final OtsSimulatorInterface simulator,
218 final WidthGenerator widthGenerator) throws OtsGeometryException
219 {
220 buildConflicts(lane1, lane2, simulator, widthGenerator, false);
221 }
222
223
224
225
226
227
228
229
230
231
232 @SuppressWarnings("checkstyle:parameternumber")
233 public static void buildConflicts(final Lane lane1, final Lane lane2, final OtsSimulatorInterface simulator,
234 final WidthGenerator widthGenerator, final boolean permitted) throws OtsGeometryException
235 {
236 Set<Lane> down1 = lane1.nextLanes(null);
237 Set<Lane> up1 = lane1.prevLanes(null);
238 Set<Lane> down2 = lane2.nextLanes(null);
239 Set<Lane> up2 = lane2.prevLanes(null);
240 try
241 {
242 buildConflicts(lane1, down1, up1, lane2, down2, up2, permitted, simulator, widthGenerator, new LinkedHashMap<>(),
243 new LinkedHashMap<>(), true, null);
244 }
245 catch (NetworkException ne)
246 {
247 throw new RuntimeException("Conflict build with bad combination of types / rules.", ne);
248 }
249 }
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269 @SuppressWarnings({"checkstyle:parameternumber", "checkstyle:methodlength"})
270 static void buildConflicts(final Lane lane1, final Set<Lane> down1, final Set<Lane> up1, final Lane lane2,
271 final Set<Lane> down2, final Set<Lane> up2, final boolean permitted, final OtsSimulatorInterface simulator,
272 final WidthGenerator widthGenerator, final Map<Lane, OtsLine2d> leftEdges, final Map<Lane, OtsLine2d> rightEdges,
273 final boolean intersectionCheck, final String conflictId) throws OtsGeometryException, NetworkException
274 {
275
276 if (intersectionCheck)
277 {
278 if (!lane1.getContour().intersects(lane2.getContour()))
279 {
280 return;
281 }
282 }
283
284
285
286 String paddedConflictId = null == conflictId ? "" : (" in conflict group " + conflictId);
287
288 OtsLine2d left1;
289 OtsLine2d right1;
290 synchronized (lane1)
291 {
292 left1 = leftEdges.get(lane1);
293 right1 = rightEdges.get(lane1);
294 OtsLine2d line1 = lane1.getCenterLine();
295 if (null == left1)
296 {
297 left1 = line1.offsetLine(widthGenerator.getWidth(lane1, 0.0) / 2, widthGenerator.getWidth(lane1, 1.0) / 2);
298 leftEdges.put(lane1, left1);
299 }
300 if (null == right1)
301 {
302 right1 = line1.offsetLine(-widthGenerator.getWidth(lane1, 0.0) / 2, -widthGenerator.getWidth(lane1, 1.0) / 2);
303 rightEdges.put(lane1, right1);
304 }
305 }
306
307 OtsLine2d left2;
308 OtsLine2d right2;
309 synchronized (lane2)
310 {
311 left2 = leftEdges.get(lane2);
312 right2 = rightEdges.get(lane2);
313 OtsLine2d line2 = lane2.getCenterLine();
314 if (null == left2)
315 {
316 left2 = line2.offsetLine(widthGenerator.getWidth(lane2, 0.0) / 2, widthGenerator.getWidth(lane2, 1.0) / 2);
317 leftEdges.put(lane2, left2);
318 }
319 if (null == right2)
320 {
321 right2 = line2.offsetLine(-widthGenerator.getWidth(lane2, 0.0) / 2, -widthGenerator.getWidth(lane2, 1.0) / 2);
322 rightEdges.put(lane2, right2);
323 }
324 }
325
326
327 SortedSet<Intersection> intersections = Intersection.getIntersectionList(left1, left2, 0);
328 intersections.addAll(Intersection.getIntersectionList(left1, right2, 1));
329 intersections.addAll(Intersection.getIntersectionList(right1, left2, 2));
330 intersections.addAll(Intersection.getIntersectionList(right1, right2, 3));
331
332
333 Iterator<Lane> iterator1 = down1.iterator();
334 Iterator<Lane> iterator2 = down2.iterator();
335 boolean merge = false;
336 while (iterator1.hasNext() && !merge)
337 {
338 Lane next1 = iterator1.next();
339 while (iterator2.hasNext() && !merge)
340 {
341 Lane next2 = iterator2.next();
342 if (next1.equals(next2))
343 {
344
345 double fraction1 = Double.NaN;
346 double fraction2 = Double.NaN;
347 for (Intersection intersection : intersections)
348 {
349
350 if (intersection.getCombo() == 1 || intersection.getCombo() == 2)
351 {
352 fraction1 = intersection.getFraction1();
353 fraction2 = intersection.getFraction2();
354 }
355 }
356
357 Iterator<Intersection> iterator = intersections.iterator();
358 while (iterator.hasNext())
359 {
360 if (iterator.next().getFraction1() >= fraction1)
361 {
362 iterator.remove();
363 }
364 }
365 if (Double.isNaN(fraction1))
366 {
367 simulator.getLogger().always().info("Fixing fractions of merge conflict{}", paddedConflictId);
368 fraction1 = 0;
369 fraction2 = 0;
370 }
371
372 buildMergeConflict(lane1, fraction1, lane2, fraction2, simulator, widthGenerator, permitted);
373
374 merge = true;
375 }
376 }
377 }
378
379
380 iterator1 = up1.iterator();
381 iterator2 = up2.iterator();
382 boolean split = false;
383 while (iterator1.hasNext() && !split)
384 {
385 Lane prev1 = iterator1.next();
386 while (iterator2.hasNext() && !split)
387 {
388 Lane prev2 = iterator2.next();
389 if (prev1.equals(prev2))
390 {
391
392 double fraction1 = Double.NaN;
393 double fraction2 = Double.NaN;
394 for (Intersection intersection : intersections)
395 {
396
397 if (intersection.getCombo() == 1 || intersection.getCombo() == 2)
398 {
399 fraction1 = intersection.getFraction1();
400 fraction2 = intersection.getFraction2();
401 break;
402 }
403 }
404
405 Iterator<Intersection> iterator = intersections.iterator();
406 while (iterator.hasNext())
407 {
408 if (iterator.next().getFraction1() <= fraction1)
409 {
410 iterator.remove();
411 }
412 else
413 {
414
415 break;
416 }
417 }
418 if (Double.isNaN(fraction1))
419 {
420 simulator.getLogger().always().info("Fixing fractions of split conflict{}", paddedConflictId);
421 fraction1 = 1;
422 fraction2 = 1;
423 }
424
425 buildSplitConflict(lane1, fraction1, lane2, fraction2, simulator, widthGenerator);
426
427 split = true;
428 }
429 }
430 }
431
432
433 if (!lane1.getLink().equals(lane2.getLink()))
434 {
435 boolean[] crossed = new boolean[4];
436 Iterator<Intersection> iterator = intersections.iterator();
437 double f1Start = Double.NaN;
438 double f2Start = Double.NaN;
439 double f2End = Double.NaN;
440 while (iterator.hasNext())
441 {
442 Intersection intersection = iterator.next();
443
444 if (Double.isNaN(f1Start))
445 {
446 f1Start = intersection.getFraction1();
447 }
448 f2Start = Double.isNaN(f2Start) ? intersection.getFraction2() : Math.min(f2Start, intersection.getFraction2());
449 f2End = Double.isNaN(f2End) ? intersection.getFraction2() : Math.max(f2End, intersection.getFraction2());
450
451 crossed[intersection.getCombo()] = !crossed[intersection.getCombo()];
452
453 if ((crossed[0] && crossed[1] && crossed[2] && crossed[3])
454 || (!crossed[0] && !crossed[1] && !crossed[2] && !crossed[3]))
455 {
456 if (Double.isNaN(f1Start) || Double.isNaN(f2Start) || Double.isNaN(f2End))
457 {
458 simulator.getLogger().always().warn("NOT YET Fixing fractions of crossing conflict{}",
459 paddedConflictId);
460 }
461 buildCrossingConflict(lane1, f1Start, intersection.getFraction1(), lane2, f2Start, f2End, simulator,
462 widthGenerator, permitted);
463 f1Start = Double.NaN;
464 f2Start = Double.NaN;
465 f2End = Double.NaN;
466 }
467 }
468 }
469
470 }
471
472
473
474
475
476
477
478
479
480
481
482
483
484 @SuppressWarnings("checkstyle:parameternumber")
485 private static void buildMergeConflict(final Lane lane1, final double f1start, final Lane lane2, final double f2start,
486 final OtsSimulatorInterface simulator, final WidthGenerator widthGenerator, final boolean permitted)
487 throws NetworkException, OtsGeometryException
488 {
489
490
491 double f1end = 1.0;
492 double f2end = 1.0;
493
494
495 Length longitudinalPosition1 = lane1.getLength().times(f1start);
496 Length longitudinalPosition2 = lane2.getLength().times(f2start);
497 Length length1 = lane1.getLength().times(Math.abs(f1end - f1start));
498 Length length2 = lane2.getLength().times(Math.abs(f2end - f2start));
499
500
501 Polygon2d geometry1 = getGeometry(lane1, f1start, f1end, widthGenerator);
502 Polygon2d geometry2 = getGeometry(lane2, f2start, f2end, widthGenerator);
503
504
505 ConflictRule conflictRule;
506 if (lane1.getLink().getPriority().isBusStop() || lane2.getLink().getPriority().isBusStop())
507 {
508 Throw.when(lane1.getLink().getPriority().isBusStop() && lane2.getLink().getPriority().isBusStop(),
509 IllegalArgumentException.class, "Merge conflict between two links with bus stop priority not supported.");
510
511 conflictRule = new BusStopConflictRule(simulator, DefaultsNl.BUS);
512 }
513 else
514 {
515 conflictRule = new DefaultConflictRule();
516 }
517
518
519 Conflict.generateConflictPair(ConflictType.MERGE, conflictRule, permitted, lane1, longitudinalPosition1, length1,
520 geometry1, lane2, longitudinalPosition2, length2, geometry2, simulator);
521
522 numberMergeConflicts.incrementAndGet();
523 }
524
525
526
527
528
529
530
531
532
533
534
535
536 @SuppressWarnings("checkstyle:parameternumber")
537 private static void buildSplitConflict(final Lane lane1, final double f1end, final Lane lane2, final double f2end,
538 final OtsSimulatorInterface simulator, final WidthGenerator widthGenerator)
539 throws NetworkException, OtsGeometryException
540 {
541
542
543 double f1start = 0.0;
544 double f2start = 0.0;
545
546
547 Length longitudinalPosition1 = lane1.getLength().times(f1start);
548 Length longitudinalPosition2 = lane2.getLength().times(f2start);
549 Length length1 = lane1.getLength().times(Math.abs(f1end - f1start));
550 Length length2 = lane2.getLength().times(Math.abs(f2end - f2start));
551
552
553 Polygon2d geometry1 = getGeometry(lane1, f1start, f1end, widthGenerator);
554 Polygon2d geometry2 = getGeometry(lane2, f2start, f2end, widthGenerator);
555
556
557 Conflict.generateConflictPair(ConflictType.SPLIT, new SplitConflictRule(), false, lane1, longitudinalPosition1, length1,
558 geometry1, lane2, longitudinalPosition2, length2, geometry2, simulator);
559
560 numberSplitConflicts.incrementAndGet();
561 }
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577 @SuppressWarnings("checkstyle:parameternumber")
578 private static void buildCrossingConflict(final Lane lane1, final double f1start, final double f1end, final Lane lane2,
579 final double f2start, final double f2end, final OtsSimulatorInterface simulator,
580 final WidthGenerator widthGenerator, final boolean permitted) throws NetworkException, OtsGeometryException
581 {
582
583
584
585 double f1startDirected;
586 double f2startDirected;
587 if (f1end < f1start)
588 {
589 f1startDirected = f1end;
590 }
591 else
592 {
593 f1startDirected = f1start;
594 }
595 if (f2end < f2start)
596 {
597 f2startDirected = f2end;
598 }
599 else
600 {
601 f2startDirected = f2start;
602 }
603
604
605 Length longitudinalPosition1 = lane1.getLength().times(f1startDirected);
606 Length longitudinalPosition2 = lane2.getLength().times(f2startDirected);
607 Length length1 = lane1.getLength().times(Math.abs(f1end - f1start));
608 Length length2 = lane2.getLength().times(Math.abs(f2end - f2start));
609
610
611 Polygon2d geometry1 = getGeometry(lane1, f1start, f1end, widthGenerator);
612 Polygon2d geometry2 = getGeometry(lane2, f2start, f2end, widthGenerator);
613
614
615 ConflictRule conflictRule;
616 if (lane1.getLink().getPriority().isBusStop() || lane2.getLink().getPriority().isBusStop())
617 {
618 Throw.when(lane1.getLink().getPriority().isBusStop() && lane2.getLink().getPriority().isBusStop(),
619 IllegalArgumentException.class, "Merge conflict between two links with bus stop priority not supported.");
620
621 conflictRule = new BusStopConflictRule(simulator, DefaultsNl.BUS);
622 }
623 else
624 {
625 conflictRule = new DefaultConflictRule();
626 }
627
628
629 Conflict.generateConflictPair(ConflictType.CROSSING, conflictRule, permitted, lane1, longitudinalPosition1, length1,
630 geometry1, lane2, longitudinalPosition2, length2, geometry2, simulator);
631
632 numberCrossConflicts.incrementAndGet();
633 }
634
635
636
637
638
639
640
641
642
643
644 private static Polygon2d getGeometry(final Lane lane, final double fStart, final double fEnd,
645 final WidthGenerator widthGenerator) throws OtsGeometryException
646 {
647
648 double f1;
649 double f2;
650 if (fEnd > fStart)
651 {
652 f1 = fStart;
653 f2 = fEnd;
654 }
655 else
656 {
657 f1 = fEnd;
658 f2 = fStart;
659 }
660 if (Math.abs(f1 - f2) < 1E-8)
661 {
662 lane.getLink().getSimulator().getLogger().always()
663 .debug("f1 (" + f1 + ") equals f2 (" + f2 + "); problematic lane is " + lane.toString());
664
665 if (f1 > 0)
666 {
667 f1 = f1 - f1 / 1000;
668 }
669 else
670 {
671 f2 = f2 + f2 / 1000;
672 }
673 }
674 OtsLine2d centerLine = lane.getCenterLine().extractFractional(f1, f2);
675 OtsLine2d left = centerLine.offsetLine(widthGenerator.getWidth(lane, f1) / 2, widthGenerator.getWidth(lane, f2) / 2);
676 OtsLine2d right =
677 centerLine.offsetLine(-widthGenerator.getWidth(lane, f1) / 2, -widthGenerator.getWidth(lane, f2) / 2).reverse();
678 Point2d[] points = new Point2d[left.size() + right.size()];
679 System.arraycopy(left.getPoints(), 0, points, 0, left.size());
680 System.arraycopy(right.getPoints(), 0, points, left.size(), right.size());
681 return new Polygon2d(points);
682 }
683
684
685
686
687
688
689
690
691
692
693
694
695
696 private static class Intersection implements Comparable<Intersection>
697 {
698
699
700 private final double fraction1;
701
702
703 private final double fraction2;
704
705
706 private final int combo;
707
708
709
710
711
712
713 Intersection(final double fraction1, final double fraction2, final int combo)
714 {
715 this.fraction1 = fraction1;
716 this.fraction2 = fraction2;
717 this.combo = combo;
718 }
719
720
721
722
723 public final double getFraction1()
724 {
725 return this.fraction1;
726 }
727
728
729
730
731 public final double getFraction2()
732 {
733 return this.fraction2;
734 }
735
736
737
738
739 public final int getCombo()
740 {
741 return this.combo;
742 }
743
744
745 @Override
746 public int compareTo(final Intersection o)
747 {
748 int out = Double.compare(this.fraction1, o.fraction1);
749 if (out != 0)
750 {
751 return out;
752 }
753 out = Double.compare(this.fraction2, o.fraction2);
754 if (out != 0)
755 {
756 return out;
757 }
758 return Integer.compare(this.combo, o.combo);
759 }
760
761
762 @Override
763 public int hashCode()
764 {
765 final int prime = 31;
766 int result = 1;
767 result = prime * result + this.combo;
768 long temp;
769 temp = Double.doubleToLongBits(this.fraction1);
770 result = prime * result + (int) (temp ^ (temp >>> 32));
771 temp = Double.doubleToLongBits(this.fraction2);
772 result = prime * result + (int) (temp ^ (temp >>> 32));
773 return result;
774 }
775
776
777 @Override
778 public boolean equals(final Object obj)
779 {
780 if (this == obj)
781 {
782 return true;
783 }
784 if (obj == null)
785 {
786 return false;
787 }
788 if (getClass() != obj.getClass())
789 {
790 return false;
791 }
792 Intersection other = (Intersection) obj;
793 if (this.combo != other.combo)
794 {
795 return false;
796 }
797 if (Double.doubleToLongBits(this.fraction1) != Double.doubleToLongBits(other.fraction1))
798 {
799 return false;
800 }
801 if (Double.doubleToLongBits(this.fraction2) != Double.doubleToLongBits(other.fraction2))
802 {
803 return false;
804 }
805 return true;
806 }
807
808
809
810
811
812
813
814
815
816 public static SortedSet<Intersection> getIntersectionList(final OtsLine2d line1, final OtsLine2d line2, final int combo)
817 throws OtsGeometryException
818 {
819 SortedSet<Intersection> out = new TreeSet<>();
820 double cumul1 = 0.0;
821 Point2d start1 = null;
822 Point2d end1 = line1.get(0);
823 for (int i = 0; i < line1.size() - 1; i++)
824 {
825 start1 = end1;
826 end1 = line1.get(i + 1);
827
828 double cumul2 = 0.0;
829 Point2d start2 = null;
830 Point2d end2 = line2.get(0);
831
832 for (int j = 0; j < line2.size() - 1; j++)
833 {
834 start2 = end2;
835 end2 = line2.get(j + 1);
836
837 Point2d p = Point2d.intersectionOfLineSegments(start1, end1, start2, end2);
838 if (p != null)
839 {
840
841 double dx = p.x - start1.x;
842 double dy = p.y - start1.y;
843 double length1 = cumul1 + Math.hypot(dx, dy);
844 dx = p.x - start2.x;
845 dy = p.y - start2.y;
846 double length2 = cumul2 + Math.hypot(dx, dy);
847 out.add(new Intersection(length1 / line1.getLength().si, length2 / line2.getLength().si, combo));
848 }
849
850 double dx = end2.x - start2.x;
851 double dy = end2.y - start2.y;
852 cumul2 += Math.hypot(dx, dy);
853 }
854
855 double dx = end1.x - start1.x;
856 double dy = end1.y - start1.y;
857 cumul1 += Math.hypot(dx, dy);
858 }
859
860 return out;
861 }
862
863
864 @Override
865 public String toString()
866 {
867 return "Intersection [fraction1=" + this.fraction1 + ", fraction2=" + this.fraction2 + ", combo=" + this.combo
868 + "]";
869 }
870
871 }
872
873
874
875
876
877
878
879
880
881
882
883
884 public interface WidthGenerator
885 {
886
887
888
889
890
891
892
893 double getWidth(Lane lane, double fraction);
894
895 }
896
897
898
899
900
901
902
903
904
905
906
907
908 public static class FixedWidthGenerator implements WidthGenerator
909 {
910
911
912 private final double width;
913
914
915
916
917
918 public FixedWidthGenerator(final Length width)
919 {
920 this.width = width.si;
921 }
922
923
924 @Override
925 public final double getWidth(final Lane lane, final double fraction)
926 {
927 return this.width;
928 }
929
930
931 @Override
932 public final String toString()
933 {
934 return "FixedWidthGenerator [width=" + this.width + "]";
935 }
936
937 }
938
939
940
941
942
943
944
945
946
947
948
949
950 public static class RelativeWidthGenerator implements WidthGenerator
951 {
952
953
954 private final double factor;
955
956
957
958
959
960 public RelativeWidthGenerator(final double factor)
961 {
962 this.factor = factor;
963 }
964
965
966 @Override
967 public final double getWidth(final Lane lane, final double fraction)
968 {
969 return lane.getWidth(fraction).si * this.factor;
970 }
971
972
973 @Override
974 public final String toString()
975 {
976 return "RelativeWidthGenerator [factor=" + this.factor + "]";
977 }
978
979 }
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996 public static void buildConflictsParallel(final RoadNetwork network, final OtsSimulatorInterface simulator,
997 final WidthGenerator widthGenerator) throws OtsGeometryException
998 {
999 buildConflictsParallel(network, simulator, widthGenerator, new LaneCombinationList(), new LaneCombinationList());
1000 }
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011 public static void buildConflictsParallel(final RoadNetwork network, final OtsSimulatorInterface simulator,
1012 final WidthGenerator widthGenerator, final LaneCombinationList ignoreList, final LaneCombinationList permittedList)
1013 throws OtsGeometryException
1014 {
1015 buildConflictsParallelBig(getLanes(network), simulator, widthGenerator, ignoreList, permittedList);
1016 }
1017
1018
1019
1020
1021
1022
1023
1024
1025 public static void buildConflictsParallel(final List<Lane> lanes, final OtsSimulatorInterface simulator,
1026 final WidthGenerator widthGenerator) throws OtsGeometryException
1027 {
1028 buildConflictsParallelBig(lanes, simulator, widthGenerator, new LaneCombinationList(), new LaneCombinationList());
1029 }
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040 public static void buildConflictsParallelSmall(final List<Lane> lanes, final OtsSimulatorInterface simulator,
1041 final WidthGenerator widthGenerator, final LaneCombinationList ignoreList, final LaneCombinationList permittedList)
1042 throws OtsGeometryException
1043 {
1044 long totalCombinations = ((long) lanes.size()) * ((long) lanes.size() - 1) / 2;
1045 System.out.println("PARALLEL GENERATING OF CONFLICTS (SMALL JOBS). " + totalCombinations + " COMBINATIONS");
1046 long lastReported = 0;
1047 Map<Lane, OtsLine2d> leftEdges = new LinkedHashMap<>();
1048 Map<Lane, OtsLine2d> rightEdges = new LinkedHashMap<>();
1049
1050
1051 int cores = Runtime.getRuntime().availableProcessors();
1052 System.out.println("USING " + cores + " CORES");
1053 ThreadPoolExecutor executor = (ThreadPoolExecutor) Executors.newFixedThreadPool(cores);
1054 AtomicInteger numberOfJobs = new AtomicInteger(0);
1055 final int maxqueue = 2 * cores;
1056
1057 for (int i = 0; i < lanes.size(); i++)
1058 {
1059 long combinationsDone = totalCombinations - ((long) (lanes.size() - i)) * ((long) (lanes.size() - i - 1)) / 2;
1060 if (combinationsDone / 100000000 > lastReported)
1061 {
1062 simulator.getLogger().always()
1063 .debug(String.format(
1064 "generating conflicts at %.0f%% (generated %d merge conflicts, %d split "
1065 + "conflicts, %d crossing conflicts)",
1066 100.0 * combinationsDone / totalCombinations, numberMergeConflicts.get(),
1067 numberSplitConflicts.get(), numberCrossConflicts.get()));
1068 lastReported = combinationsDone / 100000000;
1069 }
1070 Lane lane1 = lanes.get(i);
1071 Set<Lane> down1 = lane1.nextLanes(null);
1072 Set<Lane> up1 = lane1.prevLanes(null);
1073
1074 for (int j = i + 1; j < lanes.size(); j++)
1075 {
1076 Lane lane2 = lanes.get(j);
1077 if (ignoreList.contains(lane1, lane2))
1078 {
1079 continue;
1080 }
1081
1082 try
1083 {
1084 if (!lane1.getContour().intersects(lane2.getContour()))
1085 {
1086 continue;
1087 }
1088 }
1089 catch (Exception e)
1090 {
1091 System.err.println("Contour problem - lane1 = [" + lane1.getFullId() + "], lane2 = [" + lane2.getFullId()
1092 + "]; skipped");
1093 continue;
1094 }
1095
1096 boolean permitted = permittedList.contains(lane1, lane2);
1097
1098 while (numberOfJobs.get() > maxqueue)
1099 {
1100 try
1101 {
1102 Thread.sleep(1);
1103 }
1104 catch (InterruptedException exception)
1105 {
1106
1107 }
1108 }
1109 numberOfJobs.incrementAndGet();
1110 Set<Lane> down2 = lane2.nextLanes(null);
1111 Set<Lane> up2 = lane2.prevLanes(null);
1112 ConflictBuilderRecordSmall cbr = new ConflictBuilderRecordSmall(lane1, down1, up1, lane2, down2, up2, permitted,
1113 simulator, widthGenerator, leftEdges, rightEdges);
1114 executor.execute(new CbrTaskSmall(numberOfJobs, cbr));
1115 }
1116 }
1117
1118 long time = System.currentTimeMillis();
1119
1120 while (numberOfJobs.get() > 0 && System.currentTimeMillis() - time < 60000)
1121 {
1122 try
1123 {
1124 Thread.sleep(10);
1125 }
1126 catch (InterruptedException exception)
1127 {
1128
1129 }
1130 }
1131
1132 executor.shutdown();
1133 while (!executor.isTerminated())
1134 {
1135 try
1136 {
1137 Thread.sleep(1);
1138 }
1139 catch (InterruptedException exception)
1140 {
1141
1142 }
1143 }
1144
1145 simulator.getLogger().always()
1146 .debug(String.format(
1147 "generating conflicts complete (generated %d merge conflicts, %d split "
1148 + "conflicts, %d crossing conflicts)",
1149 numberMergeConflicts.get(), numberSplitConflicts.get(), numberCrossConflicts.get()));
1150 }
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161 public static void buildConflictsParallelBig(final List<Lane> lanes, final OtsSimulatorInterface simulator,
1162 final WidthGenerator widthGenerator, final LaneCombinationList ignoreList, final LaneCombinationList permittedList)
1163 throws OtsGeometryException
1164 {
1165 long totalCombinations = ((long) lanes.size()) * ((long) lanes.size() - 1) / 2;
1166 System.out.println("PARALLEL GENERATING OF CONFLICTS (BIG JOBS). " + totalCombinations + " COMBINATIONS");
1167 long lastReported = 0;
1168 Map<Lane, OtsLine2d> leftEdges = new LinkedHashMap<>();
1169 Map<Lane, OtsLine2d> rightEdges = new LinkedHashMap<>();
1170
1171
1172 int cores = Runtime.getRuntime().availableProcessors();
1173 System.out.println("USING " + cores + " CORES");
1174 ThreadPoolExecutor executor = (ThreadPoolExecutor) Executors.newFixedThreadPool(cores);
1175 AtomicInteger numberOfJobs = new AtomicInteger(0);
1176 final int maxqueue = 200;
1177
1178 for (int i = 0; i < lanes.size(); i++)
1179 {
1180 long combinationsDone = totalCombinations - ((long) (lanes.size() - i)) * ((long) (lanes.size() - i - 1)) / 2;
1181 if (combinationsDone / 100000000 > lastReported)
1182 {
1183 simulator.getLogger().always()
1184 .debug(String.format(
1185 "generating conflicts at %.0f%% (generated %d merge conflicts, %d split "
1186 + "conflicts, %d crossing conflicts)",
1187 100.0 * combinationsDone / totalCombinations, numberMergeConflicts.get(),
1188 numberSplitConflicts.get(), numberCrossConflicts.get()));
1189 lastReported = combinationsDone / 100000000;
1190 }
1191
1192 while (numberOfJobs.get() > maxqueue)
1193 {
1194 try
1195 {
1196 Thread.sleep(0, 10);
1197 }
1198 catch (InterruptedException exception)
1199 {
1200
1201 }
1202 }
1203 numberOfJobs.incrementAndGet();
1204
1205 ConflictBuilderRecordBig cbr = new ConflictBuilderRecordBig(i, lanes, ignoreList, permittedList, simulator,
1206 widthGenerator, leftEdges, rightEdges);
1207 executor.execute(new CbrTaskBig(numberOfJobs, cbr));
1208
1209 }
1210
1211 long time = System.currentTimeMillis();
1212
1213 while (numberOfJobs.get() > 0 && System.currentTimeMillis() - time < 60000)
1214 {
1215 try
1216 {
1217 Thread.sleep(10);
1218 }
1219 catch (InterruptedException exception)
1220 {
1221
1222 }
1223 }
1224
1225 executor.shutdown();
1226 while (!executor.isTerminated())
1227 {
1228 try
1229 {
1230 Thread.sleep(1);
1231 }
1232 catch (InterruptedException exception)
1233 {
1234
1235 }
1236 }
1237
1238 simulator.getLogger().always()
1239 .debug(String.format(
1240 "generating conflicts complete (generated %d merge conflicts, %d split "
1241 + "conflicts, %d crossing conflicts)",
1242 numberMergeConflicts.get(), numberSplitConflicts.get(), numberCrossConflicts.get()));
1243 }
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254 public static void buildConflictsParallel(final RoadNetwork network, final Map<String, Set<Link>> conflictCandidateMap,
1255 final OtsSimulatorInterface simulator, final WidthGenerator widthGenerator) throws OtsGeometryException
1256 {
1257 for (String conflictId : conflictCandidateMap.keySet())
1258 {
1259
1260 List<Lane> lanes = new ArrayList<>();
1261 for (Link link : conflictCandidateMap.get(conflictId))
1262 {
1263 if (link instanceof CrossSectionLink)
1264 {
1265 for (CrossSectionElement element : ((CrossSectionLink) link).getCrossSectionElementList())
1266 {
1267 if (element instanceof Lane lane && !(element instanceof Shoulder))
1268 {
1269 lanes.add((Lane) element);
1270 }
1271 }
1272 }
1273 }
1274
1275
1276 buildConflicts(lanes, simulator, widthGenerator, new LaneCombinationList(), new LaneCombinationList(), conflictId);
1277 simulator.getLogger().setAllLogLevel(Level.DEBUG);
1278 }
1279 }
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292 static class CbrTaskSmall implements Runnable
1293 {
1294
1295 final ConflictBuilderRecordSmall cbr;
1296
1297
1298 final AtomicInteger nrOfJobs;
1299
1300
1301
1302
1303
1304
1305 CbrTaskSmall(final AtomicInteger nrOfJobs, final ConflictBuilderRecordSmall cbr)
1306 {
1307 this.nrOfJobs = nrOfJobs;
1308 this.cbr = cbr;
1309 }
1310
1311
1312 @Override
1313 public void run()
1314 {
1315 try
1316 {
1317 buildConflicts(this.cbr.lane1, this.cbr.down1, this.cbr.up1, this.cbr.lane2, this.cbr.down2, this.cbr.up2,
1318 this.cbr.permitted, this.cbr.simulator, this.cbr.widthGenerator, this.cbr.leftEdges,
1319 this.cbr.rightEdges, false, null);
1320 }
1321 catch (NetworkException | OtsGeometryException ne)
1322 {
1323 throw new RuntimeException("Conflict build with bad combination of types / rules.", ne);
1324 }
1325 this.nrOfJobs.decrementAndGet();
1326 }
1327 }
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351 @SuppressWarnings("checkstyle:visibilitymodifier")
1352 static record ConflictBuilderRecordSmall(Lane lane1, Set<Lane> down1, Set<Lane> up1, Lane lane2, Set<Lane> down2,
1353 Set<Lane> up2, boolean permitted, OtsSimulatorInterface simulator, WidthGenerator widthGenerator,
1354 Map<Lane, OtsLine2d> leftEdges, Map<Lane, OtsLine2d> rightEdges)
1355 {
1356 }
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370 static class CbrTaskBig implements Runnable
1371 {
1372
1373 final ConflictBuilderRecordBig cbr;
1374
1375
1376 final AtomicInteger nrOfJobs;
1377
1378
1379
1380
1381
1382
1383 CbrTaskBig(final AtomicInteger nrOfJobs, final ConflictBuilderRecordBig cbr)
1384 {
1385 this.nrOfJobs = nrOfJobs;
1386 this.cbr = cbr;
1387 }
1388
1389
1390 @Override
1391 public void run()
1392 {
1393 try
1394 {
1395 Lane lane1 = this.cbr.lanes.get(this.cbr.starti);
1396 Set<Lane> up1 = lane1.prevLanes(null);
1397 Set<Lane> down1 = lane1.nextLanes(null);
1398 for (int j = this.cbr.starti + 1; j < this.cbr.lanes.size(); j++)
1399 {
1400 Lane lane2 = this.cbr.lanes.get(j);
1401 if (this.cbr.ignoreList.contains(lane1, lane2))
1402 {
1403 continue;
1404 }
1405
1406 try
1407 {
1408 if (!lane1.getContour().intersects(lane2.getContour()))
1409 {
1410 continue;
1411 }
1412 }
1413 catch (Exception e)
1414 {
1415 System.err.println("Contour problem - lane1 = [" + lane1.getFullId() + "], lane2 = ["
1416 + lane2.getFullId() + "]; skipped");
1417 continue;
1418 }
1419
1420 boolean permitted = this.cbr.permittedList.contains(lane1, lane2);
1421
1422 Set<Lane> down2 = lane2.nextLanes(null);
1423 Set<Lane> up2 = lane2.prevLanes(null);
1424
1425 try
1426 {
1427 buildConflicts(lane1, down1, up1, lane2, down2, up2, permitted, this.cbr.simulator,
1428 this.cbr.widthGenerator, this.cbr.leftEdges, this.cbr.rightEdges, false, null);
1429 }
1430 catch (NetworkException | OtsGeometryException ne)
1431 {
1432 lane2.getLink().getSimulator().getLogger().always().error(ne,
1433 "Conflict build with bad combination of types / rules.");
1434 }
1435 }
1436
1437 }
1438 catch (Exception e)
1439 {
1440 e.printStackTrace();
1441 }
1442 this.nrOfJobs.decrementAndGet();
1443 }
1444 }
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466 @SuppressWarnings("checkstyle:visibilitymodifier")
1467 static record ConflictBuilderRecordBig(int starti, List<Lane> lanes, LaneCombinationList ignoreList,
1468 LaneCombinationList permittedList, OtsSimulatorInterface simulator, WidthGenerator widthGenerator,
1469 Map<Lane, OtsLine2d> leftEdges, Map<Lane, OtsLine2d> rightEdges)
1470 {
1471 }
1472
1473 }