Тріангуляція многокутника: відмінності між версіями

[неперевірена версія]

← Попереднє редагування Наступне редагування →

Вилучено вміст Додано вміст

Лінійно

Версія за 08:13, 22 липня 2018

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

До 1988 року відкритим залишалось питання про те, чи можлива тріангуляція простого багатокутника за час швидший ніж $O(n log n)$ .^[1] Поки Помилка скрипту: Функції «harvard_core» не існує. не знайшли алгоритм тріангуляції, який виконувався за час $O(n log log n)$ ,^[7] згодом спрощений Помилка скрипту: Функції «harvard_core» не існує..^[8] Потім було декілька поліпшених методів зі складністю $O(n log * n)$ (на практиці не відрізнялись від лінійного часу) followed.^[9]^[10]^[11]

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

Алгоритм декомпозиції Зейделя і метод тріангуляції Шазеля детально обговорюються в Помилка скрипту: Функції «harvard_core» не існує.. ^[14]

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

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

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

Примітки

↑ ^а ^б ^в Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000), Computational Geometry (вид. 2nd revised), Springer-Verlag, ISBN 3-540-65620-0 Chapter 3: Polygon Triangulation: pp.45–61.
↑ Pickover, Clifford A., The Math Book, Sterling, 2009: p. 184.
↑ 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
↑ 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
↑ 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.
↑ 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.
↑ 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.
↑ 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.
↑ 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
↑ 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.
↑ Chazelle, Bernard (1991), Triangulating a Simple Polygon in Linear Time, Discrete & Computational Geometry, 6: 485—524, doi:10.1007/BF02574703, ISSN 0179-5376
↑ 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
↑ Li, Fajie; Klette, Reinhard (2011), Euclidean Shortest Paths, Springer, doi:10.1007/978-1-4471-2256-2, ISBN 978-1-4471-2255-5.

[bkos-1] а ^б ^в Mark de Berg, Marc van Kreveld, Mark Overmars, and 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] 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.

[8] 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.

[9] 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.

[10] 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

[11] 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.

[12] Chazelle, Bernard (1991), Triangulating a Simple Polygon in Linear Time, Discrete & Computational Geometry, 6: 485—524, doi:10.1007/BF02574703, ISSN 0179-5376

[13] 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

[14] Li, Fajie; Klette, Reinhard (2011), Euclidean Shortest Paths, Springer, doi:10.1007/978-1-4471-2256-2, ISBN 978-1-4471-2255-5.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

@@ Рядок 33: / Рядок 33: @@
 == Обчислювальна складність ==
+До 1988 року відкритим залишалось питання про те, чи можлива тріангуляція  простого багатокутника за час швидший ніж {{math|O(<var>n</var> log <var>n</var>)}}.<ref name= bkos/> Поки {{harvtxt|Tarjan|Van Wyk|1988}} не знайшли алгоритм тріангуляції, який виконувався за час {{math|O(<var>n</var> log log <var>n</var>)}},<ref>{{citation
-До 1988 року, коли простий багатокутник може бути тріангулійован швидше, ніж
+ | last1 = Tarjan | first1 = Robert E. | author1-link = Роберт Андре Тарджан
-O (n log n), час був відкритою проблемою в обчислювальної геометрії. [1] Потім Тар'ян і Ван Вайк (Tarjan & Van Wyk, 1988) виявили алгоритм O (n log log n) для тріангуляції, пізніше спрощений Кіркпатріком, Клауе і Тарьяном (1992). Кілька поліпшених методів зі складністю O (n log * n) (на практиці, не відрізняються від лінійного часу).
+ | last2 = Van Wyk | first2 = Christopher J.
+ | doi = 10.1137/0217010
+ | issue = 1
+ | journal = [[SIAM Journal on Computing]]
+ | mr = 925194
+ | pages = 143–178
+ | title = An O(''n'' log log ''n'')-time algorithm for triangulating a simple polygon
+ | volume = 17
+ | year = 1988| citeseerx = 10.1.1.186.5949}}.</ref> згодом спрощений {{harvtxt|Kirkpatrick|Klawe|Tarjan|1992}}.<ref>{{citation
+ | last1 = Kirkpatrick | first1 = David G. | author1-link = David G. Kirkpatrick
+ | last2 = Klawe | first2 = Maria M. | author2-link = Maria Klawe
+ | last3 = Tarjan | first3 = Robert E. | author3-link = Роберт Андре Тарджан
+ | doi = 10.1007/BF02187846
+ | issue = 4
+ | journal = [[Discrete and Computational Geometry]]
+ | mr = 1148949
+ | pages = 329–346
+ | title = Polygon triangulation in O(''n'' log log ''n'') time with simple data structures
+ | volume = 7
+ | year = 1992}}.</ref> Потім було декілька поліпшених методів зі складністю [[Повторний логарифм|{{math|O(<var>n</var> log<sup>*</sup> <var>n</var>)}}]] (на практиці не відрізнялись від лінійного часу) followed.<ref>{{citation
+ | last1 = Clarkson | first1 = Kenneth L. | author1-link = Kenneth L. Clarkson
+ | last2 = Tarjan | first2 = Robert | author2-link = Роберт Андре Тарджан
+ | last3 = van Wyk | first3 = Christopher J.
+ | doi = 10.1007/BF02187741
+ | journal = [[Discrete and Computational Geometry]]
+ | pages = 423–432
+ | title = A fast Las Vegas algorithm for triangulating a simple polygon
+ | volume = 4
+ | year = 1989}}.</ref><ref>{{Citation |last=Seidel|first=Raimund |author-link= Raimund Seidel| title=A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons |journal=[[Computational Geometry (journal)|Computational Geometry: Theory and Applications]] |volume=1 |year=1991 |pages=51–64 |doi=10.1016/0925-7721(91)90012-4}}</ref><ref>{{citation
+ | last1 = Clarkson | first1 = Kenneth L. | author1-link = Kenneth L. Clarkson
+ | last2 = Cole | first2 = Richard
+ | last3 = Tarjan | first3 = Robert E. | author3-link = Роберт Андре Тарджан
+ | doi = 10.1142/S0218195992000081
+ | issue = 2
+ | journal = International Journal of Computational Geometry & Applications
+ | mr = 1168952
+ | pages = 117–133
+ | title = Randomized parallel algorithms for trapezoidal diagrams
+ | volume = 2
+ | year = 1992}}.</ref>
-У 1991 році Бернард Шазель показав, що будь-який простий багатокутник може бути тріангулійован в лінійному часу, хоча запропонований алгоритм дуже складний.  Відомий також більш простий рандомізований алгоритм з лінійним очікуваним часом.
+У 1991 році {{Нп|Бернард Шазель|||Bernard Chazelle}} показав, що будь-який простий багатокутник може бути тріангульований за лінійний час, хоча запропонований алгоритм був дуже складним.<ref>{{Citation |last=Chazelle |first=Bernard |author-link=Bernard Chazelle | title=Triangulating a Simple Polygon in Linear Time |journal=Discrete & Computational Geometry |volume=6 |year=1991|pages=485–524 |issn=0179-5376 |doi=10.1007/BF02574703}}</ref> Відомий також більш простий рандомізований алгоритм з очикуваним лінійним часом виконання.<ref>{{Citation |last1=Amato |first1=Nancy M. | author1-link = Nancy M. Amato |last2=Goodrich |first2=Michael T. |author2-link=Michael T. Goodrich|last3=Ramos |first3=Edgar A. |title=A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time |journal=Discrete & Computational Geometry |volume=26 |year=2001 <!--|month=May--> |pages=245–265 |issn=0179-5376 |doi=10.1007/s00454-001-0027-x |url=http://parasol.tamu.edu/publications/abstract.php?pub_id=185 |issue=2}}</ref>
-Алгоритм декомпозиції Зейделя і метод тріангуляції Шазель детально обговорюються в Li & Klette (2011).
+Алгоритм декомпозиції Зейделя і метод тріангуляції Шазеля детально обговорюються в {{harvtxt|Li|Klette|2011}}.
-Тимчасова складність тріангуляції n-вершинного багатокутника з дірками має нижню межу Ω (n log n).
+<ref>{{citation
+ | last1 = Li | first1 = Fajie
+ | last2 = Klette | first2 = Reinhard
+ | title = Euclidean Shortest Paths
+ | publisher = [[Springer (publisher)|Springer]]
+ | doi = 10.1007/978-1-4471-2256-2
+ | ISBN = 978-1-4471-2255-5
+ | year = 2011}}.</ref>
+{{Нп|Часова складність алгоритму|||Time complexity}} тріангуляції {{math|<var>n</var>}}-вершинного багатокутника з дірками має [[Нижня межа|нижню межу]] {{math|Ω(<var>n</var> log <var>n</var>)}}.<ref name= bkos/>
 == Пов'язані проблеми ==

Тріангуляція многокутника: відмінності між версіями

Версія за 08:13, 22 липня 2018

Зміст