RotatingCalipers Playground

RotatingCalipers.swift

import XCTest

struct Point {
    let x: Double
    let y: Double
}

class RotatingCalipers {
    // Calculate distance between two points
    private func distance(_ p1: Point, _ p2: Point) -> Double {
        let dx = p2.x - p1.x
        let dy = p2.y - p1.y
        return sqrt(dx * dx + dy * dy)
    }
    
    // Calculate cross product to determine turn direction
    private func crossProduct(_ p1: Point, _ p2: Point, _ p3: Point) -> Double {
        return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x)
    }
    
    // Get convex hull using Graham's scan (needed for rotating calipers)
    private func convexHull(_ points: [Point]) -> [Point] {
        guard points.count >= 3 else { return points }
        
        // Sort by x-coordinate
        let sorted = points.sorted { $0.x < $1.x || ($0.x == $1.x && $0.y < $1.y) }
        var upper: [Point] = []
        var lower: [Point] = []
        
        // Build lower hull
        for point in sorted {
            while lower.count >= 2 {
                let cp = crossProduct(lower[lower.count - 2],
                                    lower[lower.count - 1],
                                    point)
                if cp <= 0 { break }
                lower.removeLast()
            }
            lower.append(point)
        }
        
        // Build upper hull
        for point in sorted.reversed() {
            while upper.count >= 2 {
                let cp = crossProduct(upper[upper.count - 2],
                                    upper[upper.count - 1],
                                    point)
                if cp <= 0 { break }
                upper.removeLast()
            }
            upper.append(point)
        }
        
        // Combine hulls, removing duplicate endpoints
        upper.removeLast()
        lower.removeLast()
        return lower + upper
    }
    
    func findMostDistantPair(_ points: [Point]) -> (Point, Point, Double) {
        guard points.count >= 2 else {
            if points.count == 1 { return (points[0], points[0], 0) }
            return (points[0], points[1], distance(points[0], points[1]))
        }
        
        // Get convex hull
        let hull = convexHull(points)
        let n = hull.count
        guard n >= 2 else { return (hull[0], hull[0], 0) }
        
        // Initialize variables for maximum distance
        var maxDistance = 0.0
        var farthestPair = (hull[0], hull[1])
        
        // Initialize calipers
        var i = 0
        var j = 1
        
        // Rotating calipers algorithm
        while i < n || j < n {
            // Calculate current distance
            let currentDistance = distance(hull[i % n], hull[j % n])
            if currentDistance > maxDistance {
                maxDistance = currentDistance
                farthestPair = (hull[i % n], hull[j % n])
            }
            
            // Find the next points to rotate
            let nextI = (i + 1) % n
            let nextJ = (j + 1) % n
            
            // Calculate angles to determine which pointer to move
            let v1 = Point(x: hull[nextI].x - hull[i % n].x,
                         y: hull[nextI].y - hull[i % n].y)
            let v2 = Point(x: hull[nextJ].x - hull[j % n].x,
                         y: hull[nextJ].y - hull[j % n].y)
            
            let cross = v1.x * v2.y - v1.y * v2.x
            
            if i >= n || (j < n && cross <= 0) {
                j += 1
            } else {
                i += 1
            }
        }
        
        return (farthestPair.0, farthestPair.1, maxDistance)
    }
}

class RotatingCalipersTests: XCTestCase {
    var calipers: RotatingCalipers!
    
    override func setUp() {
        super.setUp()
        calipers = RotatingCalipers()
    }
    
    override func tearDown() {
        calipers = nil
        super.tearDown()
    }
    
    func testSquare() {
        let points = [
            Point(x: 0, y: 0),
            Point(x: 0, y: 1),
            Point(x: 1, y: 0),
            Point(x: 1, y: 1)
        ]
        
        let (p1, p2, distance) = calipers.findMostDistantPair(points)
        let expectedDistance = sqrt(2.0) // Diagonal of unit square
        debugPrint("testSquare: distance \(distance) expected \(expectedDistance)")
        XCTAssertEqual(distance, expectedDistance, accuracy: 0.0001)
        XCTAssertTrue(
            (p1.x == 0 && p1.y == 0 && p2.x == 1 && p2.y == 1) ||
            (p1.x == 1 && p1.y == 1 && p2.x == 0 && p2.y == 0) ||
            (p1.x == 0 && p1.y == 1 && p2.x == 1 && p2.y == 0) ||
            (p1.x == 1 && p1.y == 0 && p2.x == 0 && p2.y == 1)
        )
    }
    
    func testTriangle() {
        let points = [
            Point(x: 0, y: 0),
            Point(x: 1, y: 0),
            Point(x: 0, y: 1)
        ]
        
        let (p1, p2, distance) = calipers.findMostDistantPair(points)
        let expectedDistance = sqrt(2.0) // Hypotenuse
        debugPrint("testTriangle: distance \(distance) expected \(expectedDistance)")
        XCTAssertEqual(distance, expectedDistance, accuracy: 0.0001)
    }
    
    func testPerformance() {
        let n = 1000
        var points: [Point] = []
        for _ in 0..<n {
            points.append(Point(x: Double.random(in: 0...100),
                              y: Double.random(in: 0...100)))
        }
        
        measure(metrics: [XCTClockMetric()]) {
            _ = calipers.findMostDistantPair(points)
        }
    }
    
    
    func testSampleData() {
        let points = [
            Point(x: 22.2769931, y: 114.2285758),
            Point(x: 22.2769931, y: 114.2285758),
            Point(x: 22.2769747, y: 114.2285489),
            Point(x: 22.2769931, y: 114.2285758),
            Point(x: 22.2769931, y: 114.2285758),
            Point(x: 22.2769747, y: 114.2285489)
        ]

        print("testSampleData: \(calipers.findMostDistantPair(points))")
    }
}

extension Point: Equatable {
    static func == (lhs: Point, rhs: Point) -> Bool {
        return lhs.x == rhs.x && lhs.y == rhs.y
    }
}

RotatingCalipersTests.defaultTestSuite.run()


/*
Test Suite 'RotatingCalipersTests' started at 2025-03-22 12:08:59.136.
Test Case '-[__lldb_expr_11.RotatingCalipersTests testPerformance]' started.
<unknown>:0: Test Case '-[__lldb_expr_11.RotatingCalipersTests testPerformance]' measured [Clock Monotonic Time, s] average: 0.320, relative standard deviation: 0.328%, values: [0.321331, 0.321667, 0.320036, 0.319805, 0.318791], performanceMetricID:com.apple.dt.XCTMetric_Clock.time.monotonic, baselineName: "", baselineAverage: , polarity: prefers smaller, maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.000, maxStandardDeviation: 0.000
Test Case '-[__lldb_expr_11.RotatingCalipersTests testPerformance]' passed (3.711 seconds).
Test Case '-[__lldb_expr_11.RotatingCalipersTests testSampleData]' started.
testSampleData: (__lldb_expr_11.Point(x: 22.2769747, y: 114.2285489), __lldb_expr_11.Point(x: 22.2769931, y: 114.2285758), 3.259094965857658e-05)
Test Case '-[__lldb_expr_11.RotatingCalipersTests testSampleData]' passed (0.002 seconds).
Test Case '-[__lldb_expr_11.RotatingCalipersTests testSquare]' started.
"testSquare: distance 1.4142135623730951 expected 1.4142135623730951"
Test Case '-[__lldb_expr_11.RotatingCalipersTests testSquare]' passed (0.001 seconds).
Test Case '-[__lldb_expr_11.RotatingCalipersTests testTriangle]' started.
"testTriangle: distance 1.4142135623730951 expected 1.4142135623730951"
Test Case '-[__lldb_expr_11.RotatingCalipersTests testTriangle]' passed (0.001 seconds).
Test Suite 'RotatingCalipersTests' passed at 2025-03-22 12:09:02.854.
	 Executed 4 tests, with 0 failures (0 unexpected) in 3.715 (3.718) seconds

*/