KD-Tree的C++实现

• 构建KD-Tree
• 最近邻搜索
• 增量式构建KD-Tree: 再平衡
• 半径搜索
• 简化排序算法(1M数据构建耗时: 1.25s->0.95s)
• 使用PCL容器重构KD-Tree(1M数据构建耗时: 0.95s->0.6s)

测试结果

1000000 points' building time is: 0.603789s
100000  points' insert time is  : 0.074711s
input         : 0.969599 0.217454 0.154454
**********************************
********* nearest search *********
**********************************
----------- kdtree search -----------
The run time is: 4e-06 s
nearest: 0.967563 0.216187 0.158846
----------- linear search -----------
The run time is: 0.00229 s
nearest: 0.967563 0.216187 0.158846
*********************************
********* radius search *********
*********************************
----------- kdtree search -----------
The run time is: 0.001459 s
total num: 21475
----------- linear search -----------
The run time is: 0.00228 s
total num: 21475