Изменения

Отсортируем все вершины многоугольника <tex>P</tex> в порядке убывания их <tex>y</tex>-координаты. В момент обработки некоторой вершины, будем пытаться провести из неё как можно больше диагоналей. Эти диагонали отрезают треугольники от <tex>P</tex>. Заведём стек вершин <tex>S</tex>. В стеке будем хранить вершины, которые были обработаны, но не были отрезаны от многоугольника, то есть находятся в той части многоугольника, которая ещё не была триангулирована. В момент обработки некоторой вершины, будем пытаться провести из неё как можно больше диагоналей к вершинам, содержащимся в стеке. Эти диагонали отрезают треугольники от <tex>P</tex>. На вершине стека будет храниться вершина, котораябудет обрабатываться последней. Часть многоугольника <tex>P</tex>, лежащая выше последней обработанной вершины и которая ещё не была триангулирована имеет форму перевёрнутой воронки (см. рисунки). Одна сторона воронки состоит из одной из сторон <tex>P</tex>, а другая состоит из цепи вершин, внутренние углы которых не меньше <tex>\pi</tex>. Несложно догадаться тогда, что самая нижняя вершина стека является выпуклой. Рассмотрим алгоритм обработки вершины более подробно.