nanoflann库使用笔记

zxl19 2023-04-11

我的nanoflann库使用笔记。

nanoflann Hello World

nanoflann是基于K-D树（K-Dimensional Tree，K-D Tree）的最近邻（Nearest Neighbor，NN）搜索库；
nanoflann支持$\mathbb{R}^{2}$、$\mathbb{R}^{3}$欧氏空间，$\mathrm{SO}\left(2\right)$、$\mathrm{SO}\left(3\right)$旋转群上的最近邻搜索；
nanoflann使用C++11标准，只由一个头文件构成（header-only），推荐直接将头文件添加到项目中，使用时需要包含头文件：
```
 #include "nanoflann.hpp"
```
在Ubuntu 21.04及其之后的版本中可以通过软件包管理器安装：
```
 sudo apt install libnanoflann-dev
```

CMakeLists

# 方法一：本地安装（待测试）
find_package(nanoflann REQUIRED QUIET)
# 方法二：非本地安装（推荐）
set(NANOFLANN_INCLUDE_DIRS "${PROJECT_SOURCE_DIR}/third_party/nanoflann")

include_directories(${NANOFLANN_INCLUDE_DIRS})

示例

以std::vector<std::vector<T>>或std::vector<Eigen::VectorXd>的点云数据结构为例，在构建K-D树时需要使用对应的适配器KDTreeVectorOfVectorsAdaptor：

// C++98/03
typedef std::vector<Eigen::Vector3d, Eigen::aligned_allocator<Eigen::Vector3d>> VVec3d;
typedef KDTreeVectorOfVectorsAdaptor<VVec3d, double> KdtreeType;

// C++11
template <int N, typename T>
using Vec = Eigen::Matrix<T, N, 1>;
template <int N, typename T>
using VVec = std::vector<Vec<N, T>, Eigen::aligned_allocator<Vec<N, T>>>;
using VVec3d = VVec<3, double>;
using KdtreeType = KDTreeVectorOfVectorsAdaptor<VVec3d, double>;

// construct a kd-tree index:
// Dimensionality set at run-time (default: L2)
std::size_t dim;
VVec3d samples;
KdtreeType kdtree(dim /*dim*/, samples, 10 /* max leaf */);

// do a knn search
const std::size_t num_results = 3;
std::vector<std::size_t> ret_indexes(num_results);
std::vector<double> out_dists_sqr(num_results);

nanoflann::KNNResultSet<double> resultSet(num_results);

resultSet.init(&ret_indexes[0], &out_dists_sqr[0]);
bool found = kdtree.index->findNeighbors(resultSet, &query_pt[0], nanoflann::SearchParams());

// !在没有找到指定数量的最近邻点时会返回false
if (found) {
  std::cout << "resultSet.size() == num_results" << std::endl;
} else {
  std::cout << "resultSet.size() < num_results" << std::endl;
}

std::cout << "knnSearch(nn=" << num_results << "): \n";
for (size_t i = 0; i < resultSet.size(); i++) {
  std::cout << "ret_index[" << i << "]=" << ret_indexes[i] << " out_dist_sqr=" << out_dists_sqr[i] << std::endl;
}

注意事项

通过内部实现可以看出，KDTreeVectorOfVectorsAdaptor也可以支持自定义点云数据结构，需要满足以下要求：
- 点云：
  - 具有size()成员函数，返回点云中点的总数；
  - 支持通过下标运算符[]访问点云中的点；
- 点：
  - 具有size()成员函数，返回点的维度；
  - 支持通过下标运算符[]访问点的坐标；
nanoflann封装了findNeighbors()函数，可以通过knnSearch()函数进行最近邻搜索并获得最近邻点数量，与FLANN库的接口一致：
```
 // 返回最近邻点数量
 std::size_t knn_num = kdtree.index->knnSearch(&query_pt[0], num_results, &ret_index[0], &out_dist_sqr[0]);
```
当多个坐标完全相同的点都是最近邻点时，最近邻搜索返回的最近邻点顺序与其在点云中的保存顺序不具有对应关系；
当点云发生变化时，需要重新构建K-D树，否则会索引到错误的最近邻点坐标；

参考

jlblancoc/nanoflann

nanoflann库使用笔记

nanoflann Hello World

CMakeLists

最近邻搜索

示例

注意事项

参考