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

/**This is our main polygon class.**/

public class PolyWedge {
    Complex[] z=new Complex[400];
    int count;
    int orbit;
    int strip;
    int history;
    int[] r=new int[2];

    /**constructors**/

    public PolyWedge() {}


    public PolyWedge(PolyWedge Q) {
	this.count=Q.count;
	for(int i=0;i<Q.count;++i) this.z[i]=Q.z[i];
	history=0;
    }

    /**The penrose kite*/

    public static PolyWedge penroseKite() {
	PolyWedge P=new PolyWedge();
	P.count=4;
	P.z[0]=new Complex(0,1);
	P.z[1]=new Complex(-1,0);
	P.z[2]=new Complex(0,-1);
	P.z[3]=new Complex(Math.sqrt(5)-2,0);
	return(P);
    }

    /**the fundamental strip*/
  public static PolyWedge strip(double n) {
      double[] d={-2,2};
      return(strip(n,d));
  }

    /**The top half of the fundamental strip**/
  public static PolyWedge stripTop(double n) {
      double[] d={0,2};
      return(strip(n,d));
  }
    public static PolyWedge strip(double n,double[] d) {
       PolyWedge STRIP=new PolyWedge();
       STRIP.count=4;
       STRIP.z[0]=new Complex(-n,d[0]);
       STRIP.z[1]=new Complex(-n,d[1]);
       STRIP.z[2]=new Complex(n,d[1]);
       STRIP.z[3]=new Complex(n,d[0]);
       return(STRIP);
    }





    /**print routine**/

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


    /**convert to general path**/

    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);
    }


    /**tests if point is inside**/

    public boolean inside(Complex z) {
	GeneralPath gp=this.toGeneralPath();
	if(gp.contains(z.x,z.y)==true) return(true);
	return(false);
    }


    /**returns center of mass**/

    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));
    }


    /**scales the PolyWedge about the fixed point**/

    public PolyWedge scale(Complex FIX,double SIZE) {
	PolyWedge Q=new PolyWedge();
	Q.count=this.count;
	for(int i=0;i<Q.count;++i) Q.z[i]=Complex.scale(FIX,SIZE,this.z[i]);
	return(Q);
    }

    /**Applies a homothety about the center of mass. d=1 is identity**/

    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);
    }

    /**translation**/

    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);
    }

    /**These two routines start with a PolyWedge that
       may have repeated vertices.  The output is a
       PolyWedge with the repeated vertices weeded out.**/

    public PolyWedge trim() {
	PolyWedge Q=new PolyWedge();
	Complex[] LIST=new Complex[this.count];
	int c=0;
	for(int i=0;i<count;++i) {
	    if(onList(z[i],LIST,c)==false) {
		LIST[c]=new Complex(z[i]);
		++c;
	    }
	}
	Q.count=c;
	for(int i=0;i<c;++i) Q.z[i]=new Complex(LIST[i]);
	return(Q);
    }


    public boolean onList(Complex z,Complex[] LIST,int count) {
	for(int i=0;i<count;++i) {
	    if(Complex.dist(z,LIST[i])<.00000001) return(true);
	}
	return(false);
    }

    /** returns index of closest vertex.**/

    public int getClosest(Complex w) {
	double min=100000;
	int index=0;
	for(int i=0;i<count;++i) {
	    double test=Complex.dist(w,z[i]);
	    if(min>test) {
		min=test;
		index=i;
	    }
	}
	return(index);
    }

    /**Assuming that the polygon is already dihedrally ordered,
       this routine returns a specifically counterclockwise ordered
       version of the polygon.**/

    public PolyWedge orient() {
	boolean test=Complex.isPositivelyOriented(z[0],z[1],z[2]);
	if(test==true) return(this);
	PolyWedge Q=new PolyWedge();
	Q.count=this.count;
	for(int i=0;i<this.count;++i) {
	    Q.z[i]=new Complex(this.z[this.count-1-i]);
	}
	return(Q);
    }


    /**This finds the intersection with a horizontal line.
       It assumes that no vertex lies on the horizontal line.*/

    public Complex[] intersectLine(double y) {
	Complex w1=new Complex(-1000,y);
	Complex w2=new Complex(1000,y);
	Complex[] Z=new Complex[2];
	int total=0;
	for(int i=0;i<count;++i) {
	    int i0=i;
	    int i1=(i+1)%count;
            Complex w=Vector.findCross(w1,w2,z[i0],z[i1]);
	    if(Complex.between(w,z[i0],z[i1])==true) {
		Z[total]=new Complex(w);
		++total;
	    }
	}
	if(total!=2) return(null);
	if(Z[0].x<Z[1].x) return(Z);
	Complex[] ZZ={Z[1],Z[0]};
	return(ZZ);
    }



    /**This takes the convex hull.  What makes this
       routine work for us is that we have a bound (4) on
       the possible side directions of our polygons.
       This routine is not robust.*/

    public static PolyWedge cheapHull(PolyWedge P) {
	PolyWedge Q=new PolyWedge();
	int[] n=new int[65];
	for(int i=0;i<65;++i) n[i]=-1;
	Complex u=new Complex();
	for(int i=0;i<64;++i) {
	    double theta=1.0*Math.PI*i/32.0+Math.PI/64.0;
	    u=new Complex(Math.cos(theta),Math.sin(theta));
	    n[i]=extreme(u,P);
	}
	int count=0;
	Q.z[0]=P.z[n[0]];
	++count;
	for(int i=1;i<64;++i) {
	    if((n[i]!=-1)&&(n[i]!=n[i-1])) {
	       Q.z[count]=P.z[n[i]];
	       ++count;
	    }
	}
	Q.count=count;
	Q=Q.trim();
	return(Q);
    }

       
    /**Finds the extreme points in a given direction*/

    public static int extreme(Complex u,PolyWedge P) {
         double test,min;
         int X;
         min=10000.0;
         X=0;
	 Complex v;
         for(int i=0;i<P.count;++i) {
	     v=Complex.times(u,P.z[i]);
	     test=v.y;
            if(test<min) {
             X=i;
	     min=test;
	    }
	 }
	 return(X);
    }


    /**this computes the intersection of two polygons.
       Again, this is not a robust routine.*/ 

    public static PolyWedge merge(PolyWedge P1,PolyWedge P2) {
	PolyWedge Q=new PolyWedge();
	int total=0;
	for(int i=0;i<P1.count;++i) {
	    for(int j=0;j<P2.count;++j) {
		int i0=i;
		int i1=(i+1)%P1.count;
		int j0=j;
		int j1=(j+1)%P2.count; 
		Complex z=Vector.findCross(P1.z[i0],P1.z[i1],P2.z[j0],P2.z[j1]);
		boolean test1=Complex.between(z,P1.z[i0],P1.z[i1]);
		boolean test2=Complex.between(z,P2.z[j0],P2.z[j1]);
		if((test1==true)&&(test2==true)) {
		    Q.z[total]=new Complex(z);
		    ++total;
		}
	    }
	}
	for(int i=0;i<P1.count;++i) {
	    if(P2.inside(P1.z[i])==true) {
		Q.z[total]=new Complex(P1.z[i]);
		++total;
	    }
	}
	for(int i=0;i<P2.count;++i) {
	    if(P1.inside(P2.z[i])==true) {
		Q.z[total]=new Complex(P2.z[i]);
		++total;
	    }
	}
	Q.count=total;
	if(Q.count==0) return(null);
	Q=cheapHull(Q);
	return(Q);
    }




}