package Current.popups.Deg100;
import Current.*;
import java.applet.Applet;
import java.awt.event.*;
import java.awt.*;
import java.awt.geom.*;
import java.math.*;


/**This is a self contained file which verifies that our polygon list for the
  100 degree theorem makes a covering.  There is some overlay between the
  geometric routines here and the ones in the Deg100IntegerPolygon class.
  The largest denominator we see is 2^18, but we need to allow for doing
  at most 9 subdivisions, so we multiply by the larger 2^27.*/


public class Deg100CoveringPolygon {
    BigInteger[] K1=new BigInteger[8];
    BigInteger[] K2=new BigInteger[8];
    int[] right=new int[8];
    int n;
    int age;
    int index;


    /**Constructor routines.  Basically we take a dyadic polygon and inflate it by 2^27**/


    public Deg100CoveringPolygon() {}


    public Deg100CoveringPolygon(Deg100Polygon P) {
	this.n=P.n;
	for(int i=0;i<P.n;++i) {
	    K1[i]=amplify(P.k1[i],P.n1[i]);
	    K2[i]=amplify(P.k2[i],P.n2[i]);
	    BigInteger TEST0=new BigInteger("134217728");
	    BigInteger TEST1=K1[i].add(K2[i]);
	    if(TEST1.compareTo(TEST0)==0) right[i]=1;
	}
    }

    //this produces a line segment
    public Deg100CoveringPolygon(Deg100CoveringPolygon Y,int k) {
	int i=k;
	int j=k+1;
	if(j==Y.n) j=0;
	K1[0]=Y.K1[i];
	K2[0]=Y.K2[i];
	K1[1]=Y.K1[j];
	K2[1]=Y.K2[j];
	right[0]=0;
	right[1]=0;
	n=2;
	age=0;
	BigInteger TEST0=new BigInteger("134217728");
	BigInteger TEST1=K1[0].add(K2[0]);
	if(TEST1.compareTo(TEST0)==0) right[0]=1;	
	BigInteger TEST2=K1[1].add(K2[1]);
	if(TEST2.compareTo(TEST0)==0) right[1]=1;
    }

    public BigInteger amplify(int k,int n) {
	Integer K=new Integer(k);
	BigInteger BIG=new BigInteger("2");
	BIG=BIG.pow(27-n);
	BigInteger X=new BigInteger(K.toString());
        X=X.multiply(BIG);
	return(X);
    }

    public Deg100CoveringPolygon[] MasterList(Deg100Data D) {
	Deg100CoveringPolygon[] ML=new Deg100CoveringPolygon[222];
	for(int i=1;i<=221;++i) {
            ML[i]=new Deg100CoveringPolygon(D.P[i]);
	    ML[i].index=i;
	}
	return(ML);
    }









    /**geometric routines for checking intersections*/



    public static int orientation(BigInteger x1,BigInteger y1,BigInteger x2,BigInteger y2,BigInteger x3,BigInteger y3)
{
    BigInteger X1=BigInteger.ZERO;
    X1=X1.add(x1.multiply(y2));
    X1=X1.add(x2.multiply(y3));
    X1=X1.add(x3.multiply(y1));

    BigInteger X2=BigInteger.ZERO;
    X2=X2.add(y1.multiply(x2));
    X2=X2.add(y2.multiply(x3));
    X2=X2.add(y3.multiply(x1));
    return(X1.compareTo(X2));
}


    //tests if these points come in order on a line segment
    public static int between(BigInteger x1,BigInteger y1,BigInteger x2,BigInteger y2,BigInteger x3,BigInteger y3) {
	int test=orientation(x1,y1,x2,y2,x3,y3);
	if(test!=0) return(0);  //not collinear
	if(x1.compareTo(x2)*x2.compareTo(x3)==1) return(1);  //X ordering is correct, all unequal
	if(y1.compareTo(y2)*y2.compareTo(y3)==1) return(1);  //Y ordering is correct, all unequal
	if((x1.compareTo(x2)==0)&&(y1.compareTo(y2)==0)) return(1); //first two points agree
	if((x3.compareTo(x2)==0)&&(y3.compareTo(y2)==0)) return(1); //last two points agree
	return(0);
    }


    //checks if the point (x,y) is on the polygon
public int checkOn(BigInteger x,BigInteger y) {
    int local=0;
  for(int i=0;i<n;++i) {
      int j=i+1;
      if(j==n) j=0;
      local=between(K1[i],K2[i],x,y,K1[j],K2[j]);
      if(local==1) return(1);

  }
  return(0);
}


    //checks if the point (x,y) is inside the polygon
public int checkInside(BigInteger x,BigInteger y) {
  int total,local;
  total=0;
  local=0;
  for(int i=0;i<n;++i) {
      int j=i+1;
      if(j==n) j=0;
      local=orientation(x,y,K1[i],K2[i],K1[j],K2[j]);
      total=total+local;
  }
  if (total<0) total=-total;
  if(total<n) return(0);
  return(1);
}


//checks if a segment X is contained in one of the polygons

    public int checkInside(Deg100CoveringPolygon[] ML,Deg100CoveringPolygon X,int omit) {
	int test=0;
	for(int i=1;i<=221;++i) {
	  if(i!=omit) {
	      Deg100CoveringPolygon Y=ML[i];

	    if((X.right[0]==0)&&(X.right[1]==0)) {
	       if((Y.checkInside(X.K1[0],X.K2[0])==1)&&(Y.checkInside(X.K1[1],X.K2[1])==1)) return(i);
	    }

	    if((X.right[0]==1)&&(X.right[1]==0)) {
	       if((Y.checkOn(X.K1[0],X.K2[0])==1)&&(Y.checkInside(X.K1[1],X.K2[1])==1)) return(i);
	    }

	    if((X.right[0]==0)&&(X.right[1]==1)) {
	       if((Y.checkInside(X.K1[0],X.K2[0])==1)&&(Y.checkOn(X.K1[1],X.K2[1])==1)) return(i);
	    }

	    if((X.right[0]==1)&&(X.right[1]==1)) {
	      return(1);
	    }
	  }
	}
	return(0);
    }









    //NOW FOR THE COVERING ALGORITHM


    //subdivides a segment in half

    public Deg100CoveringPolygon subdivide1() {
	Deg100CoveringPolygon P=new Deg100CoveringPolygon();
	P.K1[0]=this.K1[0];
	P.K2[0]=this.K2[0];
	P.K1[1]=this.K1[0].add(this.K1[1]);
	P.K1[1]=P.K1[1].divide(new BigInteger("2"));
	P.K2[1]=this.K2[0].add(this.K2[1]);
	P.K2[1]=P.K2[1].divide(new BigInteger("2"));
	P.right[0]=this.right[0];
	P.right[1]=0;
	if(right[0]+right[1]==2) P.right[1]=1;



	P.n=2;
	P.age=this.age+1;
	return(P);
    }

    public Deg100CoveringPolygon subdivide2() {
	Deg100CoveringPolygon P=new Deg100CoveringPolygon();
	P.K1[1]=this.K1[1];
	P.K2[1]=this.K2[1];
	P.K1[0]=this.K1[0].add(this.K1[1]);
	P.K1[0]=P.K1[0].divide(new BigInteger("2"));
	P.K2[0]=this.K2[0].add(this.K2[1]);
	P.K2[0]=P.K2[0].divide(new BigInteger("2"));
	P.right[1]=this.right[1];
	P.right[0]=0;
	if(right[0]+right[1]==2) P.right[0]=1;
	P.n=2;
	P.age=this.age+1;
	return(P);
    }



    /*goes through a list of polygons and decides if the jth edge of the ith
      polygon in the list is covered by the other polygons on the list*/

    public int[] coveringAlgorithm(Deg100CoveringPolygon[] ML,int i,int j) {
	int[] record=new int[30];
	record[0]=0;
	Deg100CoveringPolygon[] X=new Deg100CoveringPolygon[30];
	X[0]=new Deg100CoveringPolygon(ML[i],j);
	int X_N=1;

	while(X_N>0) {
	    Deg100CoveringPolygon A=X[X_N-1];
	    int test=checkInside(ML,A,i);
	    if(test>0) {
		int match=0;
 		for(int jj=0;jj<record[0];++jj) if(test==record[jj]) match=1;
		if(match==0) {
                    record[record[0]+1]=test;
		    ++record[0];
		}
                --X_N;
	    }
	    if(test==0) {
		X[X_N-1]=A.subdivide1();
		X[X_N-0]=A.subdivide2();



		++X_N;
		if(A.age>=10) {record[0]=0;return(record);}
	    }
	}
	return(record);
    }


    /*applies the above algorithm to each of the edges of the polygon*/
        public int[][] coveringAlgorithm(Deg100Data D,int i) {
	    Deg100CoveringPolygon[] ML=MasterList(D);
        int[][] record=new int[10][30];
	for(int ii=0;ii<D.P[i].n;++ii) {
            record[ii+1]=coveringAlgorithm(ML,i,ii);
	    if(record[ii+1][0]==0) {record[0][0]=0;return(record);}
	}
	record[0][0]=D.P[i].n;
	return(record);
    }

}