通常采集的点云数量级能够达到百万甚至更高，如此庞大的点云数据会严重影响处理速度，并且数据中存在冗余信息。因此，在处理前首先需要建立离散点之间的关系，从而实现基于邻域关系的快速查找，即建立点云的空间索引。

一、空间栅格法

空间栅格法是一种基于空间均匀划分的方法，根据给定的参数将点云包围盒均匀划分为多个立方体，并建立点与立方体、立方体与其邻接立方体之间的关系。

（1）空间均匀划分

若点云的包围盒为

，点云总数为 N ，单个立方体中的点数为k ，则包围盒的边长和立方体的边长分别为：

公式（1）

将包围盒边长分别均匀划分为m、n、l 份：

公式（2）

公式（3）

所以，根据上式，遍历点云可以得到每个离散点的索引号、点与所在立方体、立方体与包含点的对应关系。

对于索引坐标为(i , j , k )的立方体，其邻接立方体的索引坐标为(i ±1, j± 1, k±1)。由于立方体在包围盒中的位置有 4 种情况（如图 1）：A 位于包围盒的顶点处，其邻接立方体有 7 个；B 位于包围盒的棱非顶点处，其邻接立方体有 11 个；C 位于包围盒的面非顶点非棱处，其邻接立方体有 17 个；D 位于包围盒内部，其邻接立方体有 26 个。因此，需要根据索引坐标 的情况获取其邻接立方体，从而得到包含的点云。

至此，实现了点云与立方体索引坐标（或索引号）的双向索引。

图1

（2）近邻搜索

这里讨论的是三种索引方法实现 K 近邻搜索和半径内搜索的效率。其中，KNN 搜索是指获取与给定点距离最近的k 个点； RNN 搜索是指获取以给定点为球心，半径为r 的球包含的点。空间栅格法实现近邻搜索的过程为：对于给定的任意点，首先利用上述公式（3）计算其所在立方体索引号，得到对应的范围（立方体及邻接立方体包含的点），然后在此基础上实现上述两种近邻搜索。

（3）优缺点

空间栅格法原理简单、直接访问，适用于空间分布均匀的点云。若是基于曲面的点云，由于该方法均匀分割的特性，可能会对空白区域不断划分，出现内存浪费的现象。

注意：近邻搜索（K 近邻搜索（k-Nearest Neighbor，KNN）和半径内搜索（radius-earest Neighbor，RNN））

参考：李晶晶《城市点云真三维网格构建方法研究》