package Current.plot.Dyadic;
import Current.*;
import Current.basic.*;

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

public class ConvexIntersector {
    public ConvexIntersector() {}

    /**Ethis routine decides if three
points in the plane 
make a positively oriented 
triangle or a negatively
oriented triangle */

public static int orientation(Complex z1,Complex z2,Complex z3)
{
  double x1,x2;
  x1=z1.x*z2.y+z2.x*z3.y+z3.x*z1.y;
  x2=z1.y*z2.x+z2.y*z3.x+z3.y*z1.x;
  if(x1<x2) return(1);
  if(x1>x2) return(-1);
  return(0);
}



    /**this routine decides is a point w1
  nearly lies on the line segment joining
  w2 to w3.  We just test the triangle
  inequality.  1 means that there is
  a near-degeneracy.*/

    public static int nearDegeneracy(Complex z1,Complex z2,Complex z3) {
	double[] d=new double[7];
        d[1]=Complex.dist(z1,z3);
        d[2]=Complex.dist(z1,z2);
        d[3]=Complex.dist(z2,z3);
        d[4]=(d[1]+d[2])/d[3];
        if(d[4]<1.00000000001) return(1);
        return(0);
    }


/**this routine checks if a point z0 lies
   in a region bounded by a convex polygon P*/


public static int checkTouch(Complex z0,Complex[] P) {
  Complex z1=new Complex();
  Complex z2=new Complex();
  int total,local;
  int n=P.length;

  total=0;
  for(int i=0;i<n;++i) {
    z1=P[i];
    if(i<n-1)  z2=P[i+1];
    if(i==n-1) z2=P[0];
    local=orientation(z0,z1,z2);
    int touch=nearDegeneracy(z0,z1,z2);
    if(touch==1) return(1);
    total=total+local;
  }
  if (total<0) total=-total;
  if(total<n) return(0);
  return(1);
}


    /**this routine tests if one polygon is contained
       inside another a return of 1 means yes.*/

public static int checkContains(Complex[] P1,Complex[] P2) {
	for(int i=0;i<P1.length;++i) {
	    if(checkTouch(P1[i],P2)==0) return(0);
	}
	return(1);
}




/**this routine checks if the 
  line segment with endpoints z1,z2 
  intersects the dyadic line segment
  with endpoints z3,z4. 
  0 means segments are disjoint
  1 means that a near-degeneracy caused the test to fail.
  2 means there is a genuine crossing */


public static int checkCross(Complex z1,Complex z2,Complex z3,Complex z4) {
  int test1,test2;
  int on1,on2,on3,on4;

  on1=nearDegeneracy(z1,z3,z4);
  on2=nearDegeneracy(z2,z3,z4);
  on3=nearDegeneracy(z3,z1,z2);
  on4=nearDegeneracy(z4,z1,z2);
  if(on1==1) return(1);
  if(on2==1) return(1);
  if(on3==1) return(1);
  if(on4==1) return(1);

  test1=orientation(z1,z3,z4)*orientation(z2,z3,z4);
  test2=orientation(z1,z2,z4)*orientation(z1,z2,z3);
  if((test1==-1)&&(test2==-1)) return(2);
  return(0);
}


/**this routine returns
0 if the polygons intersect
1 if the first polygon is contained in the second one
2 if the second polygon is contained in the first one
3 if the polygons are disjoint
*/

   public static int checkDisjoint(Complex[] P1,Complex[] P2) {
	if(checkContains(P1,P2)==1) return(1);
	if(checkContains(P2,P1)==1) return(2);

	Complex z1=new Complex();
	Complex z2=new Complex();
	Complex w1=new Complex();
	Complex w2=new Complex();
	int n1=P1.length;
	int n2=P2.length;
	int test=0;				      

  for(int j=0;j<n2;++j) {
  for(int i=0;i<n1;++i) {
    z1=P1[i];
    if(i< n1-1)  z2=P1[i+1];
    if(i==n1-1)  z2=P1[0];
    w1=P2[j];
    if(j< n2-1)  w2=P2[j+1];
    if(j==n2-1)  w2=P2[0];
    test=checkCross(z1,z2,w1,w2);
    if(test!=0) return(0);
  }}
  return(3);
   }



  public static int checkDisjoint(DyadicSquare Q,Complex[] P2) {
      Complex[] P1=Q.toPolygon();
      return(checkDisjoint(P1,P2));
  }



    /**some geometric routines*/

    /**This routine checks if a point is nearer to the
       zeroth vertex of a polygon than to any other*/

    public static int checkNearCorner(Complex Z,Complex[] P2) {
	double dist0=Complex.dist(Z,P2[0]);
	double dist1=0;
	for(int i=1;i<P2.length;++i) {
	    dist1=Complex.dist(Z,P2[i]);
	    if(Complex.dist(P2[0],P2[i])<.000000001) return(0);
	    if(dist1<dist0) return(0);
	}
	return(1);
    }

    /**this routine checks if the whole polygon P1 is
       closer to the zeroth vertex of P2 than to any other vertex.*/

    public static int checkNearCorner(Complex[] P1,Complex[] P2) {
	for(int i=0;i<P1.length;++i) {
	    if(checkNearCorner(P1[i],P2)==0) return(0);
	}
	return(1);
    }


    public static int checkNearCorner(DyadicSquare Q,Complex[] P2) {
	Complex[] P1=Q.toPolygon();
	return(checkNearCorner(P1,P2));
    }


    public static Complex[] getBoundingBox(Complex[] P) {
	double xmin,xmax,ymin,ymax;
	xmin=1;
	ymin=1;
	xmax=0;
	ymax=0;

	for(int i=0;i<P.length;++i) {
	    if(xmin>P[i].x) xmin=P[i].x;
	    if(xmax<P[i].x) xmax=P[i].x;
	    if(ymin>P[i].y) ymin=P[i].y;
	    if(ymax<P[i].y) ymax=P[i].y;
	}
	Complex[] Z=new Complex[2];
	Z[0]=new Complex(xmin,ymin);
	Z[1]=new Complex(xmax,ymax);
	return(Z);
    }

    public static double boxDiameter(Complex[] P) {
	Complex[] Z=getBoundingBox(P);
	double max=Z[1].x-Z[0].x;
	if(max<Z[1].y-Z[0].y) max=Z[1].y-Z[0].y;
	return(max);
    }


    public static DyadicSquare findDyadicFit(Complex[] P) {
	Complex[] B=getBoundingBox(P);
	int k=DyadicRational.content(boxDiameter(P));
	if(k<=1) return(new DyadicSquare(1,1,1));


	DyadicSquare Q=new DyadicSquare(1,1,1);
	for(int kk=k+2;kk>1;--kk) {

	for(int i=1;i<Math.pow(2,kk);++i) {
	  for(int j=1;j<Math.pow(2,kk);++j) {
	      Q=new DyadicSquare(i,j,kk);
	      Complex[] QQ=Q.toPolygon();
	      if(checkContains(B,QQ)==1) return(Q);
	  }}
	}
	return(new DyadicSquare(1,1,1));
    }








}