Надеюсь, последнее не означает самопересечений исходного? Если означает, то нужно уточнить, что тут понимать под триангуляцией. Иначе так:
На входе — последовательность вершин (необязательно выпуклого, но без самопересечений) многоугольника, взятых по часовой стрелке, А1, А2, ..., Аi, ..., Аn.
Перебираем последовательность циклически, до тех пор, пока в ней > 3 вершин.
Определяем угол при текущей вершине, как разность углов наклона векторов А[i-1]А[i] и А[i]А[i+1].
Если угол > развернутого, идем дальше
иначе добавляем в результат треугольник А[i-1]А[i]А[i+1]
и выбрасываем из последовательности А[i]
