355
правок
Изменения
м
→Вставка
}}
=== Вставка ===
Смотрим на список рёбер, пересечённых ещё не вставленным констрейнтом ({{TODO|t=Картинку бы}}), и флипаем их. Последнее флипнутое ребро и будет констрейнтом {{Acronym|(по понятным причинам)|Рёбра, пересечённые констрейнтом, после флипа будут начинаться в той же точке, что и констрейнт, а заканчиваться в точке, в которой начинается ещё одно пересекающее ребро. Последнее же ребро будет начинаться и заканчиваться в начале и конце констрейнта}}, после флипа пометим его как констрейнт. Понятное дело, критерий «хорошести» ребра при таких фокусов фокусах немного изменится: туда добавится проверка на то, не является ли ребро констрейнтом. Затем флипаем всё, что могло стать плохим (кроме констрейнта), пока триангуляция вновь не станет условно хорошей.
{{TODO|t=Тут должно быть ещё несколько упоительных фактов про то, что вставка производится за <tex>O(k^2)</tex>, где <tex>k</tex> — число пересечённых рёбер, и про то, что, если флипать что попало, можно нарваться на флип в невыпуклом многоугольнике}}
=== Удаление ===
Аналогично: помечаем ребро как не-констрейнт и начинаем флипать, пока не дойдём до хорошей (или условно хорошей) триангуляции.
