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.

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(
    [
        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]),
    ]
    .into(),
);

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

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 real space
• WithinDistance
  A query which yields all objects within a given distance to a central point in N-dimensional real space

Traits

• Object
  Defines the objects which can be organized in a KdTree by positioning them in a real space defined via the Point trait
• Point
  Defines a finite-dimensional real 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