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

[Igors]

Добрый день

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

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

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

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

Спасибо

[Racheengel]

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

[Igors]

а) непонятно, а что сортировать-то? стены? нормали? точки?

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

[Igors]

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

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

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

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

[Racheengel]

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

[Igors]

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

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

[Racheengel]

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

[Igors]

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

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

Код

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

[m_ax]

Требуется для заданной точки P с нормалью N найти все ближайшие к ней в заданном радиусе R,

kd-tree? 

[Racheengel]

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

[Igors]

kd-tree? 

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

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

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

[m_ax]

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

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

[Igors]

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

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

Ну например, по скалярному произведению.. 

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

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

[m_ax]

Ну вот, еще один "держится за стены"

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

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

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

[Igors]

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

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

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

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

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

r = sin(angle / 2) * 2;

Да, но что делать если есть и позиция и нормаль? Просто 6-мерный вектор - явно глупо, измерения "неоднородны". Тогда что?