Finding the points of intersecion of two circles.

intersect.py

#!/usr/bin/env python

# Finding the points of intersecion of two circles.

import math

class Point:
    def __init__(self, x = 0, y = 0):
        self.x = x
        self.y = y

    def distance(self, other):
        x = self.x - other.x
        y = self.y - other.y
        return math.sqrt(x**2 + y**2)

    def __str__(self):
        return '({}, {})'.format(self.x, self.y)

    def __repr__(self):
        return self.__str__()

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

    def __str__(self):
        return '<{}, {}>'.format(self.center, self.radius)

    def __repr__(self):
        return self.__str__()

    def intersection_points(self, other):
        # P0 = center of self-triangle
        # P1 = center of other-triangle
        # Circles intersection points: P3, P4
        # P2 = intersection of lines P0-P1 and P3-P3
        # Right triangles P0-P2-P3, P1-P2-P3 and P0-P2-P4, P1-P2-P4
        # a = distance between P0 and P1
        # height = distance between P2 and P3

        dist = self.center.distance(other.center)

        if dist > self.radius + other.radius:
            return ()

        if dist < abs(self.radius - other.radius):
            return ()

        a = 0.5 * (self.radius**2 - other.radius**2 + dist**2) / dist

        height = math.sqrt(self.radius**2 - a**2)

        p0 = self.center
        p1 = other.center
        p2 = Point()
        p2.x = p0.x + a * (p1.x - p0.x) / dist
        p2.y = p0.y + a * (p1.y - p0.y) / dist

        p3 = Point()
        p3.x = p2.x + height * (p1.y - p0.y) / dist
        p3.y = p2.y - height * (p1.x - p0.x) / dist

        p4 = Point()
        p4.x = p2.x - height * (p1.y - p0.y) / dist
        p4.y = p2.y + height * (p1.x - p0.x) / dist

        return (p3, p4)

    def on_border(self, point, epsilon = 0.0001):
        x = self.center.x - point.x
        y = self.center.y - point.y
        radius = math.sqrt(x**2 + y**2)
        return abs(self.radius - radius) < epsilon

def main():
    c1 = Circle(10, 15, 10)
    c2 = Circle(20, 20, 10)

    print c1, c2

    points = c1.intersection_points(c2)
    for point in points:
        print point, c1.on_border(point) and c2.on_border(point)

if __name__ == '__main__':
    main()