用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

试试nanoflann。它是为低维空间设计的，并给出了精确的近邻。此外，它只是一个头文件，您可以"安装"或只是复制到您的项目。

Answer 2

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

该参数通常在近似最近邻搜索(ANNS)中被发现为ε (ε)，它用于高维空间，以(尝试)克服维度的诅咒。据我所知，FLANN通常用于128维，而不是3维，这可能解释了您遇到的糟糕性能。

在三维空间中工作得很好的c++库是CGAL。然而，它比FLANN要大得多，因为它是一个计算几何的库，因此它为许多问题提供了功能，而不仅仅是神经网络。