    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     */
    017    package org.apache.commons.math3.geometry.euclidean.twod;
    018
    019    import java.awt.geom.AffineTransform;
    020
    021    import org.apache.commons.math3.exception.MathIllegalArgumentException;
    022    import org.apache.commons.math3.exception.util.LocalizedFormats;
    023    import org.apache.commons.math3.geometry.Vector;
    024    import org.apache.commons.math3.geometry.euclidean.oned.Euclidean1D;
    025    import org.apache.commons.math3.geometry.euclidean.oned.IntervalsSet;
    026    import org.apache.commons.math3.geometry.euclidean.oned.OrientedPoint;
    027    import org.apache.commons.math3.geometry.euclidean.oned.Vector1D;
    028    import org.apache.commons.math3.geometry.partitioning.Embedding;
    029    import org.apache.commons.math3.geometry.partitioning.Hyperplane;
    030    import org.apache.commons.math3.geometry.partitioning.SubHyperplane;
    031    import org.apache.commons.math3.geometry.partitioning.Transform;
    032    import org.apache.commons.math3.util.FastMath;
    033    import org.apache.commons.math3.util.MathUtils;
    034
    035    /** This class represents an oriented line in the 2D plane.
    036
    037     * <p>An oriented line can be defined either by prolongating a line
    038     * segment between two points past these points, or by one point and
    039     * an angular direction (in trigonometric orientation).</p>
    040
    041     * <p>Since it is oriented the two half planes at its two sides are
    042     * unambiguously identified as a left half plane and a right half
    043     * plane. This can be used to identify the interior and the exterior
    044     * in a simple way by local properties only when part of a line is
    045     * used to define part of a polygon boundary.</p>
    046
    047     * <p>A line can also be used to completely define a reference frame
    048     * in the plane. It is sufficient to select one specific point in the
    049     * line (the orthogonal projection of the original reference frame on
    050     * the line) and to use the unit vector in the line direction and the
    051     * orthogonal vector oriented from left half plane to right half
    052     * plane. We define two coordinates by the process, the
    053     * <em>abscissa</em> along the line, and the <em>offset</em> across
    054     * the line. All points of the plane are uniquely identified by these
    055     * two coordinates. The line is the set of points at zero offset, the
    056     * left half plane is the set of points with negative offsets and the
    057     * right half plane is the set of points with positive offsets.</p>
    058
    059     * @version $Id: Line.java 1422195 2012-12-15 06:45:18Z psteitz $
    060     * @since 3.0
    061     */
    062    public class Line implements Hyperplane<Euclidean2D>, Embedding<Euclidean2D, Euclidean1D> {
    063
    064        /** Angle with respect to the abscissa axis. */
    065        private double angle;
    066
    067        /** Cosine of the line angle. */
    068        private double cos;
    069
    070        /** Sine of the line angle. */
    071        private double sin;
    072
    073        /** Offset of the frame origin. */
    074        private double originOffset;
    075
    076        /** Build a line from two points.
    077         * <p>The line is oriented from p1 to p2</p>
    078         * @param p1 first point
    079         * @param p2 second point
    080         */
    081        public Line(final Vector2D p1, final Vector2D p2) {
    082            reset(p1, p2);
    083        }
    084
    085        /** Build a line from a point and an angle.
    086         * @param p point belonging to the line
    087         * @param angle angle of the line with respect to abscissa axis
    088         */
    089        public Line(final Vector2D p, final double angle) {
    090            reset(p, angle);
    091        }
    092
    093        /** Build a line from its internal characteristics.
    094         * @param angle angle of the line with respect to abscissa axis
    095         * @param cos cosine of the angle
    096         * @param sin sine of the angle
    097         * @param originOffset offset of the origin
    098         */
    099        private Line(final double angle, final double cos, final double sin, final double originOffset) {
    100            this.angle        = angle;
    101            this.cos          = cos;
    102            this.sin          = sin;
    103            this.originOffset = originOffset;
    104        }
    105
    106        /** Copy constructor.
    107         * <p>The created instance is completely independent from the
    108         * original instance, it is a deep copy.</p>
    109         * @param line line to copy
    110         */
    111        public Line(final Line line) {
    112            angle        = MathUtils.normalizeAngle(line.angle, FastMath.PI);
    113            cos          = FastMath.cos(angle);
    114            sin          = FastMath.sin(angle);
    115            originOffset = line.originOffset;
    116        }
    117
    118        /** {@inheritDoc} */
    119        public Line copySelf() {
    120            return new Line(this);
    121        }
    122
    123        /** Reset the instance as if built from two points.
    124         * <p>The line is oriented from p1 to p2</p>
    125         * @param p1 first point
    126         * @param p2 second point
    127         */
    128        public void reset(final Vector2D p1, final Vector2D p2) {
    129            final double dx = p2.getX() - p1.getX();
    130            final double dy = p2.getY() - p1.getY();
    131            final double d = FastMath.hypot(dx, dy);
    132            if (d == 0.0) {
    133                angle        = 0.0;
    134                cos          = 1.0;
    135                sin          = 0.0;
    136                originOffset = p1.getY();
    137            } else {
    138                angle        = FastMath.PI + FastMath.atan2(-dy, -dx);
    139                cos          = FastMath.cos(angle);
    140                sin          = FastMath.sin(angle);
    141                originOffset = (p2.getX() * p1.getY() - p1.getX() * p2.getY()) / d;
    142            }
    143        }
    144
    145        /** Reset the instance as if built from a line and an angle.
    146         * @param p point belonging to the line
    147         * @param alpha angle of the line with respect to abscissa axis
    148         */
    149        public void reset(final Vector2D p, final double alpha) {
    150            this.angle   = MathUtils.normalizeAngle(alpha, FastMath.PI);
    151            cos          = FastMath.cos(this.angle);
    152            sin          = FastMath.sin(this.angle);
    153            originOffset = cos * p.getY() - sin * p.getX();
    154        }
    155
    156        /** Revert the instance.
    157         */
    158        public void revertSelf() {
    159            if (angle < FastMath.PI) {
    160                angle += FastMath.PI;
    161            } else {
    162                angle -= FastMath.PI;
    163            }
    164            cos          = -cos;
    165            sin          = -sin;
    166            originOffset = -originOffset;
    167        }
    168
    169        /** Get the reverse of the instance.
    170         * <p>Get a line with reversed orientation with respect to the
    171         * instance. A new object is built, the instance is untouched.</p>
    172         * @return a new line, with orientation opposite to the instance orientation
    173         */
    174        public Line getReverse() {
    175            return new Line((angle < FastMath.PI) ? (angle + FastMath.PI) : (angle - FastMath.PI),
    176                            -cos, -sin, -originOffset);
    177        }
    178
    179        /** {@inheritDoc} */
    180        public Vector1D toSubSpace(final Vector<Euclidean2D> point) {
    181            Vector2D p2 = (Vector2D) point;
    182            return new Vector1D(cos * p2.getX() + sin * p2.getY());
    183        }
    184
    185        /** {@inheritDoc} */
    186        public Vector2D toSpace(final Vector<Euclidean1D> point) {
    187            final double abscissa = ((Vector1D) point).getX();
    188            return new Vector2D(abscissa * cos - originOffset * sin,
    189                                abscissa * sin + originOffset * cos);
    190        }
    191
    192        /** Get the intersection point of the instance and another line.
    193         * @param other other line
    194         * @return intersection point of the instance and the other line
    195         * or null if there are no intersection points
    196         */
    197        public Vector2D intersection(final Line other) {
    198            final double d = sin * other.cos - other.sin * cos;
    199            if (FastMath.abs(d) < 1.0e-10) {
    200                return null;
    201            }
    202            return new Vector2D((cos * other.originOffset - other.cos * originOffset) / d,
    203                                (sin * other.originOffset - other.sin * originOffset) / d);
    204        }
    205
    206        /** {@inheritDoc} */
    207        public SubLine wholeHyperplane() {
    208            return new SubLine(this, new IntervalsSet());
    209        }
    210
    211        /** Build a region covering the whole space.
    212         * @return a region containing the instance (really a {@link
    213         * PolygonsSet PolygonsSet} instance)
    214         */
    215        public PolygonsSet wholeSpace() {
    216            return new PolygonsSet();
    217        }
    218
    219        /** Get the offset (oriented distance) of a parallel line.
    220         * <p>This method should be called only for parallel lines otherwise
    221         * the result is not meaningful.</p>
    222         * <p>The offset is 0 if both lines are the same, it is
    223         * positive if the line is on the right side of the instance and
    224         * negative if it is on the left side, according to its natural
    225         * orientation.</p>
    226         * @param line line to check
    227         * @return offset of the line
    228         */
    229        public double getOffset(final Line line) {
    230            return originOffset +
    231                   ((cos * line.cos + sin * line.sin > 0) ? -line.originOffset : line.originOffset);
    232        }
    233
    234        /** {@inheritDoc} */
    235        public double getOffset(final Vector<Euclidean2D> point) {
    236            Vector2D p2 = (Vector2D) point;
    237            return sin * p2.getX() - cos * p2.getY() + originOffset;
    238        }
    239
    240        /** {@inheritDoc} */
    241        public boolean sameOrientationAs(final Hyperplane<Euclidean2D> other) {
    242            final Line otherL = (Line) other;
    243            return (sin * otherL.sin + cos * otherL.cos) >= 0.0;
    244        }
    245
    246        /** Get one point from the plane.
    247         * @param abscissa desired abscissa for the point
    248         * @param offset desired offset for the point
    249         * @return one point in the plane, with given abscissa and offset
    250         * relative to the line
    251         */
    252        public Vector2D getPointAt(final Vector1D abscissa, final double offset) {
    253            final double x       = abscissa.getX();
    254            final double dOffset = offset - originOffset;
    255            return new Vector2D(x * cos + dOffset * sin, x * sin - dOffset * cos);
    256        }
    257
    258        /** Check if the line contains a point.
    259         * @param p point to check
    260         * @return true if p belongs to the line
    261         */
    262        public boolean contains(final Vector2D p) {
    263            return FastMath.abs(getOffset(p)) < 1.0e-10;
    264        }
    265
    266        /** Compute the distance between the instance and a point.
    267         * <p>This is a shortcut for invoking FastMath.abs(getOffset(p)),
    268         * and provides consistency with what is in the
    269         * org.apache.commons.math3.geometry.euclidean.threed.Line class.</p>
    270         *
    271         * @param p to check
    272         * @return distance between the instance and the point
    273         * @since 3.1
    274         */
    275        public double distance(final Vector2D p) {
    276            return FastMath.abs(getOffset(p));
    277        }
    278
    279        /** Check the instance is parallel to another line.
    280         * @param line other line to check
    281         * @return true if the instance is parallel to the other line
    282         * (they can have either the same or opposite orientations)
    283         */
    284        public boolean isParallelTo(final Line line) {
    285            return FastMath.abs(sin * line.cos - cos * line.sin) < 1.0e-10;
    286        }
    287
    288        /** Translate the line to force it passing by a point.
    289         * @param p point by which the line should pass
    290         */
    291        public void translateToPoint(final Vector2D p) {
    292            originOffset = cos * p.getY() - sin * p.getX();
    293        }
    294
    295        /** Get the angle of the line.
    296         * @return the angle of the line with respect to the abscissa axis
    297         */
    298        public double getAngle() {
    299            return MathUtils.normalizeAngle(angle, FastMath.PI);
    300        }
    301
    302        /** Set the angle of the line.
    303         * @param angle new angle of the line with respect to the abscissa axis
    304         */
    305        public void setAngle(final double angle) {
    306            this.angle = MathUtils.normalizeAngle(angle, FastMath.PI);
    307            cos        = FastMath.cos(this.angle);
    308            sin        = FastMath.sin(this.angle);
    309        }
    310
    311        /** Get the offset of the origin.
    312         * @return the offset of the origin
    313         */
    314        public double getOriginOffset() {
    315            return originOffset;
    316        }
    317
    318        /** Set the offset of the origin.
    319         * @param offset offset of the origin
    320         */
    321        public void setOriginOffset(final double offset) {
    322            originOffset = offset;
    323        }
    324
    325        /** Get a {@link org.apache.commons.math3.geometry.partitioning.Transform
    326         * Transform} embedding an affine transform.
    327         * @param transform affine transform to embed (must be inversible
    328         * otherwise the {@link
    329         * org.apache.commons.math3.geometry.partitioning.Transform#apply(Hyperplane)
    330         * apply(Hyperplane)} method would work only for some lines, and
    331         * fail for other ones)
    332         * @return a new transform that can be applied to either {@link
    333         * Vector2D Vector2D}, {@link Line Line} or {@link
    334         * org.apache.commons.math3.geometry.partitioning.SubHyperplane
    335         * SubHyperplane} instances
    336         * @exception MathIllegalArgumentException if the transform is non invertible
    337         */
    338        public static Transform<Euclidean2D, Euclidean1D> getTransform(final AffineTransform transform)
    339            throws MathIllegalArgumentException {
    340            return new LineTransform(transform);
    341        }
    342
    343        /** Class embedding an affine transform.
    344         * <p>This class is used in order to apply an affine transform to a
    345         * line. Using a specific object allow to perform some computations
    346         * on the transform only once even if the same transform is to be
    347         * applied to a large number of lines (for example to a large
    348         * polygon)./<p>
    349         */
    350        private static class LineTransform implements Transform<Euclidean2D, Euclidean1D> {
    351
    352            // CHECKSTYLE: stop JavadocVariable check
    353            private double cXX;
    354            private double cXY;
    355            private double cX1;
    356            private double cYX;
    357            private double cYY;
    358            private double cY1;
    359
    360            private double c1Y;
    361            private double c1X;
    362            private double c11;
    363            // CHECKSTYLE: resume JavadocVariable check
    364
    365            /** Build an affine line transform from a n {@code AffineTransform}.
    366             * @param transform transform to use (must be invertible otherwise
    367             * the {@link LineTransform#apply(Hyperplane)} method would work
    368             * only for some lines, and fail for other ones)
    369             * @exception MathIllegalArgumentException if the transform is non invertible
    370             */
    371            public LineTransform(final AffineTransform transform) throws MathIllegalArgumentException {
    372
    373                final double[] m = new double[6];
    374                transform.getMatrix(m);
    375                cXX = m[0];
    376                cXY = m[2];
    377                cX1 = m[4];
    378                cYX = m[1];
    379                cYY = m[3];
    380                cY1 = m[5];
    381
    382                c1Y = cXY * cY1 - cYY * cX1;
    383                c1X = cXX * cY1 - cYX * cX1;
    384                c11 = cXX * cYY - cYX * cXY;
    385
    386                if (FastMath.abs(c11) < 1.0e-20) {
    387                    throw new MathIllegalArgumentException(LocalizedFormats.NON_INVERTIBLE_TRANSFORM);
    388                }
    389
    390            }
    391
    392            /** {@inheritDoc} */
    393            public Vector2D apply(final Vector<Euclidean2D> point) {
    394                final Vector2D p2D = (Vector2D) point;
    395                final double  x   = p2D.getX();
    396                final double  y   = p2D.getY();
    397                return new Vector2D(cXX * x + cXY * y + cX1,
    398                                   cYX * x + cYY * y + cY1);
    399            }
    400
    401            /** {@inheritDoc} */
    402            public Line apply(final Hyperplane<Euclidean2D> hyperplane) {
    403                final Line   line    = (Line) hyperplane;
    404                final double rOffset = c1X * line.cos + c1Y * line.sin + c11 * line.originOffset;
    405                final double rCos    = cXX * line.cos + cXY * line.sin;
    406                final double rSin    = cYX * line.cos + cYY * line.sin;
    407                final double inv     = 1.0 / FastMath.sqrt(rSin * rSin + rCos * rCos);
    408                return new Line(FastMath.PI + FastMath.atan2(-rSin, -rCos),
    409                                inv * rCos, inv * rSin,
    410                                inv * rOffset);
    411            }
    412
    413            /** {@inheritDoc} */
    414            public SubHyperplane<Euclidean1D> apply(final SubHyperplane<Euclidean1D> sub,
    415                                                    final Hyperplane<Euclidean2D> original,
    416                                                    final Hyperplane<Euclidean2D> transformed) {
    417                final OrientedPoint op     = (OrientedPoint) sub.getHyperplane();
    418                final Line originalLine    = (Line) original;
    419                final Line transformedLine = (Line) transformed;
    420                final Vector1D newLoc =
    421                    transformedLine.toSubSpace(apply(originalLine.toSpace(op.getLocation())));
    422                return new OrientedPoint(newLoc, op.isDirect()).wholeHyperplane();
    423            }
    424
    425        }
    426
    427    }