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


/**This class gets all the Eisenstein points touching a given polygon.  The points are ordered
   by proximity*/

public class PolygonFiller {




    /**This gets the list of all the Eisenstein integers which
       intersect the polygon.  These are classified as
       interior (0),  edge interior (1) and vertex (3).
       They are also ordered*/
    

    public static Complex[] totalList(PolygonWrapper P,int mode) {
	Complex[] L0=vertexList(P);
	Complex[] L1=pointList(P,1);
  	Complex[] L2=interiorListFinal(P,mode);
	Complex[] L=ListHelp.merge(L0,L1);
	L=ListHelp.merge(L,L2);
        for(int i=0;i<L.length;++i) L[i].a[2]=i;
	return L;
    }

    public static Complex[] interiorListFinal(PolygonWrapper P,int mode) {
	Complex[] L=pointList(P,0);
	if(mode==0) return L;
	if(mode==1) {
	    Complex[] L2=interiorList(P);
	    if(L2.length==L.length) return L2;
	}
	return L;
    }



    
    public static Complex[] vertexList(PolygonWrapper P) {
	Complex[] LIST=new Complex[P.count];
        int count=0;
	for(int i=0;i<P.count;++i) {
	    LIST[i]=new Complex(P.z[i]);
	    LIST[i].a[0]=2;
	    LIST[i].a[1]=i;
	    LIST[i].a[2]=i;
	}
	return LIST;
    }


    /**when k=1 this gets the Eisenstein points on the edges.
       It is the final routine in this case.
       when k=0 this gets the interior Eisenstein points.
       In this case we do some further ordering to get a nicer list.*/

   
    public static Complex[] pointList(PolygonWrapper P,int k) {
	int[] t=eisBox(P);
	Complex[] LIST=new Complex[1000];
	int c=0;
	
	for(int i=t[0];i<=t[1];++i) {
	    for(int j=t[2];j<=t[3];++j) {
		Complex w=Complex.eis(i,j);
		int[] test=P.classifyPoint(w);
		
		if(test[0]==k) {
		    w.a[0]=test[0];
		    w.a[1]=test[1];
		    w.a[2]=c;
		    LIST[c]=w;
		    ++c;
		}
	    }
	}
	return ListHelp.trim(LIST,c);
    }


    /**This re-enumerates the interior points according to a random start.
       The points are added on as neighbors*/

    public static Complex[] interiorListRaw(PolygonWrapper E) {
	Complex[] W=pointList(E,0);
	int n=W.length;
	int k=(int)(n*Math.random());
	Complex[] Z={W[k]};
	int count=0;
	while((count<1000)&&(Z.length<W.length)) {
	    Z=neighbors(Z,W);
	    ++count;
	}
	return Z;
    }


    public static Complex[] interiorList(PolygonWrapper E) {
	Complex[] Z=interiorListRaw(E);
	boolean test=true;
	while(test==true) {
	  int[] A=crossingIndex(Z);
	  if(A!=null) Z=eliminateCrossing(Z,A);
	  if(A==null) test=false;
	}
	return Z;
    }






    
     public static Complex[] neighbors(Complex[] Z,Complex[] W) {
	Complex[] Z2=ListHelp.trim(Z,Z.length);
	int[] p=ListHelp.randomPermutation(Z2.length);
	for(int i=0;i<Z.length;++i) Z2=neighbors(Z2,W,p[i]);
	return Z2;
    }


    public static Complex[] neighbors(Complex[] Z,Complex[] W,int k) {
	Complex[] LIST=new Complex[6];
	int count=0;
	for(int i=0;i<W.length;++i) {
	    if(ListHelp.onList(W[i],Z)==false) {
	       double d=Complex.dist(Z[k],W[i]);
	       if((d>.9)&&(d<1.1)) {
		   LIST[count]=new Complex(W[i]);
		   ++count;
	       }
	    }
	}
	LIST=ListHelp.trim(LIST,count);
   	return ListHelp.merge(Z,LIST);
    }



    /**This removes a crossing in the path of complex numbers*/

    public static Complex[] eliminateCrossing(Complex[] Z,int[] A) {
	int n=Z.length;
	Complex[] W=new Complex[n];
	int count=0;
	for(int i=0;i<=A[0];++i) {
	    W[count]=new Complex(Z[i]);
	    ++count;
	}
	for(int i=A[2];i>=A[1];--i) {
	    W[count]=new Complex(Z[i]);
	    ++count;
	}
	for(int i=A[3];i<n;++i) {
	    W[count]=new Complex(Z[i]);
	    ++count;
	}
	return W;
    }
    

    /**This finds the indices of the first pair of non-embedded segments*/
    
    public static int[] crossingIndex(Complex[] Z) {
	for(int i0=0;i0<Z.length-1;++i0) {
	for(int i2=i0+1;i2<Z.length-1;++i2) {
	    int i1=i0+1;
	    int i3=i2+1;
	    boolean test=Complex.doTheyCross(Z[i0],Z[i1],Z[i2],Z[i3]);
	    if((i1<i2)&&(test==true)) {
		int[] A={i0,i1,i2,i3};
		return A;
	    }
	}}
	return null;
    }
    



    /**This gets the list of all the Eisenstein integers which
       intersect the polygon.  These are classified as
       interior (0),  edge interior (1) and vertex (3).
       They are also ordered*/
    

    public static Complex[] totalListX(PolygonWrapper P) {
	int[] t=eisBox(P);
	Complex[] LIST=new Complex[1000];
	int c1=0;


	for(int i=0;i<P.count;++i) {
	    LIST[i]=new Complex(P.z[i]);
	    LIST[i].a[0]=2;
	    LIST[i].a[1]=i;
	    LIST[i].a[2]=i;
	}
	c1=P.count;
	
	
	for(int i=t[0];i<=t[1];++i) {
	    for(int j=t[2];j<=t[3];++j) {
		Complex w=Complex.eis(i,j);
		int[] test=P.classifyPoint(w);
		
		if((test[0]!=2)&&(test[0]!=-1)) {
		    w.a[0]=test[0];
		    w.a[1]=test[1];
		    w.a[2]=c1;
		    LIST[c1]=w;
		    ++c1;
		}
	    }
	}
	Complex[] LIST2=new Complex[c1];
	for(int i=0;i<c1;++i) LIST2[i]=new Complex(LIST[i]);
	return LIST2;
    }

    /**This gets the raw form of the bounding box,
       in terms of the integer coordinates of the corners*/

    public static int[] eisBox(PolygonWrapper P) {
	int min0=10000;
	int max0=-10000;
	int min1=10000;
	int max1=-10000;
	for(int i=0;i<P.count;++i) {
	    int[] t=P.z[i].toEis();
	    if(min0>t[0]) min0=t[0];
	    if(min1>t[1]) min1=t[1];
	    if(max0<t[0]) max0=t[0];
	    if(max1<t[1]) max1=t[1];
	}
	int[] y={min0,max0,min1,max1};
	return y;
    }



}
