Нахождение диагоналей многоугольника

Учитывая вогнутый многоугольник (без самопересечений), узлы которого расположены по часовой стрелке, как мы можем определить все его внутренние диагонали (те, которые находятся внутри многоугольника)?

Меня интересует решение, в котором не используются триггерные функции.

Предыстория и то, что я пробовал:

В моем классе вычислительной геометрии нам дали следующий алгоритм, чтобы проверить, является ли [pi, pj] внутренней диагональю многоугольника p0, p1, ... pn-1:

1. Проверить, пересекает ли [pi, pj] край многоугольника, который не примыкает к нему. Если да, то это не внутренняя диагональ. Если нет, переходите к шагу 2.
2. 1. if pi is a convex point (pi-1, pi, pi+1 make a right turn), then [pi, pj] is an inner diagonal iff pi, pj, pi+1 and pi, pi-1, pj make a left turn.
   2. если pi не является выпуклой точкой (pi-1, pi, pi+1 повернуть налево), то [pi, pj] - внутренняя диагональ, если pj, pj-1, pi повернуть налево.

Этот алгоритм был дан нам для алгоритма триангуляции, включающего обрезку ушей. Я реализовал этот алгоритм, и, похоже, он там отлично работает, но загвоздка в том, что алгоритм обрезки ушей использует только диагонали формы [pi, pi+2].

Однако рассмотрим алгоритм триангуляции методом грубой силы, который выбирает все непересекающиеся диагонали. Используя то, что я описал как подпрограмму для проверки внутренних диагоналей (вместе с методом пересечения сегментов), я получаю следующий результат:

Легко проверить, что опубликованный мной алгоритм отклоняет внутреннюю диагональ [3, 6], хотя на самом деле это не должно:

3 не является выпуклой точкой, и 6, 5, 3 делает поворот направо, а не налево, поэтому он отклоняется.

Обратите внимание, что при использовании алгоритма обрезки ушей этот многоугольник триангулируется правильно.

Мне интересно, как этот алгоритм можно адаптировать для обнаружения всех диагоналей в многоугольнике. Мне не удалось заставить его работать.

Я также обнаружил другие проблемы с этим методом, такие как многоугольники, для которых нарисованы внешние диагонали. Опять же, они работают с алгоритмом обрезки ушей. Однако нам никогда не говорили, что этот метод применим только к особой форме диагоналей, поэтому я ищу пояснений.

Примечание. Я не мог решить, размещать ли это на math.stackexchange.com или здесь, поскольку вычислительная геометрия в некоторой степени связана как с программированием, так и с математикой, однако я чувствовал, что программисты могут быть более знакомы с такими алгоритмами, чем математики, поскольку кто-то, вероятно, действительно реализовал это в какой-то момент.