Skip to content

Instantly share code, notes, and snippets.

@adunsmoor
Last active December 17, 2018 08:45
Show Gist options
  • Save adunsmoor/e848356a57980ab9f822 to your computer and use it in GitHub Desktop.
Save adunsmoor/e848356a57980ab9f822 to your computer and use it in GitHub Desktop.
closed convex hull in Swift
import UIKit
// Returns a list of points on the convex hull in counter-clockwise order.
// Note: the last point in the returned list is the same as the first one.
//
// https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
//
func closedConvexHull(points_ : [CGPoint]) -> [CGPoint] {
// 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
// Returns a positive value, if OAB makes a counter-clockwise turn,
// negative for clockwise turn, and zero if the points are collinear.
func cross(P: CGPoint, A: CGPoint, B: CGPoint) -> CGFloat {
let part1 = (A.x - P.x) * (B.y - P.y)
let part2 = (A.y - P.y) * (B.x - P.x)
return part1 - part2;
}
// Sort points lexicographically
let points = sorted(points_) {
$0.x == $1.x ? $0.y < $1.y : $0.x < $1.x
}
// Build the lower hull
var lower: [CGPoint] = []
for p in points {
while lower.count >= 2 && cross(lower[lower.count-2], lower[lower.count-1], p) <= 0 {
lower.removeLast()
}
lower.append(p)
}
// Build upper hull
var upper: [CGPoint] = []
for p in reverse(points) {
while upper.count >= 2 && cross(upper[upper.count-2], upper[upper.count-1], p) <= 0 {
upper.removeLast()
}
upper.append(p)
}
// Last point of upper list is omitted because it is repeated at the
// beginning of the lower list.
upper.removeLast()
// Concatenation of the lower and upper hulls gives the convex hull.
return (upper + lower)
}
var points = map ( 0..<100 ) { CGPointMake(CGFloat($0/10), CGFloat($0%10)) }
var hull = closedConvexHull(points)
for point in hull {
println(point)
}
@jmdecombe
Copy link

Not sure that code even compiles on its own with sorted() and reversed(), plus parameter names are missing in both calls to the cross() function, and the last parameter p should really be the first?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment