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