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

[Igors]

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

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

[m_ax]

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

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

[Igors]

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

Ах как быстро завершен мыслительный процесс (а он вообще начинался?). Ну да, как же мы можем "искать быстро" если заранее не построили нужных структур для поиска? А строить их всякий раз наверняка обойдется дороже перебора. Вот и все, и нефиг тут думать! Низзя!

Хотя есть одна идейка... Простая, всем известная, можно сказать "детская" 

[m_ax]

Хотя есть одна идейка... Простая, всем известная, можно сказать "детская" 

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

[Igors]

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

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

Собсно проблема в том что "кратность" поиска здесь мала, напр всего 200. Значит нужно делать "самые дешевые" структуры что помогут искать быстрее. Напрашивается "регулярная сетка". Прогоняем все найденные по расстоянию и заносим их в свои ячейки. Потом для каждого из 200 смотрим что сидит в ихней ячейке (и, возможно, соседних). Вряд ли это "так уж ускорит", но позорное пятно квадратичного перебора смоет.

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

Ну вот, сейчас опять начнется "чего-то не понял" и.т.п.

[m_ax]

Ну вот, сейчас опять начнется "чего-то не понял" и.т.п.  

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

Псевдокод:

Код

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?
Так?

[Igors]

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

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

Сортировка по 2 и более ключам здесь смысла не имеет. Ну отсортировали, как бум искать? Кстати kd-tree сортированный result вовсе не гарантирует

[m_ax]

Кстати kd-tree сортированный result вовсе не гарантирует

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

Сортировка по 2 и более ключам здесь смысла не имеет. Ну отсортировали, как бум искать?

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

[Igors]

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

Чего это? Та же регулярная (или нерегулярная) сетка имеет сложность O(N). Правда нужны хорошие "руки" чтобы здесь ее реализовать.

Кстати если так уж хотелось покритиковать постановку - это можно было легко сделать. При миллионах исходных точек скорее всего "чистый" поиск по нормали выдаст много тысяч подходящих/ближайших даже при отклонении < 1 градуса. А при углах 5-10 и подавно.

[m_ax]

Чего это? Та же регулярная (или нерегулярная) сетка имеет сложность O(N). Правда нужны хорошие "руки" чтобы здесь ее реализоват

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

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

[Igors]

Стоит ли создавать некие новые структуры, если речь идёт о O(N) против O(N log(N))?

Какой "log", откуда он тут взялся? O(N * M), где N - число запросных точек, M - найденных по первому критерию близости (расстоянию). Рабочий случай N = 200, M = 100, бОльшие значения возможны.

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

Я уже сказал как - хеш. Получается O(M) + O(N) (занесение в хеш + поиск в нем). Правда неизвестно насколько это быстрее

Оно вообще того стоит?

"стоит или нет" означает "это для меня слишком трудно, сложно, давайте искать как обойти". В принципе это нормально, но "вторая часть" почему-то никогда не звучит

[m_ax]

Какой "log", откуда он тут взялся?

Смотрите: У Вас есть result.. Вы его можете отсортировать по положениям точек (O(N log(N))) и аналогично по нормалям.
Т.е. грубо говоря, у Вас будет два контейнера, отсортированных.
В чём проблема, имея их, вытащить нужные точки?

Я уже сказал как - хеш.

Так это не спасёт.. Формирование хэша тоже дорого обходится..
Пользователь задаёт точку и радиус. kd-tree даёт вам result..
Вы хотите result в хэш преобразовать?
 

[Igors]

Смотрите: У Вас есть result.. Вы его можете отсортировать по положениям точек (O(N log(N))) и аналогично по нормалям.
Т.е. грубо говоря, у Вас будет два контейнера, отсортированных.
В чём проблема, имея их, вытащить нужные точки?

Почему два? И зачем вообще сортировать если поиску это никак не помогает?

Так это не спасёт.. Формирование хэша тоже дорого обходится..
Пользователь задаёт точку и радиус. kd-tree даёт вам result..
Вы хотите result в хэш преобразовать?

Чего это оно "дорого"? Я же не собираюсь юзать std::unordered_map и.т.п. Есть массив (preallocated) что хранит головы списков. Перед началом поиска он зачищается (memset).  Обе ф-ции (занесение в хеш и поиск) получают на вход точку и по ее вектору напр-я вычисляют ячейку/эл-т этого массива. Занесение линкует точку к ячейке, поиск пробегается по списку. Здесь все ясно.

По сути все сводится к тому "как соскочить на ячейку" имея вектор напр-я (x, y, z). Шаблонное решение - получить инты из x, y, z и дальше банальный hash, остаток от деления. Как это усилить? Предположим на входе 2D вектор (x, y). Тогда ячейка вычисляется гораздо проще, как индексы двумерного массива. Да и точнее. Механически переносить это на 3 измерения, как обычно, плохо (опустим подробности). Вспоминаем что длины всех векторов = 1. Так не использовать ли проекцию вектора на плоскость, напр XZ ? Правда за отбрасывание одной координаты придется заплатить - нужно иметь 2 хеша (один для +y, др для -y). Ну это в общем случае, и это приемлемо. Однако проекции векторов распределены на плоскости совсем неравномерно, можно ли это учесть?

Успеваете за ходом мысли? Если нет, не торопитесь чего-то отвечать, подумайте. А я пока чайку нагною..

[qtkoder777]

Добрый день

Пример: на стенах комнаты разбросаны точки, в каждую записана нормаль N (грубо говоря "перпендикуляр к стене"). Требуется:

а)  отсортировать так чтобы сначала шли точки первой стены, затем второй и.т.д

b) для заданного вектора V найти точку с ближайшей нормалью (минимальным углом между V и N)

Как-то выглядит "совершенно нерешаемо"

Спасибо

В лоб нельзя?