import java.awt.*;
import java.lang.Math;
import point;
import segment;
import polygon;

class polyCanvas extends Canvas
{
    polygon P = new polygon(100);
    //polygon P_backup = new polygon(100);
    //maximum points is 100 or so...	
    polygon CEx = new polygon(8);
    //polygon CEx_backup = new polygon(8);
    stepInfo NextStep = new stepInfo();
    boolean UsingExample = false;
    int sumX = 0;
    int sumY = 0;
    int totalpoints = 0;
    point greg = new point(0,0);
    int X[] = new int[101];
    int Y[] = new int[101];
    int CH[] = new int[101];
    int depth[] = new int[101];
    int count = 0;
    int peel_number = 0;
    /*****************INITIALIZE The Counter Example***************/	
    public void CounterExample()  //hardcoded example
    {
	CEx.n = 8;   //we know there are 8 points
	CEx.vlist[0] = new point(219,33,0);
	CEx.vlist[1] = new point(331,138,1);
	CEx.vlist[2] = new point(240,254,2);
	CEx.vlist[3] = new point(95,215,3);
	CEx.vlist[4] = new point(211,195,4);
	CEx.vlist[5] = new point(179,105,5);
	CEx.vlist[6] = new point(161,159,6);
	CEx.vlist[7] = new point(86,76,7);
	/*CEx_backup.n = 8;   //we know there are 8 points
	  CEx_backup.vlist[0] = new point(219,33,0);
	  CEx_backup.vlist[1] = new point(331,138,1);
	  CEx_backup.vlist[2] = new point(240,254,2);
	  CEx_backup.vlist[3] = new point(95,215,3);
	  CEx_backup.vlist[4] = new point(211,195,4);
	  CEx_backup.vlist[5] = new point(179,105,5);
	  CEx_backup.vlist[6] = new point(161,159,6);
	  CEx_backup.vlist[7] = new point(86,76,7);*/
	
	UsingExample = true;
	P.closed = true;
	/*DrawPolygon(CEx,Color.green);
	  point greg = new point(100,100);
	  drawPoint(greg, Color.red);
	*/    
    }
    
    /*-*****************************
     *
     *    GRAPHICS FUNCTIONS
     *    ==================
     */
    /*****************DRAW A POINT**********************/
    public void drawPoint(point p, Color c)
    {
	Graphics g = getGraphics();
	g.setColor(c);
	g.fillOval(p.x - 3, p.y - 3, 6, 6);
	/*g.setColor(Color.black);
	  g.drawOval(p.x - 3, p.y - 3, 6, 6);
	*/
	}
    
    /*****************DRAW A COIN**********************/
    public void drawCoin(point p)
    {
	Graphics g = getGraphics();
	g.setColor(p.coin);
	g.fillOval(p.x - 4, p.y - 4, 10, 10);
  	g.setColor(Color.black);
	g.drawOval(p.x - 4, p.y - 4, 10, 10);
    }
    
    /*****************REDRAW POINT COINLESS**********************/
    public void redrawPoint(point p, 
			    point prev, 
			    point next,
			    point realPrev,
			    point realNext,
			    Color c)
    { //first we erase (white!)
	Graphics g = getGraphics();
  	
  	g.setColor(Color.white);
	g.fillOval(p.x - 4, p.y - 4, 10, 10);
  	g.drawOval(p.x - 4, p.y - 4, 10, 10);
  	g.setColor(c);
	g.fillOval(p.x - 3, p.y - 3, 6, 6);
	g.setColor(Color.black);
	g.drawOval(p.x - 3, p.y - 3, 6, 6);
	
  	drawSegment(new segment(prev,p),Color.red);
  	drawSegment(new segment(p,next),Color.red);	
  	drawSegment(new segment(realPrev,p),Color.blue);
  	drawSegment(new segment(p,realNext),Color.blue);	
	
  	if(!(prev.coin == Color.blue))
	    {g.setColor(prev.coin);
	    g.fillOval(prev.x - 4, prev.y - 4, 10, 10);
	    g.setColor(Color.black);
	    g.drawOval(prev.x - 4, prev.y - 4, 10, 10);
	    }
  	if(!(next.coin == Color.blue))
	    {g.setColor(next.coin);
	    g.fillOval(next.x - 4, next.y - 4, 10, 10);
	    g.setColor(Color.black);
	    g.drawOval(next.x - 4, next.y - 4, 10, 10);
	    }
  	
    }
    
    
    /*****************DRAW A SEGMENT**********************/
    public void drawSegment(segment s, Color c)
    {
	Graphics g = getGraphics();
	g.setColor(c);
	g.drawLine(s.tail().x,s.tail().y,s.head().x,s.head().y);
	drawPoint(s.tail(),Color.blue);
	drawPoint(s.head(),Color.blue);
    }
    /*****************DRAW NEW SEGMENT**********************/
    public void drawNewSeg(segment s)
    {
	Graphics g = getGraphics();
	g.setColor(Color.red);
	g.drawLine(s.tail().x,s.tail().y,s.head().x,s.head().y);
  	drawCoin(s.tail());    
	drawCoin(s.head());
  	System.out.println("\tDrawing new edge");
    }
    /*****************RESET POLYGON!**********************/
    public void reset()
    {
	P = new polygon(100);
  	//P_backup = new polygon(100);
  	CEx = new polygon(8);
  	//CEx_backup = new polygon(8);
  	UsingExample = false;
  	NextStep = new stepInfo();
	Graphics g = getGraphics();
	g.setColor(Color.white);
	g.fillRect(0,0,500,350);
	for (count = 0; count < 101; count++)
	{
	    X[count] = 0;
	    Y[count] = 0;
	}
	count = 0;
	totalpoints = 0;
	sumX = 0; sumY = 0;
    }
    
    /*****************FIND EXTREME POINT ON POLYGON!**********************/
    public int ExtremePoint(polygon Q)
    {//returns the index of the minimum X value point
  	int indexOfMin = 0;
  	int min = Q.vlist[0].x;
  	for (int i = 1; i < Q.n; i++)
	    {//System.out.print(" ("+i+") " +Q.vlist[i].x +" ");
  	   	if(min > Q.vlist[i].x)
		    {indexOfMin = i;
		    min = Q.vlist[i].x;
		    }
	    }
  	System.out.println("\nIndex of min is: " + indexOfMin);
	return(indexOfMin);
    }
    
    
    /*****************DRAW POLYGON**********************/
    public void DrawPolygon(polygon Q,Color c)
    {
	Graphics g = getGraphics();
	g.setColor(Color.white);
	g.fillRect(0,0,500,350);
  	for (int i = 0; i < Q.n; i++)
	    {
		drawSegment(new segment(Q.vlist[i],Q.vlist[(i+1)%Q.n]), c);
	    }
    }
    /*****************DRAW CONVEX POLYGON and points***************/
    public void DrawConvexPolygon(polygon Q)
    {int i,j;
    boolean done = false;
    Graphics g = getGraphics();
    g.setColor(Color.white);
    g.fillRect(0,0,500,350);  	
    for (i = 0; i < Q.n; i++)
	{
	    drawPoint(Q.vlist[i], Color.darkGray);
	}
    i = ExtremePoint(Q);
    j = i;
    while(!done)
	{	drawSegment(new segment(Q.vlist[i],Q.vlist[Q.next(i)]), Color.red);
    	i = Q.next(i);
    	if(i == j)
	    {done = true;}
	}
    }
    
    /*****************RE-LABELING OF POINTS**********************/
    public polygon ReLabel(int start)
    {//we wish to relabel the polygon in clockwise fashion starting at 'start'
	polygon tempPolygon = new polygon(100);
	for(int i =0; i< P.n; i++)
	    {tempPolygon.addVertex(P.vlist[start]);
	    start = (start + P.n - 1)%P.n;	
	    }
	System.out.println("\tDone relabelling");
	return(tempPolygon);
	
    }
    
    /*****************CHECK FOR INTERSECTIONS**********************/
    public int numIntersect(segment s)
    {
	int numIntersect = 0;
	for (int i = 0; i < P.n; i++)
	    {
		segment e = new segment(P.vlist[i],P.vlist[(i+1)%P.n]);
		if (intersect(s,e)) { numIntersect++; }
	    }
	return numIntersect;
    }
    
    
    /*-************************************************
     *
     *  EVENT HANDLING FUNCTION (calls action functions
     *  MOUSE and BUTTON STUFF!
     */
    
    public boolean handleEvent(Event evt)
    {
	/*this all works fine from here on*/
	if (evt.id == Event.MOUSE_DOWN)
	    {
		/*System.out.println("point: "+evt.x+","+evt.y);*/
		totalpoints = totalpoints + 1;/* user has added a point*/
		if (totalpoints <100) /* else do nothing */
		    {
			X[totalpoints] = evt.x;
			Y[totalpoints] = evt.y;
			
			Graphics g = getGraphics();/* clear screen */
			g.setColor(Color.white);
			g.fillRect(0,0,500,350);
			
			sumX = sumX + evt.x; /* recalculate mean */
			sumY = sumY + evt.y;
			greg.x = (sumX/totalpoints);
			greg.y = (sumY/totalpoints);

			/*NEW STUFF IN HERE, WILL ATTEMPT TO GET
			  CONVEX HULL PEELING DONE */
			/* this stuff is all done whenever a new point is entered */
			/* start copying here if changes are made and you want to duplicate them in Mouse_drag*/
			if (totalpoints >= 3)
			    {
				int i; int j;
				double angle;
				int Yminindex = 1;
				int Ymaxindex = 1;
				int Ymin = 10000;
				int Ymax = -1;
				int GlobalYmin;
				int Yminindex2 = 1;
				int remainingCH = 0;
				peel_number = 0;
				for (i = 1; i <= 100; i++)
				    {
					CH[i] = 0; /* no points on CH yet */
					depth[i] = 0;
				    }
				int keep_peeling = 1;
					
				
				while (keep_peeling == 1)
				    {
					peel_number++;   /* how many times have we peeled ? */
					/*new*/ Ymin = 10000;
					/*new*/ Ymax = -1;
					for (i = 1; i <= totalpoints; i++)
					    {			
						if (CH[i] == 0) /* points on CH are "erased" */ 
						    {
							if (Y[i] < Ymin)
							    {
								Ymin = Y[i];
								Yminindex = i;
								Yminindex2 = i;
							    }
							else if (Y[i] == Ymin)
							    {
								if (X[i] < X[Yminindex])
								    Yminindex = i; /* leftmost Ymin */
								if (X[i] > X[Yminindex2])
								    Yminindex2 = i; /* rightmost Ymin */
							    }
							if (Y[i] > Ymax)
							    {
								Ymax = Y[i];
								Ymaxindex = i;
							    }
							else if (Y[i] == Ymax)
							    {
								if (X[i] > X[Ymaxindex])
								    Ymaxindex = i;
							    }
						    }
					    }/* now we should have Ymin and Ymax, with indices */
					/*System.out.println("Ymin: "+Ymin+" at index "+Yminindex);
					  System.out.println("Ymax: "+Ymax+" at index "+Ymaxindex);*/
					GlobalYmin = Ymin;
					
					/*
					for (i = 1; i <= totalpoints; i++)
					    System.out.println("point "+i+" : "+X[i]+","+Y[i]);
					*/
					
					
					double minangle = -10000; /* minus Inf */
					double maxangle = -1;     /* bogus */
					int nextCH = -1;
					CH[Yminindex] = 1;   /* place point with smallest Ycoord on the CH */
					CH[Yminindex2] = 1; /* if another Ymin exists put it on CH too */
					depth[Yminindex2] = peel_number;
					depth[Yminindex] = peel_number;
				/* the following while loop will construct the left chain of the CH, 
				   starting from Ymin and going up, (clockwise) until Ymax is reached*/
					while (Yminindex != Ymaxindex)
					    {
						/*System.out.println(" ");
						  System.out.println("--- Entering LHS while loop");*/
						minangle = -10000;
						maxangle = -1;         
						nextCH = -1;
						/* System.out.println("I'm going to check the next candidate");*/
						
						for (i = 1; i <= totalpoints; i++)
						    {
							/*consider all points */
				/*if the point we're looking at is not on the CH chain
				  yet, and it is higher than the last point added... */
							/*if (CH[i] == 1)
							  System.out.println("point "+X[i]+","+Y[i]+" is on CH");
							  else
							  System.out.println("point "+X[i]+","+Y[i]+" not  on CH");
							*/
							if ((CH[i] == 0) && (Y[i] >= Y[Yminindex]))
							    {/*
							       System.out.println("   it's larger than Ymin, so i'll check it");	*/
								if (X[i] == X[Yminindex])
								    angle = 10000;/* larger than any ratio */
								else
								    {
									angle = ((double) (Y[i]-Y[Yminindex]))/
									    ((double) (X[i]-X[Yminindex]));
								    }
								/*want angle to be largest negative (close to 0)*/
								/*if no negatives, largest positive (close to Inf)*/  
							       
								if (angle < 0) /* if negative angle, Q2 */
								    {
									if (angle > minangle)/* see if closer to 0*/
									    {
										minangle = angle;
										nextCH = i;
									    }
								    }
								else if (angle == 0) /* this should only happen at Ymax */
								    {
									if (Y[Yminindex] == Y[Ymaxindex])
									    nextCH  = Ymaxindex;
								    }
								else       /* if angle strictly positive */
								    if (minangle == -10000) /*otherwise dont bother
											      with Q1 */
									if (angle > maxangle)
									    {
										maxangle = angle;
										nextCH = i;
									    }
									
								/* System.out.println("   angle= "+angle);*/
							    }
							
						    }
						/*
						  System.out.println("I select point "+X[nextCH]+","+Y[nextCH]+" as next CHvertex");*/
				/*now we have the next CH vertex index*/
				/* if there was a negative angle, it was found,
				   otherwise the largest angle was found */
						CH[nextCH] = 1; /* add point to CH */
						depth[nextCH] = peel_number;
						Ymin = Y[nextCH]; /* update the new "Ymin" on the left chain*/
						Yminindex = nextCH; 
						/*System.out.println("New Ymin: "+Ymin);*/
					    } /* end while */
					/* draw LCH points green */
					/*
					if (totalpoints >= 3)
					    for (count = 1; count <= totalpoints; count++)
						{
						    if (CH[count] == 1)
							{
							    drawPoint((new point((X[count]+5),Y[count])), Color.green);
							    System.out.println("CH pt "+count+": "+X[count]+","+Y[count]);
							}
						}
					*/
					
				/* NOW DO THE RHS OF THE CHAIN */
					CH[Ymaxindex] = 0;      /* this is necessary to compute RHS correctly */
					/*System.out.println(" ");
					System.out.println(" ");
					System.out.println("Doing RHS now !");*/
					
					Yminindex = Yminindex2;  /* now Yminindex is the rightmost Ymin */
					Ymin = GlobalYmin; /* restore Ymin, since it had changed on LH of CH */
					
					minangle = 10001; /* Inf + 1 */
					maxangle = 1;     /* bogus */
					nextCH = -1;
					
				/* the following while loop will construct the right chain of the CH, 
				   starting from Ymin and going up, (counterclockwise) until Ymax is reached*/
					while (Yminindex != Ymaxindex)
					    {
						minangle = 10001; /* angles in Q1 */
						maxangle = 1;         /* in Q2 */
						nextCH = -1;
						/*System.out.println("I'm going to check the next candidate");*/
						
						for (i = 1; i <= totalpoints; i++)
						    {/*consider all points */
				/*if the point we're looking at is not on the CH chain
				  yet, and it is higher than the last point added... */
							/*
							if (CH[i] == 1)
							    System.out.println("point "+X[i]+","+Y[i]+" is on CH");
							else
							    System.out.println("point "+X[i]+","+Y[i]+" not  on CH");
							*/
							if ((CH[i] == 0) && (Y[i] >= Y[Yminindex]))
							    {/*
							       System.out.println("   it's larger than Ymin, so i'll check it");	*/
								if (X[i] == X[Yminindex])
								    angle = 10000;/* Inf : larger than any ratio */
								else
								    {
									angle = ((double) (Y[i]-Y[Yminindex]))/
									    ((double) (X[i]-X[Yminindex]));
								    }
								/*want angle to be smallest positive (close to 0)*/
								/*if no positives, smallest negative (close to -Inf)*/
								if (angle > 0) /* if positive angle, Q1 */
								    {
									if (angle < minangle)/* see if closer to 0*/
									    {
										minangle = angle;
										nextCH = i;
									    }
								    }
								else if (angle == 0) /*  do nothing */
									; 
								else        /* if angle negative */
								    if (minangle == 10001) /*otherwise dont bother
											     with Q2 */
									if (angle < maxangle)
									    {
										maxangle = angle;
										nextCH = i;
									    }
								/*System.out.println("   angle= "+angle);*/
							    }
							
						    }
						if (nextCH == -1) /* there are no points on RCH */
						    Yminindex = Ymaxindex;  /* dont go back into while loop */
						else
						    {/*
						       System.out.println("I select point "+X[nextCH]+","+Y[nextCH]+" as next CHvertex");*/
				/*now we have the next CH vertex index*/
				/* if there was a negative angle, it was found,
				   otherwise the largest angle was found */
							CH[nextCH] = 1;
							depth[nextCH] = peel_number; /* add point to CH */
							Ymin = Y[nextCH]; /* update the new "Ymin" on the left chain*/
							Yminindex = nextCH; 
							/*System.out.println("New Ymin: "+Ymin);*/
						    }
					    } /* end while */
					
					remainingCH = 0;
					for (i = 1; i <= totalpoints; i++)
					    remainingCH += CH[i]; /* count pts on CH */
					if ((totalpoints-remainingCH) <= 3) /* still have >3 pts not on CH*/ 
					    keep_peeling = 0;
					
					
				    }	/* end while keep_peeling */
			    } /* end if totalpoints >=3 */
			
			
			/* draw all points */
			if (totalpoints < 3)
			    for (count = 1; count <= totalpoints; count++)
				drawPoint((new point(X[count],Y[count])), Color.blue);
			
			
			int CHmean_sumX = 0;
			int CHmean_sumY = 0;
			int killmeX = 0;
			int killmeY = 0;
			int flag = 0;
			int innerCHpts = 0;
			int innerCHpts2 = 0;
			point CHmean = new point(0,0);
			if (totalpoints >= 3)
			    {
				for (count = 1; count <= totalpoints; count++)
				    {
					if (CH[count] != 1)
					    {
						drawPoint((new point((X[count]),Y[count])), Color.black);
						/*System.out.println("CH pt "+count+": "+X[count]+","+Y[count]);*/
					    }
					else /* point is on CH, but which one ? */
					    {
						if      (depth[count] == 1)
						    drawPoint((new point((X[count]),Y[count])), Color.blue);
						else if (depth[count] == 2)
						    drawPoint((new point((X[count]),Y[count])), Color.orange);    
						else if (depth[count] == 3)
						    drawPoint((new point((X[count]),Y[count])), Color.cyan);  
						else if (depth[count] == 4)
						    drawPoint((new point((X[count]),Y[count])), Color.lightGray);  
						else if (depth[count] == 5)
						    drawPoint((new point((X[count]),Y[count])), Color.magenta);  
						else if (depth[count] == 6)
						    drawPoint((new point((X[count]),Y[count])), Color.yellow);  
						else if (depth[count] == 7)
						    drawPoint((new point((X[count]),Y[count])), Color.pink);
						
						else if (depth[count] == 8)
						    drawPoint((new point((X[count]),Y[count])), Color.blue); 
						else if (depth[count] == 9)
						    drawPoint((new point((X[count]),Y[count])), Color.orange);    
						else if (depth[count] == 10)
						    drawPoint((new point((X[count]),Y[count])), Color.cyan);  
						else if (depth[count] == 11)
						    drawPoint((new point((X[count]),Y[count])), Color.lightGray);  
						else if (depth[count] == 12)
						    drawPoint((new point((X[count]),Y[count])), Color.magenta);  
						else if (depth[count] == 13)
						    drawPoint((new point((X[count]),Y[count])), Color.yellow);  
						else if (depth[count] == 14)
						    drawPoint((new point((X[count]),Y[count])), Color.pink); 
						
						else if (depth[count] >= 15)
						    drawPoint((new point((X[count]),Y[count])), Color.blue); 
						
					    }
					/* now to compute the exact CH median */
					if (depth[count] == peel_number) /* peel_number is the greatest CH depth */
					    {
						CHmean_sumX += X[count];
						CHmean_sumY += Y[count];
						innerCHpts++;
					    }
					else if (depth[count] == 0)
					    {
						flag = 1;
						killmeX += X[count];
						killmeY += Y[count];
						innerCHpts2++;
					    }
				    }
				if (flag == 1)/* found at least one point with depth 0, i.e. not on CH */
				    {
					CHmean.x = killmeX/innerCHpts2;
					CHmean.y = killmeY/innerCHpts2;
				    }
				else
				    {
					CHmean.x = CHmean_sumX/innerCHpts;
					CHmean.y = CHmean_sumY/innerCHpts;
				    }
				drawPoint(CHmean, Color.green);
				
			    }
				/* draw mean */
			System.out.println("totalpoints: "+totalpoints);
			if (totalpoints > 1)
			    drawPoint(greg, Color.red);
			/* end copying*/
			
			/*System.out.println("point: "+evt.x+","+evt.y);*/
		    }
		else
		    System.out.println("thats 100 points already!");  
	    }
	/********************************************************************************************/
/********************************************************************************************/
/********************************************************************************************/
/********************************************************************************************/


	if (evt.id == Event.MOUSE_DRAG)/* user is PLAYING */
	    {
		if (totalpoints < 101) /* have added extra point above */
		    {
			sumX -= X[totalpoints]; /* delete latest point from mean summation...*/
			sumY -= Y[totalpoints];
			
			X[totalpoints] = evt.x; /* ... recalculate it....*/
			Y[totalpoints] = evt.y;	
			
			Graphics g = getGraphics(); /* clear board */
			g.setColor(Color.white);
			g.fillRect(0,0,500,350);
			
			sumX = sumX + evt.x;/*... and re-add pt to summation for the mean*/
			sumY = sumY + evt.y;
			
			greg.x = (sumX/totalpoints);   /*recalculate mean */
			greg.y = (sumY/totalpoints);
			
			
			
			/* recalculate convex hull peeling */
			/* CODE FROM HERE ON IS IDENTICAL TO MOUSE_DOWN CODE */
			
				if (totalpoints >= 3)
			    {
				int i; int j;
				double angle;
				int Yminindex = 1;
				int Ymaxindex = 1;
				int Ymin = 10000;
				int Ymax = -1;
				int GlobalYmin;
				int Yminindex2 = 1;
				int remainingCH = 0;
				peel_number = 0;
				for (i = 1; i <= 100; i++)
				    {
					CH[i] = 0; /* no points on CH yet */
					depth[i] = 0;
				    }
				int keep_peeling = 1;
					
				
				while (keep_peeling == 1)
				    {
					peel_number++;   /* how many times have we peeled ? */
					/*new*/ Ymin = 10000;
					/*new*/ Ymax = -1;
					for (i = 1; i <= totalpoints; i++)
					    {			
						if (CH[i] == 0) /* points on CH are "erased" */ 
						    {
							if (Y[i] < Ymin)
							    {
								Ymin = Y[i];
								Yminindex = i;
								Yminindex2 = i;
							    }
							else if (Y[i] == Ymin)
							    {
								if (X[i] < X[Yminindex])
								    Yminindex = i; /* leftmost Ymin */
								if (X[i] > X[Yminindex2])
								    Yminindex2 = i; /* rightmost Ymin */
							    }
							if (Y[i] > Ymax)
							    {
								Ymax = Y[i];
								Ymaxindex = i;
							    }
							else if (Y[i] == Ymax)
							    {
								if (X[i] > X[Ymaxindex])
								    Ymaxindex = i;
							    }
						    }
					    }/* now we should have Ymin and Ymax, with indices */
					/*System.out.println("Ymin: "+Ymin+" at index "+Yminindex);
					  System.out.println("Ymax: "+Ymax+" at index "+Ymaxindex);*/
					GlobalYmin = Ymin;
					
					/*
					for (i = 1; i <= totalpoints; i++)
					    System.out.println("point "+i+" : "+X[i]+","+Y[i]);
					*/
					
					
					double minangle = -10000; /* minus Inf */
					double maxangle = -1;     /* bogus */
					int nextCH = -1;
					CH[Yminindex] = 1;   /* place point with smallest Ycoord on the CH */
					CH[Yminindex2] = 1; /* if another Ymin exists put it on CH too */
					depth[Yminindex] = peel_number;
					depth[Yminindex2] = peel_number;
				/* the following while loop will construct the left chain of the CH, 
				   starting from Ymin and going up, (clockwise) until Ymax is reached*/
					while (Yminindex != Ymaxindex)
					    {
						/*System.out.println(" ");
						  System.out.println("--- Entering LHS while loop");*/
						minangle = -10000;
						maxangle = -1;         
						nextCH = -1;
						/* System.out.println("I'm going to check the next candidate");*/
						
						for (i = 1; i <= totalpoints; i++)
						    {
							/*consider all points */
				/*if the point we're looking at is not on the CH chain
				  yet, and it is higher than the last point added... */
							/*if (CH[i] == 1)
							  System.out.println("point "+X[i]+","+Y[i]+" is on CH");
							  else
							  System.out.println("point "+X[i]+","+Y[i]+" not  on CH");
							*/
							if ((CH[i] == 0) && (Y[i] >= Y[Yminindex]))
							    {/*
							       System.out.println("   it's larger than Ymin, so i'll check it");	*/
								if (X[i] == X[Yminindex])
								    angle = 10000;/* larger than any ratio */
								else
								    {
									angle = ((double) (Y[i]-Y[Yminindex]))/
									    ((double) (X[i]-X[Yminindex]));
								    }
								/*want angle to be largest negative (close to 0)*/
								/*if no negatives, largest positive (close to Inf)*/  
							       
								if (angle < 0) /* if negative angle, Q2 */
								    {
									if (angle > minangle)/* see if closer to 0*/
									    {
										minangle = angle;
										nextCH = i;
									    }
								    }
								else if (angle == 0) /* this should only happen at Ymax */
								    {
									if (Y[Yminindex] == Y[Ymaxindex])
									    nextCH  = Ymaxindex;
								    }
								else       /* if angle strictly positive */
								    if (minangle == -10000) /*otherwise dont bother
											      with Q1 */
									if (angle > maxangle)
									    {
										maxangle = angle;
										nextCH = i;
									    }
									
								/* System.out.println("   angle= "+angle);*/
							    }
							
						    }
						/*
						  System.out.println("I select point "+X[nextCH]+","+Y[nextCH]+" as next CHvertex");*/
				/*now we have the next CH vertex index*/
				/* if there was a negative angle, it was found,
				   otherwise the largest angle was found */
						CH[nextCH] = 1; /* add point to CH */
						depth[nextCH] = peel_number;
						Ymin = Y[nextCH]; /* update the new "Ymin" on the left chain*/
						Yminindex = nextCH; 
						/*System.out.println("New Ymin: "+Ymin);*/
					    } /* end while */
					/* draw LCH points green */
					/*
					if (totalpoints >= 3)
					    for (count = 1; count <= totalpoints; count++)
						{
						    if (CH[count] == 1)
							{
							    drawPoint((new point((X[count]+5),Y[count])), Color.green);
							    System.out.println("CH pt "+count+": "+X[count]+","+Y[count]);
							}
						}
					*/
					
				/* NOW DO THE RHS OF THE CHAIN */
					CH[Ymaxindex] = 0;      /* this is necessary to compute RHS correctly */
					/*System.out.println(" ");
					System.out.println(" ");
					System.out.println("Doing RHS now !");*/
					
					Yminindex = Yminindex2;  /* now Yminindex is the rightmost Ymin */
					Ymin = GlobalYmin; /* restore Ymin, since it had changed on LH of CH */
					
					minangle = 10001; /* Inf + 1 */
					maxangle = 1;     /* bogus */
					nextCH = -1;
					
				/* the following while loop will construct the right chain of the CH, 
				   starting from Ymin and going up, (counterclockwise) until Ymax is reached*/
					while (Yminindex != Ymaxindex)
					    {
						minangle = 10001; /* angles in Q1 */
						maxangle = 1;         /* in Q2 */
						nextCH = -1;
						/*System.out.println("I'm going to check the next candidate");*/
						
						for (i = 1; i <= totalpoints; i++)
						    {/*consider all points */
				/*if the point we're looking at is not on the CH chain
				  yet, and it is higher than the last point added... */
							/*
							if (CH[i] == 1)
							    System.out.println("point "+X[i]+","+Y[i]+" is on CH");
							else
							    System.out.println("point "+X[i]+","+Y[i]+" not  on CH");
							*/
							if ((CH[i] == 0) && (Y[i] >= Y[Yminindex]))
							    {/*
							       System.out.println("   it's larger than Ymin, so i'll check it");	*/
								if (X[i] == X[Yminindex])
								    angle = 10000;/* Inf : larger than any ratio */
								else
								    {
									angle = ((double) (Y[i]-Y[Yminindex]))/
									    ((double) (X[i]-X[Yminindex]));
								    }
								/*want angle to be smallest positive (close to 0)*/
								/*if no positives, smallest negative (close to -Inf)*/
								if (angle > 0) /* if positive angle, Q1 */
								    {
									if (angle < minangle)/* see if closer to 0*/
									    {
										minangle = angle;
										nextCH = i;
									    }
								    }
								else if (angle == 0) /*  do nothing */
									; 
								else        /* if angle negative */
								    if (minangle == 10001) /*otherwise dont bother
											     with Q2 */
									if (angle < maxangle)
									    {
										maxangle = angle;
										nextCH = i;
									    }
								/*System.out.println("   angle= "+angle);*/
							    }
							
						    }
						if (nextCH == -1) /* there are no points on RCH */
						    Yminindex = Ymaxindex;  /* dont go back into while loop */
						else
						    {/*
						       System.out.println("I select point "+X[nextCH]+","+Y[nextCH]+" as next CHvertex");*/
				/*now we have the next CH vertex index*/
				/* if there was a negative angle, it was found,
				   otherwise the largest angle was found */
							CH[nextCH] = 1;
							depth[nextCH] = peel_number; /* add point to CH */
							Ymin = Y[nextCH]; /* update the new "Ymin" on the left chain*/
							Yminindex = nextCH; 
							/*System.out.println("New Ymin: "+Ymin);*/
						    }
					    } /* end while */
					
					remainingCH = 0;
					for (i = 1; i <= totalpoints; i++)
					    remainingCH += CH[i]; /* count pts on CH */
					if ((totalpoints-remainingCH) <= 3) /* still have >3 pts not on CH*/ 
					    keep_peeling = 0;
					
					
				    }	/* end while keep_peeling */
			    } /* end if totalpoints >=3 */
			
			
			/* draw all points */
			if (totalpoints < 3)
			    for (count = 1; count <= totalpoints; count++)
				drawPoint((new point(X[count],Y[count])), Color.blue);
			
			
			int CHmean_sumX = 0;
			int CHmean_sumY = 0;
			int killmeX = 0;
			int killmeY = 0;
			int flag = 0;
			int innerCHpts = 0;
			int innerCHpts2 = 0;
			point CHmean = new point(0,0);
			if (totalpoints >= 3)
			    {
				for (count = 1; count <= totalpoints; count++)
				    {
					if (CH[count] != 1)
					    {
						drawPoint((new point((X[count]),Y[count])), Color.black);
						/*System.out.println("CH pt "+count+": "+X[count]+","+Y[count]);*/
					    }
					else /* point is on CH, but which one ? */
					    {
						if      (depth[count] == 1)
						    drawPoint((new point((X[count]),Y[count])), Color.blue);
						else if (depth[count] == 2)
						    drawPoint((new point((X[count]),Y[count])), Color.orange);    
						else if (depth[count] == 3)
						    drawPoint((new point((X[count]),Y[count])), Color.cyan);  
						else if (depth[count] == 4)
						    drawPoint((new point((X[count]),Y[count])), Color.lightGray);  
						else if (depth[count] == 5)
						    drawPoint((new point((X[count]),Y[count])), Color.magenta);  
						else if (depth[count] == 6)
						    drawPoint((new point((X[count]),Y[count])), Color.yellow);  
						else if (depth[count] == 7)
						    drawPoint((new point((X[count]),Y[count])), Color.pink); 


						else if (depth[count] == 8)
						    drawPoint((new point((X[count]),Y[count])), Color.blue); 
						else if (depth[count] == 9)
						    drawPoint((new point((X[count]),Y[count])), Color.orange);    
						else if (depth[count] == 10)
						    drawPoint((new point((X[count]),Y[count])), Color.cyan);  
						else if (depth[count] == 11)
						    drawPoint((new point((X[count]),Y[count])), Color.lightGray);  
						else if (depth[count] == 12)
						    drawPoint((new point((X[count]),Y[count])), Color.magenta);  
						else if (depth[count] == 13)
						    drawPoint((new point((X[count]),Y[count])), Color.yellow);  
						else if (depth[count] == 14)
						    drawPoint((new point((X[count]),Y[count])), Color.pink); 
						
						else if (depth[count] >= 15)
						    drawPoint((new point((X[count]),Y[count])), Color.blue); 

					    }
					
					if (depth[count] == peel_number) /* peel_number is the greatest CH depth */
					    {
						CHmean_sumX += X[count];
						CHmean_sumY += Y[count];
						innerCHpts++;
					    }
					else if (depth[count] == 0)
					    {
						flag = 1;
						killmeX += X[count];
						killmeY += Y[count];
						innerCHpts2++;
					    }
				    }
				if (flag == 1)
				    {
					CHmean.x = killmeX/innerCHpts2;
					CHmean.y = killmeY/innerCHpts2;
				    }
				else
				    {
					CHmean.x = CHmean_sumX/innerCHpts;
					CHmean.y = CHmean_sumY/innerCHpts;
				    }
				drawPoint(CHmean, Color.green);
				
			    }
				/* draw mean */
			if (totalpoints > 1)
			    drawPoint(greg, Color.red);
			
			/* UP TO HERE CH  CODE IS IDENTICAL */
			/*
			  for (count = 1; count <= totalpoints; count++)
			  drawPoint((new point(X[count],Y[count])), Color.blue);
			  if (totalpoints > 1)
			  drawPoint(greg, Color.red);
			*/
		    }
	    }
	return true;
    }
    
    /*-**********************************************
     *
     *  ACTION FUNCTIONS
     *
     */
    
    // Attempt to add a new point p to the polygon P
    /*****************ADD A POINT**********************/
    void AddToPolygon(point p)
    {
	int i;
	boolean simple = true;
	
	if (P.n == 0)  // first point in the polygon
	    {
		P.addVertex(p);
		//P_backup.addVertex(p); //backup copy
		drawPoint(p,Color.blue);
	    }
	else
	    {
		segment NewEdge;
		boolean close = false;
		if (!near(P.vlist[P.n-1],p))
		    {
			if ( near(P.vlist[0],p) || (P.n == P.maxsize) )
			    {
				// potential closing edge
				NewEdge = new segment(P.vlist[P.n-1],P.vlist[0]);
				close = true;  P.closed = true;
				if (NewEdge.equals(new segment(P.vlist[0], P.vlist[1])))
				    {
					simple = false;
				    }
			    }
			else
			    {
				// potential next edge
				NewEdge = new segment(P.vlist[P.n-1], p);
			    }
			
			for (i = 0; i < (P.n-2); i++)
			    {
				if (close == true) { i++; close = false; }
				
				if ( near(P.vlist[i+1],p) ) { simple = false; break; }
				else
				    {
            			// considered intersection edge
					segment CurrEdge = new segment(P.vlist[i],P.vlist[i+1]);
					
					if (intersect(NewEdge,CurrEdge)) { simple = false; break;}
				    }
			    }
			
			if (simple)
			    { //draw the new edge...
				drawSegment(NewEdge,Color.blue);
				if (NewEdge.head().equals(P.vlist[0]))
				    {
					System.out.println("P closed: " + P.n + " vertices");
				    }
				else 
				    { P.addVertex(NewEdge.head()); 
				    //P_backup.addVertex(p);
				    }
			    }
			else { P.closed = false; }
		    }
	    }
    }
    
    
    //******************************************************
    //*******************Sklansky's 3 coins algorithm*******
    public boolean Sklansky(boolean withSteps)
    {polygon Q;
	   point back;
	   point center;
	   point front;
	   point temp;

	  	int startIndex;
	  	int currentIndex;
	  	boolean rightTurn = true;
	  	Color tempColor;
	  	
	  	if(UsingExample == true)
	  	  { Q = CEx;
	  	  }
	  	else
	  		{Q = P;
	  		}

	  	
	  	startIndex = ExtremePoint(Q);
	  	currentIndex = startIndex;
	  	
	  	//we now place our 3 coins 

	  	back = Q.vlist[startIndex];
	  	center = Q.vlist[(startIndex+1)%Q.n];
	  	front = Q.vlist[(startIndex+2)%Q.n];
	  	
	  	//System.out.println("(-1+Q.n)% Q.n ="+((-1+Q.n) %Q.n));
	
	  	if(turn(Q.vlist[(startIndex -1 +Q.n)%Q.n],back,center) == -1)
	  	  {rightTurn = false;
	  	  	System.out.println("Left turn! swap time: "+ currentIndex);
	  	  	P = this.ReLabel(startIndex);
	  	  	Q = P;
	  	  	back = Q.vlist[0];
	  	  	center = Q.vlist[1];
	  	  	front = Q.vlist[2];
	  	  	startIndex = 0;
	  	  	
	  	  	if(turn(Q.vlist[Q.n - 1],back,center) == -1)
	  	  	   {System.out.println("Error: still a left turn!!");
	  	  	   }
	  	  }
	  	else
	  	  {	  	  	
	  	  	rightTurn = true;
	  	  	System.out.println("Right turn: things are good: "+ currentIndex);
	  	  }
	  	
	  	back.coin = Color.black;
	  	center.coin = Color.red;
	  	front.coin = Color.gray;
	  	
	  	drawCoin(back);
	  	drawCoin(center);
	  	drawCoin(front);
	  	//we have the coins in place, know which way to go...
	  	//here is the meat... for now we assume right turns only...
     	if(withSteps)
	  		{
	  			NextStep.P = Q;
	  			NextStep.back = back;
	  			NextStep.center = center;
	  			NextStep.front = front;
	  			NextStep.startIndex = startIndex;
	  			return(true);
	  		}
	  	
	  	while(!front.equals(Q.vlist[startIndex]) 
	  		     || (turn(back,center,front) == -1))
	  			{if(turn(back,center,front) != -1)
		  				{
		  				//right turn or collinear
		  				 //System.out.println("RIGHT TURN!");
		  					tempColor = back.coin;
		  				 back.coin = Color.blue; //erase the coin!	
		  				 redrawPoint(back,
		  				 			        Q.vlist[Q.prev(back.index)],
		  				 							Q.vlist[Q.next(back.index)],
		  				 							Q.vlist[(back.index - 1 +Q.n)%Q.n],
		  				 							Q.vlist[(back.index+1)%Q.n],
		  				 							Color.blue);
		  				 back = center;	
		  				 center = front;
		  				 front = Q.vlist[Q.next(front.index)];
		  				 front.coin = tempColor;	
		  		     //we need to redraw some stuff here...
		  				 drawCoin(back);
		  					drawCoin(center);
		  					drawCoin(front);
		  					//drawCoin(Q.vlist[Q.prev(back.index)]); //remove coin
		  				}
	  				else
	  					{//left turn: remove a vertex
	  					 //System.out.println("LEFT TURN!");
	  					 temp =	back;
	  					 tempColor = center.coin;
	  					 back = Q.vlist[Q.prev(back.index)];
	  					 back.coin = tempColor;
	  					 System.out.println("Removed: "+center.index);
	  					 center.removed = true;
	  					 center.coin = Color.blue; //erase coin	
	  					 //we need to draw stuff here!
	  					 //drawCoin(center);  //remove coin
	  					 redrawPoint(center,
		  				 							Q.vlist[Q.prev(center.index)],
		  				 							Q.vlist[Q.next(center.index)],
		  				 						  Q.vlist[(center.index - 1 +Q.n)%Q.n],
		  				 							Q.vlist[(center.index+1)%Q.n],
		  				 							Color.blue);
	  					 center = temp;
	  						drawNewSeg(new segment(center,front));
	  						drawCoin(back);
	  						drawCoin(center);
	  						drawCoin(front);	  					
	  					}
	  			}	  	
	  	
	  		return(false);
	  }
	
	/**********************Sklansky while loop using steps**************/
	public boolean StepSklansky()
			{Color tempColor;
				point temp;
				
				if(NextStep.front.equals(NextStep.P.vlist[NextStep.startIndex]) 
	  		     && !(turn(NextStep.back,NextStep.center,NextStep.front) == -1))
						{
							return(false);
						}
				else
	  			{if(turn(NextStep.back,NextStep.center,NextStep.front) != -1)
		  				{
		  				//right turn or collinear
		  				 //System.out.println("RIGHT TURN!");
		  					tempColor = NextStep.back.coin;
		  				 NextStep.back.coin = Color.blue; //erase the coin!	
		  				 redrawPoint(NextStep.back,
		  				 							NextStep.P.vlist[NextStep.P.prev(NextStep.back.index)],
		  				 							NextStep.P.vlist[NextStep.P.next(NextStep.back.index)],
		  				 							NextStep.P.vlist[(NextStep.back.index - 1 +NextStep.P.n)%NextStep.P.n],
		  				 							NextStep.P.vlist[(NextStep.back.index+1)%NextStep.P.n],
		  				 							Color.blue);
		  				 NextStep.back = NextStep.center;
		  				 NextStep.center = NextStep.front;
		  				 NextStep.front = NextStep.P.vlist[NextStep.P.next(NextStep.front.index)];
		  				 NextStep.front.coin = tempColor;	
		  		     //we need to redraw some stuff here...
		  				 drawCoin(NextStep.back);
		  					drawCoin(NextStep.center);
		  					drawCoin(NextStep.front);
		  					//drawCoin(NextStep.P.vlist[NextStep.P.prev(NextStep.back.index)]); 
		  					//remove coin
		  				}
	  			else
	  					{//left turn: remove a vertex
	  					 //System.out.println("LEFT TURN!");
	  					 temp =	NextStep.back;
	  					 tempColor = NextStep.center.coin;
	  					 NextStep.back = NextStep.P.vlist[NextStep.P.prev(NextStep.back.index)];
	  					 NextStep.back.coin = tempColor;
	  					 System.out.println("Removed: "+NextStep.center.index);
	  					 NextStep.center.removed = true;
		  				 redrawPoint(NextStep.center,
		  				 							NextStep.P.vlist[NextStep.P.prev(NextStep.center.index)],
		  				 							NextStep.P.vlist[NextStep.P.next(NextStep.center.index)],
		  				 							NextStep.P.vlist[(NextStep.center.index - 1 +NextStep.P.n)%NextStep.P.n],
		  				 							NextStep.P.vlist[(NextStep.center.index+1)%NextStep.P.n],		  				 							
		  				 							Color.blue);

	  					 NextStep.center.coin = Color.blue; //erase coin	
	  						
	  					 //we need to draw stuff here!
	  					 //drawCoin(NextStep.center);  //remove coin
	  					 NextStep.center = temp;
	  						drawNewSeg(new segment(NextStep.center,NextStep.front));
	  						drawCoin(NextStep.back);
	  						drawCoin(NextStep.center);
	  						drawCoin(NextStep.front);	  					
	  					}
	  			}	  		
				
				return(true);
			}
	
	/*###########################################################*/
	/*#####################Don't go past here!##################*/
  /*-***********************************************************
   *
   *  SUPPORT FUNCTIONS
   *
   */
  // returns true if p1 and p2 are "near" eachother
  boolean near(point p1, point p2)
  {
    return ((Math.abs(p1.x - p2.x) <= 3) &&
	    (Math.abs(p1.y - p2.y) <= 3));
  }


  /*
   * returns 1 if abc is a right turn
   *        -1 if abc is a left turn
   *         0 if a, b, and c are collinear
   */

  byte turn(point a, point b, point c)
  {	
    point[] T = { a , b , c };  // Triangle defined by points
    int AreaT = 0;  // Area of triangle
    
    AreaT += (T[0].x * T[1].y) - (T[0].y * T[1].x);
    AreaT += (T[1].x * T[2].y) - (T[1].y * T[2].x);
    AreaT += (T[2].x * T[0].y) - (T[2].y * T[0].x);

    if (AreaT > 0) return 1;  // right turn
    if (AreaT < 0) return -1; // left turn
    return 0;		      // collinear
  }

  // returns true if s1 and s2 intersect
  boolean intersect(segment s1, segment s2)
  {
    int t1h,t1t,t2h,t2t;

    if (!bbintersect(s1,s2)) // Quick rejection
    {
      return false;
    }
    else // Bounding boxes of edges intersect
    {
      if (!s1.equals(s2))
      {
        t1h = turn(s1.head(),s1.tail(),s2.head());
        t1t = turn(s1.head(),s1.tail(),s2.tail());
    
        if ((t1h == t1t)&&(t1h != 0)&&(t1t != 0)) { return false; }
      
        t2h = turn(s2.head(),s2.tail(),s1.head());
        t2t = turn(s2.head(),s2.tail(),s1.tail());

        if ((t2h == t2t)&&(t2h != 0)&&(t2t != 0)) { return false; }
      }
    }
    return true;
  }
 
  // Intersection of bounding boxes of two line segments
  boolean bbintersect(segment s1, segment s2)
  {
    int xmin1,xmax1,ymin1,ymax1;
    int xmin2,xmax2,ymin2,ymax2;

    // min and max x-coords of s1
    if (s1.head().x >= s1.tail().x)
      { xmin1 = s1.tail().x; xmax1 = s1.head().x;}
    else
      { xmin1 = s1.head().x; xmax1 = s1.tail().x;}

    // min and max y-coords of s1
    if (s1.head().y >= s1.tail().y)
      { ymin1 = s1.tail().y; ymax1 = s1.head().y;}
    else
      { ymin1 = s1.head().y; ymax1 = s1.tail().y;}

    // min and max x-coords of s2
    if (s2.head().x >= s2.tail().x)
      { xmin2 = s2.tail().x; xmax2 = s2.head().x;}
    else
      { xmin2 = s2.head().x; xmax2 = s2.tail().x;}

    // min and max y-coords of s2
    if (s2.head().y >= s2.tail().y)
      { ymin2 = s2.tail().y; ymax2 = s2.head().y;}
    else
      { ymin2 = s2.head().y; ymax2 = s2.tail().y;}

    return ((xmax1 >= xmin2) && (xmax2 >= xmin1) &&
	    (ymax1 >= ymin2) && (ymax2 >= ymin2));
  }
}