[−][src]Trait rstar::SelectionFunction
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.
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
.