# Apollonius Problem:
# Finde einen Kreis, der drei vorgegebene Kreise von innen berührt
# rekursive Erweiterung

from Tkinter import *
import random

MAX_ITERATIONS = 3000

class Apollonius:

    def __init__(self):
        self.root = Tk()
        self.root.title("HIB - Apollonius Problem")
        SIZE = 600
        self.c = Canvas(self.root,width=SIZE+6,height=SIZE+6,bg="#e0e0e0")
        self.c.pack()
        self.mid = SIZE/2+3
    
    # plot circle
    def circle(self,x,y,r,c=0):
        scale = self.mid
        if c != 0: color = "#ff0000"
        else: color = "#0000ff"
        self.c.create_oval(self.mid+scale*(x-r),self.mid+scale*(y-r),
                           self.mid+scale*(x+r),self.mid+scale*(y+r),outline=color )
        self.c.update()
            

    def start(self,depth=4,shrink=100.0):
        D = 4
        h = D/2.0*(3**0.5)
        x1,y1,r1 = -D/2,-h/3+h/12,D/2
        x2,y2,r2 = D/2,-h/3+h/12,D/2
        x3,y3,r3 = 0.0,h*2/3+h/12,D/2
        self.circle(x1,y1,r1,1)
        self.circle(x2,y2,r2,1)
        self.circle(x3,y3,r3,1)
        self.solution = []
        self.minimal_r = float(D)/shrink
        self.recurse((x1,y1,r1),(x2,y2,r2),(x3,y3,r3),depth)
        print len(self.solution),"circles found"

    def recurse(self,s1,s2,s3,depth):
        if depth==0: return
        x1,y1,r1 = s1
        x2,y2,r2 = s2
        x3,y3,r3 = s3

        ## new radius
        r = (r1*r2*r3)/(r1*r2+r2*r3+r1*r3+2*(r1*r2*r3*(r1+r2+r3))**0.5)
        
        ## new center
        a,a1 = 2*(x1-x2),2*(x1-x3)
        b,b1 = 2*(y1-y2),2*(y1-y3)
        c,c1 = 2*(r1-r2),2*(r1-r3)
        d,d1 = (x1**2+y1**2-r1**2)-(x2**2+y2**2-r2**2),(x1**2+y1**2-r1**2)-(x3**2+y3**2-r3**2)
        x = (b1*d-b*d1-b1*c*r+b*c1*r)/(a*b1-b*a1)
        y = (-a1*d+a*d1+a1*c*r-a*c1*r)/(a*b1-b*a1)

        s = (x,y,r)
        if r >= self.minimal_r: 
            self.circle(x,y,r)
            self.solution.append(s)

        self.recurse(s1,s2,s,depth-1)
        self.recurse(s1,s,s3,depth-1)
        self.recurse(s,s2,s3,depth-1)
        
    # save list of spheres as povray union object
    def save(self,name):
        if self.solution == []: return
        f = open(name,"w")
        f.write("// automatic include file from apollonius.py\n\n")
        f.write("#declare ApolloObject = union {\n")
        for x,y,r in self.solution:
            f.write("    sphere {<%f,%f,%f>,%f}\n"%(x,0.0,y,r))
        f.write("}\n")
        f.close()

a = Apollonius()
a.start(10,500)     # perhaps depth 12, shrink factor 1000
a.save("Apollo.inc")