1 package org.djutils.draw.line;
2
3 import java.util.ArrayList;
4 import java.util.List;
5
6 import org.djutils.draw.DrawRuntimeException;
7 import org.djutils.draw.Drawable;
8 import org.djutils.draw.point.Point;
9
10 /**
11 * PolyLine is the interface for PolyLine2d and PolyLine3d implementations.
12 * <p>
13 * Copyright (c) 2020-2023 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved. <br>
14 * BSD-style license. See <a href="https://djutils.org/docs/current/djutils/licenses.html">DJUTILS License</a>.
15 * </p>
16 * @author <a href="https://www.tudelft.nl/averbraeck">Alexander Verbraeck</a>
17 * @author <a href="https://www.tudelft.nl/pknoppers">Peter Knoppers</a>
18 * @param <L> the PolyLine type (2d or 3d)
19 * @param <P> The matching Point type (2d or 3d)
20 * @param <R> The matching Ray type (2d or 3d)
21 * @param <LS> The matching LineSegment type (2d or 3d)
22 */
23 public interface PolyLine<L extends PolyLine<L, P, R, LS>, P extends Point<P>, R extends Ray<R, P>,
24 LS extends LineSegment<P, R>> extends Drawable<P>, Project<P>
25 {
26 /**
27 * Constructor that can be accessed as a method (used to implement default methods in this interface).
28 * @param pointList List<P>; a list of points
29 * @return L; the new PolyLine
30 * @throws NullPointerException when pointList is null
31 * @throws DrawRuntimeException when pointList has fewer than two points or contains successive duplicate points
32 */
33 L instantiate(List<P> pointList) throws NullPointerException, DrawRuntimeException;
34
35 /**
36 * Construct a new PolyLine that is equal to this line except for segments that are shorter than the
37 * <cite>noiseLevel</cite>. The result is guaranteed to start with the first point of this line and end with the last point
38 * of this line.
39 * @param noiseLevel double; the minimum segment length that is <b>not</b> removed
40 * @return PolyLine2d; the filtered line
41 */
42 L noiseFilteredLine(double noiseLevel);
43
44 /**
45 * Return the length of this line. This is NOT the number of points; it is the sum of the lengths of the segments.
46 * @return double; the length of this line
47 */
48 double getLength();
49
50 /**
51 * Return one of the points of this line.
52 * @param index int; the index of the requested point
53 * @return P; the point at the specified index
54 * @throws IndexOutOfBoundsException when index < 0 or index >= size
55 */
56 P get(int index) throws IndexOutOfBoundsException;
57
58 /**
59 * Return the x-coordinate of a point of this PolyLine.
60 * @param index int; the index of the requested x-coordinate
61 * @return double; the x-coordinate of the requested point of this PolyLine
62 * @throws IndexOutOfBoundsException when index < 0 or index >= size()
63 */
64 double getX(int index) throws IndexOutOfBoundsException;
65
66 /**
67 * Return the y-coordinate of a point of this PolyLine.
68 * @param index int; the index of the requested y-coordinate
69 * @return double; the y-coordinate of the requested point of this PolyLine
70 * @throws IndexOutOfBoundsException when index < 0 or index >= size()
71 */
72 double getY(int index) throws IndexOutOfBoundsException;
73
74 /**
75 * Return the first point of this PolyLine.
76 * @return P; the first point of this line
77 */
78 default P getFirst()
79 {
80 try
81 {
82 return get(0);
83 }
84 catch (IndexOutOfBoundsException ioobe)
85 {
86 throw new RuntimeException("cannot happen");
87 }
88 }
89
90 /**
91 * Return the last point of this PolyLine.
92 * @return P; the last point of this line
93 */
94 default P getLast()
95 {
96 try
97 {
98 return get(size() - 1);
99 }
100 catch (IndexOutOfBoundsException ioobe)
101 {
102 throw new RuntimeException("cannot happen");
103 }
104 }
105
106 /**
107 * Extract one LineSegment of this PolyLine, or Polygon.
108 * @param index int; the rank number of the segment; must be in range 0..Size() - 2 for PolyLine, or 0.. Size() - 1 for
109 * Polygon.
110 * @return LS; the LineSegment that connects point index to point index + 1
111 */
112 LS getSegment(int index);
113
114 /**
115 * Access the internal lengthIndexedLine. Return the cumulative length up to point <code>index</code> of this line
116 * @param index int; the index
117 * @return double; the cumulative length of this line up to point <code>index</code>
118 * @throws IndexOutOfBoundsException when index < 0 or index >= size()
119 */
120 double lengthAtIndex(int index) throws IndexOutOfBoundsException;
121
122 /**
123 * Construct a new PolyLine with all points of this PolyLine in reverse order.
124 * @return L; the new PolyLine
125 */
126 default L reverse()
127 {
128 List<P> reversedPoints = new ArrayList<>(size());
129 for (int index = size(); --index >= 0;)
130 {
131 reversedPoints.add(get(index));
132 }
133 return instantiate(reversedPoints);
134 }
135
136 /**
137 * Construct a new PolyLine covering the indicated fraction of this PolyLine.
138 * @param start double; fractional starting position, valid range [0..<cite>end</cite>)
139 * @param end double; fractional ending position, valid range (<cite>start</cite>..1]
140 * @return L; a new PolyLine covering the selected sub-section
141 * @throws DrawRuntimeException when start >= end, or start < 0, or end > 1
142 */
143 default L extractFractional(final double start, final double end) throws DrawRuntimeException
144 {
145 if (start < 0 || start >= end || end > 1)
146 {
147 throw new DrawRuntimeException(
148 "Bad interval (start=" + start + ", end=" + end + ", this is " + this.toString() + ")");
149 }
150 return extract(start * getLength(), end * getLength());
151 }
152
153 /**
154 * Create a new PolyLine that covers a sub-section of this PolyLine.
155 * @param start double; length along this PolyLine where the sub-section starts, valid range [0..<cite>end</cite>)
156 * @param end double; length along this PolyLine where the sub-section ends, valid range
157 * (<cite>start</cite>..<cite>length</cite> (length is the length of this PolyLine)
158 * @return L; a new PolyLine covering the selected sub-section
159 * @throws DrawRuntimeException when start >= end, or start < 0, or end > length
160 */
161 L extract(double start, double end) throws DrawRuntimeException;
162
163 /**
164 * Project a Point on this PolyLine. If the the projected points lies outside this PolyLine, the nearest end point of this
165 * PolyLine is returned. Otherwise the returned point lies between the end points of this PolyLine. <br>
166 * @param point P; the point to project onto this PolyLine
167 * @return P; either the start point, or the end point of this PolyLine or a Point that lies somewhere along this PolyLine.
168 * @throws NullPointerException when point is null
169 */
170 P closestPointOnPolyLine(P point) throws NullPointerException;
171
172 /**
173 * Get the location at a position on the line, with its direction. Position should be between 0.0 and line length.
174 * @param position double; the position on the line for which to calculate the point on the line
175 * @return R; a Ray at the position on the line, pointing in the direction of the line at that position. If the position is
176 * at (or very near) a point on this PolyLine, the direction is either the direction before, or the direction after
177 * that point
178 * @throws DrawRuntimeException when position is NaN, less than 0.0, or more than line length.
179 */
180 R getLocation(double position) throws DrawRuntimeException;
181
182 /**
183 * Get the location at a position on the line, with its direction. Position can be below 0 or more than the line length. In
184 * that case, the position will be extrapolated in the direction of the line at its start or end.
185 * @param position double; the position on the line for which to calculate the point on, before, or after the line
186 * @return R; a Ray at the position on the line, pointing in the direction of the line at that position. If the position is
187 * at (or very near) a point on this PolyLine, the direction is either the direction before, or the direction after
188 * that point. If the position is before the start point of this PolyLine, the direction is towards the start point.
189 * If the position is beyond the end of this PolyLine, the direction is the direction of the last segment of this
190 * PolyLine.
191 */
192 R getLocationExtended(double position);
193
194 /**
195 * Get the location at a fraction of the line, with its direction. Fraction should be between 0.0 and 1.0.
196 * @param fraction double; the fraction for which to calculate the point on the line
197 * @return R; a Ray at the position on the line, pointing in the direction of the line at that position. If the position is
198 * at (or very near) a point on this PolyLine, the direction is either the direction before, or the direction after
199 * that point
200 * @throws DrawRuntimeException when fraction less than 0.0 or more than 1.0.
201 */
202 default R getLocationFraction(final double fraction) throws DrawRuntimeException
203 {
204 if (fraction < 0.0 || fraction > 1.0)
205 {
206 throw new DrawRuntimeException("getLocationFraction for line: fraction < 0.0 or > 1.0. fraction = " + fraction);
207 }
208 return getLocation(fraction * getLength());
209 }
210
211 /**
212 * Get the location at a fraction of the line, with its direction. Fraction should be between 0.0 and 1.0.
213 * @param fraction double; the fraction for which to calculate the point on the line
214 * @param tolerance double; the delta from 0.0 and 1.0 that will be forgiven
215 * @return R; a Ray at the position on the line, pointing in the direction of the line at that position. If the position is
216 * at (or very near) a point on this PolyLine, the direction is either the direction before, or the direction after
217 * that point. If the position is before the start point of this PolyLine, the direction is towards the start point.
218 * If the position is beyond the end of this PolyLine, the direction is the direction of the last segment of this
219 * PolyLine.
220 * @throws DrawRuntimeException when fraction less than 0.0 or more than 1.0.
221 */
222 default R getLocationFraction(final double fraction, final double tolerance) throws DrawRuntimeException
223 {
224 if (fraction < -tolerance || fraction > 1.0 + tolerance)
225 {
226 throw new DrawRuntimeException(
227 "getLocationFraction for line: fraction < 0.0 - tolerance or > 1.0 + tolerance; fraction = " + fraction);
228 }
229 double f = fraction < 0 ? 0.0 : fraction > 1.0 ? 1.0 : fraction;
230 return getLocation(f * getLength());
231 }
232
233 /**
234 * Get the location at a fraction of the line (or outside the line), with its direction.
235 * @param fraction double; the fraction for which to calculate the point on the line
236 * @return R; a Ray at the position on the line, pointing in the direction of the line at that position. If the position is
237 * at (or very near) a point on this PolyLine, the direction is either the direction before, or the direction after
238 * that point. If the position is before the start point of this PolyLine, the direction is towards the start point.
239 * If the position is beyond the end of this PolyLine, the direction is the direction of the last segment of this
240 * PolyLine.
241 */
242 default R getLocationFractionExtended(final double fraction)
243 {
244 return getLocationExtended(fraction * getLength());
245 }
246
247 /**
248 * Truncate this PolyLine at the given length (less than the length of the line, and larger than zero) and return a new
249 * line.
250 * @param position double; the position along the line where to truncate the line
251 * @return L; a new PolyLine that follows this PolyLine, but ends at the position where line.getLength() == lengthSI
252 * @throws DrawRuntimeException when position less than 0.0 or more than line length.
253 */
254 L truncate(double position) throws DrawRuntimeException;
255
256 /**
257 * Binary search for a point index on this PolyLine that is at, or the the nearest one before a given position.
258 * @param pos double; the position to look for
259 * @return the index below the position; the position lies between points[index] and points[index+1]
260 * @throws DrawRuntimeException when index could not be found
261 */
262 default int find(final double pos) throws DrawRuntimeException
263 {
264 if (pos == 0)
265 {
266 return 0;
267 }
268
269 int lo = 0;
270 int hi = size() - 1;
271 while (lo <= hi)
272 {
273 if (hi == lo)
274 {
275 return lo;
276 }
277 int mid = lo + (hi - lo) / 2;
278 if (pos < lengthAtIndex(mid))
279 {
280 hi = mid - 1;
281 }
282 else if (pos > lengthAtIndex(mid + 1))
283 {
284 lo = mid + 1;
285 }
286 else
287 {
288 return mid;
289 }
290 }
291 throw new DrawRuntimeException("Could not find position " + pos + " on line with length: " + getLength());
292 }
293
294 /**
295 * Convert this PolyLine to something that MS-Excel can plot.
296 * @return String MS-excel XY, or XYZ plottable output
297 */
298 String toExcel();
299
300 /** Default precision of approximation of arcs in the offsetLine method. */
301 double DEFAULT_CIRCLE_PRECISION = 0.001;
302
303 /** By default, noise in the reference line of the offsetLine method less than this value is always filtered. */
304 double DEFAULT_OFFSET_MINIMUM_FILTER_VALUE = 0.001;
305
306 /** By default, noise in the reference line of the offsetLineMethod greater than this value is never filtered. */
307 double DEFAULT_OFFSET_MAXIMUM_FILTER_VALUE = 0.1;
308
309 /**
310 * By default, noise in the reference line of the offsetLineMethod less than <cite>offset / offsetFilterRatio</cite> is
311 * filtered except when the resulting value exceeds <cite>offsetMaximumFilterValue</cite>.
312 */
313 double DEFAULT_OFFSET_FILTER_RATIO = 10;
314
315 /** By default, the offsetLineMethod uses this offset precision. */
316 double DEFAULT_OFFSET_PRECISION = 0.00001;
317
318 /**
319 * Construct an offset PolyLine. This is similar to what geographical specialists call buffering, except that this method
320 * only construct a new line on one side of the reference line and does not add half disks (or miters) at the end points.
321 * This method tries to strike a delicate balance between generating too few and too many points to approximate arcs. Noise
322 * in <cite>this</cite> (the reference line) can cause major artifacts in the offset line. This method calls the underlying
323 * method with default values for circlePrecision (<cite>DEFAULT_OFFSET</cite>), offsetMinimumFilterValue
324 * (<cite>DEFAULT_OFFSET_MINIMUM_FILTER_VALUE</cite>), offsetMaximumFilterValue
325 * (<cite>DEFAULT_OFFSET_MAXIMUM_FILTER_VALUE</cite>), offsetFilterRatio (<cite>DEFAULT_OFFSET_FILTER_RATIO</cite>),
326 * minimumOffset (<cite>DEFAULT_OFFSET_PRECISION</cite>). <br>
327 * In the 3D version the offset is parallel to the X-Y plane.
328 * @param offset double; the offset; positive values indicate left of the reference line, negative values indicate right of
329 * the reference line
330 * @return L; a PolyLine at the specified offset from the this PolyLine
331 * @throws DrawRuntimeException Only if P is PolyLine3d and the line cannot be projected into 2d
332 */
333 default L offsetLine(final double offset) throws DrawRuntimeException
334 {
335 return offsetLine(offset, DEFAULT_CIRCLE_PRECISION, DEFAULT_OFFSET_MINIMUM_FILTER_VALUE,
336 DEFAULT_OFFSET_MAXIMUM_FILTER_VALUE, DEFAULT_OFFSET_FILTER_RATIO, DEFAULT_OFFSET_PRECISION);
337 }
338
339 /**
340 * Construct an offset line. This is similar to what geographical specialists call buffering, except that this method only
341 * construct a new line on one side of the reference line and does not add half disks (or miters) around the end points.
342 * This method tries to strike a delicate balance between generating too few and too many points to approximate arcs. Noise
343 * in <cite>this</cite> (the reference line) can cause major artifacts in the offset line. <br>
344 * In the 3D version the offset is parallel to the X-Y plane.
345 * @param offset double; the offset; positive values indicate left of the reference line, negative values indicate right of
346 * the reference line
347 * @param circlePrecision double; precision of approximation of arcs; the line segments that are used to approximate an arc
348 * will not deviate from the exact arc by more than this value
349 * @param offsetMinimumFilterValue double; noise in the reference line less than this value is always filtered
350 * @param offsetMaximumFilterValue double; noise in the reference line greater than this value is never filtered
351 * @param offsetFilterRatio double; noise in the reference line less than <cite>offset / offsetFilterRatio</cite> is
352 * filtered except when the resulting value exceeds <cite>offsetMaximumFilterValue</cite>
353 * @param minimumOffset double; an offset value less than this value is treated as 0.0
354 * @return L; a PolyLine at the specified offset from the reference line
355 * @throws IllegalArgumentException when offset is NaN, or circlePrecision, offsetMinimumFilterValue,
356 * offsetMaximumfilterValue, offsetFilterRatio, or minimumOffset is not positive, or NaN, or
357 * offsetMinimumFilterValue >= offsetMaximumFilterValue
358 * @throws DrawRuntimeException Only if P is PolyLine3d and the line cannot be projected into 2d
359 */
360 L offsetLine(double offset, double circlePrecision, double offsetMinimumFilterValue, double offsetMaximumFilterValue,
361 double offsetFilterRatio, double minimumOffset) throws IllegalArgumentException, DrawRuntimeException;
362
363 /**
364 * Construct an offset line. This is similar to what geographical specialists call buffering, except that this method only
365 * construct a new line on one side of the reference line and does not add half disks (or miters) around the end points.
366 * This method tries to strike a delicate balance between generating too few and too many points to approximate arcs. Noise
367 * in <cite>this</cite> (the reference line) can cause major artifacts in the offset line. This method calls the underlying
368 * method with default values for circlePrecision (<cite>DEFAULT_OFFSET</cite>), offsetMinimumFilterValue
369 * (<cite>DEFAULT_OFFSET_MINIMUM_FILTER_VALUE</cite>), offsetMaximumFilterValue
370 * (<cite>DEFAULT_OFFSET_MAXIMUM_FILTER_VALUE</cite>), offsetFilterRatio (<cite>DEFAULT_OFFSET_FILTER_RATIO</cite>),
371 * minimumOffset (<cite>DEFAULT_OFFSET_PRECISION</cite>). <br>
372 * In the 3D version the offset is parallel to the X-Y plane.
373 * @param offsetAtStart double; the offset at the start of this line; positive values indicate left of the reference line,
374 * negative values indicate right of the reference line
375 * @param offsetAtEnd double; the offset at the end of this line; positive values indicate left of the reference line,
376 * negative values indicate right of the reference line
377 * @return L; a PolyLine at the specified offset from the reference line
378 * @throws IllegalArgumentException when offset is NaN, or circlePrecision, offsetMinimumFilterValue,
379 * offsetMaximumfilterValue, offsetFilterRatio, or minimumOffset is not positive, or NaN, or
380 * offsetMinimumFilterValue >= offsetMaximumFilterValue
381 * @throws DrawRuntimeException Only if P is PolyLine3d and the line cannot be projected into 2d
382 */
383 default L offsetLine(final double offsetAtStart, final double offsetAtEnd) throws IllegalArgumentException, DrawRuntimeException
384 {
385 return offsetLine(offsetAtStart, offsetAtEnd, DEFAULT_CIRCLE_PRECISION, DEFAULT_OFFSET_MINIMUM_FILTER_VALUE,
386 DEFAULT_OFFSET_MAXIMUM_FILTER_VALUE, DEFAULT_OFFSET_FILTER_RATIO, DEFAULT_OFFSET_PRECISION);
387 }
388
389 /**
390 * Construct an offset line. This is similar to what geographical specialists call buffering, except that this method only
391 * construct a new line on one side of the reference line and does not add half disks (or miters) around the end points.
392 * This method tries to strike a delicate balance between generating too few and too many points to approximate arcs. Noise
393 * in <cite>this</cite> (the reference line) can cause major artifacts in the offset line. <br>
394 * In the 3D version the offset is parallel to the X-Y plane.
395 * @param offsetAtStart double; the offset at the start of this line; positive values indicate left of the reference line,
396 * negative values indicate right of the reference line
397 * @param offsetAtEnd double; the offset at the end of this line; positive values indicate left of the reference line,
398 * negative values indicate right of the reference line
399 * @param circlePrecision double; precision of approximation of arcs; the line segments that are used to approximate an arc
400 * will not deviate from the exact arc by more than this value
401 * @param offsetMinimumFilterValue double; noise in the reference line less than this value is always filtered
402 * @param offsetMaximumFilterValue double; noise in the reference line greater than this value is never filtered
403 * @param offsetFilterRatio double; noise in the reference line less than <cite>offset / offsetFilterRatio</cite> is
404 * filtered except when the resulting value exceeds <cite>offsetMaximumFilterValue</cite>
405 * @param minimumOffset double; an offset value less than this value is treated as 0.0
406 * @return L; a PolyLine at the specified offset from the reference line
407 * @throws IllegalArgumentException when offset is NaN, or circlePrecision, offsetMinimumFilterValue,
408 * offsetMaximumfilterValue, offsetFilterRatio, or minimumOffset is not positive, or NaN, or
409 * offsetMinimumFilterValue >= offsetMaximumFilterValue
410 * @throws DrawRuntimeException Only if P is PolyLine3d and the line cannot be projected into 2d
411 */
412 L offsetLine(double offsetAtStart, double offsetAtEnd, double circlePrecision, double offsetMinimumFilterValue,
413 double offsetMaximumFilterValue, double offsetFilterRatio, double minimumOffset)
414 throws IllegalArgumentException, DrawRuntimeException;
415
416 /**
417 * Make a transition line from this PolyLine to another PolyLine using a user specified function.
418 * @param endLine L; the other PolyLine
419 * @param transition TransitionFunction; how the results changes from this line to the other line
420 * @return L; a transition between this PolyLine and the other PolyLine
421 * @throws DrawRuntimeException when construction of some point along the way fails. E.g. when the transition function
422 * returns NaN.
423 */
424 L transitionLine(L endLine, TransitionFunction transition) throws DrawRuntimeException;
425
426 /**
427 * Interface for transition function.
428 */
429 interface TransitionFunction
430 {
431 /**
432 * Function that returns some value for inputs between 0.0 and 1.0. For a smooth transition, this function should return
433 * 0.0 for input 0.0 and 1.0 for input 1.0 and be continuous and smooth.
434 * @param fraction double; the input for the function
435 * @return double; a ratio between 0.0 and 1.0 (values outside this domain are not an error, but will cause the
436 * transition line to go outside the range of the reference line and the other line)
437 */
438 double function(double fraction);
439 }
440
441 }