import java.awt.*;

public class polygon
{
public vector  N;       // normal
public vector vertex[];// vertices
public int    num;     // number of vertices
public int    max;     // max number of vertices
//public static double  epsilon = 0.136d; // epsilon value necessary to split polygons
public static double  epsilon = 0.025d; // epsilon value necessary to split polygons
public vector color;    // the color of this polygon
    
//--------- optimization ---------
private static vector temp_1 = new vector();
private static vector temp_2 = new vector();
//--------------------------------

    
public polygon(int count, vector c, vector normal)
    {
	color  = c;
	N      = new vector(normal.xyz[0], normal.xyz[1], normal.xyz[2]);
	N.normalize();
	num    = 0;
	max    = count;
	vertex = new vector[max];
    }

public polygon(poly p, vector c)
    {
	color = c;
	num = p.num;
	vertex = new vector[num];
	for(int i=0; i<num; i++)
	    vertex[i] = new vector(p.tvertx[i]);
	if(p.normal != null)
	    {
		N = new vector(p.normal.xyz[0], p.normal.xyz[1], p.normal.xyz[2]);
		N.normalize();
	    }
	else
	    solve_N();
    }

public void solve_N()
    {
	N = new vector();
        vector.subu(vertex[1], vertex[0], temp_1);                         
        vector.subu(vertex[2], vertex[0], temp_2);                         
        vector.cross(temp_1, temp_2, N); // N = (V1-V0)X(V2-V0)
	N.normalize();
    }
    
// I do not test for 3 vertices on the same line, although it is simple to do   
public boolean insert(vector v)
    {
	if(num+1 > max)
	    return false;
	for(int i=0; i<num; i++)
	    if(vertex[i].equals(v))
		return false;
	vertex[num++] = v;
	return true;
    }


// (N . temp_1)/|N|      -- projection of temp_1 on N
// (N . temp_1)/|temp_1| -- projection of N on temp_1
// if all 'N's are the same size ( unit, for example) ,
// I am able to apply epsilon to resolve boundary cases.
// In this program I assume all normals are unit vectors
// (and hope that I actually follow this rule ;-)
public int locate(polygon p)
    {
	N.normalize();
        double prev = epsilon;
        for(int i=0; i<p.num; i++)
            {
		vector.subtract(p.vertex[i], vertex[0], temp_1);
		temp_1.normalize();
		double dotp = vector.dot(N, temp_1);
		if(prev != 0)
		    {
			if((dotp < -epsilon) && (prev > epsilon))
			    return 0;
			else if((dotp > epsilon) && (prev < -epsilon))
			    return 0;
		    }
		if((dotp>epsilon) || (dotp<-epsilon))
		    prev = dotp;
            }
        if(prev<-epsilon)
            return -1; // minus
	return 1;      // plus and in plane
    }

public int locatevertex(vector v, int prev)
    {
	vector.subtract(v, vertex[0], temp_1);
	double dotp = vector.dot(N, temp_1);
	if(dotp < -epsilon)
	    return -1;
	else if(dotp > epsilon)
	    return 1;
	return prev;
    }

public vector locateintersection(vector a, vector b)
    {
	vector.subtract(a, vertex[0], temp_1); // a - p(0)
	vector.subtract(b, a        , temp_2); // b - a
	double tc = -(vector.dot(N, temp_1))/(vector.dot(N, temp_2));
	vector res = new vector();
	vector.scale(temp_2, tc, res);
	vector.add(res, a, res);
	return res;
    }

public polygonpair split(polygon p)
    {
	polygon plus = null;
	polygon minus = null;
	int found;
	for(int k = 0; k<p.num; k++)
	    {
		plus = new polygon(num+1, p.color, N);  // don't know how many vertices it will have, but the max is n+1
		minus = new polygon(num+1, p.color, N); // --/--
		int prev = 0;
		int dotp;
		int index;
		int preindex = -1;
		int k_end = k+p.num;
		found = 0;
		for(int i=k; i<=k_end; i++)
		    {
			index = i%p.num;
			dotp = locatevertex(p.vertex[index], prev);
			if(dotp>0 && prev<0)     // - to + transition
			    {
				// find the intersection, add it to both polygons
				vector v = locateintersection(p.vertex[preindex], p.vertex[index]);
				plus.insert(v);
				plus.insert(p.vertex[index]);
				minus.insert(v);
				found++;
			    }
			else if(dotp<0 && prev>0)// + to - transition
			    {
				// find the intersection, add it to both polygons
				vector v = locateintersection(p.vertex[preindex], p.vertex[index]);
				plus.insert(v);
				minus.insert(v);
				minus.insert(p.vertex[index]);
				found++;
			    }
			else if(dotp>0)
			    plus.insert(p.vertex[index]);
			else
			    minus.insert(p.vertex[index]);
			prev = dotp;
			preindex = index;
		    }
		if(found == 2)
		    break;
	    }
	if(plus != null)
	    {
		if(plus.num<3)
		    plus = null;
		else
		    plus.solve_N();
	    }
	if(minus != null)
	    {
		if(minus.num<3)
		    minus = null;
		else
		    minus.solve_N();
	    }
	return (new polygonpair(plus, minus));
    }

public void dump()
    {
	N.dump("normal ");
	for(int i = 0; i<num; i++)
	    vertex[i].dump("vertex "+i);
    }

public void dump(String comment)
    {
//	N.dump(comment+" normal ");
	for(int i = 0; i<num; i++)
	    vertex[i].dump(comment+" vertex "+i);
    }
}