Lazy Calculation(s)

[m_ax]

Для kd-tree это ещё пол беды.. После множества вставок оно у вас быстро станет несбалансированным.

Любое пополнение ведет к немедленной пере-балансировке, т.е. перестройке всего дерева (медиана-то убежала). Строго говоря, это не дерево а просто массив (хитро отсортированный)

Чтож тогда в красно-чёрных деревьях (например std::map) вставка за O(ln(N)) происходит?   (Любая вставка с сохранением балансировки)
Или, например, декартово дерево, совсем недавно появилось.. Очень интересная идея балансировки)

[Igors]

Чтож тогда в красно-чёрных деревьях (например std::map) вставка за O(ln(N)) происходит?   (Любая вставка с сохранением балансировки)
Или, например, декартово дерево, совсем недавно появилось.. Очень интересная идея балансировки)

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

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

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

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

[m_ax]

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

Вы знаете, как то опять размыто вопрос ставится.. Я считаю, что при такой постановке, такое решение мне кажется разумным, во всяком случае в первом приближении.
А дальше экспериментировать нужно. Многие тонкости могут вылезти именно на этой стадии.

У меня тут на днях случай был со студентом: он уже защитился, докладывал результаты, все в восторге (крутая теория и всё такое).. А на днях я решил (просто ради интереса)
проверить кое-что.. И бабах, выяснилось, что все выводы этой теории были ошибочны( Если бы мы сразу это посчитали.. Но если-бы, да ка-бы..
Короче, всего сразу в теории не предусмотришь. Путь к пониманию лежит через пробы и ошибки.   

[Igors]

Я считаю, что при такой постановке, такое решение мне кажется разумным, во всяком случае в первом приближении.
А дальше экспериментировать нужно. Многие тонкости могут вылезти именно на этой стадии.
...
Короче, всего сразу в теории не предусмотришь. Путь к пониманию лежит через пробы и ошибки.   

Ну все-таки "тщательного обдумывания" (скажем так) никто не отменял. Допустим Вы начали писать алгоритм выше.

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

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

Вы знаете, как то опять размыто вопрос ставится..

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

[m_ax]

А как Вы определите что интерполяция возможна?

Ну вот.. Выясняется, что мы и не можем на первом проходе определить - а возможна ли вообще интерполяция..

Найдете в дереве N ближайших? И что из этого выйдет?

Да хотя бы и так.. Я бы "потыкал" в случайных точках вблизи заданной, и смотрел бы уже на статистику распределения её ближайших соседей.. (см., например,  наивный подход в  vanda)

[Racheengel]

У меня тут на днях случай был со студентом: он уже защитился, докладывал результаты, все в восторге (крутая теория и всё такое).. А на днях я решил (просто ради интереса)
проверить кое-что.. И бабах, выяснилось, что все выводы этой теории были ошибочны( Если бы мы сразу это посчитали.. Но если-бы, да ка-бы..

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

[m_ax]

У меня тут на днях случай был со студентом: он уже защитился, докладывал результаты, все в восторге (крутая теория и всё такое).. А на днях я решил (просто ради интереса)
проверить кое-что.. И бабах, выяснилось, что все выводы этой теории были ошибочны( Если бы мы сразу это посчитали.. Но если-бы, да ка-бы..

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

Да где они в нашей РФ преподов то столько найдут?   Между прочим у него (у студента) целый список наград/премий и т.д.) И я не последнюю роль в этом сыграл)
И потом, мы признали свою ошибку)

[Igors]

Ну вот.. Выясняется, что мы и не можем на первом проходе определить - а возможна ли вообще интерполяция..
...
Да хотя бы и так.. Я бы "потыкал" в случайных точках вблизи заданной, и смотрел бы уже на статистику распределения её ближайших соседей.. (см., например,  наивный подход в  vanda)

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

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

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

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

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

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

..ходит вокруг да около
..размыто вопрос ставится..
..ну вот опять (как всегда)..
..не умеет поставить задачу
..посмотри в гугле

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

[Racheengel]

Уязвимое место: представим, что мы посчитали точку 1.
Теперь пришло еще 100 точек, которые лежат примерно на одной прямой и отстоят друг от друга чуть менее чем на R.
Получается, что эти 100 точек будут скопированы с 1-й, и точка на удалении 100R от 1-й будет иметь те же самые свойства.
И вот добавляется 101-я точка, которая удалена от 100-й чуть более чем на R.
Честно пересчитываем её, и оказывается, что в данном сегменте пространства сооовсем другие параметры уже.
И по хорошему все предыдущие, например, 90 точек, очень сильно должны отличаться от 1-й - а это не так...

[Igors]

Уязвимое место: представим, что мы посчитали точку 1.
Теперь пришло еще 100 точек, которые лежат примерно на одной прямой и отстоят друг от друга чуть менее чем на R.
Получается, что эти 100 точек будут скопированы с 1-й, и точка на удалении 100R от 1-й будет иметь те же самые свойства.

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

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

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

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