Graham Scan in Swift

GrahamScan.swift

struct Point: CustomStringConvertible {
  let x: Int
  let y: Int
  
  func theta(anchor: Point) -> Float {
    let dx = Float(x - anchor.x)
    let dy = Float(y - anchor.y)
    let t = dy / (abs(dx) + abs(dy))
    if dx == 0 && dy == 0 {
      return 0
    } else if dx < 0 {
      return 2 - t
    } else if dy < 0 {
      return 4 + t
    } else {
      return t
    }
  }
  
  func continuesLeftTurn(first first: Point, middle: Point) -> Bool {
    return (first.x - x) * (middle.y - y) - (first.y - y) * (middle.x - x) > 0
  }
  
  var description: String {
    return "(\(x), \(y))"
  }
}

func getHull(points: [Point]) -> [Int] {
  guard let first = points.first else {
    return []
  }
  let anchor = points.reduce(first) { smallest, compare in
    if compare.y < smallest.y {
      return compare
    } else if compare.y == smallest.y && compare.x < smallest.x {
      return compare
    } else {
      return smallest
    }
  }
  let sortedPointsWithIndex = points.enumerate().sort { a, b in
    let (_, pta) = a
    let (_, ptb) = b
    return pta.theta(anchor) < ptb.theta(anchor)
  }
  var hull = [Int]()
  for (i, point) in sortedPointsWithIndex {
    if hull.count < 2 {
      hull.append(i)
    } else {
      let fst = points[hull[hull.endIndex - 2]]
      let mid = points[hull[hull.endIndex - 1]]
      if !point.continuesLeftTurn(first: fst, middle: mid) {
        hull.removeLast()
      }
      hull.append(i)
    }
  }
  return hull
}

let hull = getHull([
  Point(x: 1, y: 1),
  Point(x: 2, y: 2),
  Point(x: 3, y: 3),
  Point(x: 1, y: 3),
])
print(hull)