Anonymous user
Convex hull: Difference between revisions
Add Swift
(Add Swift) |
|||
Line 2,557:
Convex Hull (9 points): (-3, -9) (1, -9) (14, -9) (19, -8) (17, 5) (12, 17) (5, 19) (-3, 15) (-9, -3)
</pre>
=={{header|Swift}}==
{{trans|Rust}}
<lang 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))")</lang>
{{out}}
<pre>Input: [Point(x: 16.0, y: 3.0), Point(x: 12.0, y: 17.0), Point(x: 0.0, y: 6.0), Point(x: -4.0, y: -6.0), Point(x: 16.0, y: 6.0), Point(x: 16.0, y: -7.0), Point(x: 16.0, y: -3.0), Point(x: 17.0, y: -4.0), Point(x: 5.0, y: 19.0), Point(x: 19.0, y: -8.0), Point(x: 3.0, y: 16.0), Point(x: 12.0, y: 13.0), Point(x: 3.0, y: -4.0), Point(x: 17.0, y: 5.0), Point(x: -3.0, y: 15.0), Point(x: -3.0, y: -9.0), Point(x: 0.0, y: 11.0), Point(x: -9.0, y: -3.0), Point(x: -4.0, y: -2.0), Point(x: 12.0, y: 10.0)]
Output: [Point(x: -9.0, y: -3.0), Point(x: -3.0, y: -9.0), Point(x: 19.0, y: -8.0), Point(x: 17.0, y: 5.0), Point(x: 12.0, y: 17.0), Point(x: 5.0, y: 19.0), Point(x: -3.0, y: 15.0)]</pre>
=={{header|Visual Basic .NET}}==
| |||