package real;

import psplot.*;

// an array of vertices
public class RealPolygon {
	public RealPoint b[];
	
	public RealPolygon(int n) {
		b = new RealPoint[n];
	}
	
	public RealPolygon(RealPoint B[]) {
		b = B;
	}
	
	// Sutherland-Hodgman algorithm
	public RealPolygon clippedTo(RealLine ell) {
		// returns the polygon clipped to Ax + By <= C
		double A = ell.A, B = ell.B, C = ell.C;
		int n = b.length;
		// System.out.println("n = " + n);
		int m = 0;
		RealPoint out[] = new RealPoint[2*n];
		RealPoint P = b[n-1];
		double cP = A*P.x + B*P.y;
		for (int i=0;i<n;i++) {
			RealPoint Q = b[i];
			double cQ = A*Q.x + B*Q.y;
			double t;
			if (cP <= C) {
				// P in
				if (cQ <= C) {
					// Q in
					out[m++] = Q;
				} else {
					// Q out
					t = (C - cP)/(cQ - cP);
					RealPoint R = RealPoint.interpolate(t, P, Q);
					out[m++] = R;
				}
			} else {
				// cP > C: P out
				if (cQ <= C) {
					// Q in
					t = (C - cP)/(cQ - cP);
					RealPoint R = RealPoint.interpolate(t, P, Q);
					out[m++] = R;
					out[m++] = Q;
				} /* else {
					// Q out: do nothing 
				} */ 
			}
			P = Q;
			cP = cQ;
		} 
		RealPoint S[] = new RealPoint[m];
		for (int i=0;i<m;i++) S[i] = out[i];
		return(new RealPolygon(S));
	}
	
	public int length() {
		return(b.length);
	} 
	
	public RealPolygon clippedTo(ConvexPolygon cp) {
		int n = b.length;
		RealPoint p[] = new RealPoint[n];
		for (int i=0;i<cp.ell.length;i++) {
			// check: P could be small, even empty
			p[i] = b[i];
		}
		RealPolygon P = new RealPolygon(p);
		int i = 0;
		while (i < n && P.length() > 0) {
			P = P.clippedTo(cp.ell[i]);
			i++;
		}
		return(P);
	}
	
	public RealPolygon intersection(RealLine ell) {
		// returns the array of segments of the intersection
		// as a polygon of even size
		double A = ell.A, B = ell.B, C = ell.C;
		int n = b.length;
		int m = 0;
		RealPoint out[] = new RealPoint[2*n];
		RealPoint P = b[n-1];
		double cP = A*P.x + B*P.y;
		for (int i=0;i<n;i++) {
			RealPoint Q = b[i];
			double cQ = A*Q.x + B*Q.y;
			double t;
			if (cP <= C) {
				// P in
				if (cQ <= C) {
					// Q in
					// out[m++] = Q;
				} else {
					// Q out
					t = (C - cP)/(cQ - cP);
					RealPoint R = RealPoint.interpolate(t, P, Q);
					out[m++] = R;
				}
			} else {
				// cP > C: P out
				if (cQ <= C) {
					// Q in
					t = (C - cP)/(cQ - cP);
					RealPoint R = RealPoint.interpolate(t, P, Q);
					out[m++] = R;
					// out[m++] = Q;
				} /* else {
					// Q out: do nothing 
				} */ 
			}
			P = Q;
			cP = cQ;
		} 
		RealPoint S[] = new RealPoint[m];
		for (int i=0;i<m;i++) S[i] = out[i];
		return(new RealPolygon(S));
	}
	
	public PlotPath path(PlotCanvas c) {
		PlotPath p = new PlotPath(c);
		int n = b.length;
		p.moveto(b[0]);
		for (int i=1;i<b.length;i++) {
			p.lineto(b[i]);
		}
		return(p);
	}
	
	// returns the nearest point of the polygon, assumed to be convex
	public RealPoint projection(RealPoint P) {
		// look in turn at each vertex and each edge
		// the vertex traps all P with P = au + bv, a, b >= 0
		// at least 1 vertex assumed 
		int n = b.length;
		switch (n) {
			case 0:
				return(P);
			case 1:
				return(b[0]);
			case 2:
				double A = b[1].x - b[0].x, 
				B = b[1].y - b[0].y, 
				C0 = A*b[0].x + B*b[0].y, 
				C1 = A*b[1].x + B*b[1].y,
				C = A*P.x + B*P.y;
				if (C <= C0) return(b[0]);
				if (C > C1) return(b[1]);
				// C1 now > C0
				double t = (C - C0)/(C1 - C0);
				return(RealPoint.interpolate(t, b[0], b[1]));
			default: 
				break;
		}
		// now n > 2
		RealPoint cp = b[n-2];
		RealPoint next = b[n-1];
		for (int i=0;i<n;i++) {
			RealPoint last = cp;
			cp = next;
			next = b[i];
			// we are looking at b[i-2], b[i-1], b[i]
			// 1: last - current, 0: next - current
			double A1 = last.x - cp.x, B1 = last.y - cp.y, C1 = A1*cp.x + B1*cp.y;
			double A0 = next.x - cp.x, B0 = next.y - cp.y, C0 = A0*cp.x + B0*cp.y;
			// [A0, B0]: cp -> next, [A1, B1] cp -> last
			double D0 = A0*P.x + B0*P.y;
			double D1 = A1*P.x + B1*P.y;
			if ((D0 <= C0) && (D1 <= C1)) {
				// nearest point is the vertex cp
				return(cp);
			}
			double E0 = A0*next.x + B0*next.y;
			C1 = B0*cp.x - A0*cp.y;
			// [B, -A] faces out
			D1 = B0*P.x - A0*P.y;
			if (C0 < D0 && D0 < E0 && C1 <= D1) {
				// projection on the face
				double t = (D0 - C0)/(E0 - C0);
				RealPoint Q = RealPoint.interpolate(t, cp, next);
				return(Q);
			}
		}
		return(P);
	}
	
	public RealPolygon translatedBy(Real2DVector v) {
		int n = b.length;
		RealPoint p[] = new RealPoint[n];
		for (int i=0;i<n;i++) {
			p[i] = b[i].translatedBy(v);
		}
		return(new RealPolygon(p));
	}
	
	public String toString() {
		String s = new String("");
		for (int i=0;i<b.length;i++) {
			s = s + ":" + b[i];
		}
		return(s);
	}
}