View Javadoc
1   package org.opentrafficsim.draw.graphs.road;
2   
3   import java.util.ArrayList;
4   import java.util.Collections;
5   import java.util.Comparator;
6   import java.util.Iterator;
7   import java.util.LinkedHashMap;
8   import java.util.LinkedHashSet;
9   import java.util.List;
10  import java.util.Map;
11  import java.util.Set;
12  
13  import org.djunits.value.vdouble.scalar.Length;
14  import org.djunits.value.vdouble.scalar.Speed;
15  import org.djutils.exceptions.Throw;
16  import org.djutils.immutablecollections.ImmutableMap;
17  import org.djutils.immutablecollections.ImmutableSet;
18  import org.opentrafficsim.core.gtu.GTUDirectionality;
19  import org.opentrafficsim.core.network.DirectedLinkPosition;
20  import org.opentrafficsim.core.network.Link;
21  import org.opentrafficsim.core.network.NetworkException;
22  import org.opentrafficsim.draw.graphs.GraphCrossSection;
23  import org.opentrafficsim.draw.graphs.GraphPath;
24  import org.opentrafficsim.draw.graphs.GraphPath.Section;
25  import org.opentrafficsim.kpi.sampling.KpiGtuDirectionality;
26  import org.opentrafficsim.kpi.sampling.KpiLaneDirection;
27  import org.opentrafficsim.road.network.lane.CrossSectionLink;
28  import org.opentrafficsim.road.network.lane.DirectedLanePosition;
29  import org.opentrafficsim.road.network.lane.Lane;
30  import org.opentrafficsim.road.network.lane.LaneDirection;
31  import org.opentrafficsim.road.network.sampling.LaneData;
32  
33  /**
34   * Utilities to create {@code GraphPath}s and {@code GraphCrossSection}s for graphs, based on lanes.
35   * <p>
36   * Copyright (c) 2013-2020 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved. <br>
37   * BSD-style license. See <a href="http://opentrafficsim.org/node/13">OpenTrafficSim License</a>.
38   * <p>
39   * @version $Revision$, $LastChangedDate$, by $Author$, initial version 19 okt. 2018 <br>
40   * @author <a href="http://www.tbm.tudelft.nl/averbraeck">Alexander Verbraeck</a>
41   * @author <a href="http://www.tudelft.nl/pknoppers">Peter Knoppers</a>
42   * @author <a href="http://www.transport.citg.tudelft.nl">Wouter Schakel</a>
43   */
44  public final class GraphLaneUtil
45  {
46  
47      /**
48       * Constructor.
49       */
50      private GraphLaneUtil()
51      {
52          //
53      }
54  
55      /**
56       * Creates a path starting at the provided lane and moving downstream until a dead-end, split, or loop.
57       * @param name String; path name
58       * @param first LaneDirection; first lane
59       * @return GraphPath&lt;KpiLaneDirection&gt; path
60       * @throws NetworkException when the lane does not have any set speed limit
61       */
62      public static GraphPath<KpiLaneDirection> createPath(final String name, final LaneDirection first) throws NetworkException
63      {
64          Throw.whenNull(name, "Name may not be null.");
65          Throw.whenNull(first, "First may not be null.");
66          List<Section<KpiLaneDirection>> sections = new ArrayList<>();
67          Set<LaneDirection> set = new LinkedHashSet<>();
68          LaneDirection lane = first;
69          while (lane != null && !set.contains(lane))
70          {
71              KpiLaneDirection kpiLaneDirection = new KpiLaneDirection(new LaneData(lane.getLane()),
72                      lane.getDirection().isPlus() ? KpiGtuDirectionality.DIR_PLUS : KpiGtuDirectionality.DIR_MINUS);
73              List<KpiLaneDirection> list = new ArrayList<>();
74              list.add(kpiLaneDirection);
75              Speed speed = lane.getLane().getLowestSpeedLimit();
76              Length length = lane.getLength();
77              sections.add(new Section<KpiLaneDirection>()
78              {
79                  /** {@inheritDoc} */
80                  @Override
81                  public Iterator<KpiLaneDirection> iterator()
82                  {
83                      return list.iterator();
84                  }
85  
86                  /** {@inheritDoc} */
87                  @Override
88                  public Length getLength()
89                  {
90                      return length;
91                  }
92  
93                  /** {@inheritDoc} */
94                  @Override
95                  public Speed getSpeedLimit()
96                  {
97                      return speed;
98                  }
99  
100                 /** {@inheritDoc} */
101                 @Override
102                 public KpiLaneDirection getSource(final int series)
103                 {
104                     return kpiLaneDirection;
105                 }
106                 
107                 /** {@inheritDoc} */
108                 @Override
109                 public String toString()
110                 {
111                     return String.format("(Anonymous) Section[length=%s, speedLimit=%s, source=%s]", length, speed,
112                             kpiLaneDirection);
113                 }
114             });
115             set.add(lane);
116             ImmutableMap<Lane, GTUDirectionality> map = lane.getLane().downstreamLanes(lane.getDirection(), null);
117             if (map.size() == 1)
118             {
119                 ImmutableMap.ImmutableEntry<Lane, GTUDirectionality> entry = map.entrySet().iterator().next();
120                 lane = new LaneDirection(entry.getKey(), entry.getValue());
121             }
122         }
123         return new GraphPath<>(name, sections);
124     }
125 
126     /**
127      * Creates a path starting at the provided lanes and moving downstream for as long as no lane finds a loop (on to any of the
128      * lanes) and there's a unique link all lanes have downstream. The length and speed limit are taken from the first lane.
129      * @param names List&lt;String&gt;; lane names
130      * @param first List&lt;LaneDirection&gt;; first lanes
131      * @return GraphPath&lt;KpiLaneDirection&gt; path
132      * @throws NetworkException when a lane does not have any set speed limit
133      */
134     public static GraphPath<KpiLaneDirection> createPath(final List<String> names, final List<LaneDirection> first)
135             throws NetworkException
136     {
137         Throw.whenNull(names, "Names may not be null.");
138         Throw.whenNull(first, "First may not be null.");
139         Throw.when(names.size() != first.size(), IllegalArgumentException.class, "Size of 'names' and 'first' must be equal.");
140         List<Section<KpiLaneDirection>> sections = new ArrayList<>();
141         Set<LaneDirection> set = new LinkedHashSet<>();
142         List<LaneDirection> lanes = first;
143         while (lanes != null && Collections.disjoint(set, lanes))
144         {
145             List<KpiLaneDirection> list = new ArrayList<>();
146             Speed speed = null;
147             for (LaneDirection lane : lanes)
148             {
149                 if (lane == null)
150                 {
151                     list.add(null);
152                     continue;
153                 }
154                 speed = speed == null ? lane.getLane().getLowestSpeedLimit()
155                         : Speed.min(speed, lane.getLane().getLowestSpeedLimit());
156                 KpiLaneDirection kpiLaneDirection = new KpiLaneDirection(new LaneData(lane.getLane()),
157                         lane.getDirection().isPlus() ? KpiGtuDirectionality.DIR_PLUS : KpiGtuDirectionality.DIR_MINUS);
158                 list.add(kpiLaneDirection);
159             }
160             Speed finalSpeed = speed;
161             LaneDirection firstNextLane = null;
162             for (LaneDirection lane : lanes)
163             {
164                 if (lane != null)
165                 {
166                     firstNextLane = lane;
167                     continue;
168                 }
169             }
170             Length length = firstNextLane.getLength();
171             sections.add(new Section<KpiLaneDirection>()
172             {
173                 /** {@inheritDoc} */
174                 @Override
175                 public Iterator<KpiLaneDirection> iterator()
176                 {
177                     return list.iterator();
178                 }
179 
180                 /** {@inheritDoc} */
181                 @Override
182                 public Length getLength()
183                 {
184                     return length;
185                 }
186 
187                 /** {@inheritDoc} */
188                 @Override
189                 public Speed getSpeedLimit()
190                 {
191                     return finalSpeed;
192                 }
193 
194                 /** {@inheritDoc} */
195                 @Override
196                 public KpiLaneDirection getSource(final int series)
197                 {
198                     return list.get(series);
199                 }
200             });
201             set.addAll(lanes);
202             // per link and then per lane, find the downstream lane
203             Map<Link, List<LaneDirection>> linkMap = new LinkedHashMap<>();
204             Link link = firstNextLane.getLane().getParentLink();
205             ImmutableSet<Link> links =
206                     (firstNextLane.getDirection().isPlus() ? link.getEndNode() : link.getStartNode()).getLinks();
207             for (Link nextLink : links)
208             {
209                 if (!link.equals(nextLink))
210                 {
211                     List<LaneDirection> nextLanes = new ArrayList<>();
212                     for (LaneDirection laneDir : lanes)
213                     {
214                         ImmutableMap<Lane, GTUDirectionality> map =
215                                 laneDir.getLane().downstreamLanes(laneDir.getDirection(), null);
216                         int n = 0;
217                         for (ImmutableMap.ImmutableEntry<Lane, GTUDirectionality> entry : map.entrySet())
218                         {
219                             if (entry.getKey().getParentLink().equals(nextLink))
220                             {
221                                 n++;
222                                 nextLanes.add(new LaneDirection(entry.getKey(), entry.getValue()));
223                             }
224                         }
225                         if (n > 1)
226                         {
227                             // multiple downstream lanes of this lane go to this link, this is not allowed
228                             nextLanes.clear();
229                             break;
230                         }
231                         else if (n == 0)
232                         {
233                             nextLanes.add(null);
234                         }
235                     }
236                     if (nextLanes.size() == lanes.size())
237                     {
238                         linkMap.put(nextLink, nextLanes);
239                     }
240                 }
241             }
242             // in case there are multiple downstream links, remove all links for which some lanes had no downstream lane
243             if (linkMap.size() > 1)
244             {
245                 Iterator<List<LaneDirection>> it = linkMap.values().iterator();
246                 while (it.hasNext())
247                 {
248                     if (it.next().contains(null))
249                     {
250                         it.remove();
251                     }
252                 }
253             }
254             if (linkMap.size() == 1)
255             {
256                 lanes = linkMap.values().iterator().next();
257             }
258             else
259             {
260                 lanes = null;
261             }
262         }
263         return new GraphPath<>(names, sections);
264     }
265 
266     /**
267      * Creates a single-lane path.
268      * @param name String; name
269      * @param lane LaneDirection; lane
270      * @return GraphPath&lt;KpiLaneDirection&gt; path
271      * @throws NetworkException when a lane does not have any set speed limit
272      */
273     public static GraphPath<KpiLaneDirection> createSingleLanePath(final String name, final LaneDirection lane)
274             throws NetworkException
275     {
276         List<KpiLaneDirection> lanes = new ArrayList<>();
277         lanes.add(new KpiLaneDirection(new LaneData(lane.getLane()),
278                 lane.getDirection().isPlus() ? KpiGtuDirectionality.DIR_PLUS : KpiGtuDirectionality.DIR_MINUS));
279         List<Section<KpiLaneDirection>> sections = new ArrayList<>();
280         Speed speed = lane.getLane().getLowestSpeedLimit();
281         sections.add(new Section<KpiLaneDirection>()
282         {
283 
284             /** {@inheritDoc} */
285             @Override
286             public Iterator<KpiLaneDirection> iterator()
287             {
288                 return lanes.iterator();
289             }
290 
291             /** {@inheritDoc} */
292             @Override
293             public Length getLength()
294             {
295                 return lane.getLength();
296             }
297 
298             /** {@inheritDoc} */
299             @Override
300             public Speed getSpeedLimit()
301             {
302                 return speed;
303             }
304 
305             /** {@inheritDoc} */
306             @Override
307             public KpiLaneDirection getSource(final int series)
308             {
309                 return lanes.get(0);
310             }
311 
312         });
313         return new GraphPath<>(name, sections);
314     }
315 
316     /**
317      * Creates a cross section at the provided lane and position.
318      * @param name String; name
319      * @param lanePosition DirectedLanePosition; lane position
320      * @return GraphCrossSection&lt;KpiLaneDirection&gt; cross section
321      * @throws NetworkException when the lane does not have any set speed limit
322      */
323     public static GraphCrossSection<KpiLaneDirection> createCrossSection(final String name,
324             final DirectedLanePosition lanePosition) throws NetworkException
325     {
326         Throw.whenNull(name, "Name may not be null.");
327         Throw.whenNull(lanePosition, "Lane position may not be null.");
328         List<KpiLaneDirection> list = new ArrayList<>();
329         List<String> names = new ArrayList<>();
330         List<Length> positions = new ArrayList<>();
331         names.add(name);
332         positions.add(lanePosition.getPosition());
333         list.add(new KpiLaneDirection(new LaneData(lanePosition.getLane()),
334                 lanePosition.getGtuDirection().isPlus() ? KpiGtuDirectionality.DIR_PLUS : KpiGtuDirectionality.DIR_MINUS));
335         Speed speed = lanePosition.getLane().getLowestSpeedLimit();
336         return createCrossSection(names, list, positions, speed);
337     }
338 
339     /**
340      * Creates a cross section at the provided link and position.
341      * @param names List&lt;String&gt;; lane names
342      * @param linkPosition DirectedLinkPosition; link position
343      * @return GraphCrossSection&lt;KpiLaneDirection&gt; cross section
344      * @throws NetworkException when a lane does not have any set speed limit
345      */
346     public static GraphCrossSection<KpiLaneDirection> createCrossSection(final List<String> names,
347             final DirectedLinkPosition linkPosition) throws NetworkException
348     {
349         Throw.whenNull(names, "Names may not be null.");
350         Throw.whenNull(linkPosition, "Link position may not be null.");
351         Throw.when(!(linkPosition.getLink() instanceof CrossSectionLink), IllegalArgumentException.class,
352                 "The link is not a CrossEctionLink.");
353         List<Lane> lanes = ((CrossSectionLink) linkPosition.getLink()).getLanes();
354         Throw.when(names.size() != lanes.size(), IllegalArgumentException.class,
355                 "Size of 'names' not equal to the number of lanes.");
356         Collections.sort(lanes, new Comparator<Lane>()
357         {
358             /** {@ingeritDoc} */
359             @Override
360             public int compare(final Lane o1, final Lane o2)
361             {
362                 int comp = o1.getDesignLineOffsetAtBegin().compareTo(o2.getDesignLineOffsetAtEnd());
363                 return linkPosition.getDirection().isPlus() ? comp : -comp;
364             }
365 
366         });
367         List<KpiLaneDirection> list = new ArrayList<>();
368         List<Length> positions = new ArrayList<>();
369         Speed speed = null;
370         for (Lane lane : lanes)
371         {
372             speed = speed == null ? lane.getLowestSpeedLimit() : Speed.min(speed, lane.getLowestSpeedLimit());
373             list.add(new KpiLaneDirection(new LaneData(lane),
374                     linkPosition.getDirection().isPlus() ? KpiGtuDirectionality.DIR_PLUS : KpiGtuDirectionality.DIR_MINUS));
375             positions.add(lane.getLength().times(linkPosition.getFractionalLongitudinalPosition()));
376         }
377         return createCrossSection(names, list, positions, speed);
378     }
379 
380     /**
381      * Creates a cross section.
382      * @param names List&lt;String&gt;;; names
383      * @param lanes List&lt;KpiLaneDirection&gt;;; lanes
384      * @param positions List&lt;Length&gt;; positions
385      * @param speed Speed; speed
386      * @return GraphCrossSection&lt;KpiLaneDirection&gt;; cross section
387      */
388     public static GraphCrossSection<KpiLaneDirection> createCrossSection(final List<String> names,
389             final List<KpiLaneDirection> lanes, final List<Length> positions, final Speed speed)
390     {
391         Section<KpiLaneDirection> section = new Section<KpiLaneDirection>()
392         {
393             /** {@inheritDoc} */
394             @Override
395             public Iterator<KpiLaneDirection> iterator()
396             {
397                 return lanes.iterator();
398             }
399 
400             /** {@inheritDoc} */
401             @Override
402             public Length getLength()
403             {
404                 return lanes.get(0).getLaneData().getLength();
405             }
406 
407             /** {@inheritDoc} */
408             @Override
409             public Speed getSpeedLimit()
410             {
411                 return speed;
412             }
413 
414             /** {@inheritDoc} */
415             @Override
416             public KpiLaneDirection getSource(final int series)
417             {
418                 return lanes.get(series);
419             }
420         };
421         return new GraphCrossSection<>(names, section, positions);
422     }
423 
424 }