Триангуляция многоугольника - Polygon triangulation
В вычислительной геометрии , Многоугольник триангуляции является разложение многоугольной области ( простой многоугольника ) P на множество треугольников , то есть, найти множество треугольников с попарно непересекающихся интерьеров , чей союз является Р .
Триангуляции можно рассматривать как частные случаи плоских прямолинейных графов . Когда нет отверстий или добавленных точек, триангуляции образуют максимальные внешнепланарные графы .
Триангуляция многоугольника без лишних вершин
Со временем был предложен ряд алгоритмов для триангуляции многоугольника.
Особые случаи
Триангулировать любой выпуклый многоугольник за линейное время в веерную триангуляцию , добавляя диагонали из одной вершины ко всем остальным вершинам, - тривиально .
Общее количество способов триангулировать выпуклый n -угольник непересекающимися диагоналями - это ( n - 2) -ое каталонское число , которое равно
- ,
формула, найденная Леонардом Эйлером .
Монотонной многоугольник может быть триангулированным в линейное время либо с алгоритмом А. Fournier и DY Montuno или алгоритмом Godfried Туссен .
Метод стрижки ушей
Один из способов триангуляции простого многоугольника основан на теореме о двух ушах , так как тот факт, что любой простой многоугольник с как минимум 4 вершинами без отверстий имеет как минимум два ` ` уха '', которые представляют собой треугольники, две стороны которых являются краями многоугольника, и третий полностью внутри него. Затем алгоритм состоит из поиска такого уха, удаления его из многоугольника (в результате чего получается новый многоугольник, который все еще соответствует условиям) и повторения до тех пор, пока не останется только один треугольник.
Этот алгоритм легко реализовать, но он работает медленнее, чем некоторые другие алгоритмы, и работает только с полигонами без дыр. Реализация, которая хранит отдельные списки выпуклых и вогнутых вершин, будет работать за O ( n 2 ) времени. Этот метод известен как стрижка ушей, а иногда и ушей . Эффективный алгоритм отрезания ушей был открыт Хоссамом Эль-Джинди, Хейзел Эверетт и Годфридом Туссеном .
Монотонная триангуляция многоугольника
Простой многоугольник монотонен относительно прямой L , если любая прямая, ортогональная L, пересекает многоугольник не более двух раз. Монотонный многоугольник можно разбить на две монотонные цепочки . Многоугольник, монотонный относительно оси y, называется y-монотонным . Монотонный многоугольник с n вершинами можно триангулировать за O ( n ) раз. Предполагая, что данный многоугольник является y-монотонным, жадный алгоритм начинает с обхода одной цепочки многоугольника сверху вниз, добавляя диагонали всякий раз, когда это возможно. Легко видеть, что алгоритм применим к любому монотонному многоугольнику.
Триангуляция немонотонного многоугольника
Если многоугольник не является монотонным, он может быть разбит на монотонные подполигоны за время O ( n log n ), используя метод развертки . Алгоритм не требует, чтобы многоугольник был простым, поэтому его можно применять к многоугольникам с отверстиями. Как правило, этот алгоритм может триангулировать планарное подразделение с n вершинами за время O ( n log n ), используя пространство O ( n ) .
Двойственный график триангуляции
Полезный граф, который часто ассоциируется с триангуляцией многоугольника P, - это двойственный граф . Учитывая триангуляцию Т Р из Р , один определяет граф G ( Т Р ) , как граф, множество вершин являются треугольники Т Р , две вершины (треугольники) , которые смежны тогда и только тогда , когда они имеют диагонали. Легко заметить, что G ( T P ) - дерево максимальной степени 3.
Вычислительная сложность
До 1988 г. вопрос о том, можно ли триангулировать простой многоугольник быстрее, чем за время O ( n log n ), оставался открытой проблемой вычислительной геометрии. Затем Тарджан и Ван Вик (1988) открыли алгоритм триангуляции за O ( n log log n ) , позже упрощенный Киркпатриком, Клаве и Тарьяном (1992) . Затем последовало несколько улучшенных методов со сложностью O ( n log * n ) (практически неотличимых от линейного времени ).
Бернар Шазель в 1991 году показал, что любой простой многоугольник можно триангулировать за линейное время, хотя предложенный алгоритм очень сложен. Также известен более простой рандомизированный алгоритм с линейным ожидаемым временем.
Алгоритм разложения Зейделя и метод триангуляции Шазеля подробно обсуждаются в Li & Klette (2011) .
Временная сложность триангуляции с п -vertex многоугольника с отверстиями имеет Q ( п войти п ) нижняя граница , в алгебраических вычислений дерева моделей вычислений. Можно вычислить количество различных триангуляций простого многоугольника за полиномиальное время, используя динамическое программирование , и (на основе этого алгоритма подсчета) генерировать равномерно случайные триангуляции за полиномиальное время. Однако подсчет триангуляций многоугольника с дырками является # P-полным , поэтому маловероятно, что это может быть выполнено за полиномиальное время.
Связанные объекты и проблемы
- Обе задачи триангуляции являются частным случаем триангуляции (геометрии) и частным случаем разбиения многоугольника .
- Триангуляция минимального веса - это триангуляция, цель которой - минимизировать общую длину ребра.
- Точка-множество триангуляции представляет собой многоугольник триангуляция выпуклой оболочки множества точек. Триангуляции Делоне еще один способ создать триангуляции на основе набора точек.
- Associahedron является многогранник, вершины которого соответствуют триангуляции выпуклого многоугольника.
- Покрытие многоугольником треугольником , в котором треугольники могут перекрываться.
- Тайлинг по многоугольникам , цель которого - покрыть всю плоскость многоугольниками заданной формы.
Смотрите также
использованная литература
внешние ссылки
- Демонстрация как Flash swf , алгоритм развертки линии.
- Объяснение Сон Хо тесселатора OpenGL GLU