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

Question

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

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

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

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

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

Answer 1

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

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

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

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