Sierpiński-Kurve - Sierpiński curve

Sierpiński-Kurven sind eine rekursiv definierte Folge von von Wacław Sierpiński entdeckten fraktalen Kurven kontinuierlicher geschlossener Ebenen , die im Grenzfall das Einheitsquadrat vollständig ausfüllen. Daher ist ihre Grenzkurve , auch Sierpiński-Kurve genannt , ein Beispiel für eine raumfüllende Kurve . ${\ displaystyle n \ to \ infty}$

Da die Sierpiński-Kurve raumfüllend ist, beträgt ihre Hausdorff-Dimension (im Grenzbereich ) . Die euklidische Länge der ^ten Iteration Kurve ist ${\ displaystyle n \ to \ infty}$ ${\ displaystyle 2}$
${\ displaystyle n}$ ${\ displaystyle S_ {n}}$

{\ displaystyle l_ {n} = {2 \ over 3} (1 + {\ sqrt {2}}) 2 ^ {n} - {1 \ over 3} (2 - {\ sqrt {2}}) {1 \ over 2 ^ {n}},}

das heißt, es wächst exponentiell mit über jede Grenze, während die Grenze für die der Fläche umschlossen ist , dass der Platz (in der euklidischen Metrik). ${\ displaystyle n}$ ${\ displaystyle n \ to \ infty}$ ${\ displaystyle S_ {n}}$ ${\ displaystyle 5/12 \,}$

Sierpiński-Kurve ("Sierpinskis quadratische Schneeflocke") erster Ordnung

Sierpiński-Kurven der Ordnungen 1 und 2

Sierpiński-Kurven der Ordnungen 1 bis 3

Sierpinski "quadratische Kurve" der Ordnungen 2-4

Verwendung der Kurve

Die Sierpiński-Kurve ist in mehreren praktischen Anwendungen nützlich, da sie symmetrischer ist als andere häufig untersuchte raumfüllende Kurven. Beispielsweise wurde es als Grundlage für die schnelle Erstellung einer Näherungslösung für das Problem des Handlungsreisenden verwendet (bei der nach der kürzesten Folge eines bestimmten Satzes von Punkten gefragt wird): Die Heuristik besteht einfach darin, die Punkte in derselben Folge zu besuchen wie sie auf der Sierpiński-Kurve erscheinen. Dazu sind zwei Schritte erforderlich: Berechnen Sie zunächst ein inverses Bild jedes zu besuchenden Punkts. Sortieren Sie dann die Werte. Diese Idee wurde verwendet, um Routing-Systeme für Nutzfahrzeuge zu erstellen, die nur auf Rolodex-Kartendateien basieren.

Eine raumfüllende Kurve ist eine kontinuierliche Abbildung des Einheitsintervalls auf ein Einheitsquadrat, und daher bildet eine (Pseudo-) Inverse das Einheitsquadrat auf das Einheitsintervall ab. Eine Möglichkeit, eine Pseudo-Inverse zu konstruieren, ist wie folgt. Lassen Sie die untere linke Ecke (0, 0) des Einheitsquadrats 0,0 (und 1,0) entsprechen. Dann muss die obere linke Ecke (0, 1) 0,25 entsprechen, die obere rechte Ecke (1, 1) 0,50 und die untere rechte Ecke (1, 0) 0,75. Die inverse Karte der inneren Punkte wird unter Ausnutzung der rekursiven Struktur der Kurve berechnet. Hier ist eine in Java codierte Funktion, die die relative Position eines beliebigen Punkts auf der Sierpiński-Kurve berechnet (dh einen pseudo-inversen Wert). Als Eingabe werden die Koordinaten des zu invertierenden Punkts (x, y) und die Ecken eines umschließenden rechten gleichschenkligen Dreiecks (ax, ay), (bx, by) und (cx, cy) verwendet. (Beachten Sie, dass das Einheitsquadrat die Vereinigung zweier solcher Dreiecke ist.) Die verbleibenden Parameter geben den Genauigkeitsgrad an, mit dem die Inverse berechnet werden soll.

    static long sierp_pt2code( double ax, double ay, double bx, double by, double cx, double cy,
        int currentLevel, int maxLevel, long code, double x, double y ) 
    {
        if (currentLevel <= maxLevel) {
            currentLevel++;
            if ((sqr(x-ax) + sqr(y-ay)) < (sqr(x-cx) + sqr(y-cy))) {
                code = sierp_pt2code( ax, ay, (ax+cx)/2.0, (ay+cy)/2.0, bx, by,
                    currentLevel, maxLevel, 2 * code + 0, x, y );
            }
            else {
                code = sierp_pt2code( bx, by, (ax+cx)/2.0, (ay+cy)/2.0, cx, cy,
                    currentLevel, maxLevel, 2 * code + 1, x, y );
            }
        }
        return code;    
    }

Darstellung als Lindenmayer-System

Die Sierpiński-Kurve kann durch ein Umschreibesystem ( L-System ) ausgedrückt werden .

Alphabet : F, G, X.

Konstanten : F, G, +, -

Axiom : F - XF - F - XF

Produktionsregeln :

X → XF + G + XF - F - XF + G + X.

Winkel : 45

Hier bedeuten sowohl F als auch G "Vorwärts ziehen", + bedeutet "um 45 ° nach links drehen" und - bedeutet "um 45 ° nach rechts drehen" (siehe Schildkrötengrafiken ). Die Kurve wird normalerweise mit unterschiedlichen Längen für F und G gezeichnet.

Die Sierpiński-Quadratkurve kann ähnlich ausgedrückt werden:

Alphabet : F, X.

Konstanten : F, +, -

Axiom : F + XF + F + XF

Produktionsregeln :

X → XF - F + F - XF + F + XF - F + F - X.

Winkel : 90

Pfeilspitzenkurve

Die Sierpiński-Pfeilspitzenkurve ist eine fraktale Kurve, die im Aussehen ähnlich und in ihrer Grenze mit dem Sierpiński-Dreieck identisch ist .

Entwicklung der Sierpiński-Pfeilspitzenkurve

Die Sierpiński-Pfeilspitzenkurve zeichnet ein gleichseitiges Dreieck mit dreieckigen Löchern in gleichen Abständen. Es kann mit zwei ersetzenden Produktionsregeln beschrieben werden: (A → BAB) und (B → A + B + A). A und B wiederholen sich und machen unten dasselbe - ziehen Sie eine Linie. Plus und Minus (+ und -) bedeuten eine Drehung um 60 Grad nach links oder rechts. Der Endpunkt der Sierpiński-Pfeilspitzenkurve ist immer der gleiche, vorausgesetzt, Sie wiederholen eine gerade Anzahl von Malen und halbieren die Länge der Linie bei jeder Rekursion. Wenn Sie zu einer ungeraden Tiefe zurückkehren (Reihenfolge ist ungerade), werden Sie an einem anderen Punkt im Dreieck um 60 Grad gedreht.

Eine alternative Verengung wird in dem Artikel über die De-Rham-Kurve angegeben : Man verwendet dieselbe Technik wie die De-Rham-Kurven, aber anstatt eine binäre (Basis-2) Erweiterung zu verwenden, verwendet man eine ternäre (Basis-3) Erweiterung.

Code

In Anbetracht der Zeichenfunktionen void draw_line(double distance); und void turn(int angle_in_degrees); sieht der Code zum Zeichnen einer (ungefähren) Sierpiński-Pfeilspitzenkurve folgendermaßen aus:

void sierpinski_arrowhead_curve(unsigned order, double length)
{
    // If order is even we can just draw the curve.
    if ( 0 == (order & 1) ) {
        curve(order, length, +60);
    }
    else /* order is odd */ {
        turn( +60);
        curve(order, length, -60);
    }
}

void curve(unsigned order, double length, int angle)
{
    if ( 0 == order ) {
        draw_line(length);
    } else {
        curve(order - 1, length / 2, -angle);
        turn(angle);
        curve(order - 1, length / 2, angle);
        turn(angle);
        curve(order - 1, length / 2, -angle);
    }
}

Darstellung als Lindenmayer-System

Wie viele zweidimensionale fraktale Kurven kann die Sierpiński-Pfeilspitzenkurve auf drei Dimensionen erweitert werden

Die Sierpiński-Pfeilspitzenkurve kann durch ein Umschreibesystem ( L-System ) ausgedrückt werden .

Alphabet : X, Y.

Konstanten : F, +, -

Axiom : XF

Produktionsregeln :

X → YF + XF + Y.

Y → XF - YF - X.

Hier bedeutet F "vorwärts ziehen", + "60 ° nach links drehen" und - "60 ° nach rechts drehen" (siehe Schildkrötengrafiken ).

Siehe auch

Verweise

Weiterführende Literatur

Peitgen, H.-O.; Jürgens, H.; Saupe, D. (2013) [1992]. Chaos und Fraktale: Neue Grenzen der Wissenschaft . Springer. ISBN 978-1-4757-4740-9 .
Stevens, Roger T. (1989). Fractal Programmieren in C . M & T Bücher. ISBN 9781558510371 .

Languages

In other projects

Sierpiński-Kurve - Sierpiński curve

Inhalt

Verwendung der Kurve

Darstellung als Lindenmayer-System

Pfeilspitzenkurve

Code

Darstellung als Lindenmayer-System

Siehe auch

Verweise

Weiterführende Literatur