Поиск ближайшего соседа для точек с направленными векторами.

У меня есть набор трехмерных точек, каждая из которых связана с направлением (например, единичный вектор). Учитывая другую точку + направление, я хотел бы определить ближайшую точку в наборе (используя стандартную 2-норму), которая также удовлетворяет определенному условию для векторов направления (например, угол между двумя векторами направления находится в пределах определенной угловой величины). Пока у меня есть поиск диапазона на основе KD-дерева по трехмерным точкам, а затем я проверяю, соответствует ли какая-либо из таких точек угловым ограничениям, но понимаю, что это очень неоптимизированный прием. Интересно, есть ли лучший способ сделать это.

Спасибо заранее.


nearest-neighbor kdtree
person fred august    schedule 11.02.2014    source источник
comment
Не могли бы вы также подробно рассказать о количестве проблем, с которыми вы имеете дело? И насколько быстро / медленно ваш текущий алгоритм? Для чего вы пытаетесь оптимизировать? Скорость? Объем памяти? Ясность кода? Моим первым побуждением было попытаться сформулировать это как задачу выпуклой оптимизации, поскольку функция, которая возвращает ближайшую точку к набору точек, является выпуклой функцией, а ваше ограничение кажется линейным.   -  person lightalchemist    schedule 11.02.2014
comment
Примерно от 8к до 15к очков. Хотелось бы оптимизировать по скорости - память точно не проблема. Спасибо!   -  person fred august    schedule 11.02.2014

Ответы (3)


arrow_upward
2
arrow_downward

Для меня основная проблема в вашей текущей формулировке заключается в том, что угловое сравнение является ядровым (т.е. требует сравнения между векторами). Если вы расширите ориентацию каждого угла до отдельного 2D-вектора (cos theta, sin theta), тогда вы просто сможете выполнить еще один поиск ближайшего соседа с ограниченным радиусом в этом пространстве (KDTree должно быть в порядке) и пересечь два набора результатов.

person John Greenall    schedule 24.02.2014

arrow_upward
1
arrow_downward

Рассмотрите возможность использования R * -деревьев. Эта структура данных, основанная на прямоугольниках, вполне поддается сложным запросам.

Т.е. если вы можете проверить, может ли прямоугольник содержать точки, удовлетворяющие вашим ограничениям, тогда R * -дерево можно использовать для ускорения этого запроса. Индексы в ELKI являются расширяемыми, так что это может быть хорошей отправной точкой. Насколько я понимаю, вы должны уметь сформулировать это как функцию расстояния в ELKI, как в этот учебник в их вики: если прямоугольник не может удовлетворить ограничения, вы возвращаете бесконечное расстояние.

person Has QUIT--Anony-Mousse    schedule 24.02.2014

arrow_upward
1
arrow_downward

Вы писали давно, но я работаю над аналогичной проблемой и нашел несколько ответов, поэтому я опубликую и надеюсь, что это все еще будет полезно.

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

Ваше KD-дерево - хорошая отправная точка. Алгоритм в статье для R-деревьев будет работать также и для KD-дерева.

В документе описывается специализированная версия обычного поиска ближайшего соседа, которая выглядит следующим образом.

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

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

person Gene    schedule 06.04.2014