001/* 002 * LineSegment -- Represents an abstract line segment in n-D space. 003 * 004 * Copyright (C) 2013-2018, Joseph A. Huwaldt. 005 * All rights reserved. 006 * 007 * This library is free software; you can redistribute it and/or 008 * modify it under the terms of the GNU Lesser General Public 009 * License as published by the Free Software Foundation; either 010 * version 2.1 of the License, or (at your option) any later version. 011 * 012 * This library is distributed in the hope that it will be useful, 013 * but WITHOUT ANY WARRANTY; without even the implied warranty of 014 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 015 * Lesser General Public License for more details. 016 * 017 * You should have received a copy of the GNU Lesser General Public License 018 * along with this program; if not, write to the Free Software 019 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 020 * Or visit: http://www.gnu.org/licenses/lgpl.html 021 */ 022package geomss.geom; 023 024import geomss.geom.nurbs.CurveFactory; 025import geomss.geom.nurbs.NurbsCurve; 026import jahuwaldt.js.param.Parameter; 027import jahuwaldt.tools.math.BracketRoot1D; 028import jahuwaldt.tools.math.Evaluatable1D; 029import jahuwaldt.tools.math.RootException; 030import java.text.MessageFormat; 031import java.util.List; 032import static java.util.Objects.nonNull; 033import static java.util.Objects.requireNonNull; 034import java.util.logging.Level; 035import java.util.logging.Logger; 036import javax.measure.converter.ConversionException; 037import javax.measure.quantity.Dimensionless; 038import javax.measure.quantity.Length; 039import javax.measure.unit.SI; 040import javax.measure.unit.Unit; 041import javolution.lang.MathLib; 042import javolution.text.Text; 043import javolution.text.TextBuilder; 044import javolution.util.FastTable; 045 046/** 047 * The interface and implementation in common to all line segments in n-dimensional space. 048 * 049 * <p> Modified by: Joseph A. Huwaldt </p> 050 * 051 * @author Joseph A. Huwaldt, Date: January 14, 2012 052 * @version April 3, 2018 053 */ 054@SuppressWarnings({"serial", "CloneableImplementsClone"}) 055public abstract class LineSegment extends AbstractCurve<LineSegment> implements PointGeometry<LineSegment> { 056 057 /** 058 * Return the starting point of the line segment. 059 * 060 * @return The starting point for this line segment. 061 */ 062 public abstract GeomPoint getStart(); 063 064 /** 065 * Return the end point of the line segment. 066 * 067 * @return The end point of this line segment. 068 */ 069 public abstract GeomPoint getEnd(); 070 071 /** 072 * Get unit direction vector for the line segment. 073 * 074 * @return A unit vector indicating the direction of this line segment. 075 */ 076 public abstract GeomVector<Dimensionless> getUnitVector(); 077 078 /** 079 * Return the dimensional direction/derivative vector for this line segment. The 080 * length of this vector is the length of the line segment, the origin is at the start 081 * point and the end of the vector is the line end. 082 * 083 * @return The dimensional derivative vector for this line segment. 084 */ 085 public abstract GeomVector<Length> getDerivativeVector(); 086 087 /** 088 * Returns the number of child-elements that make up this geometry element. This 089 * implementation always returns 2 as a LineSegment has two end points. 090 * 091 * @return The number of points in this line segment (always returns 2). 092 */ 093 @Override 094 public int size() { 095 return 2; 096 } 097 098 /** 099 * Returns the number of physical dimensions of the geometry element. 100 * 101 * @return The number of physical dimensions of this geometry element. 102 */ 103 @Override 104 public int getPhyDimension() { 105 return getStart().getPhyDimension(); 106 } 107 108 /** 109 * Return the total number of points in this geometry element. 110 * 111 * @return Always returns 2. 112 */ 113 @Override 114 public int getNumberOfPoints() { 115 return 2; 116 } 117 118 /** 119 * Split this curve at the specified parametric position returning a list containing 120 * two curves (a lower curve with smaller parametric positions than "s" and an upper 121 * curve with larger parametric positions). 122 * 123 * @param s The parametric position where this curve should be split (must not be 0 or 124 * 1!). 125 * @return A list containing two curves: 0 == the lower curve, 1 == the upper curve. 126 */ 127 @Override 128 public GeomList<LineSegment> splitAt(double s) { 129 validateParameter(s); 130 s = roundParNearEnds(s); 131 if (parNearEnds(s, TOL_S)) 132 throw new IllegalArgumentException(MessageFormat.format( 133 RESOURCES.getString("canNotSplitAtEnds"), "curve")); 134 135 // Get the point at the specified split point. 136 Point p = getRealPoint(s); 137 138 // Create the curve segments. 139 LineSeg cl = LineSeg.valueOf(getStart().immutable(), p); 140 LineSeg cu = LineSeg.valueOf(p, getEnd().immutable()); 141 142 // Create the output list. 143 GeomList output = GeomList.newInstance(); 144 output.add(cl, cu); 145 146 return output; 147 } 148 149 /** 150 * Return the curvature (kappa = 1/rho; where rho = the radius of curvature) of the 151 * curve at the parametric position <code>s</code>. This implementation always returns 152 * zero. 153 * 154 * @param s Parametric distance to calculate the curvature for (0.0 to 1.0 inclusive). 155 * @return The curvature of the curve at the specified parametric position in units of 156 * 1/Length. 157 */ 158 @Override 159 public Parameter getCurvature(double s) { 160 validateParameter(s); 161 return Parameter.valueOf(0, getUnit().inverse()); 162 } 163 164 /** 165 * Return the variation of curvature or rate of change of curvature (VOC or 166 * dKappa(s)/ds) at the parametric position <code>s</code>. The VOC for a line segment 167 * is always zero. 168 * 169 * @param s Parametric distance to calculate the variation of curvature for (0.0 to 170 * 1.0 inclusive). 171 * @return The variation of curvature of the curve at the specified parametric 172 * position in units of 1/Length. 173 */ 174 @Override 175 public Parameter getVariationOfCurvature(double s) { 176 validateParameter(s); 177 return Parameter.valueOf(0, getUnit().inverse()); 178 } 179 180 /** 181 * Return the torsion of the curve at the parametric position <code>s</code>. The 182 * torsion is a measure of the rotation or twist about the tangent vector. Torsion for 183 * a line segment is always zero. 184 * 185 * @param s Parametric distance to calculate the torsion for (0.0 to 1.0 inclusive). 186 * @return The torsion of the curve at the specified parametric position in units of 187 * 1/Length. 188 */ 189 @Override 190 public Parameter getTorsion(double s) { 191 validateParameter(s); 192 return Parameter.valueOf(0, getUnit().inverse()); 193 } 194 195 /** 196 * Return the arc length of a segment of this curve. 197 * 198 * @param s1 The starting parametric distance along the curve to begin the arc-length 199 * calculation from. 200 * @param s2 The ending parametric distance along the curve to end the arc-length 201 * calculation at. 202 * @param eps The desired fractional accuracy on the arc-length. For this curve type, 203 * this parameter is ignored and the exact arc length is returned. 204 * @return The arc length of the specified segment of the curve. 205 */ 206 @Override 207 public Parameter<Length> getArcLength(double s1, double s2, double eps) { 208 validateParameter(s1); 209 validateParameter(s2); 210 211 return getArcLength(0).times(MathLib.abs(s2 - s1)); 212 } 213 214 /** 215 * Return a subrange point at the position on the curve with the specified arc-length. 216 * If the requested arc-length is ≤ 0, the start of the curve is returned. If the 217 * requested arc length is > the total arc length of the curve, then the end point 218 * is returned. 219 * 220 * @param targetArcLength The target arc length to find in meters. May not be null. 221 * @param tol Fractional tolerance (in parameter space) to refine the 222 * point position to. For this curve, this parameter is ignored 223 * and the exact point position is always returned. 224 * @return A subrange point on the curve at the specified arc-length position. 225 */ 226 @Override 227 public SubrangePoint getPointAtArcLength(Parameter<Length> targetArcLength, double tol) { 228 // Deal with an obvious case first. 229 if (targetArcLength.isApproxZero()) 230 return SubrangePoint.newInstance(this, Point.valueOf(0)); 231 232 double arcLengthValue = targetArcLength.getValue(SI.METER); 233 234 // Calculate the full arc-length of the curve (tolerance is ignored). 235 double fullArcLength = getArcLength(0).getValue(SI.METER); 236 237 // Is the requested arc length > than the actual arc length? 238 if (arcLengthValue > fullArcLength) 239 return SubrangePoint.newInstance(this, Point.valueOf(1)); 240 241 // The parametric position is the ratio of the desired arc-length to the full arc-length. 242 double s = arcLengthValue / fullArcLength; 243 244 return getPoint(s); 245 } 246 247 /** 248 * Return a string of points that are gridded onto the curve using the specified 249 * spacing and gridding rule. 250 * 251 * @param gridRule Specifies whether the subdivision spacing is applied with respect 252 * to arc-length in real space or parameter space. May not be null. 253 * @param spacing A list of values used to define the subdivision spacing. 254 * <code>gridRule</code> specifies whether the subdivision spacing is 255 * applied with respect to arc-length in real space or parameter 256 * space. If the spacing is arc-length, then the values are 257 * interpreted as fractions of the arc length of the curve from 0 to 258 * 1. May not be null. 259 * @return A string of subrange points gridded onto the curve at the specified 260 * parametric positions. 261 */ 262 @Override 263 public PointString<SubrangePoint> extractGrid(GridRule gridRule, List<Double> spacing) { 264 265 PointString<SubrangePoint> str = PointString.newInstance(); 266 267 switch (gridRule) { 268 case PAR: 269 // Parametric spacing. 270 for (double s : spacing) { 271 if (s > 1) 272 s = 1; 273 else if (s < 0) 274 s = 0; 275 str.add(this.getPoint(s)); 276 } 277 break; 278 279 case ARC: 280 // Arc-length spacing. 281 Parameter<Length> fullArcLength = getArcLength(0); 282 for (double s : spacing) { 283 SubrangePoint p = getPointAtArcLength(fullArcLength.times(s), 0); 284 str.add(p); 285 } 286 break; 287 288 default: 289 throw new IllegalArgumentException( 290 MessageFormat.format(RESOURCES.getString("crvUnsupportedGridRule"), 291 gridRule.toString())); 292 293 } 294 295 return str; 296 } 297 298 /** 299 * Return a string of points that are gridded onto the curve with the number of points 300 * and spacing chosen to result in straight line segments between the points that have 301 * mid-points that are all within the specified tolerance of this curve. 302 * 303 * @param tol The maximum distance that a straight line between gridded points may 304 * deviate from this curve. Ignored by this implementation. 305 * @return A string of subrange points gridded onto the curve. 306 */ 307 @Override 308 public PointString<SubrangePoint> gridToTolerance(Parameter<Length> tol) { 309 310 // Create the list of points. 311 PointString str = PointString.newInstance(); 312 str.add(getPoint(0)); 313 str.add(getPoint(1)); 314 315 return str; 316 } 317 318 /** 319 * Return the intersection between a plane and this curve. 320 * 321 * @param plane The plane to intersect with this curve. May not be null. 322 * @param tol Fractional tolerance (in parameter space) to refine the point 323 * positions to. For this curve, this parameter is ignored and the exact 324 * point positions are returned. 325 * @return A PointString containing zero or one subrange points made by the 326 * intersection of this curve with the specified plane. If no intersection is 327 * found, an empty PointString is returned. 328 */ 329 @Override 330 public PointString<SubrangePoint> intersect(GeomPlane plane, double tol) { 331 requireNonNull(plane); 332 333 // Intersect the plane with an infinite line. 334 MutablePoint p = MutablePoint.newInstance(getPhyDimension(), getUnit()); 335 IntersectType type = GeomUtil.linePlaneIntersect(getStart(), getDerivativeVector(), plane, p); 336 337 // Check for no intersection. 338 PointString<SubrangePoint> str = PointString.newInstance(); 339 if (type == IntersectType.DISJOINT) 340 return str; 341 342 // Determine the parametric position of the intersection point. 343 Parameter sDir = p.minus(getStart()).toGeomVector().dot(getDerivativeVector()); 344 if (sDir.getValue() >= 0) { 345 // The intersection is not at a negative parametric position. 346 double length = getArcLength(0).getValue(); 347 double pp0_dist = p.distance(getStart()).getValue(); 348 if (pp0_dist <= length) { 349 // The intersection is not beyond the end of the line. 350 double s = pp0_dist / length; 351 str.add(getPoint(s)); 352 } 353 } 354 355 return str; 356 } 357 358 /** 359 * Return the intersection between a line segment and this curve. 360 * 361 * @param line The line segment to intersect. May not be null. 362 * @param tol Tolerance (in physical space) to refine the point positions to. A null 363 * value indicates an exact intersection is required. 364 * @return A list containing two PointString instances each containing zero or 1 365 * subrange points, on this line segment and the input line segment 366 * respectively, made by the intersection of this line segment with the 367 * specified line segment. If no intersections are found a list of two empty 368 * PointStrings are returned. 369 */ 370 @Override 371 public GeomList<PointString<SubrangePoint>> intersect(LineSegment line, Parameter<Length> tol) { 372 // This is simply a single line-line intersection problem. 373 374 GeomList<PointString<SubrangePoint>> output = GeomList.newInstance(); 375 output.add(PointString.newInstance()); 376 output.add(PointString.newInstance()); 377 378 // Check bounding boxes first. 379 if (!GeomUtil.boundsIntersect(this, line)) 380 return output; 381 382 // Extract the start point and tangent vector of the two lines. 383 GeomPoint p1 = this.getStart(); 384 GeomVector<Length> t1 = this.getDerivativeVector(); 385 GeomPoint p2 = line.getStart(); 386 GeomVector<Length> t2 = line.getDerivativeVector(); 387 388 // Do the line-line intersection problem. 389 MutablePoint sOut = MutablePoint.newInstance(2); 390 IntersectType type = GeomUtil.lineLineIntersect(p1, t1, p2, t2, tol, sOut, null, null); 391 392 // Collect the outputs. 393 if (type == IntersectType.DISJOINT || 394 (sOut.getValue(0) < 0 || sOut.getValue(0) > 1 || 395 sOut.getValue(1) < 0 || sOut.getValue(1) > 1)) { 396 MutablePoint.recycle(sOut); 397 return output; 398 } 399 400 output.get(0).add(getPoint(sOut.getValue(0))); 401 output.get(1).add(line.getPoint(sOut.getValue(1))); 402 MutablePoint.recycle(sOut); 403 404 return output; 405 } 406 407 /** 408 * Return a list of brackets that surround possible closest/farthest points. Each of 409 * the brackets will be refined using a root solver in order to find the actual 410 * closest or farthest points. 411 * <p> 412 * This implementation sub-divides the curve into 2 equal-sized segments and looks for 413 * a single bracket inside each segment. 414 * </p> 415 * 416 * @param point The point to find the closest/farthest point on this curve to/from 417 * (guaranteed to be the same physical dimension before this method is 418 * called). Ignored by this implementation. 419 * @param closest Set to <code>true</code> to return the closest point or 420 * <code>false</code> to return the farthest point. Ignored by this 421 * implementation. 422 * @param eval A function that calculates the dot product of (p(s)-q) and ps(s) on 423 * the curve. May not be null. 424 * @return A list of brackets that each surround a potential closest/farthest point. 425 */ 426 @Override 427 protected List<BracketRoot1D> guessClosestFarthest(GeomPoint point, boolean closest, 428 Evaluatable1D eval) { 429 430 // Find multiple closest/farthest points (roots) by sub-dividing curve into pieces and 431 // bracketing any roots that occur in any of those segments. 432 List<BracketRoot1D> brackets; 433 try { 434 435 brackets = BracketRoot1D.findBrackets(requireNonNull(eval), 0, 1, 2); 436 437 } catch (RootException err) { 438 Logger.getLogger(LineSegment.class.getName()).log(Level.WARNING, 439 "Failed to bracket closest/farthest point.", err); 440 return FastTable.newInstance(); 441 } 442 443 return brackets; 444 } 445 446 /** 447 * Return a list of brackets that surround possible points on this curve that are 448 * closest to the target geometry object. Each of the brackets will be refined using a 449 * root solver in order to find the actual closest points. 450 * <p> 451 * This implementation sub-divides the curve into 2 equal-sized segments and looks for 452 * a single bracket inside each segment. 453 * </p> 454 * 455 * @param eval A function that calculates the dot product of (p(s)-q) and ps(s) on the 456 * curve where "q" is the closest point on the target geometry object. 457 * May not be null. 458 * @return A list of brackets that each surround a potential closest point on this 459 * curve. 460 */ 461 @Override 462 protected List<BracketRoot1D> guessClosest(PerpPointPlaneEvaluatable eval) { 463 464 // Find multiple closest/farthest points (roots) by sub-dividing curve into pieces and 465 // bracketing any roots that occur in any of those segments. 466 List<BracketRoot1D> brackets; 467 try { 468 469 brackets = BracketRoot1D.findBrackets(eval, 0, 1, 2); 470 471 } catch (RootException err) { 472 Logger.getLogger(LineSegment.class.getName()).log(Level.WARNING, 473 "Failed to bracket closest point.", err); 474 return FastTable.newInstance(); 475 } 476 477 return brackets; 478 } 479 480 /** 481 * Returns the most extreme point, either minimum or maximum, in the specified 482 * coordinate direction on this curve. 483 * 484 * @param dim An index indicating the dimension to find the min/max point for (0=X, 485 * 1=Y, 2=Z, etc). 486 * @param max Set to <code>true</code> to return the maximum value, <code>false</code> 487 * to return the minimum. 488 * @param tol Fractional tolerance (in parameter space) to refine the min/max point 489 * position to. 490 * @return The point found on this curve that is the min or max in the specified 491 * coordinate direction. 492 */ 493 @Override 494 public SubrangePoint getLimitPoint(int dim, boolean max, double tol) { 495 // Check the input dimension for consistancy. 496 int thisDim = getPhyDimension(); 497 if (dim < 0 || dim >= thisDim) 498 throw new DimensionException(MessageFormat.format( 499 RESOURCES.getString("inputDimOutOfRange"), "line")); 500 501 // Get the start and end points. 502 GeomPoint p0 = getStart(); 503 GeomPoint p1 = getEnd(); 504 505 // Limit point must always be one of the ends of a line segment. 506 if (max) { 507 if (p0.get(dim).isGreaterThan(p1.get(dim))) 508 return getPoint(0); // p0 509 else 510 return getPoint(1); // p1 511 512 } 513 // else min 514 if (p0.get(dim).isLessThan(p1.get(dim))) 515 return getPoint(0); // p0 516 517 return getPoint(1); // p1 518 } 519 520 /** 521 * Return the number of points per segment that should be used when analyzing curve 522 * segments by certain methods. Subclasses should override this method to provide a 523 * more appropriate number of points per segment. 524 *<p> 525 * This implementation always returns 1. 526 *</p> 527 * 528 * @return Always returns 1. 529 */ 530 @Override 531 protected int getNumPointsPerSegment() { 532 return 1; 533 } 534 535 /** 536 * Return <code>true</code> if this LineSegment contains valid and finite numerical 537 * components. A value of <code>false</code> will be returned if any of the coordinate 538 * values are NaN or Inf. 539 * 540 * @return true if this line segment contains valid and finite data. 541 */ 542 @Override 543 public boolean isValid() { 544 return getStart().isValid() && getEnd().isValid(); 545 } 546 547 /** 548 * Returns <code>true</code> if this curve is a line to within the specified 549 * tolerance. This implementation always returns <code>true</code> if the line is not 550 * degenerate. 551 * 552 * @param tol The tolerance for determining if this curve is a line. May not be null. 553 * @return Always returns <code>true</code> if the line is not degenerate. 554 */ 555 @Override 556 public boolean isLine(Parameter<Length> tol) { 557 return !isDegenerate(tol); 558 } 559 560 /** 561 * Return <code>true</code> if this curve is planar or <code>false</code> if it is 562 * not. This implementation always returns <code>true</code> 563 * 564 * @param tol The geometric tolerance to use in determining if the curve is planar. 565 * Ignored by this implementation. 566 * 567 * @return Always returns true. 568 */ 569 @Override 570 public boolean isPlanar(Parameter<Length> tol) { 571 return true; 572 } 573 574 /** 575 * Returns <code>true</code> if this curve is a circular arc to within the specified 576 * tolerance. This implementation always returns <code>false</code>. 577 * 578 * @param tol The tolerance for determining if this curve is a circular arc. 579 * Ignored by this implementation. 580 * 581 * @return Always returns false. 582 */ 583 @Override 584 public boolean isCircular(Parameter<Length> tol) { 585 return false; 586 } 587 588 /** 589 * Returns transformed version of this element. The returned object implements 590 * {@link geomss.geom.GeomTransform} and contains this element as a child. 591 * 592 * @param transform The transformation to apply to this geometry. May not be null. 593 * @return A new line segment that is identical to this one with the specified 594 * transformation applied. 595 * @throws DimensionException if this point is not 3D. 596 */ 597 @Override 598 public LineSegTrans getTransformed(GTransform transform) { 599 return LineSegTrans.newInstance(this, requireNonNull(transform)); 600 } 601 602 /** 603 * Returns the unit in which this curve is stated. 604 * 605 * @return The unit in which this curve is stated. 606 */ 607 @Override 608 public Unit<Length> getUnit() { 609 return getStart().getUnit(); 610 } 611 612 /** 613 * Return a NURBS curve representation of this line segment. An exact representation 614 * is returned and the tolerance parameter is ignored. 615 * 616 * @param tol Ignored. May pass <code>null</code>. 617 * @return A NURBS curve that exactly represents this line segment. 618 */ 619 @Override 620 public NurbsCurve toNurbs(Parameter<Length> tol) { 621 NurbsCurve curve = CurveFactory.createLine(getStart(), getEnd()); 622 copyState(curve); // Copy over the super-class state for this curve to the new one. 623 return curve; 624 } 625 626 /** 627 * Return a NURBS curve representation of this line segment. An exact representation 628 * is returned. 629 * 630 * @return A NURBS curve that exactly represents this line segment. 631 */ 632 public NurbsCurve toNurbs() { 633 return toNurbs(null); 634 } 635 636 /** 637 * Returns the text representation of this geometry element that consists of the name 638 * followed by the start and end points. For example: 639 * <pre> 640 * {aLine = {{0.0 m, 0.0 m},{1.0 , 0.0 }} 641 * </pre> 642 * If there is no name, then the output looks like this: 643 * <pre> 644 * {{0.0 m, 0.0 m},{1.0 , 0.0 }} 645 * </pre> 646 * 647 * @return the text representation of this geometry element. 648 */ 649 @Override 650 public Text toText() { 651 TextBuilder tmp = TextBuilder.newInstance(); 652 tmp.append('{'); 653 String nameStr = getName(); 654 boolean hasName = nonNull(nameStr); 655 if (hasName) { 656 tmp.append(nameStr); 657 tmp.append(" = {"); 658 } 659 660 tmp.append(getStart().toText()); 661 tmp.append(","); 662 tmp.append(getEnd().toText()); 663 664 if (hasName) 665 tmp.append('}'); 666 tmp.append('}'); 667 Text txt = tmp.toText(); 668 TextBuilder.recycle(tmp); 669 return txt; 670 } 671 672 /** 673 * Returns the equivalent to this LineSegment object but stated in the specified 674 * unit. 675 * 676 * @param unit the length unit of the line segment to be returned. May not be null. 677 * @return an equivalent to this line segment object but stated in the specified 678 * unit. 679 * @throws ConversionException if the the input unit is not a length unit. 680 */ 681 @Override 682 public abstract LineSegment to(Unit<Length> unit) throws ConversionException; 683 684}