Я работаю над алгоритмом, которому постоянно требуется (евклидово) расстояние до k-й ближайшей точки из некоторой заданной точки запроса, взятой из вектора точек. Кроме того, мне постоянно нужно найти все точки в пределах заданного радиуса точки.
Я думаю об использовании деревьев k-d из библиотеки nanoflann. Однако функция knnSearch() возвращает все k ближайших соседей, что мне не нужно. (Хотя функция radiusSearch() меня вполне устраивает).
Есть ли более эффективный способ получить то, что мне нужно, кроме как каждый раз перебирать все k ближайших соседей? Лучшая структура данных или лучшая реализация? (Я использую С++.)
Ответ 1 · рейтинг 1 · gsamaras
Я думаю об использовании 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 - это просто заголовок).
