Как запрограммировать фрактал? - PullRequest
70 голосов
/ 09 января 2009

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

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

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

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

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

Ответы [ 13 ]

53 голосов
/ 09 января 2009

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

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

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

[new value] = [old-value]^2 + [original-value], отслеживая две вещи:

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) прямоугольную область в экранные координаты.

26 голосов
/ 09 января 2009

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

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

f (z) = z 2 + C

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

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

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

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

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

9 голосов
/ 19 сентября 2012

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

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

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

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

ps l-system pythagoras tree luser-droog

8 голосов
/ 09 января 2009

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

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

6 голосов
/ 07 августа 2009

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

Алгоритм IFS: es следующий:

Start with a random point.

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

Apply one of N predefined transformations (matrix transformations or similar) to the point. An example would be that multiply each coordinate with 0.5. Plot the new point on the screen.

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

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

6 голосов
/ 09 января 2009

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

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

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

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

5 голосов
/ 09 января 2009

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

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

fractal(p0, p1){
    Pmid = midpoint(p0,p1) + moved some distance perpendicular to p0 or p1;
    fractal(p0,Pmid);
    fractal(Pmid, p1);
}
4 голосов
/ 28 сентября 2013

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

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

enter image description here

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

3 голосов
/ 23 ноября 2010

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

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

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

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

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

3 голосов
/ 09 января 2009

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

псевдокод:

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 + b i) возводится в квадрат, чтобы дать (a a-b * b + 2 * a b i). Вам придется использовать сложный тип или включить это вычисление в свой цикл.

...