
%\noindent \textbf{Graham Scan for computing Convex Hulls}
\subsection{Convex Hulls - Graham Scan, Melkman}


\lstset{language=Java}
\begin{lstlisting}
import java.awt.geom.*;
import java.util.*;
import java.awt.*;
import java.io.*;

public class ConvexHull {
  private class PDD extends Point2D.Double {
    PDD(double x, double y) { super(x,y); }
  }

 public static void main(String[] args)
                 throws IOException {
   new ConvexHull().run();
 }

 public void run() throws IOException {
   ArrayList<PDD> hull,
                  pts = new ArrayList<PDD>();
   Scanner fin = new Scanner(System.in);

   int datasets = fin.nextInt();
   for(int ds=0; ds < datasets; ++ds) {
     pts.clear();
     int N = fin.nextInt();

     for(int i = 0; i < N; ++i) {
       double px = fin.nextDouble();
       double py = fin.nextDouble();
       pts.add(new PDD(px,py));
     }

     hull = convexHull(pts);

     Polygon p = new Polygon();
     for(PDD pt : hull) {
      p.addPoint(pt.x, pt.y);
     }
     Area a = new Area(p);
     System.out.println(
       "Area of convex hull is: "
         + areaOf(a));
   }
 }

// Melkman's algorithm (for polylines): 38 lines
  double area( PDD a, PDD b, PDD c) {
      return (b.x-a.x)*(c.y-a.y) -
             (c.x-a.x)*(b.y-a.y);
  }

  public ArrayList<PDD>
  MconvexHull(ArrayList<PDD> v) {
      int n = v.size();
      PDD[] D = new PDD[2*n + 1];
      int bot = n-2, top = bot+3;
      D[bot] = D[top] = v.get(2);
      if(area( v.get(0), v.get(1),
                         v.get(2) ) > 0) {
          D[bot+1] = v.get(0);
          D[bot+2] = v.get(1);
      } else {
          D[bot+1] = v.get(1);
          D[bot+2] = v.get(0);
      }
      for(int i = 3; i < n; ++i) {
          PDD x = v.get(i);
          if((area(D[bot],
                   D[bot+1], x) > 0) &&
             (area(D[top-1],
                   D[top], x) > 0) )
                  continue;
          while(area(D[bot],
                     D[bot+1], x) <= 0)
              ++bot;
          D[--bot] = x;
          while(area(D[top-1],
                     D[top], x) <= 0)
              --top;
          D[++top] = x;
      }
      ArrayList<PDD> rv =
           new ArrayList<PDD>();
      int h;
      for(h=0; h < (top-bot); ++h)
         rv.add(D[bot+h]);
      return rv;
  }

// Graham Scan, for set of points: 53 lines
  private class PtCmp
          implements Comparator<PDD> {
    public int compare(PDD a, PDD b) {
      if(a.y < b.y) return -1;
      if(a.y > b.y) return 1;
      if(a.x < b.x) return -1;
      if(a.x > b.x) return 1;
      return 0;
    }
  }

  class AngleCmp implements Comparator<PDD> {
    PDD p;
    AngleCmp(PDD pt) { p = pt; }
    public int compare(PDD a, PDD b) {
      // clockwise -> right turns
      return -DIRECTION * ccw(p, a, b);
    }
  }
 // -1 means ccw/left
 static final int DIRECTION = -1;

 // c is on line ab, close to a: -1;
 //     after b: 1. between = 0
 public int ccw( PDD a, PDD b, PDD c) {
   return Line2D.relativeCCW(a.x, a.y,
                        b.x, b.y, c.x, c.y);
 }

 static double areaOf(Shape s) {
  PathIterator i = s.getPathIterator(null);
  double[] coords = new double[6];
  int r;
  double area = 0.;
  double mx, my, lx, ly, x, y;
  mx= my= lx= ly= 0.;
  while(!i.isDone()) {
    r = i.currentSegment(coords);
    x = coords[0]; y = coords[1];

   if(r == PathIterator.SEG_LINETO) {
      area += (lx*y - x*ly);
   } else if(r == PathIterator.SEG_CLOSE) {
      area += (lx*my - mx*ly);
   } else if(r == PathIterator.SEG_MOVETO) {
      mx = x;
      my = y;
   }
    lx = x; ly = y;
    i.next();
  }
  return Math.abs(area/2);
 }

 public ArrayList<PDD>
 convexHull(ArrayList<PDD> l) {
   PDD p, last, next2last;

   // find pivot
   p = Collections.min(l, new PtCmp());

   l.remove(p); // remove pivot from sort
   Collections.sort(l, new AngleCmp(p));

   Stack<PDD> stack = new Stack<PDD>();
   stack.push(p); // add pivot back
   stack.push(l.get(0));
   for(int i = 1; i < l.size(); ++i) {
     boolean done = false;
     while(!done && stack.size() > 1) {
       last = stack.pop();
       next2last = stack.peek();
       stack.push(last);
       // "good" ccw pt means left turn
       if( DIR == ccw(next2last, last,
                          l.get(i))) {
         done = true;
       } else  stack.pop();
     }
     stack.push(l.get(i));
   }

   return new ArrayList<PDD>(stack);
 }
}

\end{lstlisting}
\normalsize

\noindent \textbf{End Graham Scan for Convex Hulls}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "../ref-doc"
%%% End:
