Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Для более широкого освещения этой темы см. Триангуляция (геометрия) .
Триангуляция многоугольника.

В вычислительной геометрии , Многоугольник триангуляции является разложение многоугольной области ( простой многоугольника ) P на множество треугольников , [1] то есть, найти множество треугольников с попарно непересекающихся интерьеров , чей союз является Р .

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

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

Со временем был предложен ряд алгоритмов для триангуляции многоугольника.

Особые случаи [ править ]

42 возможных триангуляции для выпуклого семиугольника (7-сторонний выпуклый многоугольник). Это число обозначается пятым каталонским числом .

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

Общее количество способов триангулировать выпуклый n -угольник непересекающимися диагоналями - это ( n −2) -ое каталонское число , которое равно решению, найденному Леонардом Эйлером . [2]

Монотонной многоугольник может быть триангулированным в линейное время либо с алгоритмом А. Fournier и DY Montuno, [3] или алгоритмом Godfried Туссен . [4]

Метод обрезки ушей [ править ]

Многоугольное ухо

Один из способов триангуляции простого многоугольника основан на теореме о двух ушах , так как тот факт, что любой простой многоугольник с как минимум 4 вершинами без отверстий имеет как минимум два ` ` уха '', которые представляют собой треугольники, две стороны которых являются краями многоугольника, и третий полностью внутри него. [5] Затем алгоритм состоит из поиска такого уха, удаления его из многоугольника (в результате получается новый многоугольник, который все еще соответствует условиям) и повторения до тех пор, пока не останется только один треугольник.

Этот алгоритм легко реализовать, но он работает медленнее, чем некоторые другие алгоритмы, и работает только с полигонами без дыр. Реализация, которая хранит отдельные списки выпуклых и вогнутых вершин, будет работать за O ( n 2 ) времени. Этот метод известен как стрижка ушей, а иногда и ушей . Эффективный алгоритм отрезания ушей был открыт Хоссамом Эль-Джинди, Хейзел Эверетт и Годфридом Туссеном . [6]

Монотонная триангуляция многоугольника [ править ]

Разбиение многоугольника на монотонные многоугольники

Простой многоугольник монотонен относительно прямой L , если любая прямая, ортогональная L, пересекает многоугольник не более двух раз. Монотонный многоугольник можно разбить на две монотонные цепочки . Многоугольник, монотонный относительно оси y, называется y-монотонным . Монотонный многоугольник с n вершинами можно триангулировать за O ( n ) раз. Предполагая, что данный многоугольник является y-монотонным, жадный алгоритм начинает с обхода одной цепочки многоугольника сверху вниз, добавляя диагонали всякий раз, когда это возможно. [1] Легко видеть, что алгоритм применим к любому монотонному многоугольнику.

Триангуляция немонотонного многоугольника [ править ]

Если многоугольник не является монотонным, он может быть разбит на монотонные подполигоны за время O ( n log n ), используя метод развертки . Алгоритм не требует, чтобы многоугольник был простым, поэтому его можно применять к многоугольникам с отверстиями. Как правило, этот алгоритм может триангулировать планарное подразделение с n вершинами за время O ( n log n ), используя пространство O ( n ) . [1]

Двойной график триангуляции [ править ]

Полезный граф, который часто ассоциируется с триангуляцией многоугольника P, - это двойственный граф . Учитывая триангуляцию Т Р из Р , один определяет граф G ( Т Р ) , как граф, множество вершин являются треугольники Т Р , две вершины (треугольники) , которые смежны тогда и только тогда , когда они имеют диагонали. Легко заметить, что G ( T P ) - дерево максимальной степени 3.

Вычислительная сложность [ править ]

До 1988 года вопрос о том, можно ли триангулировать простой многоугольник быстрее, чем за время O ( n log n ), оставался открытой проблемой вычислительной геометрии. [1] Затем Тарьян и Ван Вик (1988) открыли алгоритм триангуляции за O ( n log log n ) , [7] позже упрощенный Киркпатриком, Клаве и Тарьяном (1992) . [8] За этим последовало несколько улучшенных методов со сложностью O ( n log * n ) (на практике неотличимых от линейного времени ). [9][10] [11]

Бернар Шазель в 1991 году показал, что любой простой многоугольник можно триангулировать за линейное время, хотя предложенный алгоритм очень сложен. [12] Также известен более простой рандомизированный алгоритм с линейным ожидаемым временем. [13]

Алгоритм разложения Зейделя и метод триангуляции Шазеля подробно обсуждаются в Li & Klette (2011) .[14]

Временная сложность триангуляции с п -vertex многоугольника с отверстиями имеет Q ( п войти п ) нижняя граница , в алгебраических вычислений дерева моделей вычислений. [1] Можно вычислить количество различных триангуляций простого многоугольника за полиномиальное время с помощью динамического программирования и (на основе этого алгоритма подсчета) генерировать равномерно случайные триангуляции за полиномиальное время. [15] Однако подсчет триангуляций многоугольника с дырами является # P-полным., что делает маловероятным то, что это можно сделать за полиномиальное время. [16]

Связанные проблемы [ править ]

  • Обе задачи триангуляции являются частным случаем триангуляции (геометрии) и частным случаем разбиения многоугольника .
  • Триангуляция минимального веса - это триангуляция, цель которой - минимизировать общую длину ребра.
  • Множество точек триангуляции представляет собой многоугольник триангуляция выпуклой оболочки множества точек. Триангуляции Делоне еще один способ создать триангуляции на основе набора точек.
  • Покрытие многоугольным треугольником , в котором треугольники могут перекрываться.
  • Тайлинг по многоугольникам , цель которого - покрыть всю плоскость многоугольниками заданной формы.

См. Также [ править ]

  • Ненулевое правило
  • Каталонский номер
  • Планарный график

Ссылки [ править ]

  1. ^ a b c d e Марк де Берг , Марк ван Кревельд , Марк Овермарс и Отфрид Шварцкопф (2000), Вычислительная геометрия (2-е исправленное издание), Springer-Verlag , ISBN 3-540-65620-0CS1 maint: multiple names: authors list (link) Глава 3: Триангуляция многоугольника: стр.45–61.
  2. ^ Пиковер, Clifford A. , Математика книги , Sterling, 2009: с. 184.
  3. ^ Фурнье, А .; Montuno, DY (1984), "Триангулирующие простые многоугольники и эквивалентные проблемы", ACM Сделки на графике , 3 (2): 153-174, DOI : 10,1145 / 357337,357341 , ISSN 0730-0301 , S2CID 33344266  
  4. ^ Туссен, Годфрид Т. (1984), « Новый линейный алгоритм для триангуляции монотонных многоугольников », Письма о распознавании образов , 2 (март): 155–158.
  5. ^ Мейстер, Г. Х., «У многоугольников есть уши ». Американский математический ежемесячник 82 (1975). 648–651
  6. ^ ElGindy, H .; Everett, H .; Туссен, GT (1993). «Нарезка уха методом обрезки и поиска». Письма о распознавании образов . 14 (9): 719–722. DOI : 10.1016 / 0167-8655 (93) 90141-у .
  7. ^ Тарьян, Роберт Э .; Ван Вик, Кристофер Дж. (1988), « Алгоритм времени O ( n log log n ) для триангуляции простого многоугольника», SIAM Journal on Computing , 17 (1): 143–178, CiteSeerX 10.1.1.186.5949 , DOI : 10,1137 / 0217010 , МР 0925194  .
  8. ^ Киркпатрик, Дэвид Г .; Клаве, Мария М .; Тарьян, Роберт Е. (1992), "Многоугольник триангуляция в O ( п войти лог п ) время со структурами данных простых", Дискретная и Вычислительная геометрия , 7 (4): 329-346, DOI : 10.1007 / BF02187846 , МР 1148949 .
  9. ^ Кларксон, Кеннет Л .; Тарджан, Роберт ; ван Вик, Christopher J. (1989), "Быстрый Лас - Вегас алгоритм триангуляции простой многоугольник", Дискретная и вычислительная геометрия , 4 (5): 423-432, DOI : 10.1007 / BF02187741.
  10. ^ Зайдель, Раймунд (1991), «Простой и быстрый инкрементальный рандомизированный алгоритм для вычисления трапециевидных разложений и триангуляции многоугольников», Computational Geometry: Theory and Applications , 1 : 51–64, doi : 10.1016 / 0925-7721 (91) 90012 -4
  11. ^ Кларксон, Кеннет Л .; Коул, Ричард; Тарьян, Роберт Е. (1992), "Рандомизированные алгоритмы параллельных для трапециевидных диаграмм", Международный журнал вычислительной геометрии и приложений , 2 (2): 117-133, DOI : 10,1142 / S0218195992000081 , МР 1168952 .
  12. ^ Chazelle, Бернар (1991), "Триангулирующий простой многоугольник в линейном время", Дискретная & Вычислительная геометрия , 6 (3): 485-524, DOI : 10.1007 / BF02574703 , ISSN 0179-5376 
  13. ^ Амато, Нэнси М .; Гудрич, Майкл Т .; Рамос, Эдгар А. (2001), "Рандомизированное Алгоритм Триангулирующего простой многоугольника в линейном время" , дискретная и вычислительная геометрия , 26 (2): 245-265, DOI : 10.1007 / s00454-001-0027-X , ISSN 0179-5376 
  14. ^ Ли, Фэджи; Клетт, Рейнхард (2011), Евклидовы кратчайшие пути , Springer , DOI : 10.1007 / 978-1-4471-2256-2 , ISBN 978-1-4471-2255-5.
  15. ^ Эпштейн, Питер; Мешок, Йорг-Рюдигер (1994), "Генерирование триангуляции случайным", ACM Сделки по и компьютерное моделирование , 4 (3): 267-278, DOI : 10,1145 / 189443,189446 , S2CID 14039662 
  16. ^ Эппштейн, Дэвид (2019), «Подсчет триангуляций многоугольников - сложная задача», Proc. 35-й межд. Symp. Вычислительная геометрия , Лейбниц Международный Труды по информатике (LIPIcs), Замок Dagstuhl, стр ., 33: 1-33: 17, Arxiv : +1903,04737 , DOI : 10,4230 / LIPIcs.SoCG.2019.33 , S2CID 75136891 

Внешние ссылки [ править ]

  • Демонстрация как Flash swf , алгоритм развертки линии.
  • Объяснение Сон Хо тесселатора OpenGL GLU