184
правки
Изменения
→Триангуляция монотонного многоугольника
==== Триангуляция монотонного многоугольника ====
Идея такова: будем проходить сверху вниз по вершинам многоугольника проводя диагонали где это возможно.
Отсортируем все вершины многоугольника <tex>P</tex> в порядке убывания их <tex>y</tex>-координаты. В момент обработки некоторой вершины, будем пытаться провести из неё как можно больше диагоналей. Эти диагонали отрезают треугольники от <tex>P</tex>. Заведём стек вершин <tex>S</tex>. В стеке будем хранить вершины, которые были обработаны, но не были отрезаны от многоугольника, то есть находятся в той части многоугольника, которая ещё не была триангулирована. На вершине стека будет храниться вершина, которая
=== Ушной метод ===
Более эффективным я
