Построение фракталов в excel

Обновлено: 23.01.2025

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

Текст научной работы на тему «Визуализация решений логистического уравнения, множеств Мандельброта и Жюлиа в Excel и Visual Basic»

Миллер Дейв Бриджес Ричард

ВИЗУАЛИЗАЦИЯ РЕШЕНИЙ ЛОГИСТИЧЕСКОГО УРАВНЕНИЯ, МНОЖЕСТВ МАНДЕЛЬБРОТА И ЖЮЛИА В EXCEL И VISUAL BASIC

В настоящей статье рассматриваются способы изображения множеств с помощью различных программным средств. Сначала мы1 изучаем логистическое уравнение, используя современные средства управления рабочим листом (Excel worksheet) - «движки» и макросы1, управляемые кнопками. Затем те же средства применяются к множествам Мандельброта и в заключение рассматриваются образы1 множеств Мандельброта и Жюлиа, полученные с выеоким разрешением благодаря использованию менее известных но гораздо более эффективным алгоритмов.

В 1976 году Р. Мэй [1] настоятельно рекомендовал, чтобы знакомство с логистическим уравнением происходило на ранней стадии математического образования. Правда тогда только калькуляторы были доступны широкой публике.

Iterations 0 to 500

популяции к моменту п и N - максимальная популяция. Р. Мэй использовал эквивалентную модель (2), где А - константа.

Диаграмма 1. Хаотическое Диаграмма 2. Цикл с пери-поведение при А = 3.701. одом 7 при А = 3.702.

МОДЕЛИРОВАНИЕ В EXCEL

При открытии рабочего листа Excels с именем logisticterms (Miller, 2001) подсчитывают. ся 500 итераций уравнения

. (2) и демонстрируется гра-

. фик зависимости между xn

и n. Значение параметра А связано с движком и мо. жет меняться от 0 до 4 с

шагом 0.001. Другой движок связан с начальным . значением х0, которое меняется от 0 до 1 с шагом 0.001. Кнопка, связанная с макросом, позволяет пользователю увидеть больше итераций, сгруппированных по 500, и тем са-

мым увидеть, стабилизируются ли итерации при больших значениях п. Таким образом можно изучать поведение модели при разных значениях А и х0. Диаграммы 1 и 2 показывают эффект изменения А от 3.701 до 3.702 (х0 = 0.5)

Множество Мандельброта было открыто только в 1982 и с тех пор изображения самого множества, его частей и связанного с ним множества Жюлиа стали весьма популярны.

Последовательность (орбита) значений z получается посредством итераций

z1 = f(z0, c), z2 = f(zp

Очевидно, орбита зависит от начального значения z0 и от значения константы с. При этом обнаруживаются два явления. Либо zn стремится к бесконечности (обычно с большой скоростью), либо стремится к фиксированно-

Диаграмма 4. Цикл с периодом 7 при А = 3.702.

му числу или к предельному циклу, состоящему из конечного числа точек.

На рабочем листе подсчитываются 50 итераций для каждой точки из заданного диапазона и определяется число ите-

1-1 Iterations 0 to 500

Диаграмма 3. Хаотическое поведение при А = 3.701.

№ итерации Zr çz ç

5 151.19 25.63 153.35

6 22203.04 7752.05 23517.43

раций, при котором модуль z превзойдет заданное число (здесь 5000). Предполагается, что если это не произойдет за 50 итераций, то не произойдет и при большем числе итераций. Числа 50 и 5000 выбраны произвольно. Результаты расчетов с этими параметрами приведены на диаграмме 8.

Для раскраски диаграммы 8 использованы 4 цвета (в статье - оттенки серого). Точки множества Мандельброта окрашены черным цветом. Точки, для которых расходимость (I znl >5000) обнаруживается при n<17, выкрашены красным (темно-серым); если же это происходит при 17<n<33 или 34<n<49, то - желтым (светло-серым) или белым, соответственно. Выбор 4-х цветов связан со свойством рабочего листа (Microsoft Excel 97), которое позволяет связывать цвет отдельной ячейки с выполнением определенных условий (таких условий может быть только 3, что дает 4 цвета).

С ВЫСОКИМ РАЗРЕШЕНИЕМ

Наиболее распространенные «стандартные» алгоритмы построения образов множества Мандель-брота плохо работают при больших увеличениях, необходимых для демонстрации самых интригующих явлений, связанных с такими множествами. Здесь Диаграмма 7

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

Множество Мандельброта - это множество значений с, для которых последовательность итераций zn не расходится при z0 = 0. Множество Жюлиа для заданного параметра с - это множество тех z0, при которых последовательность итераций zn не расходится. Таким образом существует только одно множество Мандельброта и бесконечно много множеств Жюлиа. С этими простыми определениями связано большое количество интереснейших явлений, которых мы лишь слегка касаемся в данной статье.

Чтобы создать изображение одного из этих множеств, нужно установить соответствие между массивом пикселей на экране компьютера и множеством комплексных чисел z. Условимся, что х-коор-дината на экране представляет вещественную часть числа z, а y-координата - мнимую часть. Соответствующий программный код для среды программирования Visual Basic 5 приведен в листинге 1. В других средах могут быть отличия в деталях, но принципы сохраняются.

Первая секция листинга содержит объявления переменных. Те, что участвуют в итерациях, объявлены как Double для сохранения точности, иначе изображения могут потерять детали при большом увеличении. Подпрограмма Form_Load игра-

Остальные короткие функции и подпрограммы:

- NotPlottedYet проверяет, был ли изменен цвет пикселя по сравнению с начальным; такая проверка упрощает дальнейшую работу с массивом пикселей;

- PlotPixel окрашивает пиксель;

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

Подпрограмма Form_Load просматривает все пиксели, преобразуя экранные координаты в координаты комплексной плоскости, и затем вызывает подпрограмму ComputeColour, которая выполняет математические преобразования. Таким образом Form_Load можно рассматривать как скелет любой программы, рисующей фракталы различных типов. Нужно только внести соответствующие изменения в ComputeColour. Пользователь может увидеть почти с первых шагов, как будет выглядеть изображение. Оно вычисляется с двойным разрешением, определяемым переменной s.

Математическая часть задачи выполняется в ComputeColour. Здесь экран представляет часть комплексной плоскости параметра с. Числа zn = f(zn-1, c), n = 1, 2, 3, . z0=0, полученные из уравнения (3) хранятся в массивах zrorb() и ziorb() (для стандартного алгоритма это не явля-

ется необходимым). Цикл Do loop работает, пока либо число итераций, либо модуль zn не превысят заданных границ. В первом случае с принадлежит множеству Мандельброта, и точка окрашивается одним цветом (обычно черным), а во втором - не принадлежит и окрашивается другим цветом. В простейшем варианте (palno =1) все точки, не принадлежащие множеству Мандельброта, окрашены одним цветом. Однако, как будет показано далее, целесообразней сделать цвет зависящим от числа итераций, проделанных до того, как достигнуто предельное значение модуля zn (maxmodzsq). Это приводит к появлению множества цветных контуров вокруг множества Мандельброта. Простейший выбор - чередование цветов контуров (рисунок 1).

Выбор предельного числа итераций (maxiter) зависит от степени увеличения. Если maxiter мало, то при большом увеличении граница изображаемого множества будет искажаться. Значение maxiter = 256 годится только для небольшого увеличения, а maxiter= 1024 подходит для любого увеличения, хотя и замедляет работу программы.

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

Пусть ваш код правильно изображает множество Мандельброта и окружающие его контуры. Теперь измените код, чтобы был реализован Case 2 (двухцветная схема -palno =1). В этом случае все еще используется стандартный алгоритм, и можно увидеть, насколько он неэффективен (рисунок 2) по сравнению с более мощным алгоритмом, реализованным в Case 3. В Case 2 теряется тонкая структура границы изображаемого множества (рисунок 3).

Упомянутый выше метод основан на существовании потенциала в области комплексной с-плоскости вне множества М. Добавим, что контуры, рисуемые данной программой, являются эквипотенциальными линиями для электростатического поля заряда, распределенного на множестве М. Подробности, а также многие интересные следствия можно найти в [4].

очень большой вблизи множества М, нужно быть уверенным в отсутствии переполнения (в этом причина сравнения с maxmodzsq). Величина delta (ширина пикселя) подсчитывается в конце подпрограммы SetFractal, так как она зависит от степени увеличения. Дополнительная переменная dfactor (поправочный множитель) обеспечивает тонкую настройку, так как результат очень чувствителен к величине delta. Если Mdist (оценка расстояния между с и М) не превышает эту величину, то переменной colour присваивается значение 1 (черный), что обозначает точку, удаленную от М не более, чем на ширину пикселя, но не принадлежащую М. Если

Рисунок 2 Рисунок 3

colour = 0 соответствует серому цвету, а colour =1 - черному (как в SetColours), то при достаточно большом увеличении в правильно выбранном месте видны малые копии М, окрашенные серым цветом, сквозь которые просвечивают черные нитевидные структуры (Cases 2-15 в SetFractal и рисунок 4). Пиксели, не принадлежащие М или окрестности границы М, можно окрашивать стандартным алгоритмом.

Множества Жюлиа вычисляются аналогичным образом, так что небольшие поправки, зависящие от значения флага j, достаточны, чтобы вместо множества Ман-дельброта вычислялось множество Жюлиа. Основное изменение состоит в том, что значение с остается фиксированным в ходе вычислений, и на экране показано изменение z, а не с. Стандартный алгоритм не нуждается в изменении, а в мето-

де оценки расстояния теперь нужно для получения рекуррентного соотношения дифференцировать по z0, а не по с.

Case 18 в SetFractal дает с большим увеличением изображение части множества Жюлиа вокруг точки z = с, где с взято из малой копии множества М, построенной в Case 15. Изменяя увеличение, можно увидеть, что множество Жюлиа для с, взятого из окрестности границы множества М, само выглядит как эта часть М.

В заключение нужно предупредить о некоторых ограничениях, присущих данной программе. Наиболее серьезное из них связано с невозможностью изменять степень увеличения интересующего нас участка простым щелчком по экрану. Написать соответствующий код несложно, однако он будет существенно зависеть от используемой среды. Менее серьезным является неэффективность вычисления множества Жюлиа - значения z быстро сходятся к предельному значению или предельному циклу, однако вычисления продолжаются пока не проделано maxiter итераций. Это может быть легко исправлено. И, наконец, отсутствуют какие-либо средства сохранения результатов, но если вы работаете в Visual Basic, то можете связать управляющую кнопку с подпрограммой, помещенной в конце листинга 3. Нажатие кнопки посылает изображение в Clipboard в виде bitmap. Имеется также большой простор для экспериментирования с цветовыми схемами; другая возможность появляется при установке значения palno = 3.

1. May R.(1976) Simple mathematical models with very complicated dynamics, Nature, 261, pp.459-467.

2. Milnor J., Thurston W.(1989) Selfsimilarity and hairiness in the Mandelbrot set, Lecture Notes, Pure and Appl. Math.,114.

3. Peitgen H-O., Jurgens H. & Saupe D.(1992) Fractals for the Classroom: Part One, Introduction to Fractals and Chaos, (Spring er-Verlag).

4. Peitgen H-O., Richter P.H.(1986) The Beauty of Fractals, (Springer-Verlag).

5. Peitgen H-O., Saupe D. (1988) The Science of Fractal Images, (Springer-Verlag).

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Dim ssize, sxmin, symin, srange, scol, sbackcol As Double Dim sx, sy, s, stop flag

Dim palno, mandelcol, nearmandelcol, notmandelcol, palcol(1024) Dim iter, maxiter, maxmodsq, maxdmodsq, delta, pi, DEMflag, j, fractalno Dim zrmin, zimin, zrange, cr As Double, ci As Double, zr As Double Dim zi As Double, t As Double

Dim zrorb(1024) As Double, ziorb(1024) As Double, zdr As Double Dim zdi As Double

Private Sub Form_Load() SetScreen SetFractal 1 SetColours

s = 256: stopflag = False

While s > smin And Not CheckForStop

If CheckForStop Then Exit For Next sy

Public Sub SetScreen()

ssize = 3900: sxmin = 0: symin = 0: srange = 256: smin = 1 screen.Height = ssize: screen.ScaleHeight = -srange screen.ScaleTop = srange

screen.Width = ssize: screen.ScaleWidth = srange: MainForm.Show End Sub

Public Sub SetFractal(fractalno)

Case 1: j = 0: zrmid = -0.75: zimid = 0: zrange = 3: maxiter = 64

palno = 0: DEMflag = False: dfactor = 1 End Select

delta = dfactor * 0.71 * zrange / srange: zrmin = zrmid - zrange / 2 zimin = zimid - zrange / 2 End Sub

Public Sub SetColours()

sbackcol = vbCyan: screen.BackColor = sbackcol mandelcol = RGB(128, 128, 128): nearmandelcol = vbBlack notmandelcol = vbWhite

palcol(0) = mandelcol: palcol(1) = nearmandelcol palcol(2) = notmandelcol Select Case palno Case 0

For c = 3 To maxiter

For c = 2 To maxiter

palcol(c) = notmandelcol Next c Case 2

palcol(c) = RGB(256 * s, 256 * s, 256 * s) Next c

palcol(c) = notmandelcol Next c End Select

Public Function NotPlottedyet(sx, sy)

If screen.Point(sx, sy) = sbackcol Then NotPlottedyet = True _ Else NotPlottedyet = False

Public Sub PlotPixel(sx, sy, scol)

screen.PSet (sx, sy) , palcol(scol)

Public Function CheckForStop() DoEvents

If stopflag Then CheckForStop = True Else CheckForStop = False

Private Sub StopButton_Click() stopflag = True

Public Function ComputeColour(zr As Double, zi As Double) If j = 0 Then cr = zr: ci = zi: zr = 0: zi = 0 iter = 0: zrorb(0) = zr: ziorb(0) = zi Do

End If End If End Function

Case Case Case Case Case Case Case Case Case Case Case Case Case Case Case Case

2: j = palno = 3: j = palno = 4: j = palno = 5: j = palno = 6: j = palno = 7: j = palno = 8: j = maxiter 9: j = maxiter 10: j maxiter 11: j maxiter 12: j maxiter 13: j maxiter 14: j = maxiter 15: j = maxiter 16: j = maxiter 17: j = ci = -0 dfactor 18: j = cr = 0. DEMflag

zrmid = -0.75: zimid = 0 DEMflag = False: dfactor zrmid = -0.75: zimid = 0

DEMflag = True: dfactor = 1

zrmid = -0.75: zimid = 0

DEMflag = True: dfactor = 1 zrmid = -0.75: zimid = 0

zrange = 3 = 1 zrange = 3

DEMflag = True: dfactor = 1

zrmid = 0: zimid = -1: zrange = 0.1: maxiter = 64 DEMflag = True: dfactor = 1

zrmid = -0.05: zimid = -1: zrange = 0.05: maxiter = 256 DEMflag = True: dfactor = 1

zrmid = 0.2849758: zimid = -0.0112716: zrange = 1 = 64: palno = 1: DEMflag = True: dfactor = 0.5 0: zrmid = 0.2849758: zimid = -0.0112716: zrange = 0.1 = 128: palno = 1: DEMflag = True: dfactor = 0.5

= 256: palno = 1: DEMflag = True: dfactor

zrmid = 0.2849758: zimid = -0.0112716

= 1024: palno = 1: DEMflag = True: dfactor = 0.5

zrmid = 0.2849758: zimid = -0.0112716

= 1024: palno = 1: DEMflag = True: dfactor = 0.5

zrange = 0.01 = 0.5 zrange = 0.001

zrmid = 0.2849758: zimid = -0.0112716: = 1024: DEMflag = True: palno = 1: dfactor = 0.5 0: zrmid = 0.2849758: zimid = -0.0112716: zrange = 0.000001 = 1024: DEMflag = True: palno = 1: dfactor = 0.5 0: zrmid = 0.2849757: zimid = -0.0112718: zrange = 0.0000005 = 1024: DEMflag = True: palno = 1: dfactor = 0.5 1 : zrmid = 0 : zimid = 0 : zrange = 3 : cr = 0 : ci = 1 = 256: DEMflag = True: palno = 1: dfactor = 0.5 : 1: zrmid = 0: zimid = 0: zrange = 3: cr = 0.2849757 .0112718: maxiter = 1024: palno = 1: DEMflag = True = 0.5

= 1: zrmid = 0.2849757: zimid = -0.0112718: zrange = 0.0001 2849757: ci = -0.0112718: maxiter = 1024: palno = 1 = True : dfactor = 0.5

Система итерированных функций это конечный набор функций Fi: X -> X в метрическом про-странстве X. Каждая из них расширяется до отображения Fi: H(X) -> H(X), где H(X) это пространство точки которого являются непустыми сжатыми подмножествами X. Если использовать Хаусдорфову метрику, то H(X) полно если X было полным. Кроме того, сжатия FiX X остаются сжатиями и на H(X). В совокупности, определяют новое сжатие F: H(X) -> H(X), по следующей формуле: для каждого A∈H(X), F(A) = ∪Fi(A). Из общей теории, для полного метрического пространства X, F имеет фиксированную точку AF: F(AF) = AF, которую можно достичь последовательными приближениями из любой начальной точки. Фиксированные точки IFS иногда называются аттракторами или инвариантами.

Рисунок 6. Пример построения треугольника Серпинского с помощью IFS.
Таким образом, возникают две задачи. Первая – это нахождение аттрактора заданной IFS. Вто-рая проблема противоположна первой: для заданного множества A∈H(X), найти IFS для которой A является аттрактором.

1.2 Детерминированный алгоритм

Первая проблема решается с помощью детерминированного алгоритма.
Начнем с множества A0∈H(X) и станем последовательно вычислять
Ak = ∪Fi(Ak-1) = F(Ak-1), k > 1. Ряд

1.3 Алгоритм случайных итераций

Математика альтернативного алгоритма – алгоритма случайных итераций, сложнее, но его при-менение проще. Сопоставим позитивные частоты pi отображениям Fi. Начнем с произвольной точки x0∈X. На каждом шаге k+1, выберем xk+1 из множества . Fj(xk) выбирается с веро-ятностью pj / pi. Последовательность[5] сходится к AF. На практике, чтобы изобразить при-ближение AF на компьютере, точки последовательности выводятся на экран. Числа никак не изменяют AF, но существенно влияют на процесс отображения его приближений.

1.4 Теорема коллажа

Обратная задача приближенно решается теоремой коллажа. Цитируя М. Барнсли: “теорема го-ворит нам, что чтобы найти IFS аттрактор которой “похож” на данное множество необходимо найти набор сжимающих отображений некоторого большего множества включающего своим подмножеством исходное множество, таких, что объединение, или коллаж, отображений этого множества аппроксимировало бы исходное множество”.

1.5 Использование

Изображение делится на небольшие неперекрывающиеся квадратные области, называе-мые ранговыми блоками.
Строится пул всех возможных перекрывающихся блоков в четыре раза больших ранго-вых — доменных блоков.
Для каждого рангового блока по очереди «примеряем» доменные блоки и ищем такое преобразование, которое делает доменный блок наиболее похожим на текущий ранго-вый.
Пара «преобразование — доменный блок», которая приблизилась к идеалу, ставится в соответствие ранговому блоку. В закодированное изображение сохраняются коэффициенты преобразования и координаты доменного блока. Содержимое доменного блока нам ни к чему — вы же помните, нам все равно с какой точки стартовать.

Декодирование же производится просто и довольно быстро. Берем любое изображение, делим на ранговые области, последовательно заменяем их результатом применения соответствующего преобразования к соответствующей доменной области (что бы она ни содержала в данный мо-мент). После нескольких итераций исходное изображение станет похоже на себя:

Рисунок 8. Пример восстановления сжатого изображения.

2. Системы Линденмайера

[3]
Красота растений привлекала внимание математиков веками. Активнее всего изучались инте-ресные геометрические свойства растений, такие как симметрия листьев относительно центральной оси, радиальная симметрия цветов, и спиральное расположение семечек в шишках. «Красота связана с симметрией» (H. Weyl. Symmetry). Во время роста живых организмов, особенно растений, можно четко видеть регулярно повторяющиеся многоклеточные структуры. В случае составных листьев, например, маленькие листочки, которые являются частью большого взрослого листа, имеют ту же форму, что весь лист имел на раннем этапе формирования.

В 1968г. Венгерский биолог и ботаник Аристид Линденмайер (Aristid Lindenmayer) предложил математическую модель для изучения развития простых многоклеточных организмов, которая позже была расширена и используется для моделирования сложных ветвящихся структур — разнообразных деревьев и цветов. Эта модель получила название Lindenmayer System, или про-сто L-System.

2.1 Основные идеи

Основная идея L-систем — постоянная перезапись (rewriting) элементов строки. О чем это? В данном случае перезапись — это способ получения сложных объектов путем замены частей простого начального объекта по некоторым правилам. Классическим примером является сне-жинка Коха. На рисунке инициатор — это начальный объект, грани которого заменяются на объект-генератор. Далее с новым объектом проделывается то же самое.

Рисунок 1. Снежинка Коха.

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

Рисунок 2. Иерархия Хомского.

2.2 Простейшие L-системы

Также, как и в классификации Хомского, L-системы имеют и свою классификацию от простых до сложных и мощных.
Самым простым примером являются детерминированные контекстно-свободные L-системы или сокращенно DOL. Я не люблю формальные определения грамматик, так что скажу просто своими словами. Есть некоторый набор символов — алфавит. Этим алфавитом записывается строка, с которой работает L-система. Есть аксиома — первоначальная строка из одной или более буквы и набор правил вида a → ab. Во время каждой итерации алгоритма, применяя правило к букве из текущей строки, она (буква) заменяется на набор букв справа от стрелки. Проще рассмотреть конкретный пример развития многоклеточного организма Anabaena catenula, который изучал Линденмайер, когда он предложил модель L-систем.
Пусть наш алфавит состоит из следующих символов, каждый из которых обозначает некоторую клетку: alar bl br.
Аксиома состоит из одного символа:
ω: ar
И четырех правил.
p1: ar → albr
p2: al → blar
p3: br → ar
p4: bl → al

Правила говорят, какие символы меняются на какие в процессе роста организма. На картинке видно как, применяя правила мы наблюдаем «деление» клеток и развитие.

Рисунок 3. L-система симулирующая развитие Anabaena catenula.

2.4 Использование LOGO

F — продвинуться вперед и нарисовать линию
f — продвинуться вперед ничего не рисуя
+ — повернуть влево
— — повернуть вправо
& — повернуть вниз
^ — повернуть вверх
\ — наклониться влево
/ — наклониться вправо
| — развернуться на 180 градусов

2.5 Растения и ветвящиеся структуры

Все, что было до этого является, в общем-то, непрерывными кривыми. Такой способ моделиро-вания не подходит для моделирования растений с их ветвящейся топологией. Для этого в алфа-вит были добавлены символы [ и ], которые обозначают начало и конец ветвления соответ-ственно. Когда черепашка встречает символ [, ее текущее состояние пишется в стек и извлекает-ся оттуда при встрече символа ]. Уже такой простой грамматикой можно сгенерировать доволь-но интересные двумерные и трехмерные объекты похожие на деревья.

Рисунок 5. Примеры ветвящихся L-систем.

2.6 Стохастические L-системы

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

2.7 Контекстно-зависимые L-системы

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

2.8 Параметрические L-системы

К каждому символу добавляется параметр-переменная (возможно не одна), которая позволяет, например, указывать величину угла поворота для + и -, длину шага и толщину линии, проверять условия для применения правила, считать количество итераций и передавать «сигналы» вперед и назад. Пример параметрической L-системы.

ω: B(2)A(4, 4)
p1: A(x, y) :y <= 3 → A(x ∗ 2, x + y)
p2: A(x, y) :y > 3 → B(x)A(x/y, 0)
p3: B(x) :x < 1 → C
p4: B(x) :x >= 1 → B(x − 1)

Параметрические контекстно-зависимые L-системы позволяют моделировать рост многокле-точных организмов и растений с учетом биохимических процессов и окружающей среды.

Шёл уже последний час этого воскресенья, я уже думал идти спать, но добрый sourcerer прислал мне картинку с моего заброшенного сайта, которую можно увидеть ниже, и текст «красиво!». Эти картинки я рисовал лет пять назад, с помощью т. н. алгоритма времени убегания, но для применимости данного алгоритма, нужно уметь для заданного набора преобразований разбивать плоскость на регионы, тогда я не придумал, как это сделать, и больше к этому алгоритму не возвращался. Но сейчас я сразу сообразил, что делать, и написал Диме: «Сначала Random IFS, потом kNN, а затем Escape-Time Algorithm!»

Под рукой у меня был только старый нетбук, который мне дали друзья на время, пока мой ноутбук в ремонте. Дима мне ещё что-то говорил, я ему что-то отвечал, но у меня уже в голове писался код, и я искал на нетбуке хоть какой-нибудь компилятор или интерпретатор и нашёл C++ Builder 6! После этого я понял, что утро я встречу наедине с борландовским компилятором. Через пять часов я отправил Диме новых картинок, но он, как нормальный человек, давно спал…

Итак, немножко формул. Представим, что у нас есть конечный набор преобразований плоскости T_i: R 2 → R 2 , i = 1, . k. Для произвольного множества E определим T(E) = T₁(E) ∪… ∪ T_k(E), т. е. подействуем каждым преобразованием на множество E, а результаты объединим. Можно доказать, что если отображения T_i были сжимающими, то последовательность E, T(E), T(T(E)),… сойдётся к некоторому множеству F для любого непустого компактного E. Данная конструкция и известна как система итерируемых функций.

Например, если в качестве непустого компакта взять смайлик, и рассмотреть три преобразования, каждое из которых является композицией сжатия и сдвига в i-ую вершину правильного треугольника, то первые итерации будут выглядеть так, а в пределе получится треугольник Серпинского:

Обычно вместо прямого вычисления последовательности E, T(E), T(T(E)),… для построения фракталов используют т. н. «игру в хаос», которая заключается в следующем. Выберем произвольную точку z₀ на плоскости, далее выберем случайно преобразование T_i₁ и вычислим z₁= T_i₁(z₀), далее снова случайно выберем T_i₂ и вычислим z₁= T_i₂(z₀), и т. д. Можно показать, что всё будет хорошо, и множество полученных точек будет в некотором смысле приближать множество F, определённое выше. На этот алгоритм я ниже буду ссылаться как на Random IFS.

Теперь самое время перейти к описанию алгоритма времени убегания. Пусть у нас для начала есть одно преобразование плоскости f. Для каждой точки z плоскости начнём вычислять последовательность f(z), f(f(z)), f(f(f(z))),… до тех пор пока либо число итераций не превысит некоторого заданного числа N, либо пока норма числа z не станет больше некоторого числа B. После этого цвет точки выбираем в соответствии с количеством произведённых итераций.

Если на время представить что наша плоскость является комплексной, а преобразование f(z) равно z 2 + c, то в результате работы этого алгоритма мы получим фрактальное множество Жюлиа. Более подробно про это можно прочитать в хабрастатье «Построение множества Жюлиа» хабрапользователя mephistopheies.

Пусть теперь у нас есть система итерируемых функций, заданная набором обратимых сжимающих преобразований плоскости T₁, . T_k. Пусть F — это аттрактор этой системы.

Дополнительно предположим, что множество F можно разбить так, что T_i(F) ∩ T_j(F) = ∅, i != j (это предположение далеко не всегда выполняется). Разобъём всю плоскость R 2 на куски A₁, . A_k так, что T_i(F) является подмножеством A_i для всех i. Теперь определим функцию f(z) кусочно: на множестве A_i положим f(z) = T_k −1 (z) для всех i.

Например, для треугольника Серпинского рассмотрим такое разбиение (тут есть небольшие проблемы с тремя точками, но закроем на них глаза).

А теперь самый главный вопрос, что получится, если алгоритм времени убегания применить к построенной таким образом функции f?

Получился симпатичный такой треугольник Серпинского!

Оказывается это не случайность. Ещё пару примеров:

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

А именно, сначала с помощью Random IFS генерируем несколько тысяч точек, при этом для каждой точки запоминаем номер преобразования, с помощью которого она была получена. Затем во время работы EscapeTimeAlgorithm для каждого пикселя определяем область, в которую он попадаем с помощью 1NN.

Например, для такой звёздочки 1NN даёт следующее разбиение на четыре куска:

Собирая вместе, получим:

Ещё несколько картинок.

Вот и всё. Напоследок два замечания.

Во-первых, внимательный читатель возможно задался вопросом, раз фракталы, которые строятся с помощью Random IFS, можно построить с помощью алгоритма времени убегания, то можно ли множество Жюлиа построить с помощью Random IFS? Оказывается можно, нужно просто обратить отображение f(z) = z 2 + c, вспомнив, как извлекается корень из комплексного числа. (Правда при применении этого метода для построения изображений множества Жюлиа возникают большие трудности.)

Во-вторых, в статье было рассказано что происходит, если вы хотите узнать почему так происходит, то рекомендую книгу M. Barnsley «Fractals Everywere».

Началось всё с урока информатики, когда мы выполняли задание в Excel. Результатом работы должен был быть график в виде символа бесконечности. Я закончил немного раньше и поиграл с параметрами, а график интересно себя вёл. А потом вернулся домой и сделал вот это:

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

Всё сложно, формулы рандомные, делал так, как душа хотела.

И есть два параметра a и b (в верхнем левом углу), которые тоже зашиты в эти формулы и серьёзно влияют на вид графика.

Посмотрим, например, на первый график серого цвета. При a=b=1 он выглядит так:

Как он строился:

х меняется от 0 до 2580 град. с шагом 1. Далее x переводится в радианы. Для упрощения восприятия формул считаем, что х там уже в радианах.

Строим зависимость z(y)

Остальные графики - аналогично. Намешать всего в кучу с надеждой, что получится что-то красивое

А теперь наиболее красивые картинки. Каждый график рисуется своим цветом. Если на разных картинках будут две абсолютно разные загогулины, но одинакового цвета, то это один и тот же график, только с разными параметрами a и b

Вообще при целых a (и особенно кратных 3, 6, 12. ) достаточно часто получаются особенно чёткие графики.

Продолжать можно бесконечно.

Кому интересно, вот файл:

На этом всё! Будут вопросы - пишите, постараюсь ответить.

Лига математиков

382 поста 1.8K подписчиков

Поставь себе матлаб для этого и отстань от экселя.

Ниче не понял но получилось интересно

О, моё почтение, дружище!

(я репетитор по информатике, мне такой пост - бальзам на душу)

4. Wolphram alpha

6. python + matplotlib

9. Excel/Google table + сеть - морской бой по сети.

Когда ещё не было этих ваших экселей, такое на осциллографе делали, только там всё "вживую" можно было менять

Ахтунг! Лиссажу на Пикабу!

Наконец-то годный пост о том, чем заняться в свободное время!
ТС, плюсую!
Вы большой молодец, спасибо за содержательный пост, пояснения и ссылки.

Я когда поступил на первый курс программистской специальности, тоже любил картиночки генерировать (и сейчас люблю)

Помню на Делфи сделал треугольник Серпинского. Фрактальная геометрия, мать её

круто, но не удивительно, учитывая то, что знающие люди могут в САПР и моделирование через эксель.

автору можно перенести функционал движка UE4 на эксель в один файл, после чего к нему сразу прилетит вертолет с нобелевской премией и каким-нибудь йен-сун-хуанем, который предложит контракт на должность CEO в какой-нибудь NVIDIA.

З.Ы. я в универе на математическом моделировании подобное писал формулами, в AnyLogic. автор может посмотреть и изучить ПО, если ему интересно.

Я так делал функцию рандом() в еще 7-й одинэске году в 2005)

В институте на паскале делали анимированные графики.

Продолжай эксперименты, может и такую картинку получишь

Ну всё, теперь читай матан, про теорию хаоса и аттракторы

Теперь осваивайте фракталы, там тоже красиво может получаться

Там в одной формуле сидит теория кротовой норы. А он её визуализировал. Что до него никто в мире не делал. Вот так, мы с лёгкостью проходим мимо открытия межпространственного перемещения, и идём копаться в песочнице .

Был когда-то очень популярный mp3-плеер WinAMP. И были к нему сторонние плагины визуализации. Один из них (название не помню) был - рай для математика-гика: в настройках задавалась форму и пачка дополнительных параметров цикличности и всего такого. Параметры a, b, c, x, y и т.д. брались из звуковой дорожки по разным частотам. Вобщем вариативности хватало. Было несколько десятков уже готовых моделей, которые переключались при проигрывании трека.

5 секунд гугления: Advanced Visualization Studio. Наверное, это он.

У меня Excel отжирал много ресурсів, а вот в MathCad или mathlab как то по лучше. Фигуры Лиссажу прикольные)
аж всплакнул. Ех молодость

на третьей картинке логотип Хабра )))

Есть вопрос, офтоп но по Excel: Пользуюсь старым Excel 2007, работа с прайс-листом и его рассылка оптовикам. Но сейчас появилась необходимость вставить информацию с ценами закупки, чтоб всегда было "под рукой". Есть какие-нибудь способы "закрыть" доступ к отдельному столбцу или в крайнем случае к отдельному листу? В гугле есть какие-то инструкции чтоб установить пароль, но я не увидел результат. Гуру экселя, посоветуйте как быть с такой задачей?

Странно, что самореферентную формулу Таппера не вспомнили)

некоторые можно даж где-то использовать для иллюстраций и графики.

Рисовать в экселе?! А че так можно было?

У меня мозг нахой щас перегорел пока понимал как делается ))))

Очень красиво. Я только вбивать цифры и символы могу

Ни хрена не понятно, но красиво-о-о!)))

Блин, была же целая книга с реалистичными пейзажами. Эх, разве теперь вспомнишь.

Спасибо! Получила истинное удовольствие от вашего поста!

А я такие рисоваль

Похожая штука, но в динамике, очень красиво

Не знал что на экселе можно слелать такое. А по какому учебнику занимаетесь?

Нобелевку этому господину

О. На Спктруме 48к в бейсике такие же хрени выделывал! Было дело)))

Очень здорово!у меня вопрос,возможно глупый,можно ли каким либо способом перевести екселевские графики в вектор?

Никогда ещё математика не выглядела для меня так красиво

Графики уж очень похожи как будто призывают дьявола! Аккуратно там.

Вот это я понимаю, современное искусство

Спасибо, скачала! ) Читала и думала - надо такое же построить )

Надеюсь, наши палаты в дурдоме будут соседними)

У меня бабушка так хуярит без exel'я.

Такие узоры порой плетет,что думаешь:

"Или проверить ее на наличие укуса паука-мутанта,либо на наличие в моче каннабиноидов".

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

Сама очень уважаю Exel. За время учебы в универе только в нем и оформляла лабы.

Такими темпами изучай шейдеры и цены тебе не будет

А можно как-то озвучить такие графики? Я имею в виду, связать с нотами?

Это делается в Экселе? Я не с первого раза там формулу посчитать запущу. Не было в школе уроков таких) и по работе не был нужен, кроме заполнения там отчётов

Вроде бы прочитала пост, но к сожалению он на эльфийском.

Мне кажется, что найдена формула перемещения во времени))

Как выбрать тип диаграммы?

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

Держите шпаргалку, которая поможет определиться, какую диаграмму выбрать для построения.

В зависимости от типа данных, диаграммы на схеме разделены на 4 основные группы:

• Сравнение (характеристики: сравнение величин, много периодов, неповторяющиеся данные);

• Распределение (характеристики: распределение величин, обычно две переменных);

• Состав (характеристики: структура величин, статика);

• Отношение (характеристики: отношение величин, обычно три переменных).

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

Формула всего

Формула Таппера- впервые формула была опубликована в 2001 году в докладе Джеффа Таппера, это самореферентная (при определённых условиях) формула, будучи отображённой на плоскости, создаёт собственное изображение.

Формула является вот таким неравенством:

Что значит "будучи отображённой на плоскости, создаёт собственное изображение"? Ну, собственно это и значит. Если отобразить это неравенство на плоскости OXY, то по оси OX оно займёт 106 пикселей (от 0 до 105), а по оси OY- 17 пикселей и будет выглядеть так:

А почему это формула всего? А дело в оси OY. Видите там слева k, k+5, k+10, k+15? Ну это значения на оси OX, просто в данном случае k= 960 939 379 918 958 884 971 672 962 127 852 754 715 004 339 660 129 306 651 505 519 271 702 802 395 266 424 689 642 842 174 350 718 121 267 153 782 770 623 355 993 237 280 874 144 307 891 325 963 941 337 723 487 857 735 749 823 926 629 715 517 173 716 995 165 232 890 538 221 612 403 238 855 866 184 013 235 585 136 048 828 693 337 902 491 454 229 288 667 081 096 184 496 091 705 183 454 067 827 731 551 705 405 381 627 380 967 602 565 625 016 981 482 083 418 783 163 849 115 590 225 610 003 652 351 370 343 874 461 848 378 737 238 198 224 849 863 465 033 159 410 054 974 700 593 138 339 226 497 249 461 751 545 728 366 702 369 745 461 014 655 997 933 798 537 483 143 786 841 806 593 422 227 898 388 722 980 000 748 404 719.

Где-то там ~~в далёкой-далёкой галактике~~ на оси OY среди бесконечного количество значений есть бесконечное количество изображений, заданных этой формулой. Т.е. там есть ВСЕ ВОЗМОЖНЫЕ изображения размером 106 на 17 пикселей.

Например, при k= 172 895 466 264 656 362 238 775 198 618 400 053 006 722 417 830 074 875 710 077 840 558 718 522 933 856 481 624 057 883 539 289 927 382 958 168 812 116 931 135 487 324 743 680 349 552 434 460 222 923 986 273 388 093 735 529 486 165 346 092 911 369 252 390 353 778 634 279 896 583 455 425 859 634 440 043 584 268 093 410 716 443 082 284 154 873 275 541 781 431 502 156 517 367 941 053 074 097 258 022 615 110 586 256 528 662 395 677 501 188 461 923 095 483 961 995 173 180 815 230 411 356 269 083 712 579 786 823 770 925 493 943 423 964 558 741 203 303 534 803 553 728 066 326 116 959 373 467 996 584 250 693 892 202 679 445 143 468 361 413 129 347 669 354 301 413 221 990 4

Изображено вот такое:

Про эту формулу есть ролик у Numberphile (у Numberphile вообще много интересного есть, рекомендую)

Читайте также: