- PVSM.RU - http://www.pvsm.ru -

Приключения в математическом лесу фрактальных деревьев

Приключения в математическом лесу фрактальных деревьев

Перевод поста Bernat Espigulé Pons, «Adventures into the Mathematical Forest of Fractal Trees» [1].
Скачать перевод в виде документа
Mathematica, который содержит весь код использованный в статье, можно здесь [2].

Без сомнения, золотое сечение и в наше время представляется одним из самых таинственных, волшебных и поразительных чисел, которые известны людям: Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_1.png. (в языке Wolfram Language [3] и системе Mathematica ему соответствует символ GoldenRatio [4]). Как вы увидите из этого поста, это число действительно имеет множество интересных свойств, которые можно исследовать, причём некоторые из них рассматривались ещё в работах учёных Древней Греции, таких как Пифагор [5] и Евклид [6], другие в работах итальянского математика Леонардо Пизанского [7], более известного под прозвищем Фибоначчи, или Иоганном Кеплером [8] — астрономом эпохи Возрождения. Хотя это может прозвучать странно, в этом посте я расскажу вам о новых геометрических объектах, связанных с золотым сечением, которые осветили мне путь, когда я пытался отобразить неизвестную ранее область Математического Леса.

Обнаруженные ниже свойства были найдены не как-то случайно, я упорно работал, чтобы добыть эти новые знания еще со времён, когда я учился в старшей школе. После того, как в 2007 году я увидел рисунки “золотых” (в плане использования при их построении золотого сечения) фрактальных деревьев Ганса Вальзера [9] (Hans Walser), я понял, что в этой области ещё есть место новым исследованиям и открытиям. После некоторых поисков я нашел требующиеся мне для этого инструменты: ими стали система Mathematica и интерактивная модель Тео Грея [10] под названием “Сгибатель обнажённого обдуваемого ветром дерева Пифагора [11]”, с сайта Wolfram Demonstrations Project [12]. Собрав некоторые знания и начальные умения программирования на языке Wolfram Language, я получил свои первые результаты и озарения. Скажем, ниже вы можете видеть пример одного из первых самокасающихся “золотых” фрактальных деревьев, которые я открыл для себя, создав свою собственную версию “Сгибателя” Тео Грея, которую я изначально разрабатывал для изучения тернарных деревьев (т. е. деревьев, у которых из каждого узла выходит три ветви).

In[1]:=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_2.gif

Out[3]=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_3.gif

Это самоподобное дерево, т. е. дерево, которое получается, по сути, последовательным применением некоторого правила ветвления. Я называю “золотыми” те деревья, длина ветвей которых кратна золотому сечению GoldenRatio = φ. Для этого конкретного дерева, масштабный коэффициент для центральной ветви равен Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_4.png, а для боковых ветвей Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_5.png. Угол между центральной ветвью и каждой из боковых ветвей равен 72º. Так как это дерево не имеет пересекающихся между собой ветвей или же не соединённых между собой элементов, то его можно называть “самокасающимся” деревом. Давайте взглянем на некоторые из его свойств поближе:

In[4]:=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_6.png

Out[7]=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_7.gif

Вслед за обозначениями, предложенными Бенуа Мандельбротом (Benoit Mandelbrot) и Майклом Фрэймом (Michael Frame) [13] для бинарных деревьев, я добавил третью букву U, вместе с которой мы сможем описать все ветви нашего тройного дерева. Буквой L обозначаются ветви, выходящие слева, буквой R — ветви, выходящие справа, а буква U соответствует центральной ветви. Таким образом, строка из этих букв однозначно задаёт каждую ветвь нашего фрактала. В том случае, если такого рода “адрес” имеет бесконечную длину, то мы можем указать конкретную “вершину” нашего фрактального дерева, которую можно рассматривать, по сути, как недостижимую предельную точку, к которой постепенно приближается цепочка ветвей фрактального дерева. Например, бесконечный “адрес” вида Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_8.png задаёт “кончик” в самом верху нашего дерева:

In[8]:=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_9.png

Out[8]=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_10.png

Таким образом, высота нашего дерева равна:

In[9]:=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_11.png

Out[9]=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_12.png

А его ширина равна расстоянию между точками Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_13.png и Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_14.png:

In[10]:=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_15.png

Out[10]=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_16.png

Также весьма интересно, что длина последовательности ветвей дерева может быть выражена с помощью чисел Фибоначчи (в Mathematica для поиска n-го по счёту числа Фибоначчи служит функция Fibonacci [14][n]). Вы можете найти некоторые выражения, используемые в коде ниже, в нижнем левом углу предыдущего рисунка:

In[11]:=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_17.png

Out[11]=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_18.png

In[12]:=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_19.png

Out[12]=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_20.png

Наконец, для того, чтобы доказать, что это дерево является самокасающимся, нам необходимо показать, что две различные ветви (их вершины) касаются друг друга в одной точке, которая соответствует одновременно двум точкам (вершинам) дерева: Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_21.png. При этом тоже самое наблюдается и для зеркально симметричной точки (см. диаграмму ниже). Если это так, то самоподобие дерева будет означать, что в нём отсутствуют вершины, которые не касаются других вершин. Это означает, что можно взять любую вершину, “отрезать” подмножество дерева, содержащее её, которое повторяет по внешнему виду всё дерево, затем изменить соответствующим образом его масштаб, повернуть на нужный угол и мы получим после этого точку касания одного из двух рассмотренных основных типов:

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_22.gif

Координаты вершины Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_23.png можно определить следующим образом:

In[13]:=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_24.png

Out[13]=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_25.png

При этом координаты вершины Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_26.png будут равны:

In[14]:=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_27.png

Out[14]=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_28.png

Таким образом, ввиду того, что эти координаты равны, мы можем утверждать, что наше дерево действительно является самокасающимся.

Еще одна потрясающая вещь, связанная с этим “золотым” деревом, заключается в том, что оно создаёт красивый узор с осевой симметрией 5-го порядка, который может быть получен поворотом основного дерева вокруг его основания:

In[15]:=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_29.gif

Out[17]=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_30.gif

Или же можно создать аналогичный узор, вращая дерево вокруг его основной вершины:

In[18]:=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_31.gif

Out[20]=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_32.gif

В тот же день я открыл для себя второе тройное “золотое” дерево. Это дерево, в котором центральная ветвь идёт по направлению вниз, её мы обозначим буквой D, а правая R и левая L ветви образуют угол в 36º вместе с центральной ветвью.

In[21]:=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_33.gif

Out[23]=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_34.gif

В этом случае, мы можем создать узор с осевой симметрией 10-го порядка, вращая созданное дерево вокруг его основания:

In[24]:=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_35.gif

Out[26]=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_36.gif

Теперь позвольте представить вам самое первое “золотое” дерево, которое я открыл для себя ещё в 2011 году:

In[27]:=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_37.gif

Out[29]=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_38.gif

Это бинарное дерево асимметрично. В нём длина ветвей, которые отходят налево, на каждом шаге умножается на коэффициент Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_39.png, при этом они образуют с продолжением центральной ветви угол в 36º. Ветви, отходящие направо устроены таким образом, чтобы формировать правильные пятиугольники. Первые четыре итерации приведены ниже:

In[30]:=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_40.gif

Out[32]=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_41.gif

Ещё можно рассмотреть асимметричное дерево, приведённое ниже, которое имеет зеркальную симметрию относительно прямой, проходящей через центральную ветвь:

In[33]:=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_42.gif

Out[37]=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_43.gif

На основе этого дерева можно создать фрактал, имеющий осевую симметрию 5-го порядка:

In[38]:=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_44.gif

Out[42]=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_45.gif

Настоящая магия произошла после того, как я “сложил” это дерево так, как это показано в этой gif-анимации [15], созданной с помощью Mathematica.

Приключения в математическом лесу фрактальных деревьев

Когда ветви были полностью сложены, вершины дерева образовали “золотую” снежинку Коха [16]. Золотое сечение “выстроило” ветви таким образом, что они сформировали “золотые треугольники [17]” и “золотые гномоны [18]”, которые можно увидеть при любой степени увеличения изображения.

In[43]:=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_46.png

Out[43]=

Приключения в математическом лесу фрактальных деревьев
(посмотреть интерактивную демонстрацию CDF [19])

После того, как были рассмотрены деревья, у которых концы материнских ветвей движутся четко вдоль отрезка прямой, появилось целое семейство самокасающихся бинарных деревьев (об этом вы можете подробнее прочесть в посте “Автоматическое рисование в Mathematica: Драконовы деревья [20]”).

Затем я начал рассматривать деревья, имеющие более двух ветвей, отходящих от основной ветви. Сборник “Фрактальных мозаик [21]” Роберта Фатхауэра (Robert Fathauer) вдохновил меня на поиск способа отображения всех возможных деревьев, порождающих снежинки Коха, подобно тому дереву, что было рассмотрено ранее, с помощью одной диаграммы. Эта диаграмма была представлена на прошлогодней конференции Bridges conference [22] (статью вы можете найти по ссылке [23], сама диаграмма — рисунок с подписью figure 4). Эти исследования и наблюдения позволили мне продвинуться вперед и обобщить симметричные самокасающиеся бинарные фрактальные деревья, изученные Бенуа Мандельбротом [24] (Benoit Mandelbrot) и Майклом Фрэймом [25] (Michael Frame) (см. [1] [13]), Тарой Тэйлор [26] (Tara Taylor) (см. [2] [27][3] [28]), Душаном Пагоном (Dušan Pagon) (см. [4] [29]) и Стивеном Вольфрамом [30] (Stephen Wolfram) (см. [5] [31]). После долгой работы над выяснением того, как связаны между собой “адреса” путей до вершин дерева, в которых оно касается само себя, с углом θ, а также с количеством ветвей дерева, с помощью системы Mathematica мне удалось получить все девять типов уравнений, которые определяют коэффициент самокасания Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_48.png для n-арных симметричных фрактальных деревьев. Я не буду вдаваться в подробности здесь — вы можете сами изучить самокасающиеся деревья в манипуляторе ниже. Если же вас заинтересовал данный вопрос, вы можете прочитать пост “Девять уравнений, чтобы править ими всеми. Всё семейство фракталов Серпинского [32]” (Nine equations to rule them all. The Sierpinski’s whole family), который был написан для Wolfram Community. В этом посте получены результаты, которые были затем опубликованы в журнале Symmetry [33] (Volume 24, Numbers 1–4, pages 320–338, 2013).

In[44]:=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_49.png

Out[44]=

Приключения в математическом лесу фрактальных деревьев
(посмотреть интерактивную демонстрацию CDF [34])

Мои исследования не закончились на этом. Прошлым летом, во время первой недели моего пребывания на летней школе Wolfram Science Summer School [35], я имел счастье открыть пять трёхмерных самокасающихся бесконечных “золотых” деревьев с ветвями, направленными вниз [36] (ниже вы можете видеть одно из таких деревьев, порождающих трёхмерную снежинку кода, которое может быть получено, если взять угол наклона боковых ветвей относительно продолжения центральной ветви равным Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_51.png). Этот момент стал для меня самым выдающимся.

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_52.gif

Когда я приехал на летнюю школу Wolfram Science Summer School, у меня уже было некоторое смутное видение того, о чём я буду делать проект. Я хотел обобщить уравнения [32], которые я нашёл для двумерных фрактальных деревьев для трёхмерного случая. Я пробовал проделать это и ранее, но у меня были определённые трудности в применении всевозможных вращений, и я мог создать лишь небольшой набор высокосимметричных деревьев, подобных тетраэдрическому дереву [37], которое я напечатал на 3D-принтере непосредственно перед тем, как присоединиться к летней школе. Демонстрация “Ветвление деревьев в 4D [38]Тода Роуланда [39] (Todd Rowland), академического директора летней школы, помогла мне понять основные идеи реализации моего проекта, а мой руководитель, Виталий Кауров [40] (Vitaliy Kaurov), был очень вдохновлен моей целью [41].

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_53.gif

После моего первого разговора со Стивеном Вольфрамом (Stephen Wolfram), все были согласны, что я должен остаться в том же самом Математическом лесу, из которого я пришел и должен постараться перейти к более высокой размерности рассматриваемых деревьев. На протяжении моей первой недели я искал литературу о трёхмерных фрактальных деревьях, и я нашел статью “Симметричные трёхмерные фрактальные деревья [42]” (Symmetric Fractal Trees in Three Dimensions), написанную Фронгилло (Frongillo) и др., а также пример [43] Пола Ниландера (Paul Nylander) генерирования трёхмерных тернарных фрактальных деревьев. После этого я быстро попытался воспроизвести и расширить результаты, представленные в статье, основываясь на моей интуиции и знаниях, полученных во время изучения двумерных деревьев под руководством Сюзанны Кромкер (Susanne Krömker) в Гейдельбергском университете. Окончательные результаты были поразительны и я по-прежнему поражаюсь насколько быстро все эти уравнения [44] были получены всего за три недели. Конечно, та атмосфера, которая стояла в летней школе стала лучшим помощником для выполнения такого проекта.

“Простые правила, применяющиеся бесконечное число раз, являются неиссякаемым источником чудес” — Benoit B.Mandelbrot [45]

In[45]:=

Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_54.gif

Out[45]=

Приключения в математическом лесу фрактальных деревьев
(посмотреть интерактивную демонстрацию CDF [46])

(Манипулятор, созданный с помощью функции Manipulate [47], который вы видите выше, позволит вам изучить “лес” симметричных бинарных фрактальных деревьев. Синяя “карта” на заднем плане представляет собой множество Мандельброта для симметричных бинарных деревьев. В данном случае, множества Жулиа, связанные с этой “картой”, являются множествами вершин соответствующих деревьев. Эта “карта”, открытая Майклом Барнсли [48] (Michael Barnsley), имеет некоторые общие свойства с точечными картами [49], открытыми Стивеном Вольфрамом (Stephen Wolfram). Мнимая ось направлена на этом рисунке вверх для того, чтобы деревья “росли” вверх. При этом белая область в центре соответствует тем положениям материнских ветвей, при которых полученные на их основе деревья являются несвязными.)

Автор: OsipovRoman

Источник [50]


Сайт-источник PVSM.RU: http://www.pvsm.ru

Путь до страницы источника: http://www.pvsm.ru/programmirovanie/70601

Ссылки в тексте:

[1] «Adventures into the Mathematical Forest of Fractal Trees»: http://blog.wolfram.com/2014/05/22/adventures-into-the-mathematical-forest-of-fractal-trees/

[2] здесь: http://goo.gl/PCrihg

[3] Wolfram Language: http://www.wolfram.com/language

[4] GoldenRatio: http://reference.wolfram.com/language/ref/GoldenRatio.html

[5] Пифагор: https://ru.wikipedia.org/wiki/%D0%9F%D0%B8%D1%84%D0%B0%D0%B3%D0%BE%D1%80

[6] Евклид: https://ru.wikipedia.org/wiki/%D0%95%D0%B2%D0%BA%D0%BB%D0%B8%D0%B4

[7] Леонардо Пизанского: https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8

[8] Иоганном Кеплером: https://ru.wikipedia.org/wiki/%D0%9A%D0%B5%D0%BF%D0%BB%D0%B5%D1%80,_%D0%98%D0%BE%D0%B3%D0%B0%D0%BD%D0%BD

[9] Ганса Вальзера: http://books.google.es/books?id=oVhWBoSFbrIC&lpg=PP1&dq=inauthor%3A%22Hans%20Walser%22&pg=PA26#v=onepage&q&f=false

[10] Тео Грея: http://blog.wolfram.com/author/theodore-gray/

[11] Сгибатель обнажённого обдуваемого ветром дерева Пифагора: http://demonstrations.wolfram.com/TreeBender/

[12] Wolfram Demonstrations Project: http://demonstrations.wolfram.com/

[13] Бенуа Мандельбротом (Benoit Mandelbrot) и Майклом Фрэймом (Michael Frame): http://link.springer.com/article/10.1007%2FBF03024842

[14] Fibonacci: http://reference.wolfram.com/language/ref/Fibonacci.html

[15] gif-анимации: http://blog.wolfram.com/data/uploads/2014/05/foldingGoldenTree.gif

[16] снежинку Коха: http://www.wolframalpha.com/input/?i=koch+snowflake

[17] золотые треугольники: http://mathworld.wolfram.com/GoldenTriangle.html

[18] золотые гномоны: http://mathworld.wolfram.com/GoldenGnomon.html

[19] посмотреть интерактивную демонстрацию CDF: http://data.wolframmathematica.ru/habrahabr/Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev/Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_47.cdf

[20] Автоматическое рисование в Mathematica: Драконовы деревья: http://community.wolfram.com/groups/-/m/t/108323

[21] Фрактальных мозаик: http://www.mathartfun.com/shopsite_sc/store/html/Compendium/encyclopedia.html

[22] Bridges conference: http://bridgesmathart.org/

[23] по ссылке: http://archive.bridgesmathart.org/2013/bridges2013-295.pdf

[24] Бенуа Мандельбротом: http://youtu.be/wQTnVEXAtBY

[25] Майклом Фрэймом: http://youtu.be/bz8NJ7ZVXwQ

[26] Тарой Тэйлор: http://people.stfx.ca/ttaylor/research.html

[27] [2] : http://people.stfx.ca/ttaylor/research/thesis/thesis.pdf

[28] [3]: http://archive.bridgesmathart.org/2007/bridges2007-181.html

[29] [4]: http://ptps.oxfordjournals.org/content/150/176

[30] Стивеном Вольфрамом: http://youtu.be/60P7717-XOQ

[31] [5]: http://www.wolframscience.com/nksonline/page-406

[32] Девять уравнений, чтобы править ими всеми. Всё семейство фракталов Серпинского: http://community.wolfram.com/groups/-/m/t/142099

[33] Symmetry: http://journal-scs.symmetry.hu/content-pages/volume-24-numbers-1-4-pages-1-512-2013/

[34] посмотреть интерактивную демонстрацию CDF: http://data.wolframmathematica.ru/habrahabr/Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev/Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_50.cdf

[35] Wolfram Science Summer School: http://www.wolframscience.com/summerschool/

[36] пять трёхмерных самокасающихся бесконечных “золотых” деревьев с ветвями, направленными вниз: http://jointmathematicsmeetings.org/amsmtgs/2160_abstracts/1096-37-749.pdf

[37] тетраэдрическому дереву: http://www.shapeways.com/model/1393166/sierpinski-tree-85mm.html?li=shortUrl

[38] Ветвление деревьев в 4D: http://demonstrations.wolfram.com/TreeBranchingIn4D/

[39] Тода Роуланда: http://www.wolframscience.com/summerschool/2013/faculty.html#Rowland

[40] Виталий Кауров: http://blog.wolfram.com/author/vitaliy-kaurov/

[41] целью: http://www.wolframscience.com/summerschool/2013/alumni/pons.html

[42] Симметричные трёхмерные фрактальные деревья: http://www.sciencedirect.com/science/article/pii/S0960077906003894

[43] пример: http://bugman123.com/Fractals/index.html

[44] уравнения: http://www.wolframscience.com/summerschool/resources/BernatProjectSummary.pdf

[45] Benoit B.Mandelbrot: http://www-03.ibm.com/ibm/history/ibm100/us/en/icons/fractal/team/

[46] посмотреть интерактивную демонстрацию CDF: http://data.wolframmathematica.ru/habrahabr/Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev/Prikljuchenija-v-matematicheskom-lesu-fraktalnyh-derevev_55.cdf

[47] Manipulate: http://reference.wolfram.com/mathematica/ref/Manipulate.html

[48] Майклом Барнсли: http://books.google.es/books?id=oh7NoePgmOIC&pg=PA320&dq=Barnsley+Parameter+spaces+320#v=onepage&q=Barnsley%20Parameter%20spaces%20320&f=false

[49] точечными картами: http://www.wolframscience.com/nksonline/page-407

[50] Источник: http://habrahabr.ru/post/238661/