Как правило, отрисовка фракталов сложна, так как глубинная природа фракталов определяется концепцией рекурсии. Говоря о графиках и их вычерчивании, мы обычно считаем, что они образованы пикселями или векторами, но количество пикселей или векторов всегда ограничено, а фракталы по определению бесконечно рекурсивны. Таким образом, попытавшись нанести фрактал на координатную сетку, мы в какой-то момент должны будем остановиться, и именно поэтому мы в данном случае говорим об «итерациях». На каждой итерации фрактал становится все сложнее, и в какой-то момент становится невозможно отличить две его итерации, следующие друг за другом (такой момент наступает, когда изменения происходят на уровне, сравнимом с размером пикселя). Здесь логично остановиться, но, как правило, форма фрактала вырисовывается быстрее, и остановиться можно еще раньше.
Два подобных примера – квадратный остров Коха, чья структура четко вырисовывается после трех итераций, и дракон Картера-Хейтуэя, для построения полной структуры которого достаточно 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-систему, держа это в уме.
Аксиома и инструкции создания строк будут зависеть только от фрактала, но фрактал должен быть написан таким образом, чтобы его можно было представить только этими тремя символами. Так возникает ограничение, в силу которого мы сможем строить только однострочные фракталы, то есть, нечто наподобие множества Кантора таким образом получить невозможно. Но это всего лишь упрощение, ведь мы всегда можем ввести две другие команды для движения вперед без записи, и то же самое для движения назад.