public class ConvexHull {
  private static Sequence hull;
  private static Point2D anchorPoint;
  private static GeomTester2D geomTester = new GeomTester2DImpl();
  // public class method
  public static Sequence grahamScan (Sequence points) {
    Point2D p1, p2;
    copyInputPoints(points); // copy into hull the sequence of input points
    switch (hull.size()) {
    case 0: case 1:
      return hull;
    case 2:
      p1 = (Point2D)hull.first().element();
      p2 = (Point2D)hull.last().element();
      if (geomTester.areEqual(p1,p2))
	hull.remove(hull.last());
      return hull;
    default:  // at least 3 input points
      // compute anchor point and remove it together with coincident points
      anchorPointSearchAndRemove();
      switch (hull.size()) {
      case 0: case 1:
	hull.insertFirst(anchorPoint);
	return hull;
      default:   // at least 2 input points left besides the anchor point
	sortPoints();// sort the points in hull around the anchor point
	// remove the (possible) initial collinear points in hull except the
	// farthest one from the anchor point
	removeInitialIntermediatePoints();
        if (hull.size() == 1)
	  hull.insertFirst(anchorPoint);
	else { // insert the anchor point as first and last element in hull
	  hull.insertFirst(anchorPoint);
	  hull.insertLast(anchorPoint);
	  scan(); // Graham's scan
	  // remove one of the two copies of the anchor point from hull
	  hull.remove(hull.last());
	}
	return hull;
      }
    }
  }