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

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