Сортировка и поиск по вектору нормали

[m_ax]

Да, но что делать если есть и позиция и нормаль? Просто 6-мерный вектор - явно глупо, измерения "неоднородны". Тогда что?

Вот) А что для Вас важнее? Близость по положению или близость по нормали?

[Igors]

Вот) А что для Вас важнее? Близость по положению или близость по нормали?

А что важнее: рука или нога? Рука? Ну так давайте ногу отрежем, она ведь не очень нужна Ну ладно, все равно мыслей нет (у меня тоже), давайте покалякаем.

Есть поверхность бомбардируемая лучами, но которая и сама излучает, испуская 200 (по дефаулту) лучей в заданных напр-ях. Идея сэкономить излучающие, используя (сохраненные) рез-ты "бомбардировки" в заданном радиусе R. Пробуем порешать стандартными средствами: используя kd-tree находим всех ближайших в радиусе R. Допустим нашли 100. И вот дальше сваливаемся в унылый перебор: для каждого заданного напр-я нужно проверять все 100, что недопустимо медленно. А затевать какое-то дерево "на ходу" еще хуже.

И шо делать?

[m_ax]

А что важнее: рука или нога?

А я не знаю.. В одном случае может рука, а в другом - нога..
Я просто не вижу однозначного критерия для построения дерева..
Я бы со своим наивным подходом рассуждал бы так: Давайте вначале, в пределах заданного радиуса R найдём все ближайшие точки.
А потом отсеем из них все, которые по нормали далеки (ну с заданной точностью).. Нет? 

[Igors]

Я бы со своим наивным подходом рассуждал бы так:

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

Давайте вначале, в пределах заданного радиуса R найдём все ближайшие точки.
А потом отсеем из них все, которые по нормали далеки (ну с заданной точностью).. Нет?

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

[m_ax]

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

Нет! Один раз выбираем окрестность радиуса R. Во втором проходе выкидываете все точки, которые по нормали не попали..
В итоге два дерева получается - первое по близости, второе по нормали..

[m_ax]

Да во втором случае даже и дерево, возможно, и не понадобится..

[Igors]

В итоге два дерева получается - первое по близости, второе по нормали..

В смысле "глобальных"? Так их не удается "срастить". Первое найдет 100, второе 1000, искать "пересечения" пол-дня.

Да во втором случае даже и дерева, возможно, и не понадобится..

А прямой перебор "по нормали" точно сожрет до фига.

Не горячитесь, задача очень непростая, не исключено что (хорошего) решения вообще нет

[m_ax]

В смысле "глобальных"? Так их не удается "срастить". Первое найдет 100, второе 1000, искать "пересечения" пол-дня.

Я имею в виду, что коль скоро определён критерий близости точек, то зная радиус R, можно за порядка log(N) найти все точки, лежайшие внутри этого радиуса..
А у же потом отсеять все лишние.. Т.е. kd-дерево строится по принципу ближайших к заданной точки. Дело, конечно, не однозначное.. Ну можно среднее взять и с ним сравнивать..
Ну или.. Постановка проблемы не однозначна просто..
И да, тот чувак не из Ярославля, а с Ростова-на-Дону    Кстати, красивый город)

[Igors]

Я имею в виду, что коль скоро определён критерий близости точек, то зная радиус R, можно за порядка log(N) найти все точки, лежайшие внутри этого радиуса..
А у же потом отсеять все лишние..

Впечатление что "опять не въехал"  Ладно, еще пожуем

Из данной точки выбрасываются 200 (по дефаулту) лучей. Напр-е каждого (нормаль) известно. Перед выбросом каждого просматриваем ближайшие точки в радиусе R. Если найдена хоть одна с близким напр-ем, то используем ее/их, луч не выбрасываем.

Очевидное решение: найти все точки в радиусе R и сохранить их в pre-allocated массиве. Дальше для каждого из 200 лучей отсеивать/просеивать содержимое этого массива. Ну т.е. по расстоянию ищем деревом, по нормали - перебором. Все ясно, но увы - это тормоз. Напр найдено 100 ближайших, 100 * 200 = 20K перебор.

[m_ax]

И да, тот чувак не из Ярославля, а с Ростова-на-Дону

Если  мы об одном человеке говорим?

[m_ax]

Из данной точки выбрасываются 200 (по дефаулту) лучей. Напр-е каждого (нормаль) известно. Перед выбросом каждого просматриваем ближайшие точки в радиусе R.

Так какое  условие? Есть реализация kd-дерева - выложу. Когда однозначно критерий определите, тогда и решение будет..

[Igors]

Так какое  условие?

Прочтите хотя бы мой предыдущий пост

Есть реализация kd-дерева - выложу.

Спасибо, но не нужно, последние 25 лет пользуюсь своей

Когда однозначно критерий определите, тогда и решение будет..

С чего Вы взяли что умеете решать такие задачи?  Напр я таких иллюзий не питаю, может удастся, но очень может быть что и нет.  Не надо петь вечную песню "плохая, неясная постановка", если мыслей нет - то их и нет. Тем более обещать что, мол, "будет" 

[m_ax]

Мы, похоже, разными категориями мыслим..

Прочтите хотя бы мой предыдущий пост

Из данной точки выбрасываются 200 (по дефаулту) лучей. Напр-е каждого (нормаль) известно. Перед выбросом каждого просматриваем ближайшие точки в радиусе R. Если найдена хоть одна с близким напр-ем, то используем ее/их, луч не выбрасываем.

Что значит "луч не выбрасываем"? Как я понял имеется набор точек (x, y, z) для каждой из которых задан вектор нормали. Хорошо. Теперь Вы генерируете 200 векторов (лучей) исходящих из заданной точки. У Вас есть kd-дерево, и значит что можно найти все ближайшие точки в окрестности радиуса R.
Проблема теперь сводится к тому, чтобы из всех этих точек выкинуть те, которые по критерию близости по направлению не подходят?
 

[Igors]

Проблема теперь сводится к тому, чтобы из всех этих точек выкинуть те, которые по критерию близости по направлению не подходят?

Да, причем придется это делать для каждого из 200 сгенерированных лучей

Мы, похоже, разными категориями мыслим..

Да мЫшление тут еще не началось..

[m_ax]

Да, причем придется это делать для каждого из 200 сгенерированных лучей

Ну да.. А какие ещё есть варианты, когда для каждого из лучей нужно условие проверить?