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

public class ConvexIntersector {
    public ConvexIntersector() {}





public static int orientation(Complex z1,Complex z2,Complex z3)
{
  double x1,x2,x3;
  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);
}



    public static int inside(Complex z,Quad Q) {
	int i1,i2,i3;
	int o1,o2;
	for(int i=0;i<4;++i) {
	    i1=(i+0)%4;
	    i2=(i+1)%4;
	    i3=(i+2)%4;
	    o1=orientation(Q.z[i1],Q.z[i2],z);
	    o2=orientation(Q.z[i2],Q.z[i3],z);
	    if(o1!=o2) return(0);
	}

	return(1);
    }


    /**A return of 1 in this routine indicates that the three
       points are very nearly colinear*/



public static int degenerate(Complex z1,Complex z2,Complex z3)
{
    double x1,x2,x3;
    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;
    x3=Math.abs(x1-x2);
    if(x3<.00001) return(1);
    return(0);
}


    /* a return of 1 means that the segments (z1,z2) and (z3,z4)
       nearly determine the same line */

public static int checkSame(Complex z1,Complex z2,Complex z3,Complex z4) {
    if(degenerate(z1,z2,z3)==0) return(0);
    if(degenerate(z1,z2,z4)==0) return(0);
    return(1);
}


    /**checks if the ray (z1,z2) crosses the segment (z3,z4).  1 means yes.*/

public static int checkCross(Complex z1,Complex z2,Complex z3,Complex z4) {
  int test1,test2;
  if(degenerate(z1,z2,z3)==1) return(1);
  if(degenerate(z1,z2,z4)==1) return(1);
  if(orientation(z1,z2,z3)!=orientation(z1,z2,z4)) return(1);
  return(0);
}





    /**assuming that the lines cross, this finds the intersection*/

public static Complex findCross(Complex z1,Complex z2,Complex z3,Complex z4) {
    double x1=z1.x;
    double y1=z1.y;
    double x2=z2.x;
    double y2=z2.y;
    double x3=z3.x;
    double y3=z3.y;
    double x4=z4.x;
    double y4=z4.y;
    double n1=x2*x3*y1 - x2*x4*y1 - x1*x3*y2 + x1*x4*y2 - x1*x4*y3 + x2*x4*y3 + x1*x3*y4 - x2*x3*y4;
    double n2=x2*y1*y3 - x4*y1*y3 - x1*y2*y3 + x4*y2*y3 - x2*y1*y4 + x3*y1*y4 + x1*y2*y4 - x3*y2*y4;
    double d=x3*y1 - x4*y1 - x3*y2 + x4*y2 - x1*y3 + x2*y3 + x1*y4 - x2*y4; 
    Complex w=new Complex(n1/d,n2/d);
    return(w);
}



/**This routine determines if the line (z1,z2) lies on an edge of the polygon. A
   return of 1 means yes.*/

public static int checkEdge(Complex z1,Complex z2,PolyWedge P) {
	Complex z3=new Complex();
	Complex z4=new Complex();
	Complex W=new Complex();
	Complex[] Z=new Complex[2];
	int i2,test;
	int count=0;
	double d;

	for(int i1=0;i1<P.count;++i1) {
	    i2=(i1+1)%P.count;
	    z3=P.z[i1];
	    z4=P.z[i2];
	    test=checkSame(z1,z2,z3,z4);
	    if(test==1) return(1);
	}
	return(0);
}


    /*Find the intersection of a line segment and a polygon.
      The endpoints of the line segment are assumed to be
      outside the polygon*/

    public static Complex[] findIntersect(Complex z1,Complex z2,PolyWedge P) {
	Complex z3=new Complex();
	Complex z4=new Complex();
	Complex W=new Complex();
	Complex[] Z=new Complex[2];
	int i2,test;
	int count=0;
	double d;

	for(int i1=0;i1<P.count;++i1) {
	    i2=(i1+1)%P.count;
	    z3=P.z[i1];
	    z4=P.z[i2];
	    test=checkCross(z1,z2,z3,z4);
	    if(test==1) {
		W=findCross(z1,z2,z3,z4);
		d=1;
		if(count>0) d=Complex.dist(W,Z[count-1]);

		if((count<2)&&(d>0.000000001)) {
                    Z[count]=W;
		    ++count;
		}
	    }
	}
	if(count==0) return(null);
	Complex[] ZZ=new Complex[count];
        for(int i=0;i<count;++i) ZZ[i]=new Complex(Z[i]);
	return(ZZ);
    }



    public static PolyWedge singleChop(Complex z1,Complex z2,Complex z3,PolyWedge P) {

	if(P==null) return(null);
	if(checkEdge(z1,z2,P)==1) return(P);
	Complex[] W=findIntersect(z1,z2,P);


	/**In this case the line is either disjoint from the polygon or
           intersects it in a single vertex */

	if((W==null)||(W.length==1)) {
	       Complex ww=new Complex(0.5*(P.z[0].x+P.z[1].x),0.5*(P.z[0].y+P.z[1].y));
	       if(orientation(z1,z2,z3)==orientation(z1,z2,ww)) return(P);
	       return(null);
	   }

	/**Now we are in the case where the line intersects the polygon in 2 points*/

	Complex zz1=new Complex(W[0]);
	Complex zz2=new Complex(W[1]);
	if(Complex.dist(zz1,zz2)<.000001) return(P);
	PolyWedge Q=new PolyWedge();
	Q.z[0]=zz2;
	Q.z[1]=zz1;
	Q.count=2;
	int coincidence=0;
	for(int i=0;i<P.count;++i) {
	    coincidence=0;
	    if(Complex.dist(zz1,P.z[i])<.00001) coincidence=1;
	    if(Complex.dist(zz2,P.z[i])<.00001) coincidence=1;
	    if(coincidence==0) {
	      if(orientation(zz1,zz2,P.z[i])==orientation(zz1,zz2,z3)) {
		Q.z[Q.count]=P.z[i];
		++Q.count;
	      }
	    }
	}

        Q=makeConvex(Q);
	return(Q);
    }


    /**The first polygon should be a triangle */

    public static PolyWedge wedgeChop(PolyWedge P1,PolyWedge P2) {
	if(P2==null) return(null);
	PolyWedge Q1=singleChop(P1.z[0],P1.z[1],P1.z[2],P2);
	PolyWedge Q2=singleChop(P1.z[0],P1.z[2],P1.z[1],Q1);
	return(Q2);
    }


    public static int findFirst(PolyWedge P) {
	int o1=orientation(P.z[0],P.z[1],P.z[2]);
	int index=2;
	int o2=0;
	for(int i=3;i<P.count;++i) {
	    o2=orientation(P.z[1],P.z[index],P.z[i]);
	    if(o2!=o1) {
		index=i;
	    }
	}
	return(index);
    }


    public static int findLast(PolyWedge P) {
	int o1=orientation(P.z[0],P.z[1],P.z[2]);
	int index=2;
	int o2=0;
	for(int i=3;i<P.count;++i) {
	    o2=orientation(P.z[1],P.z[index],P.z[i]);
	    if(o2==o1) {
		index=i;
	    }
	}
	return(index);
    }



    public static int determineSense(int first,int last,int n) {

	if((first<n)&&(last<n)) {
	    if(first>last) return(1);
	    return(-1);
	}

	if(first==n) {
	    if(last==n-1) return(1);
	    return(-1);
	}

	if(last==n) {
	    if(first==n-1) return(-1);
	    return(1);
	}
	return(0);
    }






/**This routine only works for special polygons, which are not
   too far from being convex.  The vertices v0,v1 are already
   assumed to be in order, and then the vertices v2,v3... are
   assumed to be dihedrally permuted from their correct order.*/


    public static PolyWedge makeConvex(PolyWedge P) {
	if(P.count==3) return(P);

	PolyWedge Q=new PolyWedge();
	Q.count=P.count;
	int first=findFirst(P);
	int last=findLast(P);
	int test=determineSense(first,last,P.count-1);

	Q.z[0]=P.z[0];
	Q.z[1]=P.z[1];

        if(test==+1) {
	  int k=first;
	  for(int i=0;i<P.count-2;++i) {
	    Q.z[i+2]=P.z[k];
	    ++k;
	    if(k>P.count-1) k=2;
	  }
	}

        if(test==-1) {
	  int k=first;
	  for(int i=0;i<P.count-2;++i) {
	    Q.z[i+2]=P.z[k];
	    --k;
	    if(k<2) k=P.count-1;
	  }
	}

	return(Q);
    }


















}