sif-rtree

A simple library implementing an immutable, flat representation of an R-tree supporting several kinds of spatial queries, nearest neighbour search and backing storage based on memory maps.

License

Licensed under

• Apache License, Version 2.0 or
• MIT license

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

lib.rs:

A simple library implementing an immutable, flat representation of an R-tree

The library uses the same overlap-minimizing top-down bulk loading algorithm as the rstar crate. Its supports several kinds of spatial queries, nearest neighbour search and has a simple implementation as the objects in the index are fixed after construction. This also enables a flat and thereby cache-friendly memory layout which can be backed by memory maps.

The library provides optional integration with [serde] for (de-)serialization of the trees.

Example

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]);

The RTree data structure is generic over its backing storage as long as it can be converted into a slice via the AsRef trait. This can for instance be used to memory map R-trees from persistent storage.

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));