Как определить, какие диагонали принадлежат вогнутому многоугольнику

Question

У меня проблема с алгоритмом триангуляции:

В вогнутых многоугольниках некоторые диагонали не в многоугольнике. У меня есть двунаправленный список ребер, вершин и знаю, какие вершины имеют вогнутый угол.

Есть 2 случая:

А) диагональное пересечение с ребром или другая диагональ. B) диагональ не пересекается с какой-либо, но находится вне полигона.

Как я могу определить диагонали в случаях A и B?

Answer 1

Рассмотрим этот пример, где вершины отсортированы по часовой стрелке :

Посмотрите на красные диагонали вне многоугольника. Вершина «4» находится справа от линии «3-5». Вершины «3, 4» находятся справа от линии «2-5».

Мы можем вывести закон: если линия i-j имеет некоторую вершину k с i < k < j, которая находится справа от линии, то эта линия является внешней по отношению к многоугольнику.

Обратите внимание, что если вы измените порядок вершин, то вы также должны использовать «слева» вместо «справа».