import java.applet.Applet;
import java.awt.event.*;
import java.awt.*;


/**This class does some basic spherical geometry. It isn't used directly in the
   proofs, but is used in some of the sanity checks for the proofs.**/

public class XtraVector {

    /**norm**/
    public static double norm(Vector V) {
	return(Math.sqrt(Vector.dot(V,V)));
    }


    /**cross product **/

    public static Vector cross(Vector v,Vector w) {
	Vector X=new Vector();
	X.x[0]=v.x[1]*w.x[2]-w.x[1]*v.x[2];
	X.x[1]=v.x[2]*w.x[0]-w.x[2]*v.x[0];
	X.x[2]=v.x[0]*w.x[1]-w.x[0]*v.x[1];
	return(X);
    }


    /**In these routines we find the intersection between the lines X1+s U1 and X2 + s U2.  The
       routine only works when the lines actually intersect.  The first routine is the final one.**/

    public static Vector findIntersection(Vector X1,Vector U1,Vector X2,Vector U2) {
	int q=bestDeterminant(U1,U2);
	return(findIntersection(q,X1,U1,X2,U2));
    }

    public static int bestDeterminant(Vector U1,Vector U2) {
	Vector X=cross(U1,U2);
	int index=-1;
	double max=0;
	for(int i=0;i<3;++i) {
	    double test=Math.abs(X.x[i]);
	    if(max<test) {
		index=i;
		max=test;
	    }
	}
	return(index);
    }


    public static Vector findIntersection(int q,Vector X1,Vector U1,Vector X2,Vector U2) {
	if(q==0) return(findIntersection0(X1,U1,X2,U2));
	if(q==1) return(findIntersection1(X1,U1,X2,U2));
	if(q==2) return(findIntersection2(X1,U1,X2,U2));
	return(null);
    }

    public static Vector findIntersection0(Vector X1,Vector U1,Vector X2,Vector U2) {
	Vector V=findIntersection2(RotateLeft(X1),RotateLeft(U1),RotateLeft(X2),RotateLeft(U2));
	V=RotateRight(V);
	return(V);
    }

    public static Vector findIntersection1(Vector X1,Vector U1,Vector X2,Vector U2) {
	Vector V=findIntersection2(RotateRight(X1),RotateRight(U1),RotateRight(X2),RotateRight(U2));
	V=RotateLeft(V);
	return(V);
    }


    public static Vector RotateLeft(Vector V) {
	Vector W=new Vector(V.x[1],V.x[2],V.x[0]);
	return(W);
    }
    public static Vector RotateRight(Vector V) {
	Vector W=new Vector(V.x[2],V.x[0],V.x[1]);
	return(W);
    }


    /**This is the main computational component of the intersection finder.  The other routines
       just permute the coordinates in various ways so as to avoid a degenerate situation.**/

    public static Vector findIntersection2(Vector X1,Vector U1,Vector X2,Vector U2) {

	double x10=X1.x[0];
	double x11=X1.x[1];
	double x12=X1.x[2];
	double x20=X2.x[0];
	double x21=X2.x[1];
	double x22=X2.x[2];

	double u10=U1.x[0];
	double u11=U1.x[1];
	double u12=U1.x[2];
	double u20=U2.x[0];
	double u21=U2.x[1];
	double u22=U2.x[2];

	double d=u10*u21-u20*u11;

	double c1=u10*u20*x11+u10*u21*x20-u10*u20*x21-u11*u20*x10;
	c1=c1/d;

	double c2=u11*u21*x10+u11*u20*x21-u10*u21*x11-u11*u21*x20;
	c2=-c2/d;

	double c3=u12*u20*x11+u10*u21*x12+u12*u21*x20-u12*u21*x10-u11*u20*x12-u12*u20*x21;
	c3=c3/d;

	Vector Z=new Vector(c1,c2,c3);
	return(Z);
    }





    /**In this long routine, the vectors V1 and V2 are unit vectors.  We find the
       center of the circle through V1,V2 and W=(0,0,1).**/

    public static Vector center(Vector V1,Vector V2) {
	Vector W=new Vector(0,0,1);
	Vector X1=average(W,V1);
	Vector X2=average(W,V2);
	Vector N=cross(Vector.minus(W,V1),Vector.minus(W,V2));
	Vector U1=cross(N,Vector.minus(W,V1));
	Vector U2=cross(N,Vector.minus(W,V2));
	Vector Z=findIntersection(X1,U1,X2,U2);
	return(Z);
    }

    /**This routine points the point on the circle through V1,V2,(0,0,1) that
       is farthest from the midpoint of the segment joining  V1 to V2.**/

    public static Vector farPoint(Vector V1,Vector V2) {

	Vector X=center(V1,V2);
	Vector Y1=average(V1,V2);
	double d1=Vector.dist(X,V1);
	Vector Y2=Vector.minus(X,Y1);
	double d2=norm(Y2);
	Y2=scale(d1/d2,Y2);
	Vector Y3=Vector.plus(X,Y2);
	return(Y3);
    }


    /**This routine does the liner interpolation between two unit vectors V1 and V2.  The
       result is shorter than a unit vector.*/

    public static Vector interpolateLinear(Vector V1,Vector V2,double t) {
	Vector U1=scale(1-t,V1);
	Vector U2=scale(t,V2);
	Vector H=Vector.plus(U1,U2);
	return(H);
    }

    /**This is our spherical interpolation routine.**/


    public static Vector interpolate(Vector V1,Vector V2,double t) {
	if(t==0) return(V1);
	if(t==1) return(V2);
	Vector U=interpolateLinear(V1,V2,t);
	Vector Y=farPoint(V1,V2);
	double d1=Vector.dist(U,Y);
	double d2=Vector.dist(U,V1);
	double d3=Vector.dist(U,V2);
	double d4=d2*d3/d1;
	Vector H=Vector.minus(U,Y);
	double d5=norm(H);
	H=scale(d4/d5,H);
	Vector X=Vector.plus(U,H);
	return(X);
    }


    /**computes the distance between the arc center and the segment center.**/

    public static double bow(Vector V1,Vector V2) {
	Vector X1=interpolate(V1,V2,.5);
	Vector X2=average(V1,V2);
	double d=Vector.dist(X1,X2);
	return(d);
    }



    /**This routine takes the part of W that is orthogonal to V**/

    public static Vector ortho(Vector V,Vector W) {
	double d1=Vector.dot(V,W);
	double d2=Vector.dot(V,V);
	double d=d1/d2;
	Vector W1=scale(d,V);
	Vector W2=Vector.minus(W,W1);
	return(W2);
    }


    /**This routine calculates the distance from a point to a line determined by a pair of vectors **/

    public static double pointLineDist(Vector W,Vector V1,Vector V2) {
	Vector V=Vector.minus(V1,V2);
	Vector X=Vector.minus(V1,W);
	Vector Y=ortho(V,X);
	double d=norm(Y);
	return(d);
    }


    public static double[] positionData(Vector W,Vector V1,Vector V2) {
	double[] d=new double[4];
	d[0]=pointLineDist(W,V1,V2);
	d[1]=Vector.dist(W,V1);
	d[2]=Vector.dist(W,V2);

	if(d[1]>d[2]) {
	    double temp=d[2];
	    d[2]=d[1];
	    d[1]=temp;
	}
	d[1]=d[1]/d[0];
	d[2]=d[2]/d[0];
	d[3]=Vector.dist(V1,V2)/d[0];
	d[1]=Math.sqrt(d[1]*d[1]-1);
	d[2]=Math.sqrt(d[2]*d[2]-1);
	return(d);
    }

    public static double[] positionData2(Vector W,Vector V1,Vector V2) {
	Vector V=average(V1,V2);
	double r=Vector.dist(V,W);
	double s=Vector.dist(V1,V2);
	double[] d={r,s};
	return(d);
    }


    public static Vector scale(double d,Vector v) {
	Vector x=new Vector();
	for(int i=0;i<3;++i) x.x[i]=d*v.x[i];
	return(x);
    }

    public static Vector average(Vector v,Vector w) {
	Vector x=new Vector();
	for(int i=0;i<3;++i) x.x[i]=.5*(v.x[i]+w.x[i]);
	return(x);
    }


    /**project to unit sphere**/

    public static Vector unitSphere(Vector W) {
	Vector V=new Vector(W.x[0],W.x[1],W.x[2]);
	double d=Math.sqrt(Vector.dot(V,V));
	V.x[0]=V.x[0]/d;
	V.x[1]=V.x[1]/d;
	V.x[2]=V.x[2]/d;
	return(V);
    }



    /**Apply to W  the isometric reflection that swaps V1 and V2**/

    public static Vector swap(Vector V1,Vector V2,Vector W) {
	Vector[] X=new Vector[10];
	X[0]=Vector.plus(V1,V2);
	X[0]=unitSphere(X[0]);
	X[1]=cross(V1,V2);
	X[1]=unitSphere(X[1]);
	X[2]=cross(X[0],X[1]);
	double d=2*Vector.dot(W,X[2]);
	X[3]=scale(d,X[2]);
	X[4]=Vector.minus(W,X[3]);
	return(X[4]);
    }


}