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

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

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

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

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

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

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

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

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

Общее количество способов триангулировать выпуклый 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-полным , поэтому маловероятно, что это может быть выполнено за полиномиальное время.

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

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

использованная литература

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