Dibuja una junta apolínea

28

Dados tres círculos mutuamente tangentes, siempre podemos encontrar dos círculos más que sean tangentes a los tres. Estos dos se llaman círculos apolíneos . Tenga en cuenta que uno de los círculos apolíneos podría estar alrededor de los tres círculos iniciales.

A partir de tres círculos tangentes, podemos crear un fractal llamado junta apolínea , mediante el siguiente proceso:

  1. Llame a los 3 círculos iniciales los círculos principales
  2. Encuentra los dos círculos apolíneos de los círculos principales
  3. Para cada círculo apolíneo:
    1. Para cada par de los tres pares de círculos principales:
      1. Llame al círculo apolíneo y a los dos círculos principales el nuevo conjunto de círculos principales y comience nuevamente desde el paso 2.

Por ejemplo, comenzando con círculos de igual tamaño, obtenemos:

ingrese la descripción de la imagen aquí

Imagen encontrada en Wikipedia

Hay un poco más de notación que necesitamos. Si tenemos un círculo de radio r con centro (x, y) , podemos definir su curvatura como k = ± 1 / r . Por lo general, k será positivo, pero podemos usar k negativo para denotar el círculo que encierra a todos los otros círculos en la junta (es decir, todas las tangentes tocan ese círculo desde adentro). Luego podemos especificar un círculo con un triplete de números: (k, x * k, y * k) .

Para el propósito de esta pregunta, asumiremos un entero positivo k y racional x e y .

Se pueden encontrar más ejemplos de tales círculos en el artículo de Wikipedia .

También hay algunas cosas interesantes sobre las juntas integrales en este artículo (entre otras cosas divertidas con círculos).

El reto

Se le darán 4 especificaciones de círculo, cada una de las cuales se verá (14, 28/35, -112/105). Puede usar cualquier formato de lista y operador de división que sea conveniente, de modo que pueda simplemente evalingresar la entrada si lo desea. Puede suponer que los 4 círculos son tangentes entre sí y que el primero de ellos tiene una curvatura negativa. Eso significa que ya se te ha dado el círculo apolíneo circundante de los otros tres. Para obtener una lista de entradas de ejemplo válidas, consulte la parte inferior del desafío.

Escriba un programa o función que, dada esta entrada, dibuje una junta apolínea.

Puede tomar la entrada a través del argumento de función, ARGV o STDIN y renderizar el fractal en la pantalla o escribirlo en un archivo de imagen en el formato que elija.

Si la imagen resultante está rasterizada, debe tener al menos 400 píxeles en cada lado, con menos del 20% de relleno alrededor del círculo más grande. Puede dejar de recurrir cuando alcanza círculos cuyo radio es menor que 400 del círculo de entrada más grande, o círculos que son más pequeños que un píxel, lo que ocurra primero.

Debe dibujar solo contornos circulares, no discos completos, pero los colores de fondo y líneas son su elección. Los contornos no deben ser más anchos que una 200a del diámetro de los círculos exteriores.

Este es el código de golf, por lo que gana la respuesta más corta (en bytes).

Entradas de ejemplo

Aquí están todas las juntas integrales del artículo de Wikipedia convertidas al 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]]
Martin Ender
fuente
Su ejemplo de ejemplo parece haber incluido solo los círculos apolíneos "internos" después de la primera operación.
Sparr
@Sparr No estoy seguro de lo que quieres decir. Después de la primera operación, ya existe uno de los dos círculos apolíneos (el círculo original original que no seleccionó para la iteración actual) y solo está buscando la otra solución.
Martin Ender
No importa, tienes razón, estaba leyendo mal.
Sparr

Respuestas:

12

GolfScript (vector de 289 bytes / ráster de 237 bytes)

A 289 bytes y ejecutando en un tiempo razonable:

'/'/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>'

Esto toma la entrada en stdin y genera un archivo SVG para stdout. Lamentablemente, la demo en línea demora un poco, pero una versión modificada que aborta antes de tiempo puede darle una idea.

Dada la entrada, [[-2, 0, 0], [3, 1/2, 0], [6, -2, 0], [7, -3/2, 2]]la salida (convertida a PNG con InkScape) es

junta 2/3/6/7


Con 237 bytes y demasiado tiempo (extrapolo que tomaría más de una semana producir un resultado similar al anterior, aunque en blanco y negro de un 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=},!}/

La salida es en formato NetPBM sin nuevas líneas, por lo que posiblemente no siga estrictamente la especificación, aunque el GIMP aún lo cargará. Si se requiere conformidad estricta, inserte un ndespués del último !.

La rasterización es mediante la prueba de cada píxel contra cada círculo, por lo que el tiempo necesario es bastante lineal en la cantidad de píxeles multiplicada por la cantidad de círculos. Al reducir todo por un factor 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=},!}/

correrá en 10 minutos y producirá

Imagen 81x81

(convertido a PNG con el GIMP). Dadas 36 horas, produjo el 401x401

Imagen 401x401

Peter Taylor
fuente
3
Nunca hubiera pensado que podría hacer una salida gráfica con Golfscript ...
Beta Decay
12

JavaScript ( 418 410 bytes)

Implementado como una función:

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}

Demostración en línea (nota: no funciona en los navegadores que no cumplen con los requisitos de las especificaciones SVG con respecto al tamaño implícito, por lo que ofrezco una versión un poco más larga que soluciona ese error; los navegadores también pueden procesar el SVG con menos precisión que, por ejemplo, Inkscape, aunque Inkscape es un poco más estricto al citar atributos).

Tenga en cuenta que se pueden guardar 8 bytes mediante el uso document.write, pero eso en serio borks jsFiddle.

Peter Taylor
fuente
1
Probablemente pueda ahorrar más definiendo la función con ES6 y almacenando, por ejemplo, S/c[0]en una variable y luego deshacerse de él Math.abscon un operador ternario, etc.
Ingo Bürk
@ IngoBürk, si fuera a tomar la ruta ES6, lo escribiría en CoffeeScript.
Peter Taylor
use el host c99.nl. Permite document.write.
xem
2
Es bueno ver una respuesta a esto :)
MickyT
Actualizado con la sugerencia de @ IngoBürk para una variable temporal. Eliminar en Math.absrealidad costaría un personaje.
Peter Taylor
6

Mathematica 289 caracteres

Al resolver el sistema bilineal según http://arxiv.org/pdf/math/0101066v1.pdf Teorema 2.2 (altamente ineficiente).

Espacios no necesarios, aún jugando al golf:

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))] &

Una animación de tamaño reducido con entrada {{-13, 0, 0}, {23, 10/13, 0}, {30, -84/65, -1/5}, {38, -44/65, 9/5}}

ingrese la descripción de la imagen aquí

Dr. belisario
fuente
¿Cómo tomas entrada?
Martin Ender
@ MartinBüttner como argumento de función, al agregar @{{-1, 0, 0}, {2, 1, 0}, {2, -1, 0}, {3, 0, 2}}a la última línea
Dr. belisarius
@ MartinBüttner Si va a probarlo, intente primero con en 50/hlugar de 400/h. Vas a obtener el resultado más rápido. también, puede monitorear el progreso ingresando Dynamic@Length@aantes de ejecutar la función
Dr. belisarius
Instructions for testing this answer (with a reduced number of circles) without Mathematica installed: 1) Descargue esto desde pastebin y guárdelo como * .CDF 2) Descargue e instale el entorno CDF gratuito de Wolfram Research en (no es un archivo pequeño). Disfrutar. ¡Dime si funciona! - Nota: los cálculos son lentos, espera a que aparezcan los gráficos.
Dr. belisario
¿A qué se refiere el comentario "altamente ineficiente"? ¿Es que (mirando la animación) aparentemente estás dibujando la mayoría de los círculos al menos dos veces? Creo que el enfoque complejo de Descartes es inherentemente tan eficiente como se pone.
Peter Taylor
4

Arce (960 bytes)

Usé el teorema de Descartes para generar la junta apolínea y luego utilicé el sistema de trazado de Maple para trazarlo. Si tengo tiempo, quiero seguir jugando golf y cambiarlo a Python (Maple definitivamente no es el mejor para fractales). Aquí hay un enlace a un reproductor Maple gratuito si desea ejecutar mi 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:

Algunas juntas de muestra

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

ingrese la descripción de la imagen aquí

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

ingrese la descripción de la imagen aquí

Cameron
fuente