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             set.add(lane);
108             ImmutableMap<Lane, GTUDirectionality> map = lane.getLane().downstreamLanes(lane.getDirection(), null);
109             if (map.size() == 1)
110             {
111                 ImmutableMap.ImmutableEntry<Lane, GTUDirectionality> entry = map.entrySet().iterator().next();
112                 lane = new LaneDirection(entry.getKey(), entry.getValue());
113             }
114         }
115         return new GraphPath<>(name, sections);
116     }
117 
118     /**
119      * 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
120      * lanes) and there's a unique link all lanes have downstream. The length and speed limit are taken from the first lane.
121      * @param names List&lt;String&gt;; lane names
122      * @param first List&lt;LaneDirection&gt;; first lanes
123      * @return GraphPath&lt;KpiLaneDirection&gt; path
124      * @throws NetworkException when a lane does not have any set speed limit
125      */
126     public static GraphPath<KpiLaneDirection> createPath(final List<String> names, final List<LaneDirection> first)
127             throws NetworkException
128     {
129         Throw.whenNull(names, "Names may not be null.");
130         Throw.whenNull(first, "First may not be null.");
131         Throw.when(names.size() != first.size(), IllegalArgumentException.class, "Size of 'names' and 'first' must be equal.");
132         List<Section<KpiLaneDirection>> sections = new ArrayList<>();
133         Set<LaneDirection> set = new LinkedHashSet<>();
134         List<LaneDirection> lanes = first;
135         while (lanes != null && Collections.disjoint(set, lanes))
136         {
137             List<KpiLaneDirection> list = new ArrayList<>();
138             Speed speed = null;
139             for (LaneDirection lane : lanes)
140             {
141                 if (lane == null)
142                 {
143                     list.add(null);
144                     continue;
145                 }
146                 speed = speed == null ? lane.getLane().getLowestSpeedLimit()
147                         : Speed.min(speed, lane.getLane().getLowestSpeedLimit());
148                 KpiLaneDirection kpiLaneDirection = new KpiLaneDirection(new LaneData(lane.getLane()),
149                         lane.getDirection().isPlus() ? KpiGtuDirectionality.DIR_PLUS : KpiGtuDirectionality.DIR_MINUS);
150                 list.add(kpiLaneDirection);
151             }
152             Speed finalSpeed = speed;
153             LaneDirection firstNextLane = null;
154             for (LaneDirection lane : lanes)
155             {
156                 if (lane != null)
157                 {
158                     firstNextLane = lane;
159                     continue;
160                 }
161             }
162             Length length = firstNextLane.getLength();
163             sections.add(new Section<KpiLaneDirection>()
164             {
165                 /** {@inheritDoc} */
166                 @Override
167                 public Iterator<KpiLaneDirection> iterator()
168                 {
169                     return list.iterator();
170                 }
171 
172                 /** {@inheritDoc} */
173                 @Override
174                 public Length getLength()
175                 {
176                     return length;
177                 }
178 
179                 /** {@inheritDoc} */
180                 @Override
181                 public Speed getSpeedLimit()
182                 {
183                     return finalSpeed;
184                 }
185 
186                 /** {@inheritDoc} */
187                 @Override
188                 public KpiLaneDirection getSource(final int series)
189                 {
190                     return list.get(series);
191                 }
192             });
193             set.addAll(lanes);
194             // per link and then per lane, find the downstream lane
195             Map<Link, List<LaneDirection>> linkMap = new LinkedHashMap<>();
196             Link link = firstNextLane.getLane().getParentLink();
197             ImmutableSet<Link> links =
198                     (firstNextLane.getDirection().isPlus() ? link.getEndNode() : link.getStartNode()).getLinks();
199             for (Link nextLink : links)
200             {
201                 if (!link.equals(nextLink))
202                 {
203                     List<LaneDirection> nextLanes = new ArrayList<>();
204                     for (LaneDirection laneDir : lanes)
205                     {
206                         ImmutableMap<Lane, GTUDirectionality> map =
207                                 laneDir.getLane().downstreamLanes(laneDir.getDirection(), null);
208                         int n = 0;
209                         for (ImmutableMap.ImmutableEntry<Lane, GTUDirectionality> entry : map.entrySet())
210                         {
211                             if (entry.getKey().getParentLink().equals(nextLink))
212                             {
213                                 n++;
214                                 nextLanes.add(new LaneDirection(entry.getKey(), entry.getValue()));
215                             }
216                         }
217                         if (n > 1)
218                         {
219                             // multiple downstream lanes of this lane go to this link, this is not allowed
220                             nextLanes.clear();
221                             break;
222                         }
223                         else if (n == 0)
224                         {
225                             nextLanes.add(null);
226                         }
227                     }
228                     if (nextLanes.size() == lanes.size())
229                     {
230                         linkMap.put(nextLink, nextLanes);
231                     }
232                 }
233             }
234             // in case there are multiple downstream links, remove all links for which some lanes had no downstream lane
235             if (linkMap.size() > 1)
236             {
237                 Iterator<List<LaneDirection>> it = linkMap.values().iterator();
238                 while (it.hasNext())
239                 {
240                     if (it.next().contains(null))
241                     {
242                         it.remove();
243                     }
244                 }
245             }
246             if (linkMap.size() == 1)
247             {
248                 lanes = linkMap.values().iterator().next();
249             }
250             else
251             {
252                 lanes = null;
253             }
254         }
255         return new GraphPath<>(names, sections);
256     }
257 
258     /**
259      * Creates a single-lane path.
260      * @param name String; name
261      * @param lane LaneDirection; lane
262      * @return GraphPath&lt;KpiLaneDirection&gt; path
263      * @throws NetworkException when a lane does not have any set speed limit
264      */
265     public static GraphPath<KpiLaneDirection> createSingleLanePath(final String name, final LaneDirection lane)
266             throws NetworkException
267     {
268         List<KpiLaneDirection> lanes = new ArrayList<>();
269         lanes.add(new KpiLaneDirection(new LaneData(lane.getLane()),
270                 lane.getDirection().isPlus() ? KpiGtuDirectionality.DIR_PLUS : KpiGtuDirectionality.DIR_MINUS));
271         List<Section<KpiLaneDirection>> sections = new ArrayList<>();
272         Speed speed = lane.getLane().getLowestSpeedLimit();
273         sections.add(new Section<KpiLaneDirection>()
274         {
275 
276             /** {@inheritDoc} */
277             @Override
278             public Iterator<KpiLaneDirection> iterator()
279             {
280                 return lanes.iterator();
281             }
282 
283             /** {@inheritDoc} */
284             @Override
285             public Length getLength()
286             {
287                 return lane.getLength();
288             }
289 
290             /** {@inheritDoc} */
291             @Override
292             public Speed getSpeedLimit()
293             {
294                 return speed;
295             }
296 
297             /** {@inheritDoc} */
298             @Override
299             public KpiLaneDirection getSource(final int series)
300             {
301                 return lanes.get(0);
302             }
303 
304         });
305         return new GraphPath<>(name, sections);
306     }
307 
308     /**
309      * Creates a cross section at the provided lane and position.
310      * @param name String; name
311      * @param lanePosition DirectedLanePosition; lane position
312      * @return GraphCrossSection&lt;KpiLaneDirection&gt; cross section
313      * @throws NetworkException when the lane does not have any set speed limit
314      */
315     public static GraphCrossSection<KpiLaneDirection> createCrossSection(final String name,
316             final DirectedLanePosition lanePosition) throws NetworkException
317     {
318         Throw.whenNull(name, "Name may not be null.");
319         Throw.whenNull(lanePosition, "Lane position may not be null.");
320         List<KpiLaneDirection> list = new ArrayList<>();
321         List<String> names = new ArrayList<>();
322         List<Length> positions = new ArrayList<>();
323         names.add(name);
324         positions.add(lanePosition.getPosition());
325         list.add(new KpiLaneDirection(new LaneData(lanePosition.getLane()),
326                 lanePosition.getGtuDirection().isPlus() ? KpiGtuDirectionality.DIR_PLUS : KpiGtuDirectionality.DIR_MINUS));
327         Speed speed = lanePosition.getLane().getLowestSpeedLimit();
328         return createCrossSection(names, list, positions, speed);
329     }
330 
331     /**
332      * Creates a cross section at the provided link and position.
333      * @param names List&lt;String&gt;; lane names
334      * @param linkPosition DirectedLinkPosition; link position
335      * @return GraphCrossSection&lt;KpiLaneDirection&gt; cross section
336      * @throws NetworkException when a lane does not have any set speed limit
337      */
338     public static GraphCrossSection<KpiLaneDirection> createCrossSection(final List<String> names,
339             final DirectedLinkPosition linkPosition) throws NetworkException
340     {
341         Throw.whenNull(names, "Names may not be null.");
342         Throw.whenNull(linkPosition, "Link position may not be null.");
343         Throw.when(!(linkPosition.getLink() instanceof CrossSectionLink), IllegalArgumentException.class,
344                 "The link is not a CrossEctionLink.");
345         List<Lane> lanes = ((CrossSectionLink) linkPosition.getLink()).getLanes();
346         Throw.when(names.size() != lanes.size(), IllegalArgumentException.class,
347                 "Size of 'names' not equal to the number of lanes.");
348         Collections.sort(lanes, new Comparator<Lane>()
349         {
350             /** {@ingeritDoc} */
351             @Override
352             public int compare(final Lane o1, final Lane o2)
353             {
354                 int comp = o1.getDesignLineOffsetAtBegin().compareTo(o2.getDesignLineOffsetAtEnd());
355                 return linkPosition.getDirection().isPlus() ? comp : -comp;
356             }
357 
358         });
359         List<KpiLaneDirection> list = new ArrayList<>();
360         List<Length> positions = new ArrayList<>();
361         Speed speed = null;
362         for (Lane lane : lanes)
363         {
364             speed = speed == null ? lane.getLowestSpeedLimit() : Speed.min(speed, lane.getLowestSpeedLimit());
365             list.add(new KpiLaneDirection(new LaneData(lane),
366                     linkPosition.getDirection().isPlus() ? KpiGtuDirectionality.DIR_PLUS : KpiGtuDirectionality.DIR_MINUS));
367             positions.add(lane.getLength().times(linkPosition.getFractionalLongitudinalPosition()));
368         }
369         return createCrossSection(names, list, positions, speed);
370     }
371 
372     /**
373      * Creates a cross section.
374      * @param names List&lt;String&gt;;; names
375      * @param lanes List&lt;KpiLaneDirection&gt;;; lanes
376      * @param positions List&lt;Length&gt;; positions
377      * @param speed Speed; speed
378      * @return GraphCrossSection&lt;KpiLaneDirection&gt;; cross section
379      */
380     public static GraphCrossSection<KpiLaneDirection> createCrossSection(final List<String> names,
381             final List<KpiLaneDirection> lanes, final List<Length> positions, final Speed speed)
382     {
383         Section<KpiLaneDirection> section = new Section<KpiLaneDirection>()
384         {
385             /** {@inheritDoc} */
386             @Override
387             public Iterator<KpiLaneDirection> iterator()
388             {
389                 return lanes.iterator();
390             }
391 
392             /** {@inheritDoc} */
393             @Override
394             public Length getLength()
395             {
396                 return lanes.get(0).getLaneData().getLength();
397             }
398 
399             /** {@inheritDoc} */
400             @Override
401             public Speed getSpeedLimit()
402             {
403                 return speed;
404             }
405 
406             /** {@inheritDoc} */
407             @Override
408             public KpiLaneDirection getSource(final int series)
409             {
410                 return lanes.get(series);
411             }
412         };
413         return new GraphCrossSection<>(names, section, positions);
414     }
415 
416 }