Кривая дракона

Дракон Хартера — Хейтуэя

Кривая дракона — общее название для некоторых фрактальных кривых, которые могут быть аппроксимированы рекурсивными методами, такими как L-системы.

Дракон Хартера — Хейтуэя

Дракон Хартера, также известный как дракон Хартера — Хейтуэя, был впервые исследован физиками NASA — John Heighway, Bruce Banks, и William Harter. Он был описан в 1967 году Мартином Гарднером (Martin Gardner) в колонке «Математические игры» журнала «Scientific American». Многие свойства фрактала были описаны Chandler Davis и Дональдом Кнутом.

«Дракон Хартера — Хейтуэя» с числом итераций от 1 до 23

Фрактал может быть записан как L-система с параметрами:

• угол равен 90°
• начальная строка — FX
• правила преобразования строк:
  • X $\mapsto$ X+YF+
  • Y $\mapsto$ -FX-Y

Кроме того, фрактал может быть описан системой итерируемых функций на комплексной плоскости:

$f_1(z)=\frac{(1+i)z}{2}$

$f_2(z)=1-\frac{(1-i)z}{2}$.

Берём отрезок, сгибаем его пополам. Затем многократно повторяем итерацию. Если после этого снова разогнуть получившуюся (сложенную) линию так, чтобы все углы были равны 90°, мы получим драконову ломаную.

Пример алгоритма на PHP

<?php
function st($x1,$y1,$x2,$y2,$k,$image,$pcolor)
{
  if ($k > 0)
  {
    $xn = ($x1 + $x2) / 2 + ($y2 - $y1) / 2;
    $yn = ($y1 + $y2) / 2 - ($x2 - $x1) / 2;
    st($x2,$y2,$xn,$yn,$k - 1,$image,$pcolor);
    st($x1,$y1,$xn,$yn,$k - 1,$image,$pcolor);
  } 
  else
  {
    imageline($image,$x1,$y1,$x2,$y2,$pcolor);
  }
}
$dragon = imagecreatetruecolor(640,480);
$bcolor = imagecolorallocate($dragon,255,255,255);
imagecolortransparent($dragon,$bcolor);
imagefill($dragon,1,1,$bcolor);
$dcolor = imagecolorallocate($dragon,255,0,0);
st(200,200,500,300,20,$dragon,$dcolor);
header("Content-type: image/png");
imagepng($dragon);
imagedestroy($dragon);
?>

Пример алгоритма на Delphi (VCL)

procedure Dragon(x1,y1,x2,y2,Depth:Longint;canv:TCanvas);
  procedure Paint(x1,y1,x2,y2,k:Longint);
  var tx,ty:Longint;
  begin
   if k=0 then
    begin
     canv.MoveTo(x1,y1);
     canv.LineTo(x2,y2);
     Exit;
    end;
   tx:=(x1+x2) div 2+(y2-y1) div 2;
   ty:=(y1+y2) div 2-(x2-x1) div 2;
   Paint(x2,y2,tx,ty,k-1);
   Paint(x1,y1,tx,ty,k-1);
  end;
begin
 Paint(x1,y1,x2,y2,Depth);
end;

Ссылки

	Кривая дракона на Викискладе?

• Сайт посвященный Дракону Хартера-Хейтуэя с исходниками на Visual Basic
• Фракталы на сайте Алгоритмы
• Weisstein, Eric W. Кривая дракона (англ.) на сайте Wolfram MathWorld.
• Кривая дракона и складывание бумаги