Dračí křivka - Dragon curve

Animace iterací dračí křivky Heighway

A dračí křivka je kterýkoli člen rodiny podobný fraktální křivky, kterou lze aproximovat pomocí rekurzivní metody jako Systémy Lindenmayer. Dračí křivka je pravděpodobně nejčastěji považována za tvar, který je generován opakovaným skládáním proužku papíru na polovinu, i když existují další křivky, které se nazývají dračí křivky a které se generují odlišně.

Dráha na dálnici

Křivka dračí dálnice

The Dráha na dálnici (také známý jako Harter – Heighway drak nebo Drak Jurského parku) byl poprvé vyšetřován NASA fyzici John Heighway, Bruce Banks a William Harter. Popsal to Martin Gardner v jeho Scientific American sloupec Matematické hry v roce 1967. Mnoho z jeho vlastností bylo poprvé publikováno Chandler Davis a Donald Knuth.^[1] Objevilo se to na titulních stránkách sekce Michael Crichton román Jurský park.

Konstrukce

Rekurzivní konstrukce křivky

Rekurzivní konstrukce křivky

Lze jej zapsat jako Systém Lindenmayer s

• úhel 90 °
• počáteční řetězec FX
• pravidla přepisování řetězců
  • X ↦ X+YF+
  • Y ↦ −FX−Y.

To lze popsat takto: počínaje od základního segmentu nahraďte každý segment 2 segmenty s pravým úhlem a rotací o 45 ° alternativně doprava a doleva:

Dráha na dálnici je také limitem pro následující iterovaný funkční systém v komplexní rovině:

${ displaystyle f_ {1} (z) = { frac {(1 + i) z} {2}}}$

${ displaystyle f_ {2} (z) = 1 - { frac {(1-i) z} {2}}}$

s počáteční sadou bodů ${ displaystyle S_ {0} = {0,1 }}$.

Místo toho použijeme dvojice reálných čísel, což je stejné jako u dvou funkcí, z nichž se skládá

${ displaystyle f_ {1} (x, y) = { frac {1} { sqrt {2}}} { begin {pmatrix} cos 45 ^ { circ} & - sin 45 ^ { circ } sin 45 ^ { circ} & cos 45 ^ { circ} end {pmatrix}} { begin {pmatrix} x y end {pmatrix}}}$

${ displaystyle f_ {2} (x, y) = { frac {1} { sqrt {2}}} { begin {pmatrix} cos 135 ^ { circ} & - sin 135 ^ { circ } sin 135 ^ { circ} & cos 135 ^ { circ} end {pmatrix}} { begin {pmatrix} x y end {pmatrix}} + { begin {pmatrix} 1 0 end {pmatrix}}}$

Tato reprezentace se běžněji používá v softwaru, jako je Apofýza.

Dráhu křivky lze snáze vidět s každou zakřivenou zatáčkou

[Un] skládání draka

Při sledování iterace dračí křivky Heighway z jednoho konce na druhý narazíte na sérii 90stupňových zatáček, některé vpravo a některé vlevo. U prvních několika iterací je sekvence zatáček vpravo (R) a doleva (L) následující:

1. iterace: R

2. iterace: R R L

3. iterace: R R L R R L L

4. iterace: R R L R R L L R R R L L R L L.

To naznačuje několik různých vzorů. Nejprve je každá iterace vytvořena převzetím předchozího a přidáním střídavých práv a levice mezi každé písmeno. Zadruhé také navrhuje následující vzorec: každá iterace je vytvořena převzetím předchozí iterace, přidáním R na konci a následným převzetím původní iterace, převrácením zpětně, zaměněním každého písmene a přidáním výsledku za R. Due vzhledem k sebepodobnosti vystavené drakem Heighway to efektivně znamená, že každá následující iterace přidá kopii poslední iterace otočené proti směru hodinových ručiček k fraktálu.

Tento vzor zase navrhuje následující metodu vytváření modelů iterací dračí křivky Heighway pomocí skládání proužku papíru. Vezměte proužek papíru a přeložte jej na polovinu doprava. Přeložte jej znovu na polovinu doprava. Pokud by byl proužek nyní otevřen, při ohýbání každého záhybu, aby se stal otočením o 90 stupňů, by sekvence otočení byla RRL, tj. Druhá iterace draka Heighway. Přeložte proužek znovu na polovinu doprava a pořadí otáčení rozloženého proužku je nyní RRLRRLL - třetí iterace draka na dálnici. Pokračováním ve skládání pruhu na polovinu doprava k vytvoření dalších iterací draka Heighway (v praxi je pás příliš silný na to, aby se po čtyřech nebo pěti iteracích ostře složil).

Tuto rozkládací metodu lze vidět výpočtem řady iterací (pro animaci vpravo bylo použito 13 iterací) křivky pomocí výše popsané metody „swapování“, ale řízení úhlů pro správné zatáčky a negování předchozích úhlů.

Tento vzor také poskytuje metodu pro určení směru nth turn in the turn sequence of a Heighway dragon iteration. Nejprve vyjádřit n ve formě k2^m, kde k je liché číslo. Směr ntah je určen k mod 4, tj. zbytek zbývá, když k se dělí 4. Pokud k mod 4 je 1, pak ntým je R; -li k mod 4 je 3, pak nje tah L.

Například pro určení směru otáčení 76376:

76376 = 9547 × 8,

9547 = 2386×4 + 3,

takže 9547 mod 4 = 3,

76376 je tedy L.

Existuje jednoduchá jednorázová nerekurzivní metoda implementace výše uvedeného k mod 4 metoda nalezení směru otáčení v kódu. Ošetřující tah n jako binární číslo vypočítejte následující booleovský hodnota:

bool turn = ((((n & −n) << 1) & n)! = 0;

• „n & −n“ ponechává pouze jeden bit jako „1“, úplně „1“ v binární expanzi n;
• „<< 1“ posune tento bit do levé polohy;
• "& n" ponechává buď tento jediný bit (pokud k mod 4 = 3), nebo nula (pokud k mod 4 = 1);
• takže „bool turn = ((((n & −n) << 1) & n)! = 0) je PRAVDA, pokud ntah je L a je FALSE, pokud nna řadě je R.

Metoda šedého kódu

Dalším způsobem řešení je redukce výše uvedeného algoritmu. Použitím Šedý kód, počínaje od nuly, určete změnu na další hodnotu. Pokud je změna 1, pak zahněte doleva a pokud je 0, pak zahněte doprava. Vzhledem k binárnímu vstupu B je odpovídající šedý kód G dán „G = B XOR (B >> 1)“. Použitím G_i a G_i−1, otočit se rovná "(ne G_i) A G_i−1".

• G = B ^ (B >> 1) získá z binárního kódu šedý kód.
• T = (~ G0) & G1: je-li T stejné, pak se 0 otočí ve směru hodinových ručiček, jinak se otočí proti směru hodinových ručiček.

Kód

Jiný přístup k generování tohoto fraktálu lze vytvořit pomocí rekurzivní funkce a těchto Želví grafika funkce drawLine (vzdálenost) a turn (angleInDegrees).Pythonovský kód pro nakreslení (přibližné) dračí křivky Heighway by vypadal takto.

def dragon_curve(objednat: int, délka) -> Žádný:    "" "Nakreslete dračí křivku." ""    otáčet se(objednat * 45)    dragon_curve_recursive(objednat, délka, 1)def dragon_curve_recursive(objednat: int, délka, podepsat) -> Žádný:    -li objednat == 0:        drawLine(délka)    jiný:        rootPůl = (1 / 2) ** (1 / 2)        dragon_curve_recursive(objednat - 1, délka * rootPůl, 1)        otáčet se(podepsat * -90)        dragon_curve_recursive(objednat - 1, délka * rootPůl, -1)

Rozměry

• Navzdory svému podivnému aspektu má dračí křivka Heighway jednoduché rozměry. Všimněte si, že rozměry 1 a 1,5 jsou limity a nikoli skutečné hodnoty.

• Své povrch je také docela jednoduché: Pokud se počáteční segment rovná 1, pak se jeho povrch rovná ${ displaystyle textstyle { frac {1} {2}}}$. Tento výsledek pochází z jeho dlažebních vlastností.
• Křivka se nikdy neprotíná sama.
• Mnoho sebe-podobnosti je vidět na dračí křivce Heighway. Nejviditelnější je opakování stejného vzoru nakloněného o 45 ° as redukčním poměrem ${ displaystyle textstyle { sqrt {2}}}$.

• Své fraktální dimenze lze vypočítat: ${ displaystyle textstyle {{ frac { ln 2} { ln { sqrt {2}}}} = 2}}$. Díky tomu je křivka vyplňování prostoru.
• Své hranice má nekonečnou délku, protože každou iterací se zvyšuje o podobný faktor.
• Fraktální rozměr jeho hranice byl numericky aproximován Changem a Zhangem.^[2]).

Ve skutečnosti jej lze najít analyticky:^[3]${ displaystyle log _ {2} left ({ frac {1 + { sqrt [{3}] {73-6 { sqrt {87}}}} + { sqrt [{3}] {73 +6 { sqrt {87}}}}} {3}} vpravo) přibližně 1,523627086202492.}$ Toto je kořen rovnice ${ displaystyle textstyle {4 ^ {x} (2 ^ {x} -1) = 4 (2 ^ {x} +1).}}$

Obklady

Křivka draka může obkládat letadlo mnoha způsoby.

Twindragon

The Twindragon (také známý jako Davis-Knuth drak) lze zkonstruovat umístěním dvou dračích křivek Heighway zády k sobě. Je to také sada limitů následujícího iterovaného funkčního systému:

${ displaystyle f_ {1} (z) = { frac {(1 + i) z} {2}}}$

${ displaystyle f_ {2} (z) = 1 - { frac {(1 + i) z} {2}}}$

kde počáteční tvar je definován následující sadou ${ displaystyle S_ {0} = {0,1,1-i }}$.

Lze jej také zapsat jako Systém Lindenmayer - pouze potřebuje přidat další sekci do počátečního řetězce:

• úhel 90 °
• počáteční řetězec FX + FX +
• pravidla přepisování řetězců
  • X ↦ X+YF
  • Y ↦ FX−Y.

Twindragonova křivka.

Twindragonova křivka sestrojená ze dvou draků na dálnici.

Terdragon

Terdragonova křivka.

The terdragon lze psát jako Systém Lindenmayer:

• úhel 120 °
• počáteční řetězec F
• pravidla přepisování řetězců
  • F ↦ F + F - F.

Je to sada limitů následujícího iterovaného funkčního systému:

${ displaystyle f_ {1} (z) = lambda z}$

${ displaystyle f_ {2} (z) = { frac {i} { sqrt {3}}} z + lambda}$

${ displaystyle f_ {3} (z) = lambda z + lambda ^ {*}}$

${ displaystyle { mbox {where}} lambda = { frac {1} {2}} - { frac {i} {2 { sqrt {3}}}} { text {and}} lambda ^ {*} = { frac {1} {2}} + { frac {i} {2 { sqrt {3}}}}.}$

Lévy drak

The Křivka Lévy C. je někdy známý jako Lévy drak.^[4]

Křivka Lévy C.

Varianty

Je možné změnit úhel otočení z 90 ° na jiné úhly. Změna na 120 ° poskytuje strukturu trojúhelníků, zatímco 60 ° dává následující křivku:

Dračí křivka, 60 ° varianta. Self-podobnost je jasně viditelný.

Diskrétní dračí křivku lze převést na draka polyomino Stejně jako diskrétní dračí křivky se dračí polyomino blíží fraktální dračí křivce jako limit.

Dragon Polyomino

Výskyt dračí křivky v sadách řešení

Po získání sady řešení lineární diferenciální rovnice bude jakákoli lineární kombinace řešení kvůli princip superpozice, dodržujte také původní rovnici. Jinými slovy, nová řešení se získají aplikací funkce na sadu stávajících řešení. To je podobné tomu, jak iterovaný funkční systém produkuje nové body v sadě, i když ne všechny IFS jsou lineární funkce. V koncepčně podobném duchu je sada Littlewood polynomials k nim lze dosáhnout takovými iterovanými aplikacemi sady funkcí.

Littlewoodův polynom je polynom: ${ displaystyle p (x) = součet _ {i = 0} ^ {n} a_ {i} x ^ {i} ,}$ kde všichni ${ displaystyle a_ {i} = pm 1}$.

Pro některé ${ displaystyle | w | <1}$ definujeme následující funkce:

${ displaystyle f _ {+} (z) = 1 + wz}$

${ displaystyle f _ {-} (z) = 1-wz}$

Počínaje z = 0 můžeme pomocí těchto funkcí vygenerovat všechny Littlewoodovy polynomy stupně d iterativně d + 1 krát.^[5] Například: ${ displaystyle f _ {+} (f _ {-} (f _ {-} (0))) = 1+ (1-w) w = 1 + 1w-1w ^ {2}}$

Je vidět, že pro ${ displaystyle w = (1 + i) / 2}$, výše uvedená dvojice funkcí je ekvivalentní formulaci IFS draka na dálnici. To znamená, že drak Heighway, iterovaný do určité iterace, popisuje do jisté míry množinu všech polynomů Littlewood, hodnocených v bodě ${ displaystyle w = (1 + i) / 2}$Při vykreslování dostatečně vysokého počtu kořenů polynomů v Littlewoodu se struktury podobné dračí křivce objevují v bodech blízkých těmto souřadnicím.^[5][6][7]

Viz také

• Seznam fraktálů podle Hausdorffovy dimenze
• Komplexní základní systém

Poznámky

Další čtení

• Angel Chang; Tianrong Zhang (1999–2000). „Fraktální geometrie hranice dračích křivek“. J. Rekreační matematika. 30 (1): 9–22.

externí odkazy

• Dračí křivka -z MathWorld
• Dlaždice od Davida Chowa
• Dvojitá dračí taška s JAVOU
• Eastaway, Rob. "Dračí křivky". Numberphile. Brady Haran.
• Bernard, Pierre (animace); Stewart, Alan (hudba). „Dragon Curve to Music“. Numberphile. Brady Haran.
• Knuth na dračí křivce