KNN是寻找临近最近的K个点

radiusNN是半径为r的圆内的点

pcl提供上述最邻近搜索算法库，但是开源的执行速度慢。自己写的都比库里快。

为什么点云处理起来运算慢：

1.点云是无规则的，存在空间任何位置

2.点云是三维的，数据量导致指数上升，可以使用三维网格转换为三维图像形式，但是产生一些问题：

    1.如果网格很多，我的分辨率提升了，所需内存就会很大。如果网格很少，内存需求降低，但是分辨率下降，1

    2.网格本身就有问题，网格大部分是空白区，原理上不是很高效。

3.点云数量庞大，例如Velodyne64E，每秒产生22w点云，以20HZ频率处理点云，所需50ms处理11w个点。如何对这11w个点暴力寻找最近的点，所需次数为11w*11w*.0.5=6*10-9@20HZ次运算。一秒处理120亿次。对于i7处理器单核主频4.7Ghz的47亿次/每秒，就略显吃力了。

所以搜索算法就应运而生。主要用到的最邻近搜索算法

二叉树binary search tree BST:：解决1D问题， 

二叉树实现方式递归与循环比较：

递归需要不断地压栈出栈，需要树层的存储量，优点代码简洁。C++代码会自动把递归程序转换为循环。递归使用的CPU，GPU一般只能提供十几层的栈，所以递归建议使用在CPU中。

循环：可以用在ＧＰＵ上，二叉树、八叉树一些算法想要使用GPU，最好写成循环方式。 缺点：写起来复杂

中序遍历（左中右）可实现排序，前序遍历（中左右）实现copytree，后续遍历（左右中）实现删除一个节点

kdtree（K-dimansional tree）：2D统计，就是把每一个维度当成一个二叉树，不同的是叶子节点可以包含多个point。使用超平面不断地将点云数量平分轮流切开，直到得到的区域点小于定义的leaf。

octree：2D/3D统计，面向于三维