68
правок
Изменения
→Вставка точки
===Вставка точки===
==== Вставка точки, лежащей внутри триангуляции на поверхности сферы ====
[[Файл:Insert.jpg|right||Вставка в треугольник]]
Пусть мы добавляем точку <tex>P'</tex>. Для начала локализуемся: поймём, в каком фейсе она лежит (или на каком ребре).
Если точка лежит внутри фейса, добавляем три ребра, сам фейс превращаем в один из новых смежных с вставляемой точкой и добавялем ещё два фейса.
Если же точка лежит на ребре, два смежных с ребром фейса превращаем в два новых, добавляем ещё два, а так же превращаем ребро, на которое вставляется точка, в ребро, которое заканчивается в этой точке, и вставляем три новых.
Итого у нас появилось несколько новых рёбер. Они все хорошие (по лемме 7), плохими могут оказаться только рёбра, противолежащие вставленной точке. Флипаем рёбра, пока триангуляция не станет хорошей.
==== Вставка точки, лежащей внутри триангуляции на поверхности сферы ====
Пусть мы добавляем точку <tex>P''</tex>.
==== Время работы ====
{{Лемма
|about=8
