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/


# ccw returns true if the three points make a counter-clockwise turn
def ccw(a; b; c):
  a as [$ax, $ay]
  | b as [$bx, $by]
  | c as [$cx, $cy]
  | (($bx - $ax) * ($cy - $ay)) > (($by - $ay) * ($cx - $ax)) ;
 
def convexHull:
  if . == [] then []
  else sort as $pts
  # lower hull:
  | reduce $pts[] as $pt ([];
      until (length < 2 or ccw(.[-2]; .[-1]; $pt); .[:-1] )
      | . + [$pt] )
  # upper hull
  | (length + 1) as $t
  | reduce range($pts|length-2; -1; -1) as $i (.;
      $pts[$i] as $pt
      | until (length < $t or ccw(.[-2]; .[-1]; $pt); .[:-1] )
      | . + [$pt])
  | .[:-1]
  end ;