Триангуляция многоугольника ушным методом

1. Если число вершин <= 3 разбиение закончено
2. Выбраем первую вершину как текущую (N)
3. Если из неё нельзя провести диагональ внутри многоугольника к точке N+2, то теущей становится следующая и т.д. по кольцу. Думаю можно доказать что этот цикл не бесконечен.
4. "Отрезаем" треугольник от многоугольника, вершин становится на одну меньше за счёт исключения вершины N+1.
5. Переходим к пункту 1

Наверно удобно использовать связный список.

Определение проходит ли диагональ внутри многоугольника.

Заранее определим в каком направлении задан многоугольник - по или против часовой стрелки. Далее если треугольник N N+1 N+2 обходится в противоположном направлении, значит наша диагональ снаружи - не подходит. В противном случае возможен ещё вариант когда диагональ оказывается снаружи полностью или частично по вине других внутренних углов.

Для точек N+3 и N-1 нужно проверить, чтобы эти углы при этих вершинах были больше чем соответствующие углы отрезаемого треугольника. Т.е. вершина лежит по другую сторону от диагонали относительно вершины N+1, либо угол при вершине больше развёрнутого.

Для оставшихся сторон нужно проверить не пересекают ли они данную диагональ.

Определение направления обхода многоугольника

Проводим из одной вершины A1 вектора ко всем остальным A1->A2, A1->A3, ... A1->AN. Считаем сумму N-1 векторных произведений соседних векторов по порядку, нас интересует только координата z. Эта сумма по модулю равна удвоенной площади фигуры, а знак указывает направление обхода.

В противном случае возможен ещё вариант когда диагональ оказывается снаружи полностью или частично по вине других внутренних углов.

Для точек N+3 и N-1 нужно проверить, чтобы эти углы при этих вершинах были больше чем соответствующие углы отрезаемого треугольника. Т.е. вершина лежит по другую сторону от диагонали относительно вершины N+1, либо угол при вершине больше развёрнутого.

Для оставшихся сторон нужно проверить не пересекают ли они данную диагональ.