1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 package org.apache.commons.math3.geometry.euclidean.twod; 18 19 import java.awt.geom.AffineTransform; 20 21 import org.apache.commons.math3.exception.MathIllegalArgumentException; 22 import org.apache.commons.math3.exception.util.LocalizedFormats; 23 import org.apache.commons.math3.geometry.Point; 24 import org.apache.commons.math3.geometry.Vector; 25 import org.apache.commons.math3.geometry.euclidean.oned.Euclidean1D; 26 import org.apache.commons.math3.geometry.euclidean.oned.IntervalsSet; 27 import org.apache.commons.math3.geometry.euclidean.oned.OrientedPoint; 28 import org.apache.commons.math3.geometry.euclidean.oned.Vector1D; 29 import org.apache.commons.math3.geometry.partitioning.Embedding; 30 import org.apache.commons.math3.geometry.partitioning.Hyperplane; 31 import org.apache.commons.math3.geometry.partitioning.SubHyperplane; 32 import org.apache.commons.math3.geometry.partitioning.Transform; 33 import org.apache.commons.math3.util.FastMath; 34 import org.apache.commons.math3.util.MathArrays; 35 import org.apache.commons.math3.util.MathUtils; 36 37 /** This class represents an oriented line in the 2D plane. 38 39 * <p>An oriented line can be defined either by prolongating a line 40 * segment between two points past these points, or by one point and 41 * an angular direction (in trigonometric orientation).</p> 42 43 * <p>Since it is oriented the two half planes at its two sides are 44 * unambiguously identified as a left half plane and a right half 45 * plane. This can be used to identify the interior and the exterior 46 * in a simple way by local properties only when part of a line is 47 * used to define part of a polygon boundary.</p> 48 49 * <p>A line can also be used to completely define a reference frame 50 * in the plane. It is sufficient to select one specific point in the 51 * line (the orthogonal projection of the original reference frame on 52 * the line) and to use the unit vector in the line direction and the 53 * orthogonal vector oriented from left half plane to right half 54 * plane. We define two coordinates by the process, the 55 * <em>abscissa</em> along the line, and the <em>offset</em> across 56 * the line. All points of the plane are uniquely identified by these 57 * two coordinates. The line is the set of points at zero offset, the 58 * left half plane is the set of points with negative offsets and the 59 * right half plane is the set of points with positive offsets.</p> 60 61 * @since 3.0 62 */ 63 public class Line implements Hyperplane<Euclidean2D>, Embedding<Euclidean2D, Euclidean1D> { 64 65 /** Default value for tolerance. */ 66 private static final double DEFAULT_TOLERANCE = 1.0e-10; 67 68 /** Angle with respect to the abscissa axis. */ 69 private double angle; 70 71 /** Cosine of the line angle. */ 72 private double cos; 73 74 /** Sine of the line angle. */ 75 private double sin; 76 77 /** Offset of the frame origin. */ 78 private double originOffset; 79 80 /** Tolerance below which points are considered identical. */ 81 private final double tolerance; 82 83 /** Reverse line. */ 84 private Line reverse; 85 86 /** Build a line from two points. 87 * <p>The line is oriented from p1 to p2</p> 88 * @param p1 first point 89 * @param p2 second point 90 * @param tolerance tolerance below which points are considered identical 91 * @since 3.3 92 */ Line(final Vector2D p1, final Vector2D p2, final double tolerance)93 public Line(final Vector2D p1, final Vector2D p2, final double tolerance) { 94 reset(p1, p2); 95 this.tolerance = tolerance; 96 } 97 98 /** Build a line from a point and an angle. 99 * @param p point belonging to the line 100 * @param angle angle of the line with respect to abscissa axis 101 * @param tolerance tolerance below which points are considered identical 102 * @since 3.3 103 */ Line(final Vector2D p, final double angle, final double tolerance)104 public Line(final Vector2D p, final double angle, final double tolerance) { 105 reset(p, angle); 106 this.tolerance = tolerance; 107 } 108 109 /** Build a line from its internal characteristics. 110 * @param angle angle of the line with respect to abscissa axis 111 * @param cos cosine of the angle 112 * @param sin sine of the angle 113 * @param originOffset offset of the origin 114 * @param tolerance tolerance below which points are considered identical 115 * @since 3.3 116 */ Line(final double angle, final double cos, final double sin, final double originOffset, final double tolerance)117 private Line(final double angle, final double cos, final double sin, 118 final double originOffset, final double tolerance) { 119 this.angle = angle; 120 this.cos = cos; 121 this.sin = sin; 122 this.originOffset = originOffset; 123 this.tolerance = tolerance; 124 this.reverse = null; 125 } 126 127 /** Build a line from two points. 128 * <p>The line is oriented from p1 to p2</p> 129 * @param p1 first point 130 * @param p2 second point 131 * @deprecated as of 3.3, replaced with {@link #Line(Vector2D, Vector2D, double)} 132 */ 133 @Deprecated Line(final Vector2D p1, final Vector2D p2)134 public Line(final Vector2D p1, final Vector2D p2) { 135 this(p1, p2, DEFAULT_TOLERANCE); 136 } 137 138 /** Build a line from a point and an angle. 139 * @param p point belonging to the line 140 * @param angle angle of the line with respect to abscissa axis 141 * @deprecated as of 3.3, replaced with {@link #Line(Vector2D, double, double)} 142 */ 143 @Deprecated Line(final Vector2D p, final double angle)144 public Line(final Vector2D p, final double angle) { 145 this(p, angle, DEFAULT_TOLERANCE); 146 } 147 148 /** Copy constructor. 149 * <p>The created instance is completely independent from the 150 * original instance, it is a deep copy.</p> 151 * @param line line to copy 152 */ Line(final Line line)153 public Line(final Line line) { 154 angle = MathUtils.normalizeAngle(line.angle, FastMath.PI); 155 cos = line.cos; 156 sin = line.sin; 157 originOffset = line.originOffset; 158 tolerance = line.tolerance; 159 reverse = null; 160 } 161 162 /** {@inheritDoc} */ copySelf()163 public Line copySelf() { 164 return new Line(this); 165 } 166 167 /** Reset the instance as if built from two points. 168 * <p>The line is oriented from p1 to p2</p> 169 * @param p1 first point 170 * @param p2 second point 171 */ reset(final Vector2D p1, final Vector2D p2)172 public void reset(final Vector2D p1, final Vector2D p2) { 173 unlinkReverse(); 174 final double dx = p2.getX() - p1.getX(); 175 final double dy = p2.getY() - p1.getY(); 176 final double d = FastMath.hypot(dx, dy); 177 if (d == 0.0) { 178 angle = 0.0; 179 cos = 1.0; 180 sin = 0.0; 181 originOffset = p1.getY(); 182 } else { 183 angle = FastMath.PI + FastMath.atan2(-dy, -dx); 184 cos = dx / d; 185 sin = dy / d; 186 originOffset = MathArrays.linearCombination(p2.getX(), p1.getY(), -p1.getX(), p2.getY()) / d; 187 } 188 } 189 190 /** Reset the instance as if built from a line and an angle. 191 * @param p point belonging to the line 192 * @param alpha angle of the line with respect to abscissa axis 193 */ reset(final Vector2D p, final double alpha)194 public void reset(final Vector2D p, final double alpha) { 195 unlinkReverse(); 196 this.angle = MathUtils.normalizeAngle(alpha, FastMath.PI); 197 cos = FastMath.cos(this.angle); 198 sin = FastMath.sin(this.angle); 199 originOffset = MathArrays.linearCombination(cos, p.getY(), -sin, p.getX()); 200 } 201 202 /** Revert the instance. 203 */ revertSelf()204 public void revertSelf() { 205 unlinkReverse(); 206 if (angle < FastMath.PI) { 207 angle += FastMath.PI; 208 } else { 209 angle -= FastMath.PI; 210 } 211 cos = -cos; 212 sin = -sin; 213 originOffset = -originOffset; 214 } 215 216 /** Unset the link between an instance and its reverse. 217 */ unlinkReverse()218 private void unlinkReverse() { 219 if (reverse != null) { 220 reverse.reverse = null; 221 } 222 reverse = null; 223 } 224 225 /** Get the reverse of the instance. 226 * <p>Get a line with reversed orientation with respect to the 227 * instance.</p> 228 * <p> 229 * As long as neither the instance nor its reverse are modified 230 * (i.e. as long as none of the {@link #reset(Vector2D, Vector2D)}, 231 * {@link #reset(Vector2D, double)}, {@link #revertSelf()}, 232 * {@link #setAngle(double)} or {@link #setOriginOffset(double)} 233 * methods are called), then the line and its reverse remain linked 234 * together so that {@code line.getReverse().getReverse() == line}. 235 * When one of the line is modified, the link is deleted as both 236 * instance becomes independent. 237 * </p> 238 * @return a new line, with orientation opposite to the instance orientation 239 */ getReverse()240 public Line getReverse() { 241 if (reverse == null) { 242 reverse = new Line((angle < FastMath.PI) ? (angle + FastMath.PI) : (angle - FastMath.PI), 243 -cos, -sin, -originOffset, tolerance); 244 reverse.reverse = this; 245 } 246 return reverse; 247 } 248 249 /** Transform a space point into a sub-space point. 250 * @param vector n-dimension point of the space 251 * @return (n-1)-dimension point of the sub-space corresponding to 252 * the specified space point 253 */ toSubSpace(Vector<Euclidean2D> vector)254 public Vector1D toSubSpace(Vector<Euclidean2D> vector) { 255 return toSubSpace((Point<Euclidean2D>) vector); 256 } 257 258 /** Transform a sub-space point into a space point. 259 * @param vector (n-1)-dimension point of the sub-space 260 * @return n-dimension point of the space corresponding to the 261 * specified sub-space point 262 */ toSpace(Vector<Euclidean1D> vector)263 public Vector2D toSpace(Vector<Euclidean1D> vector) { 264 return toSpace((Point<Euclidean1D>) vector); 265 } 266 267 /** {@inheritDoc} */ toSubSpace(final Point<Euclidean2D> point)268 public Vector1D toSubSpace(final Point<Euclidean2D> point) { 269 Vector2D p2 = (Vector2D) point; 270 return new Vector1D(MathArrays.linearCombination(cos, p2.getX(), sin, p2.getY())); 271 } 272 273 /** {@inheritDoc} */ toSpace(final Point<Euclidean1D> point)274 public Vector2D toSpace(final Point<Euclidean1D> point) { 275 final double abscissa = ((Vector1D) point).getX(); 276 return new Vector2D(MathArrays.linearCombination(abscissa, cos, -originOffset, sin), 277 MathArrays.linearCombination(abscissa, sin, originOffset, cos)); 278 } 279 280 /** Get the intersection point of the instance and another line. 281 * @param other other line 282 * @return intersection point of the instance and the other line 283 * or null if there are no intersection points 284 */ intersection(final Line other)285 public Vector2D intersection(final Line other) { 286 final double d = MathArrays.linearCombination(sin, other.cos, -other.sin, cos); 287 if (FastMath.abs(d) < tolerance) { 288 return null; 289 } 290 return new Vector2D(MathArrays.linearCombination(cos, other.originOffset, -other.cos, originOffset) / d, 291 MathArrays.linearCombination(sin, other.originOffset, -other.sin, originOffset) / d); 292 } 293 294 /** {@inheritDoc} 295 * @since 3.3 296 */ project(Point<Euclidean2D> point)297 public Point<Euclidean2D> project(Point<Euclidean2D> point) { 298 return toSpace(toSubSpace(point)); 299 } 300 301 /** {@inheritDoc} 302 * @since 3.3 303 */ getTolerance()304 public double getTolerance() { 305 return tolerance; 306 } 307 308 /** {@inheritDoc} */ wholeHyperplane()309 public SubLine wholeHyperplane() { 310 return new SubLine(this, new IntervalsSet(tolerance)); 311 } 312 313 /** Build a region covering the whole space. 314 * @return a region containing the instance (really a {@link 315 * PolygonsSet PolygonsSet} instance) 316 */ wholeSpace()317 public PolygonsSet wholeSpace() { 318 return new PolygonsSet(tolerance); 319 } 320 321 /** Get the offset (oriented distance) of a parallel line. 322 * <p>This method should be called only for parallel lines otherwise 323 * the result is not meaningful.</p> 324 * <p>The offset is 0 if both lines are the same, it is 325 * positive if the line is on the right side of the instance and 326 * negative if it is on the left side, according to its natural 327 * orientation.</p> 328 * @param line line to check 329 * @return offset of the line 330 */ getOffset(final Line line)331 public double getOffset(final Line line) { 332 return originOffset + 333 (MathArrays.linearCombination(cos, line.cos, sin, line.sin) > 0 ? -line.originOffset : line.originOffset); 334 } 335 336 /** Get the offset (oriented distance) of a vector. 337 * @param vector vector to check 338 * @return offset of the vector 339 */ getOffset(Vector<Euclidean2D> vector)340 public double getOffset(Vector<Euclidean2D> vector) { 341 return getOffset((Point<Euclidean2D>) vector); 342 } 343 344 /** {@inheritDoc} */ getOffset(final Point<Euclidean2D> point)345 public double getOffset(final Point<Euclidean2D> point) { 346 Vector2D p2 = (Vector2D) point; 347 return MathArrays.linearCombination(sin, p2.getX(), -cos, p2.getY(), 1.0, originOffset); 348 } 349 350 /** {@inheritDoc} */ sameOrientationAs(final Hyperplane<Euclidean2D> other)351 public boolean sameOrientationAs(final Hyperplane<Euclidean2D> other) { 352 final Line otherL = (Line) other; 353 return MathArrays.linearCombination(sin, otherL.sin, cos, otherL.cos) >= 0.0; 354 } 355 356 /** Get one point from the plane. 357 * @param abscissa desired abscissa for the point 358 * @param offset desired offset for the point 359 * @return one point in the plane, with given abscissa and offset 360 * relative to the line 361 */ getPointAt(final Vector1D abscissa, final double offset)362 public Vector2D getPointAt(final Vector1D abscissa, final double offset) { 363 final double x = abscissa.getX(); 364 final double dOffset = offset - originOffset; 365 return new Vector2D(MathArrays.linearCombination(x, cos, dOffset, sin), 366 MathArrays.linearCombination(x, sin, -dOffset, cos)); 367 } 368 369 /** Check if the line contains a point. 370 * @param p point to check 371 * @return true if p belongs to the line 372 */ contains(final Vector2D p)373 public boolean contains(final Vector2D p) { 374 return FastMath.abs(getOffset(p)) < tolerance; 375 } 376 377 /** Compute the distance between the instance and a point. 378 * <p>This is a shortcut for invoking FastMath.abs(getOffset(p)), 379 * and provides consistency with what is in the 380 * org.apache.commons.math3.geometry.euclidean.threed.Line class.</p> 381 * 382 * @param p to check 383 * @return distance between the instance and the point 384 * @since 3.1 385 */ distance(final Vector2D p)386 public double distance(final Vector2D p) { 387 return FastMath.abs(getOffset(p)); 388 } 389 390 /** Check the instance is parallel to another line. 391 * @param line other line to check 392 * @return true if the instance is parallel to the other line 393 * (they can have either the same or opposite orientations) 394 */ isParallelTo(final Line line)395 public boolean isParallelTo(final Line line) { 396 return FastMath.abs(MathArrays.linearCombination(sin, line.cos, -cos, line.sin)) < tolerance; 397 } 398 399 /** Translate the line to force it passing by a point. 400 * @param p point by which the line should pass 401 */ translateToPoint(final Vector2D p)402 public void translateToPoint(final Vector2D p) { 403 originOffset = MathArrays.linearCombination(cos, p.getY(), -sin, p.getX()); 404 } 405 406 /** Get the angle of the line. 407 * @return the angle of the line with respect to the abscissa axis 408 */ getAngle()409 public double getAngle() { 410 return MathUtils.normalizeAngle(angle, FastMath.PI); 411 } 412 413 /** Set the angle of the line. 414 * @param angle new angle of the line with respect to the abscissa axis 415 */ setAngle(final double angle)416 public void setAngle(final double angle) { 417 unlinkReverse(); 418 this.angle = MathUtils.normalizeAngle(angle, FastMath.PI); 419 cos = FastMath.cos(this.angle); 420 sin = FastMath.sin(this.angle); 421 } 422 423 /** Get the offset of the origin. 424 * @return the offset of the origin 425 */ getOriginOffset()426 public double getOriginOffset() { 427 return originOffset; 428 } 429 430 /** Set the offset of the origin. 431 * @param offset offset of the origin 432 */ setOriginOffset(final double offset)433 public void setOriginOffset(final double offset) { 434 unlinkReverse(); 435 originOffset = offset; 436 } 437 438 /** Get a {@link org.apache.commons.math3.geometry.partitioning.Transform 439 * Transform} embedding an affine transform. 440 * @param transform affine transform to embed (must be inversible 441 * otherwise the {@link 442 * org.apache.commons.math3.geometry.partitioning.Transform#apply(Hyperplane) 443 * apply(Hyperplane)} method would work only for some lines, and 444 * fail for other ones) 445 * @return a new transform that can be applied to either {@link 446 * Vector2D Vector2D}, {@link Line Line} or {@link 447 * org.apache.commons.math3.geometry.partitioning.SubHyperplane 448 * SubHyperplane} instances 449 * @exception MathIllegalArgumentException if the transform is non invertible 450 * @deprecated as of 3.6, replaced with {@link #getTransform(double, double, double, double, double, double)} 451 */ 452 @Deprecated getTransform(final AffineTransform transform)453 public static Transform<Euclidean2D, Euclidean1D> getTransform(final AffineTransform transform) 454 throws MathIllegalArgumentException { 455 final double[] m = new double[6]; 456 transform.getMatrix(m); 457 return new LineTransform(m[0], m[1], m[2], m[3], m[4], m[5]); 458 } 459 460 /** Get a {@link org.apache.commons.math3.geometry.partitioning.Transform 461 * Transform} embedding an affine transform. 462 * @param cXX transform factor between input abscissa and output abscissa 463 * @param cYX transform factor between input abscissa and output ordinate 464 * @param cXY transform factor between input ordinate and output abscissa 465 * @param cYY transform factor between input ordinate and output ordinate 466 * @param cX1 transform addendum for output abscissa 467 * @param cY1 transform addendum for output ordinate 468 * @return a new transform that can be applied to either {@link 469 * Vector2D Vector2D}, {@link Line Line} or {@link 470 * org.apache.commons.math3.geometry.partitioning.SubHyperplane 471 * SubHyperplane} instances 472 * @exception MathIllegalArgumentException if the transform is non invertible 473 * @since 3.6 474 */ getTransform(final double cXX, final double cYX, final double cXY, final double cYY, final double cX1, final double cY1)475 public static Transform<Euclidean2D, Euclidean1D> getTransform(final double cXX, 476 final double cYX, 477 final double cXY, 478 final double cYY, 479 final double cX1, 480 final double cY1) 481 throws MathIllegalArgumentException { 482 return new LineTransform(cXX, cYX, cXY, cYY, cX1, cY1); 483 } 484 485 /** Class embedding an affine transform. 486 * <p>This class is used in order to apply an affine transform to a 487 * line. Using a specific object allow to perform some computations 488 * on the transform only once even if the same transform is to be 489 * applied to a large number of lines (for example to a large 490 * polygon)./<p> 491 */ 492 private static class LineTransform implements Transform<Euclidean2D, Euclidean1D> { 493 494 /** Transform factor between input abscissa and output abscissa. */ 495 private double cXX; 496 497 /** Transform factor between input abscissa and output ordinate. */ 498 private double cYX; 499 500 /** Transform factor between input ordinate and output abscissa. */ 501 private double cXY; 502 503 /** Transform factor between input ordinate and output ordinate. */ 504 private double cYY; 505 506 /** Transform addendum for output abscissa. */ 507 private double cX1; 508 509 /** Transform addendum for output ordinate. */ 510 private double cY1; 511 512 /** cXY * cY1 - cYY * cX1. */ 513 private double c1Y; 514 515 /** cXX * cY1 - cYX * cX1. */ 516 private double c1X; 517 518 /** cXX * cYY - cYX * cXY. */ 519 private double c11; 520 521 /** Build an affine line transform from a n {@code AffineTransform}. 522 * @param cXX transform factor between input abscissa and output abscissa 523 * @param cYX transform factor between input abscissa and output ordinate 524 * @param cXY transform factor between input ordinate and output abscissa 525 * @param cYY transform factor between input ordinate and output ordinate 526 * @param cX1 transform addendum for output abscissa 527 * @param cY1 transform addendum for output ordinate 528 * @exception MathIllegalArgumentException if the transform is non invertible 529 * @since 3.6 530 */ LineTransform(final double cXX, final double cYX, final double cXY, final double cYY, final double cX1, final double cY1)531 LineTransform(final double cXX, final double cYX, final double cXY, 532 final double cYY, final double cX1, final double cY1) 533 throws MathIllegalArgumentException { 534 535 this.cXX = cXX; 536 this.cYX = cYX; 537 this.cXY = cXY; 538 this.cYY = cYY; 539 this.cX1 = cX1; 540 this.cY1 = cY1; 541 542 c1Y = MathArrays.linearCombination(cXY, cY1, -cYY, cX1); 543 c1X = MathArrays.linearCombination(cXX, cY1, -cYX, cX1); 544 c11 = MathArrays.linearCombination(cXX, cYY, -cYX, cXY); 545 546 if (FastMath.abs(c11) < 1.0e-20) { 547 throw new MathIllegalArgumentException(LocalizedFormats.NON_INVERTIBLE_TRANSFORM); 548 } 549 550 } 551 552 /** {@inheritDoc} */ apply(final Point<Euclidean2D> point)553 public Vector2D apply(final Point<Euclidean2D> point) { 554 final Vector2D p2D = (Vector2D) point; 555 final double x = p2D.getX(); 556 final double y = p2D.getY(); 557 return new Vector2D(MathArrays.linearCombination(cXX, x, cXY, y, cX1, 1), 558 MathArrays.linearCombination(cYX, x, cYY, y, cY1, 1)); 559 } 560 561 /** {@inheritDoc} */ apply(final Hyperplane<Euclidean2D> hyperplane)562 public Line apply(final Hyperplane<Euclidean2D> hyperplane) { 563 final Line line = (Line) hyperplane; 564 final double rOffset = MathArrays.linearCombination(c1X, line.cos, c1Y, line.sin, c11, line.originOffset); 565 final double rCos = MathArrays.linearCombination(cXX, line.cos, cXY, line.sin); 566 final double rSin = MathArrays.linearCombination(cYX, line.cos, cYY, line.sin); 567 final double inv = 1.0 / FastMath.sqrt(rSin * rSin + rCos * rCos); 568 return new Line(FastMath.PI + FastMath.atan2(-rSin, -rCos), 569 inv * rCos, inv * rSin, 570 inv * rOffset, line.tolerance); 571 } 572 573 /** {@inheritDoc} */ apply(final SubHyperplane<Euclidean1D> sub, final Hyperplane<Euclidean2D> original, final Hyperplane<Euclidean2D> transformed)574 public SubHyperplane<Euclidean1D> apply(final SubHyperplane<Euclidean1D> sub, 575 final Hyperplane<Euclidean2D> original, 576 final Hyperplane<Euclidean2D> transformed) { 577 final OrientedPoint op = (OrientedPoint) sub.getHyperplane(); 578 final Line originalLine = (Line) original; 579 final Line transformedLine = (Line) transformed; 580 final Vector1D newLoc = 581 transformedLine.toSubSpace(apply(originalLine.toSpace(op.getLocation()))); 582 return new OrientedPoint(newLoc, op.isDirect(), originalLine.tolerance).wholeHyperplane(); 583 } 584 585 } 586 587 } 588