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/


public struct Point: Equatable, Hashable {
  public var x: Double
  public var y: Double
 
  public init(fromTuple t: (Double, Double)) {
    self.x = t.0
    self.y = t.1
  }
}
 
public func calculateConvexHull(fromPoints points: [Point]) -> [Point] {
  guard points.count >= 3 else {
    return points
  }
 
  var hull = [Point]()
  let (leftPointIdx, _) = points.enumerated().min(by: { $0.element.x < $1.element.x })!
 
  var p = leftPointIdx
  var q = 0
 
  repeat {
    hull.append(points[p])
 
    q = (p + 1) % points.count
 
    for i in 0..<points.count where calculateOrientation(points[p], points[i], points[q]) == .counterClockwise {
      q = i
    }
 
    p = q
  } while p != leftPointIdx
 
  return hull
}
 
private func calculateOrientation(_ p: Point, _ q: Point, _ r: Point) -> Orientation {
  let val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y)
 
  if val == 0 {
    return .straight
  } else if val > 0 {
    return .clockwise
  } else {
    return .counterClockwise
  }
}
 
private enum Orientation {
  case straight, clockwise, counterClockwise
}
 
let 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),
  (12,10)
].map(Point.init(fromTuple:))
 
print("Input: \(points)")
print("Output: \(calculateConvexHull(fromPoints: points))")