Я имел ввиду конкретно kd-tree, для него есть соседняя тема. Хотя с удовольствием поддержу разговор и о др деревьях, создавайте топик

Вернемся к теме. Пусть сейчас используется такой алгоритм

- сначала не выполняем трудоемких расчетов, а только строим дерево помещая туда опорные точки. Для этого (сначала, на первом проходе) просматриваем все входные точки. Интерполяция возможна? Зер гут, поехали дальше. Невозможна - добавляем точку в дерево. Какое дерево взять - чисто "дело техники", здесь-то стандартные решения найдутся. Как дальше юзать построенное дерево - разжевано выше

Какие Вы видите здесь минусы, проблемы?

Ну все-таки "тщательного обдумывания" (скажем так) никто не отменял. Допустим Вы начали писать алгоритм выше. А как Вы определите что интерполяция возможна? Найдете в дереве N ближайших? И что из этого выйдет? Зачем начинать реализацию не посчитав даже на один ход вперед? 

Работа алгоритмиста - анализ и оценка различных ситуаций. По существу все решения принимаются здесь. А как реализовать то или это - конечно тоже имеет значение, но далеко не первостепенное 

"Студента - отчислить, диплом - порвать, на научрука надеть дурацкий колпак и перевести в ассистенты"

А что мешает сделать не "наивно" а "нормально"? Кстати примененный Вами jitter - довольно стандартный прием, но нужно юзать его сознательно, а не так, на ходу дырки затыкать.

Попробуем поразмыслить (аттач). Начало: есть N точек, дерево пока пусто. Выбора нет, нужно добавлять точку в дерево. Поехали дальше, берем следующую точку. Если она оказалась в радиусе R предыдущей - интерполяция возможна, иначе нет. Есть какие-то др решения? Я их не вижу. Ладно, проходимся так по всем точкам, в итоге поучаем некоторое "покрытие", любая из точек имеет хотя бы одну опорную на расстоянии не более R.

Анализируем рез-т. Выясняется что с собсно интерполяцией все практически определено: используя построенное дерево, нужно сложить всех соседей в радиусе R с весом обратным расстоянию

w = 1 - dist / R, // где dist = расстояние от интерполируемой точки до опорной

Для придания наукообразности можно подмазать эрмитным переходом или др полиномом. Что еще тут хорошо или плохо? По чертежу замечаем что очень многие точки будут иметь всего одну опорную в радиусе R. Это может устраивать (напр для моих задач), но может и нет (хотя бы для того же восстановления изображения).

Ладно, еще что? Уязвимое/проблемное место = "берем точку". Ведь они могут браться как угодно. Напр можно отсортировать их по осям (а как еще?), но можно и просто "в изначальном порядке", можно и случайно, в любом случае "покрытие" будет построено. Только вот всякий раз разное. Правда сортировка гарантирует воспроизводимый рез-т в случае тех же данных при любом начальном порядке, но это очень слабенькое решение. Напр изменится лишь небольшая часть данных (или хотя бы флоты неравны из-за др матрицы камеры).

И.т.п. Ну работа такая с алгоритмами. Ах если б кто сказал, да расписал (а лучше с видео-уроками), "дал бы формулы"

Нет. Порядок расчета

- точку 1 занесли в дерево (это опорная точка)
- смотрим точку 2, она на расстоянии < R, стало быть это интерполируемая, в дерево ее не заносим
- смотрим точку 3, она на расстоянии > R от первой (но не второй которой в дереве нет). Значит точку 3 тоже опорная, фиксируем ее в дереве

В рез-те примерно половина из 100 точек станут опорными (ну так фишка легла)

Edit: важно что опорные точки мы (пока) не считаем а лишь заносим в дерево. Поэтому точку 2 мы можем спокойно пропустить, когда дело дойдет до ее интерполяции будем юзать все опорные в радиусе R  (а не только точку 1)