Створено алгоритм, що генерує інструкції зі складання орігамі будь-якої форми

У 1999 році Ерік Демейн (Erik Demaine), тоді ще 18-річний аспірант Університету Вотерлу в Канаді описав алгоритм, який міг би визначити, як згорнути аркуш паперу в будь-яку мислиму тривимірну форму. Це була значуща віха в області обчислювальних орігамі, але алгоритм не міг створити схеми для складання, які можна було б дійсно застосувати на практиці.

По суті, алгоритм брав за основу дуже довгу смужку паперу й повертав її в бажану форму. Отримані структури, як правило, мали багато ліній швів, де шари паперової стрічки накладалися один на одного, утворюючи складки, з-за чого отримуються конструкції були не дуже міцними.

У 1999 році Демейн довів, що можна скласти будь полиэдр, але спосіб, яким цього можна досягти, виявився не дуже ефективним. Запропонований метод працює, якщо вихідний аркуш паперу довгий і вузький. Але якщо потрібно працювати, наприклад, з квадратним листом, то алгоритм все одно буде спочатку складати папір до тонкої смуги, витрачаючи весь матеріал почому дарма.

Тепер професор електротехніки та інформатики Массачусетського технологічного інституту Ерік Демейн і його колега Томохіро Тачі з Токійського університету готові оголосити про завершення квесту, який почався з роботи 1999 року: в липні 2017 року на симпозіумі з обчислювальної геометрії вони представлять алгоритм для створення орігамі, який гарантує мінімально можливу кількість швів. Демейн і Тачі також працюють над впровадженням алгоритму в новій версії Origamizer — безкоштовного ПЗ для генерації малюнків з орігамі. Перша версія була випущена Тачі в 2008 році.

Алгоритм дослідників розробляє шаблони згинів для створення будь-якого багатогранника, тобто тривимірної поверхні, що складається з багатьох площин. Програмне забезпечення для створення комп’ютерної графіки моделює тривимірні об’єкти як многогранники, що складаються з безлічі крихітних трикутників.

Строго кажучи, гарантія того, що складання листа буде включати мінімальну кількість швів означає, що він зберігає «кордону» оригінального аркуша паперу. Припустимо, у вас є цілий аркуш паперу і ви хочете скласти з нього чашку. Залишивши менший круг в центрі цього листа, ви можете з’єднати боку.

У цьому випадку межа чашки — її обід — така ж, як межа розгорнутої колу — її зовнішній край. Те ж саме робив попередній алгоритм Демейна: чаша, яку він пропонував, складалася з тонкої смужки паперу, загорнутої в котушку, і, ймовірно, не змогла б утримувати воду.

Математичне властивість, различающее обидва методу, вчені називають «водонепроникністю». Так новий алгоритм зберігає кордон оригінального аркуша паперу на кордоні поверхні, яку користувач намагається зробити. Закрита поверхню, така як сфера, не має межі, тому орігамі зажадає шва, де зустрінуться ці межі. Ми не можемо отримати повністю замкнуту поверхню, але можемо вибрати, де поставити кордон.

На першому етапі алгоритм проектує межі потрібної фігури на плоску поверхню. Але в той час, коли межі будуть стикатися, коли згортання завершено, вони можуть бути досить далеко один від одного на плоскій поверхні. Користувач складає всі додаткові матеріали і об’єднує межі фігури. Складання додаткового матеріалу може бути дуже складним процесом. Згини, що об’єднують кілька сторін, можуть включати в себе десятки або навіть сотні окремих згинів.

Розробка методу автоматичного розрахунку інструкцій орігамі включала в себе кілька різних ідей, але центральною стала та, яку можна було б назвати приблизно відповідній діаграмі Вороного. Щоб зрозуміти цю концепцію, автори пропонують уявити собі рівнину, вкриту травою, На ній одночасно включається ряд вогнів, і всі вони поширюються у всіх напрямках з однаковою швидкістю.

Діаграма Вороного, названа на честь російського вченого XIX століття Геория Вороного, описується як місце, де встановлені вогні, так і кордони, з якими зустрічаються прилеглі вогні. В алгоритмі Демейна і Тачі кордону діаграми Вороного визначають місця згину паперу.

Робота вчених отримала дуже схвальні відгуки від інших експертів у цій області. Роберт Ланг (Robert Lang), один з піонерів обчислювальних орігамі та член Американського математичного товариства, який у 2001 році відмовився від успішної кар’єри в області оптичної техніки, щоб стати повноправним оригамистом, зазначив, що це дуже вражаючий матеріал.

Ланг вважає, що вченим вдалося вдало завершити довгий шлях зі створення обчислювального методу для ефективного згинання аркуша паперу будь-якої заданої форми, що розпочався 20 років тому. По дорозі деяким дослідникам вдавалося продемонструвати кілька варіантів вирішення проблеми, які не можна було назвати універсальними. Були розроблені алгоритми складання паперу будь-якої форми, які виявилися не дуже ефективними, а також алгоритм складання деревовидних форм, але не поверхонь. На його думку, алгоритм Демейна і Точи досить складний, але це пов’язано більшою мірою з тим, що він є всеосяжним.