Триангуляция многоугольника
В вычислительной геометрии триангуляция многоугольника — это разделение многоугольной области ( простого многоугольника ) P на набор треугольников , [1] т. е. найти набор треугольников с попарно непересекающимися внутренностями, объединение которых равно P .
Триангуляции можно рассматривать как частные случаи плоских прямолинейных графов . Когда нет дыр или добавленных точек, триангуляции образуют максимальные внешнепланарные графы .
Триангуляция полигона без лишних вершин [ править ]
Со временем был предложен ряд алгоритмов триангуляции многоугольника.
Особые случаи [ править ]
Триангуляцию любого выпуклого многоугольника за линейное время в веерную триангуляцию тривиально путем добавления диагоналей от одной вершины ко всем остальным вершинам, не являющимся ближайшими соседями.
Общее количество способов триангулировать выпуклый n -угольник по непересекающимся диагоналям есть ( 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]
Связанные объекты и проблемы [ править ]
- Обе задачи триангуляции являются частным случаем триангуляции (геометрии) и частным случаем разделения многоугольника .
- Триангуляция минимального веса — это триангуляция, целью которой является минимизация общей длины ребра.
- — Триангуляция множества точек это многоугольная триангуляция выпуклой оболочки набора точек. Триангуляция Делоне — это еще один способ создания триангуляции на основе набора точек.
- Ассоциэдр — это многогранник, вершины которого соответствуют триангуляциям выпуклого многоугольника.
- Покрытие многоугольного треугольника , в котором треугольники могут перекрываться.
- Мозаика полигонами , цель которой — покрыть всю плоскость многоугольниками заранее заданной формы.
См. также [ править ]
Ссылки [ править ]
- ^ Jump up to: а б с д и Марк де Берг , Марк ван Кревелд , Марк Овермарс и Отфрид Шварцкопф (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 , МР 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
- ^ Jump up to: а б Зайдель, Раймунд (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