Intersection of two circles in two dimensions

intersect_circles.py

from math import cos, sin, atan2

class Circle:
    def __init__(self, x, y, radius):
        self.x, self.y, self.radius = x, y, radius

def intersect_circles(first, second):
    """
    >>> intersect_circles(Circle(0, 0, 1), Circle(1, 1, 1))
    ((1.5700924586837752e-16, 1.0), (1.0, 0.0))
    >>> intersect_circles(Circle(-3, 0, 5), Circle(3, 0, 5))
    ((0.0, 4.0), (0.0, -4.0))
    >>> intersect_circles(Circle(0, 0, 1), Circle(2, 0, 1))
    (1.0, 0.0)
    >>> intersect_circles(Circle(0, 0, 1), Circle(3, 0, 1))
    >>> intersect_circles(Circle(0, 0, 1), Circle(1, 0, 0))
    (1.0, 0.0)
    """
    k = 1. / ((first.x - second.x)**2 + (first.y - second.y)**2) ** .5
    theta = atan2(second.y - first.y, second.x - first.x)
    r1 = k * first.radius
    r2 = k * second.radius
    numSolutions = 2
    # u and v are in a coordinate system that has been scaled, rotated, and translated
    # to move the two centers to (0, 0) and (1, 0) to simplify some of the math.
    u = (r1**2 + 1 - r2**2) / 2
    if abs(r1) < abs(u):
        return None    # the circles do not overlap
    elif abs(r1) == abs(u):
        numSolutions = 1
    v1 = (r1**2 - u**2) ** .5
    # Transform u and v back into the original coordinate system.
    x1 = first.x + (u * cos(theta) - v1 * sin(theta)) / k
    y1 = first.y + (v1 * cos(theta) + u * sin(theta)) / k
    if numSolutions == 1:
        return (x1, y1)
    v2 = -v1
    x2 = first.x + (u * cos(theta) - v2 * sin(theta)) / k
    y2 = first.y + (v2 * cos(theta) + u * sin(theta)) / k
    return ((x1, y1), (x2, y2))

if __name__ == "__main__":
    import doctest
    doctest.testmod()