Триангуляция полигона

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

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

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

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

Особые случаи

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

Общее число способов триангуляции выпуклого n- угольника непересекающимися диагоналями равно ( n −2)-му числу Каталана , которое равно

{\frac {n(n+1)...(2n-4)}{(n-2)!}}

формула, найденная Леонардом Эйлером . ^[2]

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

Метод обрезки ушей

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

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

Монотонная полигональная триангуляция

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

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

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

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

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

Полезный граф, который часто ассоциируется с триангуляцией многоугольника $P$ , — это двойственный граф . Если задана триангуляция $T P$ многоугольника $P$ , то граф $G (T P)$ определяется как граф, множество вершин которого — треугольники $T P$ , причем две вершины (треугольники) являются смежными тогда и только тогда, когда они имеют общую диагональ. Легко заметить, что $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]

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

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

Связанные объекты и проблемы

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

Смотрите также

Ссылки

^ abcde Марк де Берг , Марк ван Кревелд , Марк Овермарс и Отфрид Шварцкопф (2000), «3: Триангуляция полигонов», Вычислительная геометрия (2-е изд.), Springer-Verlag , стр. 45–61, ISBN 3-540-65620-0{{citation}}: CS1 maint: multiple names: authors list (link)
^ Пиковер, Клиффорд А. (2009), The Math Book , Sterling, стр. 184
^ Фурнье, Ален ; Монтуно, Дельфин И. (1984), «Триангуляция простых многоугольников и эквивалентные проблемы», ACM Transactions on Graphics , 3 (2): 153–174, doi : 10.1145/357337.357341 , ISSN 0730-0301, S2CID 33344266
^ Туссен, Годфрид Т. (1984), «Новый линейный алгоритм триангуляции монотонных многоугольников», Pattern Recognition Letters , 2 (3): 155–158, Bibcode : 1984PaReL...2..155T, doi : 10.1016/0167-8655(84)90039-4
↑ Мейстерс, Гэри Хослер (1975), «У многоугольников есть уши», American Mathematical Monthly , 82 (6): 648–651, doi :10.2307/2319703, JSTOR 2319703
^ ElGindy, Hossam; Everett, Hazel; Toussaint, Godfried T. (1993), «Нарезка уха с помощью prune-and-search», Pattern Recognition Letters , 14 (9): 719–722, Bibcode : 1993PaReL..14..719E, doi : 10.1016/0167-8655(93)90141-y
^ Тарьян, Роберт Э .; Ван Вик, Кристофер Дж. (1988), « Алгоритм триангуляции простого многоугольника с временем O( n log log n )», SIAM Journal on Computing , 17 (1): 143–178, CiteSeerX 10.1.1.186.5949 , doi :10.1137/0217010, MR 0925194
^ Киркпатрик, Дэвид Г .; Клэве, Мария М .; Тарьян, Роберт Э. (1992), «Триангуляция многоугольника за время O( n log log n ) с простыми структурами данных», Дискретная и вычислительная геометрия , 7 (4): 329–346, doi : 10.1007/BF02187846 , MR 1148949
^ Кларксон, Кеннет Л .; Тарьян, Роберт ; ван Вик, Кристофер Дж. (1989), «Быстрый алгоритм Лас-Вегаса для триангуляции простого многоугольника», Дискретная и вычислительная геометрия , 4 (5): 423–432, doi : 10.1007/BF02187741
^ ab Seidel, Raimund (1991), "Простой и быстрый инкрементальный рандомизированный алгоритм для вычисления трапециевидных разложений и триангуляции многоугольников", Computational Geometry , 1 : 51–64, CiteSeerX 10.1.1.55.5877 , doi : 10.1016/0925-7721(91)90012-4
^ Кларксон, Кеннет Л .; Коул, Ричард; Тарьян, Роберт Э. (1992), «Рандомизированные параллельные алгоритмы для трапециевидных диаграмм», Международный журнал вычислительной геометрии и приложений , 2 (2): 117–133, doi :10.1142/S0218195992000081, MR 1168952
^ Шазелл, Бернар (1991), «Триангуляция простого многоугольника за линейное время», Дискретная и вычислительная геометрия , 6 (3): 485–524, doi : 10.1007/BF02574703 , ISSN 0179-5376
^ Амато, Нэнси М .; Гудрич, Майкл Т .; Рамос, Эдгар А. (2001), «Рандомизированный алгоритм триангуляции простого многоугольника за линейное время», Дискретная и вычислительная геометрия , 26 (2): 245–265, doi : 10.1007/s00454-001-0027-x , ISSN 0179-5376
^ Ли, Фаджи; Клетте, Рейнхард (2011), Кратчайшие евклидовы пути , Springer , doi : 10.1007/978-1-4471-2256-2, ISBN 978-1-4471-2255-5
^ Эпштейн, Питер; Сак, Йорг-Рюдигер (1994), «Случайное создание триангуляций», ACM Transactions on Modeling and Computer Simulation , 4 (3): 267–278, doi :10.1145/189443.189446, S2CID 14039662
^ Эппштейн, Дэвид (2019), «Подсчет триангуляций полигонов — сложная задача», Proc. 35nd Int. Symp. Computational Geometry , Leibniz International Proceedings in Informatics (LIPIcs), т. 129, Schloss Dagstuhl, стр. 33:1–33:17, arXiv : 1903.04737 , doi : 10.4230/LIPIcs.SoCG.2019.33 , ISBN 9783959771047, S2CID 75136891

Внешние ссылки

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