Simple script to generate an apollonian gasket

apollonian_gasket.py

import math, cmath
import pygame

class Circle:
    def __init__(self, x, y, curvature):
        self.center = complex(x, y)
        self.curvature = curvature
        self.radius = abs(1 / curvature)

def descartes_theorem(k1, k2, k3):
    x = k1 + k2 + k3
    discriminant = abs(k1 * k2 + k2 * k3 + k3 * k1)
    y = 2 * math.sqrt(discriminant)
    return [x + y, x - y]

def complex_descartes_theorem(z1, k1, z2, k2, z3, k3, k4):
    zk1 = z1 * k1
    zk2 = z2 * k2
    zk3 = z3 * k3

    x = zk1 + zk2 + zk3
    y = 2 * cmath.sqrt(zk1 * zk2 + zk2 * zk3 + zk3 * zk1)

    return [(x + y) / k4, (x - y) / k4]

def tangential(c1, c2):
    epsilon = 0.1
    r1, r2 = c1.radius, c2.radius
    distance = abs(c1.center - c2.center) # euclidean distance
    case1 = abs(distance - (r1 + r2)) < epsilon # c1 and c2 are adjacent
    case2 = abs(distance - abs(r2 - r1)) < epsilon # c2 is inside c1
    return case1 or case2

def alreadyExists(circles, circle):
    epsilon = 0.1
    for other in circles:
        distance = abs(circle.center - other.center)
        if distance < epsilon:
            return True
    return False

def find_next_circles(c1, c2, c3):
    k1, k2, k3 = c1.curvature, c2.curvature, c3.curvature
    z1, z2, z3 = c1.center, c2.center, c3.center

    curvatures = descartes_theorem(k1, k2, k3)
    circles = []

    for k in curvatures:
        z4, z5 = complex_descartes_theorem(z1, k1, z2, k2, z3, k3, k)
        circles.append(Circle(z4.real, z4.imag, k))
        circles.append(Circle(z5.real, z5.imag, k))

    return circles

def generate_gasket(circles, c1, c2, c3, depth):
    if depth <= 0:
        return

    next_circles = find_next_circles(c1, c2, c3)

    for c in next_circles:
        too_small = c.radius < 3
        mutually_tangential = all(tangential(c, x) for x in [c1, c2, c3])
        if not mutually_tangential or too_small or alreadyExists(circles, c):
            continue

        circles.append(c)

        # Generate with new sets of 3 circles
        generate_gasket(circles, c1, c2, c, depth - 1)
        generate_gasket(circles, c2, c3, c, depth - 1)
        generate_gasket(circles, c1, c3, c, depth - 1)

# Example circles
c1 = Circle(300, 300, -1/200)  # Outer circle
c2 = Circle(200, 300,  1/100)  # Left inner circle
c3 = Circle(400, 300,  1/100)  # Right inner circle

circles = [c1, c2, c3]
generate_gasket(circles, c1, c2, c3, 4)

pygame.init()
window = pygame.display.set_mode((600, 600))

running = True
while running:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False

    window.fill((255, 255, 255))

    for circle in circles:
        x, y = circle.center.real, circle.center.imag
        pygame.draw.circle(window, (0, 0, 0), (x, y), circle.radius, 1)

    pygame.display.update()