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

import java.awt.geom.*;


public class PolyWedge {
    Complex[] z=new Complex[100];
    int count,radius,orbit;
    int history;
    Complex[] X=new Complex[4];  //strip 0 data
    Complex[] w=new Complex[3];  //pinwheel barrier
    int[] slopes=new int[100];

    public PolyWedge() {}

    public PolyWedge(Complex z0,Complex z1,Complex z2) {
    this.count=3;
    this.z[0]=z0;
    this.z[1]=z1;
    this.z[2]=z2;
    }

    public PolyWedge(Complex[] Z,int n) {
	this.count=n;
	for(int i=0;i<n;++i) this.z[i]=new Complex(Z[i]);
    }





    public static PolyWedge regular(int n) {
	PolyWedge X=new PolyWedge();
	X.count=n;
	double fudge=0;
	if(n==10) fudge=0.01;
	for(int i=0;i<n;++i) {
	    double t=2.0*Math.PI*i/n+fudge;
	    X.z[i]=new Complex(Math.cos(t),Math.sin(t));
	}
	return(X);
    }


    /* tt controls the degree of randomness.*/

    public static PolyWedge random(int n,double tt) {
	PolyWedge X=new PolyWedge();
	double[] x=BasicMath.randomList(n,tt);
	X.count=n;
	for(int i=0;i<n;++i) {
	    double t=2.0*Math.PI*x[i];
	    X.z[i]=new Complex(Math.cos(t),Math.sin(t));
	}
	return(X);
    }







    public int nearestVertex(Complex z) {
	int index=-1;
	double min=1000000.0;
	for(int i=0;i<count;++i) {
	    double test=Complex.dist(z,this.z[i]);
	    if(test<min) {
		min=test;;
		index =i;
	    }
	}
	return(index);
    }




    public PolyWedge(PolyVector X) {
	this.count=X.count;
	for(int i=0;i<X.count;++i) {
	    this.z[i]=X.V[i].toComplex();
	}
    }




    public PolyWedge(PolyWedge Q) {
	for(int i=0;i<100;++i) z[i]=new Complex();
	this.count=Q.count;
	for(int i=0;i<Q.count;++i) this.z[i]=Q.z[i];
	for(int i=0;i<2*Q.count;++i) this.slopes[i]=Q.slopes[i];
	for(int i=0;i<3;++i) this.w[i]=Q.w[i];
	for(int i=0;i<4;++i) this.X[i]=Q.X[i];
    }

    public GeneralPath toGeneralPath() {
	GeneralPath gp=new GeneralPath();
	gp.moveTo((float)(z[0].x),(float)(z[0].y));
	for(int i=0;i<count;++i) {
	    gp.lineTo((float)(z[i].x),(float)(z[i].y));
	}
	gp.closePath();
	return(gp);
    }


    public GeneralPath toGeneralPathOpen() {
	GeneralPath gp=new GeneralPath();
	gp.moveTo((float)(z[0].x),(float)(z[0].y));
	for(int i=0;i<count;++i) {
	    gp.lineTo((float)(z[i].x),(float)(z[i].y));
	}
	return(gp);
    }


    public PolyWedge coerce(int a,int b) {
	PolyWedge P=new PolyWedge(this);
	for(int i=0;i<P.count;++i) P.z[i]=P.z[i].coerce(a,b);
	return(P);
    }

    public PolyWedge coerce(int a,int b,int vtx) {
	PolyWedge P=new PolyWedge(this);
	P.z[vtx]=P.z[vtx].coerce(a,b);
	return(P);
    }




    public PolyWedge reflectIn(Complex w) {
	PolyWedge Q=new PolyWedge();
	Q.count=this.count;
	for(int i=0;i<Q.count;++i) {
	    Q.z[i]=w.reflect(this.z[i]);
	}
	return(Q);
    }


    public static PolyWedge vertexReverse(PolyWedge W) {
	PolyWedge Q=new PolyWedge();
	Q.count=W.count;
	for(int i=0;i<Q.count;++i) {
	    Q.z[Q.count-1-i]=new Complex(W.z[i]);
	}
	return(Q);
    }


    public static PolyWedge bigSquare(Complex z,double d) {
	  PolyWedge P=new PolyWedge();
          P.count=4;
	  P.z[0]=Complex.plus(z,new Complex(-d, d));
          P.z[1]=Complex.plus(z,new Complex(-d,-d));
          P.z[2]=Complex.plus(z,new Complex( d,-d));
          P.z[3]=Complex.plus(z,new Complex( d, d));
	  return(P);
    }

    public static PolyWedge conjugate(PolyWedge X) {
	PolyWedge Y=new PolyWedge();
	Y.count=X.count;
	for(int i=0;i<X.count;++i) Y.z[i]=X.z[X.count-i-1].conjugate();
	Y.radius=X.radius;
	Y.history=X.history;
	Y.orbit=X.orbit;
	return(Y);
    }

    public static PolyWedge symmetrize(PolyWedge X,int k) {
	int n=X.count/k;
	if(k*n<X.count) return(X);
	PolyWedge Y=new PolyWedge();
	Y.count=X.count;
	Complex Z=new Complex();
	for(int q=0;q<n;++q) {
	     for(int i=0;i<k;++i) {   
                          double c=Math.cos(2*Math.PI*i/k);
	        double s=Math.sin(2*Math.PI*i/k);
	        Z=new Complex(c,s);
	        Y.z[q+n*i]=Complex.times(Z,X.z[q]);
	    }
	}
	return(Y);
    }




    public Complex findIntersect(Complex z1,Complex z2,double y) {
	Complex z3=new Complex(0,y);
	Complex z4=new Complex(10000,y);
	Complex z5=Vector.findCross2(z1,z2,z3,z4);
	return(z5);
    }


    public double dec(double x) {
	return(x-Math.floor(x+.5));
    }

    public PolyWedge toFundamentalDomain() {
	PolyWedge P=new PolyWedge();
	P.count=count;
	for(int i=0;i<count;++i) {
	    P.z[i]=new Complex(dec(z[i].x),dec(z[i].y));
	}
	return(P);
    }



    public PolyWedge rotate(int k) {
	PolyWedge P=new PolyWedge();
	P.count=this.count;
	for(int i=0;i<P.count;++i) {
	    P.z[i]=this.z[(i+k)%P.count];
	}
	return(P);
    }


    public PolyWedge pivot(int k) {

	PolyWedge P=new PolyWedge();
	Complex w=this.z[k];
	P.count=this.count;
	for(int i=0;i<P.count;++i) {
	    P.z[i]=new Complex(2*w.x-z[i].x,2*w.y-z[i].y);
	}
	return(P);
    }



    public void print() {
	System.out.println("PolyWedge");
	for(int i=0;i<count;++i) z[i].print();
    }



    public Complex getCenter() {
	double x=0;
	double y=0;
	for(int i=0;i<count;++i) {
	    x=x+z[i].x/count;
	    y=y+z[i].y/count;
	}
	return(new Complex(x,y));
    }

    /**A return of 1 means that the polygon is close enough to the origin*/

    public int isWithinRange(double dx,double dy) {
    double xmin=+1000000;
    double xmax=-1000000;
    double ymin=+1000000;
    double ymax=-1000000;
    for(int i=0;i<count;++i) {
	if(xmin>z[i].x) xmin=z[i].x;
	if(xmax<z[i].x) xmax=z[i].x;
	if(ymin>z[i].y) ymin=z[i].y;
	if(ymax<z[i].y) ymax=z[i].y;
    }
    if(xmin>dx) return(0);
    if(ymin>dy) return(0);
    if(xmax<-dx) return(0);
    if(ymax<-dy) return(0);
    return(1);
    }


    //d=1 is identity and d in (0,1) is shrinking

    public PolyWedge homothety(double d) {
	PolyWedge P=new PolyWedge();
	P.count=count;
	Complex Z=getCenter();
	for(int i=0;i<count;++i) {
	    P.z[i]=new Complex((1-d)*Z.x+d*z[i].x,(1-d)*Z.y+d*z[i].y);
	}
	return(P);
    }

    public static int doTheyIntersect(PolyWedge Q1,PolyWedge Q2) {
	PolyVector P1=new PolyVector(Q1.homothety(.99999));
	PolyVector P2=new PolyVector(Q2.homothety(.99999));
	return(ConvexIntersector.doTheyIntersect(P1,P2));
    }


    public static int isSubset(PolyWedge Q1,PolyWedge Q2) {
	PolyWedge P1=new PolyWedge(Q1);
	P1.homothety(.99999);
	GeneralPath gp=Q2.toGeneralPath();
	for(int i=0;i<P1.count;++i) {
	    if(gp.contains(P1.z[i].x,P1.z[i].y)==false) return(0);
	}
	return(1);
    }

    public int contains(Complex z) {
	GeneralPath gp=this.toGeneralPath();
	if(gp.contains(z.x,z.y)==false) return(0);
	return(1);
    }


    public PolyWedge polyChop(PolyWedge X1,PolyWedge X2) {
	PolyVector Y1=new PolyVector(X1);
	PolyVector Y2=new PolyVector(X2);
	PolyVector Y3=ConvexIntersector.polyChop(Y1,Y2);
	PolyWedge X3=Y3.toPolyWedge();
	return(X3);
    }


    public PolyWedge translate(Complex Z) {
	PolyWedge Q=new PolyWedge();
	Q.count=count;
	for(int i=0;i<count;++i) Q.z[i]=Complex.plus(z[i],Z);
	return(Q);
    }


    public static int compare(PolyWedge Q1,PolyWedge Q2) {
      for(int i=0;i<Q1.count;++i) {
	if(Complex.dist(Q1.z[i],Q2.z[i])>.0000001) return(0);
      }
    return(1);
    }

   public static PolyWedge  makeWedge(PolyWedge Q0,int i) {
       int count=Q0.count; 
	PolyWedge Q1=Q0.pivot(i);
	Complex z0=Q0.z[i];

	int i1=(i-1+count)%count;
	int i2=(i+1)%count;

	double d=.1;
	Complex z1=Complex.minus(Q0.z[i1],z0);
	Complex z2=Complex.minus(Q1.z[i2],z0);
	z1=Complex.plus(z0,new Complex(d*z1.x,d*z1.y));
	z2=Complex.plus(z0,new Complex(d*z2.x,d*z2.y));

	PolyWedge W=new PolyWedge();
	W.count=3;
	W.z[0]=new Complex(z0);
	W.z[1]=new Complex(z1);
	W.z[2]=new Complex(z2);
	return(W);
   }

    public int isReversed() {
	int k=Complex.isPositivelyOriented(z[0],z[1],z[2]);
	return(k);
    }

    public int isParallel(int i0,int j0) {
	int n=this.count;
	int i1=(i0+n)%n;
	int j1=(j0+n)%n;
	int i2=i1;
	int j2=j1;
	if(i1==j1) return(0);
	if(i1>j1) {
	    i2=j1;
	    j2=i1;
	}
	int i3=(i2+1)%n;
	int j3=(j2+1)%n;

	Complex z1=this.z[i2];
	Complex z2=this.z[i3];
	Complex z3=this.z[j2];
	Complex z4=this.z[j3];

	Complex w1=Complex.minus(z1,z2);
	Complex w2=Complex.minus(z3,z4);
	Complex w3=Complex.times(w1,w2.conjugate());
	double test=Math.abs(w3.y);
	if(test<.01) return(1);
	return(0);
    }

    public int isParallel() {
	int n=this.count;
	for(int i=0;i<n;++i) {
	    for(int j=i+1;j<n;++j) {
		int test=isParallel(i,j);
		if(test==1) return(1);
	    }
	}
	return(0);
    }




    /**Strip 0 has a canonical cutoff.  The final routine,
       correct region, decides if the point lies in strip 0
       beyond the cutoff*/

    public int insideStrip(Complex u) {
	double a1=Complex.area(this.X[0],this.X[1],u);
	double a2=Complex.area(this.X[2],this.X[3],u);
	if(a1<0) return(0);
	if(a2<0) return(0);
	return(1);
    }

    //1 means yes
    public int beyondMarker(Complex u) {	
        Complex p1=this.w[0];
	Complex p2=Complex.plus(this.w[0],this.w[2]);
	Complex u0=new Complex(0,0);	
	double a0=Complex.area(p1,p2,u0);	
	double a1=Complex.area(p1,p2,u);
	if(a0*a1<0) return(1);
	return(0);
    }


    public int correctRegion(Complex u) {
	int test=insideStrip(u);
	if(test==0) return(0);
	test=beyondMarker(u);
	if(test==0) return(0);
	return(1);
    }

    public int tinyTest() {
	Complex w=getCenter();
	double diam=0;
	for(int i=0;i<count;++i) {
	    double test=Complex.dist(w,z[i]);
	    if(diam<test) diam=test;
	}
	if(diam<.000001) return(1);
	return(0);
    }


}