kd树可能是我们最熟悉的空间索引。kd树的全称是k-dimensional tree,顾名思义，是一种将多维数据组织起来的数据结构。不仅服务于计算几何领域，而且在统计分析、机器学习领域都是非常活跃的。本文将主要围绕kd树的结构、构建、半径搜索（范围搜索）、最近邻搜索(KNN)等主要的算法进行展开，同时也会涉及到近似最近邻与最近邻算法的区别，spliting 策略等有趣的细节。并且，我还会介绍部分FLANN库(被PCL使用)对上述算法的实现方式。在文章末尾，提供了c++实现代码。 Continue reading →