Find the points which form a convex hull from a set of arbitrary two dimensional points.

For example, given the points (16,3), (12,17), (0,6), (-4,-6), (16,6), (16,-7), (16,-3), (17,-4), (5,19), (19,-8), (3,16), (12,13), (3,-4), (17,5), (-3,15), (-3,-9), (0,11), (-9,-3), (-4,-2) and (12,10) the convex hull would be (-9,-3), (-3,-9), (19,-8), (17,5), (12,17), (5,19) and (-3,15).




See also
 Convex Hull (youtube)
 http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/


// Use Graham Scan to sort points into a convex hull
// https://en.wikipedia.org/wiki/Graham_scan, O(n log n)
// http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
// http://geomalgorithms.com/a10-_hull-1.html
fcn grahamScan(points){
   N:=points.len();
   # find the point with the lowest y-coordinate, x is tie breaker
   p0:=points.reduce(fcn([(a,b)]ab,[(x,y)]xy){
	if(b<y)ab else if(b==y and a<x)ab else xy });
   #sort points by polar angle with p0, ie ccw from p0
   points.sort('wrap(p1,p2){ ccw(p0,p1,p2)>0 });
 
   # We want points[0] to be a sentinel point that will stop the loop.
   points.insert(0,points[-1]);
   M:=1; # M will denote the number of points on the convex hull.
   foreach i in ([2..N]){
      # Find next valid point on convex hull.
      while(ccw(points[M-1], points[M], points[i])<=0){
	 if(M>1) M-=1;
	 else if(i==N) break;  # All points are collinear
	 else i+=1;
      }
      points.swap(M+=1,i); # Update M and swap points[i] to the correct place.
   }
   points[0,M]
}
# Three points are a counter-clockwise turn if ccw > 0, clockwise if
# ccw < 0, and collinear if ccw = 0 because ccw is a determinant that
# gives twice the signed  area of the triangle formed by p1, p2 and p3.
fcn ccw(a,b,c){  // a,b,c are points: (x,y)
   ((b[0] - a[0])*(c[1] - a[1])) - ((b[1] - a[1])*(c[0] - a[0]))
}