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/


F orientation(p, q, r)
   V val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y)
   I val == 0
      R 0
   R I val > 0 {1} E 2
 
F calculateConvexHull(points)
   [(Int, Int)] result
 
   I points.len < 3
      R points
 
   V indexMinX = 0
   L(p) points
      V i = L.index
      I p.x < points[indexMinX].x
         indexMinX = i
 
   V p = indexMinX
   V q = 0
 
   L
      result.append(points[p])
 
      q = (p + 1) % points.len
 
      L(i) 0 .< points.len
         I orientation(points[p], points[i], points[q]) == 2
            q = i
 
      p = q
      I p == indexMinX
         L.break
 
   R result
 
V points = [(16, 3), 
            (12, 17), 
            (0, 6), 
            (-4, -6), 
            (16, 6), 
            (16, -7), 
            (17, -4), 
            (5, 19), 
            (19, -8), 
            (3, 16), 
            (12, 13), 
            (3, -4), 
            (17, 5), 
            (-3, 15), 
            (-3, -9), 
            (0, 11), 
            (-9, -3), 
            (-4, -2), 
            (12, 10)]
 
V hull = calculateConvexHull(points)
L(i) hull
   print(i)