source: trunk/src/org/expeditee/core/Line.java@ 1097

package org.expeditee.core;

/**
 * The line class represents a line-segment in 2-dimensional space (i.e.
 * the connection between 2 points).
 * 
 * @author cts16
 */
public class Line {
        
        /** The amount of error to use to ensure lines passing through pixels are hit.
            Equal to 1 / sqrt(2). */
        public static final double PIXEL_ERROR = 0.707106781;
        
        /** The two end-points of the line segment. */
        private Point _p1, _p2;
        
        public Line(Point p1, Point p2)
        {
                _p1 = new Point(p1);
                _p2 = new Point(p2);
        }
        
        public Line(int x1, int y1, int x2, int y2)
        {
                _p1 = new Point(x1, y1);
                _p2 = new Point(x2, y2);
        }
        
        /** Gets the position of the first end of the line. */
        public Point getFirstEnd()
        {
                return _p1;
        }
        
        /** Gets the position of the second end of the line. */
        public Point getSecondEnd()
        {
                return _p2;
        }
        
        /** Sets the first end of the line to the given point. */
        public void setFirstEnd(Point p)
        {
                if (p != null) _p1 = p;
        }
        
        /** Sets the second end of the line to the given point. */
        public void setSecondEnd(Point p)
        {
                if (p != null) _p2 = p;
        }
        
        /** Gets the change in x-coordinate from one end to the other. */
        public int deltaX()
        {
                return _p2.x - _p1.x;
        }
        
        /** Gets the change in y-coordinate from one end to the other. */
        public int deltaY()
        {
                return _p2.y - _p1.y;
        }
        
        /** Gets the length of the line. */
        public double length()
        {
                return Point.distanceBetween(_p1, _p2);
        }
        
        /**
         * Checks if this line intersects the given line.
         * 
         * https://stackoverflow.com/questions/563198/whats-the-most-efficent-way-to-calculate-where-two-line-segments-intersect
         */
        public boolean intersects(Line other, double error)
        {
                Point p = this._p1;
                Point q = other._p1;
                Point r = Point.difference(this._p2, p);
                Point s = Point.difference(other._p2, q);
                
                int numerator = crossLength(Point.difference(q, p), r);
                int denominator = crossLength(r, s);
                
                if (denominator == 0) {
                        return numerator == 0 && (contains(other._p1, error) || contains(other._p2, error));
                } else {
                        double u = ((double) numerator) / denominator;
                        return u >= 0 && u <= 1 && this.contains(new Point((int) (q.x + u * s.x), (int) (q.y + u * s.y)), error);
                }
        }
        
        /**
         * Calculates the length of the cross-product between points a and b.
         */
        private int crossLength(Point a, Point b)
        {
                return a.x * b.y - a.y * b.x;
        }
        
        /**
         * Checks if the given point falls on the line.
         * 
         * @param p
         *              The point to check.
         * 
         * @param error
         *              The maximum distance from the line that will be considered part of the line.
         * 
         * @return
         *              True if the given point falls on the line (within <code>error</code>), false if not.
         */
        public boolean contains(Point p, double error)
        {
                // If the point is within error from either end,
                // then we say it's on the line
                if (Point.distanceBetween(p, _p1) <= error || Point.distanceBetween(p, _p2) <= error) return true;
                
                // Point's projection onto the line must be between the two ends
                double length = length();
                double projection = Point.dotProduct(_p1, _p2, p) / length;
                if (!(0 <= projection && projection <= length)) return false;
                
                // Point must be within error distance from the line
                double hypotenuse = Point.distanceBetween(p, _p1);
                if ((hypotenuse * hypotenuse - projection * projection) <= (error * error)) return true;
                
                // The point is too far from the line
                return false;
        }
        
        /**
         * Checks if there are any intersections between to sets of lines.
         * Does not check for intersections within each set.
         * 
         * @param lines1
         *              The first set of lines.
         * 
         * @param lines2
         *              The second set of lines.
         * 
         * @return
         *              True if a line from set 1 intersects a line from set 2,
         *              false if no intersections occur.
         */
        public static boolean anyIntersections(Line[] lines1, Line[] lines2, double error)
        {
                for (Line line1 : lines1) {
                        for (Line line2 : lines2) {
                                if (line1.intersects(line2, error)) return true;
                        }
                }
                
                return false;
        }
        
        /** Gets the point on the line nearest to the given point. */
        public Point getPointNearestTo(Point p)
        {
                // If the line is degenerate, then that is the nearest point
                if (_p1.equals(_p2)) return _p1.clone();
                
                // Work out the distance from _p1 to the nearest point
                double lineLength = length();
                double projectionLength = Point.dotProduct(_p1, _p2, p) / lineLength;
                
                // Calculate the position of the nearest point
                if (projectionLength <= 0.0) {
                        return _p1.clone();
                } else if (projectionLength >= lineLength) {
                        return _p2.clone();
                } else {
                        double scaleFactor = projectionLength / lineLength;
                        return _p1.clone().add((_p2.x - _p1.x) * scaleFactor, (_p2.y - _p1.y) * scaleFactor);
                }
        }

}