О фракталах и их алгоритмах

Фрактал происходит от латинского прилагательного "fractus", и в переводе означает состоящий из фрагментов, а соответствующий латинский глагол "frangere" означает разбивать, то есть создавать неправильные фрагменты. Понятия фрактал и фрактальная геометрия, появившиеся в конце 70-х, с середины 80-х прочно вошли в обиход математиков и программистов. Термин был предложен Бенуа Мандельбротом в 1975 году для обозначения нерегулярных, но самоподобных структур, которыми он занимался. Рождение фрактальной геометрии принято связывать с выходом в 1977 году книги Мандельброта «The Fractal Geometry of Nature» - «Фрактальная геометрия природы». В его работах использованы научные результаты других ученых, работавших в период 1875-1925 годов в той же области (Пуанкаре, Фату, Жюлиа, Кантор, Хаусдорф). Фракталам посвящены многочисленные публикации и ресурсы интернет на некоторые странички вы можете отправиться прямо сейчас.

Коррективы

Позволю себе внести некоторые коррективы в алгоритмы предложенные в книге Х.-О. Пайтгена и П.Х.Рихтера "Красота фракталов" М. 1993 сугубо для искоренения опечаток иоблегчения понимания процессов поскольку после их изучения многое осталось для меня загадкой. К сожалению эти "понятные" и "простые" алгоритмы ведут качующий образ жизни.

В основе построения фракталов лежит некая нелинейная функция комплексного процесса с обратной связью z=> z²+c поскольку z и с -комплексные числа, то z=x+iy, c=p+iq необходимо разложить его на х и у чтобы перейти в более реальную для простого человека плоскость:

x(k+1)=x(k)²-y(k)² + p,
y(k+1)=2*x(k)*y(k) + q.

Плоскость, состоящая из всех пар (x,y), может рассматриваться, как при фиксированных значениях р и q, так и при динамических. В первом случае перебирая по закону все точки (х,у) плоскости и окрашивая их в зависимости от количества повторений функции необходимых для выхода из итерационного процесса или не окрашивая (черный цвет) при привышении допустимого максимума повторений мы получим отображение множества Жюлиа. Если, напротив, определить начальнуюя пару значений (x,y) и проследить ее колористическую судьбу при динамически изменяющихся значениях параметров p и q, то получаим изображения, называемые множествами Мандельброта.

Это только присказка и дальше по порядку.

Предположим, что разрешающая способность экрана монитора или графического окна равна a x b точек, твипсов и т.п. и что он может быть одновременно раскрашен в K + 1 цветов, которые мы пронумеруем от 0 до K цветов (0 соответствует черному цвету).

1.Множества Жюлиа.
Ваш алгоритм таков:

Шаг 0:

Выбрать параметр c=p+iq, выбрать Xmin = -1.5, Ymin = -1.5, Xmax = 1.5, Ymax = 1.5
Это означает, что p- реальная переменная, iq - воображаемая, но тоже вполне реальная переменная. Например, p = 0.32 c_img = 0.043. Эти параметры являются константой при построении одного отображения и их значения определяют рисунок. Масштабировать отображения можно мненяя значения Xmax, Xmin, Ymax, Ymin.
Выбрать число M, которое считается бесконечно большим.
Этот параметр определяет максимальное число итераций
Вычислить dx=(Xmax-Xmin)/(A-1), dy=(Ymax-Ymin)/(B-1).
Для всех пар (Nx, Ny), где Nx=0,1... A-1 и Ny=0,1...B-1 выполнить следующую процедуру.

Шаг 1(первый и второй циклы):

Положить x(n)=xmin+Nx*dx, y(n)=ymin+Ny*dy, k=0. Здесь последовательно изменяются только Nx и Ny, на одно изменение Nx приходится В изменений Ny. Пиксел который будет в дальнейшем окрашиваться имеет координаты (x(n),y(n)).

Шаг 2 (третий цикл, итерация):

Вычислить x(k+1) и y(k+1), по формулам
x(k+1)=x(k)²*x(k)-y(k)² + p,
y(k+1)=2*x(k)*y(k) + q.
Увеличить счетчик k на 1 (k:=k+1).

Шаг 3 (оценка внутри 3 цикла):
Вычислить r=x(k)²+y(k)².
Если r>M, то идти на шаг 4.
Если k=K, то выбрать цвет 0 (черный) и идти на шаг 4. В этой строке что-то не так, опечатка наверное, дело в том, что количество цветов К может равняться 2, 16, 255 и т.д. и прерывать цикл с М>К нет смысла. В целом это условие касается только алгоритма раскрашивания. Строка получает законный и концептуальный вид прерывания итерации при достижении допустимого максимума если к=М, или полностью:
Если k=M то выбрать цвет 0 (черный) и идти на шаг 4.
Если r<=M и k<M. Вернуться на шаг 2.Здесь тоже была опечатка типа (Если r<=М, k<К)

Шаг 4:
Приписать цвет k точке экрана (x(n), y(n)) и перейти к следующей точке, начиная с шага 1.

2.Множества Мандельброта
Ваш алгоритм таков (с исправлениями и почти без комментариев):

Шаг 0:
выбрать pmin, pmax, qmin, qmax, .
Выбрать число M, которое считается бесконечно большим.
Положить dp=(pmax-pmin)/(A-1), dq=(qmax-qmin)/(B-1).
Для всех пар (Np, Nq), где Np=0,1... A-1 и Nq=0,1...B-1 выполнить следующую процедуру.

Шаг 1:
Положить p(0)=pmin+Np*dp, q(0)=qmin+Nq*dq, k=0, x(0)=y(0)=0. x и у - обнуляются при каждом обращении к 1 шагу поскольку в процессе итерирования значения х и у изменяются.

Шаг 2 (итерация):
Вычислить x(k+1) и y(k+1), используя формулы
x(k+1)=x(k)²*x(k)-y(k)² + p,
Увеличить счетчик k на 1 (k:=k+1).

Шаг 3 (оценка):
Вычислить r=x(k)²+y(k)².
Если r>M, то выбрать цвет k и идти на шаг 4.
Если k=M, то выбрать цвет 0 (черный) и идти на шаг 4.
r<=M, k<M. Вернуться на шаг 2.

Шаг 4:
Приписать цвет k точке экрана (p(n), q(n)) и перейти к следующей точке, начиная с шага 1.

К вопросу о алгоритмах раскраски фракталов
.

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

Применение "фрактального микроскопа"
для демонстрации пограничных явлений.

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

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

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

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