77 lines
1.4 KiB
Swift
77 lines
1.4 KiB
Swift
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))")
|