天天看點
傳回

深入了解ikd-Tree從閱讀代碼開始(三)

0. 簡介

增量KD樹,我們知道這類算法可以更加高效并且有意義地完成資料結構的動态空間劃分. ikd-Tree可以主動監視樹結構并重新平衡樹結構，進而在後期實作高效的最近點搜尋，ikd-Tree經過了精心設計，支援多線程并行計算，以最大限度地提高整體效率.mars實驗室已經将這個代碼公開了,而且有很多人對代碼進行了總結與闡述.這裡我們主要來看一下KennyWGH ikd-Tree,并對作者的一些疑問進行解釋.

1. ikd-Tree的插入與删除

增量更新指的是增量操作，随後進行動态重新平衡。增量操作包括向k-D樹插入、删除和重新插入新點，具體而言，插入操作将一個新點（即節點）附加到k-d樹，在删除操作中，我們使用了延遲删除政策，也就是說，不會立即從樹中删除點，而隻會通過将屬性deleted設定為true來标記為“deleted”（已删除）。如果已删除以T為根的子樹上的所有節點，則T的屬性treedeleted設定為true，是以，删除的屬性和樹删除的屬性稱為惰性标簽。如果标記為“已删除”但未删除的點稍後插入到樹中，則稱為“重新插入”，隻需将删除的屬性設定回false即可有效地實作。否則，标記為“已删除”的點将在重建過程中從樹中删除，我們的增量更新支援兩種類型：點式更新和框式更新，逐點更新在樹上插入、删除或重新插入單個點，而逐框更新在與資料坐标軸對齊的給定框中插入、删除或重新插入所有點，框式更新可能需要删除或重新插入以T為根的整個子樹。在這種情況下，遞歸更新T的所有子節點的已删除和已删除的懶惰标簽仍然是低效的。為了解決這個問題，我們使用了進一步的延遲政策來更新子節點的延遲标簽。

1.1 插入節點

增量k-d樹上的逐點更新以遞歸方式實作，類似于k-d樹，對于逐點插入，該算法從根節點遞歸向下搜尋，并将新點在分割軸上的坐标與存儲在樹節點上的點進行比較，直到找到一個葉節點來附加新的樹節點，對于點P的删除或重新插入，該算法會找到存儲點P的樹節點，并修改删除的屬性。ikd-Tree插入新點的流程如下:

  1. 首先将整個空間體素化，并明确新點落入哪個體素（目标體素）；
  2. 然後向ikd-Tree查詢目标體素内是否已經有點以及有哪些點（查詢過程參考box-wise delete）；
  3. 如果已經有點了，将已有點和新點一起排序，找出離體素中心最近的那個點，然後做判斷：如果最近的點是已有點，意味着新點無必要再插入了，結束處理；如果最近的點是新點，則把已有點全部标記删除，并插入新點；
  4. 如果體素内尚不存在點，則直接插入新點。 
// KD_TREE 類的 Add_Points 函數,用于将一組點添加到 KD 樹中
template <typename PointType>
int KD_TREE<PointType>::Add_Points(PointVector & PointToAdd, bool downsample_on)
{
    // 初始化一些變量
    // int NewPointSize = PointToAdd.size();   // wgh: unused variable.
    // int tree_size = size();                 // wgh: unused variable.
    BoxPointType Box_of_Point;
    PointType downsample_result, mid_point;
    bool downsample_switch = downsample_on && DOWNSAMPLE_SWITCH;
    float min_dist, tmp_dist;
    int tmp_counter = 0;
    // 周遊所有點，逐個插入。
    for (std::size_t i=0; i<PointToAdd.size();i++){
        if (downsample_switch){
            // 獲得插入點所在的Voxel，計算Voxel的幾何中心點（将來隻保留最接近中心點的point）
            Box_of_Point.vertex_min[0] = floor(PointToAdd[i].x/downsample_size)*downsample_size;
            Box_of_Point.vertex_max[0] = Box_of_Point.vertex_min[0]+downsample_size;
            Box_of_Point.vertex_min[1] = floor(PointToAdd[i].y/downsample_size)*downsample_size;
            Box_of_Point.vertex_max[1] = Box_of_Point.vertex_min[1]+downsample_size; 
            Box_of_Point.vertex_min[2] = floor(PointToAdd[i].z/downsample_size)*downsample_size;
            Box_of_Point.vertex_max[2] = Box_of_Point.vertex_min[2]+downsample_size;   
            mid_point.x = Box_of_Point.vertex_min[0] + (Box_of_Point.vertex_max[0]-Box_of_Point.vertex_min[0])/2.0;
            mid_point.y = Box_of_Point.vertex_min[1] + (Box_of_Point.vertex_max[1]-Box_of_Point.vertex_min[1])/2.0;
            mid_point.z = Box_of_Point.vertex_min[2] + (Box_of_Point.vertex_max[2]-Box_of_Point.vertex_min[2])/2.0;
            // 在目前 Voxel 中搜尋最近的點
            PointVector ().swap(Downsample_Storage);
            Search_by_range(Root_Node, Box_of_Point, Downsample_Storage);
            min_dist = calc_dist(PointToAdd[i],mid_point);
            downsample_result = PointToAdd[i]; 
            // 找到距離目前點最近的點
            for (std::size_t index = 0; index < Downsample_Storage.size(); index++){
                tmp_dist = calc_dist(Downsample_Storage[index], mid_point);
                if (tmp_dist < min_dist){
                    min_dist = tmp_dist;
                    downsample_result = Downsample_Storage[index];//降采樣
                }
            }
            // 如果目前沒有re-balancing任務，也即沒有并行線程，則直接執行`BoxDelete`和`插入一個點`。
            if (Rebuild_Ptr == nullptr || *Rebuild_Ptr != Root_Node){  
                if (Downsample_Storage.size() > 1 || same_point(PointToAdd[i], downsample_result)){
                    if (Downsample_Storage.size() > 0) Delete_by_range(&Root_Node, Box_of_Point, true, true);
                    Add_by_point(&Root_Node, downsample_result, true, Root_Node->division_axis);
                    tmp_counter ++;                      
                }
            // 如果有re-balancing任務在并行運作，在對目前tree執行`BoxDelete`和`插入一個點`之外，還需要把這些操作緩存到logger裡。
            } else {
                if (Downsample_Storage.size() > 1 || same_point(PointToAdd[i], downsample_result)){
                    Operation_Logger_Type  operation_delete, operation;
                    operation_delete.boxpoint = Box_of_Point;
                    operation_delete.op = DOWNSAMPLE_DELETE;
                    operation.point = downsample_result;
                    operation.op = ADD_POINT;
                    pthread_mutex_lock(&working_flag_mutex);
                    if (Downsample_Storage.size() > 0) Delete_by_range(&Root_Node, Box_of_Point, false , true);                                      
                    Add_by_point(&Root_Node, downsample_result, false, Root_Node->division_axis);
                    tmp_counter ++;
                    if (rebuild_flag){
                        pthread_mutex_lock(&rebuild_logger_mutex_lock);
                        if (Downsample_Storage.size() > 0) Rebuild_Logger.push(operation_delete);
                        Rebuild_Logger.push(operation);
                        pthread_mutex_unlock(&rebuild_logger_mutex_lock);
                    }
                    pthread_mutex_unlock(&working_flag_mutex);
                };
            }
        }
       else {
          //如果不需要降采樣，且無并行re-balancing任務，直接插入點。
          if (Rebuild_Ptr == nullptr || *Rebuild_Ptr != Root_Node){
              Add_by_point(&Root_Node, PointToAdd[i], true, Root_Node->division_axis);     
          } 
          // 如果有并行re-balancing任務，還需額外把目前操作放入logger緩存。
          else {
              Operation_Logger_Type operation;
              operation.point = PointToAdd[i];
              operation.op = ADD_POINT;                
              pthread_mutex_lock(&working_flag_mutex);
              Add_by_point(&Root_Node, PointToAdd[i], false, Root_Node->division_axis);
              if (rebuild_flag){
                  pthread_mutex_lock(&rebuild_logger_mutex_lock);
                  Rebuild_Logger.push(operation);
                  pthread_mutex_unlock(&rebuild_logger_mutex_lock);
              }
              pthread_mutex_unlock(&working_flag_mutex);       
          }
      }
  }
  return tmp_counter;
}

// 工具屬性，單純地往tree結構中插入新節點。
template <typename PointType>
void KD_TREE<PointType>::Add_by_point(KD_TREE_NODE ** root, PointType point, bool allow_rebuild, int father_axis)
{     
    // 如果已經到達葉子節點，直接插入。
    if (*root == nullptr){
        *root = new KD_TREE_NODE;
        InitTreeNode(*root);
        (*root)->point = point;
        (*root)->division_axis = (father_axis + 1) % 3;
        Update(*root);
        return;
    }

    // 标記目前節點為“工作中”，并将操作記錄到Logger中
    (*root)->working_flag = true;
    Operation_Logger_Type add_log;
    // struct timespec Timeout; // wgh: unused variable.
    add_log.op = ADD_POINT;
    add_log.point = point;
    Push_Down(*root);

    // 遞歸插入左子樹
    if (((*root)->division_axis == 0 && point.x < (*root)->point.x) || 
        ((*root)->division_axis == 1 && point.y < (*root)->point.y) || 
        ((*root)->division_axis == 2 && point.z < (*root)->point.z) )
    {
        if ((Rebuild_Ptr == nullptr) || (*root)->left_son_ptr != *Rebuild_Ptr){ 
            Add_by_point(&(*root)->left_son_ptr, point, allow_rebuild, (*root)->division_axis);
        } 
        else {
            // 如果目前有re-balancing任務在并行運作，則将操作記錄到Logger中
            pthread_mutex_lock(&working_flag_mutex);
            Add_by_point(&(*root)->left_son_ptr, point, false,(*root)->division_axis);
            if (rebuild_flag){
                pthread_mutex_lock(&rebuild_logger_mutex_lock);
                Rebuild_Logger.push(add_log);
                pthread_mutex_unlock(&rebuild_logger_mutex_lock);                 
            }
            pthread_mutex_unlock(&working_flag_mutex);            
        }
    }
    //遞歸插入右子樹。
    else {  
        // 如果目前有re-balancing任務在并行運作，則将操作記錄到Logger中
        if ((Rebuild_Ptr == nullptr) || (*root)->right_son_ptr != *Rebuild_Ptr){         
            Add_by_point(&(*root)->right_son_ptr, point, allow_rebuild,(*root)->division_axis);
        } 
        else {
            pthread_mutex_lock(&working_flag_mutex);
            Add_by_point(&(*root)->right_son_ptr, point, false,(*root)->division_axis);       
            if (rebuild_flag){
                pthread_mutex_lock(&rebuild_logger_mutex_lock);
                Rebuild_Logger.push(add_log);
                pthread_mutex_unlock(&rebuild_logger_mutex_lock);                 
            }
            pthread_mutex_unlock(&working_flag_mutex); 
        }
    }

    // 更新目前節點資訊（自下而上），并檢查是否需要re-balancing。
    Update(*root);   
    if (Rebuild_Ptr != nullptr && 
        *Rebuild_Ptr == *root && 
        (*root)->TreeSize < Multi_Thread_Rebuild_Point_Num) Rebuild_Ptr = nullptr; 
    bool need_rebuild = allow_rebuild & Criterion_Check((*root));
    if (need_rebuild) Rebuild(root); 
    // 将目前節點的“工作中”标志位設為false
    if ((*root) != nullptr) (*root)->working_flag = false;   
    return;
}

1.2 插入框節點

框式插入是通過在增量k-d樹中逐個插入新點來實作的，其他框式更新（框式删除和重新插入）是利用屬性range中的範圍資訊實作的，該屬性range形成一個框式CT，并在樹節點上使用惰性标簽。僞代碼如算法2所示。

深入了解ikd-Tree從閱讀代碼開始(三)

點選深入了解ikd-Tree從閱讀代碼開始(三) - 古月居可檢視全文

上一篇: 【跨境電商】2024跨境電商物流深度分析報告-52頁附下載下傳
下一篇: 【大模型】2024大模型十大趨勢手冊-52附下載下傳