1 package org.opentrafficsim.base.geometry;
2
3 import java.util.ArrayList;
4 import java.util.Iterator;
5 import java.util.List;
6 import java.util.Optional;
7
8 import org.djunits.value.vdouble.scalar.Direction;
9 import org.djunits.value.vdouble.scalar.Length;
10 import org.djutils.draw.bounds.Bounds;
11 import org.djutils.draw.line.PolyLine2d;
12 import org.djutils.draw.point.DirectedPoint2d;
13 import org.djutils.draw.point.Point2d;
14 import org.djutils.exceptions.Throw;
15 import org.opentrafficsim.base.geometry.FractionalProjectionHelper.FractionalFallback;
16
17 import nl.tudelft.simulation.dsol.animation.Locatable;
18
19 /**
20 * This class supports fractional projection, radius, and has locatable methods.
21 * <p>
22 * Copyright (c) 2013-2026 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 Alexander Verbraeck
26 * @author Peter Knoppers
27 * @author Guus Tamminga
28 * @author Wouter Schakel
29 */
30 public class OtsLine2d extends PolyLine2d implements Locatable
31 {
32
33 /** Fractional projection helper. */
34 private final FractionalProjectionHelper fracHelper;
35
36 /** Radius calculator. */
37 private final RadiusCalculator2d radiusCalc;
38
39 /**
40 * Constructor from points.
41 * @param points array of points
42 */
43 public OtsLine2d(final Point2d... points)
44 {
45 super(0.0, points);
46 this.fracHelper = new FractionalProjectionHelper(this);
47 this.radiusCalc = new RadiusCalculator2d(this, this.fracHelper);
48 }
49
50 /**
51 * Constructor based on 2d line.
52 * @param line2d 2d line
53 */
54 public OtsLine2d(final PolyLine2d line2d)
55 {
56 super(0.0, line2d.iterator());
57 this.fracHelper = new FractionalProjectionHelper(this);
58 this.radiusCalc = new RadiusCalculator2d(this, this.fracHelper);
59 }
60
61 /**
62 * Constructor based on point iterator.
63 * @param line2d point iterator
64 */
65 public OtsLine2d(final Iterator<Point2d> line2d)
66 {
67 super(0.0, line2d);
68 this.fracHelper = new FractionalProjectionHelper(this);
69 this.radiusCalc = new RadiusCalculator2d(this, this.fracHelper);
70 }
71
72 /**
73 * Constructor based on a {@link List}{@code <}{@link Point2d}{@code >}.
74 * @param pointList list of points
75 */
76 public OtsLine2d(final List<Point2d> pointList)
77 {
78 super(0.0, pointList);
79 this.fracHelper = new FractionalProjectionHelper(this);
80 this.radiusCalc = new RadiusCalculator2d(this, this.fracHelper);
81 }
82
83 /**
84 * Construct parallel line.
85 * @param offset offset distance from the reference line; positive is LEFT, negative is RIGHT
86 * @return the line that has the specified offset from this reference line
87 */
88 @Override
89 public OtsLine2d offsetLine(final double offset)
90 {
91 return new OtsLine2d(super.offsetLine(offset));
92 }
93
94 /**
95 * Create a line at linearly varying offset from this line. The offset may change linearly from its initial value at the
96 * start of the reference line to its final offset value at the end of the reference line.
97 * @param offsetAtStart offset at the start of the reference line (positive value is Left, negative value is Right)
98 * @param offsetAtEnd offset at the end of the reference line (positive value is Left, negative value is Right)
99 * @return line with linear offset
100 */
101 @Override
102 public OtsLine2d offsetLine(final double offsetAtStart, final double offsetAtEnd)
103 {
104 return new OtsLine2d(super.offsetLine(offsetAtStart, offsetAtEnd).getPointList());
105 }
106
107 /**
108 * Create a line at linearly varying offset from this line. The offset may change linearly from its initial value at the
109 * start of the reference line via a number of intermediate offsets at intermediate positions to its final offset value at
110 * the end of the reference line.
111 * @param relativeFractions positional fractions for which the offsets have to be generated
112 * @param offsets offsets at the relative positions (positive value is Left, negative value is Right)
113 * @return line with profiled offset
114 */
115 public OtsLine2d offsetLine(final double[] relativeFractions, final double[] offsets)
116 {
117 return new OtsLine2d(OtsGeometryUtil.offsetLine(this, relativeFractions, offsets));
118 }
119
120 /**
121 * Concatenate several OtsLine2d instances.
122 * @param lines OtsLine2d... one or more OtsLine2d. The last point of the first <strong>must</strong> match the
123 * first of the second, etc.
124 * @return concatenated line
125 */
126 public static OtsLine2d concatenate(final OtsLine2d... lines)
127 {
128 return concatenate(0.0, lines);
129 }
130
131 /**
132 * Concatenate two OtsLine2d instances. This method is separate for efficiency reasons.
133 * @param toleranceSI the tolerance between the end point of a line and the first point of the next line
134 * @param line1 first line
135 * @param line2 second line
136 * @return concatenated line
137 */
138 public static OtsLine2d concatenate(final double toleranceSI, final OtsLine2d line1, final OtsLine2d line2)
139 {
140 return new OtsLine2d(PolyLine2d.concatenate(toleranceSI, line1, line2));
141 }
142
143 /**
144 * Concatenate several OtsLine2d instances.
145 * @param toleranceSI the tolerance between the end point of a line and the first point of the next line
146 * @param lines OtsLine2d... one or more OtsLine2d; the last point of the first <b>must</b> match the first of the second,
147 * etc.
148 * @return concatenated line
149 */
150 public static OtsLine2d concatenate(final double toleranceSI, final OtsLine2d... lines)
151 {
152 List<PolyLine2d> lines2d = new ArrayList<>();
153 for (OtsLine2d line : lines)
154 {
155 lines2d.add(line);
156 }
157 return new OtsLine2d(PolyLine2d.concatenate(toleranceSI, lines2d.toArray(new PolyLine2d[lines.length])));
158 }
159
160 /**
161 * Returns a reversed instance of this line.
162 * @return reversed line
163 */
164 @Override
165 public OtsLine2d reverse()
166 {
167 return new OtsLine2d(super.reverse());
168 }
169
170 /**
171 * Create a new line covering the indicated fraction of this line.
172 * @param start starting point, valid range [0..<i>end</i>)
173 * @param end ending point, valid range (<i>start</i>..1]
174 * @return extracted line
175 */
176 @Override
177 public OtsLine2d extractFractional(final double start, final double end)
178 {
179 return extract(start * getLength(), end * getLength());
180 }
181
182 /**
183 * Create a new line that covers a sub-section of this line.
184 * @param start the length along this OtsLine2d where the sub-section starts, valid range [0..<i>end</i>)
185 * @param end length along this OtsLine2d where the sub-section ends, valid range (<i>start</i>..<i>length</i> (length is
186 * the length of this line)
187 * @return extracted line
188 */
189 public OtsLine2d extract(final Length start, final Length end)
190 {
191 return extract(start.si, end.si);
192 }
193
194 /**
195 * Create a new line that covers a sub-section of this line.
196 * @param start length along this line where the sub-section starts, valid range [0..<i>end</i>)
197 * @param end length along this line where the sub-section ends, valid range (<i>start</i>..<i>length</i>] (length is the
198 * length of this line)
199 * @return extracted line
200 */
201 @Override
202 public OtsLine2d extract(final double start, final double end)
203 {
204 return new OtsLine2d(super.extract(start, end));
205 }
206
207 /**
208 * Return the length of this line.
209 * @return length of the line
210 */
211 public Length getTypedLength()
212 {
213 return Length.ofSI(super.getLength());
214 }
215
216 /**
217 * Get the location at a position on the line, with its direction. Position can be below 0 or more than the line length. In
218 * that case, the position will be extrapolated in the direction of the line at its start or end.
219 * @param position the position on the line for which to calculate the point on, before, of after the line
220 * @return a directed point
221 */
222 public DirectedPoint2d getLocationExtended(final Length position)
223 {
224 return getLocationExtended(position.si);
225 }
226
227 /**
228 * Get the location at a position on the line, with its direction. Position should be in [0..<i>length</i>].
229 * @param position the position on the line for which to calculate the point on the line
230 * @return a directed point
231 */
232 public DirectedPoint2d getLocation(final Length position)
233 {
234 return getLocation(position.si);
235 }
236
237 /**
238 * Truncate line at the given length in range (0..<i>length</i>).
239 * @param lengthSI the location where to truncate the line
240 * @return truncated line
241 */
242 @Override
243 public OtsLine2d truncate(final double lengthSI)
244 {
245 return new OtsLine2d(super.truncate(lengthSI));
246 }
247
248 /**
249 * Orthogonally project a point onto this polyline. If the perpendicular foot on the closest segment falls outside that
250 * segment, this method snaps to the nearest vertex of that segment. The result is returned as a fraction along the entire
251 * polyline. The returned fraction is clamped to [0..1].
252 * @param x x-coordinate of the point to project
253 * @param y y-coordinate of the point to project
254 * @return fraction along the line in [0..1]
255 */
256 public double projectOrthogonalSnapAt(final double x, final double y)
257 {
258 return projectOrthogonalSnapAt(x, y, true);
259 }
260
261 /**
262 * Orthogonally project a point onto this polyline. If the perpendicular foot on the closest segment falls outside that
263 * segment, this method snaps to the nearest vertex of that segment. The result is returned as a fraction along the entire
264 * polyline.
265 * <p>
266 * If {@code clampToDomain} is {@code true}, the returned fraction is clamped to [0..1]. If {@code false}, the fraction may
267 * be negative (before the start of the line) or larger than 1 (beyond the end of the line) when the closest point is the
268 * first or last vertex, respectively.
269 * @param x x-coordinate of the point to project
270 * @param y y-coordinate of the point to project
271 * @param clampToDomain whether to clamp the resulting fraction to [0..1]
272 * @return fraction along the line; in [0..1] when {@code clampToDomain} is true; otherwise possibly <0 or >1
273 */
274 public double projectOrthogonalSnapAt(final double x, final double y, final boolean clampToDomain)
275 {
276 final int nPoints = size();
277 if (nPoints < 2)
278 {
279 return Double.NaN; // no segments to project on
280 }
281
282 // Track the best (closest) candidate across all segments.
283 double bestD2 = Double.POSITIVE_INFINITY;
284 double bestFraction = Double.NaN;
285
286 // Useful constants
287 final double totalLength = lengthAtIndex(nPoints - 1);
288 final double xFirst = getX(0);
289 final double yFirst = getY(0);
290 final double xLast = getX(nPoints - 1);
291 final double yLast = getY(nPoints - 1);
292
293 // Loop over segments and compute the closest point (orthogonal if interior, otherwise snap to an end-point)
294 for (int i = 0; i < nPoints - 1; i++)
295 {
296 final double xA = getX(0);
297 final double yA = getY(0);
298 final double xB = getX(nPoints - 1);
299 final double yB = getY(nPoints - 1);
300
301 final double abx = xB - xA;
302 final double aby = yB - yA;
303 final double ab2 = abx * abx + aby * aby;
304 if (ab2 == 0.0)
305 {
306 // Degenerate segment; skip
307 continue;
308 }
309
310 final double apx = x - xA;
311 final double apy = y - yA;
312
313 // Un-clamped parameter along the infinite line through segment [a,b]
314 final double t = (apx * abx + apy * aby) / ab2;
315
316 // Compute the "nearest point on the segment" by clamping t to [0, 1]
317 final double tClamped = Math.max(0.0, Math.min(1.0, t));
318 final double px = xA + tClamped * abx;
319 final double py = yA + tClamped * aby;
320
321 // Distance squared to the candidate on this segment
322 final double dx = x - px;
323 final double dy = y - py;
324 final double d2 = dx * dx + dy * dy;
325
326 if (d2 < bestD2)
327 {
328 bestD2 = d2;
329
330 // Convert this segment-local candidate to a fraction along the entire polyline.
331 if (t >= 0.0 && t <= 1.0)
332 {
333 // Orthogonal foot lies within the segment.
334 final double segStart = lengthAtIndex(i);
335 final double segEnd = lengthAtIndex(i + 1);
336 final double absS = segStart + t * (segEnd - segStart);
337 bestFraction = absS / totalLength;
338 }
339 else
340 {
341 // Orthogonal foot outside the segment: snap to the nearest endpoint of this segment.
342 // For t < 0 -> endpoint a; for t > 1 -> endpoint b.
343 if (t < 0.0)
344 {
345 if (clampToDomain)
346 {
347 bestFraction = lengthAtIndex(i) / totalLength; // fraction at vertex a
348 }
349 else
350 {
351 // Extended: if this is the first vertex, return a negative fraction
352 if (i == 0)
353 {
354 final double dStart = Math.hypot(x - xFirst, y - yFirst);
355 bestFraction = (0.0 - dStart) / totalLength;
356 }
357 else
358 {
359 // For internal vertices, still snap to the vertex fraction in-domain
360 bestFraction = lengthAtIndex(i) / totalLength;
361 }
362 }
363 }
364 else // t > 1.0
365 {
366 if (clampToDomain)
367 {
368 bestFraction = lengthAtIndex(i + 1) / totalLength; // fraction at vertex b
369 }
370 else
371 {
372 // Extended: if this is the last vertex, return a fraction beyond 1
373 if (i + 1 == nPoints - 1)
374 {
375 final double dEnd = Math.hypot(x - xLast, y - yLast);
376 bestFraction = (totalLength + dEnd) / totalLength;
377 }
378 else
379 {
380 // For internal vertices, still snap to the vertex fraction in-domain
381 bestFraction = lengthAtIndex(i + 1) / totalLength;
382 }
383 }
384 }
385 }
386 }
387 }
388
389 return bestFraction;
390 }
391
392 /**
393 * Returns the fractional projection of a point to a line. The projection works by taking slices in space per line segment
394 * as shown below. A point is always projected to the nearest segment, but not necessarily to the closest point on that
395 * segment. The slices in space are analogous to a Voronoi diagram, but for the line segments instead of points. If
396 * fractional projection fails, a fallback projection is returned.
397 * <p>
398 * The point 'A' is projected to point 'B' on the 3rd segment of line 'C-D'. The line from 'A' to 'B' extends towards point
399 * 'E', which is the intersection of lines 'E-F' and 'E-G'. Line 'E-F' cuts the first bend of the 3rd segment (at point 'H')
400 * in half, while the line 'E-G' cuts the second bend of the 3rd segment (at point 'I') in half.
401 *
402 * <pre>
403 * ____________________________ G .
404 * . | | . .
405 * . | . . . . helper lines | . .
406 * . | _.._.._ projection line | I. .
407 * . |____________________________| _.'._ . L
408 * F. _.' . '-. .
409 * .. B _.' . '-.
410 * . . _.\ . . D
411 * . . _.' : . .
412 * J . . _.' \ . .
413 * .. . _.' : . M
414 * . . ..-' \ .
415 * . . /H. A .
416 * . . / . .
417 * C _________/ . .
418 * . . . .
419 * K . . . .
420 * . . . .
421 * . . . . N
422 * . . . .
423 * . . . .
424 * . . . .
425 * . . . .
426 * . .E
427 * . .
428 * . .
429 * . .
430 * </pre>
431 *
432 * Fractional projection may fail in three cases.
433 * <ol>
434 * <li>Numerical difficulties at slight bend, orthogonal projection returns the correct point.</li>
435 * <li>Fractional projection is possible only to segments that aren't the nearest segment(s).</li>
436 * <li>Fractional projection is possible for no segment.</li>
437 * </ol>
438 * In the latter two cases the projection is undefined and the provided fallback is used to provide a point.
439 * @param start direction in first point
440 * @param end direction in last point
441 * @param x x-coordinate of point to project
442 * @param y y-coordinate of point to project
443 * @param fallback fallback method for when fractional projection fails
444 * @return fractional position along this line of the fractional projection on that line of a point
445 */
446 public double projectFractionalAt(final Direction start, final Direction end, final double x, final double y,
447 final FractionalFallback fallback)
448 {
449 return this.fracHelper.projectFractionalAt(start, end, x, y, fallback);
450 }
451
452 /**
453 * Returns the projected directional radius of the line at a given fraction. Negative values reflect right-hand curvature in
454 * the design-line direction. The radius is taken as the minimum of the radii at the vertices before and after the given
455 * fraction. The radius at a vertex is calculated as the radius of a circle that is equidistant from both edges connected to
456 * the vertex. The circle center is on a line perpendicular to the shortest edge, crossing through the middle of the
457 * shortest edge. This method ignores Z components.
458 * @param fraction fraction along the line, between 0.0 and 1.0 (both inclusive)
459 * @return radius; the local radius; empty if there is no radius as two segments have the same direction
460 * @throws IllegalArgumentException fraction out of bounds
461 */
462 public Optional<Length> radiusAtFraction(final double fraction) throws IllegalArgumentException
463 {
464 return this.radiusCalc.radiusAtFraction(fraction);
465 }
466
467 /**
468 * Calculates the directional radius at a vertex. Negative values reflect right-hand curvature in the design-line direction.
469 * The radius at a vertex is calculated as the radius of a circle that is equidistant from both edges connected to the
470 * vertex. The circle center is on a line perpendicular to the shortest edge, crossing through the middle of the shortest
471 * edge. This function ignores Z components.
472 * @param index index of the vertex in range [1 ... size() - 2]
473 * @return radius at the vertex, empty if there is no radius as two segments have the same direction
474 * @throws IndexOutOfBoundsException if the index is out of bounds
475 */
476 public Optional<Length> radiusAtVertex(final int index) throws IndexOutOfBoundsException
477 {
478 return this.radiusCalc.radiusAtVertex(index);
479 }
480
481 /**
482 * Returns the length fraction at the vertex.
483 * @param index index of vertex [0 ... size() - 1]
484 * @return length fraction at the vertex
485 * @throws IndexOutOfBoundsException if the index is out of bounds
486 */
487 public double vertexFraction(final int index) throws IndexOutOfBoundsException
488 {
489 Throw.when(index < 0 || index > size() - 1, IndexOutOfBoundsException.class, "Index %d is out of bounds [0 %d].", index,
490 size() - 1);
491 return lengthAtIndex(index) / getLength();
492 }
493
494 @Override
495 public Bounds<?, ?> getRelativeBounds()
496 {
497 return OtsShape.toRelativeTransform(getLocation()).transform(getAbsoluteBounds());
498 }
499
500 @Override
501 public Point2d getLocation()
502 {
503 return getAbsoluteBounds().midPoint();
504 }
505
506 }