Нарисуйте аполлоновскую прокладку

28

Учитывая три взаимно касательных круга, мы всегда можем найти еще два круга, которые касаются всех трех из них. Эти два называются кругами Аполлона . Обратите внимание, что один из кругов Аполлона может быть вокруг трех начальных кругов.

Начиная с трех касательных окружностей, мы можем создать фрактал, называемый аполлоновой прокладкой , следующим образом:

  1. Назовите первые 3 круга родительскими кругами
  2. Найти родительские круги - два круга Аполлона
  3. Для каждого круга Аполлона:
    1. Для каждой пары из трех пар родительских кругов:
      1. Назовите круг Аполлона и два родительских круга новым набором родительских кругов и начните заново с шага 2.

Например, начиная с кругов одинакового размера, мы получаем:

введите описание изображения здесь

Изображение найдено в Википедии

Нам нужна еще одна нотация. Если у нас есть круг радиуса r с центром (x, y) , мы можем определить его кривизну как k = ± 1 / r . Обычно k будет положительным, но мы можем использовать отрицательный k для обозначения круга, который охватывает все другие круги в прокладке (т.е. все касательные касаются этого круга изнутри). Тогда мы можем указать круг с тройкой чисел: (k, x * k, y * k) .

Для целей этого вопроса мы будем принимать положительное целое число k и рациональные x и y .

Другие примеры таких кругов можно найти в статье в Википедии .

В этой статье также есть кое-что интересное о встроенных прокладках (среди прочих забавных вещей с кружками).

Соревнование

Вам будут предоставлены 4 круга спецификаций, каждая из которых будет выглядеть так (14, 28/35, -112/105). Вы можете использовать любой удобный формат списка и оператор деления, так что вы можете просто evalввести, если хотите. Вы можете предположить, что 4 круга действительно касаются друг друга, и что первый из них имеет отрицательную кривизну. Это означает, что вам уже дан окружающий Аполлонийский круг остальных трех. Список допустимых примеров ввода см. В нижней части задачи.

Напишите программу или функцию, которая с учетом этого ввода рисует аполлоновскую прокладку.

Вы можете получить ввод через аргумент функции, ARGV или STDIN и либо отобразить фрактал на экране, либо записать его в файл изображения в выбранном вами формате.

Если получающееся изображение растеризовано, оно должно быть не менее 400 пикселей с каждой стороны, с отступом менее 20% вокруг наибольшего круга. Вы можете прекратить повторение, когда достигнете кругов, радиус которых меньше 400-й от наибольшего входного круга, или кругов, которые меньше пикселя, в зависимости от того, что произойдет раньше.

Вы должны рисовать только круговые контуры, а не полные диски, но цвета фона и линий - ваш выбор. Контуры не должны быть шире, чем 200-й диаметр наружных кругов.

Это код гольф, поэтому самый короткий ответ (в байтах) выигрывает.

Пример входов

Вот все интегральные прокладки из статьи Википедии, преобразованные в предписанный формат ввода:

[[-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]]
Мартин Эндер
источник
Кажется, что ваш пример иллюстрирует только «внутренние» круги аполлонов после первой операции.
Спарр
@Sparr Я не уверен, что ты имеешь в виду. После первой операции один из двух кругов Аполлона уже существует (исходный родительский круг, который вы не выбрали для текущей итерации), и вы ищете только другое решение.
Мартин Эндер
Неважно, ты прав, я неправильно читал.
Спарр

Ответы:

12

GolfScript (вектор 289 байтов / растр 237 байтов)

На 289 байтов и выполняется в разумные сроки:

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

Он принимает входные данные в stdin и генерирует SVG-файл для stdout. К сожалению, для онлайн-демонстрации это занимает слишком много времени, но подправленная версия, которая прерывается раньше, может дать вам представление.

С учетом ввода [[-2, 0, 0], [3, 1/2, 0], [6, -2, 0], [7, -3/2, 2]]в выход ( в пересчете на PNG с InkScape) является

прокладка 2/3/6/7


На 237 байтах и ​​занимает слишком много времени (я экстраполирую, что потребуется чуть больше недели, чтобы произвести аналогичный результат, как показано выше, хотя в однобитном черно-белом):

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

Вывод - это формат NetPBM без перевода строки, поэтому, возможно, он не совсем соответствует спецификации, хотя GIMP все равно его загрузит. Если требуется строгое соответствие, вставьте nпосле последнего !.

Растеризация происходит путем проверки каждого пикселя на каждом круге, поэтому время, затрачиваемое на это, в значительной степени линейно по числу пикселей, умноженному на количество кругов. Уменьшая все в 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=},!}/

побежит через 10 минут и выдаст

81x81 изображение

(преобразовано в PNG с GIMP). Учитывая 36 часов, он произвел 401x401

Изображение 401x401

Питер Тейлор
источник
3
Я никогда бы не подумал, что вы можете сделать графический вывод с помощью Golfscript ...
Beta Decay
12

JavaScript ( 418 410 байт)

Реализовано как функция:

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}

Демонстрация в Интернете (примечание: не работает в браузерах, которые не удовлетворяют требованиям спецификации SVG в отношении неявного определения размера, поэтому я предлагаю немного более длинную версию, которая работает с этой ошибкой; браузеры также могут отображать SVG менее точно, чем, например, Inkscape, хотя Inkscape немного строже в цитировании атрибутов).

Обратите внимание, что 8 байтов могут быть сохранены с помощью document.write, но это серьезно мешает jsFiddle.

Питер Тейлор
источник
1
Вероятно, вы можете сэкономить больше, определив функцию с помощью ES6 и сохранив ее, например, S/c[0]в переменной, а затем избавившись от Math.abs
нее
@ IngoBürk, если бы я собирался пойти по пути ES6, я бы вместо этого написал его на CoffeeScript.
Питер Тейлор
используйте хост c99.nl. Это позволяет document.write.
xem
2
Рад
Обновлено с предложением @ IngoBürk для временной переменной. Исключение Math.absбудет стоить персонажа.
Питер Тейлор
6

Mathematica 289 символов

Решая билинейную систему согласно http://arxiv.org/pdf/math/0101066v1.pdf Теорема 2.2 (крайне неэффективная).

Пространства не нужны, все еще игра в гольф:

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, {Thread@m.q.m, 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))] &

Анимация уменьшенного размера с вводом {{-13, 0, 0}, {23, 10/13, 0}, {30, -84/65, -1/5}, {38, -44/65, 9/5}}

введите описание изображения здесь

Доктор белисарий
источник
Как вы принимаете вход?
Мартин Эндер
@ MartinBüttner в качестве аргумента функции, добавив @{{-1, 0, 0}, {2, 1, 0}, {2, -1, 0}, {3, 0, 2}}к последней строке
Dr. belisarius
@ MartinBüttner Если вы собираетесь проверить это, попробуйте сначала 50/hвместо 400/h. Вы получите результат быстрее. Кроме того, вы можете отслеживать прогресс, введя Dynamic@Length@aперед выполнением функции
д-р belisarius
Instructions for testing this answer (with a reduced number of circles) without Mathematica installed: 1) Загрузите это из pastebin и сохраните как * .CDF. 2) Загрузите и установите бесплатную среду CDF от Wolfram Research по адресу (не маленький файл). Наслаждаться. Скажите, работает ли он? - Примечание. Вызовы медленные, дождитесь появления графики.
Доктор Белизарий
К чему относится «крайне неэффективный» комментарий? Это (глядя на анимацию) вы, по-видимому, рисуете большинство кругов по крайней мере дважды? Я думаю, что комплексный подход Декарта по своей сути настолько эффективен, насколько это возможно.
Питер Тейлор
4

Клен (960 байт)

Я использовал теорему Декарта для создания аполлоновой набивки, а затем использовал систему построения Maple для ее построения. Если у меня есть время, я хочу продолжить игру в гольф и изменить ее на Python (Maple определенно не лучший для фракталов). Вот ссылка на бесплатный проигрыватель Maple, если вы хотите запустить мой код.

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:

Некоторые образцы прокладок

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

введите описание изображения здесь

Cameron
источник