Dado três círculos mutuamente tangentes, sempre podemos encontrar mais dois círculos tangentes a todos os três. Esses dois são chamados círculos apolíneos . Observe que um dos círculos apolíneos pode realmente estar ao redor dos três círculos iniciais.

A partir de três círculos tangentes, podemos criar um fractal chamado junta apolloniana , pelo seguinte processo:

1. Chame os 3 círculos iniciais os círculos principais
2. Encontre os dois círculos apolíneos dos círculos pais
3. Para cada círculo apolíneo:
   4. Para cada par dos três pares de círculos principais:
      5. Chame o círculo apolíneo e os dois círculos pai o novo conjunto de círculos pai e comece novamente a partir da etapa 2.

Por exemplo, começando com círculos de tamanho igual, obtemos:

^{Imagem encontrada na Wikipedia}

Precisamos de mais um pouco de notação. Se temos um círculo de raio r com o centro (x, y) , podemos definir sua curvatura como k = ± 1 / r . Normalmente, k será positivo, mas podemos usar k negativo para indicar o círculo que envolve todos os outros círculos na junta (ou seja, todas as tangentes tocam esse círculo por dentro). Em seguida, podemos especificar um círculo com um triplo de números: (k, x * k, y * k) .

Para o propósito desta questão, assumiremos o número inteiro positivo k racional x e y .

Outros exemplos para esses círculos podem ser encontrados no artigo da Wikipedia .

Há também algumas coisas interessantes sobre juntas integrais neste artigo (entre outras coisas divertidas com círculos).

O desafio

Você receberá 4 especificações de círculo, cada uma das quais será semelhante (14, 28/35, -112/105). Você pode usar qualquer operador de formato e divisão de lista que seja conveniente, de modo que você possa simplesmente evaldigitar a entrada, se desejar. Você pode supor que os 4 círculos são tangentes um ao outro e que o primeiro deles tem curvatura negativa. Isso significa que você já recebeu o círculo apolíneo circundante dos outros três. Para obter uma lista de exemplos válidos de entradas, consulte a parte inferior do desafio.

Escreva um programa ou função que, dada essa entrada, gire uma junta apolínica.

Você pode receber informações por meio do argumento da função, ARGV ou STDIN e renderizar o fractal na tela ou gravá-lo em um arquivo de imagem no formato de sua escolha.

Se a imagem resultante for rasterizada, ela deverá ter pelo menos 400 pixels de cada lado, com menos de 20% de preenchimento ao redor do círculo maior. Você pode parar de repetir quando alcançar círculos cujo raio é menor que 400º do maior círculo de entrada ou círculos menores que um pixel, o que ocorrer primeiro.

Você deve desenhar apenas contornos circulares, não discos completos, mas as cores do plano de fundo e das linhas são a sua escolha. Os contornos não devem ter mais de 200º do diâmetro dos círculos externos.

Isso é código de golfe, então a resposta mais curta (em bytes) vence.

Exemplo de entradas

Aqui estão todas as juntas integrais do artigo da Wikipedia convertidas para o formato de entrada prescrito:

[[-1, 0, 0], [2, 1, 0], [2, -1, 0], [3, 0, 2]]
[[-2, 0, 0], [3, 1/2, 0], [6, -2, 0], [7, -3/2, 2]]
[[-3, 0, 0], [4, 1/3, 0], [12, -3, 0], [13, -8/3, 2]]
[[-3, 0, 0], [5, 2/3, 0], [8, -4/3, -1], [8, -4/3, 1]]
[[-4, 0, 0], [5, 1/4, 0], [20, -4, 0], [21, -15/4, 2]]
[[-4, 0, 0], [8, 1, 0], [9, -3/4, -1], [9, -3/4, 1]]
[[-5, 0, 0], [6, 1/5, 0], [30, -5, 0], [31, -24/5, 2]]
[[-5, 0, 0], [7, 2/5, 0], [18, -12/5, -1], [18, -12/5, 1]]
[[-6, 0, 0], [7, 1/6, 0], [42, -6, 0], [43, -35/6, 2]]
[[-6, 0, 0], [10, 2/3, 0], [15, -3/2, 0], [19, -5/6, 2]]
[[-6, 0, 0], [11, 5/6, 0], [14, -16/15, -4/5], [15, -9/10, 6/5]]
[[-7, 0, 0], [8, 1/7, 0], [56, -7, 0], [57, -48/7, 2]]
[[-7, 0, 0], [9, 2/7, 0], [32, -24/7, -1], [32, -24/7, 1]]
[[-7, 0, 0], [12, 5/7, 0], [17, -48/35, -2/5], [20, -33/35, 8/5]]
[[-8, 0, 0], [9, 1/8, 0], [72, -8, 0], [73, -63/8, 2]]
[[-8, 0, 0], [12, 1/2, 0], [25, -15/8, -1], [25, -15/8, 1]]
[[-8, 0, 0], [13, 5/8, 0], [21, -63/40, -2/5], [24, -6/5, 8/5]]
[[-9, 0, 0], [10, 1/9, 0], [90, -9, 0], [91, -80/9, 2]]
[[-9, 0, 0], [11, 2/9, 0], [50, -40/9, -1], [50, -40/9, 1]]
[[-9, 0, 0], [14, 5/9, 0], [26, -77/45, -4/5], [27, -8/5, 6/5]]
[[-9, 0, 0], [18, 1, 0], [19, -8/9, -2/3], [22, -5/9, 4/3]]
[[-10, 0, 0], [11, 1/10, 0], [110, -10, 0], [111, -99/10, 2]]
[[-10, 0, 0], [14, 2/5, 0], [35, -5/2, 0], [39, -21/10, 2]]
[[-10, 0, 0], [18, 4/5, 0], [23, -6/5, -1/2], [27, -4/5, 3/2]]
[[-11, 0, 0], [12, 1/11, 0], [132, -11, 0], [133, -120/11, 2]]
[[-11, 0, 0], [13, 2/11, 0], [72, -60/11, -1], [72, -60/11, 1]]
[[-11, 0, 0], [16, 5/11, 0], [36, -117/55, -4/5], [37, -112/55, 6/5]]
[[-11, 0, 0], [21, 10/11, 0], [24, -56/55, -3/5], [28, -36/55, 7/5]]
[[-12, 0, 0], [13, 1/12, 0], [156, -12, 0], [157, -143/12, 2]]
[[-12, 0, 0], [16, 1/3, 0], [49, -35/12, -1], [49, -35/12, 1]]
[[-12, 0, 0], [17, 5/12, 0], [41, -143/60, -2/5], [44, -32/15, 8/5]]
[[-12, 0, 0], [21, 3/4, 0], [28, -4/3, 0], [37, -7/12, 2]]
[[-12, 0, 0], [21, 3/4, 0], [29, -5/4, -2/3], [32, -1, 4/3]]
[[-12, 0, 0], [25, 13/12, 0], [25, -119/156, -10/13], [28, -20/39, 16/13]]
[[-13, 0, 0], [14, 1/13, 0], [182, -13, 0], [183, -168/13, 2]]
[[-13, 0, 0], [15, 2/13, 0], [98, -84/13, -1], [98, -84/13, 1]]
[[-13, 0, 0], [18, 5/13, 0], [47, -168/65, -2/5], [50, -153/65, 8/5]]
[[-13, 0, 0], [23, 10/13, 0], [30, -84/65, -1/5], [38, -44/65, 9/5]]
[[-14, 0, 0], [15, 1/14, 0], [210, -14, 0], [211, -195/14, 2]]
[[-14, 0, 0], [18, 2/7, 0], [63, -7/2, 0], [67, -45/14, 2]]
[[-14, 0, 0], [19, 5/14, 0], [54, -96/35, -4/5], [55, -187/70, 6/5]]
[[-14, 0, 0], [22, 4/7, 0], [39, -12/7, -1/2], [43, -10/7, 3/2]]
[[-14, 0, 0], [27, 13/14, 0], [31, -171/182, -10/13], [34, -66/91, 16/13]]
[[-15, 0, 0], [16, 1/15, 0], [240, -15, 0], [241, -224/15, 2]]
[[-15, 0, 0], [17, 2/15, 0], [128, -112/15, -1], [128, -112/15, 1]]
[[-15, 0, 0], [24, 3/5, 0], [40, -5/3, 0], [49, -16/15, 2]]
[[-15, 0, 0], [24, 3/5, 0], [41, -8/5, -2/3], [44, -7/5, 4/3]]
[[-15, 0, 0], [28, 13/15, 0], [33, -72/65, -6/13], [40, -25/39, 20/13]]
[[-15, 0, 0], [32, 17/15, 0], [32, -161/255, -16/17], [33, -48/85, 18/17]]

GolfScript (vetor de 289 bytes / raster de 237 bytes)

Em 289 bytes e executando em um tempo razoável:

'/'/n*','/']['*0,`1/*~1.$[]*(~-400*:&;{1+1=*}/:D;{{1+2<~D@*\/}%}%'<svg><g fill="none" stroke="red">'puts.{[[~@:b[D&*\abs]{@&*[b]+}2*]{'.0/'*'"#{
}"'n/*~}%'<circle r="
" cx="
" cy="
" />'n/\]zip puts}:|/[{.([.;]+}3*]{(:?zip{)\~++2*\-}%:c.|0=D&*<{?);[c]+[{([.;]+.}3*;]+}*.}do'</g></svg>'

Isso recebe entrada no stdin e gera um arquivo SVG no stdout. Infelizmente, leva um pouco de tempo para uma demonstração online, mas uma versão aprimorada que aborta cedo pode lhe dar uma idéia.

Dada a entrada, [[-2, 0, 0], [3, 1/2, 0], [6, -2, 0], [7, -3/2, 2]]a saída (convertida em PNG com InkScape) é

Com 237 bytes e demorando muito (extrapolo que levaria pouco mais de uma semana para produzir uma saída semelhante à anterior, embora em preto e branco de um bit):

'/'/n*','/']['*0,`1/*~1.$[]*(~-400*:&;{1+1=*}/:D;{{1+2<~D@*\/}%}%.[{.([.;]+}3*]{(:?[zip{)\~++2*\-}%:c]@+\0c=D&*<{?);[c]+[{([.;]+.}3*;]+}*.}do;:C;'P1 ''801 '2*.~:B*,{:P;C{:?[0=2/.D&*-.*\D&*+.*]{2,{P{B/}2$*B%400-?0=*\)?=&*-.*}/+<},,1=},!}/

A saída é no formato NetPBM sem novas linhas, portanto, possivelmente não segue rigorosamente as especificações, embora o GIMP ainda a carregue. Se uma conformidade estrita for necessária, insira um napós o último !.

A rasterização é testando cada pixel em relação a cada círculo, de modo que o tempo gasto é praticamente linear no número de pixels vezes o número de círculos. Ao reduzir tudo por um fator de 10,

'/'/n*','/']['*0,`1/*~1.$[]*(~-40*:&;{1+1=*}/:D;{{1+2<~D@*\/}%}%.[{.([.;]+}3*]{(:?[zip{)\~++2*\-}%:c]@+\0c=D&*<{?);[c]+[{([.;]+.}3*;]+}*.}do;:C;'P1 ''81 '2*.~:B*,{:P;C{:?[0=2/.D&*-.*\D&*+.*]{2,{P{B/}2$*B%40-?0=*\)?=&*-.*}/+<},,1=},!}/

funcionará em 10 minutos e produzirá

(convertido para PNG com o GIMP). Dadas 36 horas, produziu o 401x401

JavaScript ( 418 410 bytes)

Implementado como uma função:

function A(s){P='<svg><g fill=none stroke=red transform=translate(400,400)>';Q=[];s=eval(s);S=-400*s[0][0];function d(c){P+='<circle r='+Math.abs(p=S/c[0])+' cx='+p*c[1]+' cy='+p*c[2]+' />'}for(c=4;c--;d(s[0]),s.push(s.shift()))Q.push(s.slice());for(;s=Q.shift();d(c)){c=[];for(i=4;i--;)c[i]=2*(s[0][i]+s[1][i]+s[2][i])-s[3][i];for(i=6;c[0]<S&&i;)Q.push([s[i--%3],s[i--%3],c,s[i%3]])}document.body.innerHTML=P}

Demonstração on-line (observação: não funciona em navegadores que não cumprem os requisitos das especificações SVG com relação ao tamanho implícito, por isso ofereço uma versão um pouco mais longa que contorna esse bug; os navegadores também podem renderizar o SVG com menos precisão do que, por exemplo, o Inkscape, embora o Inkscape seja um pouco mais rígido quanto à citação de atributos).

Observe que 8 bytes podem ser salvos usando document.write, mas isso atrapalha seriamente o jsFiddle.

Mathematica 289 caracteres

Resolvendo o sistema bilinear conforme http://arxiv.org/pdf/math/0101066v1.pdf Teorema 2.2 (altamente ineficiente).

Espaços não necessários, ainda jogando golfe:

w = {k, x, y};
d = IdentityMatrix;
j = Join;
p_~f~h_ := If[#[[-1, 1]] < 6! h,
    q = 2 d@4 - 1;
    m = #~j~{w};
    r = Complement[w /. NSolve[ And @@ j @@ 
                        MapThread[Equal, {[email protected], 4 d@3 {0, 1, 1}}, 2], w], a];
    If[r != {},
     a~AppendTo~# & @@ r;
     Function[x, x~j~{#}~f~h & /@ r]@#]] & /@ p~Subsets~{3}; 
Graphics[Circle @@@ ({{##2}, 1}/# & @@@ (f[a = #, -Tr@#]; a))] &

Uma animação de tamanho reduzido com entrada {{-13, 0, 0}, {23, 10/13, 0}, {30, -84/65, -1/5}, {38, -44/65, 9/5}}

Bordo (960 bytes)

Eu usei o Teorema de Descartes para gerar a Junta Apolloniana e depois usei o sistema de plotagem de Maple para plotá-la. Se eu tiver tempo, quero continuar jogando isso e alterá-lo para Python (o Maple definitivamente não é o melhor para fractais). Aqui está um link para um player Maple gratuito, se você quiser executar meu código.

X,Y,Z,S,N:=abs,evalf,member,sqrt,numelems;
f:=proc(J)
    L:=map((x)->[x[1],(x[2]+x[3]*I)/x[1]+50*(1+I)/X(J[1][2])],J);
    R:=Vector([L]);
    T,r:=X(L[1][3]),L[1][4];
    A(L[1][5],L[2][6],L[3][7],L[1][8],L[2][9],L[3][10],R,T,r);
    A(L[1][11],L[2][12],L[4][13],L[1][14],L[2][15],L[4][16],R,T,r);
    A(L[1][17],L[3][18],L[4][19],L[1][20],L[3][21],L[4][22],R,T,r);
    A(L[2][23],L[3][24],L[4][25],L[2][26],L[3][27],L[4][28],R,T,r);
    plots[display](seq(plottools[circle]([Re(R[i][29]),Im(R[i][30])],X(1/R[i][31])),i=1..N(R))):
end proc:
A:=proc(a,b,c,i,j,k,R,E,F)
    K:=i+k+j+2*S(i*k+i*j+k*j);
    if K>400*E then
    return;
    end if;
    C:=(a*i+c*k+b*j+2*S(a*c*i*k+b*c*j*k+a*b*i*j))/K;
    C2:=(a*i+c*k+b*j-2*S(a*c*i*k+b*c*j*k+a*b*i*j))/K;
    if Y(X(C-F))<1/E and not Z([K,C],R) then
    R(N(R)+1):=[K,C];
    A(a,b,C,i,j,K,R,E,F);
    A(a,c,C,i,k,K,R,E,F);
    A(b,c,C,j,k,K,R,E,F);
    end if:    
    if Y(X(C2-F))<1/E and not Z([K,C2],R) then
    R(N(R)+1):=[K,C2];
    A(a,b,C2,i,j,K,R,E,F);
    A(a,c,C2,i,k,K,R,E,F);
    A(b,c,C2,j,k,K,R,E,F);
    end if: 
end proc:

Algumas juntas de amostra

f([[-1, 0, 0], [2, 1, 0], [2, -1, 0], [3, 0, 2]]);

f([[-9, 0, 0], [14, 5/9, 0], [26, -77/45, -4/5], [27, -8/5, 6/5]]);