Expand description
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));
Structs§
- An immutable, flat representation of an R-tree
Enums§
- A node in the tree
Constants§
- A sensible default value for the node length, balancing query efficency against memory overhead
Traits§
- Defines a distance metric between a type (objects, points, AABB, etc.) and points
- Defines a finite-dimensional space in terms of coordinate values along a chosen set of axes