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

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

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

Сообщений: 11445


Просмотр профиля
« : Март 07, 2021, 07:47 »
Добрый день

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

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

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

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

Спасибо
Записан
Racheengel
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2679


Я работал с дискетам 5.25 :(


Просмотр профиля
« Ответ #1 : Март 17, 2021, 15:33 »
а) непонятно, а что сортировать-то? стены? нормали? точки?
б) как это должно выглядеть ("на картинке"), в чём собственно суть задачи?
Записан
What is the 11 in the C++11? It’s the number of feet they glued to C++ trying to obtain a better octopus.

COVID не волк, в лес не уйдёт
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #2 : Март 18, 2021, 08:48 »
Цитата: Racheengel от Март 17, 2021,  15:33
а) непонятно, а что сортировать-то? стены? нормали? точки?
Точки в которых записаны нормали
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #3 : Март 18, 2021, 08:59 »
По ходу дела образовалась еще задача, которая включает предыдущую.

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

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

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

Сообщений: 2679


Я работал с дискетам 5.25 :(


Просмотр профиля
« Ответ #4 : Март 18, 2021, 11:09 »
А известно заранее, какая точка принадлежит какой стене?
Записан
What is the 11 in the C++11? It’s the number of feet they glued to C++ trying to obtain a better octopus.

COVID не волк, в лес не уйдёт
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #5 : Март 18, 2021, 11:51 »
Цитата: Racheengel от Март 18, 2021,  11:09
А известно заранее, какая точка принадлежит какой стене?
Нет. "Стена" - это просто для примера чего нужно добиться, данных для стены нема
Записан
Racheengel
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2679


Я работал с дискетам 5.25 :(


Просмотр профиля
« Ответ #6 : Март 18, 2021, 12:07 »
Тогда, как говорится, "мало данных". Нормали у нескольких стен могут совпадать. Необходимо как минимум иметь координаты точек в пространстве и информацию о том, к какой "стене" они принадлежат.
Записан
What is the 11 in the C++11? It’s the number of feet they glued to C++ trying to obtain a better octopus.

COVID не волк, в лес не уйдёт
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #7 : Март 18, 2021, 12:10 »
Цитата: Racheengel от Март 18, 2021,  12:07
Тогда, как говорится, "мало данных". Нормали у нескольких стен могут совпадать. Необходимо как минимум иметь координаты точек в пространстве и информацию о том, к какой "стене" они принадлежат.
Ну шо так тяжко, совсем старый уже? Улыбающийся Конечно есть и координаты и нормали
Код
C++ (Qt)
struct CPoint {
  QVector3D position;
  QVector3D normal;
...
};
Записан
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #8 : Март 18, 2021, 12:23 »
Цитировать
Требуется для заданной точки P с нормалью N найти все ближайшие к ней в заданном радиусе R,
kd-tree?  Улыбающийся
Записан
Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

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

Сообщений: 2679


Я работал с дискетам 5.25 :(


Просмотр профиля
« Ответ #9 : Март 18, 2021, 12:31 »
эх "Старость не радость"...
Координаты есть - это уже хорошо. А координаты стен, может, тоже где-то лежат? Улыбающийся
Записан
What is the 11 in the C++11? It’s the number of feet they glued to C++ trying to obtain a better octopus.

COVID не волк, в лес не уйдёт
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #10 : Март 18, 2021, 13:17 »
Цитата: m_ax от Март 18, 2021,  12:23
kd-tree?  Улыбающийся
И как Вы себе представляете отсечку/деление "по нормали"?

Цитата: Racheengel от Март 18, 2021,  12:31
Координаты есть - это уже хорошо. А координаты стен, может, тоже где-то лежат? Улыбающийся
Ну да, "может еще че дадут" (логика кота  Улыбающийся). Стены - просто конкретный пример, в общем случае есть "3D сцена" (со всеми вытекающими)
Записан
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #11 : Март 18, 2021, 13:37 »
Цитировать
И как Вы себе представляете отсечку/деление "по нормали"?
Ну если стены известны (нормали к каждой из стен), то принадлежность произвольного вектора можно к какой либо из стен (с заданной точностью) можно определить..
Ну например, по скалярному произведению.. 
Записан
Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

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

Сообщений: 11445


Просмотр профиля
« Ответ #12 : Март 18, 2021, 14:14 »
Цитата: m_ax от Март 18, 2021,  13:37
Ну если стены известны (нормали к каждой из стен), то принадлежность произвольного вектора можно к какой либо из стен (с заданной точностью) можно определить..
Ну вот, еще один "держится за стены" Улыбающийся Конечно можно, но требуется макс быстро находить(всех) ближайших, а не "проверяться" (с тем чего нет).

Цитата: m_ax от Март 18, 2021,  13:37
Ну например, по скалярному произведению.. 
А разве есть какой-то еще пример?  Улыбающийся

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

Сообщений: 2094



Просмотр профиля
« Ответ #13 : Март 18, 2021, 16:39 »
Цитировать
Ну вот, еще один "держится за стены"
А за что ещё держаться, если такая постановка проблемы?
Да, возможно kd-дерево будет скудным (всего 4 стены), но хоть что-то..
А как Вы вообще себе представляете сортировку в пределах одной стены? Какой критерий?

Цитировать
А разве есть какой-то еще пример?
Ну это самый разумный..
Записан
Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

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

Сообщений: 11445


Просмотр профиля
« Ответ #14 : Март 19, 2021, 09:38 »
Цитата: m_ax от Март 18, 2021,  16:39
А за что ещё держаться, если такая постановка проблемы?
Нормальная, творческая постановка, то Вы, как всегда, тормозите.

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

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

Рассмотрим только нормаль (стартовый пост). В пр-ве это соответствует точкам на поверхности сферы единичного радиуса. Обычное kd-tree будет работать, нужно только перевести угол отклонения в радиус, это несложно
Цитировать
r = sin(angle / 2) * 2;
Да, но что делать если есть и позиция и нормаль? Просто 6-мерный вектор - явно глупо, измерения "неоднородны". Тогда что?
Записан
Страниц: [1] 2 3   Вверх
  Печать  
« предыдущая тема следующая тема »
 
Перейти в:  


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