View Javadoc

    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.geometry.euclidean.twod;
    18
    19  import java.text.MessageFormat;
    20  import java.util.Objects;
    21
    22  import org.apache.commons.geometry.core.Transform;
    23  import org.apache.commons.geometry.core.partitioning.AbstractHyperplane;
    24  import org.apache.commons.geometry.core.partitioning.EmbeddingHyperplane;
    25  import org.apache.commons.geometry.core.partitioning.Hyperplane;
    26  import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
    27  import org.apache.commons.geometry.euclidean.oned.AffineTransformMatrix1D;
    28  import org.apache.commons.geometry.euclidean.oned.Vector1D;
    29  import org.apache.commons.numbers.angle.PlaneAngleRadians;
    30  import org.apache.commons.numbers.arrays.LinearCombination;
    31
    32  /** This class represents an oriented line in the 2D plane.
    33
    34   * <p>An oriented line can be defined either by extending a line
    35   * segment between two points past these points, by specifying a
    36   * point and a direction, or by specifying a point and an angle
    37   * relative to the x-axis.</p>
    38
    39   * <p>Since the line oriented, the two half planes on its sides are
    40   * unambiguously identified as the left half plane and the right half
    41   * plane. This can be used to identify the interior and the exterior
    42   * in a simple way when a line is used to define a portion of a polygon
    43   * boundary.</p>
    44
    45   * <p>A line can also be used to completely define a reference frame
    46   * in the plane. It is sufficient to select one specific point in the
    47   * line (the orthogonal projection of the original reference frame on
    48   * the line) and to use the unit vector in the line direction (see
    49   * {@link #getDirection()} and the orthogonal vector oriented from the
    50   * left half plane to the right half plane (see {@link #getOffsetDirection()}.
    51   * We define two coordinates by the process, the <em>abscissa</em> along
    52   * the line, and the <em>offset</em> across the line. All points of the
    53   * plane are uniquely identified by these two coordinates. The line is
    54   * the set of points at zero offset, the left half plane is the set of
    55   * points with negative offsets and the right half plane is the set of
    56   * points with positive offsets.</p>
    57   * @see Lines
    58   */
    59  public final class Line extends AbstractHyperplane<Vector2D>
    60      implements EmbeddingHyperplane<Vector2D, Vector1D> {
    61
    62      /** Format string for creating line string representations. */
    63      static final String TO_STRING_FORMAT = "{0}[origin= {1}, direction= {2}]";
    64
    65      /** The direction of the line as a normalized vector. */
    66      private final Vector2D.Unit direction;
    67
    68      /** The distance between the origin and the line. */
    69      private final double originOffset;
    70
    71      /** Simple constructor.
    72       * @param direction The direction of the line.
    73       * @param originOffset The signed distance between the line and the origin.
    74       * @param precision Precision context used to compare floating point numbers.
    75       */
    76      Line(final Vector2D.Unit direction, final double originOffset, final DoublePrecisionContext precision) {
    77          super(precision);
    78
    79          this.direction = direction;
    80          this.originOffset = originOffset;
    81      }
    82
    83      /** Get the angle of the line in radians with respect to the abscissa (+x) axis. The
    84       * returned angle is in the range {@code [0, 2pi)}.
    85       * @return the angle of the line with respect to the abscissa (+x) axis in the range
    86       *      {@code [0, 2pi)}
    87       */
    88      public double getAngle() {
    89          final double angle = Math.atan2(direction.getY(), direction.getX());
    90          return PlaneAngleRadians.normalizeBetweenZeroAndTwoPi(angle);
    91      }
    92
    93      /** Get the direction of the line.
    94       * @return the direction of the line
    95       */
    96      public Vector2D.Unit getDirection() {
    97          return direction;
    98      }
    99
    100     /** Get the offset direction of the line. This vector is perpendicular to the
    101      * line and points in the direction of positive offset values, meaning that
    102      * it points from the left side of the line to the right when one is looking
    103      * along the line direction.
    104      * @return the offset direction of the line.
    105      */
    106     public Vector2D getOffsetDirection() {
    107         return Vector2D.of(direction.getY(), -direction.getX());
    108     }
    109
    110     /** Get the line origin point. This is the projection of the 2D origin
    111      * onto the line and also serves as the origin for the 1D embedded subspace.
    112      * @return the origin point of the line
    113      */
    114     public Vector2D getOrigin() {
    115         return toSpace(Vector1D.ZERO);
    116     }
    117
    118     /** Get the signed distance from the origin of the 2D space to the
    119      * closest point on the line.
    120      * @return the signed distance from the origin to the line
    121      */
    122     public double getOriginOffset() {
    123         return originOffset;
    124     }
    125
    126     /** {@inheritDoc} */
    127     @Override
    128     public Line reverse() {
    129         return new Line(direction.negate(), -originOffset, getPrecision());
    130     }
    131
    132     /** {@inheritDoc} */
    133     @Override
    134     public Line transform(final Transform<Vector2D> transform) {
    135         final Vector2D origin = getOrigin();
    136
    137         final Vector2D tOrigin = transform.apply(origin);
    138         final Vector2D tOriginPlusDir = transform.apply(origin.add(getDirection()));
    139
    140         return Lines.fromPoints(tOrigin, tOriginPlusDir, getPrecision());
    141     }
    142
    143     /** Get an object containing the current line transformed by the argument along with a
    144      * 1D transform that can be applied to subspace points. The subspace transform transforms
    145      * subspace points such that their 2D location in the transformed line is the same as their
    146      * 2D location in the original line after the 2D transform is applied. For example, consider
    147      * the code below:
    148      * <pre>
    149      *      SubspaceTransform st = line.subspaceTransform(transform);
    150      *
    151      *      Vector1D subPt = Vector1D.of(1);
    152      *
    153      *      Vector2D a = transform.apply(line.toSpace(subPt)); // transform in 2D space
    154      *      Vector2D b = st.getLine().toSpace(st.getTransform().apply(subPt)); // transform in 1D space
    155      * </pre>
    156      * At the end of execution, the points {@code a} (which was transformed using the original
    157      * 2D transform) and {@code b} (which was transformed in 1D using the subspace transform)
    158      * are equivalent.
    159      *
    160      * @param transform the transform to apply to this instance
    161      * @return an object containing the transformed line along with a transform that can be applied
    162      *      to subspace points
    163      * @see #transform(Transform)
    164      */
    165     public SubspaceTransform subspaceTransform(final Transform<Vector2D> transform) {
    166         final Vector2D origin = getOrigin();
    167
    168         final Vector2D p1 = transform.apply(origin);
    169         final Vector2D p2 = transform.apply(origin.add(direction));
    170
    171         final Line tLine = Lines.fromPoints(p1, p2, getPrecision());
    172
    173         final Vector1D tSubspaceOrigin = tLine.toSubspace(p1);
    174         final Vector1D tSubspaceDirection = tSubspaceOrigin.vectorTo(tLine.toSubspace(p2));
    175
    176         final double translation = tSubspaceOrigin.getX();
    177         final double scale = tSubspaceDirection.getX();
    178
    179         final AffineTransformMatrix1D subspaceTransform = AffineTransformMatrix1D.of(scale, translation);
    180
    181         return new SubspaceTransform(tLine, subspaceTransform);
    182     }
    183
    184     /** {@inheritDoc} */
    185     @Override
    186     public LineConvexSubset span() {
    187         return Lines.span(this);
    188     }
    189
    190     /** Create a new line segment from the given 1D interval. The returned line
    191      * segment consists of all points between the two locations, regardless of the order the
    192      * arguments are given.
    193      * @param a first 1D location for the interval
    194      * @param b second 1D location for the interval
    195      * @return a new line segment on this line
    196      * @throws IllegalArgumentException if either of the locations is NaN or infinite
    197      * @see Lines#segmentFromLocations(Line, double, double)
    198      */
    199     public Segment segment(final double a, final double b) {
    200         return Lines.segmentFromLocations(this, a, b);
    201     }
    202
    203     /** Create a new line segment from two points. The returned segment represents all points on this line
    204      * between the projected locations of {@code a} and {@code b}. The points may be given in any order.
    205      * @param a first point
    206      * @param b second point
    207      * @return a new line segment on this line
    208      * @throws IllegalArgumentException if either point contains NaN or infinite coordinate values
    209      * @see Lines#segmentFromPoints(Line, Vector2D, Vector2D)
    210      */
    211     public Segment segment(final Vector2D a, final Vector2D b) {
    212         return Lines.segmentFromPoints(this, a, b);
    213     }
    214
    215     /** Create a new convex line subset that starts at infinity and continues along
    216      * the line up to the projection of the given end point.
    217      * @param endPoint point defining the end point of the line subset; the end point
    218      *      is equal to the projection of this point onto the line
    219      * @return a new, half-open line subset that ends at the given point
    220      * @throws IllegalArgumentException if any coordinate in {@code endPoint} is NaN or infinite
    221      * @see Lines#reverseRayFromPoint(Line, Vector2D)
    222      */
    223     public ReverseRay reverseRayTo(final Vector2D endPoint) {
    224         return Lines.reverseRayFromPoint(this, endPoint);
    225     }
    226
    227     /** Create a new convex line subset that starts at infinity and continues along
    228      * the line up to the given 1D location.
    229      * @param endLocation the 1D location of the end of the half-line
    230      * @return a new, half-open line subset that ends at the given 1D location
    231      * @throws IllegalArgumentException if {@code endLocation} is NaN or infinite
    232      * @see Lines#reverseRayFromLocation(Line, double)
    233      */
    234     public ReverseRay reverseRayTo(final double endLocation) {
    235         return Lines.reverseRayFromLocation(this, endLocation);
    236     }
    237
    238     /** Create a new ray instance that starts at the projection of the given point
    239      * and continues in the direction of the line to infinity.
    240      * @param startPoint point defining the start point of the ray; the start point
    241      *      is equal to the projection of this point onto the line
    242      * @return a ray starting at the projected point and extending along this line
    243      *      to infinity
    244      * @throws IllegalArgumentException if any coordinate in {@code startPoint} is NaN or infinite
    245      * @see Lines#rayFromPoint(Line, Vector2D)
    246      */
    247     public Ray rayFrom(final Vector2D startPoint) {
    248         return Lines.rayFromPoint(this, startPoint);
    249     }
    250
    251     /** Create a new ray instance that starts at the given 1D location and continues in
    252      * the direction of the line to infinity.
    253      * @param startLocation 1D location defining the start point of the ray
    254      * @return a ray starting at the given 1D location and extending along this line
    255      *      to infinity
    256      * @throws IllegalArgumentException if {@code startLocation} is NaN or infinite
    257      * @see Lines#rayFromLocation(Line, double)
    258      */
    259     public Ray rayFrom(final double startLocation) {
    260         return Lines.rayFromLocation(this, startLocation);
    261     }
    262
    263     /** Get the abscissa of the given point on the line. The abscissa represents
    264      * the distance the projection of the point on the line is from the line's
    265      * origin point (the point on the line closest to the origin of the
    266      * 2D space). Abscissa values increase in the direction of the line. This method
    267      * is exactly equivalent to {@link #toSubspace(Vector2D)} except that this method
    268      * returns a double instead of a {@link Vector1D}.
    269      * @param point point to compute the abscissa for
    270      * @return abscissa value of the point
    271      * @see #toSubspace(Vector2D)
    272      */
    273     public double abscissa(final Vector2D point) {
    274         return direction.dot(point);
    275     }
    276
    277     /** {@inheritDoc} */
    278     @Override
    279     public Vector1D toSubspace(final Vector2D point) {
    280         return Vector1D.of(abscissa(point));
    281     }
    282
    283     /** {@inheritDoc} */
    284     @Override
    285     public Vector2D toSpace(final Vector1D point) {
    286         return toSpace(point.getX());
    287     }
    288
    289     /** Convert the given abscissa value (1D location on the line)
    290      * into a 2D point.
    291      * @param abscissa value to convert
    292      * @return 2D point corresponding to the line abscissa value
    293      */
    294     public Vector2D toSpace(final double abscissa) {
    295         // The 2D coordinate is equal to the projection of the
    296         // 2D origin onto the line plus the direction multiplied
    297         // by the abscissa. We can combine everything into a single
    298         // step below given that the origin location is equal to
    299         // (-direction.y * originOffset, direction.x * originOffset).
    300         return Vector2D.of(
    301                     LinearCombination.value(abscissa, direction.getX(), -originOffset, direction.getY()),
    302                     LinearCombination.value(abscissa, direction.getY(), originOffset, direction.getX())
    303                 );
    304     }
    305
    306     /** Get the intersection point of the instance and another line.
    307      * @param other other line
    308      * @return intersection point of the instance and the other line
    309      *      or null if there is no unique intersection point (ie, the lines
    310      *      are parallel or coincident)
    311      */
    312     public Vector2D intersection(final Line other) {
    313         final double area = this.direction.signedArea(other.direction);
    314         if (getPrecision().eqZero(area)) {
    315             // lines are parallel
    316             return null;
    317         }
    318
    319         final double x = LinearCombination.value(
    320                 other.direction.getX(), originOffset,
    321                 -direction.getX(), other.originOffset) / area;
    322
    323         final double y = LinearCombination.value(
    324                 other.direction.getY(), originOffset,
    325                 -direction.getY(), other.originOffset) / area;
    326
    327         return Vector2D.of(x, y);
    328     }
    329
    330     /** Compute the angle in radians between this instance's direction and the direction
    331      * of the given line. The return value is in the range {@code [-pi, +pi)}. This method
    332      * always returns a value, even for parallel or coincident lines.
    333      * @param other other line
    334      * @return the angle required to rotate this line to point in the direction of
    335      *      the given line
    336      */
    337     public double angle(final Line other) {
    338         final double thisAngle = Math.atan2(direction.getY(), direction.getX());
    339         final double otherAngle = Math.atan2(other.direction.getY(), other.direction.getX());
    340
    341         return PlaneAngleRadians.normalizeBetweenMinusPiAndPi(otherAngle - thisAngle);
    342     }
    343
    344     /** {@inheritDoc} */
    345     @Override
    346     public Vector2D project(final Vector2D point) {
    347         return toSpace(toSubspace(point));
    348     }
    349
    350     /** {@inheritDoc} */
    351     @Override
    352     public double offset(final Vector2D point) {
    353         return originOffset - direction.signedArea(point);
    354     }
    355
    356     /** Get the offset (oriented distance) of the given line relative to this instance.
    357      * Since an infinite number of distances can be calculated between points on two
    358      * different lines, this method returns the value closest to zero. For intersecting
    359      * lines, this will simply be zero. For parallel lines, this will be the
    360      * perpendicular distance between the two lines, as a signed value.
    361      *
    362      * <p>The sign of the returned offset indicates the side of the line that the
    363      * argument lies on. The offset is positive if the line lies on the right side
    364      * of the instance and negative if the line lies on the left side
    365      * of the instance.</p>
    366      * @param line line to check
    367      * @return offset of the line
    368      * @see #distance(Line)
    369      */
    370     public double offset(final Line line) {
    371         if (isParallel(line)) {
    372             // since the lines are parallel, the offset between
    373             // them is simply the difference between their origin offsets,
    374             // with the second offset negated if the lines point if opposite
    375             // directions
    376             final double dot = direction.dot(line.direction);
    377             return originOffset - (Math.signum(dot) * line.originOffset);
    378         }
    379
    380         // the lines are not parallel, which means they intersect at some point
    381         return 0.0;
    382     }
    383
    384     /** {@inheritDoc} */
    385     @Override
    386     public boolean similarOrientation(final Hyperplane<Vector2D> other) {
    387         final Line otherLine = (Line) other;
    388         return direction.dot(otherLine.direction) >= 0.0;
    389     }
    390
    391     /** Get one point from the plane, relative to the coordinate system
    392      * of the line. Note that the direction of increasing offsets points
    393      * to the <em>right</em> of the line. This means that if one pictures
    394      * the line (abscissa) direction as equivalent to the +x-axis, the offset
    395      * direction will point along the -y axis.
    396      * @param abscissa desired abscissa (distance along the line) for the point
    397      * @param offset desired offset (distance perpendicular to the line) for the point
    398      * @return one point in the plane, with given abscissa and offset
    399      *      relative to the line
    400      */
    401     public Vector2D pointAt(final double abscissa, final double offset) {
    402         final double pointOffset = offset - originOffset;
    403         return Vector2D.of(LinearCombination.value(abscissa, direction.getX(),  pointOffset, direction.getY()),
    404                             LinearCombination.value(abscissa, direction.getY(), -pointOffset, direction.getX()));
    405     }
    406
    407     /** Check if the line contains a point.
    408      * @param p point to check
    409      * @return true if p belongs to the line
    410      */
    411     @Override
    412     public boolean contains(final Vector2D p) {
    413         return getPrecision().eqZero(offset(p));
    414     }
    415
    416     /** Check if this instance completely contains the other line.
    417      * This will be true if the two instances represent the same line,
    418      * with perhaps different directions.
    419      * @param line line to check
    420      * @return true if this instance contains all points in the given line
    421      */
    422     public boolean contains(final Line line) {
    423         return isParallel(line) && getPrecision().eqZero(offset(line));
    424     }
    425
    426     /** Compute the distance between the instance and a point.
    427      * <p>This is a shortcut for invoking Math.abs(getOffset(p)),
    428      * and provides consistency with what is in the
    429      * org.apache.commons.geometry.euclidean.threed.Line class.</p>
    430      *
    431      * @param p to check
    432      * @return distance between the instance and the point
    433      */
    434     public double distance(final Vector2D p) {
    435         return Math.abs(offset(p));
    436     }
    437
    438     /** Compute the shortest distance between this instance and
    439      * the given line. This value will simply be zero for intersecting
    440      * lines.
    441      * @param line line to compute the closest distance to
    442      * @return the shortest distance between this instance and the
    443      *      given line
    444      * @see #offset(Line)
    445      */
    446     public double distance(final Line line) {
    447         return Math.abs(offset(line));
    448     }
    449
    450     /** Check if the instance is parallel to another line.
    451      * @param line other line to check
    452      * @return true if the instance is parallel to the other line
    453      *  (they can have either the same or opposite orientations)
    454      */
    455     public boolean isParallel(final Line line) {
    456         final double area = direction.signedArea(line.direction);
    457         return getPrecision().eqZero(area);
    458     }
    459
    460     /** Return true if this instance should be considered equivalent to the argument, using the
    461      * given precision context for comparison. Instances are considered equivalent if they have
    462      * equivalent {@code origin} points and make similar angles with the x-axis.
    463      * @param other the point to compare with
    464      * @param precision precision context to use for the comparison
    465      * @return true if this instance should be considered equivalent to the argument
    466      * @see Vector2D#eq(Vector2D, DoublePrecisionContext)
    467      */
    468     public boolean eq(final Line other, final DoublePrecisionContext precision) {
    469         return getOrigin().eq(other.getOrigin(), precision) &&
    470                 precision.eq(getAngle(), other.getAngle());
    471     }
    472
    473     /** {@inheritDoc} */
    474     @Override
    475     public int hashCode() {
    476         final int prime = 167;
    477
    478         int result = 1;
    479         result = (prime * result) + Objects.hashCode(direction);
    480         result = (prime * result) + Double.hashCode(originOffset);
    481         result = (prime * result) + Objects.hashCode(getPrecision());
    482
    483         return result;
    484     }
    485
    486     /** {@inheritDoc} */
    487     @Override
    488     public boolean equals(final Object obj) {
    489         if (this == obj) {
    490             return true;
    491         } else if (!(obj instanceof Line)) {
    492             return false;
    493         }
    494
    495         final Line other = (Line) obj;
    496
    497         return Objects.equals(this.direction, other.direction) &&
    498                 Double.compare(this.originOffset, other.originOffset) == 0 &&
    499                 Objects.equals(this.getPrecision(), other.getPrecision());
    500     }
    501
    502     /** {@inheritDoc} */
    503     @Override
    504     public String toString() {
    505         return MessageFormat.format(TO_STRING_FORMAT,
    506                 getClass().getSimpleName(),
    507                 getOrigin(),
    508                 getDirection());
    509     }
    510
    511     /** Class containing a transformed line instance along with a subspace (1D) transform. The subspace
    512      * transform produces the equivalent of the 2D transform in 1D.
    513      */
    514     public static final class SubspaceTransform {
    515         /** The transformed line. */
    516         private final Line line;
    517
    518         /** The subspace transform instance. */
    519         private final AffineTransformMatrix1D transform;
    520
    521         /** Simple constructor.
    522          * @param line the transformed line
    523          * @param transform 1D transform that can be applied to subspace points
    524          */
    525         public SubspaceTransform(final Line line, final AffineTransformMatrix1D transform) {
    526             this.line = line;
    527             this.transform = transform;
    528         }
    529
    530         /** Get the transformed line instance.
    531          * @return the transformed line instance
    532          */
    533         public Line getLine() {
    534             return line;
    535         }
    536
    537         /** Get the 1D transform that can be applied to subspace points. This transform can be used
    538          * to perform the equivalent of the 2D transform in 1D space.
    539          * @return the subspace transform instance
    540          */
    541         public AffineTransformMatrix1D getTransform() {
    542             return transform;
    543         }
    544     }
    545 }