ConflictBuilder.java

  1. package org.opentrafficsim.road.network.lane.conflict;

  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;

  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;

  33. /**
  34.  * Conflict builder allows automatic generation of conflicts. This happens based on the geometry of lanes. Parallel execution
  35.  * allows this algorithm to run faster. There are two parallel implementations:
  36.  * <ul>
  37.  * <li>Small; between two lanes.</li>
  38.  * <li>Big; between one particular lane, and all lanes further in a list (i.e. similar to a triangular matrix procedure).</li>
  39.  * </ul>
  40.  * <p>
  41.  * Copyright (c) 2013-2024 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved. <br>
  42.  * BSD-style license. See <a href="https://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
  43.  * </p>
  44.  * @author <a href="https://github.com/averbraeck">Alexander Verbraeck</a>
  45.  * @author <a href="https://tudelft.nl/staff/p.knoppers-1">Peter Knoppers</a>
  46.  * @author <a href="https://github.com/wjschakel">Wouter Schakel</a>
  47.  * @see <a href="https://opentrafficsim.org/manual/99-appendices/conflict-areas/">Generation of conflics</a>
  48.  */
  49. // TODO use z-coordinate for intersections of lines
  50. // TODO use remove big parallel type, and use fibers for small tasks.
  51. public final class ConflictBuilder
  52. {
  53.     /** number of merge onflicts. */
  54.     private static AtomicInteger numberMergeConflicts = new AtomicInteger(0);

  56.     /** number of split onflicts. */
  57.     private static AtomicInteger numberSplitConflicts = new AtomicInteger(0);

  59.     /** number of cross onflicts. */
  60.     private static AtomicInteger numberCrossConflicts = new AtomicInteger(0);

  62.     /** Default width generator for conflicts which uses 80% of the lane width. */
  63.     public static final WidthGenerator DEFAULT_WIDTH_GENERATOR = new RelativeWidthGenerator(0.8);

  65.     /**
  66.      * Empty constructor.
  67.      */
  68.     private ConflictBuilder()
  69.     {
  70.         //
  71.     }

  73.     /**
  74.      * Build conflicts on network.
  75.      * @param network RoadNetwork; network
  76.      * @param simulator OtsSimulatorInterface; simulator
  77.      * @param widthGenerator WidthGenerator; width generator
  78.      * @throws OtsGeometryException in case of geometry exception
  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.     }

  86.     /**
  87.      * Build conflicts on network.
  88.      * @param network RoadNetwork; network
  89.      * @param simulator OtsSimulatorInterface; simulator
  90.      * @param widthGenerator WidthGenerator; width generator
  91.      * @param ignoreList LaneCombinationList; lane combinations to ignore
  92.      * @param permittedList LaneCombinationList; lane combinations that are permitted by traffic control
  93.      * @throws OtsGeometryException in case of geometry exception
  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.     }

  102.     /**
  103.      * Returns all the lanes in the network.
  104.      * @param network RoadNetwork; network.
  105.      * @return List&lt;Lane&gt;; list if all lanes.
  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.     }

  128.     /**
  129.      * Build conflicts on list of lanes.
  130.      * @param lanes List&lt;Lane&gt;; lanes
  131.      * @param simulator OtsSimulatorInterface; simulator
  132.      * @param widthGenerator WidthGenerator; width generator
  133.      * @throws OtsGeometryException in case of geometry exception
  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.     }

  141.     /**
  142.      * Build conflicts on list of lanes.
  143.      * @param lanes List&lt;Lane&gt;; list of Lanes
  144.      * @param simulator OtsSimulatorInterface; the simulator
  145.      * @param widthGenerator WidthGenerator; the width generator
  146.      * @param ignoreList LaneCombinationList; lane combinations to ignore
  147.      * @param permittedList LaneCombinationList; lane combinations that are permitted by traffic control
  148.      * @param conflictId String; identification of the conflict (null value permitted)
  149.      * @throws OtsGeometryException in case of geometry exception
  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<>();

  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);

  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);

  187.                 Set<Lane> down2 = lane2.nextLanes(null);
  188.                 Set<Lane> up2 = lane2.prevLanes(null);
  189.                 // See if conflict needs to be build, and build if so
  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.     }

  208.     /**
  209.      * Build conflict on single lane pair. Connecting lanes are determined.
  210.      * @param lane1 Lane; lane 1
  211.      * @param lane2 Lane; lane 2
  212.      * @param simulator OtsSimulatorInterface; simulator
  213.      * @param widthGenerator WidthGenerator; width generator
  214.      * @throws OtsGeometryException in case of geometry exception
  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.     }

  223.     /**
  224.      * Build conflict on single lane pair. Connecting lanes are determined.
  225.      * @param lane1 Lane; lane 1
  226.      * @param lane2 Lane; lane 2
  227.      * @param simulator OtsSimulatorInterface; simulator
  228.      * @param widthGenerator WidthGenerator; width generator
  229.      * @param permitted boolean; conflict permitted by traffic control
  230.      * @throws OtsGeometryException in case of geometry exception
  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.     }

  251.     /**
  252.      * Build conflicts on single lane pair.
  253.      * @param lane1 Lane; lane 1
  254.      * @param down1 Set&lt;Lane&gt;; downstream lanes 1
  255.      * @param up1 Set&lt;Lane&gt;; upstream lanes 1
  256.      * @param lane2 Lane; lane 2
  257.      * @param down2 Set&lt;Lane&gt;; downstream lane 2
  258.      * @param up2 Set&lt;Lane&gt;; upstream lanes 2
  259.      * @param permitted boolean; conflict permitted by traffic control
  260.      * @param simulator OtsSimulatorInterface; simulator
  261.      * @param widthGenerator WidthGenerator; width generator
  262.      * @param leftEdges Map&lt;Lane, OtsLine2d&gt;; cache of left edge lines
  263.      * @param rightEdges Map&lt;Lane, OtsLine2d&gt;; cache of right edge lines
  264.      * @param intersectionCheck indicate whether we have to do a contour intersection check still
  265.      * @param conflictId String; identification of the conflict (may be null)
  266.      * @throws OtsGeometryException in case of geometry exception
  267.      * @throws NetworkException if the combination of conflict type and both conflict rules is not correct
  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.         // Quick contour check, skip if not overlapping -- Don't repeat if it has taken place
  276.         if (intersectionCheck)
  277.         {
  278.             if (!lane1.getContour().intersects(lane2.getContour()))
  279.             {
  280.                 return;
  281.             }
  282.         }

  284.         // TODO: we cache, but the width generator may be different

  286.         String paddedConflictId = null == conflictId ? "" : (" in conflict group " + conflictId);
  287.         // Get left and right lines at specified width
  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.         }

  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.         }

  326.         // Get list of all intersection fractions
  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));

  332.         // Create merge
  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.                     // Same downstream lane, so a merge
  345.                     double fraction1 = Double.NaN;
  346.                     double fraction2 = Double.NaN;
  347.                     for (Intersection intersection : intersections)
  348.                     {
  349.                         // Only consider left/right and right/left intersections (others may or may not be at the end)
  350.                         if (intersection.getCombo() == 1 || intersection.getCombo() == 2)
  351.                         {
  352.                             fraction1 = intersection.getFraction1();
  353.                             fraction2 = intersection.getFraction2();
  354.                         }
  355.                     }
  356.                     // Remove all intersections beyond this point, these are the result of line starts/ends matching
  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.                     // Build conflict
  372.                     buildMergeConflict(lane1, fraction1, lane2, fraction2, simulator, widthGenerator, permitted);
  373.                     // Skip loop for efficiency, and do not create multiple merges in case of multiple same downstream lanes
  374.                     merge = true;
  375.                 }
  376.             }
  377.         }

  379.         // Create split
  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.                     // Same upstream lane, so a split
  392.                     double fraction1 = Double.NaN;
  393.                     double fraction2 = Double.NaN;
  394.                     for (Intersection intersection : intersections)
  395.                     {
  396.                         // Only consider left/right and right/left intersections (others may or may not be at the start)
  397.                         if (intersection.getCombo() == 1 || intersection.getCombo() == 2)
  398.                         {
  399.                             fraction1 = intersection.getFraction1();
  400.                             fraction2 = intersection.getFraction2();
  401.                             break; // Split so first, not last
  402.                         }
  403.                     }
  404.                     // Remove all intersections up to this point, these are the result of line starts/ends matching
  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.                             // May skip further fraction
  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.                     // Build conflict
  425.                     buildSplitConflict(lane1, fraction1, lane2, fraction2, simulator, widthGenerator);
  426.                     // Skip loop for efficiency, and do not create multiple splits in case of multiple same upstream lanes
  427.                     split = true;
  428.                 }
  429.             }
  430.         }

  432.         // Create crossings
  433.         if (!lane1.getLink().equals(lane2.getLink())) // tight inner-curves with dedicated Bezier ignored
  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.                 // First fraction found is start of conflict
  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.                 // Flip crossed state of intersecting line combination
  451.                 crossed[intersection.getCombo()] = !crossed[intersection.getCombo()];
  452.                 // If all crossed or all not crossed, end of conflict
  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.         }

  470.     }

  472.     /**
  473.      * Build a merge conflict.
  474.      * @param lane1 Lane; lane 1
  475.      * @param f1start double; start fraction 1
  476.      * @param lane2 Lane; lane 2
  477.      * @param f2start double; start fraction 2
  478.      * @param simulator OtsSimulatorInterface; simulator
  479.      * @param widthGenerator WidthGenerator; width generator
  480.      * @param permitted boolean; conflict permitted by traffic control
  481.      * @throws NetworkException if the combination of conflict type and both conflict rules is not correct
  482.      * @throws OtsGeometryException in case of geometry exception
  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.     {

  490.         // Determine lane end from direction
  491.         double f1end = 1.0;
  492.         double f2end = 1.0;

  494.         // Get locations and length
  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));

  500.         // Get geometries
  501.         Polygon2d geometry1 = getGeometry(lane1, f1start, f1end, widthGenerator);
  502.         Polygon2d geometry2 = getGeometry(lane2, f2start, f2end, widthGenerator);

  504.         // Determine conflict rule
  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.             // TODO: handle bus priority on the model side
  511.             conflictRule = new BusStopConflictRule(simulator, DefaultsNl.BUS);
  512.         }
  513.         else
  514.         {
  515.             conflictRule = new DefaultConflictRule();
  516.         }

  518.         // Make conflict
  519.         Conflict.generateConflictPair(ConflictType.MERGE, conflictRule, permitted, lane1, longitudinalPosition1, length1,
  520.                 geometry1, lane2, longitudinalPosition2, length2, geometry2, simulator);

  522.         numberMergeConflicts.incrementAndGet();
  523.     }

  525.     /**
  526.      * Build a split conflict.
  527.      * @param lane1 Lane; lane 1
  528.      * @param f1end double; end fraction 1
  529.      * @param lane2 Lane; lane 2
  530.      * @param f2end double; end fraction 2
  531.      * @param simulator OtsSimulatorInterface; simulator
  532.      * @param widthGenerator WidthGenerator; width generator
  533.      * @throws NetworkException if the combination of conflict type and both conflict rules is not correct
  534.      * @throws OtsGeometryException in case of geometry exception
  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.     {

  542.         // Determine lane start from direction
  543.         double f1start = 0.0;
  544.         double f2start = 0.0;

  546.         // Get locations and length
  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));

  552.         // Get geometries
  553.         Polygon2d geometry1 = getGeometry(lane1, f1start, f1end, widthGenerator);
  554.         Polygon2d geometry2 = getGeometry(lane2, f2start, f2end, widthGenerator);

  556.         // Make conflict
  557.         Conflict.generateConflictPair(ConflictType.SPLIT, new SplitConflictRule(), false, lane1, longitudinalPosition1, length1,
  558.                 geometry1, lane2, longitudinalPosition2, length2, geometry2, simulator);

  560.         numberSplitConflicts.incrementAndGet();
  561.     }

  563.     /**
  564.      * Build a crossing conflict.
  565.      * @param lane1 Lane; lane 1
  566.      * @param f1start double; start fraction 1
  567.      * @param f1end double; end fraction 1
  568.      * @param lane2 Lane; lane 2
  569.      * @param f2start double; start fraction 2
  570.      * @param f2end double; end fraction 2
  571.      * @param simulator OtsSimulatorInterface; simulator
  572.      * @param widthGenerator WidthGenerator; width generator
  573.      * @param permitted boolean; conflict permitted by traffic control
  574.      * @throws NetworkException if the combination of conflict type and both conflict rules is not correct
  575.      * @throws OtsGeometryException in case of geometry exception
  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.     {

  583.         // Fractions may be in opposite direction, for the start location this needs to be correct
  584.         // Note: for geometry (real order, not considering direction) and length (absolute value) this does not matter
  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.         }

  604.         // Get locations and length
  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));

  610.         // Get geometries
  611.         Polygon2d geometry1 = getGeometry(lane1, f1start, f1end, widthGenerator);
  612.         Polygon2d geometry2 = getGeometry(lane2, f2start, f2end, widthGenerator);

  614.         // Determine conflict rule
  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.             // TODO: handle bus priority on the model side
  621.             conflictRule = new BusStopConflictRule(simulator, DefaultsNl.BUS);
  622.         }
  623.         else
  624.         {
  625.             conflictRule = new DefaultConflictRule();
  626.         }

  628.         // Make conflict
  629.         Conflict.generateConflictPair(ConflictType.CROSSING, conflictRule, permitted, lane1, longitudinalPosition1, length1,
  630.                 geometry1, lane2, longitudinalPosition2, length2, geometry2, simulator);

  632.         numberCrossConflicts.incrementAndGet();
  633.     }

  635.     /**
  636.      * Creates geometry for conflict.
  637.      * @param lane Lane; lane
  638.      * @param fStart double; longitudinal fraction of start
  639.      * @param fEnd double; longitudinal fraction of end
  640.      * @param widthGenerator WidthGenerator; width generator
  641.      * @return geometry for conflict
  642.      * @throws OtsGeometryException in case of geometry exception
  643.      */
  644.     private static Polygon2d getGeometry(final Lane lane, final double fStart, final double fEnd,
  645.             final WidthGenerator widthGenerator) throws OtsGeometryException
  646.     {
  647.         // extractFractional needs ordered fractions, irrespective of driving direction
  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.             // Fix up
  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.     }

  684.     /**
  685.      * Intersection holds two fractions where two lines have crossed. There is also a combo to identify which lines have been
  686.      * used to find the intersection.
  687.      * <p>
  688.      * Copyright (c) 2013-2024 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
  689.      * <br>
  690.      * BSD-style license. See <a href="https://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
  691.      * </p>
  692.      * @author <a href="https://github.com/averbraeck">Alexander Verbraeck</a>
  693.      * @author <a href="https://tudelft.nl/staff/p.knoppers-1">Peter Knoppers</a>
  694.      * @author <a href="https://github.com/wjschakel">Wouter Schakel</a>
  695.      */
  696.     private static class Intersection implements Comparable<Intersection>
  697.     {

  699.         /** Fraction on lane 1. */
  700.         private final double fraction1;

  702.         /** Fraction on lane 2. */
  703.         private final double fraction2;

  705.         /** Edge combination number. */
  706.         private final int combo;

  708.         /**
  709.          * @param fraction1 double; fraction on lane 1
  710.          * @param fraction2 double; fraction on lane 1
  711.          * @param combo int; edge combination number
  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.         }

  720.         /**
  721.          * @return fraction1.
  722.          */
  723.         public final double getFraction1()
  724.         {
  725.             return this.fraction1;
  726.         }

  728.         /**
  729.          * @return fraction2.
  730.          */
  731.         public final double getFraction2()
  732.         {
  733.             return this.fraction2;
  734.         }

  736.         /**
  737.          * @return combo.
  738.          */
  739.         public final int getCombo()
  740.         {
  741.             return this.combo;
  742.         }

  744.         /** {@inheritDoc} */
  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.         }

  761.         /** {@inheritDoc} */
  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.         }

  776.         /** {@inheritDoc} */
  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.         }

  808.         /**
  809.          * Returns a set of intersections, sorted by the fraction on line 1.
  810.          * @param line1 OtsLine2d; line 1
  811.          * @param line2 OtsLine2d; line 2
  812.          * @param combo int; edge combination number
  813.          * @return set of intersections, sorted by the fraction on line 1
  814.          * @throws OtsGeometryException in case of geometry exception
  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);

  828.                 double cumul2 = 0.0;
  829.                 Point2d start2 = null;
  830.                 Point2d end2 = line2.get(0);

  832.                 for (int j = 0; j < line2.size() - 1; j++)
  833.                 {
  834.                     start2 = end2;
  835.                     end2 = line2.get(j + 1);

  837.                     Point2d p = Point2d.intersectionOfLineSegments(start1, end1, start2, end2);
  838.                     if (p != null)
  839.                     {
  840.                         // Segments intersect
  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.                     }

  850.                     double dx = end2.x - start2.x;
  851.                     double dy = end2.y - start2.y;
  852.                     cumul2 += Math.hypot(dx, dy);
  853.                 }

  855.                 double dx = end1.x - start1.x;
  856.                 double dy = end1.y - start1.y;
  857.                 cumul1 += Math.hypot(dx, dy);
  858.             }

  860.             return out;
  861.         }

  863.         /** {@inheritDoc} */
  864.         @Override
  865.         public String toString()
  866.         {
  867.             return "Intersection [fraction1=" + this.fraction1 + ", fraction2=" + this.fraction2 + ", combo=" + this.combo
  868.                     + "]";
  869.         }

  871.     }

  873.     /**
  874.      * Generator for width.
  875.      * <p>
  876.      * Copyright (c) 2013-2024 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
  877.      * <br>
  878.      * BSD-style license. See <a href="https://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
  879.      * </p>
  880.      * @author <a href="https://github.com/averbraeck">Alexander Verbraeck</a>
  881.      * @author <a href="https://tudelft.nl/staff/p.knoppers-1">Peter Knoppers</a>
  882.      * @author <a href="https://github.com/wjschakel">Wouter Schakel</a>
  883.      */
  884.     public interface WidthGenerator
  885.     {

  887.         /**
  888.          * Returns the begin width of this lane.
  889.          * @param lane Lane; lane
  890.          * @param fraction double; fraction
  891.          * @return begin width of this lane
  892.          */
  893.         double getWidth(Lane lane, double fraction);

  895.     }

  897.     /**
  898.      * Generator with fixed width.
  899.      * <p>
  900.      * Copyright (c) 2013-2024 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
  901.      * <br>
  902.      * BSD-style license. See <a href="https://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
  903.      * </p>
  904.      * @author <a href="https://github.com/averbraeck">Alexander Verbraeck</a>
  905.      * @author <a href="https://tudelft.nl/staff/p.knoppers-1">Peter Knoppers</a>
  906.      * @author <a href="https://github.com/wjschakel">Wouter Schakel</a>
  907.      */
  908.     public static class FixedWidthGenerator implements WidthGenerator
  909.     {

  911.         /** Fixed width. */
  912.         private final double width;

  914.         /**
  915.          * Constructor with width.
  916.          * @param width Length; width
  917.          */
  918.         public FixedWidthGenerator(final Length width)
  919.         {
  920.             this.width = width.si;
  921.         }

  923.         /** {@inheritDoc} */
  924.         @Override
  925.         public final double getWidth(final Lane lane, final double fraction)
  926.         {
  927.             return this.width;
  928.         }

  930.         /** {@inheritDoc} */
  931.         @Override
  932.         public final String toString()
  933.         {
  934.             return "FixedWidthGenerator [width=" + this.width + "]";
  935.         }

  937.     }

  939.     /**
  940.      * Generator with width factor on actual lane width.
  941.      * <p>
  942.      * Copyright (c) 2013-2024 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
  943.      * <br>
  944.      * BSD-style license. See <a href="https://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
  945.      * </p>
  946.      * @author <a href="https://github.com/averbraeck">Alexander Verbraeck</a>
  947.      * @author <a href="https://tudelft.nl/staff/p.knoppers-1">Peter Knoppers</a>
  948.      * @author <a href="https://github.com/wjschakel">Wouter Schakel</a>
  949.      */
  950.     public static class RelativeWidthGenerator implements WidthGenerator
  951.     {

  953.         /** Width factor. */
  954.         private final double factor;

  956.         /**
  957.          * Constructor with width factor.
  958.          * @param factor double; width factor
  959.          */
  960.         public RelativeWidthGenerator(final double factor)
  961.         {
  962.             this.factor = factor;
  963.         }

  965.         /** {@inheritDoc} */
  966.         @Override
  967.         public final double getWidth(final Lane lane, final double fraction)
  968.         {
  969.             return lane.getWidth(fraction).si * this.factor;
  970.         }

  972.         /** {@inheritDoc} */
  973.         @Override
  974.         public final String toString()
  975.         {
  976.             return "RelativeWidthGenerator [factor=" + this.factor + "]";
  977.         }

  979.     }

  981.     /* ******************************************************************************************************************** */
  982.     /* ******************************************************************************************************************** */
  983.     /* ******************************************************************************************************************** */
  984.     /* ********************************************* PARALLEL IMPLEMENTATION ********************************************** */
  985.     /* ******************************************************************************************************************** */
  986.     /* ******************************************************************************************************************** */
  987.     /* ******************************************************************************************************************** */

  989.     /**
  990.      * Build conflicts on network; parallel implementation.
  991.      * @param network RoadNetwork; network
  992.      * @param simulator OtsSimulatorInterface; simulator
  993.      * @param widthGenerator WidthGenerator; width generator
  994.      * @throws OtsGeometryException in case of geometry exception
  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.     }

  1002.     /**
  1003.      * Build conflicts on network; parallel implementation.
  1004.      * @param network RoadNetwork; network
  1005.      * @param simulator OtsSimulatorInterface; simulator
  1006.      * @param widthGenerator WidthGenerator; width generator
  1007.      * @param ignoreList LaneCombinationList; lane combinations to ignore
  1008.      * @param permittedList LaneCombinationList; lane combinations that are permitted by traffic control
  1009.      * @throws OtsGeometryException in case of geometry exception
  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.     }

  1018.     /**
  1019.      * Build conflicts on list of lanes; parallel implementation.
  1020.      * @param lanes List&lt;Lane&gt;; lanes
  1021.      * @param simulator OtsSimulatorInterface; simulator
  1022.      * @param widthGenerator WidthGenerator; width generator
  1023.      * @throws OtsGeometryException in case of geometry exception
  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.     }

  1031.     /**
  1032.      * Build conflicts on list of lanes; parallel implementation. Small jobs.
  1033.      * @param lanes List&lt;Lane&gt;; list of Lanes
  1034.      * @param simulator OtsSimulatorInterface; the simulator
  1035.      * @param widthGenerator WidthGenerator; the width generator
  1036.      * @param ignoreList LaneCombinationList; lane combinations to ignore
  1037.      * @param permittedList LaneCombinationList; lane combinations that are permitted by traffic control
  1038.      * @throws OtsGeometryException in case of geometry exception
  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<>();

  1050.         // make a threadpool and execute buildConflicts for all records
  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;

  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);

  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.                 // Quick contour check, skip if non-overlapping envelopes
  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.                 }

  1096.                 boolean permitted = permittedList.contains(lane1, lane2);

  1098.                 while (numberOfJobs.get() > maxqueue) // keep max maxqueue jobs in the pool
  1099.                 {
  1100.                     try
  1101.                     {
  1102.                         Thread.sleep(1);
  1103.                     }
  1104.                     catch (InterruptedException exception)
  1105.                     {
  1106.                         // ignore
  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.         }

  1118.         long time = System.currentTimeMillis();
  1119.         // wait max 60 sec for last maxqueue jobs
  1120.         while (numberOfJobs.get() > 0 && System.currentTimeMillis() - time < 60000)
  1121.         {
  1122.             try
  1123.             {
  1124.                 Thread.sleep(10);
  1125.             }
  1126.             catch (InterruptedException exception)
  1127.             {
  1128.                 // ignore
  1129.             }
  1130.         }

  1132.         executor.shutdown();
  1133.         while (!executor.isTerminated())
  1134.         {
  1135.             try
  1136.             {
  1137.                 Thread.sleep(1);
  1138.             }
  1139.             catch (InterruptedException exception)
  1140.             {
  1141.                 // ignore
  1142.             }
  1143.         }

  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.     }

  1152.     /**
  1153.      * Build conflicts on list of lanes; parallel implementation. Big jobs.
  1154.      * @param lanes List&lt;Lane&gt;; list of Lanes
  1155.      * @param simulator OtsSimulatorInterface; the simulator
  1156.      * @param widthGenerator WidthGenerator; the width generator
  1157.      * @param ignoreList LaneCombinationList; lane combinations to ignore
  1158.      * @param permittedList LaneCombinationList; lane combinations that are permitted by traffic control
  1159.      * @throws OtsGeometryException in case of geometry exception
  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<>();

  1171.         // make a threadpool and execute buildConflicts for all records
  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;

  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.             }

  1192.             while (numberOfJobs.get() > maxqueue) // keep max maxqueue jobs in the pool
  1193.             {
  1194.                 try
  1195.                 {
  1196.                     Thread.sleep(0, 10);
  1197.                 }
  1198.                 catch (InterruptedException exception)
  1199.                 {
  1200.                     // ignore
  1201.                 }
  1202.             }
  1203.             numberOfJobs.incrementAndGet();

  1205.             ConflictBuilderRecordBig cbr = new ConflictBuilderRecordBig(i, lanes, ignoreList, permittedList, simulator,
  1206.                     widthGenerator, leftEdges, rightEdges);
  1207.             executor.execute(new CbrTaskBig(numberOfJobs, cbr));

  1209.         }

  1211.         long time = System.currentTimeMillis();
  1212.         // wait max 60 sec for last maxqueue jobs
  1213.         while (numberOfJobs.get() > 0 && System.currentTimeMillis() - time < 60000)
  1214.         {
  1215.             try
  1216.             {
  1217.                 Thread.sleep(10);
  1218.             }
  1219.             catch (InterruptedException exception)
  1220.             {
  1221.                 // ignore
  1222.             }
  1223.         }

  1225.         executor.shutdown();
  1226.         while (!executor.isTerminated())
  1227.         {
  1228.             try
  1229.             {
  1230.                 Thread.sleep(1);
  1231.             }
  1232.             catch (InterruptedException exception)
  1233.             {
  1234.                 // ignore
  1235.             }
  1236.         }

  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.     }

  1245.     /**
  1246.      * Build conflicts on network using only the groups of links that have been identified as candidates with conflicts;
  1247.      * parallel implementation.
  1248.      * @param network RoadNetwork; network
  1249.      * @param conflictCandidateMap Map&lt;String, Set&lt;Link&gt;&gt;; the map of the conflicting links to implement
  1250.      * @param simulator OtsSimulatorInterface; simulator
  1251.      * @param widthGenerator WidthGenerator; width generator
  1252.      * @throws OtsGeometryException in case of geometry exception
  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.             // System.out.println(conflictId);
  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.             // TODO: make parallel
  1275.             // simulator.getLogger().setAllLogLevel(Level.WARNING);
  1276.             buildConflicts(lanes, simulator, widthGenerator, new LaneCombinationList(), new LaneCombinationList(), conflictId);
  1277.             simulator.getLogger().setAllLogLevel(Level.DEBUG);
  1278.         }
  1279.     }

  1281.     /**
  1282.      * Small conflict builder task. A small task is finding all conflicts between two lanes.
  1283.      * <p>
  1284.      * Copyright (c) 2023-2024 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
  1285.      * <br>
  1286.      * BSD-style license. See <a href="https://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
  1287.      * </p>
  1288.      * @author <a href="https://github.com/averbraeck">Alexander Verbraeck</a>
  1289.      * @author <a href="https://tudelft.nl/staff/p.knoppers-1">Peter Knoppers</a>
  1290.      * @author <a href="https://github.com/wjschakel">Wouter Schakel</a>
  1291.      */
  1292.     static class CbrTaskSmall implements Runnable
  1293.     {
  1294.         /** Small conflict builder record. */
  1295.         final ConflictBuilderRecordSmall cbr;

  1297.         /** Number of jobs to do. */
  1298.         final AtomicInteger nrOfJobs;

  1300.         /**
  1301.          * Constructor.
  1302.          * @param nrOfJobs AtomicInteger; number of jobs to do.
  1303.          * @param cbr ConflictBuilderRecordSmall; the record to execute.
  1304.          */
  1305.         CbrTaskSmall(final AtomicInteger nrOfJobs, final ConflictBuilderRecordSmall cbr)
  1306.         {
  1307.             this.nrOfJobs = nrOfJobs;
  1308.             this.cbr = cbr;
  1309.         }

  1311.         /** {@inheritDoc} */
  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.     }

  1329.     /**
  1330.      * Small conflict builder record. Small means this holds the information to create conflicts between two lanes.
  1331.      * <p>
  1332.      * Copyright (c) 2023-2024 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
  1333.      * <br>
  1334.      * BSD-style license. See <a href="https://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
  1335.      * </p>
  1336.      * @author <a href="https://github.com/averbraeck">Alexander Verbraeck</a>
  1337.      * @author <a href="https://tudelft.nl/staff/p.knoppers-1">Peter Knoppers</a>
  1338.      * @author <a href="https://github.com/wjschakel">Wouter Schakel</a>
  1339.      * @param lane1 Lane; lane 1
  1340.      * @param down1 Set&lt;Lane&gt;; downstream lanes 1
  1341.      * @param up1 Set&lt;Lane&gt;; upstream lanes 1
  1342.      * @param lane2 Lane; lane 2
  1343.      * @param down2 Set&lt;Lane&gt;; downstream lane 2
  1344.      * @param up2 Set&lt;Lane&gt;; upstream lanes 2
  1345.      * @param permitted boolean; conflict permitted by traffic control
  1346.      * @param simulator OtsSimulatorInterface; simulator
  1347.      * @param widthGenerator WidthGenerator; width generator
  1348.      * @param leftEdges Map&lt;Lane, OtsLine2d&gt;; cache of left edge lines
  1349.      * @param rightEdges Map&lt;Lane, OtsLine2d&gt;; cache of right edge lines
  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.     }

  1358.     /**
  1359.      * Large conflict builder task. A large task is finding all conflicts between one particular lane, and all lanes further in
  1360.      * a list.
  1361.      * <p>
  1362.      * Copyright (c) 2023-2024 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
  1363.      * <br>
  1364.      * BSD-style license. See <a href="https://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
  1365.      * </p>
  1366.      * @author <a href="https://github.com/averbraeck">Alexander Verbraeck</a>
  1367.      * @author <a href="https://tudelft.nl/staff/p.knoppers-1">Peter Knoppers</a>
  1368.      * @author <a href="https://github.com/wjschakel">Wouter Schakel</a>
  1369.      */
  1370.     static class CbrTaskBig implements Runnable
  1371.     {
  1372.         /** Big conflict builder record. */
  1373.         final ConflictBuilderRecordBig cbr;

  1375.         /** Number of jobs to do. */
  1376.         final AtomicInteger nrOfJobs;

  1378.         /**
  1379.          * Constructor.
  1380.          * @param nrOfJobs AtomicInteger; number of jobs to do.
  1381.          * @param cbr ConflictBuilderRecordBig; the record to execute.
  1382.          */
  1383.         CbrTaskBig(final AtomicInteger nrOfJobs, final ConflictBuilderRecordBig cbr)
  1384.         {
  1385.             this.nrOfJobs = nrOfJobs;
  1386.             this.cbr = cbr;
  1387.         }

  1389.         /** {@inheritDoc} */
  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.                     // Quick contour check, skip if non-overlapping envelopes
  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.                     }

  1420.                     boolean permitted = this.cbr.permittedList.contains(lane1, lane2);

  1422.                     Set<Lane> down2 = lane2.nextLanes(null);
  1423.                     Set<Lane> up2 = lane2.prevLanes(null);

  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.                 }

  1437.             }
  1438.             catch (Exception e)
  1439.             {
  1440.                 e.printStackTrace();
  1441.             }
  1442.             this.nrOfJobs.decrementAndGet();
  1443.         }
  1444.     }

  1446.     /**
  1447.      * Big conflict builder record. Big means this holds the information to create conflicts between one particular lane, and
  1448.      * all lanes further in a list.
  1449.      * <p>
  1450.      * Copyright (c) 2023-2024 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
  1451.      * <br>
  1452.      * BSD-style license. See <a href="https://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
  1453.      * </p>
  1454.      * @author <a href="https://github.com/averbraeck">Alexander Verbraeck</a>
  1455.      * @author <a href="https://tudelft.nl/staff/p.knoppers-1">Peter Knoppers</a>
  1456.      * @author <a href="https://github.com/wjschakel">Wouter Schakel</a>
  1457.      * @param starti int; the start index
  1458.      * @param lanes List of lanes
  1459.      * @param ignoreList list of lane combinations to ignore
  1460.      * @param permittedList list of lane combinations to permit
  1461.      * @param simulator OtsSimulatorInterface; simulator
  1462.      * @param widthGenerator WidthGenerator; width generator
  1463.      * @param leftEdges Map&lt;Lane, OtsLine2d&gt;; cache of left edge lines
  1464.      * @param rightEdges Map&lt;Lane, OtsLine2d&gt;; cache of right edge lines
  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.     }

  1473. }
Created with JaCoCo 0.8.12.202403310830