Крива дракона — приклад системи ітераційних функцій, загальна назва для деяких фрактальних кривих, які можуть бути апроксимовані рекурсивними методами, такими як [en].
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOHlMekl4TDBSeVlXZHZibDlqZFhKMlpWOWhibWx0WVhScGIyNHVaMmxtTHpNd01IQjRMVVJ5WVdkdmJsOWpkWEoyWlY5aGJtbHRZWFJwYjI0dVoybG0uZ2lm.gif)
Дракон Хартера — Хейтуея
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODJMelk1TDBaeVlXTjBZV3hmWkhKaFoyOXVYMk4xY25abExtcHdaeTh5TWpCd2VDMUdjbUZqZEdGc1gyUnlZV2R2Ymw5amRYSjJaUzVxY0djPS5qcGc=.jpg)
Дракон Хартера, також відомий як дракон Хартера — Хейтуея, був вперше досліджений фізиками NASA. Він був описаний в 1967 році Мартіном Гарднером в колонці «Математичні ігри» журналу «Scientific American». Багато властивостей фрактала були описані [en] і Дональдом Кнутом.
Фрактал може бути записаний як [en] з параметрами:
- кут дорівнює 90°
- початковий рядок FX
- правила перетворення рядків:
Це може бути описано так: Починаючи з базового сегмента, замінити кожен сегмент двома сегментами з прямим кутом і з обертанням на 45°, альтернативно, праворуч і ліворуч:
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODVMemszTDBSeVlXZHZibDlqZFhKMlpWOXBkR1Z5WVhScGIyNXpYeVV5T0RJbE1qa3VjM1puTHpjd01IQjRMVVJ5WVdkdmJsOWpkWEoyWlY5cGRHVnlZWFJwYjI1elh5VXlPRElsTWprdWMzWm5MbkJ1Wnc9PS5wbmc=.png)
Крім того, фрактал може бути описаний системою ітераційних функцій на комплексній площині:
з початковим набором пунктів.
Використання натомість пар дійсних чисел ілюструють дві функції:
Це подання найчастіше використовується у програмах, таких як Apophysis.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOHlMekkxTDBOMWNuWmxaRjlFY21GbmIyNWZRM1Z5ZG1VdWMzWm5Mekl5TUhCNExVTjFjblpsWkY5RWNtRm5iMjVmUTNWeWRtVXVjM1puTG5CdVp3PT0ucG5n.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 — третьої ітерації дракона. Продовжуючи складання смуги наполовину вправо, будуть створюватися додаткові ітерації дракона (на практиці, смуга стає занадто товстою, щоб різко скинути після чотирьох або п'яти ітерацій).
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOW1MMll4TDBSeVlXZHZibDlqZFhKMlpWOXdZWEJsY2w5emRISnBjQzV3Ym1jdk9EQXdjSGd0UkhKaFoyOXVYMk4xY25abFgzQmhjR1Z5WDNOMGNtbHdMbkJ1Wnc9PS5wbmc=.png)
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTh4THpGa0wwUnlZV2R2Ymw5RGRYSjJaVjlWYm1admJHUnBibWN1WjJsbS5naWY=.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 є границею, а не фактичним значенням.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOWtMMlEzTDBScGJXVnVjMmx2Ym5OZlpuSmhZM1JoYkdWZlpISmhaMjl1TG5CdVp5ODFNREJ3ZUMxRWFXMWxibk5wYjI1elgyWnlZV04wWVd4bFgyUnlZV2R2Ymk1d2JtYz0ucG5n.png)
- Його поверхня також досить проста: якщо початковий відрізок дорівнює 1, то його поверхню дорівнює
. Цей результат походить від його властивості.
- Крива ніколи не перетинає себе.
- Багато самостійно схожих елементів можна побачити на кривій дракона. Найбільш очевидним є повторення тієї ж схеми, нахиленої на 45 ° і з коефіцієнтом обтиснення
.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOWpMMk0wTDBGMWRHOHRjMmx0YVd4aGNtbDBlVjlrY21GbmIyNWZZM1Z5ZG1VdWNHNW5Mek0xTUhCNExVRjFkRzh0YzJsdGFXeGhjbWwwZVY5a2NtRm5iMjVmWTNWeWRtVXVjRzVuLnBuZw==.png)
- Його фрактальна розмірність може бути обчислена :
: Ця [en].
- Його межа має нескінченну довжину, так як це збільшує аналогічний коефіцієнт кожної ітерації.
- Фрактальна розмірність його межі була наближена чисельно до розмірності Чанг і Чжан.
Насправді він може бути знайдений аналітично:
У цьому корінь рівняння
Черепиця
- 1-й елемент з 4 кривих
- 2-й елемент з 4 кривих
- 3-й елемент з 4 кривих
- Крива дракона
- 1-й елемент з 2 кривих
- 2-й елемент з 2 кривих (twindragon)
- 3-й елемент з 2 кривих
- Приклад площини плитки
- Приклад площини плитки
- Приклад площини плитки
- Крива дракона в зростаючих розмірах утворюють нескінченну спіраль. 4 з цих спіралей (з обертанням 90 °).
Twindragon
Twindragon (також відомий як дракон Девіс-Кнута) може бути побудований шляхом розміщення двох кривих дракона спина до спини. Ця система функцій може мати також безліч повторів:
де вихідна форма визначається наступним набором.
Це також можна записати у вигляді L-системи — достатньо лише додати ще один розділ в початковому рядку:
- кут 90 °;
- Початковий рядок FX + FX +;
- рядок переписування правил:
- Х ↦ X + YF
- У ↦ FX — У.
![]() | ![]() |
Terdragon
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOWxMMlV6TDFSbGNtUnlZV2R2Ymk1d2JtY3ZNalV3Y0hndFZHVnlaSEpoWjI5dUxuQnVadz09LnBuZw==.png)
Terdragon може бути записаний у вигляді системи:
- кут 120 °;
- Початковий рядок F;
- рядок переписування правил:
- F ↦ F+F−F.
Ця система функцій може мати безліч повторів:
де :
Крива Леві
![]() |
Приклад алгоритму на 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.
Примітки
- . Архів оригіналу за 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.