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

В вычислительной геометрии триангуляция многоугольника — это разделение многоугольной области ( простого многоугольника ) $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),$ используя метод прогонки линий . Алгоритм не требует, чтобы многоугольник был простым, поэтому его можно применять к многоугольникам с отверстиями . Как правило, этот алгоритм может триангулировать плоское подразделение с $n$ вершинами за $время O(n log n),$ используя $O(n) .$ пространство ^{[ 1 ]}

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

Полезным графом, который часто ассоциируется с триангуляцией многоугольника $P,$ является двойственный граф . Учитывая триангуляцию $TP P$ причем $определяется как граф ,$ , граф $G (TP .)$ множество вершин которого являются треугольниками $TP,$ две вершины (треугольники) смежны тогда и только тогда, когда они имеют общую диагональ Легко заметить, что $) — дерево G(TP максимальной$ степени 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 ]} и метод триангуляции Шазеля подробно обсуждаются в Li & Klette (2011) . ^{[ 14 ]}

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

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

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

См. также

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и Марк де Берг , Марк ван Кревелд , Марк Овермарс и Отфрид Шварцкопф (2000), «3: Триангуляция полигонов», Вычислительная геометрия (2-е изд.), Springer-Verlag , стр. 45–61, ISBN 3-540-65620-0 {{citation}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Пиковер, Клиффорд А. (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
^ ЭльДжинди, Хосам; Эверетт, Хейзел; Туссен, Годфрид Т. (1993), «Отрезание уха с помощью обрезки и поиска», Pattern Recognition Letters , 14 (9): 719–722, Бибкод : 1993PaReL..14..719E , doi : 10.1016/0167- 8655(93)90141-у
^ Тарьян, Роберт Э .; Ван Вик, Кристофер Дж. (1988), «Алгоритм за время O ( n log log n ) для триангуляции простого многоугольника», SIAM Journal on Computing , 17 (1): 143–178, CiteSeerX 10.1.1.186.5949 , дои : 10.1137/0217010 , MR 0925194
^ Киркпатрик, Дэвид Г .; Клове, Мария М .; Тарьян, Роберт Э. (1992), «Триангуляция многоугольника за время O ( n log log n ) с простыми структурами данных», Discrete & Computational Geometry , 7 (4): 329–346, doi : 10.1007/BF02187846 , MR 1148949
^ Кларксон, Кеннет Л .; Тарьян, Роберт ; ван Вик, Кристофер Дж. (1989), «Быстрый алгоритм Лас-Вегаса для триангуляции простого многоугольника», Discrete & Computational Geometry , 4 (5): 423–432, doi : 10.1007/BF02187741
^ Перейти обратно: ^а ^б Зайдель, Раймунд (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), «Рандомизированный алгоритм триангуляции простого многоугольника за линейное время», Discrete & Computational Geometry , 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. 35-й Международный Симп. Вычислительная геометрия , Международные труды Лейбница по информатике (LIPIcs), том. 129, Schloss Dagstuhl, стр. 33:1–33:17, arXiv : 1903.04737 , doi : 10.4230/LIPIcs.SoCG.2019.33 , ISBN 9783959771047 , S2CID 75136891

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

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

[bkos-1] Перейти обратно: ^а ^б ^с ^д ^и Марк де Берг , Марк ван Кревелд , Марк Овермарс и Отфрид Шварцкопф (2000), «3: Триангуляция полигонов», Вычислительная геометрия (2-е изд.), Springer-Verlag , стр. 45–61, ISBN 3-540-65620-0 {{citation}}: CS1 maint: несколько имен: список авторов ( ссылка )

[2] Пиковер, Клиффорд А. (2009), The Math Book , Sterling, стр. 184

[3] Фурнье, Ален ; Монтуно, Дельфин Ю. (1984), «Триангуляция простых многоугольников и эквивалентные проблемы», ACM Transactions on Graphics , 3 (2): 153–174, doi : 10.1145/357337.357341 , ISSN 0730-0301 , S2CID 33344266

[4] Туссен, Годфрид Т. (1984), «Новый линейный алгоритм триангуляции монотонных многоугольников», Pattern Recognition Letters , 2 (3): 155–158, Bibcode : 1984PaReL...2..155T , doi : 10.1016/0167- 8655(84)90039-4

[5] Мейстерс, Гэри Хослер (1975), «У многоугольников есть уши» , American Mathematical Monthly , 82 (6): 648–651, doi : 10.2307/2319703 , JSTOR 2319703

[6] ЭльДжинди, Хосам; Эверетт, Хейзел; Туссен, Годфрид Т. (1993), «Отрезание уха с помощью обрезки и поиска», Pattern Recognition Letters , 14 (9): 719–722, Бибкод : 1993PaReL..14..719E , 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 , дои : 10.1137/0217010 , MR 0925194

[8] Киркпатрик, Дэвид Г .; Клове, Мария М .; Тарьян, Роберт Э. (1992), «Триангуляция многоугольника за время O ( n log log n ) с простыми структурами данных», Discrete & Computational Geometry , 7 (4): 329–346, doi : 10.1007/BF02187846 , MR 1148949

[9] Кларксон, Кеннет Л .; Тарьян, Роберт ; ван Вик, Кристофер Дж. (1989), «Быстрый алгоритм Лас-Вегаса для триангуляции простого многоугольника», Discrete & Computational Geometry , 4 (5): 423–432, doi : 10.1007/BF02187741

[Seidel-10] Перейти обратно: ^а ^б Зайдель, Раймунд (1991), «Простой и быстрый инкрементальный рандомизированный алгоритм для вычисления трапециевидных разложений и триангуляции многоугольников», Computational Geometry , 1 : 51–64, CiteSeerX 10.1.1.55.5877 , doi : 10.1016/0925-7721(91)90012-4

[11] Кларксон, Кеннет Л .; Коул, Ричард; Тарьян, Роберт Э. (1992), «Рандомизированные параллельные алгоритмы для трапециевидных диаграмм», Международный журнал вычислительной геометрии и приложений , 2 (2): 117–133, doi : 10.1142/S0218195992000081 , MR 1168952

[12] Шазель, Бернар (1991), «Триангуляция простого многоугольника за линейное время», Дискретная и вычислительная геометрия , 6 (3): 485–524, doi : 10.1007/BF02574703 , ISSN 0179-5376

[13] Амато, Нэнси М .; Гудрич, Майкл Т .; Рамос, Эдгар А. (2001), «Рандомизированный алгоритм триангуляции простого многоугольника за линейное время», Discrete & Computational Geometry , 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 Transactions on Modeling and Computer Simulation , 4 (3): 267–278, doi : 10.1145/189443.189446 , S2CID 14039662

[16] Эппштейн, Дэвид (2019), «Подсчет триангуляции многоугольника труден», Proc. 35-й Международный Симп. Вычислительная геометрия , Международные труды Лейбница по информатике (LIPIcs), том. 129, Schloss Dagstuhl, стр. 33:1–33:17, arXiv : 1903.04737 , doi : 10.4230/LIPIcs.SoCG.2019.33 , ISBN 9783959771047 , S2CID 75136891

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]