Dračí křivka

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
10. iterace dračí křivky

Dračí křivka (z angl. Dragon curve) je sobě-podobná křivka, která má vlastnosti fraktálu. Může být aproximována např. L-systémem nebo systémem iterovaných funkcí. Poprvé jí popsal fyzik z výzkumného střediska NASA John Heighway ,[1] po kterém je někdy nazývána „Heighway Dragon“.

Vlastnosti[editovat | editovat zdroj]

  • soběpodobnost – dračí křivka má mnoho sobě-podobných částí, které jsou vzájemně otočeny o 45° a jejich velikosti jsou násobky v poměru 1:√2

Soběpodobnosti dračí křivky

  • rozměry křivky jsou 1,5 × 1 (při délce výchozí úsečky 1)

Rozměr dračí křivky je 1,5 × 1

  • délka křivky se každou iterací násobí √2, z každého segmentu délky s se stanou dva segmenty délky \textstyle{s \over \sqrt{2}}
{2s \over \sqrt{2}} = {2s \over \sqrt{2}} \cdot {\sqrt{2} \over \sqrt{2}} = \sqrt{2}s
  • křivka nikdy neprotne sama sebe, to je vidět, když se vykreslí se zkosenými rohy

Dračí křivka se zkosenými rohy, aby bylo vidět, že se nikdy neprotne

\log_2\left(\frac{1+\sqrt[3]{73-6\sqrt{87}}+\sqrt[3]{73+6\sqrt{87}}}{3}\right)\cong 1.523627086202492.

Konstrukce[editovat | editovat zdroj]

Jedna z možných konstrukcí je následující. Začne se s úsečkou o libovolné délce. V Každém kroku se nad každou úsečkou postaví pravoúhlý rovnoramenný trojúhelník. Přepona tohoto trojúhelníka bude výchozí úsečka a orientace trojúhelníka se bude střídat, na první úsečce doleva, na druhé doprava (směr vzhledem k průchodu křivkou). Nakonec se přepony odeberou a vznikne další iterace.

Prvních 5 iterací s 9. iterací

Animace vývoje:

Animovaný vývoj Dračí křivky

L-systém[editovat | editovat zdroj]

Výše uvedený postup lze simulovat následujícím L-systémem:

gramatika
abeceda: R L + -
axiom: R(1)
přepis. pravidla: R(d)- R(d/√2) ++ L(d/√2) -
L(d)+ R(d/√2) -- L(d/√2) +
interpretace
úhel otočení: 45°

Tento L-systém je parametrický, dračí křivka však lze popsat i bezparametrickým L-systémem. Ten má tu nevýhodu, že výsledná velikost obrázku, záleží na počtu iterací (na rozdíl od prvního L-systému). Na druhou stranu se v něm nevyskytují žádná iracionální čísla, se kterými počítače neumí pracovat, proto bude aproximace velmi přesná i pro vysoké iterace.

gramatika
abeceda: L R + -
axiom: L
přepis. pravidla: LL+R+
R-L-R
interpretace
úhel otočení: 90°

Výsledek bude vznikat po iteracích takto:

Animace rozvoje dračí křivky

Systémy iterovaných funkcí[editovat | editovat zdroj]

Dračí křivka je také limita následujícího systému iterovaných funkcí v komplexní rovině:

f_1(z)={(1+i)z \over 2}
f_2(z)=1-{(1-i)z \over 2}.

Použitím dvojice reálných čísel místo komplexního dostaneme tyto dvě funkce:

f_1(x,y)= {1 \over \sqrt{2}} \begin{pmatrix} \cos 45^{\circ} & -\sin 45^{\circ} \\ \sin 45^{\circ} & \cos 45^{\circ} \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix}
f_2(x,y)= {1 \over \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}

Skládání papíru[editovat | editovat zdroj]

Pomocí proužku papíru se dá Dračí křivka sestrojit následovně. Proužek přehýbáme napůl tak dlouho, dokud nevznikne čtverec. Poté jednotlivá složení rozevíráme, vždy ale jen o 90 stupňů.

Postup skládání papíru

Kód v PHP[editovat | editovat zdroj]

<?php
header("Content-type: image/png");
$image=imagecreatetruecolor(800,550);
$white=imagecolorallocate($image,255,255,255);
$points=array(array(188,190),array(700,190));
for($iteration=1;$iteration<17;$iteration++){
	$oldpoints=$points; 
	$points=array();
	for($i=0;$i<count($oldpoints)-1;$i++){
		$points[]=array($x1=$oldpoints[$i][0],$y1=$oldpoints[$i][1]);
		$x2=$oldpoints[$i+1][0]; $y2=$oldpoints[$i+1][1];
		if($iteration&1){
			if($y1==$y2)
				{ $x3=($x1+$x2)/2; $y3=$y1+(($x1<$x2)^($i&1)?1:-1)*abs($x1-$x2)/2; }
			else
				{ $y3=($y1+$y2)/2; $x3=$x1+(($y1<$y2)^($i&1)?-1:1)*abs($y1-$y2)/2; }
		}else{
			if    ($x1<$x2 && $y1<$y2){ $x3=($i&1)?$x2:$x1; $y3=($i&1)?$y1:$y2; }
			elseif($x1<$x2 && $y1>$y2){ $x3=($i&1)?$x1:$x2; $y3=($i&1)?$y2:$y1; }
			elseif($x1>$x2 && $y1<$y2){ $x3=($i&1)?$x1:$x2; $y3=($i&1)?$y2:$y1; }
			elseif($x1>$x2 && $y1>$y2){ $x3=($i&1)?$x2:$x1; $y3=($i&1)?$y1:$y2; }
		}
		$points[]=array($x3,$y3);		
	}
	$points[]=end($oldpoints);
}
for($i=0;$i<count($points)-1;$i++)
	imageline($image,$points[$i][0],$points[$i][1],$points[$i+1][0],$points[$i+1][1],$white);
imagepng($image);

Výše uvedený kód nejdříve po jednotlivých iteracích vytváří nové body (vrcholy trojúhelníků nad stávajícími úsečkami), které nakonec hromadně vykreslí. Souřadnice všech bodů si uchovává v poli, jehož velikost se zdvojnásobuje s každou iterací. Vzhledem k jednoduchosti operace se zde lze obejít bez rovnic pro obecnou rotaci geometrických útvarů. Rekurze v tomto případě též není, zásobník více méně simuluje práce s polem; program by však šel do rekurze přepsat.

Dláždění roviny[editovat | editovat zdroj]

Protože Dračí křivka má vlastnosti plochu-vyplňující křivky a dá se přikládat sama k sobě tak, že části na sebe těsně dolehnou, dá se pomocí ní dláždit rovina. Na následujících obrázcích je několik způsobů dláždění.

Reference[editovat | editovat zdroj]

  1. GARDNER, Martin. Mathematical Magic Show. The United States of America : The Mathematical Association of America, 1977. 302 s. Kapitola Teh Dragon Curve and Other Problems, s. 207. (anglicky) 
  2. (anglicky)the Fractal Structure of the Boundary of Dragon Curve
  3. (anglicky)The Boundary of Periodic Iterated Function Systems", Jarek Duda, The Wolfram Demonstrations Project. Rekurentní konstrukce hranice dračí křivky

Související články[editovat | editovat zdroj]

Logo Wikimedia Commons Obrázky, zvuky či videa k tématu Dragon curves ve Wikimedia Commons