rstar/envelope.rs
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
use crate::{Point, RTreeObject};
/// 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.
pub trait Envelope: Clone + PartialEq + ::core::fmt::Debug {
/// The envelope's point type.
type Point: Point;
/// Creates a new, empty envelope that does not encompass any child.
fn new_empty() -> Self;
/// Returns true if a point is contained within this envelope.
fn contains_point(&self, point: &Self::Point) -> bool;
/// Returns true if another envelope is _fully contained_ within `self`.
fn contains_envelope(&self, aabb: &Self) -> bool;
/// Extends `self` to contain another envelope.
fn merge(&mut self, other: &Self);
/// Returns the minimal envelope containing `self` and another envelope.
fn merged(&self, other: &Self) -> Self;
/// Returns true if `self` and `other` intersect. The intersection might be
/// of zero area (the two envelopes only touching each other).
fn intersects(&self, other: &Self) -> bool;
/// Returns the area of the intersection of `self` and another envelope.
fn intersection_area(&self, other: &Self) -> <Self::Point as Point>::Scalar;
/// Returns this envelope's area. Must be at least 0.
fn area(&self) -> <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](https://en.wikipedia.org/wiki/Metric_space)
/// can be used when implementing this method
/// - Implementers **must** ensure that the distance metric used matches that of [crate::PointDistance::distance_2]
fn distance_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.](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.133.2288)
fn min_max_dist_2(&self, point: &Self::Point) -> <Self::Point as Point>::Scalar;
/// Returns the envelope's center point.
fn center(&self) -> Self::Point;
/// Returns a value proportional to the envelope's perimeter.
fn perimeter_value(&self) -> <Self::Point as Point>::Scalar;
/// Sorts a given set of objects with envelopes along one of their axes.
fn sort_envelopes<T: RTreeObject<Envelope = Self>>(axis: usize, envelopes: &mut [T]);
/// Partitions objects with an envelope along a certain axis.
///
/// After calling this, envelopes[0..selection_size] are all smaller
/// than envelopes[selection_size + 1..].
fn partition_envelopes<T: RTreeObject<Envelope = Self>>(
axis: usize,
envelopes: &mut [T],
selection_size: usize,
);
}