package ConvexHull;

import java.awt.*;
import java.awt.event.*;
import java.applet.*;
import java.util.Vector;

public class DrawingBoard extends Canvas {

	private ConvexHullApplet applet;
	private int width = 500;
	private int height = 500;
	private Vector points;
	private Vector convex_hull;
	private Point2D selected_point;
	private boolean is_polygon = false;
	private boolean is_closed = false;
	private AndrewsAlgorithm andrews;
	private boolean running_andrews = false;
	private boolean lock_x = false;
	private boolean lock_y = false;

	public DrawingBoard(ConvexHullApplet a) {
		setLocation(new Point(10, 10));
		setSize(new Dimension(width, height));
		setBackground(Color.white);
		
		applet = a;
		points = new Vector();
		convex_hull = new Vector();
		selected_point = null;
		andrews = new AndrewsAlgorithm();
		
		addMouseListener(new Mouse());
		addMouseMotionListener(new MouseMotion());
		addKeyListener(new Key());
	}
	
	public void paint(Graphics g) {
		// paint the guide lines
		if (!running_andrews && selected_point != null) {
			g.setColor(Color.gray);
			for (int i=0; i<points.size(); i++) {
				Point2D p = (Point2D) points.elementAt(i);
				if (selected_point == null || selected_point == p) continue;
				if (selected_point.x == p.x)
					g.drawLine(p.x, 0, p.x, height);
				if (selected_point.y == p.y)
					g.drawLine(0, height-p.y, width, height-p.y);
				if (selected_point.x == p.x || selected_point.y == p.y)
					g.drawRect(p.x-5, height-p.y-5, 9, 9);
			}
		}
		
		g.setColor(Color.black);
		paintPoints(points, is_polygon, is_closed, g);
		
		if (is_polygon) {
			g.setColor(Color.green.darker());
			paintPoints(convex_hull, true, true, g);
		}
		
		if (selected_point != null) {
			g.setColor(Color.red);
			g.fillOval(selected_point.x-3, height-selected_point.y-3, 6, 6);
		}
		
		if (running_andrews) {
			g.setColor(Color.blue);
			for (int i=0; i<andrews.points.length; i++)
				g.drawString(""+(i+1), andrews.points[i].x+10, height - andrews.points[i].y+20);
			
			if (andrews.state == andrews.DONE) {
				g.setColor(Color.green.darker().darker());
				paintPoints(andrews.convex_hull, true, true, g);
			}
			else if (andrews.state == andrews.INIT_UPPER_HULL || andrews.state == andrews.GROW_UPPER_HULL) {
				g.setColor(Color.green);
				paintPoints(andrews.upper_hull, true, false, g);
				g.setColor(Color.yellow);
				Point2D p = andrews.points[andrews.next_point];
				g.fillOval(p.x-3, height-p.y-3, 6, 6);
				if (andrews.upper_hull.size() > 0) {
					Point2D p1 = (Point2D) andrews.upper_hull.lastElement();
					g.drawLine(p1.x, height-p1.y, p.x, height-p.y);
				}
				paintTriangle(andrews.upper_hull, g);
			}
			else if (andrews.state == andrews.INIT_LOWER_HULL || andrews.state == andrews.GROW_LOWER_HULL) {
				g.setColor(Color.green.darker().darker());
				paintPoints(andrews.upper_hull, true, false, g);
				g.setColor(Color.green);
				paintPoints(andrews.lower_hull, true, false, g);
				g.setColor(Color.yellow);
				Point2D p = andrews.points[andrews.next_point];
				g.fillOval(p.x-3, height-p.y-3, 6, 6);
				if (andrews.lower_hull.size() > 0) {
					Point2D p1 = (Point2D) andrews.lower_hull.lastElement();
					g.drawLine(p1.x, height-p1.y, p.x, height-p.y);
				}
				paintTriangle(andrews.lower_hull, g);
			}
			else if (andrews.state == andrews.CONCAT_HULLS) {
				g.setColor(Color.green.darker().darker());
				paintPoints(andrews.upper_hull, true, false, g);
				g.setColor(Color.green);
				paintPoints(andrews.lower_hull, true, false, g);
			}
		}
	}
	
	private void paintPoints(Vector pts, boolean paint_edges, boolean closed, Graphics g) {
		for (int i=0; i<pts.size(); i++) {
			Point2D p = (Point2D)pts.elementAt(i);
			g.fillOval(p.x-4, height-p.y-4, 8, 8);
			if (paint_edges) {
				Point2D p2;
				if (i == pts.size()-1) {
					if (closed)
						p2 = (Point2D) pts.elementAt(0);
					else
						break;
				}
				else
					p2 = (Point2D) pts.elementAt(i+1);
				g.drawLine(p.x, height-p.y, p2.x, height-p2.y);
			}
		}
	}
	
	private void paintTriangle(Vector pts, Graphics g) {
		if (pts.size() >= 2) {
			Point2D p1 = (Point2D) pts.elementAt(pts.size()-2);
			Point2D p2 = (Point2D) pts.elementAt(pts.size()-1);
			Point2D p3 = andrews.points[andrews.next_point];
			if (p3.leftOf(p1, p2))
				g.setColor(Color.red);
			else
				g.setColor(Color.green);
			Polygon poly = new Polygon();
			poly.addPoint(p1.x, height-p1.y);
			poly.addPoint(p2.x, height-p2.y);
			poly.addPoint(p3.x, height-p3.y);
			g.fillPolygon(poly);
		}
	}
	
	private boolean pointValid(Point2D p, boolean new_point) {
		int index = points.indexOf(p);
	  // first check that p is not the same as any other point
	  for (int i=0; i<points.size(); i++)
	  	if (points.elementAt(i) == p && i != index)
	  		return false;
	  if (points.size() < 2) return true;
	  if (!is_polygon) return true;
	  
	  Point2D p1, p3, p4;
	  
		if (index >= 0) {
			// this is already a part of the polygon
			// first check one incident edge
			if (index > 0 || (index == 0 && is_closed)) {
				p1 = (index == 0) ? (Point2D) points.lastElement() : (Point2D) points.elementAt(index-1);
				for (int i=0; i<points.size(); i++) {
					if (i != index) {
						p4 = (Point2D) points.elementAt(i);
						p3 = (i == 0) ? (Point2D) points.lastElement() : (Point2D) points.elementAt(i-1);
						boolean strict = !(index == i-1 || (i == 0 && index == points.size()-1) 
								|| index == i+1 || (i == points.size()-1 && index == 0));
						if (intersect(p1, p, p3, p4, strict)) return false;
					}
				}
			}
			// then the other
			if (index < points.size()-1 || (index == points.size()-1 && is_closed)) {
				p1 = (index == points.size()-1) ? (Point2D) points.firstElement() : (Point2D) points.elementAt(index+1);
				for (int i=0; i<points.size(); i++) {
					if (i != index) {
						p3 = (Point2D) points.elementAt(i);
						p4 = (i == points.size()-1) ? (Point2D) points.firstElement() : (Point2D) points.elementAt(i+1);
						boolean strict = !(index == i-1 || (i == 0 && index == points.size()-1) 
								|| index == i+1 || (i == points.size()-1 && index == 0));
						if (intersect(p, p1, p3, p4, strict)) return false;
					}
				}
			}
		}
		else {
			// otherwise, this is a new point
			p1 = (Point2D) points.lastElement();
			for (int i=0; i<points.size()-2; i++) {
				p3 = (Point2D) points.elementAt(i);
				p4 = (Point2D) points.elementAt(i+1);
				if (intersect(p1, p, p3, p4, true)) 
					return false;
			}
			p3 = (Point2D) points.elementAt(points.size()-2);
			p4 = p1;
			if (intersect(p1, p, p3, p4, false)) 
				return false;
		}
		return true;
	}
	
	private boolean intersect(Point2D p1, Point2D p2, Point2D p3, Point2D p4, boolean strict) {
		// check whether line segment p1p2 intersects p3p4
		float t1 = (float) ((p4.x-p3.x)*(p1.y-p3.y) - (p4.y-p3.y)*(p1.x-p3.x));
		float t2 = (float) ((p2.x-p1.x)*(p1.y-p3.y) - (p2.y-p1.y)*(p1.x-p3.x));
		float t3 = (float) ((p4.y-p3.y)*(p2.x-p1.x) - (p4.x-p3.x)*(p2.y-p1.y));
		
		if (t1 == 0 && t3 == 0 && !strict) {
			// lines are coincident, check for intersection
			int len = (p2.x-p1.x)*(p2.x-p1.x) + (p2.y-p1.y)*(p2.y-p1.y);
			int dot = (p3.x-p1.x)*(p2.x-p1.x) + (p3.y-p1.y)*(p2.y-p1.y);
			if (dot > 0 && dot < len) return true;
			dot = (p4.x-p1.x)*(p2.x-p1.x) + (p4.y-p1.y)*(p2.y-p1.y);
			if (dot > 0 && dot < len) return true;
			len = (p4.x-p3.x)*(p4.x-p3.x) + (p4.y-p3.y)*(p4.y-p3.y);
			dot = (p1.x-p3.x)*(p4.x-p3.x) + (p1.y-p3.y)*(p4.y-p3.y);
			if (dot > 0 && dot < len) return true;
			dot = (p2.x-p3.x)*(p4.x-p3.x) + (p2.y-p3.y)*(p4.y-p3.y);
			if (dot > 0 && dot < len) return true;
		}
		else if (t3 == 0) 
			return false;
			
		float u = t1 / t3;
		float v = t2 / t3;
		if (strict)
			return (u >= 0 && u <= 1 && v >= 0 && v <= 1);
		else
			return (u > 0 && u < 1 && v > 0 && v < 1);
	}
	
	
	private class Mouse extends MouseAdapter { 
		public void mousePressed(MouseEvent e) {
			if (running_andrews) {
			}
			else {
				// see if ther is any point under the mouse
				for (int i=0; i<points.size(); i++) {
					Point2D p = (Point2D) points.elementAt(i);
					if (p.contains(e.getX(), height-e.getY())) {
						selected_point = p;
						if (e.isShiftDown()) {
							// restrict movement
							if (Math.abs(e.getX()-p.x) >= Math.abs(height-e.getY()-p.y))
								lock_y = true;
							else
								lock_x = true;
						}
						applet.statusLabel.setText(selected_point.toString());
						break;
					}
				}
				// if right-click, then delete the point under the mouse
				if (e.isMetaDown() && selected_point != null) {
					int index = points.indexOf(selected_point);
					points.removeElement(selected_point);
					if (points.size() > 2) {
						Point2D p = (index > points.size()-1) ? (Point2D) points.lastElement() : (Point2D) points.elementAt(index);
						if (!pointValid(p, false))
							points.insertElementAt(selected_point, index);						
					}
				}
				// otherwise, try to add a new point
				else if (!e.isMetaDown() && selected_point == null && !is_closed && !running_andrews) {
					Point2D p = new Point2D(e.getX(), height-e.getY());
					if (pointValid(p, true)) {
						points.addElement(p);
						selected_point = p;
					}
				}
				// recompute the convex hull
				if (convex_hull.size() != 0)
					convex_hull = PolygonConvexHull.computePolygonConvexHull(points);
				if (running_andrews)
					andrews.init(points);
			}
			repaint();
		}
		
		public void mouseReleased(MouseEvent e) {
			if (selected_point != null) {
				selected_point = null;
				lock_x = false;
				lock_y = false;
				repaint();
			}
		}
		
		public void mouseExited(MouseEvent e) {
			applet.statusLabel.setText("");
		}
	}
	
	private class MouseMotion extends MouseMotionAdapter {
		public void mouseMoved(MouseEvent e) {
			applet.statusLabel.setText("[" + e.getX() + ", " + (height-e.getY()) + "]");
		}
		
		public void mouseDragged(MouseEvent e) {
			if (!running_andrews) {
				applet.statusLabel.setText("[" + e.getX() + ", " + (height-e.getY()) + "]");
				if (selected_point != null) {
					int old_x = selected_point.x;
					int old_y = selected_point.y;
					// get possible new x position
					int x = (e.getX() < 0) ? 0 : e.getX();
					x = (x >= width) ? width-1 : x;
					// get possible new y position
					int y = (height-e.getY() < 0) ? 0 : height-e.getY();
					y = (y >= height) ? height-1 : y;
					// check movement restrictions
					if (lock_x) x = old_x;
					if (lock_y) y = old_y;
					selected_point.setPosition(x, y);
					if (!pointValid(selected_point, false))
						selected_point.setPosition(old_x, old_y);
					applet.statusLabel.setText(selected_point.toString());
					if (convex_hull.size() != 0)
						convex_hull = PolygonConvexHull.computePolygonConvexHull(points);
				}
				repaint();
			}
		}
	}
	
	private class Key extends KeyAdapter {
		public void keyPressed(KeyEvent e){
			if (e.getKeyCode() == e.VK_TAB) {
				points.removeAllElements();
				convex_hull.removeAllElements();
				selected_point = null;
				is_closed = false;
				running_andrews = false;
				is_polygon = !is_polygon;
				if (is_polygon)
					applet.statusLabel2.setText("Polygon Mode");
				else
					applet.statusLabel2.setText("Point Mode");
				repaint();
			}
			else if (e.getKeyCode() == e.VK_SPACE) {
				if (is_polygon) {
					if (!is_closed) {
						is_closed = true;
						is_closed = pointValid((Point2D) points.lastElement(), false);
					}
					else if (convex_hull.size() == 0)
						convex_hull = PolygonConvexHull.computePolygonConvexHull(points);
					else
						convex_hull.removeAllElements();
				}
				else {
					running_andrews = !running_andrews;
					if (running_andrews) {
						andrews.init(points);
						applet.statusLabel2.setText(andrews.getText());
					}
					else
						applet.statusLabel2.setText("Point Mode");
				}
				repaint();
			}
			else if (e.getKeyCode() == e.VK_DELETE) {
				points.removeAllElements();
				convex_hull.removeAllElements();
				selected_point = null;
				is_closed = false;
				running_andrews = false;
				repaint();
			}
			else if (e.getKeyCode() == e.VK_RIGHT) {
				if (running_andrews) {
					andrews.step();
					applet.statusLabel2.setText(andrews.getText());
					repaint();
				}
			}
			else if (e.getKeyCode() == e.VK_LEFT) {
				if (running_andrews) {
					andrews.init(points);
					applet.statusLabel2.setText(andrews.getText());
					repaint();
				}
			}
			else if (e.getKeyCode() == e.VK_DOWN) {
				if (running_andrews) {
					while (andrews.step());
					applet.statusLabel2.setText(andrews.getText());
					repaint();
				}
			}
			else if (e.getKeyCode() == e.VK_UP) {
				if (running_andrews) {
					while (andrews.step()) {
						applet.statusLabel2.setText(andrews.getText());
						update(getGraphics());
						try {Thread.sleep(500);} catch (Exception exc) {}
					}
				}
			}
		}
	}
	
}