sif-rtree

一个简单的库，实现了 R-tree 的不可变、平面表示，支持多种空间查询、近邻搜索和基于内存映射的存储。

许可证

许可协议：

• Apache 许可证 2.0 版 或
• MIT 许可证

根据您的要求。

贡献

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

lib.rs:

一个简单的库，实现了 R-tree 的不可变、平面表示

该库使用与 rstar crate 相同的向上批量加载算法，以最小化重叠。它支持多种空间查询、近邻搜索，并且由于索引对象在构建后固定，因此具有简单的实现。这也使得内存布局扁平化，便于缓存，并可以由内存映射支持。

该库提供与 [serde] 的可选集成，用于树的结构化和反结构化。

示例

use std::ops::ControlFlow;

use sif_rtree::{DEF_NODE_LEN, Distance, RTree, Object};

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

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

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

impl Distance<[f64; 2]> for Something {
    fn distance_2(&self, point: &[f64; 2]) -> f64 {
        self.1.distance_2(point)
    }
}

let index = RTree::new(
    DEF_NODE_LEN,
    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_within_distance_of_point(&[0., 0.], 3., |thing| {
    close_by.push(thing.0);

    ControlFlow::Continue(())
});

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

《RTree》数据结构在其底层存储上具有泛型特性，只要它可以通过AsRef特性转换为切片。例如，可以使用它将持久存储中的R树内存映射。

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

use memmap2::Mmap;

use sif_rtree::{Node, Object, Point, RTree};

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

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

    fn aabb(&self) -> (Self::Point, Self::Point) {
        let min = self.0[0].min(&self.0[1]).min(&self.0[2]);
        let max = self.0[0].max(&self.0[1]).max(&self.0[2]);
        (min, max)
    }
}

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

struct TriangleSoup(Mmap);

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

        unsafe { from_raw_parts(ptr, len) }
    }
}

let index = RTree::new_unchecked(TriangleSoup(map));