Фракталы

Введение

Что, скажите, привнес компьютер в нашу жизнь нового, неведомого до него? Рискуя навлечь гнев фанатиков бесчисленных вариантов применения компьютеров, заявляю: главное - он позволил нам увидеть фракталы. Это модное понятие взрывообразно шагает по планете, завораживая своей красотой и таинственностью, проявляясь в самых неожиданных областях: метеорологии, философии, географии, биологии, механике и даже истории. Если мы зададим слово «фрактал» в любом поисковике, то придем к мысли, что Рунет создавался для фракталов.

Кто придумал "фрактал"?

Первые идеи фрактальной геометрии возникли в 19 веке. Кантор с помощью простой рекурсивной (повторяющейся) процедуры превратил линию в набор несвязанных точек (так называемая Пыль Кантора). Он брал линию и удалял центральную треть и после этого повторял то же самое с оставшимися отрезками. Пеано нарисовал особый вид линии (рисунок №1). Для ее рисования Пеано использовал следующий алгоритм.
На первом шаге он брал прямую линию и заменял ее на 9 отрезков длинной в 3 раза меньшей, чем длинна исходной линии (Часть 1 и 2 рисунка 1). Далее он делал то же самое с каждым отрезком получившейся линии. И так до бесконечности. Ее уникальность в том, что она заполняет всю плоскость. Доказано, что для каждой точки на плоскости можно найти точку, принадлежащую линии Пеано. Кривая Пеано и пыль Кантора выходили за рамки обычных геометрических объектов. Они не имели четкой размерности. Пыль Кантора строилась вроде бы на основании одномерной прямой, но состояла из точек (размерность 0). А кривая Пеано строилась на основании одномерной линии, а в результате получалась плоскость.Вплоть до 20 века шло накопление данных о таких странных объектах, без какой либо попытки их систематизировать. Так было, пока за них не взялся Бенуа Р. Мандельброт (Benoit Mandelbrot), математик из Исследовательского центра им. Томаса Уотстона при IBM - отец современной фрактальной геометрии, который и предложил термин "фрактал" для описания объектов, структура которых повторяется при переходе к все более мелким масштабам.. Работая в IBM математическим аналитиком, он изучал шумы в электронных схемах, которые невозможно было описать с помощью статистики. Постепенно сопоставив факты, он пришел к открытию нового направления в математике - фрактальной геометрии.

Красота фракталов

Почему же фракталы так красивы? Так сказочно, обворожительно, волнующе (какие еще есть эпитеты?) красивы. Математика вся пронизана красотой и гармонией, только эту красоту надо увидеть. Вот как пишет сам Мандельброт в своей книге "The Fractal Geometry of Nature"

"Почему геометрию часто называют холодной и сухой? Одна из причин лежит в ее неспособности описать форму облаков, гор или деревьев. Облака - это не сферы, горы - не углы, линия побережья - не окружность, кора не гладкая, а молния не прямая линия..."

Определение фрактала

Сам Мандельброт вывел слово fractal от латинского слова fractus, что означает разбитый (поделенный на части). И одно из определений фрактала - это геометрическая фигура, состоящая из частей и которая может быть поделена на части, каждая из которых будет представлять уменьшенную копию целого (по крайней мере, приблизительно). Фрактал - это такой объект, для которого не важно, с каким усилением его рассматривать в увеличительное стекло, но при всех его увеличениях структура остается одной и той же. Большие по масштабу структуры полностью повторяют структуры, меньшие по масштабу. Так, в одном из примеров Мандельброт предлагает рассмотреть линию побережья с самолета, стоя на ногах и в увеличительное стекло. Во всех случаях получим одни и те же узоры, но только меньшего масштаба. Чтобы представить себе фрактал понаглядней рассмотрим пример, приведенный в книге Б.Мандельброта "The Fractal Geometry of Nature" ставший классическим - "Какова длина берега Британии?". Ответ на этот вопрос не так прост, как кажется. Все зависит от длины инструмента, которым мы будем пользоваться. Померив берег с помощью километровой линейки мы получим какую-то длину. Однако мы пропустим много небольших заливчиков и полуостровков, которые по размеру намного меньше нашей линейки. Уменьшив размер линейки до, скажем, 1 метра - мы учтем эти детали ландшафта, и, соответственно длина берега станет больше. Пойдем дальше и измерим длину берега с помощью миллиметровой линейки, мы тут учтем детали, которые больше миллиметра, длина будет еще больше. В итоге ответ на такой, казалось бы, простой вопрос может поставить в тупик кого угодно - длина берега Британии бесконечна.

Типы фракталов

Фракталы делятся на группы. Самые большие группы это:

Геометрические фракталы

Именно с них и начиналась история фракталов. Этот тип фракталов получается путем простых геометрических построений. Обычно при построении этих фракталов поступают так: берется "затравка" - аксиома - набор отрезков, на основании которых будет строиться фрактал. Далее к этой "затравке" применяют набор правил, который преобразует ее в какую-либо геометрическую фигуру. Далее к каждой части этой фигуры применяют опять тот же набор правил. С каждым шагом фигура будет становиться все сложнее и сложнее, и если мы проведем (по крайней мере, в уме) бесконечное количество преобразований - получим геометрический фрактал.

Рассмотренная выше кривая Пеано является геометрическим фракталом. Классические примеры геометрических фракталов - Снежинка Коха, Лист, Треугольник Серпинского).

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

Из этих геометрических фракталов очень интересным и довольно знаменитым является первый - снежинка Коха. Строится она на основе равностороннего треугольника. Каждая линия которого ___ заменяется на 4 линии каждая длинной в 1/3 исходной _/\_. Таким образом, с каждой итерацией длинна кривой увеличивается на треть. И если мы сделаем бесконечное число итераций - получим фрактал - снежинку Коха бесконечной длинны. Получается, что наша бесконечная кривая покрывает ограниченную площадь. Попробуйте сделать то же самое методами и фигурами из евклидовой геометрии. Для построения геометрических фракталов хорошо приспособлены так называемые L-Systems. Суть этих систем состоит в том, что имеется определенных набор символов системы, каждый из которых обозначает определенное действие и набор правил преобразования символов.

Треугольник Серпинского

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

Драконова ломаная

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

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

Алгебраические фракталы

Вторая большая группа фракталов - алгебраические. Свое название они получили за то, что их строят, на основе алгебраических формул иногда весьма простых. Методов получения алгебраических фракталов несколько. Один из методов представляет собой многократный (итерационный) расчет функции Zn+1=f(Zn), где Z - комплексное число, а f некая функция. Расчет данной функции продолжается до выполнения определенного условия. И когда это условие выполнится - на экран выводится точка. При этом значения функции для разных точек комплексной плоскости может иметь разное поведение:

С течением времени стремится к бесконечности.
Стремится к 0
Принимает несколько фиксированных значений и не выходит за их пределы.
Поведение хаотично, без каких либо тенденций.
Чтобы проиллюстрировать алгебраические фракталы обратимся к классике - множеству Мандельброта.

Для его построения нам необходимы комплексные числа. Комплексное число - это число, состоящее из двух частей - действительной и мнимой, и обозначается оно a+bi. Действительная часть a это обычное число в нашем представлении, а вот мнимая часть bi интересней. i - называют мнимой единицей. Почему мнимой? А потому, что если мы возведем i в квадрат, то получим -1.

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

На рисунке, изображающем множество Мандельброта я взял небольшой участок и увеличил его до размеров всего экрана (как в микроскоп). Что же мы видим? Проявление самоподобности. Не точной самоподобности, но близкой и с ней мы будем сталкиваться постоянно, увеличивая части нашего фрактала больше и больше. До каких же пор мы можем увеличивать наше множество? Так вот если мы увеличим его до предела вычислительной мощности компьютеров, то покроем площадь равную площади солнечной системы вплоть до Сатурна.

Стохастические фракталы

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

Программирование фракталов

Псевдокод, описывающий общий принцип фрактала
Объект рисуется в достаточно большом масштабеЧасти этого объекта заменяются меньшими копиями этого объекта
Ясно, что это описание рекурсивного процесса. Рассмотрим первый пример создания фрактала. Псевдокод выглядит так
Процедура Рисования Квадрата    У каждого угла квадрата рисуется квадрат меньшего размера    Рисуется квадрат, если не существуют квадраты меньшего размераКонец Процедуры

Так будет выглядеть код на VB

Private Sub Form_Click()Scale (-2000, 2000)-(2000, -2000)Square -1000, 1000, 2000End SubSub Square(x, y, Size)' для выхода из процедуры If Size < 100 Then Exit Sub   Line (x, y)-(x + Size, y - Size), , B   Square x - Size / 4, y + Size / 4, Size / 2   Square x + Size - Size / 4, y + Size / 4, Size / 2   Square x - Size / 4, y - Size + Size / 4, Size / 2   Square x + Size - Size / 4, y - Size + Size / 4, Size / 2End Sub

При выполнении каждой рекурсии появляется четыре новых угла. Каждый из них составляет одну четвертую от предыдущего. Результат представлен на рисунке

L-системы

Любителям фракталов и математических картинок известны фантастические изображения растений, полученные с помощью программ. Это так называемые L-системы. В основе их построения лежат два принципа. Первый – это так называемая «черепашья графика» (оператор draw) патриарха GWBASIC и его детей Turbo Basic и QBasic, когда движение рисуется пошагово в приращениях относительно текущей точки. Либо моделируется данное поведение, задавая движение в приращениях координат. Второй принцип – изюминка метода: каждое единичное движение заменяется на весь рисунок. Например, нарисуем вилку-рогатульку. На следующем шаге работы программы каждая из трех палочек вилки заменяется такой-же вилкой, превращая вилку в ветку с сучками, после следующего шага получим лохматый куст, потом пушистое дерево, красивое, фрактальное. Меняя вид начальной картинки можно получать самые разные изображения от зонтиков укропа до колючего перекати-поле или пучка водорослей.

Суть L-кодирования сводится к следующему. Представим себе некое виртуальное программируемое устройство, состоящее из пера, управляющего им механизма и листа бумаги. Управляющий пером механизм способен исполнять несколько команд. А именно: он может опустить перо на бумагу и вычертить прямой отрезок заданной длины в направлении текущей ориентации пера (команда F). Он может изменить ориентацию пера по отношению к текущей на какой-то заданный относительный угол по часовой или против часовой стрелки (команды + и -). Он может также запоминать (заносить в стек) свое текущее состояние (команда [) и вспоминать (извлекать из стека) ранее запомненное состояние (команда ]). Под состоянием в данном случае понимается тройка чисел (x, y, a), где x и y - это координаты пера и а - это угол, определяющий направление ориентации пера. Таким образом, задав некое начальное направление а0, определив относительный угол поворота в 900 и задав длину отрезка, при помощи последовательности команд F+F+ F+F мы можем нарисовать квадрат. Определив относительный угол поворота в 600, при помощи последовательности команд F++F++F можно нарисовать равносторонний треугольник.

Предположим также, что в программы для нашего виртуального устройства, кроме пяти перечисленных команд, можно включать любые другие символы, которые управляющий механизм будет просто игнорировать. То есть если мы введем программу F+BF+CCF+CF, то устройство все равно нарисует квадрат. Теперь мысленно оснастим наше устройство приставкой, которая перед тем, как передать введенную программу на управляющий механизм, может заданное число раз просматривать ее, и при каждом очередном просмотре заменять любые символы последовательности по предварительно указанным правилам. Исходную программную последовательность символов теперь будем называть аксиомой. Например, введем аксиому FB+, и определим правило B < F+FB. Зададим также количество просмотров, равное, например, двум. Тогда на входе механизма после обработки введенной аксиомы приставкой получим последовательность FF+FF+FB+. Вот, собственно, и все. При помощи описанного несложного виртуального устройства можно строить множество самых разнообразных фрактальных форм - от традиционных математических фракталов, таких, как, например, снежинка Коха или кривая Гильберта, до структур, очень напоминающих растительную или подводную жизнь. Можете посмотреть на исходный код программы, объясняющий вышесказанное

На рисунке приведено несколько примеров фрактальных структур, построенных при помощи этой программы

Рассмотрим, как кодируются L-системы в общепринятых обозначениях.
Движение вперед обозначается буквой F (Forward – вперед), поворот по часовой стрелке обозначим «+», а против – «-», причем само значение поворота задается в программе и постоянно для всех движений. Буквой В (Back– назад) обозначается возврат без прорисовки, нам это не пригодится.
Для нас важнее механизм возврата. Точка, в которую надо возвращаться, обозначим «[», а место, откуда происходит возврат, обозначим «]». Тогда вилка будет иметь вид: F – движение вперед [ – запомнить позицию + – поворот вправо на 22.5 (например) градусов F – движение вперед после поворота ] – возврат в запомненную позицию [ – запомнить позицию - – поворот влево относительно направления в запомненной точке F – движение вперед после поворота ] – возврат в запомненную позицию
Это движение можно закодировать. Можно и более сложное. Можно закодировать и следующий шаг – замену каждого прямого отрезка на такую же вилку. Два шага нарисуют три шага, три шага - четыре шага. Прорисовывать каждый шаг заменой текста программы довольно утомительно, и мы вспоминаем о рекурсии. Самое подходящее для нее место! Выполнив необходимые объявления переменных и передаче значений координат точек возврата, мы добиваемся, что любое дерево рисуется по заранее заданной формуле одной маленькой процедуркой, которая сама себя и вызывает. Скачайте пример на Visual Basic. Программа позволит вам с восхищением (ибо порядок прорисовки фрактально-непредсказуем) отслеживать на экране рост дерева.

Запустив программу, вы увидете как она нарисует ветку, клонимую ветром. Меняя переменную Kmax можно уменьшать или увеличивать глубину рекурсии, или, что тоже самое, «пушистость» ветки. А меняя закон движения можно получать самые удивительные и фантастические изображения.


Существуют и другие способы рисования фракталов

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






Также можете ознакомиться и с другими программами, рисующими фракталы
Генератор веток
Несколько видов фракталов
Фрактал Мандельброта
Еще один фрактал Мандельброта
Кривые Гилберта
Fractal Studio 0.17a
Использованные материалы
Реклама