View Javadoc
1   package org.djutils.draw.curve;
2   
3   import java.util.ArrayList;
4   import java.util.HashSet;
5   import java.util.LinkedHashMap;
6   import java.util.List;
7   import java.util.Map;
8   import java.util.NavigableMap;
9   import java.util.Set;
10  import java.util.TreeMap;
11  
12  import org.djutils.draw.function.ContinuousPiecewiseLinearFunction;
13  import org.djutils.draw.line.PolyLine2d;
14  import org.djutils.draw.point.Point2d;
15  import org.djutils.exceptions.Throw;
16  import org.djutils.math.AngleUtil;
17  import org.djutils.math.functions.MathFunction.TupleSt;
18  
19  /**
20   * Flattens a Curve2d with piece-wise linear offset in to a PolyLine2d.
21   * <p>
22   * Copyright (c) 2023-2025 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved. <br>
23   * BSD-style license. See <a href="https://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
24   * </p>
25   * @author <a href="https://github.com/averbraeck">Alexander Verbraeck</a>
26   * @author <a href="https://github.com/peter-knoppers">Peter Knoppers</a>
27   * @author <a href="https://github.com/wjschakel">Wouter Schakel</a>
28   */
29  public interface OffsetFlattener2d extends Flattener<Flattener2d, Curve2d, PolyLine2d, Point2d, Double>
30  {
31      /**
32       * Flatten a OffsetCurve2d curve into a PolyLine2d while applying lateral offsets.
33       * @param curve the curve
34       * @param of the lateral offset to apply
35       * @return flattened curve
36       */
37      PolyLine2d flatten(OffsetCurve2d curve, ContinuousPiecewiseLinearFunction of);
38  
39      /**
40       * Load one knot in the map of fractions and points.
41       * @param map the map
42       * @param knot the fraction where the knot occurs
43       * @param curve the curve that can compute the point for each <code>knot</code> position
44       * @param of offset data
45       * @throws NullPointerException when <code>map</code> is <code>null</code>, <code>knot</code> is <code>null</code>,
46       *             <code>curve</code> is <code>null</code>, or <code>of</code> is <code>null</code>
47       * @throws IllegalArgumentException when <code>knot &lt; 0.0</code>, or <code>knot &gt; 1.0</code>
48       */
49      default void loadKnot(final NavigableMap<Double, Point2d> map, final double knot, final OffsetCurve2d curve,
50              final ContinuousPiecewiseLinearFunction of)
51      {
52          Throw.when(knot < 0.0 || knot > 1.0, IllegalArgumentException.class, "Knots must all be between 0.0 and 1.0, (got %f)",
53                  knot);
54          double t = curve.getT(knot * curve.getLength());
55          if (map.containsKey(t))
56          {
57              return;
58          }
59          map.put(t, curve.getPoint(t, of));
60      }
61  
62      /**
63       * Load the knots into the navigable map (including the start point and the end point).
64       * @param map the navigable map
65       * @param curve the curve
66       * @param of the offset data
67       */
68      default void loadKnots(final NavigableMap<Double, Point2d> map, final OffsetCurve2d curve,
69              final ContinuousPiecewiseLinearFunction of)
70      {
71          map.put(0.0, curve.getPoint(0.0, of));
72          Set<Double> knots = curve.getKnots();
73          if (null != knots)
74          {
75              for (double knot : knots)
76              {
77                  loadKnot(map, knot, curve, of);
78              }
79          }
80          for (TupleSt knot : of)
81          {
82              loadKnot(map, knot.s(), curve, of);
83          }
84          map.put(1.0, curve.getPoint(1.0, of));
85      }
86  
87      @Override
88      default boolean checkLoopBack(final Double prevDirection, final Double nextDirection)
89      {
90          return Math.abs(AngleUtil.normalizeAroundZero(nextDirection - prevDirection)) > Math.PI / 2;
91      }
92  
93      @Override
94      default boolean checkDirectionError(final Double segmentDirection, final Double curveDirectionAtStart,
95              final Double curveDirectionAtEnd, final double maxDirectionDeviation)
96      {
97          return (Math.abs(AngleUtil.normalizeAroundZero(segmentDirection - curveDirectionAtStart)) > maxDirectionDeviation)
98                  || Math.abs(AngleUtil.normalizeAroundZero(segmentDirection - curveDirectionAtEnd)) >= maxDirectionDeviation;
99      }
100 
101     /**
102      * Make a FlattableCurve object.
103      * @param curve the curve
104      * @param of the offset function
105      * @return the flattable curve
106      */
107     default Flattener.FlattableCurve<Point2d, Double> makeFlattableCurve(final OffsetCurve2d curve,
108             final ContinuousPiecewiseLinearFunction of)
109     {
110         return new Flattener.FlattableCurve<Point2d, Double>()
111         {
112             @Override
113             public Point2d getPoint(final double fraction)
114             {
115                 return curve.getPoint(fraction, of);
116             }
117 
118             @Override
119             public Double getDirection(final double fraction)
120             {
121                 return curve.getDirection(fraction, of);
122             }
123         };
124     }
125 
126     /**
127      * Flattener that approximates the <code>OffsetCurve2d</code> with a specified number of segments.
128      */
129     class NumSegments implements OffsetFlattener2d
130     {
131         /** Number of segments. */
132         private final int numSegments;
133 
134         /**
135          * Construct a flattener that approximates the <code>OffsetCurve2d</code> with a specified number of segments.
136          * @param numSegments number of segments to use in the construction of the <code>PolyLine2d</code>
137          * @throws IllegalArgumentException when <code>numSegments &lt; 1</code>
138          */
139         public NumSegments(final int numSegments)
140         {
141             Throw.when(numSegments < 1, IllegalArgumentException.class, "Number of segments must be at least 1.");
142             this.numSegments = numSegments;
143         }
144 
145         @Override
146         public PolyLine2d flatten(final OffsetCurve2d curve, final ContinuousPiecewiseLinearFunction of)
147         {
148             Throw.whenNull(curve, "curve");
149             List<Point2d> points = new ArrayList<>(this.numSegments + 1);
150             for (int i = 0; i <= this.numSegments; i++)
151             {
152                 double fraction = ((double) i) / this.numSegments;
153                 points.add(curve.getPoint(fraction, of));
154             }
155             return new PolyLine2d(points);
156         }
157     }
158 
159     /**
160      * Flattener that limits the distance between the <code>OffsetCurvee2d</code> and the <code>PolyLine2d</code>.
161      */
162     class MaxDeviation implements OffsetFlattener2d
163     {
164         /** Maximum deviation. */
165         private final double maxDeviation;
166 
167         /**
168          * Construct an OffsetFlattener that limits the distance between the <code>OffsetCurve2d</code> and the
169          * <code>PolyLine2d</code>.
170          * @param maxDeviation maximum deviation, must be above 0.0
171          * @throws ArithmeticException when <code>maxDeviation</code> is <code>NaN</code>
172          * @throws IllegalArgumentException when <code>maxDeviation &le; 0.0</code>
173          */
174         public MaxDeviation(final double maxDeviation)
175         {
176             Throw.whenNaN(maxDeviation, "maxDeviation");
177             Throw.when(maxDeviation <= 0.0, IllegalArgumentException.class, "Maximum deviation must be above 0.0 and finite");
178             this.maxDeviation = maxDeviation;
179         }
180 
181         @Override
182         public PolyLine2d flatten(final OffsetCurve2d curve, final ContinuousPiecewiseLinearFunction of)
183         {
184             Throw.whenNull(curve, "curve");
185             Flattener.FlattableCurve<Point2d, Double> fc = makeFlattableCurve(curve, of);
186             NavigableMap<Double, Point2d> result = new TreeMap<>();
187             loadKnots(result, curve, of);
188 
189             // Walk along all point pairs and see if additional points need to be inserted
190             double prevT = result.firstKey();
191             Point2d prevPoint = result.get(prevT);
192             Map.Entry<Double, Point2d> entry;
193             while ((entry = result.higherEntry(prevT)) != null)
194             {
195                 double nextT = entry.getKey();
196                 Point2d nextPoint = entry.getValue();
197                 double medianT = (prevT + nextT) / 2;
198                 Point2d medianPoint = curve.getPoint(medianT, of);
199                 // Check max deviation
200                 if (checkPositionError(medianPoint, prevPoint, nextPoint, this.maxDeviation))
201                 {
202                     // We need to insert another point
203                     result.put(medianT, medianPoint);
204                     continue;
205                 }
206                 if (prevPoint.distance(nextPoint) > this.maxDeviation
207                         && checkInflectionPoint(fc, prevT, medianT, nextT, prevPoint, nextPoint))
208                 {
209                     // There is an inflection point, inserting the halfway point should take care of this
210                     result.put(medianT, medianPoint);
211                     continue;
212                 }
213                 if (checkLoopBack(curve.getDirection(prevT), curve.getDirection(nextT)))
214                 {
215                     // The curve loops back onto itself. Inserting the halfway point should prevent missing out a major detour
216                     // This check is NOT needed in the MaxDeviationAndAngle flattener.
217                     result.put(medianT, medianPoint);
218                     continue;
219                 }
220                 prevT = nextT;
221                 prevPoint = nextPoint;
222             }
223             return new PolyLine2d(result.values().iterator());
224         }
225     }
226 
227     /**
228      * OffsetFlattener that limits distance <b>and</b> angle difference between the <code>OffsetCurve2d</code> and the
229      * <code>PolyLine2d</code>.
230      */
231     class MaxDeviationAndAngle implements OffsetFlattener2d
232     {
233         /** Maximum deviation. */
234         private final double maxDeviation;
235 
236         /** Maximum angle. */
237         private final double maxAngle;
238 
239         /**
240          * Construct a flattener that limits distance <b>and</b> angle difference between the <code>OffsetCurve2d</code> and the
241          * <code>PolyLine2d</code>.
242          * @param maxDeviation maximum deviation, must be above 0.0
243          * @param maxAngle maximum angle, must be above 0.0
244          * @throws ArithmeticException when <code>maxDeviation</code>, or <code>maxAngle</code> is <code>NaN</code>
245          * @throws IllegalArgumentException when <code>maxDeviation &le; 0.0</code>, or <code>maxAngle &le; 0.0</code>
246          */
247         public MaxDeviationAndAngle(final double maxDeviation, final double maxAngle)
248         {
249             Throw.whenNaN(maxDeviation, "maxDeviation");
250             Throw.whenNaN(maxAngle, "maxAngle");
251             Throw.when(maxDeviation <= 0.0, IllegalArgumentException.class, "Maximum deviation must be above 0.0.");
252             Throw.when(maxAngle <= 0.0, IllegalArgumentException.class, "Maximum angle must be above 0.0.");
253             this.maxDeviation = maxDeviation;
254             this.maxAngle = maxAngle;
255         }
256 
257         @Override
258         public PolyLine2d flatten(final OffsetCurve2d curve, final ContinuousPiecewiseLinearFunction of)
259         {
260             Throw.whenNull(curve, "curve");
261             Flattener.FlattableCurve<Point2d, Double> fc = makeFlattableCurve(curve, of);
262             NavigableMap<Double, Point2d> result = new TreeMap<>();
263             loadKnots(result, curve, of);
264             Map<Double, Double> directions = new LinkedHashMap<>();
265             directions.put(0.0, curve.getDirection(0.0, of)); // directions can't do ULP before 0.0
266             Set<Double> knots = new HashSet<>();
267             for (double knot : result.keySet())
268             {
269                 if (knot > 0)
270                 {
271                     directions.put(knot, curve.getDirection(knot - Math.ulp(knot), of));
272                 }
273                 if (knot != 0.0 && knot != 1.0)
274                 {
275                     knots.add(knot);
276                 }
277             }
278 
279             // Walk along all point pairs and see if additional points need to be inserted
280             double prevT = result.firstKey();
281             Point2d prevPoint = result.get(prevT);
282             Map.Entry<Double, Point2d> entry;
283             int iterationsAtSinglePoint = 0;
284             while ((entry = result.higherEntry(prevT)) != null)
285             {
286                 double nextT = entry.getKey();
287                 Point2d nextPoint = entry.getValue();
288                 double medianT = (prevT + nextT) / 2;
289                 Point2d medianPoint = curve.getPoint(medianT, of);
290                 // Check max deviation
291                 if (checkPositionError(medianPoint, prevPoint, nextPoint, this.maxDeviation))
292                 {
293                     // We need to insert another point
294                     result.put(medianT, medianPoint);
295                     directions.put(medianT, curve.getDirection(medianT, of));
296                     continue;
297                 }
298                 // Check max angle
299                 if (checkDirectionError(prevPoint.directionTo(nextPoint), directions.get(prevT), directions.get(nextT),
300                         this.maxAngle))
301                 {
302                     // We need to insert another point
303                     result.put(medianT, medianPoint);
304                     directions.put(medianT, curve.getDirection(medianT, of));
305                     iterationsAtSinglePoint++;
306                     Throw.when(iterationsAtSinglePoint == 50, IllegalArgumentException.class, "Required a new point 50 times "
307                             + "around the same point (t=%f). Likely there is an (unreported) knot in the OffsetCurve2d.",
308                             medianT);
309                     continue;
310                 }
311                 iterationsAtSinglePoint = 0;
312                 if (prevPoint.distance(nextPoint) > this.maxDeviation
313                         && checkInflectionPoint(fc, prevT, medianT, nextT, prevPoint, nextPoint))
314                 {
315                     // There is an inflection point, inserting the halfway point should take care of this
316                     result.put(medianT, medianPoint);
317                     directions.put(medianT, curve.getDirection(medianT, of));
318                     continue;
319                 }
320                 prevT = nextT;
321                 prevPoint = nextPoint;
322                 if (prevT < 1.0 && knots.contains(prevT))
323                 {
324                     directions.put(prevT, curve.getDirection(prevT + Math.ulp(prevT), of));
325                 }
326             }
327             return new PolyLine2d(result.values().iterator());
328         }
329     }
330 
331     /**
332      * OffsetFlattener that limits the angle difference between the <code>OffsetCurve2d</code> and the <code>PolyLine2d</code>.
333      */
334     class MaxAngle implements OffsetFlattener2d
335     {
336         /** Maximum angle. */
337         private final double maxAngle;
338 
339         /**
340          * Construct a flattener that limits the angle difference between the <code>OffsetCurve2d</code> and the
341          * <code>PolyLine2d</code>.
342          * @param maxAngle maximum angle.
343          * @throws ArithmeticException when <code>maxAngle</code> is <code>NaN</code>
344          * @throws IllegalArgumentException when <code>maxAngle &le; 0.0</code>
345          */
346         public MaxAngle(final double maxAngle)
347         {
348             Throw.whenNaN(maxAngle, "maxAngle");
349             Throw.when(maxAngle <= 0.0, IllegalArgumentException.class, "Maximum angle must be above 0.0.");
350             this.maxAngle = maxAngle;
351         }
352 
353         @Override
354         public PolyLine2d flatten(final OffsetCurve2d curve, final ContinuousPiecewiseLinearFunction of)
355         {
356             Throw.whenNull(curve, "curve");
357             Flattener.FlattableCurve<Point2d, Double> fc = makeFlattableCurve(curve, of);
358             NavigableMap<Double, Point2d> result = new TreeMap<>();
359             loadKnots(result, curve, of);
360             Map<Double, Double> directions = new LinkedHashMap<>();
361             directions.put(0.0, curve.getDirection(0.0, of)); // directions can't do ULP before 0.0
362             Set<Double> knots = new HashSet<>();
363             for (double knot : result.keySet())
364             {
365                 if (knot > 0)
366                 {
367                     directions.put(knot, curve.getDirection(knot - Math.ulp(knot), of));
368                 }
369                 if (knot != 0.0 && knot != 1.0)
370                 {
371                     knots.add(knot);
372                 }
373             }
374 
375             // Walk along all point pairs and see if additional points need to be inserted
376             double prevT = result.firstKey();
377             Point2d prevPoint = result.get(prevT);
378             Map.Entry<Double, Point2d> entry;
379             int iterationsAtSinglePoint = 0;
380             while ((entry = result.higherEntry(prevT)) != null)
381             {
382                 double nextT = entry.getKey();
383                 Point2d nextPoint = entry.getValue();
384                 double medianT = (prevT + nextT) / 2;
385 
386                 // Check max angle
387                 if (checkDirectionError(prevPoint.directionTo(nextPoint), directions.get(prevT), directions.get(nextT),
388                         this.maxAngle))
389                 {
390                     // We need to insert another point
391                     Point2d medianPoint = curve.getPoint(medianT, of);
392                     result.put(medianT, medianPoint);
393                     directions.put(medianT, curve.getDirection(medianT, of));
394                     iterationsAtSinglePoint++;
395                     Throw.when(iterationsAtSinglePoint == 50, IllegalArgumentException.class, "Required a new point 50 "
396                             + "times around the same point (t=%f). Likely there is an (unreported) knot in the OffsetCurve2d.",
397                             medianT);
398                     continue;
399                 }
400                 iterationsAtSinglePoint = 0;
401                 if (checkInflectionPoint(fc, prevT, medianT, nextT, prevPoint, nextPoint))
402                 {
403                     // There is an inflection point, inserting the halfway point should take care of this
404                     Point2d medianPoint = curve.getPoint(medianT, of);
405                     result.put(medianT, medianPoint);
406                     directions.put(medianT, curve.getDirection(medianT, of));
407                     continue;
408                 }
409                 prevT = nextT;
410                 prevPoint = nextPoint;
411                 if (knots.contains(prevT))
412                 {
413                     directions.put(prevT, curve.getDirection(prevT + Math.ulp(prevT), of));
414                 }
415             }
416             return new PolyLine2d(result.values().iterator());
417         }
418     }
419 
420 }