Russian Qt Forum

Добрый день

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

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

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

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

Спасибо

а) непонятно, а что сортировать-то? стены? нормали? точки?
б) как это должно выглядеть ("на картинке"), в чём собственно суть задачи?

Точки в которых записаны нормали

По ходу дела образовалась еще задача, которая включает предыдущую.

Я всегда считал что делать что-то для 4 и более измерений (типа "обобщать") - так, "для галочки", практического применения не имеет. Но вот "за мной пришли" :)

Как и в начальной задаче, на стенах комнаты разбросаны точки, в каждую записана нормаль. Требуется для заданной точки P с нормалью N найти все ближайшие к ней в заданном радиусе R, а также с нормалями отклоняющимися от N не более чем на заданный угол (напр 10 градусов)

Правда никаким "формальным обобщением" (типа template) здесь и не пахнет, как всегда, каждое новое измерение "меняет сущность". Тем не менее "N измерений" (N > 3) налицо

А известно заранее, какая точка принадлежит какой стене?

Нет. "Стена" - это просто для примера чего нужно добиться, данных для стены нема

Тогда, как говорится, "мало данных". Нормали у нескольких стен могут совпадать. Необходимо как минимум иметь координаты точек в пространстве и информацию о том, к какой "стене" они принадлежат.

Ну шо так тяжко, совсем старый уже? :) Конечно есть и координаты и нормали

C++ (Qt)
struct CPoint {
  QVector3D position;
  QVector3D normal;
...
};

kd-tree?  :)

эх "Старость не радость"...
Координаты есть - это уже хорошо. А координаты стен, может, тоже где-то лежат? :)

И как Вы себе представляете отсечку/деление "по нормали"?

Ну да, "может еще че дадут" (логика кота  :)). Стены - просто конкретный пример, в общем случае есть "3D сцена" (со всеми вытекающими)

Ну если стены известны (нормали к каждой из стен), то принадлежность произвольного вектора можно к какой либо из стен (с заданной точностью) можно определить..
Ну например, по скалярному произведению.. 

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

А разве есть какой-то еще пример?  :)

Возможно есть смысл заняться сначала более простой задачей (стартовый пост). Расстояние между векторами нормалей обратно пропорционально скалярному произведению, и эти 2 вещи однозначно переводятся друг в друга. Но...

А за что ещё держаться, если такая постановка проблемы?
Да, возможно kd-дерево будет скудным (всего 4 стены), но хоть что-то..
А как Вы вообще себе представляете сортировку в пределах одной стены? Какой критерий?

Ну это самый разумный..

Нормальная, творческая постановка, то Вы, как всегда, тормозите.

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

Возможно хотелась такая постановка "чтобы сразу знать как решать", но у меня таких нет :).

Рассмотрим только нормаль (стартовый пост). В пр-ве это соответствует точкам на поверхности сферы единичного радиуса. Обычное kd-tree будет работать, нужно только перевести угол отклонения в радиус, это несложно
Да, но что делать если есть и позиция и нормаль? Просто 6-мерный вектор - явно глупо, измерения "неоднородны". Тогда что?

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

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

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

И шо делать?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

Псевдокод:

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите: У Вас есть 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). Ну это в общем случае, и это приемлемо. Однако проекции векторов распределены на плоскости совсем неравномерно, можно ли это учесть?

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

В лоб нельзя?