circleintersection.swift

import UIKit

/// High precedence
precedencegroup HighPrecedence { higherThan: BitwiseShiftPrecedence }

/// Exponentiation operator
infix operator **: HighPrecedence

extension CGFloat {
    /// Returns base ^^ exp
    /// - parameter base: the base value
    /// - parameter exp: the exponentiation value
    public static func **(base: CGFloat, exp: CGFloat) -> CGFloat {
        return CGFloat(pow(Double(base), Double(exp)))
    }
    
    /// Pi
    public static var pi = CGFloat(Double.pi)
    
    /// Tau
    public static var tau = CGFloat(Double.pi * 2.0)
}

/// 2-point representation of line segment
public struct Segment {
    public let (p1, p2): (CGPoint, CGPoint)
    public var dx: CGFloat { return p2.x - p1.x }
    public var dy: CGFloat { return p2.y - p1.y }
    public var length: CGFloat { return sqrt(dx ** 2 + dy ** 2) }
}

/// Center/Radius circle representation
public struct Circle {
    public let center: CGPoint
    public let radius: CGFloat

    /// Return a line segment representing the two intersection points
    /// between self and another circle
    public func intersects(_ other: Circle) -> Segment? {
        
        // It's a lot more convenient to break this down into
        // conventional terms, which are used throughout this short
        // method
        let (x1, y1, r1) = (self.center.x, self.center.y, self.radius)
        let (x2, y2, r2) = (other.center.x, other.center.y, other.radius)
        
        // Calculate the distance from center1 to center2
        let R = Segment(p1: self.center, p2: other.center).length
        
        // Test for intersection
        guard abs(r1 - r2) <= R, R <= (r1 + r2)
            else { return nil }
        
        let (R2, R4) = (R ** 2, R ** 4)
        let a = (r1 * r1 - r2 * r2) / (2 * R2)
        let dSquares = (r1 * r1 - r2 * r2)
        let c = sqrt(2 * (r1 * r1 + r2 * r2) / R2 - (dSquares * dSquares) / R4 - 1)
        
        let (fx, fy) = ((x1 + x2) / 2 + a * (x2 - x1), (y1 + y2) / 2 + a * (y2 - y1))
        let (gx, gy) = (c * (y2 - y1) / 2, c * (x1 - x2) / 2)
        
        return Segment(p1: CGPoint(x: fx + gx, y: fy + gy),
                       p2: CGPoint(x: fx - gx, y: fy - gy))
    }
    
    /// Return the two angles representing the projection from 
    /// a circle's center to the endpoints of a line segment.
    ///
    /// This method does not test for isNaN
    public func angles(for segment: Segment) -> (CGFloat, CGFloat) {
        let segment1 = Segment(p1: self.center, p2: segment.p1)
        let segment2 = Segment(p1: self.center, p2: segment.p2)
        return (atan2(segment1.dy, segment1.dx),
                atan2(segment2.dy, segment2.dx))
    }
    
    /// Returns a Bezier path sweeping between two angles
    public func path(from startAngle: CGFloat = 0, to endAngle: CGFloat = CGFloat.tau, clockwise: Bool = true) -> UIBezierPath {
        return UIBezierPath(arcCenter: center, radius: radius,
                            startAngle: startAngle, endAngle: endAngle,
                            clockwise: clockwise)
    }
    
    /// Intersection Error
    public struct IntersectionError: Error { let message: String }
    
    /// Returns a Bezier path representing removing circle 2 from circle 1
    public static func - (c1: Circle, c2: Circle) throws -> UIBezierPath {
        // test intersection
        guard let segment = c1.intersects(c2)
            else { throw IntersectionError(message: "\(c1) does not intersect \(c2)") }
        
        let angles1 = c1.angles(for: segment)
        let angles2 = c2.angles(for: segment)
        
        let path = UIBezierPath()
        path.append(c1.path(from: angles1.0, to: angles1.1, clockwise: false))
        path.append(c2.path(from: angles2.0, to: angles2.1, clockwise: false))
        path.usesEvenOddFillRule = true
        return path
    }
}

func test(_ c1: Circle, _ c2: Circle) -> UIImage {
    let size = CGSize(width: 200, height: 200)
    let renderer = UIGraphicsImageRenderer(size: size)
    let image = renderer.image { context in
        
        // recenter drawing context
        context.cgContext.translateBy(x: size.width / 2.0, y: size.height / 2.0)
        
        // draw circles
        c1.path().stroke()
        c2.path().stroke()

        // test intersection
        guard let segment = c1.intersects(c2)
            else { return }
        
        // Draw points
        UIColor.red.set()
        
        let p1 = Circle(center: segment.p1, radius: 2.5)
        p1.path().fill()
        
        let p2 = Circle(center: segment.p2, radius: 2.5)
        p2.path().fill()

        // Draw
        UIColor.blue.set()
        let path = try! c1 - c2
        path.fill()
        
        // Draw smaller version of c2
        UIColor.green.set()
        let c3 = Circle(center: c2.center, radius: c2.radius * 0.75)
        c3.path().fill()
    }

    return image
}

let circle1 = Circle(center: CGPoint(x: 50, y: 50), radius: 30)
let circle2 = Circle(center: CGPoint(x: 75, y: 25), radius: 15)
let circle3 = Circle(center: CGPoint(x: 0, y: 0), radius: 15)


test(circle1, circle2)
test(circle1, circle3)