Trait crater::KdRegion

pub trait KdRegion: Sized + Clone {
    type Point: KdPoint;

    // Required methods
    fn split(&self, point: &Self::Point, layer: usize) -> (Self, Self);
    fn extend(&mut self, point: &Self::Point);
    fn single_point(point: &Self::Point) -> Self;
    fn min_sqdist(
        &self,
        point: &Self::Point
    ) -> <Self::Point as KdPoint>::Distance;
    fn max_sqdist(
        &self,
        point: &Self::Point
    ) -> Option<<Self::Point as KdPoint>::Distance>;
    fn might_overlap(&self, other: &Self) -> bool;
    fn is_superset(&self, other: &Self) -> bool;
}

A region in the tree, or in space in general. A type implementing this will be tightly coupled to some type implementing KdPoint. For example, the prebuilt cuboid::CuPoint struct represents a point in Cartesian space with Euclidean distance, and the prebuilt cuboid::CuRegion struct represents cuboid regions of space (rectangles in 2D, rectangular prisms in 3D, etc). Regions often represent infinitely many points in space (how many points are in your typical rectangle?). Regions should be able to represent a single point, but the ability to represent an empty region isn’t necessary.

Required Associated Types

type Point: KdPoint

Required Methods

fn split(&self, point: &Self::Point, layer: usize) -> (Self, Self)

Given a point p in this region A and a layer l, split A into two subregions B and C so that:

• Any point q in A is in B or C, that is, if A.min_sqdist(q) == 0, then either B.min_sqdist(q) == 0 or C.min_sqdist(q) == 0 (possibly both). Note that strictly speaking this only needs to be true over all points in the tree, not all points in space, but in practice it is almost always much easier to make this true for all points in space, not least because this trait and method have no reference to any particular KD tree.
• Any point q in B is <= p in layer l, using KdPoint::cmp, and any point q in C is >= p
• Any point not in A should hopefully be farther from B than from C (or visa versa) in at least some layers (note that distance doesn’t depend on layer, but split direction does). That is, if A.min_dist(q) == d where d > 0, then B.min_sqdist(q), C.min_sqdist(q) >= d (are both at least d), and ideally one should be significantly more in at least some layers. Note how the basic instance of regions, cuboid regions, obviously obey all these properties

fn extend(&mut self, point: &Self::Point)

Given a region and a point possibly not in the region, extend the region to include the point if necessary. The concrete requirements this places on the implementation are that self.min_sqdist(q) can only decrease or remain the same for any fixed q, and in particular self.extend(q) should cause self.min_sqdist(q) to be 0 if it wasn’t already

fn single_point(point: &Self::Point) -> Self

Create a region consisting of a single point. For cuboid regions for example, this is represented as a cuboid whose inclusive “start” and “end” points are both the same. Types implementing this trait should be able to represent single points fairly well, but because of the conservative nature of everything, it is acceptable to fudge it by having a very small region containing the point. It’s not necessary for types to be able to represent an empty region well or even at all.

fn min_sqdist(&self, point: &Self::Point) -> <Self::Point as KdPoint>::Distance

Return the minimal squared distance any point in this region could have to a given point. The return value must be <= KdPoint::sqdist between the given point and any point within this region. It’s safe to return a smaller value, or even always return Distance::zero(), but this degrades performance because we can’t prune subtrees from the search. If B is a subregion of A and p is a point not in A, then B.min_sqdist(p) >= A.min_sqdist(p)

fn max_sqdist( &self, point: &Self::Point ) -> Option<<Self::Point as KdPoint>::Distance>

Return the maximal squared distance any point in this region could have to a given point, or None if infinite. The return value must be >= KdPoint::sqdist between the given point and any point within this region. None is considered infinitely far away. It’s safe to return a larger value, or even always return None, but this may degrade performace for some queries that cull based on minimal distance. Currently, this only happens for kdtree::KdTree::k_closest where [kdtree::QueryOptions::lower_bound] is kdtree::QueryBound::SqDist. If B is a subregion of A and p is a point not in A, then B.max_sqdist(p) <= A.max_sqdist(p).

fn might_overlap(&self, other: &Self) -> bool

Return true if this region and another region might overlap, or false if they are definitely disjoint. Conservative implementors can always return true. Currently only used by kdtree::KdTree::k_closest if kdtree::QueryOptions::outer_bound is kdtree::QueryBound::Region.

fn is_superset(&self, other: &Self) -> bool

Return true if this region is DEFINITELY a superset of another region, or false if it is not. A may be a superset of B even if B is internally tangent to A or B is A. May return false even if self is a superset of other, if it would be expensive or difficult to compute correctly. Currently only used by kdtree::KdTree::k_closest if kdtree::QueryOptions::inner_bound is kdtree::QueryBound::Region

Object Safety

This trait is not object safe.

Implementors

impl<T, const N: usize> KdRegion for CuRegion<T, N>

where T: Ord + Clone + NumRef,

type Point = CuPoint<T, N>