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/


typedef Point = {x:Float, y:Float};
 
class Main {
 
    // Calculate orientation for 3 points
    // 0 -> Straight line
    // 1 -> Clockwise
    // 2 -> Counterclockwise
    static function orientation(pt1:Point, pt2:Point, pt3:Point): Int
    {
      var val = ((pt2.x - pt1.x) * (pt3.y - pt1.y)) - 
                ((pt2.y - pt1.y) * (pt3.x - pt1.x));
      if (val == 0)
        return 0;
      else if (val > 0)
        return 1;
      else return 2;
    }
 
    static function convexHull(pts:Array<Point>):Array<Point> {
      var result = new Array<Point>();
 
      // There must be at least 3 points
      if (pts.length < 3)
        for (i in pts) result.push(i);
 
      // Find the leftmost point
      var indexMinX = 0;
      for (i in 0...(pts.length - 1))
        if (pts[i].x < pts[indexMinX].x)
          indexMinX = i;
 
      var p = indexMinX;
      var q = 0;
 
      while (true) {
        // The leftmost point must be part of the hull.
        result.push(pts[p]);
 
        q = (p + 1) % pts.length;
 
        for (i in 0...(pts.length - 1))
          if (orientation(pts[p], pts[i], pts[q]) == 2) q = i;
 
        p = q;
 
        // Break from loop once we reach the first point again.
        if (p == indexMinX) 
          break;
      }
      return result;
    }
 
    static function main() {
      var pts = new Array<Point>();
      pts.push({x: 16, y: 3});
      pts.push({x: 12, y: 17});
      pts.push({x: 0, y: 6});
      pts.push({x: -4, y: -6});
      pts.push({x: 16, y: 6});
 
      pts.push({x: 16, y: -7});
      pts.push({x: 16, y: -3});
      pts.push({x: 17, y: -4});
      pts.push({x: 5, y: 19});
      pts.push({x: 19, y: -8});
 
      pts.push({x: 3, y: 16});
      pts.push({x: 12, y: 13});
      pts.push({x: 3, y: -4});
      pts.push({x: 17, y: 5});
      pts.push({x: -3, y: 15});
 
      pts.push({x: -3, y: -9});
      pts.push({x: 0, y: 11});
      pts.push({x: -9, y: -3});
      pts.push({x: -4, y: -2});
      pts.push({x: 12, y: 10});
 
      var hull = convexHull(pts);
      Sys.print('Convex Hull: [');
      var length = hull.length;
      var i = 0;
      while (length > 0) {
        if (i > 0)
          Sys.print(', ');
        Sys.print('(${hull[i].x}, ${hull[i].y})');
        length--;
        i++;
      }
      Sys.println(']');
    }
}