Я решил создать простую демонстрацию, разделив многоугольник на множество треугольников. Вот что у меня есть до сих пор:
Задается последовательный список вершин (P1), образующих ребра многоугольника (в большинстве случаев многоугольник не является выпуклым); необходим набор треугольников
Перебрать все вершины внутри многоугольника P1 и найти ту (v), которая удовлетворяет следующим условиям:
удалить v из многоугольника и сохранить новый в P2 предыдущая вершина v, соединенная со следующей, образует линию, которая не пересекает ни одно из P2 ребер
v не находится внутри P2
Если они выполняются, мы можем заменить P1 на (P2 + triangle(prev(v), v, next(v))) и повторять это действие до тех пор, пока P1 не будет содержать более 3 вершин.
Итак, вопросы: верен ли этот алгоритм и как его можно реализовать на C/C++ наиболее очевидным и простым способом?