Полигон-Триангуляция ⇐ Васина Википедия

[wiki_de]

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

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

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

=== Особые случаи ===
Любой выпуклый многоугольник|выпуклый многоугольник легко преобразовать в веерную триангуляцию за временную сложность|линейное время путем добавления диагоналей от одной вершины ко всем остальным несмежным вершинам.

Общее количество способов триангуляции выпуклого многоугольника|''n''-угла по непересекающимся диагоналям равно (''n''-2)teКаталанскому числу|Каталонскому числу, которое в точности совпадает с формулой Леонхарда. Эйлер .

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

Монотонный многоугольник можно создать за линейное время, используя либо алгоритм Алена Фурнье (ученого-компьютерщика)|А. Фурнье и Д.Ю. Монтуно,[1] или алгоритм Годфрида Туссена[2] можно триангулировать.

=== Метод обрезки ушей ===
Один из способов триангуляции простого многоугольника основан на теореме о двух ушках, которая гласит, что каждый простой многоугольник с хотя бы четырьмя вершинами без отверстий имеет как минимум два «угла | уши», т.е. час Треугольники, в которых две стороны образуют края многоугольника, а третья сторона полностью лежит внутри многоугольника.[1] Алгоритм состоит в том, чтобы найти такое ухо и удалить его из многоугольника (в результате получается новый многоугольник, который по-прежнему удовлетворяет условиям) и повторяйте процесс, пока не останется только один треугольник.

Этот алгоритм легко реализовать, но он медленнее, чем некоторые другие алгоритмы, и работает только с полигонами без дыр. Реализация, поддерживающая отдельные списки выпуклых и вогнутых вершин, выполняется за время O(n2). Этот метод известен как «обрезание ушей», а иногда и «обрезание ушей». Эффективный алгоритм обрезки ушей был открыт Хоссамом ЭлДжинди, Хейзел Эверетт и Годфридом Туссеном[1].

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

=== Триангуляция немонотонного многоугольника ===
Если многоугольник немонотонен, его можно разделить на монотонные подполигоны за время O(n log n), используя метод прогонки (информатика)|вытягивания линии. Алгоритм не требует, чтобы многоугольник был простым, поэтому его можно применять и к многоугольникам с отверстиями. В общем, этот алгоритм может триангулировать плоское подразделение с n вершинами в пространстве O(n) за время O(n log n).[1]

=== Двойной график триангуляции ===
Полезный граф, часто связанный с триангуляцией многоугольника P, — это двойственность (математика)#Геометрический двойственный граф|двойственный граф. Для триангуляции TP графа P граф G(TP) определяется как граф, вершины которого являются треугольниками треугольника TP, причем две вершины (треугольника) смежны только в том случае, если они имеют общую диагональ. Легко заметить, что G(TP) — дерево (теория графов)|дерево максимальной степени 3.

=== Вычислительная сложность ===
До 1988 года вопрос о том, можно ли триангулировать простой многоугольник быстрее, чем за время O(n log n), был открытой проблемой вычислительной геометрии.[1] Затем Тарьян и Ван Вик (1988) разработали алгоритм для триангуляции за время O(n log log n),[2], которая позже была упрощена Kirkpatrick, Klawe & Tarjan (1992).[3] Последовало несколько улучшенных методов. со сложностью O(n log* n) (на практике неотличимой от временной сложности|линейного времени).[4][5][6]

Бернар Шазель показал в 1991 году, что любой простой многоугольник можно триангулировать за линейное время, хотя предложенный алгоритм очень сложен.[1] Также известен более простой рандомизированный алгоритм с линейным ожидаемым временем.[ 2]

Алгоритм разложения Зейделя[1] и метод триангуляции Шазель подробно обсуждаются в Li & Klette (2011)[2].

Временная сложность триангуляции многоугольника с n вершинами и отверстиями имеет границу (математика) | нижнюю границу Ω(n log n) в моделях алгебраических вычислительных деревьев. [1] Можно вычислить количество различных триангуляций простого многоугольника за полиномиальное время, используя динамическое программирование и (на основе этого алгоритма подсчета) дискретное равномерное распределение|равномерно случайные триангуляции за полиномиальное время для генерации .[2] Однако подсчет триангуляций многоугольника с отверстиями является #P-полным, поэтому маловероятно, что это можно сделать за полиномиальное время.[3]< бр />
== Связанные объекты и задачи ==

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

== См. также ==

* Каталонский номер|Каталонский номер
* Планарный график

== Источники ==

Подробнее: https://de.wikipedia.org/wiki/Polygon-Triangulation