Trait rstar::SelectionFunction

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

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

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

It is important to know some details about the inner structure of r-trees to comprehend 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 to completely skip them and all contained children during a search instead 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 if a node should be further investigated ("unpacked") or pruned.

Usually, the various locate_[...] methods of RTree should cover most common searches. Otherwise, implementing SelectionFunction and using 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.

Loading content...

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.

Loading content...

Implementors

Loading content...