Фрактал Хартера — Хейтуея
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/21/Dragon_curve_animation.gif/300px-Dragon_curve_animation.gif)
Крива дракона — приклад системи ітераційних функцій, загальна назва для деяких фрактальних кривих, які можуть бути апроксимовані рекурсивними методами, такими як L-система[en].
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/69/Fractal_dragon_curve.jpg/220px-Fractal_dragon_curve.jpg)
Дракон Хартера, також відомий як дракон Хартера — Хейтуея, був вперше досліджений фізиками NASA. Він був описаний в 1967 році Мартіном Гарднером в колонці «Математичні ігри» журналу «Scientific American». Багато властивостей фрактала були описані Чандлерльдом Девісом[en] і Дональдом Кнутом.
Фрактал може бути записаний як L-система[en] з параметрами:
- кут дорівнює 90°
- початковий рядок FX
- правила перетворення рядків:
Це може бути описано так: Починаючи з базового сегмента, замінити кожен сегмент двома сегментами з прямим кутом і з обертанням на 45°, альтернативно, праворуч і ліворуч:
![The first 5 iterations and the 9th](http://upload.wikimedia.org/wikipedia/commons/thumb/9/97/Dragon_curve_iterations_%282%29.svg/700px-Dragon_curve_iterations_%282%29.svg.png)
Крім того, фрактал може бути описаний системою ітераційних функцій на комплексній площині:
з початковим набором пунктів.
Використання натомість пар дійсних чисел ілюструють дві функції:
Це подання найчастіше використовується у програмах, таких як Apophysis.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/25/Curved_Dragon_Curve.svg/220px-Curved_Dragon_Curve.svg.png)
При трасуванні ітерації кривої дракона від одного кінця до іншого, один стикається з низкою витків 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 — третьої ітерації дракона. Продовжуючи складання смуги наполовину вправо, будуть створюватися додаткові ітерації дракона (на практиці, смуга стає занадто товстою, щоб різко скинути після чотирьох або п'яти ітерацій).
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f1/Dragon_curve_paper_strip.png/800px-Dragon_curve_paper_strip.png)
![](http://upload.wikimedia.org/wikipedia/commons/1/1d/Dragon_Curve_Unfolding.gif)
Ця модель також дає метод для визначення напрямку -го повороту послідовності дракона. По-перше, виразити у вигляді , де — це непарне число. Напрямок у свою чергу, визначається тобто залишок наліво, коли ділиться на 4. Якщо , то -й елемент у черзі є R; якщо , то -й елемент у черзі є L.
Наприклад, щоб визначити напрямок повороту 76376:
- 76376 = 9547*8
- 9547 = 2386x4 + 3
- так +9547
- так напрямок 76376 є L.
Існує простий однолінійной нерекурсивний метод реалізації наведеного вище методу знаходження напрямку повороту в коді. Обчислення повороту у вигляді двійкового числа, обчислюється наступним логічним значенням:
- bool turn = (((n & −n) << 1) & n) != 0;
- «n & −n» залишає тільки один біт, якщо '1', то вправо '1' в двійковому розкладанні n;
- «<< 1» зрушує вліво на одну позицію;
- «& n» виходить, що або один біт (якщо ), або нуль (якщо ).
- так «bool turn = (((n & −n) << 1) & n) != 0» — TRUE якщо n у свою чергу — L; і FALSE, якщо n у свою чергу — R.
Інший спосіб обробки — зменшення за нижчезазначеним алгоритмом. Використання коду Грея, починаючи з нуля, визначає зміну до наступного значення. Якщо зміна 1, то повернути наліво, і якщо він дорівнює 0, то повернути праворуч. Враховуючи дискретний вхід, B, відповідний код Грея, G, дається «G = B XOR (B>>1)». Використання Gi та Gi−1, поворот дорівнює «(не Gi), а Gi−1».
- G = B ^ (B >> 1); Це стає сірий код з двійкового.
- Т = (~ G0) і G1; Якщо T дорівнює 0 — за годинниковою стрілкою, інше — повернути проти годинникової стрілки.
- Незважаючи на дивний вигляд, крива дракона має прості вимірювання. Зверніть увагу, що розміри 1 та 1,5 є границею, а не фактичним значенням.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d7/Dimensions_fractale_dragon.png/500px-Dimensions_fractale_dragon.png)
- Його поверхня також досить проста: якщо початковий відрізок дорівнює 1, то його поверхню дорівнює . Цей результат походить від його властивості.
- Крива ніколи не перетинає себе.
- Багато самостійно схожих елементів можна побачити на кривій дракона. Найбільш очевидним є повторення тієї ж схеми, нахиленої на 45 ° і з коефіцієнтом обтиснення .
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c4/Auto-similarity_dragon_curve.png/350px-Auto-similarity_dragon_curve.png)
- Його фрактальна розмірність може бути обчислена : : Ця крива заповнює його простір[en].
- Його межа має нескінченну довжину, так як це збільшує аналогічний коефіцієнт кожної ітерації.
- Фрактальна розмірність його межі була наближена чисельно до розмірності Чанг і Чжан[1].
Насправді він може бути знайдений аналітично[2]:
У цьому корінь рівняння
-
1-й елемент з 4 кривих
-
2-й елемент з 4 кривих
-
3-й елемент з 4 кривих
-
Крива дракона
-
1-й елемент з 2 кривих
-
2-й елемент з 2 кривих (twindragon)
-
3-й елемент з 2 кривих
-
Приклад площини плитки
-
Приклад площини плитки
-
Приклад площини плитки
-
Крива дракона в зростаючих розмірах утворюють нескінченну спіраль. 4 з цих спіралей (з обертанням 90 °).
Twindragon (також відомий як дракон Девіс-Кнута) може бути побудований шляхом розміщення двох кривих дракона спина до спини. Ця система функцій може мати також безліч повторів:
де вихідна форма визначається наступним набором.
Це також можна записати у вигляді L-системи — достатньо лише додати ще один розділ в початковому рядку:
- кут 90 °;
- Початковий рядок FX + FX +;
- рядок переписування правил:
- Х ↦ X + YF
- У ↦ FX — У.
![]() |
![]() |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e3/Terdragon.png/250px-Terdragon.png)
Terdragon може бути записаний у вигляді системи:
- кут 120 °;
- Початковий рядок F;
- рядок переписування правил:
- F ↦ F+F−F.
Ця система функцій може мати безліч повторів:
де :
Також відома як дракон Леві[3].
![]() |
<?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);
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;
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)
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.