import java.awt.*;
import java.util.*;

public class QuickHull extends GeometricAlgorithm {
  java.util.Vector hullEdges;
  Gpoint[] points;
  int interiorPointColor= 1;
  int initialPointColor = 2;
  int internalEdgeColor = 3;
  int hullEdgeColor     = 4;
  int hullColor         = 5;

  Gsegment aq=new Gsegment();

  void quickhull (Gsegment ab, int l, int r) {
     if (l <= r) {
      int i,s1,s2,pivot;
      double maxDist=0.0;
      double dist;
      Gpoint P,q,tmp;
      Gpoint a = ab.start(), b=ab.end();
      Gsegment aP,Pb;

      pivot = l;
      for (i=l; i<=r; i++) {
	q = points[i];
	aq.set(a,q);
	dist = aq.length() * Math.sin(ab.angle(aq));
	if (dist<0.0) dist = -dist;	  
	if (dist >= maxDist) {
	  maxDist = dist;
	  pivot = i;
	}
      }
      
      tmp = points[l];
      points[l] = points[pivot];
      points[pivot] = tmp;
      P = points[l];

      aP = new Gsegment(a,P);
      Pb = new Gsegment(P,b);
      view.beginEventGroup(3,"extendhull");
      view.addElement(aP);
      view.addElement(Pb);

      hullEdges.addElement(aP);
      hullEdges.addElement(Pb);

      view.endEventGroup();

      view.delElement(ab);
      hullEdges.removeElement(ab);

      i = l+1;
      s1 = l;
      s2 = r+1;

      while (i<s2) {
	q = points[i];
	if (view.ccw(a,P,q) > 0.0) {
	  view.beginEventGroup(1,"colorpoint");
	  view.changeElementColor(points[i],1,2);
	  view.endEventGroup();
	  tmp = points[++s1];
	  points[s1] = points[i];
	  points[i++] = tmp;
	}
	else if (view.ccw(P,b,q) > 0.0) {
	  view.beginEventGroup(1,"colorpoint");
	  view.changeElementColor(points[i],1,5);
	  view.endEventGroup();
	  tmp = points[--s2];
	  points[s2] = points[i];
	  points[i] = tmp;
	}
	else {
	  view.beginEventGroup(1,"colorpoint");
	  view.changeElementColor(points[i],1,interiorPointColor);
	  view.endEventGroup();
	  i++;
	}
      }

      quickhull (aP,l+1,s1);
      view.changeElementColor(P,2,6);
      quickhull (Pb,s2,r);
    }
  }

  public void run () {
    Geometry[] items = (Geometry[])data[0];
    points = new Gpoint[items.length];
    System.arraycopy(items,0,points,0,items.length);

    Gpoint a,b,q,tmp;
    double minX,maxX,x;
    int i,j,iLeft,iRight,iLower,iUpper;
    Gsegment ab,ba;

    view.setDimension(2);
    
    /* 
     *  An initial guess for the size of the hull
     */
    int initialSize = (int)Math.log((double)(points.length));
    hullEdges  = new java.util.Vector(initialSize);

    /* 
     * find the left and right extrema. These define the chord that
     * separates the upper and lower sets 
     */
    minX = maxX = points[0].x;
    iLeft = iRight = 0;
    for (i=1; i<points.length; i++) {
      q = points[i];
      x = q.x;
      if (x > maxX) {
	maxX = x;
	iRight = i;
      }
      if (x < minX) {
	minX = x;
	iLeft = i;
      }
    }

    /*
     * Partition the points into upper and lower sets 
     */
    tmp = points[0];
    points[0] = points[iRight];
    points[iRight] = tmp;

    a = points[0];
    b = points[iLeft];

    ab = new Gsegment(a,b);
    ba = new Gsegment(b,a);

    view.addElement(ab);
    view.addElement(ba);

    iUpper = 0;
    iLower = points.length;
    i = 1;

    view.beginEventGroup(iLower,"colorpoints");
    while (i < iLower) {
      q = points[i];
      if (view.ccw(b,a,q) < 0.0) {
	tmp = points[++iUpper];
	points[iUpper] = points[i];
	points[i++] = tmp;
	view.changeElementColor(points[iUpper],1,2);
      }
      else if (view.ccw(b,a,q) > 0.0) {
	tmp = points[--iLower];
	points[iLower] = points[i];
	points[i] = tmp;
	view.changeElementColor(points[iLower],1,5);
      }
      else {
	i++;
      }
    }
    view.endEventGroup();

    hullEdges.addElement(ab);
    hullEdges.addElement(ba);

    quickhull(ab, 1,      iUpper);
    quickhull(ba, iLower, points.length-1);

    int hullSize = hullEdges.size();
    Gsegment[] orderedEdges = new Gsegment[hullSize];
    Gsegment curEdge = (Gsegment) hullEdges.elementAt(0), nextEdge;
    orderedEdges[0] = curEdge;
    for (i=1; i<hullSize; i++) {
      for (j=1; j<hullSize; j++) {
	nextEdge = (Gsegment) hullEdges.elementAt(j);
	if (nextEdge.start == curEdge.end) {
	  orderedEdges[i] = nextEdge;
	  curEdge = nextEdge;
	  break;
	}
      }
    }

    Gpoint[] verts = new Gpoint[hullSize];
    for (i=0; i<hullSize; i++) {
      verts[i] = orderedEdges[i].start;
    }
    Gpoly hull = new Gpoly(verts, Gpoly.FILLED);

    view.beginEventGroup(1,"finalizepolygon");
    
    view.addElement(hull,hullEdgeColor);
    view.endEventGroup();

    view.done();
  }
}