Crate sif_kdtree

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

Structs

• KdTree
  An immutable, flat representation of a k-d tree
• WithinBoundingBox
  A query which yields all objects within a given axis-aligned boundary box (AABB) in N-dimensional space
• WithinDistance
  A query which yields all objects within a given distance to a central point in N-dimensional real space

Traits

• Distance
  Extends the Point trait by a distance metric required for nearest neighbour search
• Object
  Defines the objects which can be organized in a KdTree by positioning them in the vector space defined via the Point trait
• Point
  Defines a finite-dimensional space in terms of coordinate values along a chosen set of axes
• Query
  Defines a spatial query by its axis-aligned bounding box (AABB) and a method to test a single point