r3live ikd-tree

算法来自fast-lio2

1. 算法说明

1) kd tree

用途：查找邻近点。
方法描述：将数据点递归的进行二分。


image.png

2) ikd tree

用途：在kd tree的基础上进行改进，从而支持高效的插入、删除操作。
改进：1. 重建树时，使用两个线程。2. 删除点时，先标记为deleted，需删除的点达到一定比例后再重建树。3. 类似的，添加点时，先放到末端，不平衡的部分达到一定比例后再重建树。

重要功能：

  1. 加入点并下采样：
    找出新点所属的box，只保留box中最接近中点的点，对其他点删除
  2. 删除点
  3. 重建子树（主/第二线程）：
    a. flatten：把子树的数据进行拷贝，这个过程阻止增删操作。这个过程也会删除deleted的点
    lock incremental update -> flatten tree to V -> unlock incremental update + record requests in operation logger
    b. rebuild：重建树并把新子树赋给老树，这个过程阻止增删操作
    rebuild -> lock requests -> replace -> unlock requests
  4. 查找近邻

流程：

  1. "Build"
  2. "lasermap_fov_segment" 维持地图大小
  3. "Add_Points"：加入点并下采样
  4. "Criterion_Check" => "Rebuild"（主/第二线程）=> multi_thread_rebuild

  5. "Nearest_Search"：查找近邻


    _cgi-bin_mmwebwx-bin_webwxgetmsgimg &MsgID=8865113778370801820&skey=@crypt_16dbddde_a0b29813c5592a340ddb27a2bef8bee3&mmweb_appid=wx_webfilehelper.jpeg
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容