Trait Envelope

pub trait Envelope:
    Clone
    + PartialEq
    + Debug {
    type Point: Point;

    // Required methods
    fn new_empty() -> Self;
    fn contains_point(&self, point: &Self::Point) -> bool;
    fn contains_envelope(&self, aabb: &Self) -> bool;
    fn merge(&mut self, other: &Self);
    fn merged(&self, other: &Self) -> Self;
    fn intersects(&self, other: &Self) -> bool;
    fn intersection_area(&self, other: &Self) -> <Self::Point as Point>::Scalar;
    fn area(&self) -> <Self::Point as Point>::Scalar;
    fn distance_2(&self, point: &Self::Point) -> <Self::Point as Point>::Scalar;
    fn min_max_dist_2(
        &self,
        point: &Self::Point,
    ) -> <Self::Point as Point>::Scalar;
    fn center(&self) -> Self::Point;
    fn perimeter_value(&self) -> <Self::Point as Point>::Scalar;
    fn sort_envelopes<T: RTreeObject<Envelope = Self>>(
        axis: usize,
        envelopes: &mut [T],
    );
    fn partition_envelopes<T: RTreeObject<Envelope = Self>>(
        axis: usize,
        envelopes: &mut [T],
        selection_size: usize,
    );
}

An envelope type that encompasses some child nodes.

An envelope defines how different bounding boxes of inserted children in an r-tree can interact, e.g. how they can be merged or intersected. This trait is not meant to be implemented by the user. Currently, only one implementation exists (crate::AABB) and should be used.

Required Associated Types

type Point: Point

The envelope’s point type.

Required Methods

fn new_empty() -> Self

Creates a new, empty envelope that does not encompass any child.

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

Returns true if a point is contained within this envelope.

fn contains_envelope(&self, aabb: &Self) -> bool

Returns true if another envelope is fully contained within self.

fn merge(&mut self, other: &Self)

Extends self to contain another envelope.

fn merged(&self, other: &Self) -> Self

Returns the minimal envelope containing self and another envelope.

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

Returns true if self and other intersect. The intersection might be of zero area (the two envelopes only touching each other).

fn intersection_area(&self, other: &Self) -> <Self::Point as Point>::Scalar

Returns the area of the intersection of self and another envelope.

fn area(&self) -> <Self::Point as Point>::Scalar

Returns this envelope’s area. Must be at least 0.

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

Returns the squared distance between the envelope’s border 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::PointDistance::distance_2

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

Returns the squared min-max distance, a concept that helps to find nearest neighbors efficiently.

Visually, if an AABB and a point are given, the min-max distance returns the distance at which we can be assured that an element must be present. This serves as an upper bound during nearest neighbor search.

References

Roussopoulos, Nick, Stephen Kelley, and Frédéric Vincent. “Nearest neighbor queries.” ACM sigmod record. Vol. 24. No. 2. ACM, 1995.

fn center(&self) -> Self::Point

Returns the envelope’s center point.

fn perimeter_value(&self) -> <Self::Point as Point>::Scalar

Returns a value proportional to the envelope’s perimeter.

fn sort_envelopes<T: RTreeObject<Envelope = Self>>( axis: usize, envelopes: &mut [T], )

Sorts a given set of objects with envelopes along one of their axes.

fn partition_envelopes<T: RTreeObject<Envelope = Self>>( axis: usize, envelopes: &mut [T], selection_size: usize, )

Partitions objects with an envelope along a certain axis.

After calling this, envelopes[0..selection_size] are all smaller than envelopes[selection_size + 1..].

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<P> Envelope for AABB<P>

where P: Point,

type Point = P