Repository files navigation

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.

• Build a balanced k-d tree -Build()

• Dynamically insert points to or delete points from the k-d tree -Add_Points() / Delete_Points()

• Delete points inside given axis-aligned bounding boxes -Delete_Point_Boxes()

• K Nearest Neighbor Search with range limitation -Nearest_Search()

• Acquire points inside a given axis-aligned bounding box on the k-d tree -Box_Search()

• Acquire points inside a ball with given radius on the k-d tree -Radius_Search()

• Browse theUser Manual for using our ikd-Tree.

• Yixi CAI 蔡逸熙: Data structure design and implementation

• Wei XU 徐威: Incorporation intoLiDAR-inertial odometry package FAST_LIO2 (TRO, 2022)

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

• FAST-LIO2: Fast Direct LiDAR-Inertial Odometry

If you are using any code of this repo in your research, please cite at least one of the articles as following:

• ikd-Tree

@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}}

• FAST-LIO2

@article{xu2022fast,  title={Fast-lio2: Fast direct lidar-inertial odometry},  author={Xu, Wei and Cai, Yixi and He, Dongjiao and Lin, Jiarong and Zhang, Fu},  journal={IEEE Transactions on Robotics},  year={2022},  publisher={IEEE}}

cd~/catkin_ws/srcgit clone git@github.com:hku-mars/ikd-Tree.gitcd ikd-Tree/buildcmake ..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.

• ThanksMarcus Davi for helps in templating the ikd-Tree for more general applications.

• ThanksHyungtae Lim 임형태 for providing application examples on point clouds.

The source code of ikd-Tree is released underGPLv2 license. For commercial use, please contact Mr. Yixi CAI (yixicai@connect.hku.hk) or Dr. Fu ZHANG (fuzhang@hku.hk).