Implementing Graham Scan in Swift

'ConvexHull' 'Swift'でぐぐってみたら、なんだか物足りなかったので、なんとなく。

import simd

public struct Graham
{
    var target: [SIMD2<Float>] = []
        
    public func scan() -> [SIMD2<Float>] {
        guard let lowestPoint = target.most(in: lower)
            else { return [] }
        return scanLeftTurn(startPoint: lowestPoint,
                            angleOrder: target
                                .filter({ $0 != lowestPoint })
                                .sorted{ lowBiasedAngle(with: lowestPoint)($0,$1) })
    }
    
    func scanLeftTurn(startPoint head: SIMD2<Float>, angleOrder tail: [SIMD2<Float>]) -> [SIMD2<Float>]
    {
        var stack: [SIMD2<Float>] = []
        stack.push(head); stack.push(tail[0])
        for vertex in tail[1..<tail.count] {
            while ( !left( stack.top(1) , stack.top(0), vertex ) ) {
                _ = stack.pop()
            }
            stack.push(vertex)
        }
        return stack
    }

}

func lowBiasedAngle(with h: SIMD2<Float>) -> (_ pi: SIMD2<Float>,_ pj: SIMD2<Float>) -> Bool
{
    { (pi, pj) in areaSign( h, pi, pj ) != .negative }
}

func left(_ a: SIMD2<Float>,_ b: SIMD2<Float>,_ c: SIMD2<Float> ) -> Bool
{
    areaSign( a, b, c ) == .positive
}

func lower<Scalar: Comparable>(_ lhs: SIMD2<Scalar>, _ rhs: SIMD2<Scalar> ) -> Bool {
    lhs.y < rhs.y || (lhs.y == rhs.y && lhs.x > rhs.x)
}

enum Compare {
    case negative
    case even
    case positive
}

func areaSign(_ a: SIMD2<Float>,_ b: SIMD2<Float>,_ c: SIMD2<Float>) -> Compare
{
    let area2 = cross(b - a, c - a).z
    if abs(area2) < .ulpOfOne { return .even }
    else if area2 >  0        { return .positive }
    return .negative
}

extension Array {
    func most(in condition: (Element, Element) -> Bool) -> Element? {
        reduce(nil) { lhs, rhs in
            guard let lhs = lhs
                else { return rhs }
            return condition(lhs, rhs) ? lhs : rhs
        }
    }
}

extension Array {
    mutating func push(_ element: Element) {
        append(element)
    }
    mutating func pop() -> Element {
        removeLast()
    }
    func top(_ i: Int) -> Element {
        self[count - 1 - i]
    }
}

Reference

O'Rourke,J. (1998). Computational Geometry in C, 2nd edn, Cambridge: Cambridge University Press.