| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package org.apache.commons.geometry.euclidean.twod; |
| |
| import java.util.Objects; |
| |
| import org.apache.commons.geometry.core.Transform; |
| import org.apache.commons.geometry.core.exception.GeometryValueException; |
| import org.apache.commons.geometry.core.internal.Equivalency; |
| import org.apache.commons.geometry.core.partitioning.AbstractHyperplane; |
| import org.apache.commons.geometry.core.partitioning.EmbeddingHyperplane; |
| import org.apache.commons.geometry.core.partitioning.Hyperplane; |
| import org.apache.commons.geometry.core.precision.DoublePrecisionContext; |
| import org.apache.commons.geometry.euclidean.oned.AffineTransformMatrix1D; |
| import org.apache.commons.geometry.euclidean.oned.Interval; |
| import org.apache.commons.geometry.euclidean.oned.Vector1D; |
| import org.apache.commons.numbers.angle.PlaneAngleRadians; |
| import org.apache.commons.numbers.arrays.LinearCombination; |
| |
| /** This class represents an oriented line in the 2D plane. |
| |
| * <p>An oriented line can be defined either by extending a line |
| * segment between two points past these points, by specifying a |
| * point and a direction, or by specifying a point and an angle |
| * relative to the x-axis.</p> |
| |
| * <p>Since the line oriented, the two half planes on its sides are |
| * unambiguously identified as the left half plane and the right half |
| * plane. This can be used to identify the interior and the exterior |
| * in a simple way when a line is used to define a portion of a polygon |
| * boundary.</p> |
| |
| * <p>A line can also be used to completely define a reference frame |
| * in the plane. It is sufficient to select one specific point in the |
| * line (the orthogonal projection of the original reference frame on |
| * the line) and to use the unit vector in the line direction (see |
| * {@link #getDirection()} and the orthogonal vector oriented from the |
| * left half plane to the right half plane (see {@link #getOffsetDirection()}. |
| * We define two coordinates by the process, the <em>abscissa</em> along |
| * the line, and the <em>offset</em> across the line. All points of the |
| * plane are uniquely identified by these two coordinates. The line is |
| * the set of points at zero offset, the left half plane is the set of |
| * points with negative offsets and the right half plane is the set of |
| * points with positive offsets.</p> |
| */ |
| public final class Line extends AbstractHyperplane<Vector2D> |
| implements EmbeddingHyperplane<Vector2D, Vector1D>, Equivalency<Line> { |
| /** The direction of the line as a normalized vector. */ |
| private final Vector2D direction; |
| |
| /** The distance between the origin and the line. */ |
| private final double originOffset; |
| |
| /** Simple constructor. |
| * @param direction The direction of the line. |
| * @param originOffset The signed distance between the line and the origin. |
| * @param precision Precision context used to compare floating point numbers. |
| */ |
| private Line(final Vector2D direction, final double originOffset, final DoublePrecisionContext precision) { |
| super(precision); |
| |
| this.direction = direction; |
| this.originOffset = originOffset; |
| } |
| |
| /** Get the angle of the line in radians with respect to the abscissa (+x) axis. The |
| * returned angle is in the range {@code [0, 2pi)}. |
| * @return the angle of the line with respect to the abscissa (+x) axis in the range |
| * {@code [0, 2pi)} |
| */ |
| public double getAngle() { |
| final double angle = Math.atan2(direction.getY(), direction.getX()); |
| return PlaneAngleRadians.normalizeBetweenZeroAndTwoPi(angle); |
| } |
| |
| /** Get the direction of the line. |
| * @return the direction of the line |
| */ |
| public Vector2D getDirection() { |
| return direction; |
| } |
| |
| /** Get the offset direction of the line. This vector is perpendicular to the |
| * line and points in the direction of positive offset values, meaning that |
| * it points from the left side of the line to the right when one is looking |
| * along the line direction. |
| * @return the offset direction of the line. |
| */ |
| public Vector2D getOffsetDirection() { |
| return Vector2D.of(direction.getY(), -direction.getX()); |
| } |
| |
| /** Get the line origin point. This is the projection of the 2D origin |
| * onto the line and also serves as the origin for the 1D embedded subspace. |
| * @return the origin point of the line |
| */ |
| public Vector2D getOrigin() { |
| return toSpace(Vector1D.ZERO); |
| } |
| |
| /** Get the signed distance from the origin of the 2D space to the |
| * closest point on the line. |
| * @return the signed distance from the origin to the line |
| */ |
| public double getOriginOffset() { |
| return originOffset; |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public Line reverse() { |
| return new Line(direction.negate(), -originOffset, getPrecision()); |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public Line transform(final Transform<Vector2D> transform) { |
| final Vector2D origin = getOrigin(); |
| |
| final Vector2D tOrigin = transform.apply(origin); |
| final Vector2D tOriginPlusDir = transform.apply(origin.add(getDirection())); |
| |
| return fromPoints(tOrigin, tOriginPlusDir, getPrecision()); |
| } |
| |
| /** Get an object containing the current line transformed by the argument along with a |
| * 1D transform that can be applied to subspace points. The subspace transform transforms |
| * subspace points such that their 2D location in the transformed line is the same as their |
| * 2D location in the original line after the 2D transform is applied. For example, consider |
| * the code below: |
| * <pre> |
| * SubspaceTransform st = line.subspaceTransform(transform); |
| * |
| * Vector1D subPt = Vector1D.of(1); |
| * |
| * Vector2D a = transform.apply(line.toSpace(subPt)); // transform in 2D space |
| * Vector2D b = st.getLine().toSpace(st.getTransform().apply(subPt)); // transform in 1D space |
| * </pre> |
| * At the end of execution, the points {@code a} (which was transformed using the original |
| * 2D transform) and {@code b} (which was transformed in 1D using the subspace transform) |
| * are equivalent. |
| * |
| * @param transform the transform to apply to this instance |
| * @return an object containing the transformed line along with a transform that can be applied |
| * to subspace points |
| * @see #transform(Transform) |
| */ |
| public SubspaceTransform subspaceTransform(final Transform<Vector2D> transform) { |
| final Vector2D origin = getOrigin(); |
| |
| final Vector2D p1 = transform.apply(origin); |
| final Vector2D p2 = transform.apply(origin.add(direction)); |
| |
| final Line tLine = Line.fromPoints(p1, p2, getPrecision()); |
| |
| final Vector1D tSubspaceOrigin = tLine.toSubspace(p1); |
| final Vector1D tSubspaceDirection = tSubspaceOrigin.vectorTo(tLine.toSubspace(p2)); |
| |
| final double translation = tSubspaceOrigin.getX(); |
| final double scale = tSubspaceDirection.getX(); |
| |
| final AffineTransformMatrix1D subspaceTransform = AffineTransformMatrix1D.of(scale, translation); |
| |
| return new SubspaceTransform(tLine, subspaceTransform); |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public Segment span() { |
| return segment(Interval.full()); |
| } |
| |
| /** Create a new line segment from the given interval. |
| * @param interval interval representing the 1D region for the line segment |
| * @return a new line segment on this line |
| */ |
| public Segment segment(final Interval interval) { |
| return Segment.fromInterval(this, interval); |
| } |
| |
| /** Create a new line segment from the given interval. |
| * @param a first 1D location for the interval |
| * @param b second 1D location for the interval |
| * @return a new line segment on this line |
| */ |
| public Segment segment(final double a, final double b) { |
| return Segment.fromInterval(this, a, b); |
| } |
| |
| /** Create a new line segment between the projections of the two |
| * given points onto this line. |
| * @param a first point |
| * @param b second point |
| * @return a new line segment on this line |
| */ |
| public Segment segment(final Vector2D a, final Vector2D b) { |
| return Segment.fromInterval(this, toSubspace(a), toSubspace(b)); |
| } |
| |
| /** Create a new line segment that starts at infinity and continues along |
| * the line up to the projection of the given point. |
| * @param pt point defining the end point of the line segment; the end point |
| * is equal to the projection of this point onto the line |
| * @return a new, half-open line segment |
| */ |
| public Segment segmentTo(final Vector2D pt) { |
| return segment(Double.NEGATIVE_INFINITY, toSubspace(pt).getX()); |
| } |
| |
| /** Create a new line segment that starts at the projection of the given point |
| * and continues in the direction of the line to infinity, similar to a ray. |
| * @param pt point defining the start point of the line segment; the start point |
| * is equal to the projection of this point onto the line |
| * @return a new, half-open line segment |
| */ |
| public Segment segmentFrom(final Vector2D pt) { |
| return segment(toSubspace(pt).getX(), Double.POSITIVE_INFINITY); |
| } |
| |
| /** Create a new, empty subline based on this line. |
| * @return a new, empty subline based on this line |
| */ |
| public SubLine subline() { |
| return new SubLine(this); |
| } |
| |
| /** Get the abscissa of the given point on the line. The abscissa represents |
| * the distance the projection of the point on the line is from the line's |
| * origin point (the point on the line closest to the origin of the |
| * 2D space). Abscissa values increase in the direction of the line. This method |
| * is exactly equivalent to {@link #toSubspace(Vector2D)} except that this method |
| * returns a double instead of a {@link Vector1D}. |
| * @param point point to compute the abscissa for |
| * @return abscissa value of the point |
| * @see #toSubspace(Vector2D) |
| */ |
| public double abscissa(final Vector2D point) { |
| return direction.dot(point); |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public Vector1D toSubspace(final Vector2D point) { |
| return Vector1D.of(abscissa(point)); |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public Vector2D toSpace(final Vector1D point) { |
| return toSpace(point.getX()); |
| } |
| |
| /** Convert the given abscissa value (1D location on the line) |
| * into a 2D point. |
| * @param abscissa value to convert |
| * @return 2D point corresponding to the line abscissa value |
| */ |
| public Vector2D toSpace(final double abscissa) { |
| // The 2D coordinate is equal to the projection of the |
| // 2D origin onto the line plus the direction multiplied |
| // by the abscissa. We can combine everything into a single |
| // step below given that the origin location is equal to |
| // (-direction.y * originOffset, direction.x * originOffset). |
| return Vector2D.of( |
| LinearCombination.value(abscissa, direction.getX(), -originOffset, direction.getY()), |
| LinearCombination.value(abscissa, direction.getY(), originOffset, direction.getX()) |
| ); |
| } |
| |
| /** Get the intersection point of the instance and another line. |
| * @param other other line |
| * @return intersection point of the instance and the other line |
| * or null if there is no unique intersection point (ie, the lines |
| * are parallel or coincident) |
| */ |
| public Vector2D intersection(final Line other) { |
| final double area = this.direction.signedArea(other.direction); |
| if (getPrecision().eqZero(area)) { |
| // lines are parallel |
| return null; |
| } |
| |
| final double x = LinearCombination.value( |
| other.direction.getX(), originOffset, |
| -direction.getX(), other.originOffset) / area; |
| |
| final double y = LinearCombination.value( |
| other.direction.getY(), originOffset, |
| -direction.getY(), other.originOffset) / area; |
| |
| return Vector2D.of(x, y); |
| } |
| |
| /** Compute the angle in radians between this instance's direction and the direction |
| * of the given line. The return value is in the range {@code [-pi, +pi)}. This method |
| * always returns a value, even for parallel or coincident lines. |
| * @param other other line |
| * @return the angle required to rotate this line to point in the direction of |
| * the given line |
| */ |
| public double angle(final Line other) { |
| final double thisAngle = Math.atan2(direction.getY(), direction.getX()); |
| final double otherAngle = Math.atan2(other.direction.getY(), other.direction.getX()); |
| |
| return PlaneAngleRadians.normalizeBetweenMinusPiAndPi(otherAngle - thisAngle); |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public Vector2D project(final Vector2D point) { |
| return toSpace(toSubspace(point)); |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public double offset(final Vector2D point) { |
| return originOffset - direction.signedArea(point); |
| } |
| |
| /** Get the offset (oriented distance) of the given line relative to this instance. |
| * Since an infinite number of distances can be calculated between points on two |
| * different lines, this method returns the value closest to zero. For intersecting |
| * lines, this will simply be zero. For parallel lines, this will be the |
| * perpendicular distance between the two lines, as a signed value. |
| * |
| * <p>The sign of the returned offset indicates the side of the line that the |
| * argument lies on. The offset is positive if the line lies on the right side |
| * of the instance and negative if the line lies on the left side |
| * of the instance.</p> |
| * @param line line to check |
| * @return offset of the line |
| * @see #distance(Line) |
| */ |
| public double offset(final Line line) { |
| if (isParallel(line)) { |
| // since the lines are parallel, the offset between |
| // them is simply the difference between their origin offsets, |
| // with the second offset negated if the lines point if opposite |
| // directions |
| final double dot = direction.dot(line.direction); |
| return originOffset - (Math.signum(dot) * line.originOffset); |
| } |
| |
| // the lines are not parallel, which means they intersect at some point |
| return 0.0; |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public boolean similarOrientation(final Hyperplane<Vector2D> other) { |
| final Line otherLine = (Line) other; |
| return direction.dot(otherLine.direction) >= 0.0; |
| } |
| |
| /** Get one point from the plane, relative to the coordinate system |
| * of the line. Note that the direction of increasing offsets points |
| * to the <em>right</em> of the line. This means that if one pictures |
| * the line (abscissa) direction as equivalent to the +x-axis, the offset |
| * direction will point along the -y axis. |
| * @param abscissa desired abscissa (distance along the line) for the point |
| * @param offset desired offset (distance perpendicular to the line) for the point |
| * @return one point in the plane, with given abscissa and offset |
| * relative to the line |
| */ |
| public Vector2D pointAt(final double abscissa, final double offset) { |
| final double pointOffset = offset - originOffset; |
| return Vector2D.of(LinearCombination.value(abscissa, direction.getX(), pointOffset, direction.getY()), |
| LinearCombination.value(abscissa, direction.getY(), -pointOffset, direction.getX())); |
| } |
| |
| /** Check if the line contains a point. |
| * @param p point to check |
| * @return true if p belongs to the line |
| */ |
| @Override |
| public boolean contains(final Vector2D p) { |
| return getPrecision().eqZero(offset(p)); |
| } |
| |
| /** Check if this instance completely contains the other line. |
| * This will be true if the two instances represent the same line, |
| * with perhaps different directions. |
| * @param line line to check |
| * @return true if this instance contains all points in the given line |
| */ |
| public boolean contains(final Line line) { |
| return isParallel(line) && getPrecision().eqZero(offset(line)); |
| } |
| |
| /** Compute the distance between the instance and a point. |
| * <p>This is a shortcut for invoking Math.abs(getOffset(p)), |
| * and provides consistency with what is in the |
| * org.apache.commons.geometry.euclidean.threed.Line class.</p> |
| * |
| * @param p to check |
| * @return distance between the instance and the point |
| */ |
| public double distance(final Vector2D p) { |
| return Math.abs(offset(p)); |
| } |
| |
| /** Compute the shortest distance between this instance and |
| * the given line. This value will simply be zero for intersecting |
| * lines. |
| * @param line line to compute the closest distance to |
| * @return the shortest distance between this instance and the |
| * given line |
| * @see #offset(Line) |
| */ |
| public double distance(final Line line) { |
| return Math.abs(offset(line)); |
| } |
| |
| /** Check if the instance is parallel to another line. |
| * @param line other line to check |
| * @return true if the instance is parallel to the other line |
| * (they can have either the same or opposite orientations) |
| */ |
| public boolean isParallel(final Line line) { |
| final double area = direction.signedArea(line.direction); |
| return getPrecision().eqZero(area); |
| } |
| |
| /** {@inheritDoc} |
| * |
| * <p>Instances are considered equivalent if they |
| * <ul> |
| * <li>contain equal {@link DoublePrecisionContext precision contexts},</li> |
| * <li>have equivalent locations (as evaluated by the precision context), and</li> |
| * <li>point in the same direction (as evaluated by the precision context)</li> |
| * </ul> |
| * @param other the point to compare with |
| * @return true if this instance should be considered equivalent to the argument |
| */ |
| @Override |
| public boolean eq(final Line other) { |
| if (this == other) { |
| return true; |
| } |
| |
| final DoublePrecisionContext precision = getPrecision(); |
| |
| return precision.equals(other.getPrecision()) && |
| getOrigin().eq(other.getOrigin(), precision) && |
| precision.eq(getAngle(), other.getAngle()); |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public int hashCode() { |
| final int prime = 167; |
| |
| int result = 1; |
| result = (prime * result) + Objects.hashCode(direction); |
| result = (prime * result) + Double.hashCode(originOffset); |
| result = (prime * result) + Objects.hashCode(getPrecision()); |
| |
| return result; |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public boolean equals(Object obj) { |
| if (this == obj) { |
| return true; |
| } else if (!(obj instanceof Line)) { |
| return false; |
| } |
| |
| Line other = (Line) obj; |
| |
| return Objects.equals(this.direction, other.direction) && |
| Double.compare(this.originOffset, other.originOffset) == 0 && |
| Objects.equals(this.getPrecision(), other.getPrecision()); |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public String toString() { |
| final StringBuilder sb = new StringBuilder(); |
| sb.append(getClass().getSimpleName()) |
| .append("[origin= ") |
| .append(getOrigin()) |
| .append(", direction= ") |
| .append(direction) |
| .append(']'); |
| |
| return sb.toString(); |
| } |
| |
| /** Create a line from two points lying on the line. The line points in the direction |
| * from {@code p1} to {@code p2}. |
| * @param p1 first point |
| * @param p2 second point |
| * @param precision precision context used to compare floating point values |
| * @return new line containing {@code p1} and {@code p2} and pointing in the direction |
| * from {@code p1} to {@code p2} |
| * @throws GeometryValueException If the vector between {@code p1} and {@code p2} has zero length, |
| * as evaluated by the given precision context |
| */ |
| public static Line fromPoints(final Vector2D p1, final Vector2D p2, final DoublePrecisionContext precision) { |
| return fromPointAndDirection(p1, p1.vectorTo(p2), precision); |
| } |
| |
| /** Create a line from a point and direction. |
| * @param pt point belonging to the line |
| * @param dir the direction of the line |
| * @param precision precision context used to compare floating point values |
| * @return new line containing {@code pt} and pointing in direction {@code dir} |
| * @throws GeometryValueException If {@code dir} has zero length, as evaluated by the |
| * given precision context |
| */ |
| public static Line fromPointAndDirection(final Vector2D pt, final Vector2D dir, |
| final DoublePrecisionContext precision) { |
| if (dir.isZero(precision)) { |
| throw new GeometryValueException("Line direction cannot be zero"); |
| } |
| |
| final Vector2D normalizedDir = dir.normalize(); |
| final double originOffset = normalizedDir.signedArea(pt); |
| |
| return new Line(normalizedDir, originOffset, precision); |
| } |
| |
| /** Create a line from a point lying on the line and an angle relative to the abscissa (x) axis. Note that the |
| * line does not need to intersect the x-axis; the given angle is simply relative to it. |
| * @param pt point belonging to the line |
| * @param angle angle of the line with respect to abscissa (x) axis, in radians |
| * @param precision precision context used to compare floating point values |
| * @return new line containing {@code pt} and forming the given angle with the |
| * abscissa (x) axis. |
| */ |
| public static Line fromPointAndAngle(final Vector2D pt, final double angle, |
| final DoublePrecisionContext precision) { |
| final Vector2D.Unit dir = Vector2D.Unit.from(Math.cos(angle), Math.sin(angle)); |
| return fromPointAndDirection(pt, dir, precision); |
| } |
| |
| /** Class containing a transformed line instance along with a subspace (1D) transform. The subspace |
| * transform produces the equivalent of the 2D transform in 1D. |
| */ |
| public static final class SubspaceTransform { |
| /** The transformed line. */ |
| private final Line line; |
| |
| /** The subspace transform instance. */ |
| private final AffineTransformMatrix1D transform; |
| |
| /** Simple constructor. |
| * @param line the transformed line |
| * @param transform 1D transform that can be applied to subspace points |
| */ |
| public SubspaceTransform(final Line line, final AffineTransformMatrix1D transform) { |
| this.line = line; |
| this.transform = transform; |
| } |
| |
| /** Get the transformed line instance. |
| * @return the transformed line instance |
| */ |
| public Line getLine() { |
| return line; |
| } |
| |
| /** Get the 1D transform that can be applied to subspace points. This transform can be used |
| * to perform the equivalent of the 2D transform in 1D space. |
| * @return the subspace transform instance |
| */ |
| public AffineTransformMatrix1D getTransform() { |
| return transform; |
| } |
| } |
| } |