1

我正在尝试在大型 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);
4

2 回答 2

1

试试nanoflann。它专为低维空间而设计，并提供精确的最近邻。此外，它只是一个头文件，您可以“安装”或复制到您的项目中。

于 2019-07-26T16:57:34.250 回答
0

您应该检查flann-manual中的第 6 页以上，以微调您的搜索参数，例如target_precision应设置为 1，以获得“最大”精度。

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

一个在 3 维中运行良好的库是CGAL。然而，它比 FLANN 大得多，因为它是一个计算几何库，因此它为许多问题提供了功能，而不仅仅是 NNS。

于 2016-10-31T14:42:46.070 回答