Фрактал Гартера — Гайвея

Крива дракона — приклад системи ітераційних функцій, загальна назва для деяких фрактальних кривих, які можуть бути апроксимовані рекурсивними методами, такими як L-система^[en].

Дракон Гартера — Гайвея

Дракон Гартера, також відомий як дракон Гартера — Гайвея, вперше дослідили фізики NASA Джон Гайвей (англ. John Heighway), Брюс Бенкс (англ. Bruce Banks) і Вільям Гартер (англ. William Harter). 1967 року його описав Мартін Ґарднер у колонці «Математичні ігри» журналу «Scientific American». Багато властивостей фрактала описали Чандлер Девіс^[en] і Дональд Кнут.

Фрактал може бути записаний як L-система^[en] з параметрами:

кут дорівнює 90°
початковий рядок FX
правила перетворення рядків:

$X\rightarrow X+YF+$
$Y\rightarrow -FX-Y$

Це може бути описано так: Починаючи з базового відрізка, замінити кожен відрізок двома відрізками з прямим кутом і з обертанням на 45°, альтернативно, праворуч і ліворуч:

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

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

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

з початковим набором $S_{0}=\{0,1\}$ пунктів.

Використання натомість пар дійсних чисел ілюструють дві функції:

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

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

Це подання найчастіше використовується у програмах, таких як Apophysis.

Складання Дракона

При трасуванні ітерації кривої дракона від одного кінця до іншого, один стикається з низкою витків 90 градусів. Протягом перших декількох ітерацій послідовність праворуч (R) і ліворуч (L) виявляється таким чином:

1-а ітерація: R;
2-а ітерація: R R L;
3-а ітерація: R R L R R L L;
4-а ітерація: R R L R R L L R R R L L R L L.

Ця схема говорить про те, що кожна ітерація формується шляхом прийняття попередньої ітерації, додавання R в кінці, а потім ретроградного повороту з оригінальної ітерації, заміняти кожну букву і додавати результат після R.

Ця модель, у свою чергу, передбачає такий метод створення моделей ітерацій кривої дракона по складанню смужки паперу. Візьміть смужку паперу і складіть її навпіл з правого боку. Складіть її навпіл і знову праворуч. Якщо смуга була відкрита зараз, розгинайте кожну складку, щоб отримати 90-градусний поворот, послідовність черги буде RRL тобто другої ітерації дракона. Складіть смужку навпіл і знову праворуч, і наступна послідовність розкладеної смуги тепер RRLRRLL — третьої ітерації дракона. Продовжуючи складання смуги наполовину вправо, будуть створюватися додаткові ітерації дракона (на практиці, смуга стає занадто товстою, щоб різко скинути після чотирьох або п'яти ітерацій).

Ця модель також дає метод для визначення напрямку $n$ -го повороту послідовності дракона. По-перше, виразити $n$ у вигляді $k2^{m}$ , де $k$ — це непарне число. Напрямок $n$ у свою чергу, визначається $k{\pmod {4}},$ тобто залишок наліво, коли $k$ ділиться на 4. Якщо $k\equiv 1{\pmod {4}}$ , то $n$ -й елемент у черзі є R; якщо $k\equiv 3{\pmod {4}}$ , то $n$ -й елемент у черзі є L.

Наприклад, щоб визначити напрямок повороту 76376:

76376 = 9547*8

9547 = 2386x4 + 3

так +9547

\equiv 3{\pmod {4}}

так напрямок 76376 є L.

Існує простий однолінійной нерекурсивний метод реалізації наведеного вище методу знаходження напрямку повороту в коді. Обчислення повороту $n$ у вигляді двійкового числа, обчислюється наступним логічним значенням:

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

«n & −n» залишає тільки один біт, якщо '1', то вправо '1' в двійковому розкладанні n;
«<< 1» зрушує вліво на одну позицію;
«& n» виходить, що або один біт (якщо $k\equiv 3{\pmod {4}}$ ), або нуль (якщо $k\equiv 1{\pmod {4}}$ ).
так «bool turn = (((n & −n) << 1) & n) != 0» — TRUE якщо n у свою чергу — L; і FALSE, якщо n у свою чергу — R.

Грей код

Інший спосіб обробки — зменшення за нижчезазначеним алгоритмом. Використання коду Грея, починаючи з нуля, визначає зміну до наступного значення. Якщо зміна 1, то повернути наліво, і якщо він дорівнює 0, то повернути праворуч. Враховуючи дискретний вхід, B, відповідний код Грея, G, дається «G = B XOR (B>>1)». Використання G_i та G_i₋₁, поворот дорівнює «(не G_i), а G_i₋₁».

G = B ^ (B >> 1); Це стає сірий код з двійкового.
Т = (~ G0) і G1; Якщо T дорівнює 0 — за годинниковою стрілкою, інше — повернути проти годинникової стрілки.

Розміри

Незважаючи на дивний вигляд, крива дракона має прості вимірювання. Зверніть увагу, що розміри 1 та 1,5 є границею, а не фактичним значенням.

Його поверхня також досить проста: якщо початковий відрізок дорівнює 1, то його поверхню дорівнює ${\frac {1}{2}}$ . Цей результат походить від його властивості.
Крива ніколи не перетинає себе.
Багато самостійно схожих елементів можна побачити на кривій дракона. Найбільш очевидним є повторення тієї ж схеми, нахиленої на 45 ° і з коефіцієнтом обтиснення ${\sqrt {2}}$ .

Його фрактальна розмірність може бути обчислена : $\textstyle {{\frac {\ln 2}{\ln {\sqrt {2}}}}=2}$ : Ця крива заповнює його простір^[en].
Його межа має нескінченну довжину, так як це збільшує аналогічний коефіцієнт кожної ітерації.
Фрактальна розмірність його межі була наближена чисельно до розмірності Чанг і Чжан^[1].

Насправді він може бути знайдений аналітично^[2]:

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

У цьому корінь рівняння $\textstyle {4^{x}(2^{x}-1)=4(2^{x}+1).}$

Черепиця

1-й елемент з 4 кривих
2-й елемент з 4 кривих
3-й елемент з 4 кривих
Крива дракона
1-й елемент з 2 кривих
2-й елемент з 2 кривих (twindragon)
3-й елемент з 2 кривих
Приклад площини плитки
Приклад площини плитки
Приклад площини плитки
Крива дракона в зростаючих розмірах утворюють нескінченну спіраль. 4 з цих спіралей (з обертанням 90 °).

Twindragon

Twindragon (також відомий як дракон Девіс-Кнута) може бути побудований шляхом розміщення двох кривих дракона спина до спини. Ця система функцій може мати також безліч повторів:

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

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

де вихідна форма визначається наступним $S_{0}=\{0,1,1-i\}$ набором.

Це також можна записати у вигляді L-системи — достатньо лише додати ще один розділ в початковому рядку:

кут 90 °;
Початковий рядок FX + FX +;
рядок переписування правил:
- Х ↦ X + YF
- У ↦ FX — У.

Twindragon крива, побудована з двох кривих дракона

Terdragon

Terdragon може бути записаний у вигляді системи:

кут 120 °;
Початковий рядок F;
рядок переписування правил:
- F ↦ F+F−F.

Ця система функцій може мати безліч повторів:

f_{1}(z)=\lambda z

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

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

де : $\lambda ={\frac {1}{2}}-{\frac {i}{2{\sqrt {3}}}},\lambda ^{*}={\frac {1}{2}}+{\frac {i}{2{\sqrt {3}}}}.$

Крива Леві

Також відома як дракон Леві^[3].

Приклад алгоритму на PHP

<?php
        $i = 20;
        
        $image = imagecreatetruecolor(640, 480);
        imagefilledrectangle($image, 0, 0, imagesx($image) - 1, imagesy($image) - 1,
                imagecolorresolve($image, 255, 255, 255));
        $color = imagecolorresolve($image, 0, 0, 0);
 
        drawDragon($image, imagesx($image) * 3/8, imagesy($image) * 3/8,
                imagesx($image) * 5/8, imagesy($image) * 5/8, $i, $color);
        
        /**
         * Draws dragon curve between two points.
         * @return void
         */
        function drawDragon($image, $xa, $ya, $xc, $yc, $i, $color) {
            if($i == 0)
                imageline($image, $xa, $ya, $xc, $yc, $color);
            else {
                // A---B
                //     |
                //     C
                $xb = ($xa + $xc) / 2 + ($yc - $ya) / 2;
                $yb = ($ya + $yc) / 2 - ($xc - $xa) / 2;
                drawDragon($image, $xa, $ya, $xb, $yb, $i - 1, $color);
                drawDragon($image, $xc, $yc, $xb, $yb, $i - 1, $color);
            } 
        }
 
        header('Content-type: image/png');
        imagepng($image);
        imagedestroy($image);

Приклад алгоритму на 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;

Приклад алгоритму на Python 3

from turtle import *

def go_drakoning(t, length, depth, sign = 1):
    if depth == 1:
        t.forward(length)
    else:
        t.left(45*sign)
        go_drakoning(t, length/2**0.5, depth - 1, 1)
        t.right(90*sign)
        go_drakoning(t, length/2**0.5, depth - 1, -1)
        t.left(45*sign)

t = Turtle()
t.color("blue")
go_drakoning(t, 100, 9)

Код програми у середовищі програмування Borland Delphi

 unit Unit1;
 interface
 uses
 Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
 Dialogs, ExtCtrls, StdCtrls;
 type
 TForm1 = class(TForm)
   Button1: TButton;
   PaintBox1: TPaintBox;
   procedure Button1Click(Sender: TObject);
   procedure Paint(x1,y1,x2,y2,k:Longint);
 private
   { Private declarations }
  public
  n: integer
   { Public declarations }
  end;
  var
  Form1: TForm1;
  implementation
  {$R *.dfm}
  procedure TForm1.Paint(x1,y1,x2,y2,k:Longint);
 var tx,ty:Longint;
 begin
 if n=1 then
 begin
 PaintBox1.Canvas.Pen.Color:=clRed;
 end else begin
 PaintBox1.Canvas.Pen.Color:=clRed;
 end;
  if k=0 then
   begin
    PaintBox1.Canvas.MoveTo(x1,y1);
    PaintBox1.Canvas.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;
procedure TForm1.Button1Click(Sender: TObject);
Var x1,y1,x2,y2,k: Integer;
begin
PaintBox1.Width := 1000;
PaintBox1.Height:= 650;
PaintBox1.Canvas.Brush.Color := clWhite;
PaintBox1.Canvas.Rectangle(0,0,PaintBox1.width,PaintBox1.height);
    x1 := 200;
    y1 := 200;
    x2 := 500;
    y2 := 500;
    k  := 24;
    Paint(x1,y1,x2,y2,k);
  end;    end.

Примітки

↑ Fractal dimension of the boundary of the Dragon curve. Архів оригіналу за 16 серпня 2019. Процитовано 9 квітня 2016.
↑ «The Boundary of Periodic Iterated Function Systems [Архівовано 7 квітня 2016 у Wayback Machine.]» by Jarek Duda, The Wolfram Demonstrations Project. Recurrent construction of the boundary of dragon curve.
↑ Bailey, Scott; Kim, Theodore; Strichartz, Robert S. (2002), Inside the Lévy dragon, The American Mathematical Monthly, 109 (8): 689—703, doi:10.2307/3072395.

[chang-1] Fractal dimension of the boundary of the Dragon curve. Архів оригіналу за 16 серпня 2019. Процитовано 9 квітня 2016.

[2] «The Boundary of Periodic Iterated Function Systems [Архівовано 7 квітня 2016 у Wayback Machine.]» by Jarek Duda, The Wolfram Demonstrations Project. Recurrent construction of the boundary of dragon curve.

[3] Bailey, Scott; Kim, Theodore; Strichartz, Robert S. (2002), Inside the Lévy dragon, The American Mathematical Monthly, 109 (8): 689—703, doi:10.2307/3072395.

[1]

[2]

[3]

п о р Фрактали
Характеристики	Фрактальна розмірність (Розмірність Гаусдорфа · Розмірність Лебега) · Рекурсія · Самоподібність
Найпростіші фрактали	Папороть Барнслі · Множина Кантора · Крива дракона · Крива Коха · Губка Менгера · Килим Серпінського · Крива Серпінського · Піраміда Серпінського · Трикутник Серпінського · Крива Пеано · Сітка Аполлонія
Дивний атрактор	Мультифрактал
L-система	Крива, що заповнює простір
Біфуркаційні фрактали	Множина Жуліа · Фрактал Ляпунова · Множина Мандельброта · Басейни Ньютона
Випадкові фрактали	Броунівський рух · Броунівське дерево · Фрактальний ландшафт · Теорія протікання
Люди	Георг Кантор · Фелікс Гаусдорф · Гастон Жуліа · Гельґе фон Кох · Поль Леві · Олександр Ляпунов · Бенуа Мандельброт · Льюїс Річардсон · Вацлав Серпінський
Пов'язані теми	«Яка довжина узбережжя Великої Британії?» (Парадокс берегової лінії)