Поиск радиуса нанофланна
У меня есть сомнения относительно параметра search_radius в нанофланах radiusSearch функция. Мой код такой:
#include <iostream>
#include <vector>
#include <map>
#include "nanoflann.hpp"#include "Eigen/Dense"
int main()
{
Eigen::MatrixXf mat(7, 2);
mat(0,0) = 0.0; mat(0,1) = 0.0;
mat(1,0) = 0.1; mat(1,1) = 0.0;
mat(2,0) = -0.1; mat(2,1) = 0.0;
mat(3,0) = 0.2; mat(3,1) = 0.0;
mat(4,0) = -0.2; mat(4,1) = 0.0;
mat(5,0) = 0.5; mat(5,1) = 0.0;
mat(6,0) = -0.5; mat(6,1) = 0.0;
std::vector<float> query_pt(2);
query_pt[0] = 0.0;
query_pt[1] = 0.0;
typedef nanoflann::KDTreeEigenMatrixAdaptor<Eigen::MatrixXf> KDTree;
KDTree index(2, mat, 10);
index.index->buildIndex();
{ // Find nearest neighbors in radius
const float search_radius = 0.1f;
std::vector<std::pair<size_t, float> > matches;
nanoflann::SearchParams params;
const size_t nMatches = index.index->radiusSearch(&query_pt[0], search_radius, matches, params);
std::cout << "RadiusSearch(): radius = " << search_radius << " -> "<< nMatches << " matches" << std::endl;
for(size_t i = 0; i < nMatches; i++)
std::cout << "Idx[" << i << "] = " << matches[i].first
<< " dist[" << i << "] = " << matches[i].second << std::endl;
std::cout << std::endl;
}
}
Я хочу, чтобы точки находились в радиусе 0,1, Итак, я ожидал, что это первые три элемента в матрице, но, к моему удивлению, он вернул первые 5 элементов. Проверка возврата расстояний мне кажется, что это не фактическое расстояние, а квадрат расстояния (верно?), Поэтому я возводил квадрат в радиус, чтобы получить то, что ожидал, но, к сожалению, он возвращает только первую точку.
Таким образом, я немного увеличил радиус от 0,1 ^ 2 = 0,01 в 0.02 и, наконец, получил очки, которые я хотел.
Теперь вопрос заключается в том, не следует ли включать точки, лежащие по периметру окрестности? Где я могу изменить это условие в нанофлане?
Решение
Полное определение KDTreeEigenMatrixAdaptor начинается так:
template <class MatrixType, int DIM = -1,
class Distance = nanoflann::metric_L2,
typename IndexType = size_t>
struct KDTreeEigenMatrixAdaptor
{
//...
Итак, да: по умолчанию метрикой является квадрат Евклидова расстояния, L2_Adaptor структура, и задокументировано следующим образом:
Квадратный евклидов дистанционный функтор (универсальная версия, оптимизированная для наборов данных высокой размерности).
Что касается второго вопроса, то здесь есть два аспекта. Во-первых, вы не должны полагаться на равенство, когда речь идет о числах с плавающей запятой (обязательная ссылка: Дэвид Голдберг, Что должен знать каждый компьютерщик об арифметике с плавающей точкой, ACM Computing Surveys, 1991).
Во-вторых, в принципе, вы правы. Нанофланн основан на FLANN, в исходном коде которого вы можете найти реализацию CountRadiusResultSet класс, используемый radiusSearch метод поиска. Его ключевой метод имеет следующую реализацию:
void addPoint(DistanceType dist, size_t index)
{
if (dist<radius) {
count++;
}
}
В то время как кажется, что общее определение этой проблемы включает «меньше или равно», как, например, в следующей ссылке (Мэтью Т. Дикерсон, Дэвид Эппштейн, Алгоритмы для задач приближения в больших размерностях, Вычислительная геометрия, 1996):
Проблема 1 (Поиск ближнего радиуса с фиксированным радиусом) Для заданного конечного множества S из n различных точек в Rd и расстояние ��. Для каждой точки p ∈ S выведите все пары точек (p, q), q ∈ S, для которых расстояние от p до q равно меньше или равно ��.
(последний акцент мной)
Тем не менее, это математика, а в компьютерных науках арифметические задачи с плавающей точкой эффективно препятствуют мысли о равенстве в такой строгой манере.
Кажется, что ваш единственный выбор — немного увеличить радиус, потому что использование CountRadiusResultSet класс жестко запрограммирован в radiusSearch Реализация метода внутри FLANN.
Другие решения