/*
 * @(#)Geom.java 5.1
 *
 */

package CH.ifa.draw.util;

import java.awt.Point;
import java.awt.Rectangle;


/**
 * Some geometric utilities.
 */
public class Geom {
    /** Constant representing the direction north */
    static public final int NORTH = 1;

    /** Constant representing the direction south */
    static public final int SOUTH = 2;

    /** Constant representing the direction west */
    static public final int WEST = 3;

    /** Constant representing the direction east */
    static public final int EAST = 4;

    private Geom() {}

    /**
     * Tests if a point is on a line.
     *
     * @param x1 the x-coordinate of the start point of the line
     * @param y1 the y-coordinate of the start point of the line
     * @param x2 the x-coordinate of the end point of the line
     * @param y2 the y-coordinate of the end point of the line
     * @param px the x-coordinate of the point to test
     * @param py the y-coordinate of the point to test
     * @return <code>true</code>, if point is on the line
     */
    static public boolean lineContainsPoint(int x1, int y1, int x2, int y2, int px, int py) {
        Rectangle r = new Rectangle(new Point(x1, y1));
        r.add(x2, y2);

        r.grow(2, 2);
        if (!r.contains(px, py)) {
            return false;
        }

        double a;
        double b;
        double x;
        double y;

        if (x1 == x2) {
            return (Math.abs(px - x1) < 3);
        }

        if (y1 == y2) {
            return (Math.abs(py - y1) < 3);
        }

        a = (double) (y1 - y2) / (double) (x1 - x2);
        b = y1 - a * x1;
        x = (py - b) / a;
        y = a * px + b;

        return (Math.min(Math.abs(x - px), Math.abs(y - py)) < 4);
    }

    /**
     * Returns the direction from one point to another one as
     * {@link #NORTH}, {@link #SOUTH}, {@link #WEST} or {@link #EAST}.
     *
     * @param x1 the x-coordinate of the starting point
     * @param y1 the y-coordinate of the starting point
     * @param x2 the x-coordinate of the target point
     * @param y2 the y-coordinate of the target point
     * @return an integer representing the direction from the first point to the second
     *         (NORTH, SOUTH, WEST, or EAST)
     */
    static public int direction(int x1, int y1, int x2, int y2) {
        int direction;
        int vx = x2 - x1;
        int vy = y2 - y1;

        if (vy < vx && vx > -vy) {
            direction = EAST;
        } else if (vy > vx && vy > -vx) {
            direction = NORTH;
        } else if (vx < vy && vx < -vy) {
            direction = WEST;
        } else {
            direction = SOUTH;
        }
        return direction;
    }

    /**
     * Returns the Point south of the specified rectangle.
     *
     * @param r the rectangle for which the southern Point is calculated
     * @return a Point representing the Point south of the rectangle
     */
    static public Point south(Rectangle r) {
        return new Point(r.x + r.width / 2, r.y + r.height);
    }

    /**
     * Returns the center Point of the specified rectangle.
     *
     * @param r the rectangle for which the center Point is calculated
     * @return a Point representing the center of the rectangle
     */
    static public Point center(Rectangle r) {
        return new Point(r.x + r.width / 2, r.y + r.height / 2);
    }

    /**
     * Returns the Point west of the specified rectangle.
     *
     * @param r the rectangle for which the western Point is calculated
     * @return a Point representing the Point west of the rectangle
     */
    static public Point west(Rectangle r) {
        return new Point(r.x, r.y + r.height / 2);
    }

    /**
     * Returns the Point east of the specified rectangle.
     *
     * @param r the rectangle for which the eastern Point is calculated
     * @return a Point representing the Point east of the rectangle
     */
    static public Point east(Rectangle r) {
        return new Point(r.x + r.width, r.y + r.height / 2);
    }

    /**
     * Returns the Point north of the specified rectangle.
     *
     * @param r the rectangle for which the northern Point is calculated
     * @return a Point representing the Point north of the rectangle
     */
    static public Point north(Rectangle r) {
        return new Point(r.x + r.width / 2, r.y);
    }

    /**
     * Constrains a value to the given range.
     *
     * @param min the lower border of the range
     * @param max the upper border of the range
     * @param value the value that will be constrained
     * @return the constrained value
     */
    static public int range(int min, int max, int value) {
        if (value < min) {
            value = min;
        }
        if (value > max) {
            value = max;
        }
        return value;
    }

    /**
     * Gets the squared distance between two points.
     *
     * @param x1 the x-coordinate of point 1
     * @param y1 the y-coordinate of point 1
     * @param x2 the x-coordinate of point 2
     * @param y2 the y-coordinate of point 2
     * @return the squared distance between the two points
     */
    static public long length2(int x1, int y1, int x2, int y2) {
        return (long) (x2 - x1) * (x2 - x1) + (long) (y2 - y1) * (y2 - y1);
    }

    /**
     * Gets the distance between to points.
     *
     * @param x1 x-coordinate of point 1
     * @param y1 y-coordinate of point 1
     * @param x2 x-coordinate of point 2
     * @param y2 y-coordinate of point 2
     * @return the distance between two points
     */
    static public long length(int x1, int y1, int x2, int y2) {
        return (long) Math.sqrt(length2(x1, y1, x2, y2));
    }

    /**
     * Gets the Point in the middle between two Points.
     *
     * @param p1 the first Point
     * @param p2 the second Point
     * @return the Point between the two Points
     */
    static public Point middle(Point p1, Point p2) {
        return new Point((p1.x + p2.x) / 2, (p1.y + p2.y) / 2);
    }

    /**
     * Gets the angle of a point relative to a rectangle.
     *
     * @param r the given rectangle
     * @param p the given Point
     * @return the angle between the rectangle and the point
     */
    static public double pointToAngle(Rectangle r, Point p) {
        int px = p.x - (r.x + r.width / 2);
        int py = p.y - (r.y + r.height / 2);
        return Math.atan2(py * r.width, px * r.height);
    }

    /**
     * Gets the point on a rectangle that corresponds to the given angle.
     *
     * @param r the given rectangle
     * @param angle the angle the Point will be found from
     * @return the Point corresponding to the given angle and rectangle
     */
    static public Point angleToPoint(Rectangle r, double angle) {
        double si = Math.sin(angle);
        double co = Math.cos(angle);
        double e = 0.0001;

        int x = 0;
        int y = 0;
        if (Math.abs(si) > e) {
            x = (int) ((1.0 + co / Math.abs(si)) / 2.0 * r.width);
            x = range(0, r.width, x);
        } else if (co >= 0.0) {
            x = r.width;
        }
        if (Math.abs(co) > e) {
            y = (int) ((1.0 + si / Math.abs(co)) / 2.0 * r.height);
            y = range(0, r.height, y);
        } else if (si >= 0.0) {
            y = r.height;
        }
        return new Point(r.x + x, r.y + y);
    }

    /**
     * Converts a polar to a point.
     *
     * @param angle the angle in radians
     * @param fx the radius in the x-direction
     * @param fy the radius in the y-direction
     * @return the corresponding point in Cartesian coordinates
     */
    static public Point polarToPoint(double angle, double fx, double fy) {
        double si = Math.sin(angle);
        double co = Math.cos(angle);
        return new Point((int) (fx * co + 0.5), (int) (fy * si + 0.5));
    }

    /**
     * Gets the point on an oval that corresponds to the given angle.
     *
     * @param r the rectangle defining the oval
     * @param angle the angle from the center of the oval
     * @return the Point corresponding to the oval and angle
     */
    static public Point ovalAngleToPoint(Rectangle r, double angle) {
        Point center = Geom.center(r);
        Point p = Geom.polarToPoint(angle, (double) r.width / 2, (double) r.height / 2);
        return new Point(center.x + p.x, center.y + p.y);
    }

    /**
     * Returns whether the given Point is contained in the ellipse
     * given by the Rectangle.
     *
     * @param r the rectangle defining the ellipse
     * @param x x-coordinate of the point
     * @param y y-coordinate of the point
     * @return <code>true</code>, if point is contained in the ellipse
     */
    static public boolean ellipseContainsPoint(Rectangle r, int x, int y) {
        Point center = Geom.center(r);

        // determine both "centers" of the ellipse:
        int d =
            (int) Math.round(Math.sqrt(Math.abs(r.width * r.width / 4 - r.height * r.height / 4)));
        Point c1 = new Point(center);
        Point c2 = new Point(center);
        if (r.width > r.height) {
            c1.x -= d;
            c2.x += d;
        } else {
            c1.y += d;
            c2.y -= d;
        }
        return length(x, y, c1.x, c1.y) + length(x, y, c2.x, c2.y) <= Math.max(r.width, r.height);
    }

    /**
     * Standard line intersection algorithm
     * From Doug Lea's PolygonFigure
     *
     * @param xa line 1 point 1 x
     * @param ya line 1 point 1 y
     * @param xb line 1 point 2 x
     * @param yb line 1 point 2 y
     * @param xc line 2 point 1 x
     * @param yc line 2 point 1 y
     * @param xd line 2 point 2 x
     * @param yd line 2 point 2 y
     * @return the <code>Point</code> of intersection if it exists,<br>
     *         <code>null</code> else
     */
    static public Point intersect(int xa, int ya, int xb, int yb, int xc, int yc, int xd, int yd) {
        double denom = ((xb - xa) * (yd - yc) - (yb - ya) * (xd - xc));

        double rnum = ((ya - yc) * (xd - xc) - (xa - xc) * (yd - yc));

        if (denom == 0.0) { // parallel
            if (rnum == 0.0) { // coincident; pick one end of first line
                if ((xa < xb && (xb < xc || xb < xd)) || (xa > xb && (xb > xc || xb > xd))) {
                    return new Point(xb, yb);
                } else {
                    return new Point(xa, ya);
                }
            } else {
                return null;
            }
        }

        double r = rnum / denom;

        double snum = ((ya - yc) * (xb - xa) - (xa - xc) * (yb - ya));
        double s = snum / denom;

        if (0.0 <= r && r <= 1.0 && 0.0 <= s && s <= 1.0) {
            int px = (int) (xa + (xb - xa) * r);
            int py = (int) (ya + (yb - ya) * r);
            return new Point(px, py);
        } else {
            return null;
        }
    }
}