使用 FLANN 计算半径中的精确最近邻时出错

Question

我正在尝试查找大型 3D 点数据集中相邻节点的确切数量。目标是让数据集的每个点检索具有给定半径的区域中所有可能的邻居。 FLANN 确保对于低维数据可以检索到确切的邻居，而与蛮力搜索相比，情况似乎并非如此。邻居对于进一步计算至关重要，因此我需要确切的数字。我测试了一点点增加半径，但似乎不是这个问题。有人知道如何使用 FLANN 或其他 C++ 库计算确切的邻居吗？

代码：

// All nodes to be tested for inclusion in support domain.
flann::Matrix<double> query_nodes = flann::Matrix<double>(&nodes_pos[0].x, nodes_pos.size(), 3);

// Set default search parameters
flann::SearchParams search_parameters = flann::SearchParams();
search_parameters.checks = -1;
search_parameters.sorted = false;
search_parameters.use_heap = flann::FLANN_True;

flann::KDTreeSingleIndexParams index_parameters = flann::KDTreeSingleIndexParams();
flann::KDTreeSingleIndex<flann::L2_3D<double> > index(query_nodes, index_parameters);
index.buildIndex();

//FLANN uses L2 for radius search.
double l2_radius = (this->support_layer_*grid.spacing)*(this->support_layer_*grid.spacing);
double extension = l2_radius/10.;
l2_radius+= extension;

index.radiusSearch(query_nodes, indices, dists, l2_radius, search_parameters);

Answer 1

您应该查看 flann-manual 的第 6+ 页，以微调您的搜索参数，例如 target_precision，它应该设置为 1，以获得 "maximum" 的准确性。

该参数在近似最近邻搜索 (ANNS) 中经常以 epsilon (ε) 形式出现，用于高维空间，以便（尝试）击败维度的诅咒。据我所知，FLANN 通常用于 128 维，而不是 3 维，这可以解释您遇到的糟糕表现。

一个c++ library that works well in 3 dimensions is CGAL。然而，它比 FLANN 大得多，因为它是计算几何的库，因此它提供了很多问题的功能，而不仅仅是 NNS。

Answer 2

尝试nanoflann。它专为低维空间而设计，并给出 exact 最近邻。此外，它只是一个头文件，您可以 "install" 或直接复制到您的项目中。

使用 FLANN 计算半径中的精确最近邻时出错

Error in calculating exact nearest neighbors in radius with FLANN

c++

nearest-neighbor

flann

exact-match

approximate-nn-searching