kdtree

在Rust中用于快速地理空间索引和最近邻查找的K维树

• 包
• 文档
• 用法
• 基准测试
• 许可证

用法

将 kdtree 添加到 Cargo.toml

[dependencies]
kdtree = "0.5.1"

向kdtree添加点并使用距离函数查询最近的n个点

use kdtree::KdTree;
use kdtree::ErrorKind;
use kdtree::distance::squared_euclidean;

let a: ([f64; 2], usize) = ([0f64, 0f64], 0);
let b: ([f64; 2], usize) = ([1f64, 1f64], 1);
let c: ([f64; 2], usize) = ([2f64, 2f64], 2);
let d: ([f64; 2], usize) = ([3f64, 3f64], 3);

let dimensions = 2;
let mut kdtree = KdTree::new(dimensions);

kdtree.add(&a.0, a.1).unwrap();
kdtree.add(&b.0, b.1).unwrap();
kdtree.add(&c.0, c.1).unwrap();
kdtree.add(&d.0, d.1).unwrap();

assert_eq!(kdtree.size(), 4);
assert_eq!(
    kdtree.nearest(&a.0, 0, &squared_euclidean).unwrap(),
    vec![]
);
assert_eq!(
    kdtree.nearest(&a.0, 1, &squared_euclidean).unwrap(),
    vec![(0f64, &0)]
);
assert_eq!(
    kdtree.nearest(&a.0, 2, &squared_euclidean).unwrap(),
    vec![(0f64, &0), (2f64, &1)]
);
assert_eq!(
    kdtree.nearest(&a.0, 3, &squared_euclidean).unwrap(),
    vec![(0f64, &0), (2f64, &1), (8f64, &2)]
);
assert_eq!(
    kdtree.nearest(&a.0, 4, &squared_euclidean).unwrap(),
    vec![(0f64, &0), (2f64, &1), (8f64, &2), (18f64, &3)]
);
assert_eq!(
    kdtree.nearest(&a.0, 5, &squared_euclidean).unwrap(),
    vec![(0f64, &0), (2f64, &1), (8f64, &2), (18f64, &3)]
);
assert_eq!(
    kdtree.nearest(&b.0, 4, &squared_euclidean).unwrap(),
    vec![(0f64, &1), (2f64, &0), (2f64, &2), (8f64, &3)]
);

基准测试

cargo bench 在2.3 GHz Intel i5-7360U上

cargo bench
     Running target/release/deps/bench-9e622e6a4ed9b92a

running 2 tests
test bench_add_to_kdtree_with_1k_3d_points       ... bench:         106 ns/iter (+/- 25)
test bench_nearest_from_kdtree_with_1k_3d_points ... bench:       1,237 ns/iter (+/- 266)

test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out

感谢 Eh2406 做出各种修复和性能改进。

许可证

许可证

• 根据您的选择，许可为Apache License，版本2.0 (LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0)
• 或MIT License (LICENSE-MIT 或 http://opensource.org/licenses/MIT)

。

贡献

除非您明确声明，否则根据Apache-2.0许可证定义的任何旨在包含在作品中的有意提交的贡献，均应按照上述方式双重许可，不附加任何额外的条款或条件。