184
правки
Изменения
→Триангуляция монотонного многоугольника
Рассмотрим алгоритм обработки вершины более подробно. Возможны два случая:
* Текущая вершина <tex>v_j</tex> является нижним концом стороны <tex>e</tex>, ограничивающего воронку. Вершины противоположной цепи уже были положены в стек. В этом случае можно просто построить диагонали, соединяющие <tex>v_j</tex> со всеми вершинами, находящимися в стеке, кроме последней. Последняя вершина в стеке уже соединена с <tex>v_j</tex> стороной <tex>e</tex>. Часть многоугольника <tex>ЗP</tex>, лежащая выше <tex>v_j</tex>, которая не была триангулирована, ограничена диагональю, которая соединяет <tex>v_j</tex> с вершиной <tex>v_k1v_{k1}</tex>, которая была первой в стеке. Сторона многоугольника <tex>P</tex>, выходящая из <tex>v_k1v_{k1}</tex> направлена вниз. Снова образуется фигура, похожая на воронку -- инвариант сохраняется. Вершины <tex>v_j</tex> и <tex>v_k1v_{k1}</tex> кладутся в стек, поскольку они были были обработаны, но по прежнему являются вершинами непротриангулированной части <tex>P</tex>.
* Вершина <tex>v_j</tex> принадлежит цепи вершин, добавленных в стек, до которых невозможно провести диагонали.
=== Ушной метод ===
Более эффективным я