rstar

Trait PointDistance

Source 
pub trait PointDistance: RTreeObject {
    // Required method
    fn distance_2(
        &self,
        point: &<Self::Envelope as Envelope>::Point,
    ) -> <<Self::Envelope as Envelope>::Point as Point>::Scalar;

    // Provided methods
    fn contains_point(
        &self,
        point: &<Self::Envelope as Envelope>::Point,
    ) -> bool { ... }
    fn distance_2_if_less_or_equal(
        &self,
        point: &<Self::Envelope as Envelope>::Point,
        max_distance_2: <<Self::Envelope as Envelope>::Point as Point>::Scalar,
    ) -> Option<<<Self::Envelope as Envelope>::Point as Point>::Scalar> { ... }
}
Expand description

Defines objects which can calculate their minimal distance to a point.

This trait is most notably necessary for support of nearest_neighbor queries.

§Example

use rstar::{RTreeObject, PointDistance, AABB};

struct Circle
{
    origin: [f32; 2],
    radius: f32,
}

impl RTreeObject for Circle {
    type Envelope = AABB<[f32; 2]>;

    fn envelope(&self) -> Self::Envelope {
        let corner_1 = [self.origin[0] - self.radius, self.origin[1] - self.radius];
        let corner_2 = [self.origin[0] + self.radius, self.origin[1] + self.radius];
        AABB::from_corners(corner_1, corner_2)
    }
}

impl PointDistance for Circle
{
    fn distance_2(&self, point: &[f32; 2]) -> f32
    {
        let d_x = self.origin[0] - point[0];
        let d_y = self.origin[1] - point[1];
        let distance_to_origin = (d_x * d_x + d_y * d_y).sqrt();
        let distance_to_ring = distance_to_origin - self.radius;
        let distance_to_circle = f32::max(0.0, distance_to_ring);
        // We must return the squared distance!
        distance_to_circle * distance_to_circle
    }

    // This implementation is not required but more efficient since it
    // omits the calculation of a square root
    fn contains_point(&self, point: &[f32; 2]) -> bool
    {
        let d_x = self.origin[0] - point[0];
        let d_y = self.origin[1] - point[1];
        let distance_to_origin_2 = (d_x * d_x + d_y * d_y);
        let radius_2 = self.radius * self.radius;
        distance_to_origin_2 <= radius_2
    }
}


let circle = Circle {
    origin: [1.0, 0.0],
    radius: 1.0,
};

assert_eq!(circle.distance_2(&[-1.0, 0.0]), 1.0);
assert_eq!(circle.distance_2(&[-2.0, 0.0]), 4.0);
assert!(circle.contains_point(&[1.0, 0.0]));

Required Methods§

Source

fn distance_2( &self, point: &<Self::Envelope as Envelope>::Point, ) -> <<Self::Envelope as Envelope>::Point as Point>::Scalar

Returns the squared distance between an object and a point.

§Notes
  • While euclidean distance will be the correct choice for most use cases, any distance metric fulfilling the usual axioms can be used when implementing this method
  • Implementers must ensure that the distance metric used matches that of crate::Envelope::distance_2

Provided Methods§

Source

fn contains_point(&self, point: &<Self::Envelope as Envelope>::Point) -> bool

Returns true if a point is contained within this object.

By default, any point returning a distance_2 less than or equal to zero is considered to be contained within self. Changing this default behavior is advised if calculating the squared distance is more computationally expensive than a point containment check.

Source

fn distance_2_if_less_or_equal( &self, point: &<Self::Envelope as Envelope>::Point, max_distance_2: <<Self::Envelope as Envelope>::Point as Point>::Scalar, ) -> Option<<<Self::Envelope as Envelope>::Point as Point>::Scalar>

Returns the squared distance to this object, or None if the distance is larger than a given maximum value.

Some algorithms only need to know an object’s distance if it is less than or equal to a maximum value. In these cases, it may be faster to calculate a lower bound of the distance first and returning early if the object cannot be closer than the given maximum.

The provided default implementation will use the distance to the object’s envelope as a lower bound.

If performance is critical and the object’s distance calculation is fast, it may be beneficial to overwrite this implementation.

Implementors§