导读： 3D摄像机(雷达、激光扫描、立体摄像机)获取的点云一般具有数据量大、分布不均匀等特点，数据主要集中在目标表面的大量点的集合（无序），不具备传统实体网格数据的几何拓扑信息；
要实现这些离散点基于邻域关系3358www.Sina.com/，需要考虑这些离散点之间的拓扑关系，快速查找比对功能
典型的空间索引是自顶向下逐步划分空间的各种索引结构，例如BSP树、k-d树、kdb树、r树、蜂窝树、八叉树等。 有了这些关系，就可以实现点云下采样、特征向量计算、点云匹配、点云分割等功能。 引用来源： http://robot.czxy.com/docs/PCL/chapter 01/decomposition /
k-d树(k-dimensional树的简称)是分割k维数据空间的数据结构。 主要适用于多维空间重要数据的检索。 例如，范围搜索和最近邻搜索。 K-D树是二进制空分树的特殊情况。 用于组织表示k维空间中点的几何，是一种具有其他约束的二叉树。 为了达到这个目的，所有的kd_tree都是三维的kd_tree，因为通常只在三个维度上进行处理，kd_tree的每个维度在指定的维度上隔离所有字节点，树根中的所有子节点在第一个指定的维度上
Kd-Tree分为Kd-Tree分割的原理和基于Kd-Tree的算法(一部分是所谓Kd-Tree自身的数据结构的构筑算法，另一部分是基于Kd-Tree的最近邻搜索算法)，如下分别
所以点云的数据处理中，最为核心的问题就是建立离散点之间的拓扑关系，以便于实现基于邻域关系的快速查找。
域名数据类型描述Node-data
数据向量
数据集中给定数目的据点是n维向量(这里即k维) )
范围
空间向量
此节点表示的空间范围
剥离
整数
垂直于分割超平面的方向轴编号
左倾
中小学树
由该节点分割超平面左部分空间内的所有数据点构成的k-d树
右
中小学树
由该节点分割超平面右部分空间内的所有数据点构成的k-d树
父级
中小学树
父节点
0.关于KdTree的元素名称
首先，通过简单直观的例子介绍中小学树算法。 假设有6个二维数据点{ { 2，3 }，5，4 }，9，6 }，4，7 }，8，1 }，7，2 }，数据点位于二维空间内(用图1的黑点表示)。 k-d树算法确定图1中这些分割空间的分割线(多维空间是分割平面，一般是超平面)。 下面将进一步演示k-d树如何决定这些分割线。
这个例子很简单，因为数据维只有二维，所以可以很容易地在x、y两个方向的轴上编号0，1，即split={ 0，1 }。 (其中0表示x，1表示y。
一.Kd-tree分割算法介绍
如果分别计算x、y方向数据的方差，则可知x方向的（1）确定split域的首先该取的值（确定x方向还是y方向方差大，以便于确认分割起点是x轴还是y轴），所以split字段值首先取0，即x轴方向；
方差最大
根据x轴方向的值2、5、9、4、8、7排序的中值为7 (中值)，因此node-data=) 7、2 )。 因此，该节点的分割超平面通过(7，2 )，垂直于split=0(x ) x轴)的直线x=7。
（2）确定Node-data的域值。
如图2所示，分割超平面x=7将整个空间分为两个部分。 x=7的部分是左子空间，包含3个节点{ (2，3 )，(5，4 )，(4，7 ) }。 另一个是右子空间，包含两个节点{ { 9，6 }，(8，1 ) }。
（3）确定左子空间和右子空间。
然后，通过对左子空间和右子空间内的数据重复根节点的过程，在进一步细分空间和数据集的同时，可以得到下一个子节点(5，4 )和(9，6 )。 这样重复，直到空间中只包含一个数据点，如图1所示。 最后生成的k-d树如图3所示。
（4）k-d树的构建是一个递归的过程。
标位于居中位置的点，令其当作第二个分割点。4. 沿着第二个点的y坐标进行分割........循环上边的过程，直至全部点分割结束为止。（实际上可以理解成：按照x-y-z-x-y-z...顺序向下分割）二. Kd-tree查找算法介绍 （查找在坐标系内，与某一个指定点之间，距离最近点的坐标）
上边的动图表示了通过KD-TREE寻找最近点的过程：
1.首先在起点A;
2.然后分别计算分支点B和点C距离待测点的距离，比较得到哪个点距离最近;（图中：B点距离带测点距离近，故选择B点）；
3.然后以B点为起点，分别计算D点和E点距离带测点之间的距离，取出这两个点之间，距离带测点之间最近的的那个点；
4.当KD-TREE已经检索到末端时，可以看到E点距离待测点较近，故可以先认E点是距离最近点；
5.进行核算：以待测点为圆心，以待测点到E点距离为半径，做圆，查看这个圆是否与其他Kd-tree的分区有交割，如果有的话，需要退回到前一个节点，然后去验算另一个分支内有无与待测点距离更近的点，若没有，那么就可以认为E点是距离待测点最近的点，点已找到。
更多的查找案例：http://robot.czxy.com/docs/pcl/chapter01/decomposition/
三.Kd-Tree 查找案例 （包含查找N个相邻点+查找半径范围内的邻域点）
#include <pcl/point_cloud.h>#include <pcl/kdtree/kdtree_flann.h>#include <iostream>#include <vector>#include <ctime>int main(int argc, char** argv){srand (time (NULL));//step1:创建仿真的点云数据pcl::PointCloud<pcl::PointXYZ>::Ptr cloud (new pcl::PointCloud<pcl::PointXYZ>);cloud->width =1000;cloud->height =1;cloud->points.resize(cloud->width*cloud->height);for(std::size_t i=0;i<cloud->size();++i){ (*cloud)[i].x= 1024.0f* rand()/ (RAND_MAX + 1.0f); (*cloud)[i].y= 1024.0f* rand()/ (RAND_MAX + 1.0f); (*cloud)[i].z= 1024.0f* rand()/ (RAND_MAX + 1.0f);}//step2:创建KDTREE相关对象pcl::KdTreeFLANN<pcl::PointXYZ> kdtree;kdtree.setInputCloud(cloud);//Step3:设置将被查询的点的信息pcl::PointXYZ searchPoint;searchPoint.x =1024.0f * rand () / (RAND_MAX + 1.0f);searchPoint.y =1024.0f * rand () / (RAND_MAX + 1.0f);searchPoint.z =1024.0f * rand () / (RAND_MAX + 1.0f);//step4:设置查询邻域点的数量,并且设置存储点的编号及点的距离的Vector对象int K = 10;std::vector<int> pointIdxNKNSearch(K);std::vector<float> pointNKNSquaredDistance(K);std::cout << "K nearest neighbor search at (" <<searchPoint.x << " " <<searchPoint.y << " " <<searchPoint.z << ") with K="<< K <<std::endl;//step5: 使用kdtree寻找邻域点if(kdtree.nearestKSearch(searchPoint, K,pointIdxNKNSearch ,pointNKNSquaredDistance ) > 0 ){ for(std::size_t i=0; i<pointIdxNKNSearch.size(); ++i){ std::cout << " " << (*cloud)[ pointIdxNKNSearch[i] ].x << " " << (*cloud)[ pointIdxNKNSearch[i] ].y << " " << (*cloud)[ pointIdxNKNSearch[i] ].z << " (squared distance: " << pointNKNSquaredDistance[i] << ")" << std::endl; }}/*以上为查找10个邻域点的方法；下边是查找预订点半径之内的点的数量*///step1: 设置用于存放点的Vector+存放距离的Vectorstd::vector<int> pointIdxRadiusSearch;std::vector<float> pointRadiusSquaredDistance;//Step2：设置查找半径信息float radius = 256.0f *rand()/(RAND_MAX +1.0f);std::cout << "Neighbors within radius search at (" << searchPoint.x << " " << searchPoint.y << " " << searchPoint.z << ") with radius=" << radius << std::endl;//Step3.使用Kdtree进行检查if ( kdtree.radiusSearch (searchPoint, radius, pointIdxRadiusSearch, pointRadiusSquaredDistance) > 0 ) { for (std::size_t i = 0; i < pointIdxRadiusSearch.size (); ++i) std::cout << " " << (*cloud)[ pointIdxRadiusSearch[i] ].x << " " << (*cloud)[ pointIdxRadiusSearch[i] ].y << " " << (*cloud)[ pointIdxRadiusSearch[i] ].z << " (squared distance: " << pointRadiusSquaredDistance[i] << ")" << std::endl; } return 0;}运行结果如下，可以看到
1. 距离预设点的最近的10个点的坐标，以及相距预设点的距离。
2. 距离预设点的半径87mm之内的全部点坐标，以及相距预设点的距离：