/* @(#)Geometry.java  15 February 2006
 *
 * Copyright 2006
 * College of Computer Science
 * Northeastern University
 * Boston, MA  02115
 *
 * This software may be used for educational purposes as long as
 * this copyright notice is retained intact at the top of all files.
 *
 * To discuss commercial use of this software, contact 
 * Prof. Richard Rasala or Prof. Viera Proulx at the Northeastern 
 * University College of Computer Science: 617-373-2462.
 *
 * The principal software developer on this project is Jeff Raab.
 *
 * Should this software be modified, the words "Modified from 
 * Original" must be included as a comment below this notice.
 *
 * All publication rights are retained.  This software or its 
 * documentation may not be published in any media either in whole
 * or in part without explicit permission.
 *
 * This software was created with support from Northeastern 
 * University and from NSF grant DUE-9950829.
 */

import edu.neu.ccs.*;
import edu.neu.ccs.gui.*;
import edu.neu.ccs.codec.*;
import edu.neu.ccs.console.*;
import edu.neu.ccs.filter.*;
import edu.neu.ccs.jpf.*;
import edu.neu.ccs.parser.*;
import edu.neu.ccs.pedagogy.*;
import edu.neu.ccs.quick.*;
import edu.neu.ccs.util.*;

import java.awt.*;
import java.awt.event.*;
import java.awt.geom.*;
import java.awt.font.*;
import java.awt.image.*;
import javax.swing.*;
import javax.swing.border.*;
import java.io.*;
import java.util.*;
import java.math.*;
import java.beans.*;
import java.lang.reflect.*;
import java.net.URL;
import java.util.regex.*;
import java.text.ParseException;


public class Geometry {
    
    /**
     * Returns the point of intersection of the extended
     * lines that pass through the line segments A and B.
     * 
     * Returns null if either line segment is null,
     * if either line segment degenerates to a point,
     * or if the line segments have the same slope.
     */
    public static Point2D intersect(Line2D A, Line2D B) {
        if ((A == null) || (B == null))
            return null;
        
        // get end points
        double x1 = A.getX1();
        double y1 = A.getY1();
        double x2 = A.getX2();
        double y2 = A.getY2();
        
        double x3 = B.getX1();
        double y3 = B.getY1();
        double x4 = B.getX2();
        double y4 = B.getY2();
        
        // get end point differences 
        double xa = x2 - x1;
        double ya = y2 - y1;
        
        double xb = x4 - x3;
        double yb = y4 - y3;
        
        // get determinant
        double det = xa * yb - xb * ya;
        
        if (det == 0)
            return null;
        
        // solve the linear equations
        //
        // (x - x1) * ya = (y - y1) * xa
        // (x - x3) * yb = (y - y3) * xb
        //
        // that is
        //
        // x * ya - y * xa = x1 * ya - y1 * xa
        // x * yb - y * xb = x3 * yb - y3 * xb
        
        double ca = x1 * ya - y1 * xa;
        double cb = x3 * yb - y3 * xb;
        
        double x = (xa * cb - xb * ca) / det;
        double y = (ya * cb - yb * ca) / det;
        
        return new Point2D.Double(x, y);
    }
    
    
    /** Returns true if z is between z1 and z2. */
    public static boolean isBetween (double z, double z1, double z2) {
         if (z1 <= z2)
            return (z1 <= z) && (z <= z2);
        else
            return (z2 <= z) && (z <= z1);
    }
    
    
    /**
     * Assume that it is known that P is on the extended line
     * through the line segment A, for example, because P has
     * been returned by the intersect method in this class.
     * 
     * Then returns true if P is on the line segment A itself
     * and returns false otherwise.
     * 
     * Technical note: The method simply tests if the point P
     * is in the rectangle enclosing the line segment A.  The
     * assumption is essential for asserting that P is on the
     * line segment A itself.
     */
    public static boolean onSegment(Point2D P, Line2D A) {
        if ((P == null) || (A == null))
            return false;
        
        double x = P.getX();
        double y = P.getY();
        
        double x1 = A.getX1();
        double y1 = A.getY1();
        double x2 = A.getX2();
        double y2 = A.getY2();
        
        return isBetween(x, x1, x2) && isBetween(y, y1, y2);
    }
    
}