Как определить, является ли вершина слиянием/расщеплением? (polygon triangulation, C#)

Question

Я делаю триангуляцию многоугольника в C#. Я написал код для триангуляционного монотонного многоугольника, но я не могу найти способ сломать многоугольник в монотонных частях. Я нашел много алгоритмов, например (http://research.engineering.wustl.edu/~pless/546/lectures/l7.html), метод развертки в плоскости, где события являются вершинами многоугольника, и в зависимости от того, является ли начало, конец, регулярное, разделение или слияние вершины, я делаю с ним разные вещи. Я понимаю, как работает алгоритм, но я не знаю, как проверить, что вершина разделена/слияния или просто начинается/заканчивается?

Answer 1

Похоже, вы должны знать, какая сторона края находится внутри/снаружи, или случай действительно двусмыслен. Если это задано обмоткой/порядком вершин, легко - всегда поворачивайте угол по часовой стрелке или против часовой стрелки от первого к второму ребру (или к соседним вершинам), следовательно, упомянутые 180 градусов. Если порядок вершин произволен, я могу предположить, что вы должны явно отслеживать внутреннее/внешнее направление, которое может потребовать начального прохода классификации.