//******************************************************************************
// hull.java:	Applet
//
//******************************************************************************
import java.applet.*;
import java.awt.*;
import java.util.Stack;

//==============================================================================
// Main Class for applet hull
//
//==============================================================================
public class hull extends Applet
{
	
	Label L1;
	Label L2;
	Label L3;
	Label L4;
	Label Status;
	Label TurnLabel;				// To display the team's turn
	int maxpts = 250;				// Max # of points
	int rptcount = 3;				// Counter for # of points
	int bptcount = 3;
	point[] bluepoints = new point[maxpts+1];
	point[] redpoints = new point[maxpts+1];	// Array of red points
	Button clear;
	Image themap;
	Choice mapsel;
	int appwidth = 640;			//Height and width of the applet
	int appheight = 400;
	int mapwidth = 620;
	int mapheight = 300;
	Image offScreenImage;
	Graphics offScreenGraphic;
	int maxdist = 50;
	point closestpoint;	
	int Turn=0;			//Keeps track of whose turn it is

	// hull Class Constructor
	//--------------------------------------------------------------------------
	public hull()
	{
		// TODO: Add constructor code here
	}

	// APPLET INFO SUPPORT:
	//		The getAppletInfo() method returns a string describing the applet's
	// author, copyright date, or miscellaneous information.
    //--------------------------------------------------------------------------
	public String getAppletInfo()
	{
		return "Name: hull\r\n" +
		       "Author: Jason Plumb\r\n" +
		       "Created with Microsoft Visual J++ Version 1.0";
	}


	// The init() method is called by the AWT when an applet is first loaded or
	// reloaded.  Override this method to perform whatever initialization your
	// applet needs, such as initializing data structures, loading images or
	// fonts, creating frame windows, setting the layout manager, or adding UI
	// components.
    //--------------------------------------------------------------------------
	public void init()
	{
        // If you use a ResourceWizard-generated "control creator" class to
        // arrange controls in your applet, you may want to call its
        // CreateControls() method from within this method. Remove the following
        // call to resize() before adding the call to CreateControls();
        // CreateControls() does its own resizing.
        //----------------------------------------------------------------------
		//setLayout(new FlowLayout(FlowLayout.LEFT,10,10));
		int rx, ry;
		setLayout(new BorderLayout());
		Panel toppanel = new Panel();	//A panel for the top components
		themap = getImage(getCodeBase(), "map1.jpg");
		L1 = new Label("Red camps:", Label.RIGHT);
		toppanel.add(L1);
		L2 = new Label("3     ", Label.LEFT);		// No points to begin with
		toppanel.add(L2);
		L3 = new Label("Blue camps:", Label.RIGHT);
		toppanel.add(L3);
		L4 = new Label("3     ", Label.LEFT);
		toppanel.add(L4);
		clear = new Button("New Game");
		toppanel.add(clear);						// Add the clear button to top panel
		mapsel=new Choice();
		mapsel.addItem("Ancient Countryside");
		mapsel.addItem("Conquer Lubbock!!!");
		mapsel.addItem("Brain Microbes Attack");
		toppanel.add(mapsel);
		TurnLabel = new Label("Red's Turn   ");
		TurnLabel.setFont(new Font("Helvetica", Font.ITALIC, 16));
		toppanel.add(TurnLabel);
		add("North", toppanel);
		Status = new Label("Start of a new game!!!                             ");
		Status.setFont(new Font("Helvetica", Font.BOLD, 20));
		add("South", Status);		// Add the status label at the bottom
		InitialPoints();
		rptcount = 3;
		bptcount = 3;
		resize(appwidth, appheight);
		repaint();
	}

	// Place additional applet clean up code here.  destroy() is called when
	// when you applet is terminating and being unloaded.
	//-------------------------------------------------------------------------
	public void destroy()
	{
		// TODO: Place applet cleanup code here
	}

	// hull Update Handler
	//---------------------------------------------------------------------
	public void update(Graphics g){
		
		offScreenImage = createImage(mapwidth, mapheight+38);	//Off screen image for double buffering
		offScreenGraphic = offScreenImage.getGraphics();	//Off screen graphic for buffering	
		offScreenGraphic.drawImage(themap, 0, 38, mapwidth, mapheight, this);
		offScreenGraphic.drawRect(0,38,mapwidth-1, mapheight-1);	//Draw border box
		if(closestpoint!=null){
			offScreenGraphic.setColor(Color.green);
			offScreenGraphic.drawOval(closestpoint.x-maxdist+1, closestpoint.y-maxdist, maxdist*2, maxdist*2);
		}
		offScreenGraphic.setColor(Color.red);
		if(Turn%2==0)
			TurnLabel.setText("Red's Turn");
		drawpts(offScreenGraphic, redpoints, rptcount);
		if(rptcount>2) drawhull(offScreenGraphic, createhull(redpoints, rptcount));
		offScreenGraphic.setColor(Color.blue);
		if(Turn%2!=0)
			TurnLabel.setText("Blue's Turn");
		drawpts(offScreenGraphic, bluepoints, bptcount);
		if(bptcount>2) drawhull(offScreenGraphic, createhull(bluepoints, bptcount));
		g.drawImage(offScreenImage, 0, 0, this);			//Copy off-screen to on-screen
		paint(g);
	} 

	// hull Paint Handler
	//--------------------------------------------------------------------------
	public void paint(Graphics g)
	{
		if(offScreenImage!=null){
			g.drawImage(offScreenImage, 0, 0, this);
		}
	}

	//		The start() method is called when the page containing the applet
	// first appears on the screen. The AppletWizard's initial implementation
	// of this method starts execution of the applet's thread.
	//--------------------------------------------------------------------------
	public void start()
	{
		// TODO: Place additional applet start code here
		
	}
	
	//		The stop() method is called when the page containing the applet is
	// no longer on the screen. The AppletWizard's initial implementation of
	// this method stops execution of the applet's thread.
	//--------------------------------------------------------------------------
	public void stop()
	{
	}

	// Mouse Support:
	// The mouseMove() event handler
	public boolean mouseMove(Event evt, int x, int y){
		point target = new point(x,y);
		if((x<620) && (y<338) && (x>0) && (y>39)){	//If they're within the box
			if(Turn%2==0){		//Red's turn
				closestpoint = Closest(redpoints, target, maxdist, rptcount);
				if(closestpoint!=null){
					repaint();
					return true;
				}//if
				else return false;	// No closest point
			}//if
			else{		//Blue's turn
				closestpoint = Closest(bluepoints, target, maxdist, bptcount);
				if(closestpoint!=null){
					repaint();
					return true;
				}//if
				else return false;	// No closest point
			}
		}//if
		else return false;
	}


	// MOUSE SUPPORT:
	//		The mouseDown() method is called if the mouse button is pressed
	// while the mouse cursor is over the applet's portion of the screen.
	//--------------------------------------------------------------------------
	public boolean mouseDown(Event evt, int x, int y)
	{
		// TODO: Place applet mouseUp code here
		return true;
	}

	
	// MOUSE SUPPORT:
	//		The mouseUp() method is called if the mouse button is released
	// while the mouse cursor is over the applet's portion of the screen.
	//--------------------------------------------------------------------------
	public boolean mouseUp(Event evt, int x, int y)
	{
		point tpoint = new point(x,y); 
		point ipt;
		point ipt2;
		if((rptcount < maxpts) && (x<620) && (y<338) && (x>0) && (y>39)){
			if(Turn%2==0){	//Red's turn
				if(Closest(redpoints, tpoint, maxdist, rptcount)==null)//If there's no closest red point, don't let them click here!
					if(rptcount!=0)
						return false;
				ipt = IsOverlap(redpoints, bluepoints, rptcount, bptcount, tpoint);
				if((IsIntersection(bluepoints, bptcount, tpoint)==true) || /*If there's an intersection*/
					(ipt!=null)){		//If a battle happens
					Turn++;
					if(winbattle(rptcount, bptcount)==true){//if red won the battle
						L2.setText(String.valueOf(rptcount));
						Status.setText("Red attacks...WINS the heated battle!!!");
						while((IsIntersection(bluepoints, bptcount, tpoint)==true) || (ipt!=null)){		//If a battle happens
							ipt2 = Closest(bluepoints, tpoint, 2000, bptcount);
							RemovePoint(bluepoints, ipt2, bptcount);
							bptcount--;
							L4.setText(String.valueOf(bptcount));
							ipt = IsOverlap(redpoints, bluepoints, rptcount, bptcount, tpoint);
						}//while
						redpoints[rptcount] = new point(x,y);
						rptcount++;
						repaint();
						return true;
					}//if
					else{	//They lost the battle
						Status.setText("Red attacks...the battle is lost!!");
						return true;
					}
				}//if
				else{//No battle
					if(((double)(100*Math.random()))<8){	//Environmental hardships!, 7% chance of losing turn
						Status.setText("Red attempts to set up camp...due to harsh environment, FAILS!!!");
						Turn++;
						return true;
					}
					else{	//Ok to move
						redpoints[rptcount] = new point(x,y);
						rptcount++;
						L2.setText(String.valueOf(rptcount));
						Status.setText("Red sets up new camp...");
						if(((double)(100*Math.random()))<11){ //Free turn!
							Status.setText("Red sets up new camp...finds resources for EXTRA TURN!");
						}//if
						else{
							Turn++;
						}//else
						repaint();
						return true;
					}
				}//else
			}
			else{					//blue's turn
				if(Closest(bluepoints, tpoint, maxdist, bptcount)==null)//if there's no closest blue point, don't let them click here!
					if(bptcount!=0)
						return false;
				ipt = IsOverlap(bluepoints, redpoints, bptcount, rptcount, tpoint);
				if((IsIntersection(redpoints, rptcount, tpoint)==true) || /*If there's an intersection*/
				  (ipt!=null)){	//If there's a battle
					Turn++;
					if(winbattle(bptcount, rptcount)==true){//if red won the battle
						L4.setText(String.valueOf(bptcount));
						Status.setText("Blue attacks...WINS the heated battle!!!");
						while((IsIntersection(redpoints, rptcount, tpoint)==true) || (ipt!=null)){		//If a battle happens
							ipt2 = Closest(redpoints, tpoint, 2000, rptcount);
							RemovePoint(redpoints, ipt2, rptcount);
							rptcount--;
							L2.setText(String.valueOf(rptcount));
							ipt = IsOverlap(bluepoints, redpoints, bptcount, rptcount, tpoint);
						}//while
						bluepoints[bptcount] = new point(x,y);
						bptcount++;
						repaint();
						return true;
					}
					else{	//They lost the battle
						Status.setText("Blue attacks...the battle is lost!!");
						return true;	
					}
				}//if
				else{//No battle
					if(((double)(100*Math.random()))<8){	//Environmental hardships! 7% chance of failure
						Status.setText("Blue attempts to set up camp...due to harsh environment, FAILS!!!");
						Turn++;
						return true;
					}//if
					else{	//Ok to move
						bluepoints[bptcount] = new point(x,y);
						bptcount++;
						L4.setText(String.valueOf(bptcount));
						Status.setText("Blue sets up new camp..");
						if(((double)(100*Math.random()))<11){ //Free turn!
							Status.setText("Blue sets up new camp...finds resources for EXTRA TURN!");
						}//if
						else{
							Turn++;
						}//else
						repaint();
						return true;
					}//else
				}//else
			}//else
		}//if
		else return false;
	}

	//Event handler
	public boolean action(Event e, Object o){
		if(e.target==clear){		//They clicked the clear button
			rptcount = 3; bptcount = 3;
			L2.setText("3     "); L4.setText("3     ");
			Status.setText("Start of new battle!!!");
			Turn=0;
			InitialPoints();
			repaint();
			return true;
		}
		else if(e.target==mapsel){	//If they changed the map
			switch(mapsel.getSelectedIndex()){
				case 0:  themap = getImage(getCodeBase(), "map1.jpg"); break;
				case 1:  themap = getImage(getCodeBase(), "map2.gif"); break;
				case 2:  themap = getImage(getCodeBase(), "map3.jpg"); break;
			}//switch
			rptcount=3;				//Reset all points
			L2.setText("3     ");	//Update label
			bptcount=3;
			L4.setText("3     ");
			Status.setText("Start of new battle!!!");
			Turn=0;
			InitialPoints();
			repaint();
		}//else
		return false;
	}//action

	//Function to check if there is an overlap (reverse intersection)
	//Returns the first point found to be reverse intersection
	//If not found, returns false
	public point IsOverlap(point[] points, point[] target, int ptcount, int tcount, point tpoint){
		int minx, maxx, miny, maxy;
		maxx = tpoint.x; maxy = tpoint.y;
		minx = tpoint.x; miny = tpoint.y;
		int i;
		int tptcount=ptcount;
		point[] temp = new point[tptcount+1];
		for(i=0;i<tptcount;i++){
			temp[i] = new point(points[i].x, points[i].y);
		}
		temp[tptcount]=new point(tpoint.x, tpoint.y);
		tptcount++;
		for(i=0;i<tptcount;i++){			//Find leftmost, rightmost, topmost, and bottommost
			if(temp[i].x < minx) minx = temp[i].x;
			if(temp[i].x > maxx) maxx = temp[i].x;
			if(temp[i].y < miny) miny = temp[i].y;
			if(temp[i].y > maxy) maxy = temp[i].y;
		}
		for(i=0;i<tcount;i++){
			if((target[i].x>minx)&&(target[i].x<maxx)&&(target[i].y>miny)&&(target[i].y<maxy)){
				if(IsIntersection(temp, tptcount, target[i])==true)
					return target[i];
			}//if
		}//for
		return null;
	}//IsOverlap

	//This function will remove the specified point from the specified array.
	//It is assumed that the point exists in the array
	public void RemovePoint(point[] points, point target, int ptcount){
		int i, j;
		for(i=0;i<ptcount;i++){
			if((points[i].x==target.x)&&(points[i].y==target.y)){
				for(j=i;j<ptcount-1;j++){
					points[j] = new point(points[j+1].x, points[j+1].y);
				}//for
			}//if
		}//for
	}//RemovePoint


	//IsIntersection will determine if the given point is "inside" the convex hull of the 
	//array of points passed to it.
	//THEORY:	If the new point were put into the other point array, would it create a convex hull?   
	//			If so no intersection has occurred.  Else an intersection has occured.
	//Returns:  true if intersection, false if no intersection
	
	public boolean IsIntersection(point[] points, int ptcount, point target){
		Stack s;											// Standard stack
		int i;
		int tptcount = ptcount;
		point tp = new point(0,0);							// Temporary point
		point[] temp = new point[maxpts];
		for(i=0;i<tptcount;i++)								// Copy points into temp array
			temp[i] = new point(points[i].x, points[i].y);
		temp[ptcount] = new point(target.x, target.y);		// Put target point into array
		tptcount++;
		s = createhull(temp, tptcount);						// Fill stack with hull points
		while(s.empty()==false){							// Now check stack for added point
			tp = (point)s.pop();
			if((tp.x==target.x)&&(tp.y==target.y)) return false;// If the target is on the hull, return false
		}
		//System.out.println("There is an intersection");
		return true;
	}

	//This function will determine the winner of a battle
	public boolean winbattle(int ptcount, int tcount){
		double win;
		double temp;
		temp = (double)((double)(ptcount)/(double)((ptcount+tcount)));
		win = 100*temp;
		temp = (double)(100*Math.random());
		win = win + temp;
		if(win>100)	return true;
		else return false;
	}

	//This will draw all points in the array
	public void drawpts(Graphics g, point[] points, int ptcount){
		int i;
		for(i=0;i<ptcount;i++){
			g.drawOval(points[i].x,points[i].y,5,5);
		}//for
	}//drawpt

	//Routine for determining the hull and drawing it
	//This implements Graham's scan algorithm
	//Returns a stack containing the hull points
	public Stack createhull(point[] points, int ptcount){
		point[] temp = new point[maxpts+1];	// Array of points
		int i;
		point tp;
		point lowest;						// The lowest point
		point begin, middle, end;
		Stack s = new Stack();
		for(i=0;i<ptcount;i++){				// Copy points array into temp array
			temp[i] = new point(points[i].x,points[i].y);
		}//for
		lowest = new point(temp[0].x, temp[0].y);// Start with first one
		
		for(i=0;i<ptcount;i++){				// Find lowest in array
			if(temp[i].y<lowest.y)
				lowest = temp[i];
			else
				if((temp[i].y==lowest.y)&&(temp[i].x<lowest.x))
					lowest = temp[i];
		}//for (find lowest)
		for(i=0;i<ptcount;i++){				// Calc all angles
			temp[i].angle = calc_angle(lowest, temp[i]);
		//	g.drawString("a:" + String.valueOf(temp[i].angle), temp[i].x+25, temp[i].y);
		}//for
		QuickSort(temp, 0, ptcount-1);		// Sort temp points by angle
		temp[ptcount]=temp[0];				// Repeat start at end
		//for(i=0;i<rptcount;i++){
		//	g.drawString("sn:" + String.valueOf(i), temp[i].x+25, temp[i].y+15);
		//}
		i=0;
		s.push(temp[i++]);
		s.push(temp[i++]);
		while(i<ptcount){		// Check all points
			s.push(temp[i++]);
			//This is a silly way to access these needed stack components
			end = (point) s.pop(); middle = (point)s.pop(); begin=(point)s.pop();
			s.push(begin); s.push(middle); s.push(end);			
			while((Turn(begin, middle, end)==false)&&(end.angle!=0)&&(i>2)){				
				tp=(point)s.pop();
				s.pop();	//Get rid of point 2 because it's not in the hull
				s.push(tp);
				//This is a silly way to access these needed stack components
				end = (point) s.pop(); middle = (point)s.pop(); begin=(point)s.pop();
				s.push(begin); s.push(middle); s.push(end);			
			}//while
		}//while
		//At this point, the stack should contain only the points on the hull
		//so let's return it
		return s;
	}//createhull

	//This function will draw the hull
	public void drawhull(Graphics g, Stack s){
		int i;
		int[] xpts = new int[maxpts+1];		
		int[] ypts = new int[maxpts+1];
		point tpoint = new point(0,0);
		i=0;
		while(s.empty()==false){			//Loop until stack is empty
			tpoint = (point)s.pop();
			xpts[i]=tpoint.x+2;
			ypts[i]=tpoint.y+2;
			i++;
		}//while
		xpts[i]=xpts[0];  ypts[i]=ypts[0];	//Include first point again
		g.drawPolygon(xpts, ypts, i+1);		//Draw the hull itself
		g.drawString("HQ", xpts[i-1], ypts[i-1]-5);
	}

	//This will sort a points array by angle
	void QuickSort(point[] A, int p, int q){
		if(p<q){
			int j = partition(A,p,q+1);
			QuickSort(A,p,j-1);
			QuickSort(A,j+1,q);
		}//if
	}//QuickSort

	//Used in quick sort...Assumes sorting by point angles
	int partition(point[] A, int m, int p){
		point pivot = new point(A[m].x, A[m].y);
		pivot.angle = A[m].angle;
		//point pivot = new point(0,0);
		//pivot = A[p];
		point temp = new point(0,0);
		int i = m;
		int j = p;
		while(i<j){
			do i++;
				while((A[i]!=null)&&(A[i].angle < pivot.angle));
			do j--;
				while((A[j]!=null)&&(A[j].angle > pivot.angle));
			if(i<j){
				temp = A[i];
				A[i] = A[j];		// Swap points
				A[j] = temp;
			}//if
		}
		A[m]=A[j]; 
		A[j] = pivot;
		return j;
	}

	//This will calculate the angle between two points
	//It should return a number between 0 and 180 because it is
	//always being called with the "lowest" point, so all points
	//lie above it
	double calc_angle(point lowest, point pt){
		int xd, yd;
		double angle;
		if((lowest.x==pt.x)&&(lowest.y==pt.y)) return 0;	// If comparing to same point, return 0 to avoid div 0 err
		else if(lowest.x==pt.x) return 90;
		yd = pt.y - lowest.y;		// Calc y distance
		xd = pt.x - lowest.x;		// Calc x distance
		angle = Math.atan((double)yd/xd);
		angle = angle * 360 / (2*3.1415); // Convert to degrees
		if(angle<0) return (180 + angle); // Fix for negative angles
		else return angle;
	}//calc angle

	// This is a function to determine the direction of a "turn" between 3 points.
	// This function will return TRUE if it's a left hand turn
	// otherwise it will return false
	boolean Turn(point b, point m, point e){
		int temp;
		//temp = (b.x - m.x)*(e.y - m.y) - (e.x - m.x)*(b.y - m.y);
		temp = b.x*(m.y-e.y) - m.x*(b.y-e.y) + e.x*(b.y-m.y);
		if(temp<=0) return false;
		else return true;
	}

	
	//Creates three semi-random points in the blue and red arrays
	public void InitialPoints(){
		int rx, ry;
		
		rx = (int)(20*Math.random()) + 5;
		ry = (int)((mapheight-20)*Math.random())+70;
		redpoints[0]=new point(rx,ry);
		redpoints[1]=new point(rx+20, ry);
		redpoints[2]=new point(rx+10, ry-20);
		
		rx = (int)(20*Math.random()) + 580;
		ry = (int)((mapheight-20)*Math.random())+70;
		bluepoints[0]=new point(rx,ry);
		bluepoints[1]=new point(rx+20, ry);
		bluepoints[2]=new point(rx+10, ry-20);
		
	}//InitialPoints
	
	//This function will return the distance between two points
	double Distance(point p1, point p2){
		int xd, yd;		// x and y distances
		double dist;
		xd = Math.abs(p1.x - p2.x);
		yd = Math.abs(p1.y - p2.y);
		dist = Math.sqrt((xd*xd)+(yd*yd));	//pythagorean theorem!
		return dist;
	}

	//This function will return the point in the array that is within dist
	//distance from the passed point.  If no points are within this dist,
	//the function will return null.
	point Closest(point points[], point target, int dist, int arrsize){
		point tpoint = new point(0,0);
		double close=0;
		double oldclose=999999;		//Set initial dist very large
		int i;
		boolean found = false;
		for(i=0;i<arrsize;i++){
			close=Distance(points[i], target);
			if((close<=dist)&&(close<oldclose)){
				tpoint = points[i];
				found = true;
				oldclose=close;
			}//if
		}//for
		if(found==true)	return tpoint;
		else return null;
	}//Closest

}//hull class


//Definition of the point class
class point{
	int x;
	int y;
	double angle;		// The angle referenced to another point
	point(int nx, int ny){
		x = nx;			y = ny;
		angle = 0;		// Initialize to 0
	}//point constructor
}