Давайте создадим самую простейшую L-систему – водоросли:
- Для этого возьмём аксиому (строку с которой мы начнём) A . Поместим её в функцию (назовём её seaweed()), которая и будет нашей L-системой (например seaweed(‘ A ‘)).
- Что же будет делать наша функция? Всё очень просто. Она заданное количество раз (пусть будет n) пробегается по нашей строке и заменяет (A → AB), (B → A). Например:
n = 3 : ABAAB
n = 4 : ABAABABA
n = 5 : ABAABABAABAAB
n = 6 : ABAABABAABAABABAABABA
n = 7 : ABAABABAABAABABAABABAABAABABAABAAB
Тадам! Проще говоря у нас есть кусочек строки, который меняется на кусочек побольше, в нём происходят те же самые действия. На этом и основывается принцип самоподобия фракталов. Как же провернуть всё это в нашей функции? Я думаю, никто не будет спорить, что это рекурсия.
Водоросли l-система
Итак, n – это ограничение нашей рекурсии поэтому в самом начале зададим условия выхода. Наша рекурсия выполнится 6 раз т.к. 7 раз ей не даст выполниться выход из рекурсии (в котором мы возвращаем готовую строку).
#14. Рисуем множество Мандельброта | Фракталы на Python
Что мы видим дальше. newlevel – это строка которая в цикле преобразуется в строку, полученную заменой по нашему условию ((A → AB), (B → A)) символов старой.
А затем просто присвоим старой строке новое значение и пойдём рекурсией дальше на новый уровень. В конце концов программа напечатает: ABAABABAABAABABAABABA.
Единственное, мы не сможем её красиво визуализировать, т.к. она состоит всего из двух букв и после визуализации будет выглядеть довольно скучно. Но на ней мы поняли принцип L-систем. Кстати, по ссылке можно найти ещё несколько классных L-систем, которые уже можно преобразовать во фракталы.
Возьмём, например, фрактал кривая Дракона . Посмотрим его условия:
переменные : X, Y
константы : F, +, −
правила : (X → X+YF+), (Y → −FX−Y)
Здесь F означает «рисуем отрезок», − означает «повернуть влево на 90°», а + означает «повернуть вправо на 90°». X и Y не соответствуют какому-либо действию при рисовании, а используются только для построения кривой.
Константы − это символы, которые при создании в рекурсии новой строки, мы просто переписываем неизменными.
Итак, создадим L-систему:
Источник: dzen.ru
В мире фракталов
uses GraphABC;
var
a,b,x,y: integer;
N: integer;
procedure lrel (dx,dy: integer);
begin
x:=x+dx; y:=y+dy; LineTo(x,y);
end;
procedure BB(k: integer); forward;
procedure CC(k: integer); forward;
procedure DD(k: integer); forward;
procedure AA(k: integer);
begin
if k>0 then
ТОП способов Ускорить Код Python. На примере построения Фрактала Мандельброта в Pygame
begin
AA(k-1); lrel(a,b);
BB(k-1); lrel(a,0);
DD(k-1); lrel(a,-b);
AA(k-1);
end;
end;
procedure BB(k: integer);
begin
if k>0 then
begin
BB(k-1); lrel(-a,b);
CC(k-1); lrel(0,b);
AA(k-1); lrel(a,b);
BB(k-1);
end;
end;
procedure CC(k: integer);
begin
if k>0 then
begin
CC(k-1); lrel(-a,-b);
DD(k-1); lrel(-a,0);
BB(k-1); lrel(-a,b);
CC(k-1);
end;
end;
procedure DD(k: integer);
begin
if k>0 then
begin
DD(k-1); lrel(a,-b);
AA(k-1); lrel(0,-b);
CC(k-1); lrel(-a,-b);
DD(k-1);
end;
end;
begin
N:=6;
a:=3;
b:=a;
x:=10;
y:=10;
SetWindowCaption(‘Ковер Серпинского’);
SetWindowSize(590,590);
MoveTo(x,y);
AA(N); lrel(a,b);ирBB(N);о lrel(-a,b);
CC(N); lrel(-a,-b);
DD(N); lrel(a,-b);
end.
___________________________________________________________________
4. Программирование фрактала «Поле из одуванчиков» на языке PascalABC
uses Utils,GraphABC;
const n=255;
max=10;
var
z,z1,c: complex;
i,ix,iy: integer;
// z=z^2+c
begin
cls;
SetWindowCaption(‘Фракталы: поле из одуванчиков’);
SetWindowSize(400,300);
c:=(0.6,0.9);
for ix:=0 to WindowWidth-1 do
for iy:=0 to WindowHeight-1 do
begin
z:=0.015*(ix-200,iy-140);
for i:=1 to n do
if abs(z1)>max then break;
if i>=n then SetPixel(ix,iy,clRed)
else SetPixel(ix,iy,RGB(255,255-i,255-i));
end;
writeln(‘Время расчета = ‘,Milliseconds/1000,’ с’);
end.
5. Пример программы построения фрактала «Дерево»
Алгоритм построения «Веточки» (М. Павлова, Н. Паньгина. Рекурсивные алгоритмы и их построение.Учебное пособие. -СПб.: Издатедьство ЦПО «Информатизация образования», 2001. — 19 с.) . Первый отрезок рисуется под произвольным углом к оси Ох, из конца данного отрезка рисуется пара отрезков, направленных в противоположные стороны от направления парвого отрезка под одинаковым величиной 30 градусов. Далее рисунок повторяется с каждым из вновь построенных отрезков с умнгтшением длины отрезклв примерно в полтора раза.
Вложенность такого рекурсивного рисунка. еае видно, не менее семи.
Рекурсивная функция имеет 4 парамеира: координаты начала отрезка, его длину и угол, под ноторым рисуется лванный отрезок к ос Ох.
Алгоритм построения состоит из следующих шагов:
длина и угол наклона).
2. Нарисовать отрезок.
3. Вызвать рекурсивную процедуру, ри сующую левую ветку, с новыми параметрами (за координаты н ачала отрезка взять только что вычисленные координаты конца отрезка, за длину — длину, уменьшенную в полто ра раза, за угол, уменьш енный на 30 градусов.
4. Вызвать р екурсивную процедуру, рисующую правую ветку (параметры такие же, как в пун кте 3, за исключением уг ла — новый угол увеличивается на 30 градусов относительно первонач ального угла ).
5. Выход из процедуры осуществляется, когда длина ветки становится очень малой (около 2 пикселей).
В программе имеется лишь одно обращение к процедуре со следующими параметрами: координаты начала самого первого отрезка, первоначаная длина отрезка, первоначальная длина отре зка и произвольный угол наклона.
Программа «Ветка дерева» на языке PascalABC
uses GraphABC;
const
radian=Pi/180; deltaangle=30*radian;
Procedure Ris(x,y: integer; len, angle: real);
var
color, xnew, ynew:integer;
Begin
if len
if len
xnew:=x+round(Len*cos(angle));
ynew:=y+ round(len*sin(angle));
SetColor(color); Line(x,y,xрnew,ynew);
Ris(xnew, ynew, len*0.65, angle-deltaangle);
Ris(xnew, ynew, len*0.65, angle+deltaangle);
end;
Be gin
Ris(100,400,160,-40*radian);
End.
6. «Снежинка»
Пример программы
//Снежинка
uses graphABC;
const
step=Pi*0.2;
Procedure DrawStar(x,y,size:integer);
var i,j,newsize, xnew,ynew:integer;
Begin
if size for i:=0 to 9 do
begin
newsize:=size;
for j:=1 to 8 do
begin
xnew:=x+round(newsize*cos(i*step));
ynew:=y+round(newsize*sin(i*step));
DrawStar(xnew,ynew,newsize div 5);
newsize:=newsize*2 div 3;
end;
end;
End;
Begin
DrawStar(320,240,160);
End.
7. Множество Мандельброта (Википедия)
Помимо геометрических построений для получения фрактала можно применять алгебраические выражения (формулы). Например, озеро Мандельброта определяется так:
Zn+1 = Zn×Zn+С , где Z – комплексное число.
В данном случае применен метод итерации, т.е. многократного расчета функции
Zn+1 = f(Zn).
Визуально, внутри множества Манделедияьброта можно выделить бесконечное количество элементарных фигур, причём самая большая в центре представляет собой кардиоиду. Также есть набор овалов, касающихся кардиоиды, размер которых постепенно уменьшается, стремясь к нулю.
Каждый из этих овалов имеет свой набор меньших овалов, диаметр которых также стремится к нулю и т. д. Этот процесс продолжается бесконечно, образуя фрактал. Также важно, что эти процессы ветвления фигур не исчерпывают полностью множество Мандельброта: если рассмотреть с увеличением дополнительные «ветки», то в них можно увидеть свои кардиоиды и круги, не связанные с главной фигурой. Самая большая фигура (видимая при рассматривании основного множества) из них находится в области от −1,78 до −1,75 на отрицательной оси действительных значений.
Источник: fraktalsworld.blogspot.com
Фракталы на Python. Пошаговое руководство
Привет, Хабр! Сегодняшний пост про фракталы попался в рамках проработки темы Python, в частности, Matplotlib. Последуем примеру автора и предупредим, что в посте много тяжелой анимации, которая может даже не работать на мобильном устройстве. Зато как красиво.
Всем приятного чтения
Фракталы прекрасны. Они выстраиваются в соответствии с очень сложным паттерном и сохраняются без искажения при любом увеличении! В этой статье мы рассмотрим, как можно с легкостью начертить фракталы нескольких видов, воспользовавшись инструментом под названием L-Systems и модулем Turtle для Python, чтобы выполнить пошаговое вычерчивание.
В этой статье мы не будем чрезмерно вдаваться в технические детали; вместо этого я ограничусь кратким введением, покажу много анимированных примеров и код, при помощи которого вы сможете сами сгенерировать такой пример. Если желаете пропустить теорию и только посмотреть анимацию, сразу переходите к примерам. Кроме того, в конце я укажу несколько ресурсов, как по написанию кода, так и по базовой математике, которые вы, возможно, захотите исследовать.
Что такое фрактал?
Для начала давайте дадим «нестрогое» определение фрактала. В принципе, фрактал — это геометрическая фигура, демонстрирующая одни и те же свойства независимо от степени увеличения.
Это определение небезупречно, поэтому вот более точное с сайта Math World:
Фрактал – это объект или величина, демонстрирующие самоподобие (в формальном смысле) в любых масштабах. Объект демонстрирует при разных масштабах не идентичные структуры, но на всех уровнях фрактала должны проявляться структуры одного и того же «типа». В таком случае график, откладываемый в системе координат с логарифмическим масштабом, где по осям отсчитываются величина и масштаб, то график представляет собой прямую линию с наклоном, отражающим размерность фрактала. — Math World
Как чертить фракталы при помощи Python?
Как правило, отрисовка фракталов сложна, так как глубинная природа фракталов определяется концепцией рекурсии. Говоря о графиках и их вычерчивании, мы обычно считаем, что они образованы пикселями или векторами, но количество пикселей или векторов всегда ограничено, а фракталы по определению бесконечно рекурсивны. Таким образом, попытавшись нанести фрактал на координатную сетку, мы в какой-то момент должны будем остановиться, и именно поэтому мы в данном случае говорим об «итерациях». На каждой итерации фрактал становится все сложнее, и в какой-то момент становится невозможно отличить две его итерации, следующие друг за другом (такой момент наступает, когда изменения происходят на уровне, сравнимом с размером пикселя). Здесь логично остановиться, но, как правило, форма фрактала вырисовывается быстрее, и остановиться можно еще раньше.
Два подобных примера – квадратный остров Коха, чья структура четко вырисовывается после трех итераций, и дракон Картера-Хейтуэя, для построения полной структуры которого достаточно 8 итераций. Необходимое количество итераций сильно зависит от конкретного фрактала, с которым мы работаем.
Разумеется, существует множество библиотек на Python для построения графиков, среди которых наиболее популярна Matplotlib, но они обычно рассчитаны на нанесение статистических данных и вычерчивание хорошо известных графиков. В частности, Matplotlib содержит некоторые низкоуровневые конструкции, при помощи которых можно строить фракталы, но на этот раз мы сосредоточимся на незаслуженно малоизвестном модуле стандартной библиотеки, который называется Turtle.
Модуль Turtle
В документации Python читаем: «графика Turtle – популярный инструмент для первого знакомства детей с программированием. Он входил в состав оригинального языка программирования Logo, разработанного Уолли Фёрзегом и Сеймуром Пейпертом в 1966 году.»
Суть заключается в том, что черепаха по умолчанию распознает 3 команды:
- Ползти вперед
- Повернуть влево на угол
- Повернуть вправо на угол
- Отключить запись
- Включить запись
L-система – это способ представления рекурсивных структур (например, фракталов) в виде строки символов и многократной перезаписи такой строки. Опять же, дадим формальное определение:
Система Линденмайера, также известная как L-система, это механизм перезаписи строк, который может использоваться для генерации фракталов с размерностью от 1 до 2 — Math World
Поняв, что такое L-система, мы сможем создавать рекурсивные структуры, но прежде давайте разберемся, какие компоненты нам для этого понадобятся. В каждой L-системе есть:
- Алфавит: множество символов, которые будет использовать L-система.
- Аксиома: исходная строка для генерации.
- Набор инструкций создания строк: эти инструкции описывают, как каждый символ должен заменяться на следующей итерации.
Учитывая, что мы собираемся использовать Turtle для построения графиков и L-системы для представления того, что собираемся наносить на график, нам необходимо создать взаимосвязь между ними.
Поскольку в Turtle мы располагаем только теми командами, что перечислены выше, присвоим каждой из них символ; из этих символов и будет состоять алфавит.
- F: ползти вперед
- +: повернуть вправо
- -: повернуть влево
Теперь давайте перейдем к примерам!
Анимированные примеры
Следующие примеры были взяты в Интернете из нескольких общедоступных источников, и я решил портировать их на Python при помощи модуля Turtle, центрировать их, раскрасить и предоставить способ экспорта в векторный формат.
ВНИМАНИЕ: предлагаемые анимации достаточно велики, рекомендуется смотреть их лишь с хорошим интернетом. Код Repl может не работать, так как потребляет ваши ресурсы, и с отображением фракталов на мобильных устройствах возможны проблемы.
Внимание: Skulpt использует для рендеринга и создания анимации ВАШ БРАУЗЕР, так что при подвисании, лагах или любом странном поведении обычно достаточно просто заново воспроизвести анимацию или перезагрузить страницу. На мобильном устройстве может не работать.
Примеры даны в порядке усложнения (на мой субъективный взгляд), так что самое интересное – в конце.
axiom = «F—F—F» rules = iterations = 4 # TOP: 7 angle = 60
axiom = «F+F+F+F» rules = 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 = iterations = 4 # TOP: 6 angle = 90
axiom = «F-F-F-F» rules = iterations = 4 # TOP: 6 angle = 90
axiom = «F» rules = iterations = 10 # TOP: 16 angle = 45
axiom = «YF» rules = iterations = 1 # TOP: 10 angle = 60
axiom = «FXF—FF—FF» rules = iterations = 7 # TOP: 8 angle = 60
axiom = «F+F+F+F» rules = iterations = 3 # TOP: 5 angle = 90
axiom = «F+F+F+F» rules = iterations = 3 # TOP: 4 angle = 90
axiom = «F+F+F+F» rules = iterations = 2 # TOP: 4 angle = 90
axiom = «F+F+F+F» rules = iterations = 3 # TOP: 6 angle = 90
axiom = «F++F++F++F++F» rules = <«F»:»F++F++F+++++F-F++F»>iterations = 1 # TOP: 5 angle = 36
axiom = «F+F+F+F» rules = 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 = iterations = 4 # TOP: 8 angle = 90
axiom = » -X—X» rules = iterations = 3 # TOP: 9 angle = 45
axiom = «YF» rules = iterations = 2 # TOP: 3 angle = 90
axiom = «LFL-F-LFL» rules = iterations = 0 # TOP: 8 angle = 90
axiom = «L» rules = iterations = 8 # TOP: 9 angle = 90
axiom = «X» rules = iterations = 4 # TOP: 6 angle = 90
axiom = «F» rules = 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 = iterations = 2 # TOP: 9 angle = 120
axiom = «FX» rules = iterations = 8 # TOP: 16 angle = 90
axiom = «F» rules = iterations = 5 # TOP: 10 angle = 120
axiom = «FX+FX» rules = iterations = 6 # TOP: 16 angle = 90
axiom = «FX+FX+FX» rules = 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 и статьи Пола Бурка.
Источник: habr.com