rstar/
params.rs

1use crate::algorithm::rstar::RStarInsertionStrategy;
2use crate::{Envelope, Point, RTree, RTreeObject};
3
4/// Defines static parameters for an r-tree.
5///
6/// Internally, an r-tree contains several nodes, similar to a b-tree. These parameters change
7/// the size of these nodes and can be used to fine-tune the tree's performance.
8///
9/// # Example
10/// ```
11/// use rstar::{RTreeParams, RTree, RStarInsertionStrategy};
12///
13/// // This example uses an rtree with larger internal nodes.
14/// struct LargeNodeParameters;
15///
16/// impl RTreeParams for LargeNodeParameters
17/// {
18///     const MIN_SIZE: usize = 10;
19///     const MAX_SIZE: usize = 30;
20///     const REINSERTION_COUNT: usize = 5;
21///     type DefaultInsertionStrategy = RStarInsertionStrategy;
22/// }
23///
24/// // Optional but helpful: Define a type alias for the new r-tree
25/// type LargeNodeRTree<T> = RTree<T, LargeNodeParameters>;
26///
27/// # fn main() {
28/// // The only difference from now on is the usage of "new_with_params" instead of "new"
29/// let mut large_node_tree: LargeNodeRTree<_> = RTree::new_with_params();
30/// // Using the r-tree should allow inference for the point type
31/// large_node_tree.insert([1.0, -1.0f32]);
32/// // There is also a bulk load method with parameters:
33/// # let some_elements = vec![[0.0, 0.0]];
34/// let tree: LargeNodeRTree<_> = RTree::bulk_load_with_params(some_elements);
35/// # }
36/// ```
37pub trait RTreeParams: Send + Sync {
38    /// The minimum size of an internal node. `MIN_SIZE` must be greater than zero, and up to half
39    /// as large as `MAX_SIZE`.
40    ///
41    /// Choosing a value around one half or one third of `MAX_SIZE` is recommended. Larger values
42    /// should yield slightly better tree quality, while lower values may benefit insertion
43    /// performance.
44    const MIN_SIZE: usize;
45
46    /// The maximum size of an internal node. Larger values will improve insertion performance
47    /// but increase the average query time.
48    const MAX_SIZE: usize;
49
50    /// The number of nodes that the insertion strategy tries to occasionally reinsert to
51    /// maintain a good tree quality. Must be smaller than `MAX_SIZE` - `MIN_SIZE`.
52    /// Larger values will improve query times but increase insertion time.
53    const REINSERTION_COUNT: usize;
54
55    /// The insertion strategy which is used when calling [RTree::insert].
56    type DefaultInsertionStrategy: InsertionStrategy;
57}
58
59/// The default parameters used when creating an r-tree without specific parameters.
60#[derive(Clone, Copy, PartialEq, Eq)]
61pub struct DefaultParams;
62
63impl RTreeParams for DefaultParams {
64    const MIN_SIZE: usize = 3;
65    const MAX_SIZE: usize = 6;
66    const REINSERTION_COUNT: usize = 2;
67    type DefaultInsertionStrategy = RStarInsertionStrategy;
68}
69
70/// Defines how points are inserted into an r-tree.
71///
72/// Different strategies try to minimize both _insertion time_ (how long does it take to add a new
73/// object into the tree?) and _querying time_ (how long does an average nearest neighbor query
74/// take?).
75/// Currently, only one insertion strategy is implemented: R* (R-star) insertion. R* insertion
76/// tries to minimize querying performance while yielding reasonable insertion times, making it a
77/// good default strategy. More strategies may be implemented in the future.
78///
79/// Only calls to [RTree::insert] are affected by this strategy.
80///
81/// This trait is not meant to be implemented by the user.
82pub trait InsertionStrategy {
83    #[doc(hidden)]
84    fn insert<T, Params>(tree: &mut RTree<T, Params>, t: T)
85    where
86        Params: RTreeParams,
87        T: RTreeObject;
88}
89
90pub fn verify_parameters<T: RTreeObject, P: RTreeParams>() {
91    assert!(
92        P::MAX_SIZE >= 4,
93        "MAX_SIZE too small. Must be larger than 4."
94    );
95
96    assert!(P::MIN_SIZE > 0, "MIN_SIZE must be at least 1",);
97    let max_min_size = (P::MAX_SIZE + 1) / 2;
98    assert!(
99        P::MIN_SIZE <= max_min_size,
100        "MIN_SIZE too large. Must be less or equal to {:?}",
101        max_min_size
102    );
103
104    let max_reinsertion_count = P::MAX_SIZE - P::MIN_SIZE;
105    assert!(
106        P::REINSERTION_COUNT < max_reinsertion_count,
107        "REINSERTION_COUNT too large. Must be smaller than {:?}",
108        max_reinsertion_count
109    );
110
111    let dimension = <T::Envelope as Envelope>::Point::DIMENSIONS;
112    assert!(
113        dimension > 1,
114        "Point dimension too small - must be at least 2"
115    );
116}
rstar/params.rs

rstar/
params.rs
