Как запрограммировать фрактал?

https://stackoverflow.com/questions/425953

06-07-2019
|

Вопрос

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

Можете ли вы предоставить мне простые алгоритмы для фракталов?

Язык программирования на самом деле не имеет значения, но я больше всего знаком с actionscript, C #, Java.

Я знаю, что если я загуглю фракталы, то получу много (сложной) информации, но я хотел бы начать с простого алгоритма и поиграть с ним.

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

Решение

Программирование Мандельброта очень просто.
Ниже приведен мой быстрый код (не обязательно без ошибок, но с хорошей схемой).

Вот схема: Множество Мандельброта лежит в комплексной сетке полностью внутри круга с радиусом 2.

Итак, начните с сканирования каждой точки в этой прямоугольной области. Каждая точка представляет комплексное число (x + yi). Выполните итерацию этого комплексного числа:

[новое значение] = [старое значение] ^ 2 + [оригинальное значение] , отслеживая две вещи:

1.) количество итераций

2.) расстояние [нового значения] от источника.

Если вы достигли максимального количества итераций, все готово. Если расстояние от начала координат больше 2, все готово.

Когда закончите, раскрасьте оригинальный пиксель в зависимости от количества выполненных вами итераций. Затем перейдите к следующему пикселю.

    public void MBrot()
    {
        float epsilon = 0.0001; // The step size across the X and Y axis
        float x;
        float y;
        int maxIterations = 10; // increasing this will give you a more detailed fractal
        int maxColors = 256; // Change as appropriate for your display.

        Complex Z;
        Complex C;
        int iterations;
        for(x=-2; x<=2; x+= epsilon)
        {
            for(y=-2; y<=2; y+= epsilon)
            {
                iterations = 0;
                C = new Complex(x, y);
                Z = new Complex(0,0);
                while(Complex.Abs(Z) < 2 && iterations < maxIterations)
                {
                    Z = Z*Z + C;
                    iterations++;
                }
                Screen.Plot(x,y, iterations % maxColors); // depending on the number of iterations, color a pixel.
            }
        }
    }

Остались некоторые детали:

1.) Узнайте, что такое квадрат комплексного числа и как его вычислить.

2.) Узнайте, как перевести (-2,2) прямоугольную область в экранные координаты.

Другие советы

Вам действительно следует начать с Множество Мандельброта, и понять, что это такое на самом деле.

Идея, стоящая за этим, относительно проста.Вы начинаете с функции комплексной переменной

f (z) = z² + C

где z - сложный переменная а C - это сложный постоянный.Теперь вы повторяете его, начиная с z = 0, т.е.вы вычисляете z₁ = f(0), z₂ = f(z₁), z₃ = f(z₂) и так далее.Множество тех констант C , для которых последовательность z₁, z₂, z₃, ...является ограниченный, т. е.оно не уходит в бесконечность, это множество Мандельброта (черное множество на рисунке на странице Википедии).

На практике, чтобы нарисовать множество Мандельброта, вы должны:

Выберите прямоугольник в комплексной плоскости (скажем, из точки -2-2i в точку 2+2i).
Покройте прямоугольник подходящей прямоугольной сеткой точек (скажем, 400x400 точек), которая будет сопоставлена пикселям на вашем мониторе.
Для каждой точки / пикселя, пусть C - эта точка, вычислите, скажем, 20 членов соответствующей итерационной последовательности z₁, z₂, z₃, ...и проверьте, не "уходит ли она в бесконечность".На практике вы можете проверить во время итерации, больше ли абсолютное значение одного из 20 терминов, чем 2 (если одно из условий больше, последующие термины гарантированно будут неограниченными).Если какое-то значение z_k выполняется, последовательность "уходит в бесконечность".;в противном случае вы можете рассматривать его как ограниченный.
Если последовательность, соответствующая определенной точке C, ограничена, нарисуйте соответствующий пиксель на картинке черным цветом (поскольку он принадлежит множеству Мандельброта).В противном случае нарисуйте его другим цветом.Если вы хотите повеселиться и создать красивые сюжеты, нарисуйте их разными цветами в зависимости от величины абс (20-й член).

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

Наслаждайтесь!

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

Сначала тебе нужна черепаха. Вперед, Назад, Влево, Вправо, Pen-Up, Pen-Down. Есть много забавных форм, которые можно сделать с помощью графики черепах, используя геометрию черепах, даже без L-системы. Поиск "графика ЛОГОТИП" " или "Графика черепахи". Полная LOGO система фактически является среда программирования Lisp с использованием неперемещенных скобок Синтаксис Cambridge Polish . Но вам не нужно заходить так далеко, чтобы получить красивые картинки, используя концепцию черепахи.

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

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

ps l-system pythagoras tree luser-droog

Существует замечательная книга Chaos and Fractals , в которой есть простой пример кода в конце каждой главы, которая реализует какой-то фрактал или другой пример. Давным-давно, когда я читал эту книгу, я конвертировал каждую программу-пример (на некотором базовом диалекте) в Java-апплет, работающий на веб-странице. Апплеты находятся здесь: http://hewgill.com/chaos-and-fractals/

Один из примеров - простая реализация Мандельброта.

Еще один отличный фрактал для изучения - это фрактал Серпинского треугольника.

По сути, нарисуйте три угла треугольника (предпочтительнее равносторонний, но любой треугольник будет работать), затем начните точку P в одном из этих углов. Переместите P на полпути к любому из 3 углов наугад и нарисуйте точку там. Снова переместите P на полпути к любому случайному углу, нарисуйте и повторите.

Можно подумать, что случайное движение приведет к случайному результату, но на самом деле это не так.

Ссылка: http://en.wikipedia.org/wiki/Sierpinski_triangle

Треугольник Серпинского и кривая Коха являются особыми типами фракталов пламени. Пламя фракталов - это очень обобщенный тип системы итерированных функций, поскольку она использует нелинейные функции.

Алгоритм IFS: es заключается в следующем:

Начните со случайной точки.

Повторите следующее много раз (не менее миллиона, в зависимости от конечного размера изображения):

<код> Примените одно из N предопределенных преобразований (матричные преобразования или аналогичные) к точке. Примером может служить умножение каждой координаты на 0,5. Нарисуйте новую точку на экране.

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

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

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

Что-то очень простое, например, взять 2 точки (линию) и добавить 3-ю точку (сделать угол), а затем повторить каждый созданный новый раздел.

fractal(p0, p1){
    Pmid = midpoint(p0,p1) + moved some distance perpendicular to p0 or p1;
    fractal(p0,Pmid);
    fractal(Pmid, p1);
}

Я думаю, что вы можете не рассматривать фракталы как алгоритм или что-то для программирования. Фракталы это концепция! Это математическая концепция повторения подробного паттерна.

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

введите описание изображения здесь

Выберите подход, а затем выясните, как его реализовать. Эти четыре примера были реализованы с использованием Marvin Framework . Исходные коды доступны

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

Псевдокод:

MAX_COUNT = 64 // if we haven't escaped to infinity after 64 iterations, 
               // then we're inside the mandelbrot set!!!

foreach (x-pixel)
  foreach (y-pixel)
    calculate x,y as mathematical coordinates from your pixel coordinates
    value = (x, y)
    count = 0
    while value.absolutevalue < 1 billion and count < MAX_COUNT
        value = value * value + (x, y)
        count = count + 1

    // the following should really be one statement, but I split it for clarity
    if count == MAX_COUNT 
        pixel_at (x-pixel, y-pixel) = BLACK
    else 
        pixel_at (x-pixel, y-pixel) = colors[count] // some color map.

Примечания:

значение - это комплексное число.комплексное число (a+bi) возведено в квадрат, чтобы дать (aa-b*b+2*abя).Вам придется использовать сложный тип или включить это вычисление в свой цикл.

Вот простой и понятный код на Java для Мандельброта и других фрактальных примеров.

http://code.google.com/p/gaima/wiki/VLFImages

Просто скачайте BuildFractal.jar, чтобы протестировать его на Java, и запустите с помощью команды:

java -Xmx1500M -jar BuildFractal.jar 1000 1000 по умолчанию MANDELBROT

Исходный код также можно бесплатно загружать / исследовать / редактировать / расширять.

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

http://flam3.com/flame_draves.pdf

Люди выше используют поиск средних точек для Серпинского и Коха, я бы гораздо больше рекомендовал копировать фигуры, масштабировать их, а затем переводить их для достижения «фрактала». эффект. Псевдокод в Java для sierpinski будет выглядеть примерно так:

public ShapeObject transform(ShapeObject originalCurve)
    {
        Make a copy of the original curve
        Scale x and y to half of the original
        make a copy of the copied shape, and translate it to the right so it touches the first copied shape
        make a third shape that is a copy of the first copy, and translate it halfway between the first and second shape,and translate it up
        Group the 3 new shapes into one
        return the new shape
    }

Иногда я программирую фракталы для удовольствия и как вызов. Вы можете найти их здесь . Код написан на Javascript с использованием библиотеки P5.js и может быть прочитан непосредственно из исходного кода HTML.

Для тех, кого я видел, алгоритмы довольно просты, просто найдите основной элемент и повторяйте его снова и снова. Я делаю это с помощью рекурсивных функций, но это можно сделать по-другому.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow