深入理解ikd-Tree从阅读代码开始(一)

0. 简介

增量KD树,我们知道这类算法可以更加高效并且有意义地完成数据结构的动态空间划分. ikd-Tree可以主动监视树结构并重新平衡树结构，从而在后期实现高效的最近点搜索，ikd-Tree经过了精心设计，支持多线程并行计算，以最大限度地提高整体效率.mars实验室已经将这个代码公开了,而且有很多人对代码进行了总结与阐述.这里我们主要来看一下KennyWGH ikd-Tree,并对作者的一些疑问进行解释.

1. 头文件介绍

// 定义EPSS为1e-6，表示误差范围 
#define EPSS 1e-6

// 定义最小不平衡树大小为10，即当某个子树的节点数小于10时，需要进行重平衡 
#define Minimal_Unbalanced_Tree_Size 10

// 定义需要重建子树的点数达到1500时，使用额外线程处理 
#define Multi_Thread_Rebuild_Point_Num 1500

// 定义DOWNSAMPLE_SWITCH为true，表示开启下采样功能 
#define DOWNSAMPLE_SWITCH true

// 定义强制重建百分比为0.2，即当某个子树中删除的节点数占总节点数的20%以上时，需要进行重建 
#define ForceRebuildPercentage 0.2

// 定义支持的最大队列长度为1000000 
#define Q_LEN 1000000

2. 结构体介绍

2.1 全局结构体

// 构造函数，用来初始化点的坐标
struct ikdTree_PointType
{
    float x,y,z;
    // 传递的是float类型，而不是类类型，因此不需要使用const&做形参。
    ikdTree_PointType (float px = 0.0f, float py = 0.0f, float pz = 0.0f){
        x = px;
        y = py;
        z = pz;
    }
};

// 定义box（一个box由两个边界点定义）。 
struct BoxPointType{ 
  float vertex_min[3]; // 定义最小顶点的坐标 
  float vertex_max[3]; // 定义最大顶点的坐标 
};

// 枚举ikdtree中的所有操作。
enum operation_set {
    ADD_POINT, 
    DELETE_POINT, 
    DELETE_BOX, 
    ADD_BOX, 
    DOWNSAMPLE_DELETE, 
    PUSH_DOWN
};

// 定义一个枚举类型，用于记录删除点的存储方式
enum delete_point_storage_set {
    NOT_RECORD, //没有记录
    DELETE_POINTS_REC, //删除点记录
    MULTI_THREAD_REC//多线程记录
};

// 定义一个手动实现的队列类
template <typename T>
class MANUAL_Q{
    private:
        int head = 0,tail = 0, counter = 0;// 定义队列的头、尾、大小
        T q[Q_LEN];// 定义一个数组作为队列
        bool is_empty;// 定义一个标志位，表示队列是否为空
    public:
        void pop();// 弹出队列的头元素
        T front();// 返回队列的头元素
        T back();// 返回队列的尾元素
        void clear(); // 清空队列
        void push(T op);// 在队列尾部插入元素
        bool empty();// 判断队列是否为空
        int size();// 返回队列大小
};

2.2 KD-TREE结构体

ikd树中树节点的属性如数据结构1所示

第2-4行是标准k-d树的常见属性，属性leftson和rightson分别是指向其左和右子节点的指针，点信息（例如点坐标、强度）存储在点中，由于一个点对应k-d树上的一个节点，我们将互换使用点和节点，分割轴记录在轴中。第5-7行是为增量更新设计的新属性。

using PointVector = vector<PointType, Eigen::aligned_allocator<PointType>>;// 定义一个使用Eigen内存分配器的点向量类型
using Ptr = shared_ptr<KD_TREE<PointType>>;// 定义一个智能指针类型，指向KD_TREE类型的对象,就是本class

// 定义KD树节点结构体
struct KD_TREE_NODE{
    PointType point;                            // 数据点
    uint8_t division_axis;                      // 分割轴
    int TreeSize = 1;                           // 总节点数
    int invalid_point_num = 0;                  // label为删除的点的数量
    int down_del_num = 0;                       // 下采样删除的点的数量
    bool point_deleted = false;                 // 标记节点是否被删除
    bool tree_deleted = false;                  // 整个tree标记为删除
    bool point_downsample_deleted = false;      // 标记节点是否被下采样删除
    bool tree_downsample_deleted = false;       // 标记整个树是否被下采样删除 
    bool need_push_down_to_left = false;        // 标记是否需要将操作向左子树下传
    bool need_push_down_to_right = false;       // 标记是否需要将操作向右子树下传 
    bool working_flag = false;                  // 标记节点是否正在被访问
    float radius_sq;                            // 节点范围的平方半径
    pthread_mutex_t push_down_mutex_lock;        // 用于多线程操作的互斥锁
    float node_range_x[2], node_range_y[2], node_range_z[2];    // tree对应的包络Box
    KD_TREE_NODE *left_son_ptr = nullptr;       // 左子树指针对应KD_TREE
    KD_TREE_NODE *right_son_ptr = nullptr;      // 右子树指针对应KD_TREE
    KD_TREE_NODE *father_ptr = nullptr;         // 父树
    // For paper data record
    float alpha_del;
    float alpha_bal;
};

// 定义操作日志结构体 
struct Operation_Logger_Type{
    PointType point;// 操作点 
    BoxPointType boxpoint;// 操作box 
    bool tree_deleted, tree_downsample_deleted;// 标记树是否被删除或下采样删除
    operation_set op;// 操作类型
};

…详情请参照古月居