Last active
December 17, 2018 08:45
-
-
Save adunsmoor/e848356a57980ab9f822 to your computer and use it in GitHub Desktop.
closed convex hull in Swift
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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?