Ну и как Вы это себе представляете?
Оно вообще того стоит?
Стоит ли создавать некие новые структуры, если речь идёт о O(N) против O(N log(N))?
Вот у Вас есть result (vector<pair<point3d, point3d>>) не отсортированный ни по положениям, ни по нормалям.
Как Вы хотите, имея только его, за O(N) найти все точки, удвл. условию?

Да даже меньше.. Есть std::partial_sort,,

Да, согласен..

Ну тогда никакие структуры и "кластеризация" данных Вам не поможет.. Это всегда будет за O(N log (N))..
Если только не интерполировать начальные данные какой-либо "гладкой" функцией..

Ну как уж тут не  без этого..

Псевдокод:

C++ (Qt)
typedef vector<pair<point3d, point3d>> data_t; 
/* 
первый point3d - положение точки, второй - вектор нормали
*/ 
 
data_t data; 
// ...
kd_tree tree(data) // формируем дерево. Один раз.
//...
double R; // радиус
point3d p; // выбираемая пользователем точка
 
data_t result = tree.nearest_in_radius(p, R);
 
 

Здесь result отсортирован по положениям, ближайшим к p?
А нужно ещё по-быстрому отсортировать его по нормалям к p?
Так?

Ну дык, не томите)

Это больше риторический вопрос.. Первый критерий решается построением дерева. А вот второй - ничего не остаётся, как прямой перебор..

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

Да что-то пока руки не доходят.. Это больше по работе.. Такое расширение boost'а.. Пишу понемногу для своих нужд 

А это мои, так сказать, наработки) 

Это такая штука, которая минимум функции многих переменных находит)
В данном случае размерность = 2: Amplitude и omega)

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


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

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

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

Да и ещё.. minsearch - многопоточный, так что по хорошему нужно лочить вызываемую функцию...
Конкретно в этом примере проблем быть не должно, но имейте в виду..

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

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