10 releases (5 breaking)
0.6.0 | Feb 18, 2024 |
---|---|
0.5.2 | Feb 11, 2024 |
0.5.0 | Aug 10, 2023 |
0.4.0 | Aug 7, 2023 |
0.1.1 | Apr 10, 2023 |
#1415 in Data structures
27KB
527 lines
sif-kdtree
A simple library implementing an immutable, flat representation of a k-d tree supporting arbitrary spatial queries, nearest neighbour search and backing storage based on memory maps.
License
Licensed under
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 a k-d tree
The library supports arbitrary spatial queries via the Query
trait and nearest neighbour search.
Its implementation is simple 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 [rayon] for parallel construction and queries and [serde] for (de-)serialization of the trees.
Example
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);
The KdTree
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 k-d trees from persistent storage.
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));
Dependencies
~94–580KB
~12K SLoC