import java.awt.Point;
import java.awt.Color;

/**
 * Abstract representation of a polygon.
 * Includes code for clipping.
 * Subclasses need to provide implementation of drawing.
 */

abstract public class CG1Polygon
{
	public static final int LEFT = 0;
	public static final int RIGHT = 1;
	public static final int BOTTOM = 2;
	public static final int TOP = 3;
	public static final int X = 0;
	public static final int Y = 1;
	public static final int Z = 2;

	/// unclipped vertices (in screen coordinates)
	protected CG1Point[] vertices;

	/// clipped vertices (in screen coordinates)
	protected int[][] clipped;

	/// depths associated with the vertices
	protected double[] depth;

	protected int numVertex;
	protected Color color;

	protected Point wMin, wMax;
	protected int cnt;
	protected CG1Point[] first;
	protected CG1Point[] s;

	public CG1Polygon (CG1Point[] _vertices, Color _color)
	{
		vertices = _vertices;
		color = _color;

		numVertex = vertices.length;

		clipped = new int[2*numVertex + 1][2];
		depth = new double[2*numVertex + 1];

		first= new CG1Point[4];
		s= new CG1Point[4];
	}

	/**
	 * Draw the clipped polygon.
	 */

	abstract protected void drawClipped (CG1Canvas canvas);

	/**
	 * Clip vertices of the polygon, then call the specific method for drawing.
	 */

	public void draw (CG1Canvas canvas)
	{
		clip (canvas);

		drawClipped (canvas);
	}

	/**
	 * Find out if a point is inside the clipping window, as seen from the specified edge.
	 */

	protected boolean inside (CG1Point point, int edge)
	{
		/**
		 * TODO 2:
		 * - Implement this method.
		 */
		CG1Point p=point;
		//System.out.println("insidep:"+p+"||Edge:"+edge);
		switch (edge){
		case LEFT: if(p.x<wMin.x) {return false;}  break;// else { return true; } //linke ClippingGrenze wird ueberprueft
		case RIGHT: if(p.x>wMax.x){ return false;} break; // else { return true; } //rechte clippingGrenze
		case BOTTOM: if(p.y<wMin.y){ return false;} break;// else {return true; }//unten
		case TOP: if(p.y>wMax.y) {return false;} break;// else {return true; }//oben
		}
		return true;
	}

	/**
	 * Find out if the line between two vertices cross the specified edge.
	 */

	protected boolean cross (CG1Point p1, CG1Point p2, int edge)
	{
		/**
		 * TODO 2:
		 * - Implement this method.
		 */
		CG1Point p1_=p1;
		CG1Point p2_=p2;
		if (inside(p1_, edge)==inside(p2_, edge)){
			return false; //wenn inside fuer beide Pkte das gleiche ergibt 
		}
		return true;
	}

	/**
	 * Calculate intersection point of a line and a specified edge.
	 */

	protected CG1Point intersect (CG1Point p1, CG1Point p2, int edge)
	{
		/**
		 * TODO 2:
		 * - Implement this method.
		 * - Note that our points have a z-component, which should also be set correctly for an intersection point!
		 *   To do this, calculate an interpolated value at the right distance between the z values of p1 and p2.
		 *   (This is an addition to the algorithm implementation in the Hearn&Baker book.)
		 */

		CG1Point ipt=new CG1Point(0.0, 0.0, 0.0);
		double t;  //Verhaeltnis groesserem Dreieck zu kleinerem
		double s;
		switch (edge){
		case LEFT:
			t=(wMin.x-p1.x)/(p2.x-p1.x);
			ipt.x=wMin.x;
			ipt.y=p1.y+t*(p2.y-p1.y);
			ipt.z=p1.z+t*(p2.z-p1.z);
			break;
		case RIGHT:
			t=(wMax.x-p1.x)/(p2.x-p1.x);
			ipt.x=wMax.x;
			ipt.y=p1.y+t*(p2.y-p1.y);
			ipt.z=p1.z+t*(p2.z-p1.z);
			break;
		case BOTTOM:
			t=(wMin.y-p1.y)/(p2.y-p1.y);
			ipt.y=wMin.y;
			ipt.x=p1.x+t*(p2.x-p1.x);
			ipt.z=p1.z+t*(p2.z-p1.z);
			break;
		case TOP:
			t=(wMax.y-p1.y)/(p2.y-p1.y);
			ipt.x=p1.x+t*(p2.x-p1.x);
			ipt.y=wMax.y;
			ipt.z=p1.z+t*(p2.z-p1.z);
			break;
		}
		if (edge<4) {
			return(ipt);
 		}else{ 
			return(null);
		}
	}

	/**
	 * Clip a point to the specified edge.
	 */

	protected void clipPoint (CG1Point point, int edge)
	{
		/**
		 * TODO 2:
		 * - Implement clipping using the Sutherland-Hodgeman algorithm.
		 * - Note that our points have a z-components. To 'output' a final clipped point,
		 *   put its x/y-coordinates into the clipped[] array, and its associated z-coordinate into depth[].
		 *   (This is an addition to the algorithm implementation in the Hearn&Baker book.)
		 */
		CG1Point p=point;
		//System.out.println("clipPointp:"+p);
		if (first[edge]==null){
			first[edge]=p; //erster Punkt, der bei der Kante ueberprueft wird, wird in das first[] gespeichert
		}else{ //wenn schon ein Punkt an der Kante behandelt worden ist
			//System.out.println("cross:"+(cross(p, s[edge], edge)));
			if (cross(p, s[edge], edge)){ //schneide die aktuelle Kante die vorherige an der Kante behandelte?
				CG1Point ipt = intersect(p, s[edge], edge); //Schnittpunkt wird ausgerechnet
				//System.out.println("intersect ipt:"+ipt);
				if (edge<TOP){ //wenn die zu ueberpruefende Kante nicht Top ist
					clipPoint(ipt, edge+1); //Funktion wird rekursiv aufgerufen mit dem Schnittpunkt und der naechsten Kante
				}else{
					clipped[cnt][X]=(int)ipt.x;//ausgabe in das clipped[][]
					clipped[cnt][Y]=(int)ipt.y;
					depth[cnt]=ipt.z;
			        cnt++;//Kantencounter wird erhoeht
				}
			}
		}
		
		
		s[edge]=p;//aktueller Punkt wird fuer diese Kante gespeichert
		if (inside(p, edge)){ //wenn diser Punkt innerhalb der clippingkante ist
			if (edge <TOP){ //und die Kante nicht TOP ist
				clipPoint(p, edge+1); //Funktion wird rekursiv fuer die naechste Kante aufgerufen
			}else{ 
				clipped[cnt][X]=(int)p.x;
				clipped[cnt][Y]=(int)p.y;
				depth[cnt]=p.z;
				cnt++; //Kantencounter wird erhoeht
			}
		}
		//System.out.println("first["+edge+"]:"+first[edge]);
		//System.out.println("s["+edge+"]:"+s[edge]);
	}
	
	

	/**
	 * Finish the clipping procedure.
	 */

	protected void closeClip ()
	{
		/**
		 * TODO 2:
		 * - Implement clipping using the Sutherland-Hodgeman algorithm.
		 * - Note that our points have z-components. To 'output' a final clipped point,
		 *   put its x/y-coordinates into the clipped[] array, and its associated z-coordinate into depth[].
		 *   (This is an addition to the algorithm implementation in the Hearn&Baker book.)
		 * - There is also a bug in the implementation of the book: In closeClip(), the final segment of the polygon 
		 *   should only be clipped against an edge, if we clipped against that edge at least once before. Add an
		 *   if-statement to check for this. If we do not do this, the algorithm will fail for any polygon that lies
		 *   completely outside an edge.
		 */
		for (int edge=LEFT; edge <=TOP;  edge++){
		if (first[edge]!=null){ 
			if (cross(s[edge], first[edge], edge)){ //schneidet die Linie aus erster und letzter fuer die Clippingkante gespeicherten Punkte die Clippingkante
				CG1Point pt=intersect(s[edge], first[edge], edge); //Schnittpunkt berechnet 
				if (edge <TOP){
					clipPoint(pt, edge); //clipPointfunktion fuer schnittpunkt und clippingkante
				}else{
					clipped[cnt][X]=(int)pt.x;
					clipped[cnt][Y]=(int)pt.y;
					depth[cnt]=pt.z;
					cnt++;
				}
			}
		}}
	}

	/**
	 * Clip all vertices of this polygon.
	 */

	protected void clip (CG1Canvas canvas)
	{
		wMin = new Point (1, 1);
		wMax = new Point (canvas.getWidth()-2, canvas.getHeight()-2);

		/**
		 * TODO 2:
		 * - Implement clipping using the Sutherland-Hodgeman algorithm.
		 * - The numVertex member variable contains the number of vertices in this polygon.
		 *   Be sure to update it accordingly after clipping is complete.
		 */
		
		int nClip=4;
		for (int i=0; i<nClip; i++){//initialisierung der first und s arrays mit null
			first[i]=null;
			s[i]=null;
		}

		cnt=0;
		
		for (int k=0; k<numVertex; k++){
			//System.out.println("vertice["+k+"]:"+vertices[k]);
			clipPoint(vertices[k], LEFT);
			//System.out.println("vertice["+k+"] nach Clip:"+vertices[k]);
		}
		closeClip();
		numVertex=cnt;//Aktualisierung der Punktanzahl des sichtbaren Polygons
		
		/*for (int i=0; i<numVertex; i++)
		{
			clipped[i][X] = (int)vertices[i].x;
			clipped[i][Y] = (int)vertices[i].y;
		}*/
	}

	/**
	 * Debug output.
	 */

	public void print_vertices ()
	{
		for (int i=0; i<numVertex; i++)
		{
			System.out.println ("Point " + i + ": X=" + vertices[i].x + " Y=" + vertices[i].y + " Z=" + vertices[i].z);
		}
		System.out.println ();
	}

	/**
	 * Debug output.
	 */

	public void print_clipped ()
	{
		for (int i=0; i<numVertex; i++)
		{
			System.out.println ("Point " + i + ": X=" + clipped[i][X] + " Y=" + clipped[i][Y]);
		}
		System.out.println ();
	}
}