Trait crater::KdPoint

pub trait KdPoint: Sized + Eq {
    type Distance: Ord + Clone + Zero;

    // Required methods
    fn sqdist(&self, other: &Self) -> Self::Distance;
    fn cmp(&self, other: &Self, layer: usize) -> Ordering;
}

A point in the tree. Types implementing this can contain arbitrary data, to be accessed when the tree is queried by a point + distance, point + count, region, etc. NB: If T: KdPoint, <T as Eq>::eq can be implemented by comparing T::sqdist to T::Distance::zero()

Required Associated Types

type Distance: Ord + Clone + Zero

The type used by sqdist and related KdRegion functions to represent (squared) distance. Must be totally ordered, where greater distances mean points are farther apart. Also must be Clone and have a meaningful minimum value (0)

Required Methods

fn sqdist(&self, other: &Self) -> Self::Distance

The squared distance is more computationally convenient than the proper distance in many cases. The distance function only has to be topologically consistent and totally ordered. See KdRegion::min_sqdist for more info. The return value should be >= Distance::zero().

fn cmp(&self, other: &Self, layer: usize) -> Ordering

Compare two points in some layer of the tree. This generalizes splitting different layers of the tree in different dimensions and is tied to KdRegion::split. Traditionally, points in a KD tree are compared by their 1st coordinate in layer 0, their 2nd in layer 1, …, onto their Kth in layer k - 1, and then in layer K it wraps around to 0 and repeats. So for a 3D KD tree, layer 0 would compare x coordinates with the root having the median x coordinate, all points in the first subtree having x coordinate <=, and all points in the second subtree having x coordinate >=. This method allows for more general strategies, but pushes some of the burden of layer-dependent behavior onto the point type. It’s still possible to just implement a by-coordinate cmp function of course, and this is what the prebuilt CuPoint does.

Object Safety

This trait is not object safe.

Implementors

impl<T, const N: usize> KdPoint for CuPoint<T, N>

where T: Ord + Clone + NumRef,

type Distance = T