Fraktale Nacht

    Es war bereits die letzte Stunde dieses Sonntags, ich dachte bereits daran, ins Bett zu gehen, aber ein guter Sourcerer schickte mir ein Bild von meinem verlassenen Standort, das unten zu sehen ist, und den Text „Schön!“. Diese Bilder habe ich vor etwa fünf Jahren mit dem sogenannten gemalt. Runaway-Algorithmus, aber für die Anwendbarkeit dieses Algorithmus müssen Sie in der Lage sein, die Ebene für eine bestimmte Menge von Transformationen in Regionen aufzuteilen. Ich habe dann nicht herausgefunden, wie dies zu tun ist, und bin nicht zu diesem Algorithmus zurückgekehrt. Aber jetzt habe ich sofort herausgefunden, was zu tun ist, und schrieb an Dima: „Zuerst zufälliges IFS, dann kNN und dann Escape-Time-Algorithmus!“



    Zur Hand hatte ich nur ein altes Netbook, das mir meine Freunde eine Weile geschenkt hatten, als mein Laptop repariert wurde. Dima hat mir immer noch etwas erzählt, ich habe etwas geantwortet, aber ich habe bereits Code in meinen Kopf geschrieben und im Netbook nach mindestens einem Compiler oder Interpreter gesucht und C ++ Builder 6 gefunden! Danach wurde mir klar, dass ich mich am Morgen privat mit dem Borland-Compiler treffen würde. Fünf Stunden später schickte ich Dima neue Bilder, aber er hat als normaler Mensch lange geschlafen ...





    Also, ein bisschen Formeln. Stellen Sie sich vor, wir haben eine endliche Menge von Transformationen der Ebene T i : R 2R 2 , i = 1, ..., k . Für eine beliebige Menge E definieren wir T ( E) = T 1 ( E ) ≤ ... ≤ T k ( E ), d. H. Wir wirken auf jeden Satz auf den Satz E ein und kombinieren die Ergebnisse. Es kann bewiesen werden , dass , wenn die Mappings T i komprimiert wurden, dann ist die Sequenz E , T ( E ), T ( T ( E )), ... konvergierend zu einer Vielzahl von F für alle nicht leeren kompakten E . Diese Konstruktion ist als ein System iterabler Funktionen bekannt .

    Wenn Sie beispielsweise ein Emoticon als einen nicht leeren Compact betrachten und drei Transformationen betrachten, von denen jede eine Komprimierungs- und Verschiebungskomposition zum i-ten Scheitelpunkt eines regulären Dreiecks ist, sehen die ersten Iterationen so aus, und im Grenzfall erhalten wir das Sierpinski-Dreieck:



    Normalerweise anstatt die Sequenz direkt zu berechnen E , T ( E ), T ( T ( E )), ... genannt. "Spiel des Chaos" , das wie folgt lautet. Wir wählen einen beliebigen Punkt z 0 auf der Ebene, dann wählen wir zufällig die Transformation T i 1und berechne z 1 = T i 1 ( z 0 ), wähle dann wiederum zufällig T i 2 und berechne z 1 = T i 2 ( z 0 ) usw. Es kann gezeigt werden, dass alles in Ordnung ist und die Menge der Punkte erhalten wird in gewissem Sinne wird die oben definierte Menge F angenähert . Ich werde diesen Algorithmus im Folgenden als Zufalls-IFS bezeichnen.

    z = (0, 0)
    for (i = 0; i < maxIterNum; ++i) {
        cl = random([p1, ..., pk]) // pi -- вероятность, с которой выбираем преобразование Ti.
        z = T[cl](z)
        if (i > skipIterNum) { // Первых несколько итераций могут быть достаточно далеко от аттрактора.
            draw(z)
        }
    }
    




    Jetzt ist die Zeit gekommen, um den außer Kontrolle geratenen Algorithmus zu beschreiben. Angenommen, wir haben zuerst eine Transformation der Ebene f . Für jeden Punkt z - Ebene beginnen , um eine Sequenz zu berechnen , f ( z ) f ( f ( z )), f ( f ( f ( z ))), ... , bis entweder die Anzahl der Iterationen eine vorbestimmte Anzahl überschreitet N , oder bis der Rate von die Zahl z größer als eine bestimmte Anzahl von Bed and . Danach wählen Sie die Farbe des Punktes entsprechend der Anzahl der durchgeführten Iterationen.

    for (y = y1; y < y2; y += dy) {
        for (x = x1; x < x2; x += dx) {
            z = (x, y);
            iter = 0;
            while (iter < N && ||z|| < B) {
                 z = f(z)
                 iter += 1;
            }
            drawPixel((x, y), color(iter))
        }
    }
    

    Wenn wir uns für eine Weile vorstellen, dass unsere Ebene komplex ist und die Transformation f ( z ) gleich z 2 + c ist , erhalten wir als Ergebnis der Operation dieses Algorithmus eine Julia-Fraktalmenge . Weitere Informationen hierzu finden Sie in habrastate zu lesen „ Der Aufbau eines Julia - Menge“ habrapolzovatelya mephistopheies .



    Angenommen, wir haben ein System iterabler Funktionen, das durch eine Reihe reversibler Drucktransformationen der Ebene T 1 , ..., T k definiert ist . Sei F ein Attraktor dieses Systems.

    Nehmen wir zusätzlich an, dass die Menge Fkann so zerlegt werden, dass T i ( F ) ∩ T j ( F ) = ∅, i ! = j (diese Annahme ist bei weitem nicht immer erfüllt). Wir teilen die gesamte Ebene R 2 in Teile A 1 , ...., A k, so dass T i ( F ) eine Teilmenge von A i für alle i ist . Nun definieren wir die Funktion f ( z ) stückweise: auf der Menge A setze ich f ( z ) =T k - 1 ( z ) für alle i .

    Zum Beispiel betrachten wir für das Sierpinski-Dreieck eine solche Unterteilung (es gibt kleinere Probleme mit drei Punkten, aber wir schließen unsere Augen vor ihnen).



    Und nun ist die Hauptfrage, was passiert, wenn der Ablaufzeitalgorithmus auf die auf diese Weise konstruierte Funktion f angewendet wird ?

    Mal sehen:



    Es ist ein hübsches Sierpinski-Dreieck geworden!

    Es stellt sich heraus, dass dies kein Unfall ist. Noch ein paar Beispiele:





    In diesen Beispielen ist es nicht schwierig, die entsprechende Ebenenaufteilung unter Verwendung von Booleschen Kombinationen von Kreisen und Halbebenen unter Verwendung der Methode des engen Peerings analytisch zu bestimmen. Aber oft sind einfache Zustände nicht zu erraten. Anstatt zu raten, bringen wir dem Computer daher bei, die Partition selbst zu bestimmen. Die Methode des nächsten Nachbarn hilft uns dabei .

    Zunächst erzeugen wir mit Hilfe von Random IFS mehrere tausend Punkte, während wir uns für jeden Punkt die Transformationsnummer merken, mit der er erhalten wurde. Während Sie EscapeTimeAlgorithm für jedes Pixel ausführen, bestimmen Sie den Bereich, in den es fällt, mit 1NN.

    Beispielsweise ergibt 1NN für einen solchen Stern die folgende Aufteilung in vier Teile: Wenn man ihn



    zusammensetzt, erhält man:

    points = RandomIFS(Ts)
    classifier = kNN(points);
    for (y = y1; y < y2; y += dy) {
        for (x = x1; x < x2; x += dx) {
            z = (x, y)
            iter = 0
            while (iter < maxIterNum && ||z|| < sqrdBound) {
                cl = classifier.getClass(z);
                z = T[cl].applyInvert(z);
                iter += 1;
            }
            draw((x, y), color(iter))
        }
    }
    



    Noch ein paar Bilder.









    Das ist alles. Zum Schluss noch zwei Kommentare.

    Erstens mag sich der aufmerksame Leser gefragt haben, ob Fraktale, die mit Random IFS erstellt wurden, mit dem Laufzeitalgorithmus erstellt werden können. Ist es möglich, eine Julia-Menge mit Random IFS zu erstellen? Es stellt sich heraus, dass Sie nur die Abbildung f ( z ) = z 2 + c umkehren müssen, indem Sie sich daran erinnern, wie Sie die Wurzel aus der komplexen Zahl ziehen. (Richtig, wenn Sie diese Methode anwenden, um Bilder der Julia-Menge zu konstruieren, treten große Schwierigkeiten auf.)

    x = z0.re
    y = z0.im
    for (i = 0; i < N; ++i) {
        x -= c.re;
        y -= c.im;
        len = sqrt(x*x + y*y);
        ang = atan2(y, x);
        if (rand() % 2 == 0) { // Тут нужно что-нибудь и поинтереснее.
            x = sqrt(len) * cos(ang / 2);
            y = sqrt(len) * sin(ang / 2);
        } else {
            x = sqrt(len) * cos(ang / 2 + M_PI);
            y = sqrt(len) * sin(ang / 2 + M_PI);
        }
        draw(x, y)
    }
    



    Zweitens beschreibt der Artikel, was passiert, und wenn Sie herausfinden möchten, warum dies passiert, empfehle ich M. Barnsleys Buch „Fractals Everywere“.

    (Momente des Quellcodes sind auf dem Github zu finden .)

    Jetzt auch beliebt: