/*
 * Copyright (c) 2007 Alexander Hristov.
 * http://www.ahristov.com
 * 
 * Feel free to use this code as you wish, as long as you keep this copyright
 * notice. The only limitation on use is that this code cannot be republished
 * on other web sites. 
 *
 * As usual, this code comes with no warranties of any kind.
 *
 * 
 */
 
  public ArrayList<Point> quickHull(ArrayList<Point> points) {
    ArrayList<Point> convexHull = new ArrayList<Point>();
    if (points.size() < 3) return (ArrayList)points.clone();
    // find extremals
    int minPoint = -1, maxPoint = -1;
    int minX = Integer.MAX_VALUE;
    int maxX = Integer.MIN_VALUE;
    for (int i = 0; i < points.size(); i++) {
      if (points.get(i).x < minX) {
        minX = points.get(i).x;
        minPoint = i;
      } 
      if (points.get(i).x > maxX) {
        maxX = points.get(i).x;
        maxPoint = i;       
      }
    }
    Point A = points.get(minPoint);
    Point B = points.get(maxPoint);
    convexHull.add(A);
    convexHull.add(B);
    points.remove(A);
    points.remove(B);
    
    ArrayList<Point> leftSet = new ArrayList<Point>();
    ArrayList<Point> rightSet = new ArrayList<Point>();
    
    for (int i = 0; i < points.size(); i++) {
      Point p = points.get(i);
      if (pointLocation(A,B,p) == -1)
        leftSet.add(p);
      else
        rightSet.add(p);
    }
    hullSet(A,B,rightSet,convexHull);
    hullSet(B,A,leftSet,convexHull);
    
    return convexHull;
  }
  
  /*
   * Computes the square of the distance of point C to the segment defined by points AB
   */
  public int distance(Point A, Point B, Point C) {
    int ABx = B.x-A.x;
    int ABy = B.y-A.y;
    int num = ABx*(A.y-C.y)-ABy*(A.x-C.x);
    if (num < 0) num = -num;
    return num;
  }
  
  public void hullSet(Point A, Point B, ArrayList<Point> set, ArrayList<Point> hull) {
    int insertPosition = hull.indexOf(B);
    if (set.size() == 0) return;
    if (set.size() == 1) {
      Point p = set.get(0);
      set.remove(p);
      hull.add(insertPosition,p);
      return;
    }
    int dist = Integer.MIN_VALUE;
    int furthestPoint = -1;
    for (int i = 0; i < set.size(); i++) {
      Point p = set.get(i);
      int distance  = distance(A,B,p);
      if (distance > dist) {
        dist = distance;
        furthestPoint = i;
      }
    }
    Point P = set.get(furthestPoint);
    set.remove(furthestPoint);
    hull.add(insertPosition,P);
    
    // Determine who's to the left of AP
    ArrayList<Point> leftSetAP = new ArrayList<Point>();
    for (int i = 0; i < set.size(); i++) {
      Point M = set.get(i);
      if (pointLocation(A,P,M)==1) {
        leftSetAP.add(M);
      }
    }
    
    // Determine who's to the left of PB
    ArrayList<Point> leftSetPB = new ArrayList<Point>();
    for (int i = 0; i < set.size(); i++) {
      Point M = set.get(i);
      if (pointLocation(P,B,M)==1) {
        leftSetPB.add(M);
      }
    }
    hullSet(A,P,leftSetAP,hull);
    hullSet(P,B,leftSetPB,hull);
    
  }

  public int pointLocation(Point A, Point B, Point P) {
    int cp1 = (B.x-A.x)*(P.y-A.y) - (B.y-A.y)*(P.x-A.x);
    return (cp1>0)?1:-1;
  }