355
правок
Изменения
→Локализация
* Находим, какие рёбра треугольников пересекает <tex>v_{i+1} q</tex>, в итоге находим треугольник, в котором лежит <tex>q</tex>
* Находим ближайшую к <tex>q</tex> точку. Первым кандидатом на то, чтобы быть ближайшей точкой, становится ближайшая к <tex>q</tex> вершина найденного в предыдущем пункте треугольника. Для каждого кандидата нужно просмотреть смежные вершины в поиске точки, которая находится ближе к <tex>q</tex> — эта точка становится следующим кандидатом. Если же среди соседей точки не нашлось более близких, значит, эта точка и есть ближайшая.
=== Корректность алгоритма ===
{{Определение
|definition='''Критерий Делоне для ребра''' — : на ребре можно построить такую окружность, что внутри неё не будет лежать никаких точек.
}}
{{Лемма
|statement=Триангуляции Делоне принадлежат те и только те рёбра (с поправкой на точки, лежащие на одной окружности), которые удовлетворяют критерию Делоне.
|proof=
То, что для рёбер, принадлежащих триангуляции Делоне, выполняется критерий Делоне для рёбер, очевидно (вокруг каждого ребра можно описать окружность, проходящую через противолежащую ему точку в смежном треугольнике, причём в окружности не будет никаких точек по критерию Делоне).
Докажем, что если для ребра выполняется критерий Делоне, то оно принадлежит триангуляции Делоне.
{{TODO|t=А Надо вставить картинку}} Предположим, что это ребро (назовём его <tex>AB</tex>) не принадлежит триангуляции Делоне. Тогда существует пересекающее его ребро <tex>CD</tex>, принадлежащее триангуляции. Рассмотрим четырёхугольник <tex>ACBD</tex>. Точки <tex>C</tex> и <tex>D</tex> лежат вне окружности, построенной на <tex>AB</tex> как это вообще на хорде, поэтому сумма углов <tex>C</tex> и <tex>D</tex> меньше 180°. Аналогичным образом доказывается?}}, что сумма углов <tex>A</tex> и <tex>B</tex> тоже меньше 180°. Значит, сумма углов четырёхугольника <tex>ACBD</tex> меньше 360°, что невозможно. Противоречие. Значит, ребро <tex>AB</tex> принадлежит триангуляции Делоне.
}}
{{Теорема
