import java.applet.Applet;
import java.awt.event.*;
import java.awt.*;
import java.awt.geom.*;
import java.util.Arrays;

/**This class defines and manipulates the strips
   associated to a polygon**/


public class Strips {
    public Strips() {}

    /**This is a routine specially included for polygons with parallel sides.**/

    public static int stripCharacter(PolyWedge P,int n) {
	int n0=n%P.count;
	int n1=(n+1)%P.count;
	Complex z1=P.z[n0];
	Complex z2=P.z[n1];
	Complex z3=P.getCenter();
	Complex z4=Complex.minus(z2,z1);
	Complex z5=Complex.minus(z3,Complex.average(z1,z2));
	int a1=1;
	if(z4.y/z4.x>0) a1=-1;
	int a2=1;
	if(z5.y>0) a2=-1;

	if((a1==1)&&(a2==-1)) return(1);
	if((a1==1)&&(a2==1)) return(-1);
	if((a1==-1)&&(a2==1)) return(1);
	if((a1==-1)&&(a2==-1)) return(-1);
	return(0);

    }



    /**Given a vertex (and the counterclockwise-adjacent edge) find
         the vertex farthest from the vertex.  This works when the polygon
         has no parallel sides.**/

    public static int farthest(PolyWedge P,int n) {
	int n0=n%P.count;
	int n1=(n+1)%P.count;
	int n2=0;
	Complex z1=P.z[n0];
	Complex z2=P.z[n1];

	int parallel=stripCharacter(P,n);
	if(n>=P.count) parallel=-parallel;

	double area=0;
	double max=0;
	int index=0;
	for(int i=0;i<P.count;++i) {
	    n2=(i+n)%P.count;
	    Complex z3=P.z[n2];
	    area=Math.abs(Complex.area(z1,z2,z3));
	    if(max<area+.00000001*parallel) {
		max=area;
		index=n2;
	    }
	}
	return(index);
    }

    /**Produces 4 complex numbers, which are the vertices of a
       parallelogram on the strip*/

    public static Complex[] stripData(PolyWedge P,int n) {
	int n0=n%P.count;
	int n1=(n+1)%P.count;
	int n2=farthest(P,n);	
                  Complex[] X=new Complex[4];	 
                  Complex z=P.z[n2];
	X[0]=P.z[n0];
	X[1]=P.z[n1];
	X[2]=new Complex(2*z.x-X[0].x,2*z.y-X[0].y);
	X[3]=new Complex(2*z.x-X[1].x,2*z.y-X[1].y);
	return(X);
    }


    public static Complex stripPointer(PolyWedge P,int n,int DIST) {
	Complex[] Z=stripData(P,n);
	Complex w1=Complex.average(Z[1],Z[3]);
	Complex w2=Complex.minus(Z[0],Z[1]);
	if(w2.y<0) w2=new Complex(-w2.x,-w2.y);
	w2=Complex.times(w2,new Complex(DIST,0));
	w2=Complex.plus(w1,w2);
	return(w2);
    }


    /**This routine sorts the slopes of the edges of P.    The method considers many points
       in a big loop around the polygon and records the strips in the order that they are hit.
       This routine is not perfect.**/



    public static  int[] sortSlopes(PolyWedge P) {
	int n=P.count;
	int[] first=new int[2*n];
	Complex[] z=new Complex[2*n];	
                  double[] d1=new double[2*n];	
                  double[] d2=new double[2*n];
	for(int i=0;i<n;++i) {
                      z[i]=stripPointer(P,i,1000000);
	    z[i+n]=stripPointer(P,i,-1000000);
	    z[i]=Complex.unit(z[i]);
	    z[i+n]=Complex.unit(z[i+n]);
	    d1[i]=z[i].x;
	    d2[i]=z[i].x;
	    d1[i+n]=3-z[i+n].x;
	    d2[i+n]=3-z[i+n].x;
	}
	Arrays.sort(d2);

	for(int i=0;i<2*n;++i) {
	    for(int j=0;j<2*n;++j) {
		if(d1[i]==d2[j]) first[j]=i;
	    }
	}
	for(int i=0;i<n;++i) first[i+n]=first[i+n]-n;
	for(int i=0;i<n;++i) first[i]=first[i]+n;
	for(int i=0;i<n;++i) {
	    int temp=first[i];
	    first[i]=first[i+n];
	    first[i+n]=temp;
	}
	return(first);
    }






    public static int[] stripVector(PolyWedge P,int n) {	
	int n0=n;
	int n1=(n+1)%P.count;
	int n2=farthest(P,n);
	int[] N=new int[P.count];
	for(int i=0;i<P.count;++i) {
	    N[i]=0;
	}
	N[n1]=-1;
	N[n2]=1;
	return(N);
    }

    public static int insideStrip(PolyWedge P,int n,Complex u) {
	Complex[] X=stripData(P,n);
	Complex z1=X[0];
	Complex z2=X[1];
	Complex w1=X[2];
	Complex w2=X[3];
	double a1=Complex.area(z1,z2,u);
	double a2=Complex.area(w1,w2,u);
	if(a1<0) return(0);
	if(a2<0) return(0);
	return(1);
    }

    public static int insideStripPositive(PolyWedge P,int n,Complex u) {
	double test1=insideStrip(P,n,u);
	if(test1==0) return(0);
	Complex z1=P.getCenter();
	double t=u.x-z1.x;
	if(t<0) return(0);
	return(1);
    }


    /**Computes the position of a point relative to the strip.**/

    public static double relStrip(PolyWedge P,int n,Complex u) {
	Complex[] X=stripData(P,n);
	Complex z1=X[0];
	Complex z2=X[1];
	Complex w1=X[2];
	Complex w2=X[3];
	double a1=Complex.area(z1,z2,u);
	double a2=Complex.area(z1,z2,w1);
	double a3=a1/a2;
	return(a3);
    }


    /**always a non-negative integer*/

    public static int relStripIntegerAbs(PolyWedge P,int n,Complex u) {
        double a=relStrip(P,n,u);
        a=Math.abs(Math.floor(a));
        int b=(int)(a);
        return(b);
    }

    /**same as previous, but signed integer**/

    public static int relStripInteger(PolyWedge P,int n,Complex u) {
        double a=relStrip(P,n,u);
        a=Math.floor(a);
        int b=(int)(a);
        return(b);
    }




    public static Complex[] diamond(PolyWedge P,int n0,int n1) {
	Complex[] Z1=stripData(P,n0);
	Complex[] Z2=stripData(P,n1);
	Complex[] X=new Complex[4];
                  X[0]=Vector.findCross2(Z1[0],Z1[1],Z2[0],Z2[1]);
                  X[1]=Vector.findCross2(Z1[0],Z1[1],Z2[2],Z2[3]);
                  X[2]=Vector.findCross2(Z1[2],Z1[3],Z2[0],Z2[1]);
                  X[3]=Vector.findCross2(Z1[2],Z1[3],Z2[2],Z2[3]);
	return(X);
    }


    /**spokes**/

    public static Complex[] spoke(PolyWedge P,int j) {
                  Complex[] Z=Strips.stripData(P,j);
	Complex z=Complex.average(Z[1],Z[3]);
	Complex[] W={Z[1],z};
	return(W);
    }

    public static Complex[] antiSpoke(PolyWedge P,int j) {
        Complex[] Z=Strips.stripData(P,j);
	Complex z=Complex.average(Z[1],Z[3]);
	Complex[] W={Z[0],z};
	return(W);
    }


    public static int testConnect(PolyWedge P,int i,int j) {
	Complex[] Z1=spoke(P,i);
	Complex[] Z2=spoke(P,j);
	if(Complex.dist(Z1[0],Z2[0])<.0000001) return(1);
	if(Complex.dist(Z1[0],Z2[1])<.0000001) return(1);
	if(Complex.dist(Z1[1],Z2[0])<.0000001) return(1);
	if(Complex.dist(Z1[1],Z2[1])<.0000001) return(1);
	return(0);
    }


    public static int testAntiConnect(PolyWedge P,int i,int j) {
	Complex[] Z1=antiSpoke(P,i);
	Complex[] Z2=antiSpoke(P,j);
	if(Complex.dist(Z1[0],Z2[0])<.0000001) return(1);
	if(Complex.dist(Z1[0],Z2[1])<.0000001) return(1);
	if(Complex.dist(Z1[1],Z2[0])<.0000001) return(1);
	if(Complex.dist(Z1[1],Z2[1])<.0000001) return(1);
	return(0);
    }


    public static int firstBackwards(PolyWedge P,int i) {
	int test=0;
	for(int j=1;j<P.count;++j) {
	    int k=(i-j+P.count)%P.count;
	    test=testConnect(P,P.slopes[i],P.slopes[k]);
	    if(test==0) return(k);
	}
	if(i!=P.count-1) return(P.count-1);
	return(0);
    }

    public static int firstForwards(PolyWedge P,int i) {
	int test=0;
	for(int j=1;j<P.count;++j) {
	    int k=(i+j+P.count)%P.count;
	    test=testAntiConnect(P,P.slopes[i],P.slopes[k]);
	    if(test==0) return(k);
	} 
	if(i!=0) return(0);
	return(P.count-1);
    }



    /**adjacent strips*/

    public static int testStrips(int n0,int n1,int N) {
	int k=n1-n0;
	if(k<0) k=k+N;
	if(k==1) return(1);
	return(0);
    }

    /**routines used by the tile computer**/

    public static PolyWedge makeTriangle(int choice,PolyWedge P,int k,Complex z,double ss) {
	Complex[] w=new Complex[10];
	Complex[] Z=stripData(P,k);
	w[0]=Complex.minus(Z[3],Z[1]);
	double s=-ss;
	if(choice==1) s=ss;
	w[1]=Complex.times(w[0],new Complex(s,0));
	w[2]=Complex.plus(z,w[1]);

	w[3]=Complex.minus(Z[0],Z[1]);
	w[4]=Complex.minus(Z[1],Z[0]);
	w[5]=Complex.minus(Z[3],Z[1]);
	if(choice==1) w[5]=Complex.minus(Z[1],Z[3]);

	Complex big=new Complex(100,0);
	w[6]=Complex.plus(w[2],Complex.times(big,w[3]));
	w[7]=Complex.plus(w[2],Complex.times(big,w[4]));
	w[8]=Complex.plus(w[2],Complex.times(big,w[5]));
	PolyWedge X=new PolyWedge();
	X.count=3;
	X.z[0]=new Complex(w[6]);
	X.z[1]=new Complex(w[7]);
	X.z[2]=new Complex(w[8]);
	return(X);
    }


    /**graphics objects**/

    public static Complex prolong(Complex z1,Complex z2,double e) {
	Complex w=new Complex((e+1)*z1.x-e*z2.x,(e+1)*z1.y-e*z2.y);
	return(w);
    }


    public static Complex interpolate(Complex z1,Complex z2,double e) {
	Complex w=new Complex((1-e)*z1.x+e*z2.x,(1-e)*z1.y+e*z2.y);
	return(w);
    }





    public static GeneralPath strip(PolyWedge P,int STRIP_NUMBER,double EXTENT) {
	return(strip(P,STRIP_NUMBER,EXTENT,-EXTENT));
    }


    public static GeneralPath strip(PolyWedge P,int STRIP_NUMBER,double EXTENT1,double EXTENT2) {
	Complex[] X=stripData(P,STRIP_NUMBER);
	double e1=EXTENT1;
	double e2=EXTENT2;
	Complex z1=X[0];
	Complex z2=X[1];
	Complex w1=X[2];
	Complex w2=X[3];

	Complex a1=prolong(z1,z2,e1);
	Complex a2=prolong(z1,z2,e2);
	Complex b1=prolong(w1,w2,-e2);
	Complex b2=prolong(w1,w2,-e1);

	GeneralPath gp=new GeneralPath();
	gp.moveTo((float)(a1.x),(float)(a1.y));
	gp.lineTo((float)(a2.x),(float)(a2.y));
	gp.lineTo((float)(b1.x),(float)(b1.y));
	gp.lineTo((float)(b2.x),(float)(b2.y));
	gp.closePath();
	return(gp);
    }



    public static GeneralPath parallelogram(PolyWedge P,int n1,int n2,int SHIFT) {
	Complex[] X1=stripData(P,n1);
	Complex[] X2=stripData(P,n2);

	Complex z1=Vector.findCross2(X1[0],X1[1],X2[0],X2[1]);
	Complex z2=Vector.findCross2(X1[0],X1[1],X2[2],X2[3]);
	Complex z3=Vector.findCross2(X1[2],X1[3],X2[0],X2[1]);
	Complex z4=Vector.findCross2(X1[2],X1[3],X2[2],X2[3]);

	Complex w=Complex.minus(z1,z2);
	w=Complex.times(w,new Complex(SHIFT,0));
	z1=Complex.plus(z1,w);
	z2=Complex.plus(z2,w);
	z3=Complex.plus(z3,w);
	z4=Complex.plus(z4,w);

	GeneralPath gp=new GeneralPath();
	gp.moveTo((float)(z1.x),(float)(z1.y));
	gp.lineTo((float)(z2.x),(float)(z2.y));
	gp.lineTo((float)(z4.x),(float)(z4.y));
	gp.lineTo((float)(z3.x),(float)(z3.y));
	gp.closePath();
	return(gp);
    }




}