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}