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.line.PolyLine2d;
13 import org.djutils.draw.point.Point2d;
14 import org.djutils.exceptions.Throw;
15 import org.djutils.math.AngleUtil;
16
17
18
19
20
21
22
23
24
25
26
27 public interface Flattener2d extends Flattener<Flattener2d, Curve2d, PolyLine2d, Point2d, Double>
28 {
29
30
31
32
33
34
35 PolyLine2d flatten(Curve2d curve);
36
37 @Override
38 default boolean checkLoopBack(final Double prevDirection, final Double nextDirection)
39 {
40 return Math.abs(AngleUtil.normalizeAroundZero(nextDirection - prevDirection)) > Math.PI / 2;
41 }
42
43 @Override
44 default boolean checkDirectionError(final Double segmentDirection, final Double curveDirectionAtStart,
45 final Double curveDirectionAtEnd, final double maxDirectionDeviation)
46 {
47 return (Math.abs(AngleUtil.normalizeAroundZero(segmentDirection - curveDirectionAtStart)) > maxDirectionDeviation)
48 || Math.abs(AngleUtil.normalizeAroundZero(segmentDirection - curveDirectionAtEnd)) >= maxDirectionDeviation;
49 }
50
51
52
53
54 class NumSegments implements Flattener2d
55 {
56
57 private final int numSegments;
58
59
60
61
62
63
64 public NumSegments(final int numSegments)
65 {
66 Throw.when(numSegments < 1, IllegalArgumentException.class, "Number of segments must be at least 1");
67 this.numSegments = numSegments;
68 }
69
70 @Override
71 public PolyLine2d flatten(final Curve2d curve) throws NullPointerException
72 {
73 Throw.whenNull(curve, "curve");
74 List<Point2d> points = new ArrayList<>(this.numSegments + 1);
75 for (int i = 0; i <= this.numSegments; i++)
76 {
77 double fraction = ((double) i) / this.numSegments;
78 points.add(curve.getPoint(fraction));
79 }
80 return new PolyLine2d(points);
81 }
82 }
83
84
85
86
87 class MaxDeviation implements Flattener2d
88 {
89
90 private final double maxDeviation;
91
92
93
94
95
96
97
98 public MaxDeviation(final double maxDeviation)
99 {
100 Throw.whenNaN(maxDeviation, "maxDeviation");
101 Throw.when(maxDeviation <= 0.0, IllegalArgumentException.class, "Maximum deviation must be above 0.0 and finite");
102 this.maxDeviation = maxDeviation;
103 }
104
105 @Override
106 public PolyLine2d flatten(final Curve2d curve)
107 {
108 Throw.whenNull(curve, "curve");
109 NavigableMap<Double, Point2d> result = new TreeMap<>();
110 loadKnots(result, curve);
111
112
113 double prevT = result.firstKey();
114 Point2d prevPoint = result.get(prevT);
115 Map.Entry<Double, Point2d> entry;
116 while ((entry = result.higherEntry(prevT)) != null)
117 {
118 double nextT = entry.getKey();
119 Point2d nextPoint = entry.getValue();
120 double medianT = (prevT + nextT) / 2;
121 Point2d medianPoint = curve.getPoint(medianT);
122
123 if (checkPositionError(medianPoint, prevPoint, nextPoint, this.maxDeviation))
124 {
125
126 result.put(medianT, medianPoint);
127 continue;
128 }
129 if (prevPoint.distance(nextPoint) > this.maxDeviation
130 && checkInflectionPoint(curve, prevT, medianT, nextT, prevPoint, nextPoint))
131 {
132
133 result.put(medianT, medianPoint);
134 continue;
135 }
136 if (checkLoopBack(curve.getDirection(prevT), curve.getDirection(nextT)))
137 {
138
139
140 result.put(medianT, medianPoint);
141 continue;
142 }
143 prevT = nextT;
144 prevPoint = nextPoint;
145 }
146 return new PolyLine2d(result.values().iterator());
147 }
148 }
149
150
151
152
153
154 class MaxDeviationAndAngle implements Flattener2d
155 {
156
157 private final double maxDeviation;
158
159
160 private final double maxAngle;
161
162
163
164
165
166
167
168
169
170 public MaxDeviationAndAngle(final double maxDeviation, final double maxAngle)
171 {
172 Throw.whenNaN(maxDeviation, "maxDeviation");
173 Throw.whenNaN(maxAngle, "maxAngle");
174 Throw.when(maxDeviation <= 0.0, IllegalArgumentException.class, "Maximum deviation must be above 0.0");
175 Throw.when(maxAngle <= 0.0, IllegalArgumentException.class, "Maximum angle must be above 0.0");
176 this.maxDeviation = maxDeviation;
177 this.maxAngle = maxAngle;
178 }
179
180 @Override
181 public PolyLine2d flatten(final Curve2d curve) throws NullPointerException
182 {
183 NavigableMap<Double, Point2d> result = new TreeMap<>();
184 loadKnots(result, curve);
185 Map<Double, Double> directions = new LinkedHashMap<>();
186 Set<Double> knots = new HashSet<>();
187 for (double fraction : result.keySet())
188 {
189 directions.put(fraction, curve.getDirection(fraction));
190 knots.add(fraction);
191 }
192
193
194 double prevT = result.firstKey();
195 Point2d prevPoint = result.get(prevT);
196 Map.Entry<Double, Point2d> entry;
197 int iterationsAtSinglePoint = 0;
198 while ((entry = result.higherEntry(prevT)) != null)
199 {
200 double nextT = entry.getKey();
201 Point2d nextPoint = entry.getValue();
202 double medianT = (prevT + nextT) / 2;
203 Point2d medianPoint = curve.getPoint(medianT);
204
205 if (checkPositionError(medianPoint, prevPoint, nextPoint, this.maxDeviation))
206 {
207
208 result.put(medianT, medianPoint);
209 directions.put(medianT, curve.getDirection(medianT));
210 continue;
211 }
212
213 if (checkDirectionError(prevPoint.directionTo(nextPoint), directions.get(prevT), directions.get(nextT),
214 this.maxAngle))
215 {
216
217 result.put(medianT, medianPoint);
218 directions.put(medianT, curve.getDirection(medianT));
219 iterationsAtSinglePoint++;
220 Throw.when(iterationsAtSinglePoint == 50, IllegalArgumentException.class,
221 "Required a new point 50 times "
222 + "around the same point (t=%f). Likely there is an (unreported) knot in the Curve2d.",
223 medianT);
224 continue;
225 }
226 iterationsAtSinglePoint = 0;
227 if (prevPoint.distance(nextPoint) > this.maxDeviation
228 && checkInflectionPoint(curve, prevT, medianT, nextT, prevPoint, nextPoint))
229 {
230
231 result.put(medianT, medianPoint);
232 directions.put(medianT, curve.getDirection(medianT));
233 continue;
234 }
235 prevT = nextT;
236 prevPoint = nextPoint;
237 if (knots.contains(prevT))
238 {
239 directions.put(prevT, curve.getDirection(prevT + Math.ulp(prevT)));
240 }
241 }
242 return new PolyLine2d(result.values().iterator());
243 }
244 }
245
246
247
248
249 class MaxAngle implements Flattener2d
250 {
251
252 private final double maxAngle;
253
254
255
256
257
258
259
260 public MaxAngle(final double maxAngle)
261 {
262 Throw.whenNaN(maxAngle, "maxAngle");
263 Throw.when(maxAngle <= 0.0, IllegalArgumentException.class, "Maximum angle must be above 0.0");
264 this.maxAngle = maxAngle;
265 }
266
267 @Override
268 public PolyLine2d flatten(final Curve2d curve)
269 {
270 NavigableMap<Double, Point2d> result = new TreeMap<>();
271 loadKnots(result, curve);
272 Map<Double, Double> directions = new LinkedHashMap<>();
273 directions.put(0.0, curve.getDirection(0.0));
274 Set<Double> knots = new HashSet<>();
275 for (double knot : result.keySet())
276 {
277 if (knot > 0)
278 {
279 directions.put(knot, curve.getDirection(knot - Math.ulp(knot)));
280 }
281 if (knot != 0.0 && knot != 1.0)
282 {
283 knots.add(knot);
284 }
285 }
286
287
288 double prevT = result.firstKey();
289 Point2d prevPoint = result.get(prevT);
290 Map.Entry<Double, Point2d> entry;
291 int iterationsAtSinglePoint = 0;
292 while ((entry = result.higherEntry(prevT)) != null)
293 {
294 double nextT = entry.getKey();
295 Point2d nextPoint = entry.getValue();
296 double medianT = (prevT + nextT) / 2;
297
298
299 if (checkDirectionError(prevPoint.directionTo(nextPoint), directions.get(prevT), directions.get(nextT),
300 this.maxAngle))
301 {
302
303 Point2d medianPoint = curve.getPoint(medianT);
304 result.put(medianT, medianPoint);
305 directions.put(medianT, curve.getDirection(medianT));
306 iterationsAtSinglePoint++;
307 Throw.when(iterationsAtSinglePoint == 50, IllegalArgumentException.class, "Required a new point 50 "
308 + "times around the same point (t=%f). Likely there is an (unreported) knot in the Curve2d.",
309 medianT);
310 continue;
311 }
312 iterationsAtSinglePoint = 0;
313 if (checkInflectionPoint(curve, prevT, medianT, nextT, prevPoint, nextPoint))
314 {
315
316 Point2d medianPoint = curve.getPoint(medianT);
317 result.put(medianT, medianPoint);
318 directions.put(medianT, curve.getDirection(medianT));
319 continue;
320 }
321 prevT = nextT;
322 prevPoint = nextPoint;
323 if (knots.contains(prevT))
324 {
325 directions.put(prevT, curve.getDirection(prevT + Math.ulp(prevT)));
326 }
327 }
328 return new PolyLine2d(result.values().iterator());
329 }
330 }
331
332 }