Bei drei sich tangierenden Kreisen finden wir immer zwei weitere Kreise, die alle drei tangieren. Diese beiden werden als apollonische Kreise bezeichnet . Beachten Sie, dass sich einer der apollonischen Kreise möglicherweise tatsächlich um die drei Anfangskreise befindet.

Ausgehend von drei Tangentialkreisen können wir nach folgendem Verfahren ein Fraktal namens Apollon-Dichtung erstellen :

1. Nennen Sie die ersten 3 Kreise die Elternkreise
2. Finden Sie die beiden apollonischen Kreise der Elternkreise
3. Für jeden apollonischen Kreis:
   4. Für jedes Paar der drei Paare von Elternkreisen:
      5. Nennen Sie den apollonischen Kreis und die beiden übergeordneten Kreise die neue Gruppe der übergeordneten Kreise und beginnen Sie erneut mit Schritt 2.

ZB beginnend mit Kreisen gleicher Größe erhalten wir:

^{Bild auf Wikipedia gefunden}

Es gibt noch eine Notation, die wir brauchen. Wenn wir einen Kreis mit dem Radius r und dem Mittelpunkt (x, y) haben , können wir dessen Krümmung als k = ± 1 / r definieren . Normalerweise ist k positiv, aber wir können negatives k verwenden , um den Kreis zu bezeichnen, der alle anderen Kreise in der Dichtung einschließt (dh alle Tangenten berühren diesen Kreis von innen). Dann können wir einen Kreis mit einem Triplett von Zahlen spezifizieren: (k, x * k, y * k) .

Für den Zweck dieser Frage nehmen wir eine positive ganze Zahl k und rationale x und y an .

Weitere Beispiele für solche Kreise finden Sie im Wikipedia-Artikel .

Es gibt auch einige interessante Dinge über integrierte Dichtungen in diesem Artikel (unter anderem unterhaltsame Dinge mit Kreisen).

Die Herausforderung

Sie erhalten 4 Kreisspezifikationen, von denen jede wie folgt aussieht (14, 28/35, -112/105). Sie können ein beliebiges Listenformat und einen beliebigen Divisionsoperator verwenden, sodass Sie bei Bedarf einfach evaldie Eingabe vornehmen können. Sie können annehmen, dass die 4 Kreise tatsächlich tangential zueinander sind und dass der erste von ihnen eine negative Krümmung aufweist. Das heißt, Sie erhalten bereits den umgebenden apollonischen Kreis der anderen drei. Eine Liste der gültigen Beispieleingaben finden Sie am Ende der Challenge.

Schreiben Sie ein Programm oder eine Funktion, die bei dieser Eingabe eine apollonische Dichtung zeichnet.

Sie können Eingaben über das Funktionsargument ARGV oder STDIN vornehmen und das Fraktal entweder auf dem Bildschirm rendern oder in eine Bilddatei in einem Format Ihrer Wahl schreiben.

Wenn das resultierende Bild gerastert wird, muss es auf jeder Seite mindestens 400 Pixel groß sein, wobei der Abstand um den größten Kreis weniger als 20% beträgt. Sie können die Wiederholung beenden, wenn Sie Kreise erreichen, deren Radius kleiner als ein 400stel des größten Eingabekreises ist, oder Kreise, die kleiner als ein Pixel sind, je nachdem, was zuerst passiert.

Sie müssen nur Kreisumrisse zeichnen, keine vollständigen Scheiben, aber die Farben des Hintergrunds und der Linien sind Ihre Wahl. Die Konturen dürfen nicht breiter als ein 200stel des äußeren Kreisdurchmessers sein.

Dies ist Codegolf, daher gewinnt die kürzeste Antwort (in Bytes).

Beispieleingaben

Hier sind alle integrierten Dichtungen aus dem Wikipedia-Artikel in das vorgeschriebene Eingabeformat konvertiert:

[[-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 (289-Byte-Vektor / 237-Byte-Raster)

Bei 289 Bytes und Ausführung in angemessener Zeit:

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

Dies nimmt Eingaben über stdin entgegen und generiert eine SVG-Datei für stdout. Leider dauert eine Online-Demo etwas zu lange, aber eine optimierte Version, die vorzeitig abgebrochen wird, kann Ihnen eine Idee geben.

Bei Eingabe ist [[-2, 0, 0], [3, 1/2, 0], [6, -2, 0], [7, -3/2, 2]]die Ausgabe (konvertiert nach PNG mit InkScape)

Bei 237 Bytes und viel zu lange (ich rechne damit, dass es etwas mehr als eine Woche dauern würde, um eine ähnliche Ausgabe wie oben zu erzeugen, obwohl in Ein-Bit-Schwarzweiß):

'/'/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=},!}/

Die Ausgabe erfolgt im NetPBM-Format ohne Zeilenumbrüche. Befolgen Sie daher möglicherweise nicht die Spezifikation, obwohl GIMP sie weiterhin lädt. Wenn strikte Konformität erforderlich ist, fügen Sie nnach dem letzten ein !.

Die Rasterung erfolgt durch Testen jedes Pixels gegen jeden Kreis. Die benötigte Zeit ist also ziemlich linear in der Anzahl der Pixel multipliziert mit der Anzahl der Kreise. Indem Sie alles um den Faktor 10 verkleinern,

'/'/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=},!}/

läuft in 10 Minuten und produziert

(Mit dem GIMP in PNG konvertiert). In 36 Stunden wurde der 401x401 produziert

JavaScript ( 418.410 Byte)

Implementiert als Funktion:

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}

Online-Demo (Hinweis: Funktioniert nicht in Browsern, die die Anforderungen der SVG-Spezifikation in Bezug auf implizite Größen nicht erfüllen. Daher biete ich eine etwas längere Version an, die diesen Fehler umgeht. Browser rendern die SVG möglicherweise auch weniger genau als z. B. Inkscape.) obwohl Inkscape bei der Angabe von Attributen etwas strenger ist).

Beachten Sie, dass mit 8 Bytes gespart werden könnte document.write, aber das macht jsFiddle kaputt.

Mathematica 289 Zeichen

Durch Lösen des bilinearen Systems gemäß http://arxiv.org/pdf/math/0101066v1.pdf Theorem 2.2 (sehr ineffizient).

Nicht benötigte Plätze, trotzdem Golf spielen:

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

Eine verkleinerte Animation mit Eingabe {{-13, 0, 0}, {23, 10/13, 0}, {30, -84/65, -1/5}, {38, -44/65, 9/5}}

Ahorn (960 Bytes)

Ich habe das Descartes-Theorem verwendet, um die Apollonische Dichtung zu generieren, und dann das Diagrammsystem von Maple verwendet, um sie zu zeichnen. Wenn ich Zeit habe, möchte ich weiter Golf spielen und es in Python ändern (Maple ist definitiv nicht das Beste für Fraktale). Hier ist ein Link zu einem kostenlosen Maple-Player, wenn Sie meinen Code ausführen möchten.

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:

Einige Musterdichtungen

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