184
правки
Изменения
→Триангуляция монотонного многоугольника
S.pop()
===== Корректность =====
Данный алгоритм корректен, поскольку:
* Все построенные диагонали попарно не пересекаются. Это гарантируется тем, что при каждом просмотре определённой вершины рассматривается только та часть <tex>P'</tex> многоугольника <tex>P</tex>, которая не была протриангулирована, следовательно внутри этой области по определению не может лежать ни одной из уже построенных диагоналей. Несложно заметить, что в стеке <tex>S</tex> на каждой итерации главного цикла хранятся вершины, которые принадлежат именно <tex>P'</tex> и лежат выше рассматриваемой вершины.
* Количество построенных диагоналей всегда будет <tex>n-3</tex>, поэтому непротриангулированных частей в многоугольнике не останется.
===== Оценка работы =====
