WikiSort.ru - Не сортированное

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

Задача о триангуляции многоугольника — классическая задача комбинаторной и вычислительной геометрии, состоящая в нахождении триангуляции многоугольника без дополнительных вершин.

Доказательство существования такой триангуляции не представляет сложности. Более того, эта задача всегда имеет решение для многоугольников с дырками, то есть областей плоскости, ограниченных несколькими замкнутыми ломаными.

Формулировка

Задача состоит в нахождении оптимального алгоритма триангуляции n-угольника без дополнительных вершин.

Эта задача может быть решена за линейное время, то есть задача имеет сложность $O(n)$ .

История

Долгое время был открытым вопрос, можно ли найти триангуляцию n-угольника за время, меньше, чем $O(n\log n)$ .^[1] Затем Ван Вик (1988) обнаружил алгоритм, требующий время $O(n\log \log n)$ ,^[2] позже упрощённый Киркпатриком и Клаве.^[3] Затем последовало несколько алгоритмов со сложностью $O(n\log ^{*}n)$ (где $\log ^{*}n$ — итерированный логарифм), не отличимых на практике от линейного времени.^[4]^[5]^[6]

В 1991 году Бернард Чазелле доказал, что любой простой многоугольник может быть триангулирован в линейное время, хотя предложенный им алгоритм оказался очень сложным.^[7] Также известен более простой вероятностный алгоритм с линейным ожидаемым временем.^[8]^[9]

Алгоритмы

Отрезание ушей

Двойственный граф триангуляции без дополнительных вершин у простого многоугольника всегда является деревом. Отсюда в частности следует, что любой простой n-угольник с n > 3 имеет по меньшей мере два уха, то есть два треугольника, две стороны каждого из которых являются сторонами многоугольника, а третья полностью внутри него.^[10]

Один из способов триангуляции состоит в нахождении такого уха и отрезании его от многоугольника. После этого ту же операцию повторно применяют к оставшемуся многоугольнику до тех пор, пока не останется один треугольник.

Этот способ работает только для многоугольников без дырок. Он прост в реализации, но работает медленнее, чем некоторые другие алгоритмы. Реализация, которая хранит отдельные списки выпуклых и вогнутых вершин, работает за время $O(n^{2})$ .

Эффективный алгоритм для отрезания ушей был предложен Хоссамом Эль-Гинди, Хэзелом Эвереттом и Годфридом Туссеном.^[11]

Через монотонные многоугольники

Многоугольник называется монотонным, если его граничная ломаная имеет не более двух точек пересечения с прямой, перпендикулярной данной.

Монотонный многоугольник может быть триангулирован за линейное время с помощью алгоритма А. Фурнье и Д. Ю. Монтуно^[12] или алгоритма Годфрид Туссен.^[13]

Произвольный многоугольник может быть подразбит на монотонные. Алгоритм триангуляции простого многоугольника, построенный на этой идее, работает за время $O(n\cdot \log n)$ .

Вариации и обобщения

Многогранник Шёнхардта не допускает триангуляции без дополнительных вершин

Триангуляция многогранника без дополнительных вершин существует не всегда. Например Многогранник Шёнхардта, см. рисунок.
Выпуклый многоугольник является тривиальной задачей триангуляции. Она решается в линейное время. Можно провести диагонали из одной вершины ко всем другим вершинам.
- Общее число способов триангулировать выпуклый n-угольник диагоналями равно числу Каталана
  ${\tfrac {n\cdot (n+1)\cdots (2n-4)}{(n-2)!}}.$

Последнее было доказано Эйлером.^[14]

Примечания

↑ Mark de Berg, Marc van Kreveld, Mark Overmars and Otfried Schwarzkopf (2000), Computational Geometry (2nd revised ed.), Springer-Verlag, ISBN 3-540-65620-0
↑ 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, DOI 10.1137/0217010 .
↑ 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 .
↑ 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 .
↑ Chazelle, Bernard (1991), "Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry Т. 6: 485–524, ISSN 0179-5376, DOI 10.1007/BF02574703
↑ 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, ISSN 0179-5376, doi:10.1007/s00454-001-0027-x, <http://parasol.tamu.edu/publications/abstract.php?pub_id=185>
↑ Li, Fajie & Klette, Reinhard (2011), Euclidean Shortest Paths, Springer, ISBN 978-1-4471-2255-5, DOI 10.1007/978-1-4471-2256-2 .
↑ Meisters, G. H., «Polygons have ears.»
↑ 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.
↑ Fournier, A. & Montuno, D. Y. (1984), "Triangulating simple polygons and equivalent problems", ACM Transactions on Graphics Т. 3 (2): 153–174, ISSN 0730-0301, DOI 10.1145/357337.357341
↑ Toussaint, Godfried T. (1984), "A new linear algorithm for triangulating monotone polygons, " Pattern Recognition Letters, 2 (March):155-158.
↑ Pickover, Clifford A., The Math Book, Sterling, 2009: p. 184.

Ссылки

Demo as Flash swf, A Sweep Line algorithm.
Song Ho’s explanation of the OpenGL GLU tesselator

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .

Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2025
WikiSort.ru - проект по пересортировке и дополнению контента Википедии

[bkos-1] Mark de Berg, Marc van Kreveld, Mark Overmars and Otfried Schwarzkopf (2000), Computational Geometry (2nd revised ed.), Springer-Verlag, ISBN 3-540-65620-0

[2] 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, DOI 10.1137/0217010 .

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

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

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

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

[7] Chazelle, Bernard (1991), "Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry Т. 6: 485–524, ISSN 0179-5376, DOI 10.1007/BF02574703

[8] 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, ISSN 0179-5376, doi:10.1007/s00454-001-0027-x, <http://parasol.tamu.edu/publications/abstract.php?pub_id=185>

[9] Li, Fajie & Klette, Reinhard (2011), Euclidean Shortest Paths, Springer, ISBN 978-1-4471-2255-5, DOI 10.1007/978-1-4471-2256-2 .

[10] Meisters, G. H., «Polygons have ears.»

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

[12] Fournier, A. & Montuno, D. Y. (1984), "Triangulating simple polygons and equivalent problems", ACM Transactions on Graphics Т. 3 (2): 153–174, ISSN 0730-0301, DOI 10.1145/357337.357341

[13] Toussaint, Godfried T. (1984), "A new linear algorithm for triangulating monotone polygons, " Pattern Recognition Letters, 2 (March):155-158.

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