1 package org.opentrafficsim.core.geometry;
2
3 import java.util.ArrayList;
4 import java.util.LinkedHashMap;
5 import java.util.List;
6 import java.util.Map;
7 import java.util.NavigableMap;
8 import java.util.TreeMap;
9
10 import org.djutils.draw.line.PolyLine2d;
11 import org.djutils.draw.point.Point2d;
12 import org.djutils.exceptions.Throw;
13
14 /**
15 * Flattens a continuous line in to a polyline.
16 * <p>
17 * Copyright (c) 2023-2024 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved. <br>
18 * BSD-style license. See <a href="https://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
19 * </p>
20 * @author <a href="https://github.com/averbraeck">Alexander Verbraeck</a>
21 * @author <a href="https://tudelft.nl/staff/p.knoppers-1">Peter Knoppers</a>
22 * @author <a href="https://github.com/wjschakel">Wouter Schakel</a>
23 */
24 @FunctionalInterface
25 public interface Flattener
26 {
27
28 /**
29 * Flatten continuous line in to a polyline.
30 * @param line FlattableLine; line function.
31 * @return PolyLine2d; flattened line.
32 */
33 PolyLine2d flatten(FlattableLine line);
34
35 /**
36 * Flattener based on number of segments.
37 * <p>
38 * Copyright (c) 2023-2024 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
39 * <br>
40 * BSD-style license. See <a href="https://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
41 * </p>
42 * @author <a href="https://github.com/averbraeck">Alexander Verbraeck</a>
43 * @author <a href="https://tudelft.nl/staff/p.knoppers-1">Peter Knoppers</a>
44 * @author <a href="https://github.com/wjschakel">Wouter Schakel</a>
45 */
46 public static class NumSegments implements Flattener
47 {
48 /** Number of segments. */
49 private final int numSegments;
50
51 /**
52 * Constructor.
53 * @param numSegments int; number of segments, must be at least 1.
54 */
55 public NumSegments(final int numSegments)
56 {
57 Throw.when(numSegments < 1, IllegalArgumentException.class, "Number of segments must be at least 1.");
58 this.numSegments = numSegments;
59 }
60
61 /** {@inheritDoc} */
62 @Override
63 public PolyLine2d flatten(final FlattableLine line)
64 {
65 Throw.whenNull(line, "Line function may not be null.");
66 List<Point2d> points = new ArrayList<>(this.numSegments + 1);
67 for (int i = 0; i <= this.numSegments; i++)
68 {
69 points.add(line.get(((double) i) / this.numSegments));
70 }
71 return new PolyLine2d(points);
72 }
73 }
74
75 /**
76 * Flattener based on maximum deviation.
77 * <p>
78 * Copyright (c) 2023-2024 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
79 * <br>
80 * BSD-style license. See <a href="https://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
81 * </p>
82 * @author <a href="https://github.com/averbraeck">Alexander Verbraeck</a>
83 * @author <a href="https://tudelft.nl/staff/p.knoppers-1">Peter Knoppers</a>
84 * @author <a href="https://github.com/wjschakel">Wouter Schakel</a>
85 */
86 public static class MaxDeviation implements Flattener
87 {
88 /** Maximum deviation. */
89 private final double maxDeviation;
90
91 /**
92 * Constructor.
93 * @param maxDeviation int; maximum deviation, must be above 0.0.
94 */
95 public MaxDeviation(final double maxDeviation)
96 {
97 Throw.when(maxDeviation <= 0.0, IllegalArgumentException.class, "Maximum deviation must be above 0.0.");
98 this.maxDeviation = maxDeviation;
99 }
100
101 /** {@inheritDoc} */
102 @Override
103 public PolyLine2d flatten(final FlattableLine line)
104 {
105 Throw.whenNull(line, "Line function may not be null.");
106 NavigableMap<Double, Point2d> result = new TreeMap<>();
107 result.put(0.0, line.get(0.0));
108 result.put(1.0, line.get(1.0));
109
110 // Walk along all point pairs and see if additional points need to be inserted
111 double prevT = result.firstKey();
112 Point2d prevPoint = result.get(prevT);
113 Map.Entry<Double, Point2d> entry;
114 while ((entry = result.higherEntry(prevT)) != null)
115 {
116 double nextT = entry.getKey();
117 Point2d nextPoint = entry.getValue();
118 double medianT = (prevT + nextT) / 2;
119 Point2d medianPoint = line.get(medianT);
120
121 // Check max deviation
122 Point2d projectedPoint = medianPoint.closestPointOnSegment(prevPoint, nextPoint);
123 double errorPosition = medianPoint.distance(projectedPoint);
124 if (errorPosition >= this.maxDeviation)
125 {
126 // We need to insert another point
127 result.put(medianT, medianPoint);
128 continue;
129 }
130
131 if (prevPoint.distance(nextPoint) > this.maxDeviation)
132 {
133 // Check for an inflection point by creating additional points at one quarter and three quarters. If these
134 // are on opposite sides of the line from prevPoint to nextPoint; there must be an inflection point.
135 // https://stackoverflow.com/questions/1560492/how-to-tell-whether-a-point-is-to-the-right-or-left-side-of-a-line
136 Point2d quarter = line.get((prevT + medianT) / 2);
137 int sign1 = (int) Math.signum((nextPoint.x - prevPoint.x) * (quarter.y - prevPoint.y)
138 - (nextPoint.y - prevPoint.y) * (quarter.x - prevPoint.x));
139 Point2d threeQuarter = line.get((nextT + medianT) / 2);
140 int sign2 = (int) Math.signum((nextPoint.x - prevPoint.x) * (threeQuarter.y - prevPoint.y)
141 - (nextPoint.y - prevPoint.y) * (threeQuarter.x - prevPoint.x));
142 if (sign1 != sign2)
143 {
144 // There is an inflection point, inserting the halfway point should take care of this
145 result.put(medianT, medianPoint);
146 continue;
147 }
148 }
149 prevT = nextT;
150 prevPoint = nextPoint;
151 }
152 return new PolyLine2d(result.values().iterator());
153 }
154 }
155
156 /**
157 * Flattener based on maximum deviation and maximum angle.
158 * <p>
159 * Copyright (c) 2023-2024 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
160 * <br>
161 * BSD-style license. See <a href="https://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
162 * </p>
163 * @author <a href="https://github.com/averbraeck">Alexander Verbraeck</a>
164 * @author <a href="https://tudelft.nl/staff/p.knoppers-1">Peter Knoppers</a>
165 * @author <a href="https://github.com/wjschakel">Wouter Schakel</a>
166 */
167 public static class MaxDeviationAndAngle implements Flattener
168 {
169 /** Maximum deviation. */
170 private final double maxDeviation;
171
172 /** Maximum angle. */
173 private final double maxAngle;
174
175 /**
176 * Constructor.
177 * @param maxDeviation int; maximum deviation, must be above 0.0.
178 * @param maxAngle int; maximum angle, must be above 0.0.
179 */
180 public MaxDeviationAndAngle(final double maxDeviation, final double maxAngle)
181 {
182 Throw.when(maxDeviation <= 0.0, IllegalArgumentException.class, "Maximum deviation must be above 0.0.");
183 Throw.when(maxAngle <= 0.0, IllegalArgumentException.class, "Maximum angle must be above 0.0.");
184 this.maxDeviation = maxDeviation;
185 this.maxAngle = maxAngle;
186 }
187
188 /** {@inheritDoc} */
189 @Override
190 public PolyLine2d flatten(final FlattableLine line)
191 {
192 NavigableMap<Double, Point2d> result = new TreeMap<>();
193 result.put(0.0, line.get(0.0));
194 result.put(1.0, line.get(1.0));
195 Map<Double, Double> directions = new LinkedHashMap<>();
196 directions.put(0.0, line.getDirection(0.0));
197 directions.put(1.0, line.getDirection(1.0));
198
199 // Walk along all point pairs and see if additional points need to be inserted
200 double prevT = result.firstKey();
201 Point2d prevPoint = result.get(prevT);
202 Map.Entry<Double, Point2d> entry;
203 int iterationsAtSinglePoint = 0;
204 while ((entry = result.higherEntry(prevT)) != null)
205 {
206 double nextT = entry.getKey();
207 Point2d nextPoint = entry.getValue();
208 double medianT = (prevT + nextT) / 2;
209 Point2d medianPoint = line.get(medianT);
210
211 // Check max deviation
212 Point2d projectedPoint = medianPoint.closestPointOnSegment(prevPoint, nextPoint);
213 double errorPosition = medianPoint.distance(projectedPoint);
214 if (errorPosition >= this.maxDeviation)
215 {
216 // We need to insert another point
217 result.put(medianT, medianPoint);
218 directions.put(medianT, line.getDirection(medianT)); // for angle checks
219 continue;
220 }
221
222 // Check max angle
223 double angle = prevPoint.directionTo(nextPoint) - directions.get(prevT);
224 while (angle < -Math.PI)
225 {
226 angle += 2 * Math.PI;
227 }
228 while (angle > Math.PI)
229 {
230 angle -= 2 * Math.PI;
231 }
232 if (Math.abs(angle) >= this.maxAngle)
233 {
234 // We need to insert another point
235 result.put(medianT, medianPoint);
236 directions.put(medianT, line.getDirection(medianT));
237 iterationsAtSinglePoint++;
238 Throw.when(iterationsAtSinglePoint == 50, RuntimeException.class,
239 "Required a new point 50 times at the same point. Likely the reported direction of the point does "
240 + "not match further points produced. Consider using the numerical approach in the "
241 + "default getDirection(fraction) method of the FlattableLine.");
242 continue;
243 }
244 iterationsAtSinglePoint = 0;
245
246 // Check for an inflection point by creating additional points at one quarter and three quarters. If these
247 // are on opposite sides of the line from prevPoint to nextPoint; there must be an inflection point.
248 // https://stackoverflow.com/questions/1560492/how-to-tell-whether-a-point-is-to-the-right-or-left-side-of-a-line
249 Point2d quarter = line.get((prevT + medianT) / 2);
250 int sign1 = (int) Math.signum((nextPoint.x - prevPoint.x) * (quarter.y - prevPoint.y)
251 - (nextPoint.y - prevPoint.y) * (quarter.x - prevPoint.x));
252 Point2d threeQuarter = line.get((nextT + medianT) / 2);
253 int sign2 = (int) Math.signum((nextPoint.x - prevPoint.x) * (threeQuarter.y - prevPoint.y)
254 - (nextPoint.y - prevPoint.y) * (threeQuarter.x - prevPoint.x));
255 if (sign1 != sign2)
256 {
257 // There is an inflection point, inserting the halfway point should take care of this
258 result.put(medianT, medianPoint);
259 directions.put(medianT, line.getDirection(medianT));
260 continue;
261 }
262 prevT = nextT;
263 prevPoint = nextPoint;
264 }
265 return new PolyLine2d(result.values().iterator());
266 }
267 }
268
269 /**
270 * Flattener based on maximum angle.
271 * <p>
272 * Copyright (c) 2023-2024 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
273 * <br>
274 * BSD-style license. See <a href="https://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
275 * </p>
276 * @author <a href="https://github.com/averbraeck">Alexander Verbraeck</a>
277 * @author <a href="https://tudelft.nl/staff/p.knoppers-1">Peter Knoppers</a>
278 * @author <a href="https://github.com/wjschakel">Wouter Schakel</a>
279 */
280 public static class MaxAngle implements Flattener
281 {
282 /** Maximum angle. */
283 private final double maxAngle;
284
285 /**
286 * Constructor.
287 * @param maxAngle int; maximum angle.
288 */
289 public MaxAngle(final double maxAngle)
290 {
291 Throw.when(maxAngle <= 0.0, IllegalArgumentException.class, "Maximum angle must be above 0.0.");
292 this.maxAngle = maxAngle;
293 }
294
295 /** {@inheritDoc} */
296 @Override
297 public PolyLine2d flatten(final FlattableLine line)
298 {
299 NavigableMap<Double, Point2d> result = new TreeMap<>();
300 result.put(0.0, line.get(0.0));
301 result.put(1.0, line.get(1.0));
302 Map<Double, Double> directions = new LinkedHashMap<>();
303 directions.put(0.0, line.getDirection(0.0));
304 directions.put(1.0, line.getDirection(1.0));
305
306 // Walk along all point pairs and see if additional points need to be inserted
307 double prevT = result.firstKey();
308 Point2d prevPoint = result.get(prevT);
309 Map.Entry<Double, Point2d> entry;
310 int iterationsAtSinglePoint = 0;
311 while ((entry = result.higherEntry(prevT)) != null)
312 {
313 double nextT = entry.getKey();
314 Point2d nextPoint = entry.getValue();
315 double medianT = (prevT + nextT) / 2;
316
317 // Check max angle
318 double angle = prevPoint.directionTo(nextPoint) - directions.get(prevT);
319 while (angle < -Math.PI)
320 {
321 angle += 2 * Math.PI;
322 }
323 while (angle > Math.PI)
324 {
325 angle -= 2 * Math.PI;
326 }
327 if (Math.abs(angle) >= this.maxAngle)
328 {
329 // We need to insert another point
330 Point2d medianPoint = line.get(medianT);
331 result.put(medianT, medianPoint);
332 directions.put(medianT, line.getDirection(medianT));
333 iterationsAtSinglePoint++;
334 Throw.when(iterationsAtSinglePoint == 50, RuntimeException.class,
335 "Required a new point 50 times at the same point. Likely the reported direction of the point does "
336 + "not match further points produced. Consider using the numerical approach in the "
337 + "default getDirection(fraction) method of the FlattableLine.");
338 continue;
339 }
340 iterationsAtSinglePoint = 0;
341
342 // Check for an inflection point by creating additional points at one quarter and three quarters. If these
343 // are on opposite sides of the line from prevPoint to nextPoint; there must be an inflection point.
344 // https://stackoverflow.com/questions/1560492/how-to-tell-whether-a-point-is-to-the-right-or-left-side-of-a-line
345 Point2d quarter = line.get((prevT + medianT) / 2);
346 int sign1 = (int) Math.signum((nextPoint.x - prevPoint.x) * (quarter.y - prevPoint.y)
347 - (nextPoint.y - prevPoint.y) * (quarter.x - prevPoint.x));
348 Point2d threeQuarter = line.get((nextT + medianT) / 2);
349 int sign2 = (int) Math.signum((nextPoint.x - prevPoint.x) * (threeQuarter.y - prevPoint.y)
350 - (nextPoint.y - prevPoint.y) * (threeQuarter.x - prevPoint.x));
351 if (sign1 != sign2)
352 {
353 // There is an inflection point, inserting the halfway point should take care of this
354 Point2d medianPoint = line.get(medianT);
355 result.put(medianT, medianPoint);
356 directions.put(medianT, line.getDirection(medianT));
357 continue;
358 }
359 prevT = nextT;
360 prevPoint = nextPoint;
361 }
362 return new PolyLine2d(result.values().iterator());
363 }
364 }
365
366 }