# kd-tree

**Repository Path**: pengwushao/kd-tree

## Basic Information

- **Project Name**: kd-tree
- **Description**: 可增量构建的kd-tree
- **Primary Language**: Unknown
- **License**: BSD-3-Clause
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 6
- **Created**: 2023-10-20
- **Last Updated**: 2023-10-20

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

### KD-Tree的C++实现

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

### 测试结果
```
1000000 points' building time is: 0.604123s
100000  points' insert time is  : 0.083992s
input         : 0.474971 0.779351 0.943572
**********************************
********* nearest search *********
**********************************
----------- kdtree search -----------
The run time is: 3e-06 s
nearest: 0.477718 0.774989 0.941812
----------- linear search -----------
The run time is: 0.002381 s
nearest: 0.477718 0.774989 0.941812
*********************************
********* radius search *********
*********************************
----------- kdtree search -----------
The run time is: 0.001928 s
total num: 25881
----------- linear search -----------
The run time is: 0.002455 s
total num: 25881
*********************************
******** k-nearest search *******
*********************************
The run time is: 4e-06 s
nearest: 0.476615 0.774104 0.938523
nearest: 0.46879 0.783328 0.944876
nearest: 0.473712 0.779504 0.949804
nearest: 0.477718 0.774989 0.941812
nearest: 0.478485 0.78207 0.938184
```