KD 树

用于在 k 维空间中高效查找点的数据结构。

这是 Rust 中 KD 树的一个开发中实现。以下是当前已实现的功能和计划实现的功能列表。

• 构建树
• 查找半径内的所有点
• 查找最近邻
• 插入新点
• 查找 N 个最近邻
• 删除点
• 重新平衡树
• 序列化树
• 发布包
• 添加 K 维度（目前仅支持 2D）
• 添加示例

最初开发这个项目是为了学习 Rust 并为鸟群模拟实现 KD 树。尽管模拟还在进行中，但我计划随着对 Rust 的了解加深以及时间的允许继续完善这个项目。

性能

KD 树的性能尚未优化。我计划在实现所有功能后进行性能优化。当前的性能是通过 rustup run nightly cargo bench 获取的，如下所示

用法 - TODO

发布正在进行中

use kd_tree::KDTree;

fn main() {
    let mut node: KdNode<i32> = KdNode::new();
    // Tree Root
    node.insert(1, 1);
    node.insert(2, 2);
    node.insert(2, -12);

    assert_eq!(node.nearest_neighbor(Point{x: 1, y: 1}, 1.0), vec![Point{x: 1, y: 1}]);
}

以下是 KD 树结构的示意图。KD 树是一种二叉树，其中每个节点是 k 维空间中的一个点。树的每一层交替由不同的维度分割。根节点由第一个维度分割，根节点的子节点由第二个维度分割，通常在 2D 空间中是 x 和 y 维度。3D 空间将由 x、y 和 z 维度分割。

贡献

欢迎提交拉取请求。对于重大更改，请首先提交一个 issue 以讨论您希望进行的更改。

参考

• KD 树
• KD 树可视化
• KD 树最近邻
• 期望对数时间内邻域计算的证明 - Martin Skrodzki
• KD 树简介

许可证

MIT