001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.commons.math3.geometry.euclidean.twod; 018 019import java.awt.geom.AffineTransform; 020 021import org.apache.commons.math3.exception.MathIllegalArgumentException; 022import org.apache.commons.math3.exception.util.LocalizedFormats; 023import org.apache.commons.math3.geometry.Point; 024import org.apache.commons.math3.geometry.Vector; 025import org.apache.commons.math3.geometry.euclidean.oned.Euclidean1D; 026import org.apache.commons.math3.geometry.euclidean.oned.IntervalsSet; 027import org.apache.commons.math3.geometry.euclidean.oned.OrientedPoint; 028import org.apache.commons.math3.geometry.euclidean.oned.Vector1D; 029import org.apache.commons.math3.geometry.partitioning.Embedding; 030import org.apache.commons.math3.geometry.partitioning.Hyperplane; 031import org.apache.commons.math3.geometry.partitioning.SubHyperplane; 032import org.apache.commons.math3.geometry.partitioning.Transform; 033import org.apache.commons.math3.util.FastMath; 034import org.apache.commons.math3.util.MathArrays; 035import org.apache.commons.math3.util.MathUtils; 036 037/** This class represents an oriented line in the 2D plane. 038 039 * <p>An oriented line can be defined either by prolongating a line 040 * segment between two points past these points, or by one point and 041 * an angular direction (in trigonometric orientation).</p> 042 043 * <p>Since it is oriented the two half planes at its two sides are 044 * unambiguously identified as a left half plane and a right half 045 * plane. This can be used to identify the interior and the exterior 046 * in a simple way by local properties only when part of a line is 047 * used to define part of a polygon boundary.</p> 048 049 * <p>A line can also be used to completely define a reference frame 050 * in the plane. It is sufficient to select one specific point in the 051 * line (the orthogonal projection of the original reference frame on 052 * the line) and to use the unit vector in the line direction and the 053 * orthogonal vector oriented from left half plane to right half 054 * plane. We define two coordinates by the process, the 055 * <em>abscissa</em> along the line, and the <em>offset</em> across 056 * the line. All points of the plane are uniquely identified by these 057 * two coordinates. The line is the set of points at zero offset, the 058 * left half plane is the set of points with negative offsets and the 059 * right half plane is the set of points with positive offsets.</p> 060 061 * @since 3.0 062 */ 063public class Line implements Hyperplane<Euclidean2D>, Embedding<Euclidean2D, Euclidean1D> { 064 065 /** Default value for tolerance. */ 066 private static final double DEFAULT_TOLERANCE = 1.0e-10; 067 068 /** Angle with respect to the abscissa axis. */ 069 private double angle; 070 071 /** Cosine of the line angle. */ 072 private double cos; 073 074 /** Sine of the line angle. */ 075 private double sin; 076 077 /** Offset of the frame origin. */ 078 private double originOffset; 079 080 /** Tolerance below which points are considered identical. */ 081 private final double tolerance; 082 083 /** Reverse line. */ 084 private Line reverse; 085 086 /** Build a line from two points. 087 * <p>The line is oriented from p1 to p2</p> 088 * @param p1 first point 089 * @param p2 second point 090 * @param tolerance tolerance below which points are considered identical 091 * @since 3.3 092 */ 093 public Line(final Vector2D p1, final Vector2D p2, final double tolerance) { 094 reset(p1, p2); 095 this.tolerance = tolerance; 096 } 097 098 /** Build a line from a point and an angle. 099 * @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 */ 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 */ 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 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 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 */ 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} */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 263 public Vector2D toSpace(Vector<Euclidean1D> vector) { 264 return toSpace((Point<Euclidean1D>) vector); 265 } 266 267 /** {@inheritDoc} */ 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} */ 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 */ 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 */ 297 public Point<Euclidean2D> project(Point<Euclidean2D> point) { 298 return toSpace(toSubSpace(point)); 299 } 300 301 /** {@inheritDoc} 302 * @since 3.3 303 */ 304 public double getTolerance() { 305 return tolerance; 306 } 307 308 /** {@inheritDoc} */ 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 */ 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 */ 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 */ 340 public double getOffset(Vector<Euclidean2D> vector) { 341 return getOffset((Point<Euclidean2D>) vector); 342 } 343 344 /** {@inheritDoc} */ 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} */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 426 public double getOriginOffset() { 427 return originOffset; 428 } 429 430 /** Set the offset of the origin. 431 * @param offset offset of the origin 432 */ 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 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 */ 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 */ 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} */ 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} */ 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} */ 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}