import util.QuickSort;
import Targa.*;

import java.awt.Point;
import java.util.Vector;
import java.io.*;

/**
* works out the convex hull of the lesion boundary. Takes a boundary file as input
* and outputs the lesion area, the convex hull area and the difference.
* This algorithm came from Cormen et al 1992
* Only method worthy of note is the removeDuplicates method, which is required for the 
* GrahamScan algorithm to work.
*/
final public class GrahamScan {

	private GrahamScan() {}

	public static Vector getConvexHull(Vector p) {
		Vector v= new Vector() ;
		int min = 0;
		Point temp = null;

		Point[] points = new Point[p.size()];
		Point[] pointsTemp = new Point[p.size()-1];
		float[] angles = new float[p.size()-1] ;
		float[] angles2 = new float[p.size()] ;

		min = getStartPoint(p) ;

		temp = (Point)p.elementAt(0);
		points[0] = (Point)p.elementAt(min);
		points[min] = temp;


		for (int i = 1; i < p.size(); i++) {
			points[i] = (Point)p.elementAt(i);
			pointsTemp[i-1] = (Point)p.elementAt(i) ;
			angles[i-1] = theta(points[0].x,points[0].y,points[i].x,points[i].y) ;
		}
		QuickSort.sort(pointsTemp,angles) ;
		System.arraycopy(pointsTemp,0,points,1,pointsTemp.length) ;
		System.arraycopy(angles,0,angles2,1,angles.length) ;

//		points[0] = new Point(x[0],y[0]);
		points = removeDuplicates(points,angles2);
		v.addElement(points[0]) ;
		v.addElement(points[1]) ;
		v.addElement(points[2]) ;

		Point point1,point2,point3;
		for (int i = 3; i < points.length; i++) {
			point1 = (Point)v.lastElement();
			point2 = (Point)v.elementAt(v.size()-2) ;
			point3 = points[i];
			while (ccw(point2,point1,point3) > 0.0) {
				v.removeElementAt(v.size()-1) ;
				point1 = (Point)v.lastElement();
				point2 = (Point)v.elementAt(v.size()-2) ;
				point3 = points[i];

			}
			v.addElement(point3) ;
		}
		Point[] returnArray = new Point[v.size()];
		for (int i = 0; i < v.size(); i++) {
			returnArray[i] = (Point)v.elementAt(i) ;
		}
		return v;
	}



	static float ccw (Point p, Point q, Point r) {

		return (p.x-q.x)*(r.y-q.y) - (p.y-q.y)*(r.x-q.x);
	}



	static float getEuclidDistance(Point p1, Point p2) {
		float euclidDistance = 0.0f;
		euclidDistance = (float)java.lang.Math.sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
		return euclidDistance;
	}
	
	
	//------------------------------------------------------------
	// removeDuplicates. Given an array of points, and the angle each point makes with
	// the `first' point (the one that is definitely on the convex hull), we need to remove
	// points with the same angle, leaving only the point furtherest away from the `first' point.
	//
	static Point[] removeDuplicates(Point[] points, float[] angles) {
		int i = 0, j = 1, count = 1, length;
		float distance1=0f,distance2=0.0f;

		Point[] p2= new Point[points.length];
		Point[] p1= new Point[points.length];
		length = points.length;
		count = 1;

		for (i = 1; i < length;) {
			j = 1;
			if (i < length-1) {
				//---------------------------------------------
				// If the `first' point is duplicated anywhere, skip the copy
				//---------------------------------------------
				if (points[0].x == points[i].x && points[0].y == points[i].y) {
					i++;
					continue;
				}
				//---------------------------------------------
				//If two points have the same angle, work out which
				//point is the furtherest away, and copy that to p2 (the new array of points)
				//---------------------------------------------
				while (i+j < length && angles[i] == angles[i+j]) {
					distance1 = getEuclidDistance(points[0],points[i]) ;
					distance2 = getEuclidDistance(points[0],points[i+j]) ;
	
					if (distance1 > distance2) {
						p2[count] = points[i];
					} else {
						p2[count] = points[i+j] ;
					}
					j++ ;
				}

			}
			//----------------------------------------------------------
			// if a point has no duplicates, copy it into the new array (p2)
			//----------------------------------------------------------
			if (j == 1) p2[count] = points[i] ;
			count ++;
			i+=j;
		}
		
		Point []p3 = new Point[count] ;
		p3[0] = points[0];
		for (i = 1; i < count; i++) {
			p3[i] = p2[i] ;
		}

		return p3;
	}
				
				


	static int getStartPoint(Vector p) {
		int min = 0;
		Point pTemp = null;
		Point pMin = null;
		for (int i = 1; i < p.size(); i++) {
			pTemp = (Point)p.elementAt(i) ;
			pMin = (Point)p.elementAt(min) ;

			if (pTemp.y < pMin.y) min = i;
			if (pTemp.y == pMin.y) {
				if (pTemp.x < pMin.x) min = i;
			}
		}
		return min;
	}



	static float theta(int x1,int y1,int x2,int y2) {
		int dx=0, dy=0, ax=0, ay=0;
		float t=0;

		dx = x2-x1; ax = java.lang.Math.abs(dx) ;
		dy = y2-y1; ay = java.lang.Math.abs(dy) ;

		if ((ax+ay) == 0) t = 0 ;
		else t = dy/(float)(ax+ay) ;
		
		if (dx < 0) t = 2-t;
		else if (dy < 0) t = 4 + t;

		return (t*90);
	}




	static float calculateArea(Vector v) {
		long xt,yt,at ;
		float a ;
		Point p1,p2;
		int numPts;

		a = 0 ;
		xt = 0 ;
		yt = 0 ;
		numPts = v.size() ;
System.out.println("NUM PTS " + numPts);

		int j = 0;
		for (int i=0;i<numPts;i++) {
		      j = (i + 1) % numPts;
			p1 = (Point)v.elementAt(i) ;
			p2 = (Point)v.elementAt(j) ;

		      a += p1.x * p2.y;
		      a -= p1.y * p2.x;
		}
		a /= 2;
		return(a < 0 ? -a : a);
	}






	public static void main(String[] args) {
		Vector boundaryPoints = null;

		if (args[0].equals("iterate") == true) {
			Vector v = new Vector() ;
			FileReader fr = null;
			StreamTokenizer st = null;
			int file = 0, numberOfFiles = 0;
			String dir1=null, dir2=null;

			try {
				fr = new FileReader(args[1]) ;
				st = new StreamTokenizer(fr) ;

				st.nextToken() ;
				numberOfFiles = (int)st.nval;

				st.nextToken() ;
				dir1 = (String)st.sval;
				st.nextToken() ;
				dir2 = (String)st.sval;

				for (int i = 0; i < numberOfFiles; i++) {
					st.nextToken() ;
					file = (int)st.nval;
					v.addElement(new Integer(file)) ;
				}
			} catch (IOException e) {
System.out.println("Read Error in Specification File: ACTION: EXIT") ;
System.exit(1);
			}

			// Create log stream
			FileWriter fw = null;
			PrintWriter log = null;
			try {
				fw = new FileWriter(args[2]) ;
				log = new PrintWriter(fw, true);
			} catch (IOException e) {
System.out.println("Error opening Log File: ACTION: Use System.out") ;
		// true turns automatic flushing on, so every println causes something to print
				log = new PrintWriter(System.out, true) ;
			}

			for (int i = 0; i < numberOfFiles; i++) {
				boundaryPoints = new Vector() ;
				int x=0,y = 0;
				fr = null;
				st = null;

				try {
					fr = new FileReader(dir1+((Integer)v.elementAt(i)).toString()+".bnd");
					st = new StreamTokenizer(fr) ;
					st.nextToken() ;
					int numberOfPoints = (int)st.nval ;
					for (int j = 0; j < numberOfPoints; j++) {
						st.nextToken() ;
						x = (int)st.nval;
						st.nextToken() ;
						y = (int)st.nval;
						boundaryPoints.addElement(new Point(x,y)) ;
					}
				} catch (IOException e) {
System.out.println("Read Error in Specification File:" + fr + " ACTION: continuing") ;
log.println("Read Error in Specification File:" + fr + " ACTION: continuing") ;
					continue;
				}
				log.print(((Integer)v.elementAt(i)).toString()+".bnd");

				Vector convexHull = GrahamScan.getConvexHull(boundaryPoints);
				float area =GrahamScan.calculateArea(boundaryPoints);
				float areaCVH =GrahamScan.calculateArea(convexHull);

log.println("\t\t\t\t\t\t\t"+ area +" " + areaCVH + " " + (areaCVH-area));
			} // END FOR
		} // END IF


    ////////////////////

		else { // Only one iteration
			int x = 0, y = 0;
			try {
				FileReader fr = new FileReader(args[1]) ;
				StreamTokenizer st = new StreamTokenizer(fr);
				st.nextToken() ;
				boundaryPoints = new Vector();
				while (st.nextToken() != st.TT_EOF) {
					st.pushBack();
					st.nextToken();
					x = (int)st.nval;
					st.nextToken();
					y = (int)st.nval;
					boundaryPoints.addElement(new Point(x,y));
				}
			} catch (IOException e) {
System.out.println("Oops " + e) ;
			}

			try {
				TargaPicture tp = new TargaPicture(args[0]) ;
				tp.read() ;
				Vector v = GrahamScan.getConvexHull(boundaryPoints);
				for (int i = 0; i < v.size()-1; i++) {
					tp.addLine(((Point)v.elementAt(i)).x,((Point)v.elementAt(i)).y,
					((Point)v.elementAt(i+1)).x,((Point)v.elementAt(i+1)).y);
				}
				tp.addLine(((Point)v.elementAt(v.size()-1)).x,((Point)v.elementAt(v.size()-1)).y,
				((Point)v.elementAt(0)).x,((Point)v.elementAt(0)).y);

				tp.setBoundary(boundaryPoints);
				float area =GrahamScan.calculateArea(boundaryPoints);
				float areaCVH =GrahamScan.calculateArea(v);

System.out.println("\t\t\t\t\t\t\t"+ area +" " + areaCVH + " " + (areaCVH-area));

				TargaView tv = new TargaView(tp);
			} catch (IOException e) {
System.out.println("Error " + e);
			}
		}
	}
}











