rstar/
envelope.rs

1use crate::{Point, RTreeObject};
2
3/// An envelope type that encompasses some child nodes.
4///
5/// An envelope defines how different bounding boxes of inserted children in an r-tree can interact,
6/// e.g. how they can be merged or intersected.
7/// This trait is not meant to be implemented by the user. Currently, only one implementation
8/// exists ([crate::AABB]) and should be used.
9pub trait Envelope: Clone + PartialEq + ::core::fmt::Debug {
10    /// The envelope's point type.
11    type Point: Point;
12
13    /// Creates a new, empty envelope that does not encompass any child.
14    fn new_empty() -> Self;
15
16    /// Returns true if there are no points in the Envelope
17    fn is_empty(&self) -> bool {
18        self == &Self::new_empty()
19    }
20
21    /// Returns true if a point is contained within this envelope.
22    fn contains_point(&self, point: &Self::Point) -> bool;
23
24    /// Returns true if another envelope is _fully contained_ within `self`.
25    fn contains_envelope(&self, aabb: &Self) -> bool;
26
27    /// Extends `self` to contain another envelope.
28    fn merge(&mut self, other: &Self);
29    /// Returns the minimal envelope containing `self` and another envelope.
30    fn merged(&self, other: &Self) -> Self;
31
32    /// Returns true if `self` and `other` intersect. The intersection might be
33    /// of zero area (the two envelopes only touching each other).
34    fn intersects(&self, other: &Self) -> bool;
35    /// Returns the area of the intersection of `self` and another envelope.
36    fn intersection_area(&self, other: &Self) -> <Self::Point as Point>::Scalar;
37
38    /// Returns this envelope's area. Must be at least 0.
39    fn area(&self) -> <Self::Point as Point>::Scalar;
40
41    /// Returns the squared distance between the envelope's border and a point.
42    ///
43    /// # Notes
44    /// - While euclidean distance will be the correct choice for most use cases, any distance metric
45    ///   fulfilling the [usual axioms](https://en.wikipedia.org/wiki/Metric_space)
46    ///   can be used when implementing this method
47    /// - Implementers **must** ensure that the distance metric used matches that of [crate::PointDistance::distance_2]
48    fn distance_2(&self, point: &Self::Point) -> <Self::Point as Point>::Scalar;
49
50    /// Returns the squared min-max distance, a concept that helps to find nearest neighbors efficiently.
51    ///
52    /// Visually, if an AABB and a point are given, the min-max distance returns the distance at which we
53    /// can be assured that an element must be present. This serves as an upper bound during nearest neighbor search.
54    ///
55    /// # References
56    /// [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)
57    fn min_max_dist_2(&self, point: &Self::Point) -> <Self::Point as Point>::Scalar;
58
59    /// Returns the envelope's center point.
60    fn center(&self) -> Self::Point;
61
62    /// Returns a value proportional to the envelope's perimeter.
63    fn perimeter_value(&self) -> <Self::Point as Point>::Scalar;
64
65    /// Sorts a given set of objects with envelopes along one of their axes.
66    fn sort_envelopes<T: RTreeObject<Envelope = Self>>(axis: usize, envelopes: &mut [T]);
67
68    /// Partitions objects with an envelope along a certain axis.
69    ///
70    /// After calling this, envelopes[0..selection_size] are all smaller
71    /// than envelopes[selection_size + 1..].
72    fn partition_envelopes<T: RTreeObject<Envelope = Self>>(
73        axis: usize,
74        envelopes: &mut [T],
75        selection_size: usize,
76    );
77}
rstar/envelope.rs

rstar/
envelope.rs
