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

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

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

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

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

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

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

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

Монотонний многокутник може бути тріангульований за лінійний час за допомогою алгоритму Шаблон:Нп і Д. Я. Монтуно^[3], або алгоритмом Шаблон:Нп^[4].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

До 1988 року відкритим залишалось питання про те, чи можлива тріангуляція простого многокутника за час швидший ніж Шаблон:Math^[1]. Поки Шаблон:Harvtxt не знайшли алгоритм тріангуляції, який виконувався за час Шаблон:Math^[9], згодом спрощений Шаблон:Harvtxt^[10]. Потім було декілька поліпшених методів зі складністю [[Повторний логарифм|Шаблон:Math]] (на практиці не відрізнялись від лінійного часу)^[11]^[12]^[13].

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

Алгоритм декомпозиції Зейделя і метод тріангуляції Шазеля детально обговорюються в Шаблон:Harvtxt^[16].

Часова складність алгоритму тріангуляції Шаблон:Math-вершинного многокутника з дірками має нижню межу Шаблон:Math^[1].

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

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

Див. також

Примітки

Шаблон:Reflist

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

Demo as Flash swf, Алгоритм замітаючої прямої.
Пояснення теселяції (розбиття) в OpenGL GLU від Song Ho Шаблон:Webarchive

↑ ^1,0 ^1,1 ^1,2 Шаблон:Citation Chapter 3: Polygon Triangulation: pp.45–61.
↑ Pickover, Clifford A., The Math Book, Sterling, 2009: p. 184.
↑ Шаблон:Citation
↑ Toussaint, Godfried T. (1984), «A new linear algorithm for triangulating monotone polygons», Pattern Recognition Letters, 2 (March):155–158.
↑ Meisters, G. H., «Polygons have ears.» American Mathematical Monthly 82 (1975). 648—651
↑ Шаблон:Cite journal
↑ Шаблон:Cite web
↑ Шаблон:Cite web
↑ Шаблон:Citation.
↑ Шаблон:Citation.
↑ Шаблон:Citation.
↑ Шаблон:Citation
↑ Шаблон:Citation.
↑ Шаблон:Citation
↑ Шаблон:Citation Шаблон:Webarchive
↑ Шаблон:Citation.

[bkos-1] 1,0 ^1,1 ^1,2 Шаблон:Citation Chapter 3: Polygon Triangulation: pp.45–61.

[2] Pickover, Clifford A., The Math Book, Sterling, 2009: p. 184.

[3] Шаблон:Citation

[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] Шаблон:Cite journal

[7] Шаблон:Cite web

[8] Шаблон:Cite web

[9] Шаблон:Citation.

[10] Шаблон:Citation.

[11] Шаблон:Citation.

[12] Шаблон:Citation

[13] Шаблон:Citation.

[14] Шаблон:Citation

[15] Шаблон:Citation Шаблон:Webarchive

[16] Шаблон:Citation.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

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

Зміст