Метод разбиения многоугольника на треугольники (триангуляция) заключается в том, чтобы разбить многоугольник на наименьшее число треугольников. 12

Для многоугольника без отверстий с n вершинами триангуляцию можно вычислить за время Θ(n). 1 Для многоугольника с отверстиями существует нижняя граница Ω(nlog n). 1

Также существует вариант разбиения на треугольники с минимальной общей длиной рёбер, который называется триангуляцией с минимальным весом. 1

Алгоритм разбиения многоугольника на треугольники можно описать так: 4

1. Подготовить рабочие объекты. 4 Результатом работы должен быть список треугольников, поэтому создают пустой список. 4
2. Перед стартом просчитать углы для всех точек многоугольника. 4
3. Выбрать любую точку многоугольника как «рабочую». 4
4. Создать пустой список для хранения временных треугольников. 4
5. Если точка слева от «рабочей» имеет угол меньше 180 градусов и треугольник не содержит внутри себя других точек многоугольника — занести этот треугольник в временный список. 4
6. Если точка справа от «рабочей» имеет угол меньше 180 градусов и треугольник не содержит внутри себя других точек многоугольника — занести этот треугольник в временный список. 4
7. Если «рабочая» точка имеет угол меньше 180 градусов и треугольник не содержит внутри себя других точек многоугольника — занести этот треугольник в временный список. 4
8. Если временный список не содержит треугольников — выбрать вместо «рабочей» точку слева от неё и вернуться к первому пункту. 4
9. Если содержит — выбрать треугольник с минимальной разницей между минимальным и максимальным углом (нужно пересчитать значение углов), занести его в список треугольников, удалить из рабочего двунаправленного замкнутого списка среднюю точку из выбранного треугольника, а соседним точкам от неё пересчитать значения углов, первую точку выбрать в качестве «рабочей». 4
10. Если в рабочем двунаправленном замкнутом списке осталось только две точки — прекратить работу, список треугольников будет готов, иначе вернуться к первому пункту. 4

Также существует вариант разбиения на треугольники с минимальной общей длиной рёбер, который называется триангуляцией с минимальным весом. 1