目录

1 KDTree

knn_search

radius_search

hybrid search

2 Octree

1 从点云中创建octree

2 从voxel中创建octree

3 octree的遍历（Traversal）

4、查找点云对应的叶子节点

3、KDTree的原理介绍可以参考如下文章：

1 KDTree

        open3d使用了FLANN来创建KDTree并实现对点云最近邻的快速检索

在使用KDTree时，需要先对点云创建KDTree然后根据选中的空间点实现对knn_search或者radius_search。

1 创建KDTree（该函数包含多个重载版本，输入支持

           numpy.ndarray[numpy.float64[m, n]]        numpy array数据类型

          open3d.cpu.pybind.geometry.Geometry   o3d中的Geometry类型（包括点云、mesh等）

          open3d::pipelines::registration::Feature    o3d中的特征向量类型 ）

2 选定搜索点

3 最近邻（knn）搜索或半径搜索

代码示例

import open3d as o3d
import numpy as np"""
radius_search返回选中点半径小于radius的n个点
"""def radius_search():print("Loading pointcloud ...")sample_pcd_data = o3d.data.PCDPointCloud()pcd = o3d.io.read_point_cloud(sample_pcd_data.path)pcd_tree = o3d.geometry.KDTreeFlann(pcd)print("Find the neighbors of 50000th point with distance less than 0.3, and painting them green ...")[k, idx, _] = pcd_tree.search_radius_vector_3d(query=pcd.points[50000], radius=0.3)np.asarray(pcd.colors)[idx[1:], :] = [0, 1, 0]print("Displaying the final point cloud ...\n")o3d.visualization.draw_geometries([pcd])"""
最近邻搜索返回选中点距离最近的n个点
"""def knn_search():print("Loading pointcloud ...")sample_pcd = o3d.data.PCDPointCloud()pcd = o3d.io.read_point_cloud(sample_pcd.path)# 创建点云的KDTreepcd_tree = o3d.geometry.KDTreeFlann(pcd)print("Find the 2000 nearest neighbors of 50000th point, and painting them red ...")"""搜索点设置为点云中的第500000个点，并搜索距离该点最近的2000个点返回值  1：k为搜索得到最近点的个数2：k个最近邻点在原始点云的中索引3：未知，但不是索引点到搜索点的距离！！"""[k, idx, _] = pcd_tree.search_knn_vector_3d(query=pcd.points[50000], knn=2000)# 将搜索得到的最近的k个点的颜色设置为红色，idx切片从1开始，是因为略过了搜索点本身np.asarray(pcd.colors)[idx[1:], :] = [1, 0, 0]print("Displaying the final point cloud ...\n")o3d.visualization.draw_geometries([pcd])if __name__ == "__main__":knn_search()radius_search()

knn_search

radius_search

hybrid search

         在open3d中除了KNN search和RNN search（radius search）,还提供了一个混合的搜索模式（hybrid search）；该函数返回最多返回k个距离锚搜索点小于给定半径的最近邻点，属于KNN和RNN搜索的融合搜索方式。

import numpy as np
import open3d as o3ddef hybrid_search():print("Loading pointcloud ...")sample_pcd_data = o3d.data.PCDPointCloud()pcd = o3d.io.read_point_cloud(sample_pcd_data.path)pcd_tree = o3d.geometry.KDTreeFlann(pcd)"""在选定的半径范围内，找出最近的2000个点"""[k, idx, _] = pcd_tree.search_hybrid_vector_3d(query=pcd.points[50000],radius=0.3,max_nn=2000)np.asarray(pcd.colors)[idx[1:], :] = [0, 0, 1]print("Displaying the final point cloud ...\n")o3d.visualization.draw_geometries([pcd])if __name__ == "__main__":hybrid_search()

注：上述提到的所有搜索方式都包含更高维度的向量最近邻搜索，对应search_knn_vector_xd、search_radius_vector_xd、search_hybrid_vector_xd。

2 Octree

        octree是一个树形结构，其每个节点都有8个孩子（为什么是8个孩子呢？可以想象一个空间的每两个面都被切开，那么这个空间会被划分成大小相同的8个小方块；且树的结构说明这个操作是可以在每个小方块迭代执行的；直到你设定的最小方块大小以达到你所需的建模最高精度）；octree常用于点云的空间划分操作，octree中一个非空的叶子节点意味着该空间中包含一个或更多的点云信息。octree对于3d空间的描述非常有用且可以被用于点云邻居点的搜索。Open3D中自建了octree的几何对象，可以创建、搜索、遍历点云的octree；用户只需要定义该octree的最大深度即可。

octree例图：        

这里讲讲为什么octree相比于点云数据更加节省存储空间；在之前的点云出来中，介绍了点云的体素化，使用一个指定大小的voxel来一个空间中的所有点，该操作相当于对点云进行了下采样，使得空间中的点变少了；此处先举一个octree例子然后再进行说明，我们假定每个叶子节点的大小为1cm^3，且该octree的深度为10的话，那么该octree能建模的体积为8^10cm^3 = 1073m^3；如果假定楼层高度为4m的话，建模的面积为268.25平方米的房子； 在octree中每个节点存储的是该空间是否被占据的信息，并没有存储点的坐标，如果某个中间节点已经被占据（或为空），那么他的所有子节点都是被占据（或为空）；这样就没有必要继续按此节点展开；在实际情况中由于物体是在一个空间且连在一起；空白区域也是如此；因此octree在很多时候没有必要展开到根节点就可以达到处理的目的；所以octree可以以此方式大幅节省存储空间（使用octree生成的octomap的文件大小仅为点云文件大小的1%不到）

1 从点云中创建octree

import open3d as o3d
import numpy as npimport copyimport open3d as o3dq
import numpy as npif __name__ == "__main__":N = 3000armadillo_data = o3d.data.ArmadilloMesh()pcd = o3d.io.read_triangle_mesh(armadillo_data.path).sample_points_poisson_disk(N)# Fit to unit cube.# 点云缩放到单位正方体内，center的设置保证了对象缩放时，对象的中心位置不会因为缩放而导致移动pcd.scale(1 / np.max(pcd.get_max_bound() - pcd.get_min_bound()),center=pcd.get_center())pcd.colors = o3d.utility.Vector3dVector(np.random.uniform(0, 1, size=(N, 3)))coor_mesh = o3d.geometry.TriangleMesh.create_coordinate_frame(size=1)print('Displaying input pointcloud ...')# o3d.visualization.draw_geometries([pcd])# max_depth设置了octree的深度，每个octree都是个八叉树octree = o3d.geometry.Octree(max_depth=4)pcd_for_octree = copy.deepcopy(pcd)pcd_for_octree.translate([1, 0, 0])"""param: size_expand:- A small expansion size such that the octree is slightly bigger than the original point cloud bounds to accommodate all points."""octree.convert_from_point_cloud(pcd_for_octree, size_expand=0.01)print('Displaying octree ..')o3d.visualization.draw_geometries([pcd, octree])

下图中左边为点云信息，右边为octree的划分结果；可以看到在点云稀疏的地方octree的节点不会继续向下分割，有点云的地方则会继续向下分割得到更详细的结果。

2 从voxel中创建octree

import open3d as o3d
import numpy as npif __name__ == "__main__":N = 3000armadillo_data = o3d.data.ArmadilloMesh()pcd = o3d.io.read_triangle_mesh(armadillo_data.path).sample_points_poisson_disk(N)"""Fit to unit cube.点云归一化到体积为1的立方体内center的设置保证了对象缩放时，对象的中心位置不会因为缩放而导致移动"""pcd.scale(1 / np.max(pcd.get_max_bound() - pcd.get_min_bound()),center=pcd.get_center())pcd.colors = o3d.utility.Vector3dVector(np.random.uniform(0, 1,size=(N, 3)))print('Displaying input voxel grid ...')voxel_grid = o3d.geometry.VoxelGrid.create_from_point_cloud(pcd,voxel_size=0.05)o3d.visualization.draw_geometries([voxel_grid])octree = o3d.geometry.Octree(max_depth=4)octree.create_from_voxel_grid(voxel_grid)print('Displaying octree ..')o3d.visualization.draw_geometries([octree])

3 octree的遍历（Traversal）

        在open3d中octree可以使用traverse方法来对octree进行遍历操作，该操作基于DFS（深度优先搜索）对八叉树进行搜索。traverse方法提供了回调函数，每次对一个节点（中间节点或叶子节点）进行访问以对该点进行其他操作。

        下面示例中展示了使用traverse和early stoping对超过一定数量的叶子节点进行处理；其中early stopping可以高效的选取达到一定数量的节点。

4、查找点云对应的叶子节点

        对octree遍历的结果如果（根据程序的设定，节点包含的子节点的点云总数量少于50则不会展开子节点继续遍历）：

"""
Displaying input octree ...
Traversing octree ...
0: Internal node at depth 0 has 8 children and 3000 points ([-2.72495985 31.2744969   1.92589911])0: Internal node at depth 1 has 4 children and 94 points ([-2.72495985 31.2744969   1.92589911])4: Internal node at depth 2 has 2 children and 19 points ([-2.72495985 31.2744969   2.17839911])5: Internal node at depth 2 has 2 children and 9 points ([-2.47245985 31.2744969   2.17839911])6: Internal node at depth 2 has 1 children and 6 points ([-2.72495985 31.5269969   2.17839911])7: Internal node at depth 2 has 3 children and 60 points ([-2.47245985 31.5269969   2.17839911])4: Internal node at depth 3 has 4 children and 24 points ([-2.47245985 31.5269969   2.30464911])6: Internal node at depth 3 has 2 children and 14 points ([-2.47245985 31.6532469   2.30464911])7: Internal node at depth 3 has 4 children and 22 points ([-2.34620985 31.6532469   2.30464911])1: Internal node at depth 1 has 2 children and 68 points ([-2.21995985 31.2744969   1.92589911])4: Internal node at depth 2 has 2 children and 14 points ([-2.21995985 31.2744969   2.17839911])6: Internal node at depth 2 has 4 children and 54 points ([-2.21995985 31.5269969   2.17839911])4: Internal node at depth 3 has 1 children and 4 points ([-2.21995985 31.5269969   2.30464911])5: Internal node at depth 3 has 4 children and 19 points ([-2.09370985 31.5269969   2.30464911])6: Internal node at depth 3 has 4 children and 24 points ([-2.21995985 31.6532469   2.30464911])7: Internal node at depth 3 has 1 children and 7 points ([-2.09370985 31.6532469   2.30464911])2: Internal node at depth 1 has 8 children and 617 points ([-2.72495985 31.7794969   1.92589911])0: Internal node at depth 2 has 2 children and 11 points ([-2.72495985 31.7794969   1.92589911])1: Internal node at depth 2 has 1 children and 10 points ([-2.47245985 31.7794969   1.92589911])2: Internal node at depth 2 has 4 children and 66 points ([-2.72495985 32.0319969   1.92589911])1: Internal node at depth 3 has 1 children and 1 points ([-2.59870985 32.0319969   1.92589911])4: Internal node at depth 3 has 4 children and 25 points ([-2.72495985 32.0319969   2.05214911])5: Internal node at depth 3 has 4 children and 31 points ([-2.59870985 32.0319969   2.05214911])7: Internal node at depth 3 has 1 children and 9 points ([-2.59870985 32.1582469   2.05214911])3: Internal node at depth 2 has 1 children and 6 points ([-2.47245985 32.0319969   1.92589911])4: Internal node at depth 2 has 4 children and 90 points ([-2.72495985 31.7794969   2.17839911])2: Internal node at depth 3 has 2 children and 14 points ([-2.72495985 31.9057469   2.17839911])3: Internal node at depth 3 has 5 children and 35 points ([-2.59870985 31.9057469   2.17839911])6: Internal node at depth 3 has 1 children and 4 points ([-2.72495985 31.9057469   2.30464911])7: Internal node at depth 3 has 8 children and 37 points ([-2.59870985 31.9057469   2.30464911])5: Internal node at depth 2 has 5 children and 140 points ([-2.47245985 31.7794969   2.17839911])3: Internal node at depth 3 has 2 children and 18 points ([-2.34620985 31.9057469   2.17839911])4: Internal node at depth 3 has 1 children and 6 points ([-2.47245985 31.7794969   2.30464911])5: Internal node at depth 3 has 7 children and 38 points ([-2.34620985 31.7794969   2.30464911])6: Internal node at depth 3 has 7 children and 45 points ([-2.47245985 31.9057469   2.30464911])7: Internal node at depth 3 has 4 children and 33 points ([-2.34620985 31.9057469   2.30464911])6: Internal node at depth 2 has 4 children and 115 points ([-2.72495985 32.0319969   2.17839911])0: Internal node at depth 3 has 4 children and 28 points ([-2.72495985 32.0319969   2.17839911])1: Internal node at depth 3 has 7 children and 42 points ([-2.59870985 32.0319969   2.17839911])4: Internal node at depth 3 has 2 children and 8 points ([-2.72495985 32.0319969   2.30464911])5: Internal node at depth 3 has 6 children and 37 points ([-2.59870985 32.0319969   2.30464911])7: Internal node at depth 2 has 6 children and 179 points ([-2.47245985 32.0319969   2.17839911])1: Internal node at depth 3 has 7 children and 45 points ([-2.34620985 32.0319969   2.17839911])2: Internal node at depth 3 has 3 children and 7 points ([-2.47245985 32.1582469   2.17839911])3: Internal node at depth 3 has 7 children and 44 points ([-2.34620985 32.1582469   2.17839911])4: Internal node at depth 3 has 6 children and 31 points ([-2.47245985 32.0319969   2.30464911])5: Internal node at depth 3 has 3 children and 21 points ([-2.34620985 32.0319969   2.30464911])7: Internal node at depth 3 has 5 children and 31 points ([-2.34620985 32.1582469   2.30464911])3: Internal node at depth 1 has 7 children and 548 points ([-2.21995985 31.7794969   1.92589911])0: Internal node at depth 2 has 1 children and 6 points ([-2.21995985 31.7794969   1.92589911])2: Internal node at depth 2 has 1 children and 7 points ([-2.21995985 32.0319969   1.92589911])3: Internal node at depth 2 has 3 children and 17 points ([-1.96745985 32.0319969   1.92589911])4: Internal node at depth 2 has 5 children and 123 points ([-2.21995985 31.7794969   2.17839911])2: Internal node at depth 3 has 2 children and 14 points ([-2.21995985 31.9057469   2.17839911])4: Internal node at depth 3 has 7 children and 34 points ([-2.21995985 31.7794969   2.30464911])5: Internal node at depth 3 has 1 children and 1 points ([-2.09370985 31.7794969   2.30464911])6: Internal node at depth 3 has 5 children and 37 points ([-2.21995985 31.9057469   2.30464911])7: Internal node at depth 3 has 7 children and 37 points ([-2.09370985 31.9057469   2.30464911])5: Internal node at depth 2 has 4 children and 67 points ([-1.96745985 31.7794969   2.17839911])2: Internal node at depth 3 has 2 children and 21 points ([-1.96745985 31.9057469   2.17839911])3: Internal node at depth 3 has 1 children and 2 points ([-1.84120985 31.9057469   2.17839911])6: Internal node at depth 3 has 7 children and 40 points ([-1.96745985 31.9057469   2.30464911])7: Internal node at depth 3 has 2 children and 4 points ([-1.84120985 31.9057469   2.30464911])6: Internal node at depth 2 has 6 children and 169 points ([-2.21995985 32.0319969   2.17839911])0: Internal node at depth 3 has 6 children and 35 points ([-2.21995985 32.0319969   2.17839911])2: Internal node at depth 3 has 6 children and 43 points ([-2.21995985 32.1582469   2.17839911])3: Internal node at depth 3 has 2 children and 5 points ([-2.09370985 32.1582469   2.17839911])4: Internal node at depth 3 has 4 children and 37 points ([-2.21995985 32.0319969   2.30464911])5: Internal node at depth 3 has 4 children and 18 points ([-2.09370985 32.0319969   2.30464911])6: Internal node at depth 3 has 5 children and 31 points ([-2.21995985 32.1582469   2.30464911])7: Internal node at depth 2 has 6 children and 159 points ([-1.96745985 32.0319969   2.17839911])0: Internal node at depth 3 has 6 children and 35 points ([-1.96745985 32.0319969   2.17839911])1: Internal node at depth 3 has 4 children and 24 points ([-1.84120985 32.0319969   2.17839911])2: Internal node at depth 3 has 3 children and 30 points ([-1.96745985 32.1582469   2.17839911])3: Internal node at depth 3 has 2 children and 6 points ([-1.84120985 32.1582469   2.17839911])4: Internal node at depth 3 has 7 children and 48 points ([-1.96745985 32.0319969   2.30464911])5: Internal node at depth 3 has 3 children and 16 points ([-1.84120985 32.0319969   2.30464911])4: Internal node at depth 1 has 5 children and 515 points ([-2.72495985 31.2744969   2.43089911])0: Internal node at depth 2 has 3 children and 90 points ([-2.72495985 31.2744969   2.43089911])1: Internal node at depth 3 has 6 children and 59 points ([-2.59870985 31.2744969   2.43089911])0: Leaf node at depth 4 has 14 points with origin [-2.59870985 31.2744969   2.43089911]1: Leaf node at depth 4 has 14 points with origin [-2.53558485 31.2744969   2.43089911]3: Leaf node at depth 4 has 5 points with origin [-2.53558485 31.3376219   2.43089911]4: Leaf node at depth 4 has 4 points with origin [-2.59870985 31.2744969   2.49402411]5: Leaf node at depth 4 has 13 points with origin [-2.53558485 31.2744969   2.49402411]7: Leaf node at depth 4 has 9 points with origin [-2.53558485 31.3376219   2.49402411]3: Internal node at depth 3 has 4 children and 27 points ([-2.59870985 31.4007469   2.43089911])7: Internal node at depth 3 has 2 children and 4 points ([-2.59870985 31.4007469   2.55714911])1: Internal node at depth 2 has 4 children and 146 points ([-2.47245985 31.2744969   2.43089911])0: Internal node at depth 3 has 7 children and 45 points ([-2.47245985 31.2744969   2.43089911])2: Internal node at depth 3 has 6 children and 51 points ([-2.47245985 31.4007469   2.43089911])0: Leaf node at depth 4 has 9 points with origin [-2.47245985 31.4007469   2.43089911]1: Leaf node at depth 4 has 11 points with origin [-2.40933485 31.4007469   2.43089911]2: Leaf node at depth 4 has 3 points with origin [-2.47245985 31.4638719   2.43089911]3: Leaf node at depth 4 has 8 points with origin [-2.40933485 31.4638719   2.43089911]5: Leaf node at depth 4 has 9 points with origin [-2.40933485 31.4007469   2.49402411]7: Leaf node at depth 4 has 11 points with origin [-2.40933485 31.4638719   2.49402411]4: Internal node at depth 3 has 4 children and 31 points ([-2.47245985 31.2744969   2.55714911])6: Internal node at depth 3 has 4 children and 19 points ([-2.47245985 31.4007469   2.55714911])2: Internal node at depth 2 has 2 children and 29 points ([-2.72495985 31.5269969   2.43089911])3: Internal node at depth 2 has 8 children and 216 points ([-2.47245985 31.5269969   2.43089911])0: Internal node at depth 3 has 7 children and 38 points ([-2.47245985 31.5269969   2.43089911])1: Internal node at depth 3 has 4 children and 18 points ([-2.34620985 31.5269969   2.43089911])2: Internal node at depth 3 has 7 children and 39 points ([-2.47245985 31.6532469   2.43089911])3: Internal node at depth 3 has 5 children and 24 points ([-2.34620985 31.6532469   2.43089911])4: Internal node at depth 3 has 3 children and 12 points ([-2.47245985 31.5269969   2.55714911])5: Internal node at depth 3 has 3 children and 15 points ([-2.34620985 31.5269969   2.55714911])6: Internal node at depth 3 has 4 children and 26 points ([-2.47245985 31.6532469   2.55714911])7: Internal node at depth 3 has 7 children and 44 points ([-2.34620985 31.6532469   2.55714911])7: Internal node at depth 2 has 1 children and 34 points ([-2.47245985 31.5269969   2.68339911])5: Internal node at depth 1 has 4 children and 476 points ([-2.21995985 31.2744969   2.43089911])0: Internal node at depth 2 has 8 children and 254 points ([-2.21995985 31.2744969   2.43089911])0: Internal node at depth 3 has 3 children and 21 points ([-2.21995985 31.2744969   2.43089911])1: Internal node at depth 3 has 7 children and 64 points ([-2.09370985 31.2744969   2.43089911])0: Leaf node at depth 4 has 14 points with origin [-2.09370985 31.2744969   2.43089911]1: Leaf node at depth 4 has 17 points with origin [-2.03058485 31.2744969   2.43089911]2: Leaf node at depth 4 has 1 points with origin [-2.09370985 31.3376219   2.43089911]4: Leaf node at depth 4 has 6 points with origin [-2.09370985 31.2744969   2.49402411]5: Leaf node at depth 4 has 15 points with origin [-2.03058485 31.2744969   2.49402411]6: Leaf node at depth 4 has 10 points with origin [-2.09370985 31.3376219   2.49402411]7: Leaf node at depth 4 has 1 points with origin [-2.03058485 31.3376219   2.49402411]2: Internal node at depth 3 has 4 children and 25 points ([-2.21995985 31.4007469   2.43089911])3: Internal node at depth 3 has 8 children and 44 points ([-2.09370985 31.4007469   2.43089911])4: Internal node at depth 3 has 3 children and 25 points ([-2.21995985 31.2744969   2.55714911])5: Internal node at depth 3 has 6 children and 32 points ([-2.09370985 31.2744969   2.55714911])6: Internal node at depth 3 has 2 children and 18 points ([-2.21995985 31.4007469   2.55714911])7: Internal node at depth 3 has 4 children and 25 points ([-2.09370985 31.4007469   2.55714911])1: Internal node at depth 2 has 1 children and 3 points ([-1.96745985 31.2744969   2.43089911])2: Internal node at depth 2 has 8 children and 216 points ([-2.21995985 31.5269969   2.43089911])0: Internal node at depth 3 has 6 children and 43 points ([-2.21995985 31.5269969   2.43089911])1: Internal node at depth 3 has 6 children and 41 points ([-2.09370985 31.5269969   2.43089911])2: Internal node at depth 3 has 5 children and 22 points ([-2.21995985 31.6532469   2.43089911])3: Internal node at depth 3 has 7 children and 42 points ([-2.09370985 31.6532469   2.43089911])4: Internal node at depth 3 has 3 children and 10 points ([-2.21995985 31.5269969   2.55714911])5: Internal node at depth 3 has 2 children and 9 points ([-2.09370985 31.5269969   2.55714911])6: Internal node at depth 3 has 6 children and 39 points ([-2.21995985 31.6532469   2.55714911])7: Internal node at depth 3 has 2 children and 10 points ([-2.09370985 31.6532469   2.55714911])6: Internal node at depth 2 has 1 children and 3 points ([-2.21995985 31.5269969   2.68339911])6: Internal node at depth 1 has 6 children and 350 points ([-2.72495985 31.7794969   2.43089911])0: Internal node at depth 2 has 1 children and 11 points ([-2.72495985 31.7794969   2.43089911])1: Internal node at depth 2 has 7 children and 175 points ([-2.47245985 31.7794969   2.43089911])0: Internal node at depth 3 has 4 children and 30 points ([-2.47245985 31.7794969   2.43089911])1: Internal node at depth 3 has 2 children and 5 points ([-2.34620985 31.7794969   2.43089911])2: Internal node at depth 3 has 6 children and 37 points ([-2.47245985 31.9057469   2.43089911])4: Internal node at depth 3 has 2 children and 8 points ([-2.47245985 31.7794969   2.55714911])5: Internal node at depth 3 has 6 children and 38 points ([-2.34620985 31.7794969   2.55714911])6: Internal node at depth 3 has 5 children and 26 points ([-2.47245985 31.9057469   2.55714911])7: Internal node at depth 3 has 4 children and 31 points ([-2.34620985 31.9057469   2.55714911])2: Internal node at depth 2 has 1 children and 3 points ([-2.72495985 32.0319969   2.43089911])3: Internal node at depth 2 has 6 children and 156 points ([-2.47245985 32.0319969   2.43089911])0: Internal node at depth 3 has 6 children and 40 points ([-2.47245985 32.0319969   2.43089911])2: Internal node at depth 3 has 2 children and 2 points ([-2.47245985 32.1582469   2.43089911])3: Internal node at depth 3 has 5 children and 38 points ([-2.34620985 32.1582469   2.43089911])4: Internal node at depth 3 has 4 children and 23 points ([-2.47245985 32.0319969   2.55714911])5: Internal node at depth 3 has 5 children and 33 points ([-2.34620985 32.0319969   2.55714911])7: Internal node at depth 3 has 4 children and 20 points ([-2.34620985 32.1582469   2.55714911])5: Internal node at depth 2 has 1 children and 3 points ([-2.47245985 31.7794969   2.68339911])7: Internal node at depth 2 has 1 children and 2 points ([-2.47245985 32.0319969   2.68339911])7: Internal node at depth 1 has 6 children and 332 points ([-2.21995985 31.7794969   2.43089911])0: Internal node at depth 2 has 7 children and 173 points ([-2.21995985 31.7794969   2.43089911])0: Internal node at depth 3 has 4 children and 27 points ([-2.21995985 31.7794969   2.43089911])1: Internal node at depth 3 has 3 children and 10 points ([-2.09370985 31.7794969   2.43089911])3: Internal node at depth 3 has 7 children and 42 points ([-2.09370985 31.9057469   2.43089911])4: Internal node at depth 3 has 7 children and 40 points ([-2.21995985 31.7794969   2.55714911])5: Internal node at depth 3 has 1 children and 3 points ([-2.09370985 31.7794969   2.55714911])6: Internal node at depth 3 has 5 children and 35 points ([-2.21995985 31.9057469   2.55714911])7: Internal node at depth 3 has 3 children and 16 points ([-2.09370985 31.9057469   2.55714911])1: Internal node at depth 2 has 1 children and 13 points ([-1.96745985 31.7794969   2.43089911])2: Internal node at depth 2 has 6 children and 142 points ([-2.21995985 32.0319969   2.43089911])0: Internal node at depth 3 has 2 children and 4 points ([-2.21995985 32.0319969   2.43089911])1: Internal node at depth 3 has 6 children and 41 points ([-2.09370985 32.0319969   2.43089911])2: Internal node at depth 3 has 6 children and 33 points ([-2.21995985 32.1582469   2.43089911])4: Internal node at depth 3 has 6 children and 37 points ([-2.21995985 32.0319969   2.55714911])5: Internal node at depth 3 has 3 children and 12 points ([-2.09370985 32.0319969   2.55714911])6: Internal node at depth 3 has 4 children and 15 points ([-2.21995985 32.1582469   2.55714911])3: Internal node at depth 2 has 1 children and 2 points ([-1.96745985 32.0319969   2.43089911])4: Internal node at depth 2 has 1 children and 1 points ([-2.21995985 31.7794969   2.68339911])6: Internal node at depth 2 has 1 children and 1 points ([-2.21995985 32.0319969   2.68339911])Process finished with exit code 0"""

4、查找点云对应的叶子节点

        使用上面的traversal遍历，通过方法locate_leaf_node，可以快速定位某个点云在octree的哪个叶子节点中。

import open3d as o3d
import numpy as npif __name__ == "__main__":N = 3000armadillo_data = o3d.data.ArmadilloMesh()pcd = o3d.io.read_triangle_mesh(armadillo_data.path).sample_points_poisson_disk(N)# Fit to unit cube.pcd.scale(1 / np.max(pcd.get_max_bound() - pcd.get_min_bound()),center=pcd.get_center())pcd.colors = o3d.utility.Vector3dVector(np.random.uniform(0, 1,size=(N, 3)))octree = o3d.geometry.Octree(max_depth=4)octree.convert_from_point_cloud(pcd, size_expand=0.01)print('Displaying input octree ...')o3d.visualization.draw_geometries([octree])"""Returns leaf OctreeNode and OctreeNodeInfo where the querypoint should reside.返回查询点对应的Tuple[open3d.geometry.OctreeLeafNode, open3d.geometry.OctreeNodeInfo]"""print('Finding leaf node containing the first point of pointcloud ...')print(octree.locate_leaf_node(pcd.points[0]))"""结果：Finding leaf node containing the first point of pointcloud ...(OctreePointColorLeafNode with color [0.152902, 0.134164, 0.525544] containing 8 points., OctreeNodeInfo with origin [-2.42852, 31.9983, 2.75556], size 0.063125, depth 4, child_index 7)"""

3、KDTree的原理介绍可以参考如下文章：

欧式聚类（KD-Tree）详解，保姆级教程 - 知乎参考了 欧式聚类详解（点云数据处理）_JAT0929的博客-CSDN博客_欧式聚类欧式聚类是一种基于欧氏距离度量的聚类算法。基于KD-Tree的近邻查询算法是加速欧式聚类算法的重要预处理方法。（不想看KD-Tree的可以直接跳…https://zhuanlan.zhihu.com/p/402555908