Тріангуляція многокутника

У обчислювальної геометрії тріангуляція многокутника — це розкладання полігональної області (простого многокутника) P на множину трикутників[1], тобто знаходження множини трикутників, які попарно не перетинаються і об'єднання яких дорівнює P.

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

Тріангуляція многокутника без додаткових вершин

Згодом був запропонований ряд алгоритмів для тріангуляції многокутника.

Особливі випадки

42 можливих тріангуляції для опуклого семикутника (7-сторонній опуклий многокутник). Це число є 5-те число Каталана.

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

Загальна кількість способів тріангулювати опуклий n-кутник діагоналями, які не перетинаються буде (n–2)-ге число Каталана, яке дорівнює ${\displaystyle {\tfrac {(n)\cdot (n+1)\cdot \ldots \cdot (2n-4)}{(n-2)!}}}$. Розв'язок був знайдений Леонардом Ейлером[2].

Монотонний многокутник може бути тріангульований за лінійний час за допомогою алгоритму А. Фурньє^[en] і Д. Я. Монтуно[3], або алгоритмом Годфріда Туссена^[en][4].

Метод відтину вух

Кожен простий багатокутник має два вуха. Перше вухо, яке відтинається, затемнене.

Один із способів тріангуляції простого многокутника заснований на теоремі про два вуха, яка стверджує, що будь-який простий многокутник з не менш ніж чотирма вершинами без дірок має принаймні два «вуха», які є трикутниками, що можна відтяти, бо діагональ розташована повністю всередині многокутника[5]. Алгоритм зводиться до знаходження такого вуха, яке потім видаляється (це призводить до появи нового многокутника, який все ще відповідає наведеним умовам) і операція повторюється до тих пір, поки не залишиться тільки один трикутник.

Цей алгоритм простий в реалізації, але він виконується повільніше ніж деякі інші алгоритми і можливий тільки для многокутників без дірок. Реалізація, яка зберігає окремі списки опуклих і увігнутих вершин, буде виконуватися за O(n^2) час. Цей метод відомий як відтинання або відсікання вух. Ефективний алгоритм відсікання вух був запропонований Хоссама Ельгінді, Хейзелем Евереттом і Годфрідом Туссеном^[en][6].

Тріангуляція монотонного многокутника

Розбиття многокутника на монотонні многокутники.

Ланцюг C складений з відрізків називається монотонним щодо прямої L, якщо кожна пряма, ортогональна L, перетинає C не більше одного разу. Ми називаємо такі ланцюги монотонними ланцюгами. многокутник P буде монотонним відносно прямої L, якщо його межу можна розбити на два ланцюги, кожен з яких монотонний щодо L. Ми називаємо такі многокутники монотонними многокутниками. Ми говоримо, що многокутник P є горизонтально монотонним (або x-монотонним), якщо P монотонний відносно осі х.

Ми можемо тріангулювати монотонний многокутник за ${\displaystyle {\mathcal {O}}(n\log n)}$ час, де n — кількість вершин монотонного многокутника. Алгоритм описаний у розділі 3.3 книги М. Берг та інші, «Обчислювальна геометрія: алгоритми і програми» (2-е видання).

Розкладання простого многокутника на монотонні частини

Якщо простий многокутник не є монотонним, його можна зробити монотонним за час ${\displaystyle {\mathcal {O}}(n\log n)}$, якщо використати алгоритм замітаючої прямої. Більш детально про це можна прочитати у розділі 3.2 книги М. Берг та інші, «Обчислювальна геометрія: алгоритми і програми» (2-е видання).

Двоїстий граф тріангуляції

Корисний граф, який часто асоціюється з тріангуляцією многокутника P, це двоїстий граф. Тріангуляція T_P многокутника P, визначає граф G(T_P), множина вершин якого є трикутниками T_P, причому дві вершини (трикутники) суміжні тоді і тільки тоді, коли відповідні їм трикутники мають спільну сторону. Легко помітити, що G(T_P) є деревом з вершинами максимальної степені 3.

Метод Фройденталя (тріангуляція Куна)

Тріангуляція ${\displaystyle K_{1}}$ є розбиттям на симплекси цілого простору ${\displaystyle \mathbb {R} ^{d}.}$ Для побудови ${\displaystyle K_{1}}$ увесь простір ${\displaystyle \mathbb {R} ^{d}}$ спочатку розбивається на куби, а потім кожний куб — на симплекси.

Для того, щоб перебір симплексів був організований належним чином, кожній вершині тріангуляції присвоюється деяка мітка. Мітки можуть бути або векторами (із дійсними координатами) або (скалярними) цілими числами й називаються відповідно векторними або цілочисельними. Векторні мітки частіше є векторами вигляду ${\displaystyle f(x)-x,}$ де ${\displaystyle x}$ — вершина тріангуляції. Чим більше точок або променів, уздовж яких алгоритм може покидати точку початку пошуку, тим вище його обчислювальна ефективність. Велика кількість міток має й зворотну сторону: чим більше міток, тим більше часу потрібно для їх обчислення. Для того, щоб симпліційний алгоритм був достатньо швидким, обчислення використовуваних ним міток повинні бути ефективними. Ефективність обчислення міток може бути забезпечена регулярністю розташування променів, уздовж яких алгоритм може покидати точку початку пошуку[7][8].

Обчислювальна складність

До 1988 року відкритим залишалось питання про те, чи можлива тріангуляція простого многокутника за час швидший ніж O(n log n)[1]. Поки Tarjan та Van Wyk, (1988) не знайшли алгоритм тріангуляції, який виконувався за час O(n log log n)[9], згодом спрощений Kirkpatrick, Klawe та Tarjan, (1992)[10]. Потім було декілька поліпшених методів зі складністю O(n log^* n) (на практиці не відрізнялись від лінійного часу)[11][12][13].

У 1991 році Бернард Шазель^[en] показав, що будь-який простий многокутник може бути тріангульований за лінійний час, хоча запропонований алгоритм був дуже складним[14]. Відомий також більш простий увипадковлений алгоритм з очікуваним лінійним часом виконання[15].

Алгоритм декомпозиції Зейделя і метод тріангуляції Шазеля детально обговорюються в Li та Klette, (2011)[16].

Часова складність алгоритму тріангуляції n-вершинного многокутника з дірками має нижню межу Ω(n log n)[1].

Пов'язані проблеми

• Тріангуляція многокутника є окремими задачами тріангуляції і розбиття многокутника^[en].
• Тріангуляція мінімальної ваги^[en] — така тріангуляція, в якій метою є мінімізація загальної довжини ребер.
• Тріангуляція множини точок — це тріангуляція многокутника, який є опуклою оболонкою цієї множини точок. Тріангуляція Делоне — ще один спосіб побудувати тріангуляцію множини точок.
• Покриття полігону^[en] трикутниками, в якому трикутники можуть перекриватися.
• Замощення многокутниками площини^[en], де мета полягає в тому, щоб покрити всю площину трикутниками заздалегідь визначеної форми.

Див. також

• Число Каталана
• Планарний граф

Примітки

1. Mark de Berg, Marc van Kreveld, Mark Overmars та Otfried Schwarzkopf (2000), Computational Geometry (вид. 2nd revised), Springer-Verlag, ISBN 3-540-65620-0 Chapter 3: Polygon Triangulation: pp.45–61.
2. Pickover, Clifford A., The Math Book, Sterling, 2009: p. 184.
3. Fournier, A.; Montuno, D. Y. (1984), Triangulating simple polygons and equivalent problems, ACM Transactions on Graphics, 3 (2): 153—174, doi:10.1145/357337.357341, ISSN 0730-0301
4. Toussaint, Godfried T. (1984), «A new linear algorithm for triangulating monotone polygons», Pattern Recognition Letters, 2 (March):155–158.
5. Meisters, G. H., «Polygons have ears.» American Mathematical Monthly 82 (1975). 648—651
6. ElGindy, H.; Everett, H.; Toussaint, G. T. (1993). Slicing an ear using prune-and-search. Pattern Recognition Letters. 14 (9): 719—722. doi:10.1016/0167-8655(93)90141-y.
7. Построение симплициального многогранника из куба - PDF Free Download (PDF). Архів оригіналу (PDF) за 9 червня 2020. Процитовано 9 червня 2020.
8. М. Н. Матвеев, “Симплициальный алгоритм поиска неподвижных точек с $2^d$ целочисленными метками”, Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки, 161, № 1, Изд-во Казанского ун-та, Казань, 2019, 127–144. www.mathnet.ru. Архів оригіналу за 9 червня 2020. Процитовано 9 червня 2020.
9. Tarjan, Robert E.; Van Wyk, Christopher J. (1988), An O(n log log n)-time algorithm for triangulating a simple polygon, SIAM Journal on Computing, 17 (1): 143—178, CiteSeerX 10.1.1.186.5949, doi:10.1137/0217010, MR 0925194.
10. Kirkpatrick, David G.; Klawe, Maria M.; Tarjan, Robert E. (1992), Polygon triangulation in O(n log log n) time with simple data structures, Discrete and Computational Geometry, 7 (4): 329—346, doi:10.1007/BF02187846, MR 1148949.
11. Clarkson, Kenneth L.; Tarjan, Robert; van Wyk, Christopher J. (1989), A fast Las Vegas algorithm for triangulating a simple polygon, Discrete and Computational Geometry, 4: 423—432, doi:10.1007/BF02187741.
12. Seidel, Raimund (1991), A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons, Computational Geometry: Theory and Applications, 1: 51—64, doi:10.1016/0925-7721(91)90012-4
13. Clarkson, Kenneth L.; Cole, Richard; Tarjan, Robert E. (1992), Randomized parallel algorithms for trapezoidal diagrams, International Journal of Computational Geometry & Applications, 2 (2): 117—133, doi:10.1142/S0218195992000081, MR 1168952.
14. Chazelle, Bernard (1991), Triangulating a Simple Polygon in Linear Time, Discrete & Computational Geometry, 6: 485—524, doi:10.1007/BF02574703, ISSN 0179-5376
15. Amato, Nancy M.; Goodrich, Michael T.; Ramos, Edgar A. (2001), A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time, Discrete & Computational Geometry, 26 (2): 245—265, doi:10.1007/s00454-001-0027-x, ISSN 0179-5376, архів оригіналу за 23 липня 2018, процитовано 22 липня 2018 [Архівовано 2018-07-23 у Wayback Machine.]
16. Li, Fajie; Klette, Reinhard (2011), Euclidean Shortest Paths, Springer, doi:10.1007/978-1-4471-2256-2, ISBN 978-1-4471-2255-5.

Додаткові джерела

• Demo as Flash swf, Алгоритм замітаючої прямої.
• Пояснення теселяції (розбиття) в OpenGL GLU від Song Ho [Архівовано 13 липня 2018 у Wayback Machine.]