import java.awt.event.*;
import java.awt.*;
import java.awt.geom.*;


/**This is wrapper class for a list of points in the
   plane.  The main routine in this class is
   taking the convex hull of a finite set of points.
**/


public class PolygonWrapper {
    Complex[] z=new Complex[500];
    int count;

    /**Constructors**/
    public PolygonWrapper() {}

    public PolygonWrapper(PolygonWrapper P) {
	for(int i=0;i<P.count;++i) z[i]=new Complex(P.z[i]);
	count=P.count;
    }


    public PolygonWrapper(int cc,Complex[] zz) {
	this.count=cc;
	for(int i=0;i<cc;++i) {
             z[i]=new Complex(zz[i]);
	}
    }


    /**converting to a path*/

    public Path2D.Double toPath() {
	Path2D.Double gp=new Path2D.Double();
	gp.moveTo(z[0].x,z[0].y);
	for(int i=0;i<count;++i) {
	    gp.lineTo(z[i].x,z[i].y);
	}
	gp.closePath();
	return(gp);
    }

    public Path2D.Double toPathOpen() {
	Path2D.Double gp=new Path2D.Double();
	gp.moveTo(z[0].x,z[0].y);
	for(int i=0;i<count;++i) {
	    gp.lineTo(z[i].x,z[i].y);
	}
	return(gp);
    }

    /**recognizing the closest vertex*/
    
    public int recognize(Complex w) {
	int index=-1;
	double dist=10000;
	for(int i=0;i<count;++i) {
	    double test=Complex.dist(z[i],w);
	    if(test<dist) {
		dist=test;
		index=i;
	    }
	}
	return index;
    }

    /**check if it is embedded*/
    
    public boolean cross(int i,int j) {
	int i0=i;
	int i1=(i+1)%count;
	int j0=j;
	int j1=(j0+1)%count;
	if(i0==j0) return(false);
	if(i0==j1) return(false);
	if(i1==j0) return(false);
	if(i1==j1) return(false);
	Complex I0=z[i0];
	Complex I1=z[i1];
	Complex J0=z[j0];
	Complex J1=z[j1];
	Complex X=Complex.findCross(I0,I1,J0,J1);
	if(X==null) return false;
        double d=Complex.dist(I0,I1);
	d=d-Complex.dist(I0,X)-Complex.dist(I1,X);
	if(d<-.0000001) return(false);  
        d=Complex.dist(J0,J1);
	d=d-Complex.dist(J0,X)-Complex.dist(J1,X);
	if(d<-.0000001) return(false);
	return(true);
    }

    public boolean isEmbedded() {
	int[] I=isEmbeddedRaw();
	if(I==null) return true;
	return false;
    }

    public int[] isEmbeddedRaw() {
	for(int i=0;i<count;++i) {
	    for(int j=0;j<count;++j) {
		if(cross(i,j)==true) {
		    int[] I={i,j};
		    return I;
		}
	    }
	}
	return null;
    }

    /**containment test*/
    public boolean contains(Complex z) {
	Path2D.Double p=this.toPath();
	return p.contains(z.x,z.y);
    }

    /**gets the orientation*/

    public boolean isPositivelyOriented() {
	Complex w=this.center();
	boolean test=Complex.isPositivelyOriented(w,z[0],z[1]);
	return test;
    }
    
    public Complex center() {
	Complex w=new Complex(0,0);
	for(int i=0;i<count;++i) w=Complex.plus(w,z[i]);
	w=w.scale(1.0/count);
	return w;
    }


    

    

    /**the code is interior(0),edge(1),vertex(2) or none (-1)*/
    
    public int[] classifyPoint(Complex q) {
	int[] x={-1,-1};
	boolean test=isInteriorPoint(q);
	if(test==true) {
	    x[0]=0;
	    x[1]=0;
	    return x;
	}
	
	int t=isEdgePoint(q);
	if(t!=-1) {
	    x[0]=1;
	    x[1]=t;
	    return x;
	}

	t=isVertex(q);
	if(t!=-1) {
	    x[0]=2;
	    x[1]=t;
	    return x;
	}
  	return x;
    }

    /**This returns true if the point is an interior point*/
    public boolean isInteriorPoint(Complex q) {
  	if(isVertex(q)!=-1) return false;
	if(isEdgePoint(q)!=-1) return false;
	Path2D.Double p=this.toPath();
	return p.contains(q.x,q.y);
    }
    /**Checks if the point lies on the interior of an edge.
       Either returns the edge number of else -1*/
    
    public int isEdgePoint(Complex q) {
	if(isVertex(q)!=-1) return -1;
        for(int i=0;i<count;++i) {
	    int j=(i+1)%count;
	    double d1=Complex.dist(z[i],z[j]);
	    double d2=Complex.dist(z[i],q);
	    double d3=Complex.dist(z[j],q);
	    if(d2+d3<d1+.000000001) return i;
	}
	return -1;
    }

    /**either returns the vertex number (0,1,...) or else -1.*/
    
    public int isVertex(Complex q) {
	double tol=0.0000000001;
	for(int i=0;i<count;++i) {
	    if(Complex.dist(q,z[i])<tol) return i;
	}
	return -1;
    }


    /**This finds out if an edge incident to the vertex
       crosses an edge of the polygon*/

    public int[] crossingList(Complex w1) {
	if(w1==null) return null;
	int[] list=new int[6];

	int cc=0;
	for(int k=0;k<6;++k) {
	    Complex w2=Complex.plus(w1,Complex.alpha(k));
	    int[] t=classifyPoint(w2);
	    if(t[0]==-1) {
		
	    for(int h1=0;h1<count;++h1) {
		int h2=(h1+1)%count;
		Complex z1=z[h1];
		Complex z2=z[h2];
		if(Complex.doTheyCross(z1,z2,w1,w2)==true) {
		    list[cc]=h1;
		    ++cc;
		    if(cc==6) return list;
		}
	    }
   	    }
	}
	if(cc==0) return null;
	return ListHelp.trim(list,cc);
    }
    /**end of point classification routines*

    

       /**reversing the polygon:  This draws the complement of the polygon*/

    public PolygonWrapper reverse() {
	int index=0;
	double max=-100000;
	for(int i=0;i<this.count;++i) {
	    if(z[i].y>max) {
		max=z[i].y;
		index=i;
	    }
	}
	Complex[] w=new Complex[this.count+8];
	for(int i=0;i<this.count;++i) {
	    int j=(i+index)%count;
	    w[i]=new Complex(this.z[j]);
	}
	int c=this.count;
	w[c]=new Complex(w[0]);
	w[c+1]=new Complex(w[c].x,w[c].y+100);
	w[c+2]=new Complex(w[c].x+100,w[c].y+100);
	w[c+3]=new Complex(w[c].x+100,w[c].y-100);
	w[c+4]=new Complex(w[c].x-100,w[c].y-100);
	w[c+5]=new Complex(w[c].x-100,w[c].y+100);
	w[c+6]=new Complex(w[c].x,w[c].y+100);
	w[c+7]=new Complex(w[c]);
	PolygonWrapper P=new PolygonWrapper(c+7,w);
	return P;
    }

    

    /**printout**/

    public void print() {
	System.out.println("count "+count);
	for(int i=0;i<count;++i) z[i].print();
    }

}

