/** Geometry-related utility methods.
 */
public class Geometry {

	public static double abs(double x) {
		if (x >= 0)
		    return x;
		else 
			return -x;	
	}

    /** Determine if a point is contained in a circle with given
     *  radius and center.
     *
     * @param x x-coordinate of point
     * @param y y-coordinate of point
     * @param centerX x-coordinate of center of circle
     * @param centerY y-coordinate of center of circle
     * @param radius radius of circle
     * @return true if point is contained in circle
     */
    public static boolean contains(double x, double y,
                                   double centerX, double centerY,
                                   double radius) {
        // Compute squared distance from center
        double dx = x - centerX;
        double dy = y - centerY;
        double dist2 = dx * dx + dy * dy;
        return dist2 <= radius * radius;
    }
                                   

    /** Compute area of triangle with given corners.
     * 
     * @param aX x-coordinate of corner 1
     * @param aY y-coordinate of corner 1
     * @param bX y-coordinate of corner 2
     * @param bY x-coordinate of corner 2
     * @param cX x-coordinate of corner 3
     * @param cY y-coordinate of corner 3
     * @return area of triangle with given corner coordinates
     */
    public static double area(double aX, double aY, double bX, double bY,
                              double cX, double cY) {
        double uX = bX - aX;
        double uY = bY - aY;
        double vX = bX - cX;
        double vY = bY - cY;
        return Math.abs(0.5 * cross(uX, uY, vX, vY));
    }

    /** Return true if line segments, each defined by a start and end point,
     *  meet at any point.
     * 
     * @param aX starting x-coordinate of segment 1
     * @param aY starting y-coordinate of segment 1
     * @param bX ending x-coordinate of segment 1
     * @param bY ending y-coordinate of segment 1
     * @param cX starting x-coordinate of segment 2
     * @param cY starting y-coordinate of segment 2
     * @param dX ending x-coordinate of segment 2
     * @param dY ending y-coordinate of segment 2
     * @return true if line segments meet
     */
    public static boolean intersects(double aX, double aY,
                                     double bX, double bY,
                                     double cX, double cY,
                                     double dX, double dY) {
        
        // Some details just in case you'd like to know the math here:
        // In vector notation, we'll parametrize segment 1 and segment 2
        // respectively as:
        // s1 + u*p1, 0<=p1<=1
        // s2 + v*p2, 0<=p2<=1
        // We'll then solve for values of p0 and p1 where segments would
        // intersect, and determine if they lie in the valid range.
        // This intersection occurs if s1 + u*p1 = s2 + v*p2 for some p1,p2, or
        // s2 - s1 = u*p1 - v*p2.  Let s2 - s1 = t.  If we use the cross product
        // on both sides, we can get (with "x" denoting cross product):
        // t x u = p2*(u x v), and
        // t x v = p1*(u x v).
        // The simplification happens because the cross product of any vector
        // with itself (or a parallel vector) is 0.  Hence p2 = (t x u)/(u x v),
        // and p1 = (t x v)/(u x v) at the intersection.  If those values are
        // both in the range [0, 1], the segments intersect.
        
        // directions of each line segment
        double uX = bX - aX;
        double uY = bY - aY;
        double vX = dX - cX;
        double vY = dY - cY;

        // difference between line segment starting points
        double tX = cX - aX;
        double tY = cY - aY;
        
        // cross products
        double uvCross = cross(uX, uY, vX, vY);
        double tuCross = cross(tX, tY, uX, uY);
        double tvCross = cross(tX, tY, vX, vY);

        // solve for where lines intersect.  Can you spot a bug?
        double p1 = tuCross / uvCross;
        double p2 = tvCross / uvCross;

        return p1 >= 0 && p1 <= 1 && p2 >= 0 && p2 <= 1;
        
    }
    
    // 2-D cross product 
    public static double cross(double aX, double aY, double bX, double bY) {
        return aX * bY - aY * bX;
    }
    
	// Assert two numbers are within 1e-10, with given error message.
	public static void checkClose(double x, double y, String msg) {
		assert Math.abs(x - y) < 1e-10: msg + x + ", " + y;
	}
    
    public static void main(String[] args) {
        // Insert basic unit testing routines
		
		// Tests for abs()
		assert abs(0) == 0: "abs(0) must be 0";
		assert abs(1) == 1;
		assert abs(-1) == 1;
		
		// Tests for area()
		assert area(1, 1, 1, 1, 1, 1) == 0: "3 point degenerate case";
		assert area(1, 1, 1, 1, 2, 2) == 0: "2 point degenerate case";
		assert area(0, 0, 2, 0, 0, 2) == 2: "Right triangle case";
		checkClose(area(0, 0, 0.2, 0, 0, 0.2), .02, "Small right triangle");
		checkClose(area(0, 0, 2, 0, 1, 2), 2, "Non-right triangle");
		
		// Tests for intersects()
		
    }
    
}