KDTree（k 近邻搜索树）

Open3D 使用 FLANN 来构建 KDTree，从而实现最近邻（nearest neighbor）的快速检索。

从点云构建 KDTree

下面的代码读取一个点云并构建 KDTree。这是后续最近邻查询的预处理步骤。

print("Testing kdtree in Open3D...")
print("Load a point cloud and paint it gray.")

sample_pcd_data = o3d.data.PCDPointCloud()
pcd = o3d.io.read_point_cloud(sample_pcd_data.path)
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.

查找邻近点

我们选取第 1501 个点（数组下标从 0 开始）作为锚点，并将其涂成红色。

print("Paint the 1501st point red.")
pcd.colors[1500] = [1, 0, 0]

输出：

Paint the 1501st point red.

使用 search_knn_vector_3d

函数 search_knn_vector_3d 返回锚点的 k 个最近邻的索引列表。我们把这些邻近点涂成蓝色。注意，这里将 pcd.colors 转换为 numpy 数组，以便批量访问点颜色，并将蓝色 [0, 0, 1] 广播到所有被选中的点上。由于第一个索引就是锚点本身，我们将其跳过。

print("Find its 200 nearest neighbors, and paint them blue.")
[k, idx, _] = pcd_tree.search_knn_vector_3d(pcd.points[1500], 200)
np.asarray(pcd.colors)[idx[1:], :] = [0, 0, 1]

输出：

Find its 200 nearest neighbors, and paint them blue.

使用 search_radius_vector_3d

类似地，我们可以使用 search_radius_vector_3d 查询所有到锚点距离小于给定半径的点。我们把这些点涂成绿色。

print("Find its neighbors with distance less than 0.2, and paint them 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, and paint them 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.