Dračí křivka

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

  • 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
  • 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

  • fraktálová dimenze křivky je , jedná se tedy o plochu-vyplňující křivku
  • plocha křivky je (při délce výchozí úsečky 1)
  • fraktálovou dimenzi hranice křivky numericky aproximovali Angel Chang a Tianrong Zhang,[2] dnes již známe analytické vyjádření:[3]

Konstrukce

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

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í

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

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

Skládání papíru

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

<?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

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

  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)On 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

Externí odkazy

Média použitá na této stránce

DragonCurveEvolution.gif
Animovaný vývoj Dračí křivky, vygenerováno pomocí L-systému
Dragon tiling5.svg
Autor: Prokofiev, Licence: CC BY-SA 4.0
Tiling with 2 dragon curves. Also called the Twindragon curve.
Dragon tiling1.svg
Autor: Prokofiev, Licence: CC BY-SA 4.0
Dragon curve tiling 1. 4 dragon curves
Dragon tiling2.svg
Autor: Prokofiev, Licence: CC BY-SA 4.0
Dragon tiling 2. 4 dragon curves.
Dragon tiling6.svg
Autor: Prokofiev, Licence: CC BY-SA 4.0
Tiling with 2 gragon curves.
Full tiling dragon.svg
Autor: Prokofiev, Licence: CC BY-SA 4.0
Tiling the whole plane with dragon curves. One example.
Dragon tiling4.svg
Autor: Prokofiev, Licence: CC BY-SA 4.0
Tiling with 2 dragon curves
Dragon curve L-system.svg
Dragon curve, made using an L-system
Dragon spiral tiling.png
Autor: Prokofiev, Licence: CC BY-SA 4.0
Dragon curves of increasing sizes (ratio sqrt(2)) form an infinite spiral. 4 of these spirals (with rotation 90°) can tile the plane.
Dimensions fractale dragon.png
Autor: Alexis Monnerot-Dumaine, Licence: CC BY-SA 3.0
Size of the dragon fractal.
Dragon curve iterations (2).svg
Iterations 1 to 5 and 9 of the dragon curve
Auto-similarity dragon curve.png
Autor: Alexis Monnerot-Dumaine, Licence: CC BY-SA 3.0
Auto-similarities of the dragon curve.
Dragon curve animation.gif
Autor: 碳酸鈣, Licence: CC BY-SA 3.0
First 12 iterations of a Dragon Curve fractal, using Google Sketchup.
Dragon tiling dragon.svg
Autor: Prokofiev, Licence: CC BY-SA 4.0
4 dragon curves tiling a dragon curve
Full tiling dragon3.svg
Autor: Prokofiev, Licence: CC BY-SA 4.0
Tiling with dragon curves
Full tiling dragon2.svg
Autor: Prokofiev, Licence: CC BY-SA 4.0
Tiling of the whole plane by dragon curves.
DragonCurveWithChamferedEdges.svg
Dtačí křivka se zkosenými rohy, aby bylo vidět že sama sebe nikdy neprotne. Vygenerováno pomocí L-systémů.
Dragon tiling3.svg
Autor: Prokofiev, Licence: CC BY-SA 4.0
Dragon tiling. 4 dragon curves