closed convex hull in Swift

gistfile1.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)
}