Russian Qt Forum
Апрель 29, 2024, 03:33 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Russian Qt Forum > Forum > Программирование > Алгоритмы > Сортировка и поиск по вектору нормали
Страниц: 1 [2] 3   Вниз
« предыдущая тема следующая тема »
  Печать  
Автор Тема: Сортировка и поиск по вектору нормали  (Прочитано 12587 раз)
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #15 : Март 20, 2021, 14:37 »
Цитировать
Да, но что делать если есть и позиция и нормаль? Просто 6-мерный вектор - явно глупо, измерения "неоднородны". Тогда что?
Вот) А что для Вас важнее? Близость по положению или близость по нормали?
Записан
Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #16 : Март 20, 2021, 15:17 »
Цитата: m_ax от Март 20, 2021,  14:37
Вот) А что для Вас важнее? Близость по положению или близость по нормали?
А что важнее: рука или нога? Рука? Ну так давайте ногу отрежем, она ведь не очень нужна Улыбающийся Ну ладно, все равно мыслей нет (у меня тоже), давайте покалякаем.

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

И шо делать?
Записан
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #17 : Март 20, 2021, 15:27 »
Цитировать
А что важнее: рука или нога?
А я не знаю.. В одном случае может рука, а в другом - нога..
Я просто не вижу однозначного критерия для построения дерева..
Я бы со своим наивным подходом рассуждал бы так: Давайте вначале, в пределах заданного радиуса R найдём все ближайшие точки.
А потом отсеем из них все, которые по нормали далеки (ну с заданной точностью).. Нет? 
Записан
Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #18 : Март 20, 2021, 15:55 »
Цитата: m_ax от Март 20, 2021,  15:27
Я бы со своим наивным подходом рассуждал бы так:
Ну почему "наивным" - вполне нормальным, просто он "ни на что не претендует"

Цитата: m_ax от Март 20, 2021,  15:27
Давайте вначале, в пределах заданного радиуса R найдём все ближайшие точки.
А потом отсеем из них все, которые по нормали далеки (ну с заданной точностью).. Нет?
Так отсеивать придется снова и снова (для каждого из 200 излучаемых лучей). Тут мы все и сожжем
Записан
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #19 : Март 20, 2021, 16:24 »
Цитировать
Так отсеивать придется снова и снова (для каждого из 200 излучаемых лучей). Тут мы все и сожжем
Нет! Один раз выбираем окрестность радиуса R. Во втором проходе выкидываете все точки, которые по нормали не попали..
В итоге два дерева получается - первое по близости, второе по нормали..
Записан
Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #20 : Март 20, 2021, 16:27 »
Да во втором случае даже и дерево, возможно, и не понадобится..
« Последнее редактирование: Март 20, 2021, 16:34 от m_ax » Записан
Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #21 : Март 20, 2021, 16:34 »
Цитата: m_ax от Март 20, 2021,  16:24
В итоге два дерева получается - первое по близости, второе по нормали..
В смысле "глобальных"? Так их не удается "срастить". Первое найдет 100, второе 1000, искать "пересечения" пол-дня.

Цитата: m_ax от Март 20, 2021,  16:27
Да во втором случае даже и дерева, возможно, и не понадобится..
А прямой перебор "по нормали" точно сожрет до фига.

Не горячитесь, задача очень непростая, не исключено что (хорошего) решения вообще нет
« Последнее редактирование: Март 20, 2021, 16:56 от Igors » Записан
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #22 : Март 20, 2021, 17:30 »
Цитировать
В смысле "глобальных"? Так их не удается "срастить". Первое найдет 100, второе 1000, искать "пересечения" пол-дня.
Я имею в виду, что коль скоро определён критерий близости точек, то зная радиус R, можно за порядка log(N) найти все точки, лежайшие внутри этого радиуса..
А у же потом отсеять все лишние.. Т.е. kd-дерево строится по принципу ближайших к заданной точки. Дело, конечно, не однозначное.. Ну можно среднее взять и с ним сравнивать..
Ну или.. Постановка проблемы не однозначна просто..
И да, тот чувак не из Ярославля, а с Ростова-на-Дону Улыбающийся    Кстати, красивый город)
Записан
Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #23 : Март 21, 2021, 11:38 »
Цитата: m_ax от Март 20, 2021,  17:30
Я имею в виду, что коль скоро определён критерий близости точек, то зная радиус R, можно за порядка log(N) найти все точки, лежайшие внутри этого радиуса..
А у же потом отсеять все лишние..
Впечатление что "опять не въехал"  Плачущий Ладно, еще пожуем

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

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

Сообщений: 2094



Просмотр профиля
« Ответ #24 : Март 21, 2021, 14:37 »
Цитировать
И да, тот чувак не из Ярославля, а с Ростова-на-Дону
Если  мы об одном человеке говорим?
Записан
Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #25 : Март 21, 2021, 14:50 »
Цитировать
Из данной точки выбрасываются 200 (по дефаулту) лучей. Напр-е каждого (нормаль) известно. Перед выбросом каждого просматриваем ближайшие точки в радиусе R.
Так какое  условие? Есть реализация kd-дерева - выложу. Когда однозначно критерий определите, тогда и решение будет..
Записан
Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #26 : Март 21, 2021, 15:06 »
Цитата: m_ax от Март 21, 2021,  14:50
Так какое  условие?
Прочтите хотя бы мой предыдущий пост

Цитата: m_ax от Март 21, 2021,  14:50
Есть реализация kd-дерева - выложу.
Спасибо, но не нужно, последние 25 лет пользуюсь своей

Цитата: m_ax от Март 21, 2021,  14:50
Когда однозначно критерий определите, тогда и решение будет..
С чего Вы взяли что умеете решать такие задачи?  Улыбающийся Напр я таких иллюзий не питаю, может удастся, но очень может быть что и нет.  Не надо петь вечную песню "плохая, неясная постановка", если мыслей нет - то их и нет. Тем более обещать что, мол, "будет"  Улыбающийся
Записан
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #27 : Март 22, 2021, 15:28 »
Мы, похоже, разными категориями мыслим..

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

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

Arch Linux Plasma 5
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #28 : Март 22, 2021, 16:32 »
Цитата: m_ax от Март 22, 2021,  15:28
Проблема теперь сводится к тому, чтобы из всех этих точек выкинуть те, которые по критерию близости по направлению не подходят?
Да, причем придется это делать для каждого из 200 сгенерированных лучей
Цитата: m_ax от Март 22, 2021,  15:28
Мы, похоже, разными категориями мыслим..
Да мЫшление тут еще не началось..
Записан
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #29 : Март 22, 2021, 16:41 »
Цитировать
Да, причем придется это делать для каждого из 200 сгенерированных лучей
Ну да.. А какие ещё есть варианты, когда для каждого из лучей нужно условие проверить?
Записан
Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Страниц: 1 [2] 3   Вверх
  Печать  
« предыдущая тема следующая тема »
 
Перейти в:  


Страница сгенерирована за 0.048 секунд. Запросов: 22.