Пространственный запрос k-го ближайшего соседа точки

Я работаю над алгоритмом, которому постоянно требуется (евклидово) расстояние до k-й ближайшей точки из некоторой заданной точки запроса, взятой из вектора точек. Кроме того, мне постоянно нужно найти все точки в пределах заданного радиуса точки.

Я думаю об использовании деревьев k-d из библиотеки nanoflann. Однако функция knnSearch() возвращает все k ближайших соседей, что мне не нужно. (Хотя функция radiusSearch() меня вполне устраивает).

Есть ли более эффективный способ получить то, что мне нужно, кроме как каждый раз перебирать все k ближайших соседей? Лучшая структура данных или лучшая реализация? (Я использую С++.)


c++ data-structures knn spatial nearest-neighbor
person ameya.dubey    schedule 02.09.2017    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Я думаю об использовании k-d деревьев

Отличный выбор для 2D или 3D.

kd-деревья — хороший выбор для низкоразмерных данных (которые, я полагаю, у вас есть, поскольку nanoflann «в основном оптимизирован для 2D или 3D-облаков точек»).

Есть ли более эффективный способ получить то, что мне нужно, кроме как каждый раз перебирать все k ближайших соседей?

Вам нужен k-й ближайший сосед (NN), но при поиске дерева kd для k NN дорогостоящей операцией (с точки зрения времени) является поиск первого NN (что требует от вас спуска вниз по дереву, начиная с самого начала). корень к листу).

Поиск 2-го, 3-го или другого индексированного NN является относительно дешевым, и я очень сомневаюсь, что это повредит производительности (т.е. что получение k-го NN из k NN, возвращаемых деревом, будет узким местом).

Итак, я настоятельно рекомендую вам не беспокоиться об этом шаге.

Лучшая структура данных или лучшая реализация?

Я так не думаю. Я не использовал nanoflann, но использовал CGAL для такого рода запросов, и стоит попробовать (однако CGAL требует установки (не проще простого), а nanoflann — это просто заголовок).

person gsamaras    schedule 03.09.2017
comment
Известно, что для любого заданного набора данных размеры равны 5 или меньше. Рад узнать, что я не являюсь причиной узкого места в коде. На данный момент я придерживаюсь nanoflann именно потому, что он включает заголовки и реализует только деревья k-d, и это все, что мне нужно. Спасибо. - person ameya.dubey; 03.09.2017