ikd-Tree is an incremental k-d tree designed for robotic applications. The ikd-Tree incrementally updates a k-d tree with new coming points only, leading to much lower computation time than existing static k-d trees. Besides point-wise operations, the ikd-Tree supports several features such as box-wise operations and down-sampling that are practically useful in robotic applications.

Yixi Cai 蔡逸熙: Data structure design and implementation

Wei Xu 徐威: Incorporation into LiDAR-inertial odometry package (FAST_LIO2 Released)

More details please refer to our paper and video~

Related paper available on arxiv:

ikd-Tree: An Incremental K-D Tree for robotic applications

Cite as:

@article{cai2021ikd,
  title={ikd-Tree: An Incremental KD Tree for Robotic Applications},
  author={Cai, Yixi and Xu, Wei and Zhang, Fu},
  journal={arXiv preprint arXiv:2102.10808},
  year={2021}
}

Related video: https://youtu.be/ueOunk03zxA

• We upgraded our ikd-Tree to achieve a more stable and efficient performance. More details are shown as follows:
  • Replace the queue and priority queue in STL with our code to avoid memory conflicts.
  • Fix some bugs in re-building of the previous version, which may result in information loss during the multi-thread re-building process.
  • Add a new parameter max_dist to support ranged search to achieve faster nearest search in robotic applications.
  • Fix minor bugs to improve the overall performance.

cd ~/catkin_ws/src
git clone [email protected]:hku-mars/ikd-Tree.git
cd ikd-Tree/build
cmake ..
make -j 9

Note: To run Example 2 & 3, please download the PCD file (HKU_demo_pointcloud) into${Your own directory}/ikd-Tree/materials

cd ${Your own directory}/ikd-Tree/build
# Example 1. Check the speed of ikd-Tree
./ikd_tree_demo
# Example 2. Searching-points-by-box examples
./ikd_Tree_Search_demo
# Example 3. An aysnc. exmaple for readers' better understanding of the principle of ikd-Tree
./ikd_tree_async_demo

Example 2: ikd_tree_Search_demo

Box Search Result	Radius Search Result

Points returned from the two search methods are shown in red.

Example 3: ikd_tree_Async_demo

Original Map:

Box Delete Results:

Points removed from ikd-Tree(red)	Map after box delete

This example is to demonstrate the asynchronous phenomenon in ikd-Tree. The points are deleted by attaching 'deleted' on the tree nodes (map shown in the ) instead of being removed from the ikd-Tree immediately. They are removed from the tree when rebuilding process is performed. Please refer to our paper for more details about delete and rebuilding.

Thanks Marcus Davi for helps in templating the ikd-Tree for more general applications.

Thanks Hyungtae Lim 임형태 for providing application examples on point clouds.