001/**
002 * Copyright (c) 2011, The University of Southampton and the individual contributors.
003 * All rights reserved.
004 *
005 * Redistribution and use in source and binary forms, with or without modification,
006 * are permitted provided that the following conditions are met:
007 *
008 *   *  Redistributions of source code must retain the above copyright notice,
009 *      this list of conditions and the following disclaimer.
010 *
011 *   *  Redistributions in binary form must reproduce the above copyright notice,
012 *      this list of conditions and the following disclaimer in the documentation
013 *      and/or other materials provided with the distribution.
014 *
015 *   *  Neither the name of the University of Southampton nor the names of its
016 *      contributors may be used to endorse or promote products derived from this
017 *      software without specific prior written permission.
018 *
019 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
020 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
021 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
022 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
023 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
024 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
025 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
026 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
027 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
028 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029 */
030package org.openimaj.math.geometry.line;
031
032import java.util.Arrays;
033import java.util.Iterator;
034
035import org.openimaj.math.geometry.path.Path2d;
036import org.openimaj.math.geometry.path.Polyline;
037import org.openimaj.math.geometry.point.Point2d;
038import org.openimaj.math.geometry.point.Point2dImpl;
039import org.openimaj.math.geometry.shape.Rectangle;
040
041import Jama.Matrix;
042
043/**
044 * A line in two-dimensional space.
045 *
046 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
047 * @author David Dupplaw (dpd@ecs.soton.ac.uk)
048 */
049public class Line2d implements Path2d, Cloneable {
050        /**
051         * Start point of line
052         */
053        public Point2d begin;
054
055        /**
056         * End point of line
057         */
058        public Point2d end;
059
060        /**
061         * Construct a line
062         */
063        public Line2d() {
064        }
065
066        /**
067         * Construct a line
068         *
069         * @param begin
070         *            start point
071         * @param end
072         *            end point
073         */
074        public Line2d(Point2d begin, Point2d end) {
075                this.begin = begin;
076                this.end = end;
077        }
078
079        /**
080         * Construct a line
081         *
082         * @param x1
083         *            x-ordinate of start point
084         * @param y1
085         *            y-ordinate of start point
086         * @param x2
087         *            x-ordinate of end point
088         * @param y2
089         *            y-ordinate of end point
090         *
091         */
092        public Line2d(float x1, float y1, float x2, float y2) {
093                this.begin = new Point2dImpl(x1, y1);
094                this.end = new Point2dImpl(x2, y2);
095        }
096
097        /**
098         * Set the start point
099         *
100         * @param begin
101         *            start point
102         */
103        public void setBeginPoint(Point2d begin) {
104                this.begin = begin;
105        }
106
107        /**
108         * Set the end point
109         *
110         * @param end
111         *            end point
112         */
113        public void setEndPoint(Point2d end) {
114                this.end = end;
115        }
116
117        /**
118         * Get the start point
119         *
120         * @return the start point
121         */
122        public Point2d getBeginPoint() {
123                return begin;
124        }
125
126        /**
127         * Get the end point
128         *
129         * @return The end point
130         */
131        public Point2d getEndPoint() {
132                return end;
133        }
134
135        /**
136         * Get the end point
137         *
138         * @return the end point
139         */
140        public Point2d setEndPoint() {
141                return end;
142        }
143
144        /**
145         * The type of a result of a line intersection
146         *
147         * @author David Dupplaw (dpd@ecs.soton.ac.uk)
148         */
149        static public enum IntersectionType
150        {
151                /**
152                 * Intersecting line (lines that cross)
153                 */
154                INTERSECTING,
155                /**
156                 * Parallel line
157                 */
158                PARALLEL,
159                /**
160                 * Co-incident line (on top of each other)
161                 */
162                COINCIDENT,
163                /**
164                 * non-intersecting line
165                 */
166                NOT_INTERESECTING
167        }
168
169        /**
170         * The result of a line intersection.
171         *
172         * @author David Dupplaw (dpd@ecs.soton.ac.uk)
173         */
174        static public class IntersectionResult
175        {
176                /**
177                 * The type of intersection
178                 */
179                public IntersectionType type;
180
181                /**
182                 * The point at which the lines intersect (if the type is INTERSECTING)
183                 */
184                public Point2d intersectionPoint;
185
186                /**
187                 * Construct the IntersectionResult with the given type
188                 *
189                 * @param type
190                 *            the type
191                 */
192                public IntersectionResult(IntersectionType type) {
193                        this.type = type;
194                }
195
196                /**
197                 * Construct the IntersectionResult with the given intersection point
198                 *
199                 * @param point
200                 *            the intersection point
201                 */
202                public IntersectionResult(Point2d point) {
203                        this.type = IntersectionType.INTERSECTING;
204                        this.intersectionPoint = point;
205                }
206        }
207
208        /**
209         * Calculates the intersection point of this line and another line
210         *
211         * @param otherLine
212         *            The other line segment
213         * @return a {@link IntersectionResult}
214         * @see "http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/"
215         */
216        public IntersectionResult getIntersection(Line2d otherLine) {
217                final double denom = ((otherLine.end.getY() - otherLine.begin.getY()) * (end.getX() - begin.getX())) -
218                                ((otherLine.end.getX() - otherLine.begin.getX()) * (end.getY() - begin.getY()));
219
220                final double numea = ((otherLine.end.getX() - otherLine.begin.getX()) * (begin.getY() - otherLine.begin.getY())) -
221                                ((otherLine.end.getY() - otherLine.begin.getY()) * (begin.getX() - otherLine.begin.getX()));
222
223                final double numeb = ((end.getX() - begin.getX()) * (begin.getY() - otherLine.begin.getY())) -
224                                ((end.getY() - begin.getY()) * (begin.getX() - otherLine.begin.getX()));
225
226                if (denom == 0.0)
227                {
228                        if (numea == 0.0 && numeb == 0.0)
229                        {
230                                return new IntersectionResult(IntersectionType.COINCIDENT);
231                        }
232
233                        return new IntersectionResult(IntersectionType.PARALLEL);
234                }
235
236                final double ua = numea / denom;
237                final double ub = numeb / denom;
238
239                if (ua >= 0.0 && ua <= 1.0 && ub >= 0.0 && ub <= 1.0)
240                {
241                        // Get the intersection point.
242                        final double intX = begin.getX() + ua * (end.getX() - begin.getX());
243                        final double intY = begin.getY() + ua * (end.getY() - begin.getY());
244
245                        return new IntersectionResult(new Point2dImpl((float) intX, (float) intY));
246                }
247
248                return new IntersectionResult(IntersectionType.NOT_INTERESECTING);
249        }
250
251        /**
252         * Reflects a point around a this line.
253         *
254         * @param pointToReflect
255         *            The point to reflect
256         * @return The reflected point
257         *
258         * @see "http://algorithmist.wordpress.com/2009/09/15/reflecting-a-point-about-a-line/"
259         */
260        public Point2d reflectAroundLine(Point2d pointToReflect) {
261                double nx = end.getX() - begin.getX();
262                double ny = end.getY() - begin.getY();
263                final double d = Math.sqrt(nx * nx + ny * ny);
264                nx /= d;
265                ny /= d;
266
267                final double px = pointToReflect.getX() - begin.getX();
268                final double py = pointToReflect.getY() - begin.getY();
269                final double w = nx * px + ny * py;
270                final double rx = 2 * begin.getX() - pointToReflect.getX() + 2 * w * nx;
271                final double ry = 2 * begin.getY() - pointToReflect.getY() + 2 * w * ny;
272                return new Point2dImpl((float) rx, (float) ry);
273        }
274
275        float CalcY(float xval, float x0, float y0, float x1, float y1)
276        {
277                if (x1 == x0)
278                        return Float.NaN;
279                return y0 + (xval - x0) * (y1 - y0) / (x1 - x0);
280        }
281
282        float CalcX(float yval, float x0, float y0, float x1, float y1)
283        {
284                if (y1 == y0)
285                        return Float.NaN;
286                return x0 + (yval - y0) * (x1 - x0) / (y1 - y0);
287        }
288
289        /**
290         * Given a rectangle, return the line that actually fits inside the
291         * rectangle for this line
292         *
293         * @param r
294         *            the bounds
295         * @return the line
296         */
297        public Line2d lineWithinSquare(Rectangle r)
298        {
299                final boolean beginInside = r.isInside(begin);
300                final int nInside = (beginInside ? 1 : 0) + (r.isInside(end) ? 1 : 0);
301                if (nInside == 2) {
302                        return new Line2d(this.begin.copy(), this.end.copy());
303                }
304                Point2d begin = null;
305                Point2d end = null;
306
307                final float x0 = this.begin.getX();
308                final float y0 = this.begin.getY();
309                final float x1 = this.end.getX();
310                final float y1 = this.end.getY();
311                final float bottom = r.y + r.height;
312                final float top = r.y;
313                final float left = r.x;
314                final float right = r.x + r.width;
315                final float bottomIntersect = CalcX(bottom, x0, y0, x1, y1);
316                final float topIntersect = CalcX(top, x0, y0, x1, y1);
317                final float leftIntersect = CalcY(left, x0, y0, x1, y1);
318                final float rightIntersect = CalcY(right, x0, y0, x1, y1);
319                if (bottomIntersect <= right && bottomIntersect >= left) {
320                        if (end == null)
321                                end = new Point2dImpl(bottomIntersect, bottom);
322                }
323                if (topIntersect <= right && topIntersect >= left) {
324                        if (end == null)
325                                end = new Point2dImpl(topIntersect, top);
326                        else if (begin == null) {
327                                begin = new Point2dImpl(topIntersect, top);
328                                if (end.equals(begin))
329                                        end = null;
330                        }
331
332                }
333
334                if (leftIntersect >= top && leftIntersect <= bottom) {
335                        if (end == null)
336                                end = new Point2dImpl(left, leftIntersect);
337                        else if (begin == null) {
338                                begin = new Point2dImpl(left, leftIntersect);
339                                if (end.equals(begin))
340                                        end = null;
341                        }
342                }
343                if (rightIntersect >= top && rightIntersect <= bottom) {
344                        if (end == null)
345                                end = new Point2dImpl(right, rightIntersect);
346                        else if (begin == null) {
347                                begin = new Point2dImpl(right, rightIntersect);
348                                if (end.equals(begin))
349                                        end = null;
350                        }
351                }
352                if (end == null || begin == null)
353                        return null;
354
355                if (nInside == 0)
356                {
357                        if (distance(this.end, end) < distance(this.end, begin) == distance(this.begin, end) < distance(this.begin,
358                                        begin))
359                                return null;
360                        else
361                                return new Line2d(begin, end);
362                }
363
364                // Complex case
365                if (beginInside) {
366                        if (distance(this.end, end) < distance(this.end, begin))
367                                return new Line2d(this.begin, end);
368                        else
369                                return new Line2d(this.begin, begin);
370                }
371                else {
372                        if (distance(this.begin, begin) < distance(this.begin, end))
373                                return new Line2d(begin, this.end);
374                        else
375                                return new Line2d(end, this.end);
376                }
377        }
378
379        /**
380         * Get the Euclidean distance between two points
381         *
382         * @param p1
383         *            the first point
384         * @param p2
385         *            the second point
386         * @return the distance
387         */
388        public static double distance(Point2d p1, Point2d p2) {
389                return Math.sqrt((p1.getX() - p2.getX()) * (p1.getX() - p2.getX()) + (p1.getY() - p2.getY())
390                                * (p1.getY() - p2.getY()));
391        }
392
393        /**
394         * Get the Euclidean distance between two points
395         *
396         * @param p1x
397         *            the first point
398         * @param p1y
399         *            the first point
400         * @param p2x
401         *            the second point
402         * @param p2y
403         *            the first point
404         * @return the distance
405         */
406        public static double distance(float p1x, float p1y, float p2x, float p2y) {
407                return Math.sqrt((p1x - p2x) * (p1x - p2x) + (p1y - p2y) * (p1y - p2y));
408        }
409
410        /**
411         * Create a line of a given length that starts at a point and has a given
412         * angle.
413         *
414         * @param x1
415         *            x-ordinate of starting point
416         * @param y1
417         *            y-ordinate of starting point
418         * @param theta
419         *            angle in radians
420         * @param length
421         *            line length
422         * @return the line
423         */
424        public static Line2d lineFromRotation(int x1, int y1, double theta, int length) {
425                final int x2 = x1 + (int) Math.round(Math.cos(theta) * length);
426                final int y2 = y1 + (int) Math.round(Math.sin(theta) * length);
427
428                return new Line2d(new Point2dImpl(x1, y1), new Point2dImpl(x2, y2));
429        }
430
431        /**
432         * @return The length of the line.
433         */
434        @Override
435        public double calculateLength() {
436                return distance(begin, end);
437        }
438
439        /**
440         * Returns the angle (radians) this line makes with a horizontal line
441         *
442         * @return the angle this line makes with a horizontal line
443         */
444        public double calculateHorizontalAngle()
445        {
446                return Math.atan((end.getY() - begin.getY()) / (end.getX() - begin.getX()));
447        }
448
449        /**
450         * Returns the angle (radians) this line makes with a vertical line
451         *
452         * @return the angle this line makes with a vertical line
453         */
454        public double calculateVerticalAngle()
455        {
456                return Math.atan((end.getX() - begin.getX()) / (end.getY() - begin.getY()));
457        }
458
459        /**
460         * Transform a line.
461         *
462         * @param transform
463         *            the transform matrix.
464         * @return the transformed line.
465         */
466        @Override
467        public Line2d transform(Matrix transform) {
468                return new Line2d(begin.transform(transform), end.transform(transform));
469        }
470
471        /**
472         * Returns a line that is at 90 degrees to the original line.
473         *
474         * @return the normal line
475         */
476        public Line2d getNormal()
477        {
478                final float dx = end.getX() - begin.getX();
479                final float dy = end.getY() - begin.getY();
480                return new Line2d(new Point2dImpl(-dy, dx), new Point2dImpl(dy, -dx));
481        }
482
483        /**
484         * Returns a line that is at 90 degrees to the original line and also passes
485         * through the given point.
486         *
487         * @param p
488         *            A point that must exist on the normal line
489         * @return a new line at right-angles to this
490         */
491        public Line2d getNormal(Point2d p)
492        {
493                return new Line2d(this.reflectAroundLine(p), p);
494        }
495
496        /*
497         * (non-Javadoc)
498         *
499         * @see org.openimaj.math.geometry.GeometricObject#translate(float, float)
500         */
501        @Override
502        public void translate(float x, float y)
503        {
504                this.begin.translate(x, y);
505                this.end.translate(x, y);
506        }
507
508        /**
509         * Tests whether the given point lies on this line. If the point sits on the
510         * line but is outside of the end points, then this function will return
511         * false.
512         *
513         * @param p
514         *            The point to test.
515         * @param tolerance
516         *            The tolerance to use in the test
517         * @return TRUE if the point lies on this line.
518         */
519        public boolean isInLine(Point2d p, float tolerance)
520        {
521                final float bx = (begin.getX() <= end.getX() ? begin.getX() : end.getX());
522                final float ex = (begin.getX() > end.getX() ? begin.getX() : end.getX());
523                return isOnLine(p, tolerance) && p.getX() + tolerance > bx &&
524                                p.getX() + tolerance < ex;
525        }
526
527        @Override
528        public String toString()
529        {
530                return "Line(" + begin + "->" + end + ")";
531        }
532
533        @Override
534        public Rectangle calculateRegularBoundingBox() {
535                final float x = Math.min(begin.getX(), end.getX());
536                final float y = Math.min(begin.getY(), end.getY());
537                final float width = Math.abs(begin.getX() - end.getX());
538                final float height = Math.abs(begin.getY() - end.getY());
539
540                return new Rectangle(x, y, width, height);
541        }
542
543        @Override
544        public void scale(float sc) {
545                begin.setX(begin.getX() * sc);
546                begin.setY(begin.getY() * sc);
547                end.setX(end.getX() * sc);
548                end.setY(end.getY() * sc);
549        }
550
551        @Override
552        public void scale(Point2d centre, float sc) {
553                this.translate(-centre.getX(), -centre.getY());
554
555                begin.setX(begin.getX() * sc);
556                begin.setY(begin.getY() * sc);
557                end.setX(end.getX() * sc);
558                end.setY(end.getY() * sc);
559
560                this.translate(centre.getX(), centre.getY());
561        }
562
563        @Override
564        public void scaleCentroid(float sc) {
565                scale(this.calculateCentroid(), sc);
566        }
567
568        @Override
569        public Point2d calculateCentroid() {
570                float xSum = begin.getX() + end.getX();
571                float ySum = begin.getY() + end.getY();
572
573                xSum /= 2;
574                ySum /= 2;
575
576                return new Point2dImpl(xSum, ySum);
577        }
578
579        @Override
580        public double minX() {
581                return Math.min(begin.getX(), end.getX());
582        }
583
584        @Override
585        public double minY() {
586                return Math.min(begin.getY(), end.getY());
587        }
588
589        @Override
590        public double maxX() {
591                return Math.max(begin.getX(), end.getX());
592        }
593
594        @Override
595        public double maxY() {
596                return Math.max(begin.getY(), end.getY());
597        }
598
599        @Override
600        public double getWidth() {
601                return Math.abs(begin.getX() - end.getX());
602        }
603
604        @Override
605        public double getHeight() {
606                return Math.abs(begin.getY() - end.getY());
607        }
608
609        /**
610         * Convert the line to a unit vector
611         *
612         * @return unit vector in the same direction as the line
613         */
614        public Point2dImpl toUnitVector() {
615                final float dx = end.getX() - begin.getX();
616                final float dy = end.getY() - begin.getY();
617                final float norm = (float) Math.sqrt(dx * dx + dy * dy);
618
619                return new Point2dImpl(dx / norm, dy / norm);
620        }
621
622        @Override
623        public Line2d clone() {
624                return new Line2d(begin.copy(), end.copy());
625        }
626
627        @Override
628        public int hashCode() {
629                return Arrays.hashCode(new Object[] { this.begin, this.end });
630        }
631
632        @Override
633        public boolean equals(Object other) {
634                if (!(other instanceof Line2d))
635                        return false;
636                final Line2d o = (Line2d) other;
637                if (!(o.begin.equals(begin) && o.end.equals(end)))
638                        return false;
639                return true;
640        }
641
642        @Override
643        public Point2d begin() {
644                return begin;
645        }
646
647        @Override
648        public Point2d end() {
649                return end;
650        }
651
652        @Override
653        public Polyline asPolyline() {
654                return new Polyline(lineIterator());
655        }
656
657        @Override
658        public Iterator<Line2d> lineIterator() {
659                return new Iterator<Line2d>() {
660                        boolean hasNext = true;
661
662                        @Override
663                        public boolean hasNext() {
664                                return hasNext;
665                        }
666
667                        @Override
668                        public Line2d next() {
669                                hasNext = false;
670                                return Line2d.this;
671                        }
672
673                        @Override
674                        public void remove() {
675                                throw new UnsupportedOperationException();
676                        }
677                };
678        }
679
680        /**
681         * Tests whether the given point lies on this line. Note that this will test
682         * whether the point sits on a line that travels to infinity in both
683         * directions.
684         *
685         * @param p
686         *            The point to test.
687         * @param tolerance
688         *            The tolerance to use in the test
689         * @return TRUE if the point lies on this line.
690         */
691        public boolean isOnLine(Point2d p, float tolerance)
692        {
693                if (distanceToLine(p) < tolerance)
694                        return true;
695
696                return false;
697        }
698
699        /**
700         * Returns the shortest distance between the point and this line. Note that
701         * this assumes the line travels to infinity in both directions.
702         * 
703         * @param p
704         *            The point to test.
705         * @return The distance from the point to the closest point on the line
706         */
707        public float distanceToLine(Point2d p) {
708                // vertical line
709                if (begin.getX() == end.getX()) {
710                        return Math.abs(begin.getX() - p.getX());
711                }
712
713                // Horizontal line
714                if (begin.getY() == end.getY()) {
715                        return Math.abs(begin.getY() - p.getY());
716                }
717
718                // Given the equation for a line as ax + by + c = 0
719                final float a = end.getY() - begin.getY();
720                final float b = end.getX() - begin.getX();
721                final float c = end.getX() * begin.getY() - begin.getX() * end.getY();
722
723                // calculate the distance from the line to the point
724                // http://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line
725                final float distance = (float) (Math.abs(a * p.getX() - b * p.getY() + c) / Math.sqrt(a * a + b * b));
726
727                return distance;
728        }
729}