10.04.2020 07:33
ph_piter 3 3000 Источник
Привет, Хабр! Сегодняшний пост про фракталы попался в рамках проработки темы Python, в частности, Matplotlib. Последуем примеру автора и предупредим, что в посте много тяжелой анимации, которая может даже не работать на мобильном устройстве. Зато как красиво.



Всем приятного чтения

Фракталы прекрасны. Они выстраиваются в соответствии с очень сложным паттерном и сохраняются без искажения при любом увеличении! В этой статье мы рассмотрим, как можно с легкостью начертить фракталы нескольких видов, воспользовавшись инструментом под названием L-Systems и модулем Turtle для Python, чтобы выполнить пошаговое вычерчивание.

В этой статье мы не будем чрезмерно вдаваться в технические детали; вместо этого я ограничусь кратким введением, покажу много анимированных примеров и код, при помощи которого вы сможете сами сгенерировать такой пример. Если желаете пропустить теорию и только посмотреть анимацию, сразу переходите к примерам. Кроме того, в конце я укажу несколько ресурсов, как по написанию кода, так и по базовой математике, которые вы, возможно, захотите исследовать.

Что такое фрактал?

Для начала давайте дадим «нестрогое» определение фрактала. В принципе, фрактал — это геометрическая фигура, демонстрирующая одни и те же свойства независимо от степени увеличения.

Это определение небезупречно, поэтому вот более точное с сайта Math World:
Фрактал – это объект или величина, демонстрирующие самоподобие (в формальном смысле) в любых масштабах. Объект демонстрирует при разных масштабах не идентичные структуры, но на всех уровнях фрактала должны проявляться структуры одного и того же «типа». В таком случае график, откладываемый в системе координат с логарифмическим масштабом, где по осям отсчитываются величина и масштаб, то график представляет собой прямую линию с наклоном, отражающим размерность фрактала. — Math World

Как чертить фракталы при помощи Python?

Как правило, отрисовка фракталов сложна, так как глубинная природа фракталов определяется концепцией рекурсии. Говоря о графиках и их вычерчивании, мы обычно считаем, что они образованы пикселями или векторами, но количество пикселей или векторов всегда ограничено, а фракталы по определению бесконечно рекурсивны. Таким образом, попытавшись нанести фрактал на координатную сетку, мы в какой-то момент должны будем остановиться, и именно поэтому мы в данном случае говорим об «итерациях». На каждой итерации фрактал становится все сложнее, и в какой-то момент становится невозможно отличить две его итерации, следующие друг за другом (такой момент наступает, когда изменения происходят на уровне, сравнимом с размером пикселя). Здесь логично остановиться, но, как правило, форма фрактала вырисовывается быстрее, и остановиться можно еще раньше.

Два подобных примера – квадратный остров Коха, чья структура четко вырисовывается после трех итераций, и дракон Картера-Хейтуэя, для построения полной структуры которого достаточно 8 итераций. Необходимое количество итераций сильно зависит от конкретного фрактала, с которым мы работаем.

Разумеется, существует множество библиотек на Python для построения графиков, среди которых наиболее популярна Matplotlib, но они обычно рассчитаны на нанесение статистических данных и вычерчивание хорошо известных графиков. В частности, Matplotlib содержит некоторые низкоуровневые конструкции, при помощи которых можно строить фракталы, но на этот раз мы сосредоточимся на незаслуженно малоизвестном модуле стандартной библиотеки, который называется Turtle.

Модуль Turtle

В документации Python читаем: «графика Turtle – популярный инструмент для первого знакомства детей с программированием. Он входил в состав оригинального языка программирования Logo, разработанного Уолли Фёрзегом и Сеймуром Пейпертом в 1966 году.»

Суть заключается в том, что черепаха по умолчанию распознает 3 команды:

  • Ползти вперед
  • Повернуть влево на угол
  • Повернуть вправо на угол

Примечание: в стандартной библиотеке предоставляются и другие команды, но здесь мы будем пользоваться только этими тремя.

Также мы можем:

  • Отключить запись
  • Включить запись

Эти характеристики кажутся слишком простыми, чтобы, опираясь только на них, вычертить такой сложный график как фрактал, но мы воспользуемся другим инструментом, который использует только этот небольшой набор инструкций. Я говорю о L-системах.

L-системы

L-система – это способ представления рекурсивных структур (например, фракталов) в виде строки символов и многократной перезаписи такой строки. Опять же, дадим формальное определение:
Система Линденмайера, также известная как L-система, это механизм перезаписи строк, который может использоваться для генерации фракталов с размерностью от 1 до 2 — Math World

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

  • Алфавит: множество символов, которые будет использовать L-система.
  • Аксиома: исходная строка для генерации.
  • Набор инструкций создания строк: эти инструкции описывают, как каждый символ должен заменяться на следующей итерации.

Примечание для фанатов Computer Science: если вы глубоко изучали Computer Science, то все вышесказанное может о чем-то вам напоминать. Действительно, очень схожим образом определяются формальные грамматики; ключевое же отличие состоит в том, что, в отличие от грамматик, здесь на каждой итерации применяется столько правил, сколько возможно, а не всего одно. Поэтому L-системы являются подмножеством контекстно-свободных грамматик.

Учитывая, что мы собираемся использовать Turtle для построения графиков и L-системы для представления того, что собираемся наносить на график, нам необходимо создать взаимосвязь между ними.

Поскольку в Turtle мы располагаем только теми командами, что перечислены выше, присвоим каждой из них символ; из этих символов и будет состоять алфавит.

  • F: ползти вперед
  • +: повернуть вправо
  • -: повернуть влево

Чтобы это заработало, для каждого фрактала должен предоставляться угол; это и будет угол, на который черепаха будет поворачивать вправо или влево. Для простоты условимся, что предоставлен должен быть только один угол, и мы будем писать L-систему, держа это в уме.
Аксиома и инструкции создания строк будут зависеть только от фрактала, но фрактал должен быть написан таким образом, чтобы его можно было представить только этими тремя символами. Так возникает ограничение, в силу которого мы сможем строить только однострочные фракталы, то есть, нечто наподобие множества Кантора таким образом получить невозможно. Но это всего лишь упрощение, ведь мы всегда можем ввести две другие команды для движения вперед без записи, и то же самое для движения назад.

Теперь давайте перейдем к примерам!

Анимированные примеры

Следующие примеры были взяты в Интернете из нескольких общедоступных источников, и я решил портировать их на Python при помощи модуля Turtle, центрировать их, раскрасить и предоставить способ экспорта в векторный формат.

ВНИМАНИЕ: предлагаемые анимации достаточно велики, рекомендуется смотреть их лишь с хорошим интернетом. Код Repl может не работать, так как потребляет ваши ресурсы, и с отображением фракталов на мобильных устройствах возможны проблемы.

Внимание: Skulpt использует для рендеринга и создания анимации ВАШ БРАУЗЕР, так что при подвисании, лагах или любом странном поведении обычно достаточно просто заново воспроизвести анимацию или перезагрузить страницу. На мобильном устройстве может не работать.

Примеры даны в порядке усложнения (на мой субъективный взгляд), так что самое интересное – в конце.

Снежинка Коха

axiom = "F--F--F"
rules = {"F":"F+F--F+F"}
iterations = 4 # TOP: 7
angle = 60


Квадратный остров Коха

axiom = "F+F+F+F"
rules = {"F":"F-F+F+FFF-F-F+F"}
iterations = 2 # TOP: 4
angle = 90


Кристалл

axiom = "F+F+F+F"
rules = {"F":"FF+F++F+F"}
iterations = 3 # TOP: 6
angle = 90


Квадратная снежинка

axiom = "F--F"
rules = {"F":"F-F+F+F-F"}
iterations = 4 # TOP: 6
angle = 90


Фрактал Вичека

axiom = "F-F-F-F"
rules = {"F":"F-F+F+F-F"}
iterations = 4 # TOP: 6
angle = 90


Кривая Леви

axiom = "F"
rules = {"F":"+F--F+"}
iterations = 10 # TOP: 16
angle = 45


Ковер Серпинского

axiom = "YF"
rules = {"X":"YF+XF+Y", "Y":"XF-YF-X"}
iterations = 1 # TOP: 10
angle = 60


Решетка Серпинского

axiom = "FXF--FF--FF"
rules = {"F":"FF", "X":"--FXF++FXF++FXF--"}
iterations = 7 # TOP: 8
angle = 60


Квадрат

axiom = "F+F+F+F"
rules = {"F":"FF+F+F+F+FF"}
iterations = 3 # TOP: 5
angle = 90


Плитки

axiom = "F+F+F+F"
rules = {"F":"FF+F-F+F+FF"}
iterations = 3 # TOP: 4
angle = 90


Кольца

axiom = "F+F+F+F"
rules = {"F":"FF+F+F+F+F+F-F"}
iterations = 2 # TOP: 4
angle = 90


Крест-2

axiom = "F+F+F+F"
rules = {"F":"F+F-F+F+F"}
iterations = 3 # TOP: 6
angle = 90


Pentaplexity

axiom = "F++F++F++F++F"
rules = {"F":"F++F++F+++++F-F++F"}
iterations = 1 # TOP: 5
angle = 36


32-сегментная кривая

axiom = "F+F+F+F"
rules = {"F":"-F+F-F-F+F+FF-F+F+FF+F-F-FF+FF-FF+F+F-FF-F-F+FF-F-F+F+F-F+"}
iterations = 3 # TOP: 3
angle = 90


Кривая Пеано-Госпера

axiom = "FX"
rules = {"X":"X+YF++YF-FX--FXFX-YF+", "Y":"-FX+YFYF++YF+FX--FX-Y"}
iterations = 4 # TOP: 6
angle = 60


Кривая Серпинского

axiom = "F+XF+F+XF"
rules = {"X":"XF-F+F-XF+F+XF-F+F-X"}
iterations = 4 # TOP: 8
angle = 90


Анклеты Кришны

axiom = " -X--X"
rules = {"X":"XFX--XFX"}
iterations = 3 # TOP: 9
angle = 45


Квадратный фрактал Госпера

axiom = "YF"
rules = {"X": "XFX-YF-YF+FX+FX-YF-YFFX+YF+FXFXYF-FX+YF+FXFX+YF-FXYF-YF-FX+FX+YFYF-", 
        "Y": "+FXFX-YF-YF+FX+FXYF+FX-YFYF-FX-YF+FXYFYF-FX-YFFX+FX+YF-YF-FX+FX+YFY"}
iterations = 2 # TOP: 3
angle = 90


Кривая Мура

axiom = "LFL-F-LFL"
rules = {"L":"+RF-LFL-FR+", "R":"-LF+RFR+FL-"}
iterations = 0 # TOP: 8
angle = 90


Кривая Гильберта

axiom = "L"
rules = {"L":"+RF-LFL-FR+", "R":"-LF+RFR+FL-"}
iterations = 8 # TOP: 9
angle = 90


Кривая Гильберта-II

axiom = "X"
rules = {"X":"XFYFX+F+YFXFY-F-XFYFX", "Y":"YFXFY-F-XFYFX+F+YFXFY"}
iterations = 4 # TOP: 6
angle = 90


Кривая Пеано

axiom = "F"
rules = {"F":"F+F-F-F-F+F+F+F-F"}
iterations = 2 # TOP: 5
angle = 90


Крест

axiom = "F+F+F+F"
rules = {"F":"F+FF++F+F"}
iterations = 3 # TOP: 6
angle = 90


Треугольник

axiom = "F+F+F"
rules = {"F":"F-F+F"}
iterations = 2 # TOP: 9
angle = 120


Кривая дракона

axiom = "FX"
rules = {"X":"X+YF+", "Y":"-FX-Y"}
iterations = 8 # TOP: 16
angle = 90


Кривая Terdragon

axiom = "F"
rules = {"F":"F-F+F"}
iterations = 5 # TOP: 10
angle = 120


Двойная кривая дракона

axiom = "FX+FX"
rules = {"X":"X+YF+", "Y":"-FX-Y"}
iterations = 6 # TOP: 16
angle = 90


Тройная кривая дракона

axiom = "FX+FX+FX"
rules = {"X":"X+YF+", "Y":"-FX-Y"}
iterations = 7 # TOP: 15
angle = 90


Код

Все вышеприведенные примеры были получены при помощи одного и того же кода, и при работе над ними возникли некоторые сложности (например, как удержать фрактал в центре, насколько это возможно), работа с цветом, инверсией, смещениями, а также обеспечение быстрого экспорта в векторный формат. Здесь я демонстрирую вам лишь простейшую версию.
Данная версия выводит фракталы в черно-белом виде и не оснащена функционалом для экспорта 

import turtle

def create_l_system(iters, axiom, rules):
    start_string = axiom
    if iters == 0:
        return axiom
    end_string = ""
    for _ in range(iters):
        end_string = "".join(rules[i] if i in rules else i for i in start_string)
        start_string = end_string

    return end_string


def draw_l_system(t, instructions, angle, distance):
    for cmd in instructions:
        if cmd == 'F':
            t.forward(distance)
        elif cmd == '+':
            t.right(angle)
        elif cmd == '-':
            t.left(angle)


def main(iterations, axiom, rules, angle, length=8, size=2, y_offset=0,
        x_offset=0, offset_angle=0, width=450, height=450):

    inst = create_l_system(iterations, axiom, rules)

    t = turtle.Turtle()
    wn = turtle.Screen()
    wn.setup(width, height)

    t.up()
    t.backward(-x_offset)
    t.left(90)
    t.backward(-y_offset)
    t.left(offset_angle)
    t.down()
    t.speed(0)
    t.pensize(size)
    draw_l_system(t, inst, angle, length)
    t.hideturtle()

    wn.exitonclick()


Пояснение кода 

import turtle


Сначала нужно импортировать модуль Turtle 

def create_l_system(iters, axiom, rules):
    start_string = axiom
    if iters == 0:
        return axiom
    end_string = ""
    for _ in range(iters):
        end_string = "".join(rules[i] if i in rules else i for i in start_string)
        start_string = end_string

    return end_string

Затем потребуется сгенерировать L-систему, которая будет представлять собой набор инструкций для черепахи. Определяем функцию create_l_system, которая получает количество итераций, аксиому и правила построения. Она начинает работу с аксиомы и использует вспомогательную переменную end_string, если итерация равна 0, то она вернет аксиому, поскольку некоторые фракталы можно наносить и нулевыми итерациями. В данном случае предполагается, что правила имеют вид словарей, поэтому каждый ключ уникален, представляет собой символ, а значение указывает, что и чем нужно заменить. Так мы объединяем все замены для каждого символа и в итоге получаем строку для следующей итерации.

def draw_l_system(t, instructions, angle, distance):
    for cmd in instructions:
        if cmd == 'F':
            t.forward(distance)
        elif cmd == '+':
            t.right(angle)
        elif cmd == '-':
            t.left(angle)

Затем определяем draw_l_system, которая принимает черепаху, набор инструкций (вывод L-системы), угол для поворота влево или вправо и длину каждой отдельной линии. Она состоит из простой структуры elif для каждой из ранее определенных команд. 

def main(iterations, axiom, rules, angle, length=8, size=2, y_offset=0,
        x_offset=0, offset_angle=0, width=450, height=450):

    inst = create_l_system(iterations, axiom, rules)

    t = turtle.Turtle()
    wn = turtle.Screen()
    wn.setup(width, height)

    t.up()
    t.backward(-x_offset)
    t.left(90)
    t.backward(-y_offset)
    t.left(offset_angle)
    t.down()
    t.speed(0)
    t.pensize(size)
    draw_l_system(t, inst, angle, length)
    t.hideturtle()

    wn.exitonclick()

Наконец, поговорим о функции main, которая принимает все параметры, необходимые для генерации L-систем, а также y_offset, x_offset, offset_angle, width и height. Три первых описывают смещение черепахи, это необходимо просто для позиционирования графика на холсте так, как нам того хочется.

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

Особые соображения

Как я упоминал выше, здесь оставлено множество ограничений. Во-первых, мы не предусмотрели для черепахи возможность двигаться без отрисовки; для этого потребовался бы еще один символ. Нет здесь и символа для отступления назад, и для запоминания предыдущих позиций. Они не требовались для всех фракталов, рассмотренных выше, но обязательны для некоторых других (например, фрактальных деревьев).

Дополнительные ресурсы

В Интернете множество ресурсов по фракталам, где они рассматриваются как с точки зрения программирования, так и с точки зрения математики. Следующие два показались мне особенно интересными: 3Blue1Brown (математика) и CodingTrain (код).

Статья написана под впечатлением поста с Math World и статьи Пола Бурка.