si-f-kdtree

si-f-kdtree是一个简单的库，实现了k-d树的不可变、扁平表示，支持任意空间查询、最近邻搜索以及基于内存映射的存储。

许可证

许可协议

• Apache License, Version 2.0或
• MIT许可证

任选其一。

贡献

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

lib.rs:

实现k-d树的简单库，不可变、扁平表示

该库通过Query特性和最近邻搜索支持任意空间查询。由于其索引中的对象在构建后固定，因此实现简单。这也使得内存布局扁平，从而缓存友好，可以由内存映射支持。

该库提供与[rayon]的可选集成，用于并行构建和查询，以及与[serde]的集成，用于树的（反）序列化。

示例

use std::ops::ControlFlow;

use sif_kdtree::{KdTree, Object, WithinDistance};

struct Something(usize, [f64; 2]);

impl Object for Something {
    type Point = [f64; 2];

    fn position(&self) -> &Self::Point {
        &self.1
    }
}

let index = KdTree::new(
    vec![
        Something(0, [-0.4, -3.3]),
        Something(1, [-4.5, -1.8]),
        Something(2, [0.7, 2.0]),
        Something(3, [1.7, 1.5]),
        Something(4, [-1.3, 2.3]),
        Something(5, [2.2, 1.0]),
        Something(6, [-3.7, 3.8]),
        Something(7, [-3.2, -0.1]),
        Something(8, [1.4, 2.7]),
        Something(9, [3.1, -0.0]),
        Something(10, [4.3, 0.8]),
        Something(11, [3.9, -3.3]),
        Something(12, [0.4, -3.2]),
    ],
);

let mut close_by = Vec::new();

index.look_up(&WithinDistance::new([0., 0.], 3.), |thing| {
    close_by.push(thing.0);

    ControlFlow::Continue(())
});

assert_eq!(close_by, [2, 4, 5, 3]);

let closest = index.nearest(&[0., 0.]).unwrap().0;

assert_eq!(closest, 2);

KdTree数据结构在支持通过AsRef特性转换为切片的情况下是通用的。例如，可以使用此功能从持久存储中内存映射k-d树。

use std::fs::File;
use std::mem::size_of;
use std::slice::from_raw_parts;

use memmap2::Mmap;

use sif_kdtree::{KdTree, Object};

#[derive(Clone, Copy)]
struct Point([f64; 3]);

impl Object for Point {
    type Point = [f64; 3];

    fn position(&self) -> &Self::Point {
        &self.0
    }
}

let file = File::open("index.bin")?;
let map = unsafe { Mmap::map(&file)? };

struct PointCloud(Mmap);

impl AsRef<[Point]> for PointCloud {
    fn as_ref(&self) -> &[Point] {
        let ptr = self.0.as_ptr().cast();
        let len = self.0.len() / size_of::<Point>();

        unsafe { from_raw_parts(ptr, len) }
    }
}

let index = KdTree::new_unchecked(PointCloud(map));