264
правки
Изменения
м
→Динамический алгоритм
'''Локальный критерий Делоне:''' при построении плоскости через три точки, образующие треугольник, противолежащие сторонам треугольника вершины соседей лежат ниже этой плоскости.
}}
==Динамический алгоритм== ===Вставка точки======Удаление точки======Локализация в триангуляции===
Построим алгоритм на сфере по аналогии с плоскостью.
====Структура данных====
Локализационная структура состоит из нескольких уровней, где каждый уровень {{---}} триангуляция Делоне. На нижнем уровне содержатся все точки. Далее точка с вероятностью <tex> p </tex> попадает на следующий уровень. Если на последнем уровне находится одна точка, то дальше она уже не пойдет.
}}
====Принадлежность треугольнику====
Пусть даны точки <tex>P</tex>, <tex>A</tex>, <tex>B</tex>, <tex>C</tex> на сфере с центром <tex>O</tex>, тогда <tex>P</tex> принадлежит треугольнику <tex>ABC</tex>, тогда и только тогда, когда поворот <tex>P</tex> относительно плоскостей <tex>AOB</tex>, <tex>BOC</tex>, <tex>COA</tex> одинаковый.
====Алгоритм====
Чтобы найти треугольник, которому принадлежит точка запроса(точка <tex>Q</tex>), сначала найдем ближайшую к ней точку триангуляции(точка <tex>P</tex>), а зачем вдоль луча <tex>PQ</tex> будем обходить треугольники, пока не локализуемся.
