Задача о триангуляции многоугольника

Задан многоугольник координатами своих вершин вдоль обхода его контура. Требуется указать множество непересекающихся во внутренних точках диагоналей, разбивающих многоугольник на треугольники. Вход: файл input.txt, , в первой строке которого записано число N – количество вершин многоугольника, потом в N строках пары целых чисел – координат вершин многоугольника в порядке обхода контура. Ограничения: 4 ≤ N ≤ 200; каждая координата от -10000 до 10000 Выход: файл output.txt, в первой строке которого должно быть число k, указывающее необходимое число диагоналей. В последующих k строках должно быть по два натуральных числа – номер начальной и конечной вершины соответствующей диагонали. Дополнительные ограничения: диагонали должны лежать строго внутри многоугольника (все точки диагонали, за исключением концов, являются внутренними точками многоугольника). Пример: input.txt 5 1 1 2 5 5 5 5 1 2 2
output.txt 2 2 5 3 5 Мое решение: Количество диагоналей равно (количество вершин - 3) Соединяем все точки от (2) до (количество вершин - 2) с последней точкой; если прямая между соединяемой и последней точкой лежит вне многоугольника (многоугольник невыпуклый), то берем следующую точку и соединяем ее с некоторыми (какими?) точками. Помогите, пожалуйста, все это реализовать или подскажите, как проверить принадлежность прямой (или точки) многоугольнику и какие точки соединять, если многоугольник является невыпуклым.

Ответ

Если число вершин <= 3 разбиение закончено Выбраем первую вершину как текущую (N) Если из неё нельзя провести диагональ внутри многоугольника к точке N+2, то теущей становится следующая и т.д. по кольцу. Думаю можно доказать, что этот цикл не бесконечен. "Отрезаем" треугольник от многоугольника, вершин становится на одну меньше за счёт исключения вершины N+1. Переходим к пункту 1
Наверно удобно использовать связный список.
Определение проходит ли диагональ внутри многоугольника.
Заранее определим в каком направлении задан многоугольник - по или против часовой стрелки. Далее если треугольник N N+1 N+2 обходится в противоположном направлении, значит наша диагональ снаружи - не подходит. В противном случае возможен ещё вариант когда диагональ оказывается снаружи полностью или частично по вине других внутренних углов, это проверяется далее.
Для точек N+3 и N-1 нужно проверить, чтобы эти углы при этих вершинах были больше чем соответствующие углы отрезаемого треугольника. Т.е. вершина лежит по другую сторону от диагонали относительно вершины N+1, либо угол при вершине больше развёрнутого. (См. на картинке для вершины 2 угол 2-3-1 больше чем 2-3-4, или 4 и 2 находятся по одну сторону от диагонали 3-1, поэтому диагональ 3-1 не подходит. Для вершины 8 она с вершиной 6 по одну сторону диагонали 7-1, но угол 7 больше развёрнутого, поэтому это не мешает, вершина подходит.)
Для оставшихся сторон нужно проверить не пересекают ли они данную диагональ. (Например на рисунке сторона 6-7 пересекает диагональ 4-2. Точка пересечения прямых принадлежит отрезку.) Тут четыре стороны проверять не нужно: это стороны при вершине и соседние к ним.
Определение направления обхода многоугольника
Проводим из одной вершины A1 вектора ко всем остальным A1->A2, A1->A3, ... A1->AN. Считаем сумму N-1 векторных произведений соседних векторов по порядку, нас интереует только координата z. Эта сумма по модулю равна удвоенной площади фигуры, а знак указывает направление обхода.
Оптимизация от @AnT: Для того, чтобы определить направление обхода многоугольника достаточно вычислить векторное произведение сторон инцидентных с нижней-левой вершиной (минимальный x среди минимальных y). Делать это во всех вершинах (т.е. считать полную площадь) нет никакой необходимости.
Иллюстрация к случаям рассмотренным в алгоритме.