Open3d 学习计划—10（KDTree）
Open3D是一个开源库，支持快速开发和处理3D数据。Open3D在c++和Python中公开了一组精心选择的数据结构和算法。后端是高度优化的，并且是为并行化而设置的。
本系列学习计划有Blue同学作为发起人，主要以Open3D官方网站的教程为主进行翻译与实践的学习计划。点云PCL公众号作为免费的3D视觉，点云交流社区，期待有使用Open3D或者感兴趣的小伙伴能够加入我们的翻译计划，贡献免费交流社区，为使用Open3D提供中文的使用教程。
KDTree
Open3d使用FLANN构建KDTree以便进行快速最近邻检索。
从点云中建立KDTree
下面的代码读取一个点云并且构建一个KDTree。这是下面最邻近查询的需处理步骤。
print("Testing kdtree in open3d ...")print("Load a point cloud and paint it gray.")pcd = o3d.io.read_point_cloud("../../TestData/Feature/cloud_bin_0.pcd")pcd.paint_uniform_color([0.5, 0.5, 0.5])pcd_tree = o3d.geometry.KDTreeFlann(pcd)Testing kdtree in open3d …
Load a point cloud and paint it gray.
寻找邻域点
我们选择了1500个点作为锚点(anchor point)，并将其涂为红色。
print("Paint the 1500th point red.")pcd.colors[1500] = [1, 0, 0]使用 search_radius_vector_3d
类似的，我们能够使用 search_radius_vector_3d 去查询所有的和锚点距离小于给定半径的点，将其涂成绿色。
print("Find its neighbors with distance less than 0.2, paint green.")[k, idx, _] = pcd_tree.search_radius_vector_3d(pcd.points[1500], 0.2)np.asarray(pcd.colors)[idx[1:], :] = [0, 1, 0]Find its neighbors with distance less than 0.2, paint green.
print("Visualize the point cloud.")o3d.visualization.draw_geometries([pcd], zoom=0.5599, front=[-0.4958, 0.8229, 0.2773], lookat=[2.1126, 1.0163, -1.8543], up=[0.1007, -0.2626, 0.9596])Visualize the point cloud.
除了KNN搜索(search_knn_vector_3d)和RNN搜索(search_radius_vector_3d)以外,Open3d还提供了混合搜索函数(search_hybrid_vector_3d)。它最多返回K个和锚点距离小于给定半径的最邻近点。这个函数结合了KNN和RNN的搜索条件，在某些文献中也被称作RKNN搜索。在许多情况下它有着性能优势,并且在Open3d的函数中大量的使用。
资源
三维点云论文及相关应用分享
【点云论文速读】基于激光雷达的里程计及3D点云地图中的定位方法
3D-MiniNet: 从点云中学习2D表示以实现快速有效的3D LIDAR语义分割（2020）
PCL中outofcore模块---基于核外八叉树的大规模点云的显示
更多文章可查看：点云学习历史文章大汇总
SLAM及AR相关分享