Драконова ломаная
Драконова ломаная относится к классу самоподобных рекурсивно порождаемых геометрических структур. Ломаная нулевого порядка представляет собой просто прямой угол. Изображение фигуры каждого следующего порядка строится путем рекурсивных замен каждого из отрезков фигуры младшего порядка на два отрезка, сложенных также в виде прямого угла.
При этом каждый первый угол оказывается "вывернутым" наружу, а каждый второй - вовнутрь. Несмотря на внешнюю простоту, построение драконовой ломаной - увлекательная алгоритмическая задачка, решение которой может потребовать от вас определенных мыслительных усилий. Попробуйте "научить" ваш компьютер строить драконовы ломаные 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
Использованные материалы
- http://sakva.net/fractals_rus/
- Гарри Корнелл "Программирование в среде Visual Basic 5"
Реклама
На первом шаге он брал прямую линию и заменял ее на 9 отрезков длинной в 3 раза меньшей, чем длинна исходной линии (Часть 1 и 2 рисунка 1). Далее он делал то же самое с каждым отрезком получившейся линии. И так до бесконечности. Ее уникальность в том, что она заполняет всю плоскость. Доказано, что для каждой точки на плоскости можно найти точку, принадлежащую линии Пеано. Кривая Пеано и пыль Кантора выходили за рамки обычных геометрических объектов. Они не имели четкой размерности. Пыль Кантора строилась вроде бы на основании одномерной прямой, но состояла из точек (размерность 0). А кривая Пеано строилась на основании одномерной линии, а в результате получалась плоскость.Вплоть до 20 века шло накопление данных о таких странных объектах, без какой либо попытки их систематизировать. Так было, пока за них не взялся Бенуа Р. Мандельброт (Benoit Mandelbrot), математик из Исследовательского центра им. Томаса Уотстона при IBM - отец современной фрактальной геометрии, который и предложил термин "фрактал" для описания объектов, структура которых повторяется при переходе к все более мелким масштабам.. Работая в IBM математическим аналитиком, он изучал шумы в электронных схемах, которые невозможно было описать с помощью статистики. Постепенно сопоставив факты, он пришел к открытию нового направления в математике - фрактальной геометрии.
Из этих геометрических фракталов очень интересным и довольно знаменитым является первый - снежинка Коха. Строится она на основе равностороннего треугольника. Каждая линия которого ___ заменяется на 4 линии каждая длинной в 1/3 исходной _/\_. Таким образом, с каждой итерацией длинна кривой увеличивается на треть. И если мы сделаем бесконечное число итераций - получим фрактал - снежинку Коха бесконечной длинны. Получается, что наша бесконечная кривая покрывает ограниченную площадь. Попробуйте сделать то же самое методами и фигурами из евклидовой геометрии. Для построения геометрических фракталов хорошо приспособлены так называемые L-Systems. Суть этих систем состоит в том, что имеется определенных набор символов системы, каждый из которых обозначает определенное действие и набор правил преобразования символов. 
Второе свойство фракталов - самоподобие. Возьмем, например, треугольник Серпинского. Для его построения из центра треугольника мысленно вырежем кусок треугольной формы, который своими вершинами будет упираться в середины сторон исходного треугольника. Повторим эту же процедуру для трех образовавшихся треугольников (за исключением центрального) и так до бесконечности. Если мы теперь возьмем любой из образовавшихся треугольников и увеличим его - получим точную копию целого. В данном случае мы имеем дело с полным самоподобием.