package ConvexHull;

import java.util.Vector;

public class PolygonConvexHull {

	private static Vector convex_hull;
	private static int next_vertex;
	private static Point2D[] vertices;
	
	public static Vector computePolygonConvexHull(Vector v) {
		convex_hull = new Vector();
		if (v.size() < 3) return convex_hull;
		computeVertices(v);
		init();
		while (growConvexHull());
		return convex_hull;
	}
	
	private static void init() {
		next_vertex = 0;
		Point2D v1 = vertices[next_vertex++];
		Point2D v2 = vertices[next_vertex++];
		Point2D v3 = vertices[next_vertex++];
		if (eval(v1, v2, v3) > 0) {
			push(v1);
			push(v2);
		}
		else {
			push(v2);
			push(v1);
		}
		push(v3);
		insert(v3);
	}
	
	private static boolean growConvexHull() {
		Point2D v, b, b1, t, t1;
						
		b = (Point2D) convex_hull.elementAt(0);
		b1 = (Point2D) convex_hull.elementAt(1);
		t = (Point2D) convex_hull.elementAt(convex_hull.size()-1);
		t1 = (Point2D) convex_hull.elementAt(convex_hull.size()-2);
		v = vertices[next_vertex++];
		
		// step 2
		while (eval(v, b, b1) >= 0 && eval(t1, t, v) >= 0) {
			if (next_vertex == vertices.length)
				return false;
			v = vertices[next_vertex++];
		}
		
		// step 3
		while (eval(t1, t, v) <= 0) {
			pop();
			t = (Point2D) convex_hull.elementAt(convex_hull.size()-1);
			t1 = (Point2D) convex_hull.elementAt(convex_hull.size()-2);
		}
		push(v);
		
		// step 4
		while (eval(v, b, b1) <= 0) {
			remove();
			b = (Point2D) convex_hull.elementAt(0);
			b1 = (Point2D) convex_hull.elementAt(1);
		}
		
		if (next_vertex == vertices.length)
			return false;
		insert(v);
		return true;
	}
	
	private static void push(Object o) {
		convex_hull.addElement(o);
	}
	
	private static void pop() {
		if (convex_hull.size() > 0)
			convex_hull.removeElementAt(convex_hull.size()-1);
	}
	
	private static void insert(Object o) {
		convex_hull.insertElementAt(o, 0);
	}
	
	private static void remove() {
		if (convex_hull.size() > 0)
			convex_hull.removeElementAt(0);
	}

	private static Point2D bottom(int offset) {
		return (Point2D) convex_hull.elementAt(offset);
	}
	
	private static Point2D top(int offset) {
		return (Point2D) convex_hull.elementAt(convex_hull.size()-1-offset);
	}
	
	private static int eval(Point2D p, Point2D q, Point2D r) {
		return (q.y-p.y)*(r.x-p.x) - (q.x-p.x)*(r.y-p.y);
	}
	
	private static void computeVertices(Vector v) {
		// return vertices, so that the topmost one is second
		// that way first 3 vertices are definitely not colinear
		vertices = new Point2D[v.size()];
		int top = getTopmostVertex(v);
		top = (top == 0) ? vertices.length-1 : top-1;
		for (int i=0; i<v.size(); i++) {
			vertices[i] = (Point2D) v.elementAt(top);
			top = (top + 1) % vertices.length;
		}
	}
	
	private static int getTopmostVertex(Vector vertices) {
		int top = 0;
		Point2D top_vertex = (Point2D) vertices.elementAt(0);
		
		Point2D p;
		for (int i=1; i<vertices.size(); i++) {
			p = (Point2D) vertices.elementAt(i);
			if (p.above(top_vertex)) {
				top = i;
				top_vertex = p;
			}
		}
		return top;
	}

}