Trait rstar::SelectionFunction

pub trait SelectionFunction<T>
where
    T: RTreeObject,
{
    // Required method
    fn should_unpack_parent(&self, envelope: &T::Envelope) -> bool;

    // Provided method
    fn should_unpack_leaf(&self, _leaf: &T) -> bool { ... }
}

Advanced trait to iterate through an r-tree. Usually it should not be required to be implemented.

It is important to know some details about the inner structure of r-trees to understand this trait. Any node in an r-tree is either a leaf (containing exactly one T: RTreeObject) or a parent (containing multiple nodes). The main benefit of r-trees lies in their ability to efficiently guide searches through the tree. This is done by pruning: Knowing the envelopes of parent nodes often allows the search to completely skip them and all contained children instead of having to iterate through them, e.g. when searching for elements in a non-intersecting envelope. This often reduces the expected time from O(n) to O(log(n)).

This trait can be used to define searches through the r-tree by defining whether a node should be further investigated (“unpacked”) or pruned.

Usually, the various locate_[...] methods of super::super::RTree should cover most common searches. Otherwise, implementing SelectionFunction and using crate::RTree::locate_with_selection_function can be used to tailor a custom search.

Required Methods

fn should_unpack_parent(&self, envelope: &T::Envelope) -> bool

Return true if a parent node should be unpacked during a search.

The parent node’s envelope is given to guide the decision.

Provided Methods

fn should_unpack_leaf(&self, _leaf: &T) -> bool

Returns true if a given child node should be returned during a search. The default implementation will always return true.

Implementors