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



public class PolyhedronSlicer {

    public PolyhedronSlicer () {}

    /**This slices the polyhedron by the X-Y plane**/

    public static PolyWedge basicSlice(Polyhedron X,double t) {
	Vector U1=new Vector(1,0,0);
	Vector U2=new Vector(0,1,0);
	Vector POS=new Vector(0,0,t);
	return(slice(U1,U2,POS,X,false));
    }

    /**This slices the polyhedron by the foliating plane. 
       The foliating plane is the local image of the strip
       Sigma under our compactification map Theta.*/

    public static PolyWedge specialSlice(Polyhedron X,Vector POS) {
	Vector U1=new Vector(GoldenRatio.phi(-1),.5,0);
	Vector U2=new Vector(0,-.5,1);
	return(slice(U1,U2,POS,X,true));
    }



    /**This is the main routine.*/


    public static PolyWedge slice(Vector U1,Vector U2,Vector POS,Polyhedron X,boolean trans) {
	int count=0;	


	PolyWedge P=new PolyWedge();
	  for(int i=0;i<X.count;++i) {
	      for(int j=0;j<X.count;++j) { 
              Complex w=slice(U1,U2,POS,X,i,j,trans);
	        if(w!=null) {
	           P.z[count]=new Complex(w);
	           ++count;
		}
	      }
	  }
	  P.count=count; 
	  if(count==0) return(null);
	  P=PolyWedge.cheapHull(P);
	  P=P.trim();
	  return(P);
    }


    /**This routine does the same thing as the previous one, but it is
       sped up by the inclusion a precomputed list of edges of the polyhedron.**/

    public static PolyWedge slice(int[][] EDGE,Vector U1,Vector U2,Vector POS,Polyhedron X,boolean trans) {
	int count=0;
	PolyWedge P=new PolyWedge();
	for(int a=0;a<EDGE.length;++a) {
	    int i=EDGE[a][0];
	    int j=EDGE[a][1];
	    Complex w=slice(U1,U2,POS,X,i,j,trans);
	    if(w!=null) {
	       P.z[count]=new Complex(w);
	       ++count;
	    }
	}
	P.count=count; 
	if(count==0) return(null);
	P=PolyWedge.cheapHull(P);
	P=P.trim();
	return(P);
    }

    /**This considers a pair of vectors in a polyhedron*/

    public static Complex slice(Vector U1,Vector U2,Vector POS,Polyhedron X,int i,int j,boolean trans) {
            Vector V1=X.V[i];
	    Vector V2=X.V[j];
	    Vector DIR=Vector.cross(U1,U2);
            double t=getWeight(DIR,POS,V1,V2);
	    if((t>=0)&&(t<=1)) {
	       Complex w=project(U1,U2,POS,V1,V2,t,trans);
	       return(w);
	    }
	    return(null);
    }


    /**We consider an affine embedding of the plane into R^3.
       When trans==true, the map is

       (0,0) to POS
       (1,0) to (U1-POS)
       (0,1) to (U2-POS)

        When trans==false, the map is

       (0,0) to (0,0,0)
       (1,0) to U1
       (0,1) to U2
 
       The vector W is assumed to lie in the image.  We
       pull back W under the map, and this is our point.**/


    public static Complex project(Vector U1,Vector U2,Vector POS,Vector W,boolean trans) {
	Vector U3=Vector.cross(U1,U2);
	Matrix M=new Matrix(U1,U2,U3);
	M=M.inverse();
	M=M.transpose();
	Vector X=Matrix.act(M,W);
	Vector X0=Matrix.act(M,POS);
	if(trans==true) X=Vector.minus(X,X0);
	return(new Complex(X.x[0],X.x[1]));
    }



    /**This routine is like the previous one, except that the two
       vectors V1 and V2 lie on either side of the plane in question,
       and the number t tells us which linear combination makes the
       vectors lie in the plane.*/

    public static Complex project(Vector U1,Vector U2,Vector POS,Vector V1,Vector V2,double t,boolean trans) {
	Vector W=Vector.plus(V1.scale(t),V2.scale(1-t));
	return(project(U1,U2,POS,W,trans));
    }


    /**This routine finds where an edge crosses the plane given by the equation
 
               (p - POS) . DIR = 0

    **/

    public static double getWeight(Vector DIR,Vector POS,Vector V1,Vector V2) {
	double z=Vector.dot(POS,DIR);
	double z1=Vector.dot(V1,DIR);
	double z2=Vector.dot(V2,DIR);
	if((z1<z)&&(z2<z)) return(-1);
	if((z1>z)&&(z2>z)) return(-1);
	if(z1==z2) return(1);
	double t=Math.abs((z-z1)/(z2-z1));
	t=1-t;
	if(t<0) t=0;
	return(t);
    }


}