Введение

Разделение простого многоугольника на треугольники

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

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

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

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

Метод отрезания ушей

Один из способов триангуляции простого многоугольника основан на теореме о двух ушах, поскольку любой простой многоугольник с не менее чем 4 вершинами без отверстий имеет по крайней мере два "уха" – треугольника, две стороны которого являются сторонами многоугольника, а третья сторона полностью лежит внутри него. Алгоритм заключается в поиске такого уха, его удалении из многоугольника (в результате чего получается новый многоугольник, по-прежнему удовлетворяющий условиям) и повторении процесса, пока не останется только один треугольник. Этот алгоритм прост в реализации, но медленнее некоторых других и работает только с многоугольниками без отверстий. Реализация, поддерживающая отдельные списки выпуклых и вогнутых вершин, имеет временную сложность O(n²). Этот метод известен как отсечение ушей или обрезка ушей. Эффективный алгоритм отсечения ушей был разработан Хоссамом ЭльГинди, Хейзел Эверетт и Годфридом Туссеном.

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

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