264
правки
Изменения
м
→Удаление точки
===Удаление точки===
В результате удаления у нас появляетя некоторый звездный многоугольник на сфере, который надо триангулировать.
многоугольника, когда мы будем его триангулировать.
Из-за того, что у нас сфера, и задача триангуляции сведена к задаче построения выпуклой оболочки, то следовательно, нам перестает быть важным критерий Делоне, нам просто нужно у звездного многоугольника на сфере как-то провести ребра так, чтобы было выпукло.
Представим себе, что вместо того, чтобы удалять точку, мы просто опускаем ее во внутрь сферы до тех пор, покаона не перестает быть видимой в построенном на триангуляции многоугольнике. Предположим, что мы находимся в удаляемой точке, движемся в центр сферы и смотрим только в направлении движения. Понятно, что мы постепенно перестаем видеть какие-то грани.Это происходит когда мы уходим ближе к центру, чем плоскость, соответствующая грани.
Итак, мы перестаем видеть грани, они исчезают в каком-то порядке. И, на самом деле, этот порядок соответствует отрезанию ушей у звездного многоугольника.
Ухом является часть, которая по двум ребрам граничит с невидимыми гранями и по одному ребру может граничить с видимой.
Мы понимаем, что грани выпуклой оболочки - выпуклые многоугольники.
Посмотрим в каком порядке исчезают грани.
Предположим нас есть кандидат на то, чтобы исчезнуть. Это какой-то выпуклый многогранник.
Предположим, что у этого выпуклого многоугольника видно хотя бы два соседа, которые видны, но сам выпуклый многоугольник уже почти исчез(находится на одной плоскости с нашей точкой). Если мы видим две другие грани, это значит, что
рассмотрим центры отрезков.
рассмотрим эпс окресности центров отрезков. Если мы точку ещё чуть спустим, то этот многоугольник виден не будет, но эпс окрестности будут видны две какие-то точки. Соединим их отрезком.
этот отрезок будет виден. Он не будет лежать на плоскоси. Он не будет лежать под плоскостью. Тогла получается, что он лежит над плоскостью, а, значит, многогранник был невыпуклый.
Получается, что грань ушла и у нее только один видимый сосед. Мы можем триангулировать грань отрезая уши. Если эта грань былатреугольником, то ничего делать не нужно, в противом случае, можно перетриангулировать грань как угодно.
===Локализация в триангуляции===
Построим алгоритм на сфере по аналогии с плоскостью.
