Про тріангуляцію Делоне та діаграму Вороного
Ця симуляція демонструє тріангуляцію Делоне — спосіб з'єднати набір точок у трикутники без накладань так, щоб жодна точка не потрапляла всередину описаного кола жодного трикутника. Побудова виконується покроковим алгоритмом Бовьє-Ватсона: він додає точки одну за одною і щоразу перебудовує тріангуляцію, видаляючи та заново з'єднуючи ті трикутники, чиї описані кола охопили нову точку. Ви можете інтерактивно додавати, перетягувати й видаляти точки, спостерігаючи, як сітка оновлюється в реальному часі, а також увімкнути діаграму Вороного — геометрично двоїсту до тріангуляції Делоне структуру.
Тріангуляцію Делоне запропонував Борис Делоне у 1934 році, і відтоді вона стала наріжним каменем обчислювальної геометрії: її застосовують у побудові сіток для методу скінченних елементів, моделюванні рельєфу, комп'ютерній графіці, плануванні маршрутів роботів і геоінформаційних системах.
Часті запитання
Що таке тріангуляція Делоне?
Тріангуляція Делоне для набору точок — це єдина (для точок у загальному положенні) тріангуляція, в якій описане коло кожного трикутника не містить всередині жодної іншої точки з набору. Ця властивість "порожнього описаного кола" гарантує, що тріангуляція максимізує мінімальний кут серед усіх трикутників, утворюючи найбільш "рівносторонню" з можливих сіток для заданого набору точок.
Як взаємодіяти з цією симуляцією?
Клікніть у будь-якому місці полотна, щоб додати нову точку, і подивіться, як тріангуляція миттєво перебудовується. Перетягуйте наявні точки, щоб динамічно змінювати форму сітки. Клацніть правою кнопкою миші на точці, щоб видалити її. У панелі керування можна перемикатися між випадковим, сітковим і круговим розташуванням точок, вмикати накладення діаграми Вороного, показувати описані кола при наведенні, підсвічувати опуклу оболонку та зафарбовувати окремі трикутники. Кнопка "Анімувати побудову" відтворює послідовність вставки точок алгоритмом Бовьє-Ватсона крок за кроком.
Що означає властивість "порожнього описаного кола" і чому вона важлива?
Кожен трикутник у тріангуляції Делоне має єдине описане коло, що проходить через усі три його вершини. Умова Делоне вимагає, щоб жодна інша вхідна точка не потрапляла суворо всередину цього кола. Увімкніть "Описане коло при наведенні" і проведіть мишею над трикутниками, щоб перевірити це: підказка показує "Описане коло порожнє ✓", коли умова виконується. Ця властивість безпосередньо означає, що мінімальний кут у тріангуляції є максимально можливим, а це робить обчислення на такій сітці стабільнішими й точнішими.
Як працює алгоритм Бовьє-Ватсона?
Алгоритм Бовьє-Ватсона додає точки одну за одною до вже існуючої тріангуляції. Спочатку будується великий "супертрикутник", що охоплює всі вхідні точки. Для кожної нової точки алгоритм знаходить усі трикутники, чиє описане коло містить цю точку ("погані" трикутники), видаляє їх, утворюючи зіркоподібну порожнину, а тоді з'єднує нову точку з кожним ребром цієї порожнини, створюючи нові трикутники. Наприкінці видаляються всі трикутники, що мають спільну вершину із супертрикутником. Очікуваний час роботи алгоритму — O(n log n) для випадкових наборів точок і O(n у квадраті) у найгіршому випадку.
Що таке діаграма Вороного і як вона пов'язана з тріангуляцією Делоне?
Діаграма Вороного розбиває площину на області — по одній на кожну вхідну точку, — де кожна область містить усі місця, ближчі до цієї точки, ніж до будь-якої іншої. Тріангуляція Делоне та діаграма Вороного є геометрично двоїстими одна до одної: центр описаного кола кожного трикутника Делоне стає вершиною діаграми Вороного, а з'єднання центрів описаних кіл сусідніх трикутників (тих, що мають спільне ребро) прокреслює ребра Вороного. Увімкніть "Діаграму Вороного" в симуляції, щоб накласти обидві структури одночасно й побачити, як кожна вершина Вороного точно збігається з центром описаного кола трикутника Делоне.
Де тріангуляція Делоне застосовується в реальному світі?
Тріангуляція Делоне лежить в основі побудови сіток скінченних елементів у симуляціях механіки конструкцій і гідродинаміки, де добре сформовані трикутники підвищують точність розв'язувачів. Її використовують у геоінформаційних системах для побудови триангульованих нерегулярних мереж (TIN) для моделей рельєфу місцевості. У комп'ютерній графіці її застосовують для реконструкції поверхонь із хмар точок, альфа-форм та розкладки текстур. У плануванні бездротових і мобільних мереж клітини Вороного (двоїсту структуру) використовують для моделювання зон покриття та меж передачі обслуговування між базовими станціями.
Чи завжди тріангуляція Делоне дає єдиний результат?
Для точок у "загальному положенні" — тобто коли жодні чотири точки не лежать точно на одному колі — тріангуляція Делоне єдина. Коли чотири або більше точок лежать на спільному колі (вироджена конфігурація), між кількома допустимими тріангуляціями немає строгої переваги, тож результат залежить від правил розв'язання нічиїх. Симуляція вирішує це, додаючи крихітне випадкове зміщення до координат точок під час обчислення за алгоритмом Бовьє-Ватсона, що забезпечує стабільний результат навіть для симетричних розташувань, як-от регулярні сітки або кола.
Хто і коли відкрив тріангуляцію Делоне?
Тріангуляцію названо на честь Бориса Миколайовича Делоне, радянського математика, який формально визначив і довів цю побудову у своїй статті 1934 року "Sur la sphere vide". Дуальну діаграму до нього ще в 1908 році описав Георгій Вороний. Покроковий алгоритм Бовьє-Ватсона, який реалізовано в цій симуляції, незалежно відкрили Адріан Бовьє та Девід Ватсон у 1981 році, зробивши метод достатньо ефективним для практичного інтерактивного застосування.
Які структури обчислювальної геометрії з нею пов'язані?
До тісно пов'язаних структур належать опукла оболонка (зовнішня межа тріангуляції Делоне, яку можна показати, увімкнувши "Опуклу оболонку" в цій симуляції), граф Габріеля (підграф ребер Делоне, у якого коло з діаметром на кожному ребрі порожнє) та мінімальне остовне дерево (завжди є підграфом тріангуляції Делоне). У вищих вимірах тріангуляція Делоне узагальнюється до тетраедризації Делоне в 3D, необхідної для побудови об'ємних сіток в обчислювальній інженерії.
Як тріангуляцію Делоне застосовують в інженерії та технологіях?
У методі скінченних елементів (МСЕ) погано сформовані трикутники з дуже малими кутами спричиняють погано обумовлені матриці жорсткості й числову нестабільність; побудова сітки за Делоне з подальшим уточненням за алгоритмами на кшталт алгоритму Рупперта гарантує мінімальну межу кута (як правило, понад 20 градусів) для всієї сітки. У комп'ютерному зорі тріангуляція Делоне для точок обличчя утворює сітку, яку використовують для деформації, морфінгу обличчя та фільтрів доповненої реальності. Геопросторове програмне забезпечення на кшталт QGIS та ArcGIS застосовує її для інтерполяції висотних даних і побудови ізоліній із розрізнених даних вимірювань.
Які напрямки досліджень тріангуляції Делоне актуальні зараз?
Активні дослідження охоплюють паралельну та прискорену на GPU побудову тріангуляції Делоне для дуже великих наборів точок (мільярди точок у наукових симуляціях), динамічні структури Делоне, що підтримують ефективне додавання та видалення точок у потокових сценаріях або сценаріях з рухомими точками, а також анізотропну побудову сіток, де форма трикутників адаптується до напрямку в базовій області (наприклад, пограничні шари в гідродинаміці). Триває також робота над зваженими тріангуляціями Делоне (діаграмами потужності) та їх застосуванням в оптимальному транспортуванні й геометрії машинного навчання.