1 package org.opentrafficsim.base.geometry;
2
3 import java.awt.geom.Line2D;
4 import java.awt.geom.Point2D;
5 import java.io.Serializable;
6 import java.util.ArrayList;
7 import java.util.Iterator;
8 import java.util.List;
9
10 import org.djunits.value.vdouble.scalar.Direction;
11 import org.djunits.value.vdouble.scalar.Length;
12 import org.djutils.draw.DrawRuntimeException;
13 import org.djutils.draw.line.PolyLine2d;
14 import org.djutils.draw.line.Ray2d;
15 import org.djutils.draw.point.OrientedPoint2d;
16 import org.djutils.draw.point.Point2d;
17 import org.djutils.exceptions.Throw;
18
19 import nl.tudelft.simulation.dsol.animation.Locatable;
20
21 /**
22 * This class supports fractional projection, radius, and has location methods .
23 * <p>
24 * Copyright (c) 2013-2024 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved. <br>
25 * BSD-style license. See <a href="https://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
26 * </p>
27 * @author <a href="https://github.com/averbraeck">Alexander Verbraeck</a>
28 * @author <a href="https://github.com/peter-knoppers">Peter Knoppers</a>
29 * @author <a href="https://www.citg.tudelft.nl">Guus Tamminga</a>
30 * @author <a href="https://github.com/wjschakel">Wouter Schakel</a>
31 */
32 public class OtsLine2d extends PolyLine2d implements Locatable, Serializable
33 {
34 /** */
35 private static final long serialVersionUID = 20150722L;
36
37 /** The cached typed length; will be calculated at time of construction. */
38 private final Length length;
39
40 // Fractional projection
41
42 /** The cached helper points for fractional projection; will be calculated when needed for the first time. */
43 private Point2d[] fractionalHelperCenters = null;
44
45 /** The cached helper directions for fractional projection; will be calculated when needed for the first time. */
46 private Point2D.Double[] fractionalHelperDirections = null;
47
48 /** Intersection of unit offset lines of first two segments. */
49 private Point2d firstOffsetIntersection;
50
51 /** Intersection of unit offset lines of last two segments. */
52 private Point2d lastOffsetIntersection;
53
54 /** Precision for fractional projection algorithm. */
55 private static final double FRAC_PROJ_PRECISION = 2e-5 /* PK too fine 1e-6 */;
56
57 // Radii for curvature
58
59 /** Radius at each vertex. */
60 private Length[] vertexRadii;
61
62 /**
63 * Construct a new OtsLine2d.
64 * @param points the array of points to construct this OtsLine2d from.
65 */
66 public OtsLine2d(final Point2d... points)
67 {
68 super(points);
69 this.length = Length.instantiateSI(lengthAtIndex(size() - 1));
70 }
71
72 /**
73 * Creates a new OtsLine2d based on 2d information.
74 * @param line2d 2d information.
75 */
76 public OtsLine2d(final PolyLine2d line2d)
77 {
78 super(line2d.getPoints());
79 this.length = Length.instantiateSI(lengthAtIndex(size() - 1));
80 }
81
82 /**
83 * Creates a new OtsLine2d based on point iterator.
84 * @param line2d point iterator.
85 */
86 public OtsLine2d(final Iterator<Point2d> line2d)
87 {
88 super(line2d);
89 this.length = Length.instantiateSI(lengthAtIndex(size() - 1));
90 }
91
92 /**
93 * Construct a new OtsLine2d from a List<OtsPoint3d>.
94 * @param pointList the list of points to construct this OtsLine2d from.
95 */
96 public OtsLine2d(final List<Point2d> pointList)
97 {
98 super(pointList);
99 this.length = Length.instantiateSI(lengthAtIndex(size() - 1));
100 }
101
102 /**
103 * Construct parallel line.
104 * @param offset offset distance from the reference line; positive is LEFT, negative is RIGHT
105 * @return the line that has the specified offset from the reference line
106 */
107 @Override
108 public final OtsLine2d offsetLine(final double offset)
109 {
110 return new OtsLine2d(super.offsetLine(offset));
111 }
112
113 /**
114 * Create a line at linearly varying offset from this line. The offset may change linearly from its initial value at the
115 * start of the reference line to its final offset value at the end of the reference line.
116 * @param offsetAtStart offset at the start of the reference line (positive value is Left, negative value is Right)
117 * @param offsetAtEnd offset at the end of the reference line (positive value is Left, negative value is Right)
118 * @return the OtsLine2d of the line at linearly changing offset of the reference line
119 */
120 @Override
121 public final OtsLine2d offsetLine(final double offsetAtStart, final double offsetAtEnd)
122 {
123 return new OtsLine2d(super.offsetLine(offsetAtStart, offsetAtEnd).getPointList());
124 }
125
126 /**
127 * Create a line at linearly varying offset from this line. The offset may change linearly from its initial value at the
128 * start of the reference line via a number of intermediate offsets at intermediate positions to its final offset value at
129 * the end of the reference line.
130 * @param relativeFractions positional fractions for which the offsets have to be generated
131 * @param offsets offsets at the relative positions (positive value is Left, negative value is Right)
132 * @return the Geometry of the line at linearly changing offset of the reference line
133 */
134 public final OtsLine2d offsetLine(final double[] relativeFractions, final double[] offsets)
135 {
136 return new OtsLine2d(OtsGeometryUtil.offsetLine(this, relativeFractions, offsets));
137 }
138
139 /**
140 * Concatenate several OtsLine2d instances.
141 * @param lines OtsLine2d... one or more OtsLine2d. The last point of the first <strong>must</strong> match the
142 * first of the second, etc.
143 * @return OtsLine2d
144 */
145 public static OtsLine2d concatenate(final OtsLine2d... lines)
146 {
147 return concatenate(0.0, lines);
148 }
149
150 /**
151 * Concatenate two OtsLine2d instances. This method is separate for efficiency reasons.
152 * @param toleranceSI the tolerance between the end point of a line and the first point of the next line
153 * @param line1 first line
154 * @param line2 second line
155 * @return OtsLine2d
156 */
157 public static OtsLine2d concatenate(final double toleranceSI, final OtsLine2d line1, final OtsLine2d line2)
158 {
159 return new OtsLine2d(PolyLine2d.concatenate(toleranceSI, line1, line2));
160 }
161
162 /**
163 * Concatenate several OtsLine2d instances.
164 * @param toleranceSI the tolerance between the end point of a line and the first point of the next line
165 * @param lines OtsLine2d... one or more OtsLine2d. The last point of the first <strong>must</strong> match the
166 * first of the second, etc.
167 * @return OtsLine2d
168 */
169 public static OtsLine2d concatenate(final double toleranceSI, final OtsLine2d... lines)
170 {
171 List<PolyLine2d> lines2d = new ArrayList<>();
172 for (OtsLine2d line : lines)
173 {
174 lines2d.add(line);
175 }
176 return new OtsLine2d(PolyLine2d.concatenate(toleranceSI, lines2d.toArray(new PolyLine2d[lines.length])));
177 }
178
179 /**
180 * Construct a new OtsLine2d with all points of this OtsLine2d in reverse order.
181 * @return the new OtsLine2d
182 */
183 @Override
184 public final OtsLine2d reverse()
185 {
186 return new OtsLine2d(super.reverse());
187 }
188
189 /**
190 * Construct a new OtsLine2d covering the indicated fraction of this OtsLine2d.
191 * @param start starting point, valid range [0..<cite>end</cite>)
192 * @param end ending point, valid range (<cite>start</cite>..1]
193 * @return the new OtsLine2d
194 */
195 @Override
196 public OtsLine2d extractFractional(final double start, final double end)
197 {
198 return extract(start * this.length.si, end * this.length.si);
199 }
200
201 /**
202 * Create a new OtsLine2d that covers a sub-section of this OtsLine2d.
203 * @param start the length along this OtsLine2d where the sub-section starts, valid range [0..<cite>end</cite>)
204 * @param end length along this OtsLine2d where the sub-section ends, valid range (<cite>start</cite>..<cite>length</cite>
205 * (length is the length of this OtsLine2d)
206 * @return the selected sub-section
207 */
208 public final OtsLine2d extract(final Length start, final Length end)
209 {
210 return extract(start.si, end.si);
211 }
212
213 /**
214 * Create a new OtsLine2d that covers a sub-section of this OtsLine2d.
215 * @param start length along this OtsLine2d where the sub-section starts, valid range [0..<cite>end</cite>)
216 * @param end length along this OtsLine2d where the sub-section ends, valid range (<cite>start</cite>..<cite>length</cite>
217 * (length is the length of this OtsLine2d)
218 * @return the selected sub-section
219 */
220 @Override
221 public final OtsLine2d extract(final double start, final double end)
222 {
223 return new OtsLine2d(super.extract(start, end));
224 }
225
226 /**
227 * Return the length of this OtsLine2d in meters. (Assuming that the coordinates of the points constituting this line are
228 * expressed in meters.)
229 * @return the length of the line
230 */
231 public final Length getTypedLength()
232 {
233 return this.length;
234 }
235
236 /**
237 * Get the location at a position on the line, with its direction. Position can be below 0 or more than the line length. In
238 * that case, the position will be extrapolated in the direction of the line at its start or end.
239 * @param position the position on the line for which to calculate the point on, before, of after the line
240 * @return a directed point
241 */
242 public final OrientedPoint2d getLocationExtended(final Length position)
243 {
244 return rayToPoint(getLocationExtended(position.si));
245 }
246
247 /**
248 * Get the location at a position on the line, with its direction. Position can be below 0 or more than the line length. In
249 * that case, the position will be extrapolated in the direction of the line at its start or end.
250 * @param positionSI the position on the line for which to calculate the point on, before, of after the line, in SI units
251 * @return a directed point
252 */
253 public final OrientedPoint2d getLocationExtendedSI(final double positionSI)
254 {
255 return rayToPoint(getLocationExtended(positionSI));
256 }
257
258 /**
259 * Get the location at a fraction of the line, with its direction. Fraction should be between 0.0 and 1.0.
260 * @param fraction the fraction for which to calculate the point on the line
261 * @return a directed point
262 * @throws DrawRuntimeException when fraction less than 0.0 or more than 1.0.
263 */
264 public final OrientedPoint2d getLocationPointFraction(final double fraction) throws DrawRuntimeException
265 {
266 return rayToPoint(getLocationFraction(fraction));
267 }
268
269 /**
270 * Get the location at a fraction of the line, with its direction. Fraction should be between 0.0 and 1.0.
271 * @param fraction the fraction for which to calculate the point on the line
272 * @param tolerance the delta from 0.0 and 1.0 that will be forgiven
273 * @return a directed point
274 * @throws DrawRuntimeException when fraction less than 0.0 or more than 1.0.
275 */
276 public final OrientedPoint2d getLocationPointFraction(final double fraction, final double tolerance)
277 throws DrawRuntimeException
278 {
279 return rayToPoint(getLocationFraction(fraction, tolerance));
280 }
281
282 /**
283 * Get the location at a fraction of the line (or outside the line), with its direction.
284 * @param fraction the fraction for which to calculate the point on the line
285 * @return a directed point
286 */
287 public final OrientedPoint2d getLocationPointFractionExtended(final double fraction)
288 {
289 return rayToPoint(getLocationFractionExtended(fraction));
290 }
291
292 /**
293 * Get the location at a position on the line, with its direction. Position should be between 0.0 and line length.
294 * @param position the position on the line for which to calculate the point on the line
295 * @return a directed point
296 * @throws DrawRuntimeException when position less than 0.0 or more than line length.
297 */
298 public final OrientedPoint2d getLocation(final Length position) throws DrawRuntimeException
299 {
300 return rayToPoint(getLocation(position.si));
301 }
302
303 /**
304 * Get the location at a position on the line, with its direction. Position should be between 0.0 and line length.
305 * @param positionSI the position on the line for which to calculate the point on the line
306 * @return a directed point
307 * @throws DrawRuntimeException when position less than 0.0 or more than line length.
308 */
309 public final OrientedPoint2d getLocationSI(final double positionSI) throws DrawRuntimeException
310 {
311 return rayToPoint(getLocation(positionSI));
312 }
313
314 /**
315 * Returns an oriented point based on the information of a ray.
316 * @param ray ray
317 * @return oriented point based on the information of a ray
318 */
319 private OrientedPoint2d rayToPoint(final Ray2d ray)
320 {
321 return new OrientedPoint2d(ray.x, ray.y, ray.phi);
322 }
323
324 /**
325 * Truncate a line at the given length (less than the length of the line, and larger than zero) and return a new line.
326 * @param lengthSI the location where to truncate the line
327 * @return a new OtsLine2d truncated at the exact position where line.getLength() == lengthSI
328 */
329 @Override
330 public final OtsLine2d truncate(final double lengthSI)
331 {
332 return new OtsLine2d(super.truncate(lengthSI));
333 }
334
335 /**
336 * Returns the fractional position along this line of the orthogonal projection of point (x, y) on this line. If the point
337 * is not orthogonal to the closest line segment, the nearest point is selected.
338 * @param x x-coordinate of point to project
339 * @param y y-coordinate of point to project
340 * @return fractional position along this line of the orthogonal projection on this line of a point
341 */
342 public final double projectOrthogonalSnap(final double x, final double y)
343 {
344 Point2d closest = closestPointOnPolyLine(new Point2d(x, y));
345 return projectOrthogonalFractionalExtended(closest);
346 }
347
348 /**
349 * Returns the fractional projection of a point to a line. The projection works by taking slices in space per line segment
350 * as shown below. A point is always projected to the nearest segment, but not necessarily to the closest point on that
351 * segment. The slices in space are analogous to a Voronoi diagram, but for the line segments instead of points. If
352 * fractional projection fails, a fallback projection is returned.<br>
353 * <br>
354 * 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
355 * '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')
356 * in half, while the line 'E-G' cuts the second bend of the 3rd segment (at point 'I') in half.
357 *
358 * <pre>
359 * ____________________________ G .
360 * . | | . .
361 * . | . . . . helper lines | . .
362 * . | _.._.._ projection line | I. .
363 * . |____________________________| _.'._ . L
364 * F. _.' . '-. .
365 * .. B _.' . '-.
366 * . . _.\ . . D
367 * . . _.' : . .
368 * J . . _.' \ . .
369 * .. . _.' : . M
370 * . . ..-' \ .
371 * . . /H. A .
372 * . . / . .
373 * C _________/ . .
374 * . . . .
375 * K . . . .
376 * . . . .
377 * . . . . N
378 * . . . .
379 * . . . .
380 * . . . .
381 * . . . .
382 * . .E
383 * . .
384 * . .
385 * . .
386 * </pre>
387 *
388 * Fractional projection may fail in three cases.
389 * <ol>
390 * <li>Numerical difficulties at slight bend, orthogonal projection returns the correct point.</li>
391 * <li>Fractional projection is possible only to segments that aren't the nearest segment(s).</li>
392 * <li>Fractional projection is possible for no segment.</li>
393 * </ol>
394 * In the latter two cases the projection is undefined and the provided fallback is used to provide a point.
395 * @param start direction in first point
396 * @param end direction in last point
397 * @param x x-coordinate of point to project
398 * @param y y-coordinate of point to project
399 * @param fallback fallback method for when fractional projection fails
400 * @return fractional position along this line of the fractional projection on that line of a point
401 */
402 public final synchronized double projectFractional(final Direction start, final Direction end, final double x,
403 final double y, final FractionalFallback fallback)
404 {
405
406 // prepare
407 double minDistance = Double.POSITIVE_INFINITY;
408 double minSegmentFraction = 0;
409 int minSegment = -1;
410 Point2d point = new Point2d(x, y);
411
412 // determine helpers (centers and directions)
413 determineFractionalHelpers(start, end);
414
415 // get distance of point to each segment
416 double[] d = new double[size() - 1];
417 double minD = Double.POSITIVE_INFINITY;
418 for (int i = 0; i < size() - 1; i++)
419 {
420 d[i] = Line2D.ptSegDist(get(i).x, get(i).y, get(i + 1).x, get(i + 1).y, x, y);
421 minD = d[i] < minD ? d[i] : minD;
422 }
423
424 // loop over segments for projection
425 double distance;
426 for (int i = 0; i < size() - 1; i++)
427 {
428 // skip if not the closest segment, note that often two segments are equally close in their shared end point
429 if (d[i] > minD + FRAC_PROJ_PRECISION)
430 {
431 continue;
432 }
433 Point2d center = this.fractionalHelperCenters[i];
434 Point2d p;
435 if (center != null)
436 {
437 // get intersection of line "center - (x, y)" and the segment
438 p = intersectionOfLines(center, point, get(i), get(i + 1));
439 if (p == null || (x < center.x + FRAC_PROJ_PRECISION && center.x + FRAC_PROJ_PRECISION < p.x)
440 || (x > center.x - FRAC_PROJ_PRECISION && center.x - FRAC_PROJ_PRECISION > p.x)
441 || (y < center.y + FRAC_PROJ_PRECISION && center.y + FRAC_PROJ_PRECISION < p.y)
442 || (y > center.y - FRAC_PROJ_PRECISION && center.y - FRAC_PROJ_PRECISION > p.y))
443 {
444 // projected point may not be 'beyond' segment center (i.e. center may not be between (x, y) and (p.x, p.y)
445 continue;
446 }
447 }
448 else
449 {
450 // parallel helper lines, project along direction
451 Point2d offsetPoint =
452 new Point2d(x + this.fractionalHelperDirections[i].x, y + this.fractionalHelperDirections[i].y);
453 p = intersectionOfLines(point, offsetPoint, get(i), get(i + 1));
454 }
455 double segLength = get(i).distance(get(i + 1)) + FRAC_PROJ_PRECISION;
456 if (p == null || get(i).distance(p) > segLength || get(i + 1).distance(p) > segLength)
457 {
458 // intersection must be on the segment
459 // in case of p == null, the length of the fractional helper direction falls away due to precision
460 continue;
461 }
462 // distance from (x, y) to intersection on segment
463 double dx = x - p.x;
464 double dy = y - p.y;
465 distance = Math.hypot(dx, dy);
466 // distance from start of segment to point on segment
467 if (distance < minDistance)
468 {
469 dx = p.x - get(i).x;
470 dy = p.y - get(i).y;
471 double dFrac = Math.hypot(dx, dy);
472 // fraction to point on segment
473 minDistance = distance;
474 minSegmentFraction = dFrac / (lengthAtIndex(i + 1) - lengthAtIndex(i));
475 minSegment = i;
476 }
477 }
478
479 // return
480 if (minSegment == -1)
481
482 {
483 /*
484 * If fractional projection fails (x, y) is either outside of the applicable area for fractional projection, or is
485 * inside an area where numerical difficulties arise (i.e. far away outside of very slight bend which is considered
486 * parallel).
487 */
488 return fallback.getFraction(this, x, y);
489 }
490
491 double segLen = lengthAtIndex(minSegment + 1) - lengthAtIndex(minSegment);
492 return (lengthAtIndex(minSegment) + segLen * minSegmentFraction) / this.length.si;
493
494 }
495
496 /**
497 * Fallback method for when fractional projection fails as the point is beyond the line or from numerical limitations.
498 * <p>
499 * Copyright (c) 2013-2024 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
500 * <br>
501 * BSD-style license. See <a href="https://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
502 * </p>
503 * @author <a href="https://github.com/averbraeck">Alexander Verbraeck</a>
504 * @author <a href="https://github.com/peter-knoppers">Peter Knoppers</a>
505 * @author <a href="https://github.com/wjschakel">Wouter Schakel</a>
506 */
507 public enum FractionalFallback
508 {
509 /** Orthogonal projection. */
510 ORTHOGONAL
511 {
512 @Override
513 double getFraction(final OtsLine2d line, final double x, final double y)
514 {
515 return line.projectOrthogonalSnap(x, y);
516 }
517 },
518
519 /** Distance to nearest end point. */
520 ENDPOINT
521 {
522 @Override
523 double getFraction(final OtsLine2d line, final double x, final double y)
524 {
525 Point2d point = new Point2d(x, y);
526 double dStart = point.distance(line.getFirst());
527 double dEnd = point.distance(line.getLast());
528 if (dStart < dEnd)
529 {
530 return -dStart / line.length.si;
531 }
532 else
533 {
534 return (dEnd + line.length.si) / line.length.si;
535 }
536 }
537 },
538
539 /** NaN value. */
540 NaN
541 {
542 @Override
543 double getFraction(final OtsLine2d line, final double x, final double y)
544 {
545 return Double.NaN;
546 }
547 };
548
549 /**
550 * Returns fraction for when fractional projection fails as the point is beyond the line or from numerical limitations.
551 * @param line line
552 * @param x x coordinate of point
553 * @param y y coordinate of point
554 * @return fraction for when fractional projection fails
555 */
556 abstract double getFraction(OtsLine2d line, double x, double y);
557
558 }
559
560 /**
561 * Determines all helpers (points and/or directions) for fractional projection and stores fixed information in properties
562 * while returning the first and last center points (.
563 * @param start direction in first point
564 * @param end direction in last point
565 */
566 private synchronized void determineFractionalHelpers(final Direction start, final Direction end)
567 {
568
569 final int n = size() - 1;
570
571 // calculate fixed helpers if not done yet
572 if (this.fractionalHelperCenters == null)
573 {
574 this.fractionalHelperCenters = new Point2d[n];
575 this.fractionalHelperDirections = new Point2D.Double[n];
576 if (size() > 2)
577 {
578 // intersection of parallel lines of first and second segment
579 PolyLine2d prevOfsSeg = unitOffsetSegment(0);
580 PolyLine2d nextOfsSeg = unitOffsetSegment(1);
581 Point2d parStartPoint;
582 parStartPoint = intersectionOfLines(prevOfsSeg.get(0), prevOfsSeg.get(1), nextOfsSeg.get(0), nextOfsSeg.get(1));
583 if (parStartPoint == null || prevOfsSeg.get(1).distance(nextOfsSeg.get(0)) < Math
584 .min(prevOfsSeg.get(1).distance(parStartPoint), nextOfsSeg.get(0).distance(parStartPoint)))
585 {
586 parStartPoint = new Point2d((prevOfsSeg.get(1).x + nextOfsSeg.get(0).x) / 2,
587 (prevOfsSeg.get(1).y + nextOfsSeg.get(0).y) / 2);
588 }
589 // remember the intersection of the first two unit offset segments
590 this.firstOffsetIntersection = parStartPoint;
591 // loop segments
592 for (int i = 1; i < size() - 2; i++)
593 {
594 prevOfsSeg = nextOfsSeg;
595 nextOfsSeg = unitOffsetSegment(i + 1);
596 Point2d parEndPoint;
597 parEndPoint =
598 intersectionOfLines(prevOfsSeg.get(0), prevOfsSeg.get(1), nextOfsSeg.get(0), nextOfsSeg.get(1));
599 if (parEndPoint == null || prevOfsSeg.get(1).distance(nextOfsSeg.get(0)) < Math
600 .min(prevOfsSeg.get(1).distance(parEndPoint), nextOfsSeg.get(0).distance(parEndPoint)))
601 {
602 parEndPoint = new Point2d((prevOfsSeg.get(1).x + nextOfsSeg.get(0).x) / 2,
603 (prevOfsSeg.get(1).y + nextOfsSeg.get(0).y) / 2);
604 }
605 // center = intersections of helper lines
606 this.fractionalHelperCenters[i] = intersectionOfLines(get(i), parStartPoint, get(i + 1), parEndPoint);
607 if (this.fractionalHelperCenters[i] == null)
608 {
609 // parallel helper lines, parallel segments or /\/ cause parallel helper lines, use direction
610 this.fractionalHelperDirections[i] =
611 new Point2D.Double(parStartPoint.x - get(i).x, parStartPoint.y - get(i).y);
612 }
613 parStartPoint = parEndPoint;
614 }
615 // remember the intersection of the last two unit offset segments
616 this.lastOffsetIntersection = parStartPoint;
617 }
618 }
619
620 // use directions at start and end to get unit offset points to the left at a distance of 1
621 double ang = (start == null ? Math.atan2(get(1).y - get(0).y, get(1).x - get(0).x) : start.si) + Math.PI / 2;
622 Point2d p1 = new Point2d(get(0).x + Math.cos(ang), get(0).y + Math.sin(ang));
623 ang = (end == null ? Math.atan2(get(n).y - get(n - 1).y, get(n).x - get(n - 1).x) : end.si) + Math.PI / 2;
624 Point2d p2 = new Point2d(get(n).x + Math.cos(ang), get(n).y + Math.sin(ang));
625
626 // calculate first and last center (i.e. intersection of unit offset segments), which depend on inputs 'start' and 'end'
627 if (size() > 2)
628 {
629 this.fractionalHelperCenters[0] = intersectionOfLines(get(0), p1, get(1), this.firstOffsetIntersection);
630 this.fractionalHelperCenters[n - 1] = intersectionOfLines(get(n - 1), this.lastOffsetIntersection, get(n), p2);
631 if (this.fractionalHelperCenters[n - 1] == null)
632 {
633 // parallel helper lines, use direction for projection
634 this.fractionalHelperDirections[n - 1] = new Point2D.Double(p2.x - get(n).x, p2.y - get(n).y);
635 }
636 }
637 else
638 {
639 // only a single segment
640 this.fractionalHelperCenters[0] = intersectionOfLines(get(0), p1, get(1), p2);
641 }
642 if (this.fractionalHelperCenters[0] == null)
643 {
644 // parallel helper lines, use direction for projection
645 this.fractionalHelperDirections[0] = new Point2D.Double(p1.x - get(0).x, p1.y - get(0).y);
646 }
647
648 }
649
650 /**
651 * This method is used, rather than {@code Point2d.intersectionOfLines()} because this method will return {@code null} if
652 * the determinant < 0.0000001, rather than determinant &eq; 0.0. The benefit of this is that intersections are not so
653 * far away, that any calculations with them cause underflow or overflow issues.
654 * @param line1P1 point 1 of line 1.
655 * @param line1P2 point 2 of line 1.
656 * @param line2P1 point 1 of line 2.
657 * @param line2P2 point 2 of line 2.
658 * @return intersection of lines, or {@code null} for (nearly) parallel lines.
659 */
660 private Point2d intersectionOfLines(final Point2d line1P1, final Point2d line1P2, final Point2d line2P1,
661 final Point2d line2P2)
662 {
663 double l1p1x = line1P1.x;
664 double l1p1y = line1P1.y;
665 double l1p2x = line1P2.x - l1p1x;
666 double l1p2y = line1P2.y - l1p1y;
667 double l2p1x = line2P1.x - l1p1x;
668 double l2p1y = line2P1.y - l1p1y;
669 double l2p2x = line2P2.x - l1p1x;
670 double l2p2y = line2P2.y - l1p1y;
671 double determinant = (0 - l1p2x) * (l2p1y - l2p2y) - (0 - l1p2y) * (l2p1x - l2p2x);
672 if (Math.abs(determinant) < 0.0000001)
673 {
674 return null;
675 }
676 return new Point2d(l1p1x + (l1p2x * (l2p1x * l2p2y - l2p1y * l2p2x)) / determinant,
677 l1p1y + (l1p2y * (l2p1x * l2p2y - l2p1y * l2p2x)) / determinant);
678 }
679
680 /**
681 * Helper method for fractional projection which returns an offset line to the left of a segment at a distance of 1.
682 * @param segment segment number
683 * @return parallel line to the left of a segment at a distance of 1
684 */
685 private synchronized PolyLine2d unitOffsetSegment(final int segment)
686 {
687 return new PolyLine2d(get(segment), get(segment + 1)).offsetLine(1.0);
688 }
689
690 /**
691 * Returns the projected directional radius of the line at a given fraction. Negative values reflect right-hand curvature in
692 * the design-line direction. The radius is taken as the minimum of the radii at the vertices before and after the given
693 * fraction. The radius at a vertex is calculated as the radius of a circle that is equidistant from both edges connected to
694 * the vertex. The circle center is on a line perpendicular to the shortest edge, crossing through the middle of the
695 * shortest edge. This method ignores Z components.
696 * @param fraction fraction along the line, between 0.0 and 1.0 (both inclusive)
697 * @return radius; the local radius; or si field set to Double.NaN if line is totally straight
698 * @throws IllegalArgumentException fraction out of bounds
699 */
700 public synchronized Length getProjectedRadius(final double fraction) throws IllegalArgumentException
701 {
702 Throw.when(fraction < 0.0 || fraction > 1.0, IllegalArgumentException.class,
703 "Fraction %f is out of bounds [0.0 ... 1.0]", fraction);
704 if (this.vertexRadii == null)
705 {
706 this.vertexRadii = new Length[size() - 1];
707 }
708 int index = find(fraction * getLength());
709 if (index > 0 && this.vertexRadii[index] == null)
710 {
711 this.vertexRadii[index] = getProjectedVertexRadius(index);
712 }
713 if (index < size() - 2 && this.vertexRadii[index + 1] == null)
714 {
715 this.vertexRadii[index + 1] = getProjectedVertexRadius(index + 1);
716 }
717 if (index == 0)
718 {
719 if (this.vertexRadii.length < 2)
720 {
721 return Length.instantiateSI(Double.NaN);
722 }
723 return this.vertexRadii[1];
724 }
725 if (index == size() - 2)
726 {
727 return this.vertexRadii[size() - 2];
728 }
729 return Math.abs(this.vertexRadii[index].si) < Math.abs(this.vertexRadii[index + 1].si) ? this.vertexRadii[index]
730 : this.vertexRadii[index + 1];
731 }
732
733 /**
734 * Calculates the directional radius at a vertex. Negative values reflect right-hand curvature in the design-line direction.
735 * The radius at a vertex is calculated as the radius of a circle that is equidistant from both edges connected to the
736 * vertex. The circle center is on a line perpendicular to the shortest edge, crossing through the middle of the shortest
737 * edge. This function ignores Z components.
738 * @param index index of the vertex in range [1 ... size() - 2]
739 * @return radius at the vertex
740 * @throws IndexOutOfBoundsException if the index is out of bounds
741 */
742 public synchronized Length getProjectedVertexRadius(final int index) throws IndexOutOfBoundsException
743 {
744 Throw.when(index < 1 || index > size() - 2, IndexOutOfBoundsException.class,
745 "Index %d is out of bounds [1 ... size() - 2].", index);
746 determineFractionalHelpers(null, null);
747 double length1 = lengthAtIndex(index) - lengthAtIndex(index - 1);
748 double length2 = lengthAtIndex(index + 1) - lengthAtIndex(index);
749 int shortIndex = length1 < length2 ? index : index + 1;
750 // center of shortest edge
751 Point2d p1 =
752 new Point2d(.5 * (get(shortIndex - 1).x + get(shortIndex).x), .5 * (get(shortIndex - 1).y + get(shortIndex).y));
753 // perpendicular to shortest edge, line crossing p1
754 Point2d p2 = new Point2d(p1.x + (get(shortIndex).y - get(shortIndex - 1).y),
755 p1.y - (get(shortIndex).x - get(shortIndex - 1).x));
756 // vertex
757 Point2d p3 = get(index);
758 // point on line that splits angle between edges at vertex 50-50
759 Point2d p4 = this.fractionalHelperCenters[index];
760 if (p4 == null)
761 {
762 // parallel helper lines
763 p4 = new Point2d(p3.x + this.fractionalHelperDirections[index].x, p3.y + this.fractionalHelperDirections[index].y);
764 }
765 Point2d intersection = intersectionOfLines(p1, p2, p3, p4);
766 if (null == intersection)
767 {
768 return Length.instantiateSI(Double.NaN);
769 }
770 // determine left or right
771 double refLength = length1 < length2 ? length1 : length2;
772 double radius = intersection.distance(p1);
773 double i2p2 = intersection.distance(p2);
774 if (radius < i2p2 && i2p2 > refLength)
775 {
776 // left as p1 is closer than p2 (which was placed to the right) and not on the perpendicular line
777 return Length.instantiateSI(radius);
778 }
779 // right as not left
780 return Length.instantiateSI(-radius);
781 }
782
783 /**
784 * Returns the length fraction at the vertex.
785 * @param index index of vertex [0 ... size() - 1]
786 * @return length fraction at the vertex
787 * @throws IndexOutOfBoundsException if the index is out of bounds
788 */
789 public double getVertexFraction(final int index) throws IndexOutOfBoundsException
790 {
791 Throw.when(index < 0 || index > size() - 1, IndexOutOfBoundsException.class, "Index %d is out of bounds [0 %d].", index,
792 size() - 1);
793 return lengthAtIndex(index) / this.length.si;
794 }
795
796 /**
797 * Retrieve the centroid of this OtsLine2d.
798 * @return the centroid of this OtsLine2d
799 */
800 public final Point2d getCentroid()
801 {
802 return getBounds().midPoint();
803 }
804
805 @Override
806 @SuppressWarnings("checkstyle:designforextension")
807 public Point2d getLocation()
808 {
809 return getCentroid();
810 }
811
812 }