Драконова крива: Як складання паперу будує фрактал, що укладається в площину

Згинання смужки паперу, назавжди

Візьміть довгу смужку паперу та складіть її навпіл, завжди в одному напрямку. Зробіть це один раз: одна зморшка. Повторіть чотири рази і розгорніть кожну зморшку під прямим кутом: у вас вийде дракон Хейвей, такий самий вигин, який помітили інженери NASA на краях креслень, і той самий, що прикрашав обкладинку книги Майкла Крайтона «Парк Юрського періоду». Фізичне складання паперу – це гарна історія, але цей вигин визначається значно простішим об’єктом: послідовністю поворотів L та R, яка подвоюється в довжину на кожному кроці.

Почніть із односимвольної послідовності L. Щоб перейти від генерації n до n+1, скопіюйте послідовність, вставте L посередині, а потім додайте обернену оригінальну послідовність, з усіма символами перевернутими (L↔R). Це точне правило, якому підпорядковується смужка паперу, коли її складають навпіл і завжди складати в один і той же бік: кожен наступний згин віддзеркалює та змінює все, що було раніше.

Графічні черепашки: перетворення рядків на пікселі

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

Функція nextGen(seq) { // seq - це масив +1 (L) / -1 (R) const mid = 1; // вставте L (+1) посередині const tailRev = [...seq].reverse().map(t => -t); return [...seq, mid, ...tailRev]; } let heading = 0; // 0,1,2,3 = N,E,S,W як кратні 90° for (const turn of turnSeq) { x += DX[heading] * step; y += DY[heading] * step; drawLineTo(x, y); heading = (heading + turn + 4) % 4; } Альтернативний і часто швидший шлях пропускає побудову рядка повністю: поворот перед кроком n (1-похідний) визначається безпосередньо за допомогою положення найнижчого біта, що дорівнює 0 у двійковому представленні n, старий біт-трюк, який незалежно відкрили кілька людей, які вивчали криву дракона та її самоспіввідношення. Це дозволяє перейти до сегмента 131,072 без створення перших 131,071.

function nextGen(seq) {
  // seq is an array of +1 (L) / -1 (R)
  const mid = 1;                 // insert an L (+1) in the middle
  const tailRev = [...seq].reverse().map(t => -t);
  return [...seq, mid, ...tailRev];
}

let heading = 0;                 // 0,1,2,3 = N,E,S,W as multiples of 90°
for (const turn of turnSeq) {
  x += DX[heading] * step; y += DY[heading] * step;
  drawLineTo(x, y);
  heading = (heading + turn + 4) % 4;
}

Самоподільність та межа, що покриває площину

Дракон-крива побудована з двох копій зменшеного розміру, кожна повернута на 45° і масштабована в 1/√2, об'єднані у їхніх кінчиках – прямий наслідок правила «згортання та віддзеркалення». Ця самоподільність надає їй фрактальну розмірність рівно 2: хоча крива малюється як одномірний шлях, при достатній кількості ітерацій вона заповнює площу, а її межа також є фракльною кривою розмірності приблизно 1.5236. Незважаючи на те, що крива постійно перетинає себе поблизу, крива, згенерована цією L-системою, ніколи не перетинає себе – властивість, доведено суворо Чендером Девісом та Дональдом Кнут у їхній статті 1970 року про дракон-криву та інші послідовності складання паперу.

Найбільш вражаюча особливість: чотири копії дракон-кривої, повернуті на 90° інтервали навколо спільного центру, покривають площину без проміжків і перекриттів. Крива є, в строгому математичному сенсі, рептилою – її можна розібрати на менші копії себе, а більші копії точно укладаються за допомогою менших копій. Це пов'язує її з цілою родиною кривих складання паперу (крива Lévy C, тердракон), побудованих за тією ж ідеєю, але з різними кутами згортання або кількістю згинів на крок.

Чому покоління 17 вже має 131 072 сегменти

Кожне наступне покоління подвоює кількість сегментів попереднього покоління: n-те покоління має 2ⁿ сегментів. Саме тому, що на екрані після лише 17 ступенів збільшення вже потрібно 131 072 лінійних сегментів — і чому будь-яка реалізація, яка перераховує всю ланцюг з нуля кожного кадра, почне зависати ще до покоління 20. Виправлення, яке використовується в цій симуляції, таке ж саме, як і у всіх інших L-системних фракталів на сайті: повну послідовність поворотів обчислюють один раз при зміні покоління, використовуючи лінійну рекурсію (не експоненційну), а перемальовування відбувається лише тоді, коли змінюється покоління або розмір кроку.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Dragon Curve і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.