355
правок
Изменения
→Локализация
* Находим, в каком из треугольников, смежных с <tex>v_{i+1}</tex>, лежит отрезок <tex>v_{i+1} q</tex>
* Находим, какие рёбра треугольников пересекает <tex>v_{i+1} q</tex>, в итоге находим треугольник, в котором лежит <tex>q</tex>
* Находим ближайшую к <tex>q</tex> точку. Первым кандидатом на то, чтобы быть ближайшей точкой, становится ближайшая к <tex>q</tex> вершина найденного в предыдущем пункте треугольника. Для каждого кандидата нужно просмотреть смежные вершины в поиске точки, которая находится ближе к <tex>q</tex> — эта точка становится следующим кандидатом. Если же среди соседей точки не нашлось более близких, значит, эта точка и есть ближайшая. {{TODOТеорема|tstatement={{AcronymДанный алгоритм найдёт ближайшую точку.|Как?|Попой об косяк}} }}proof={{TODO|t=Почему этот алгоритм найдёт такую Картинку для ясности}}Предположим, что это не так. Назовём локализуемую точку <tex>q</tex>, а последнего кандидата на то, чтобы быть ближайшей точкой — <tex>v</tex>. Раз эта точка на самом деле не ближайшая, то в окружности, проходящей через <tex>v</tex>, с центром в точке <tex>q</tex> найдутся ещё какие-то точки, не смежные с <tex>v</tex>. Рассмотрим ближайшую из них к <tex>v</tex>: точку?<tex>v'</tex>. Построим на <tex>vv'</tex> окружность как на диаметре. В этой окружности не будет лежать никаких точек, так как мы взяли ближайшую. Значит, ребро <tex>vv'</tex> удовлетворяет критерию Делоне и должно являться ребром триангуляции, но по предположению этого ребра нет. Значит, предположение неверно.}}
=== Профит ===
