在本教程中，我们将介绍如何使用 KdTree 查找特定点或位置的 K 个最近邻，然后我们还将介绍如何查找用户指定的某个半径内的所有邻居（在本例中为随机）。

理论入门

k-d 树或 k 维树是计算机科学中使用的一种数据结构，用于在具有 k 维的空间中组织一定数量的点。它是一个二叉搜索树，上面施加了其他约束。K-d 树对于范围和最近邻搜索非常有用。出于我们的目的，我们通常只处理三维的点云，所以我们所有的k-d树都是三维的。k-d 树的每个级别都使用垂直于相应轴的超平面沿特定维度拆分所有子级。在树的根部，所有子级都将根据第一维进行拆分（即，如果第一维坐标小于根，它将位于左子树中，如果大于根，则显然将在右子树中）。树中的每个级别都在下一个维度上划分，一旦所有其他维度都用尽，就会返回到第一个维度。构建 k-d 树的最有效方法是使用分区方法，例如快速排序用于将中位数点放置在根部，并将所有具有较小一维值的所有内容放在左侧，将较大的所有内容放置在右侧。然后，对左右子树重复此过程，直到要分区的最后一个树仅由一个元素组成。

代码

#include <pcl/point_cloud.h>
#include <pcl/kdtree/kdtree_flann.h>

#include <iostream>
#include <vector>
#include <ctime>

int
main ()
{
  srand (time (NULL));

  pcl::