1 use crate::envelope::Envelope;
2 use crate::node::{envelope_for_children, ParentNode, RTreeNode};
3 use crate::object::RTreeObject;
4 use crate::params::{InsertionStrategy, RTreeParams};
5 use crate::point::{Point, PointExt};
6 use crate::rtree::RTree;
7 use num_traits::{Bounded, Zero};
8
9 /// Inserts points according to the r-star heuristic.
10 ///
11 /// The r*-heuristic focusses on good insertion quality at the costs of
12 /// insertion performance. This strategy is best for use cases with few
13 /// insertions and many nearest neighbor queries.
14 ///
15 /// `RStarInsertionStrategy` is used as the default insertion strategy.
16 /// See [InsertionStrategy](trait.InsertionStrategy.html) for more information on insertion strategies.
17 pub enum RStarInsertionStrategy {}
18
19 enum InsertionResult<T>
20 where
21 T: RTreeObject,
22 {
23 Split(RTreeNode<T>),
24 Reinsert(Vec<RTreeNode<T>>, usize),
25 Complete,
26 }
27
28 impl InsertionStrategy for RStarInsertionStrategy {
insert<T, Params>(tree: &mut RTree<T, Params>, t: T) where Params: RTreeParams, T: RTreeObject,29 fn insert<T, Params>(tree: &mut RTree<T, Params>, t: T)
30 where
31 Params: RTreeParams,
32 T: RTreeObject,
33 {
34 let first = recursive_insert::<_, Params>(tree.root_mut(), RTreeNode::Leaf(t), 0);
35 let mut insertion_stack = vec![first];
36 let mut start_insertion_height = 0;
37 while let Some(next) = insertion_stack.pop() {
38 match next {
39 InsertionResult::Split(node) => {
40 // The root node was split, create a new root and increase height
41 let new_root = ParentNode::new_root::<Params>();
42 let old_root = ::std::mem::replace(tree.root_mut(), new_root);
43 let new_envelope = old_root.envelope.merged(&node.envelope());
44 let root = tree.root_mut();
45 root.envelope = new_envelope;
46 root.children.push(RTreeNode::Parent(old_root));
47 root.children.push(node);
48 start_insertion_height += 1;
49 }
50 InsertionResult::Reinsert(nodes_to_reinsert, target_height) => {
51 let final_height = target_height + start_insertion_height;
52 let root = tree.root_mut();
53 insertion_stack.extend(
54 nodes_to_reinsert
55 .into_iter()
56 .map(|node| forced_insertion::<T, Params>(root, node, final_height)),
57 );
58 }
59 InsertionResult::Complete => (),
60 }
61 }
62 }
63 }
64
forced_insertion<T, Params>( node: &mut ParentNode<T>, t: RTreeNode<T>, target_height: usize, ) -> InsertionResult<T> where T: RTreeObject, Params: RTreeParams,65 fn forced_insertion<T, Params>(
66 node: &mut ParentNode<T>,
67 t: RTreeNode<T>,
68 target_height: usize,
69 ) -> InsertionResult<T>
70 where
71 T: RTreeObject,
72 Params: RTreeParams,
73 {
74 node.envelope.merge(&t.envelope());
75 let expand_index = choose_subtree(node, &t);
76
77 if target_height == 0 || node.children.len() < expand_index {
78 // Force insertion into this node
79 node.children.push(t);
80 return resolve_overflow_without_reinsertion::<_, Params>(node);
81 }
82
83 if let RTreeNode::Parent(ref mut follow) = node.children[expand_index] {
84 match forced_insertion::<_, Params>(follow, t, target_height - 1) {
85 InsertionResult::Split(child) => {
86 node.envelope.merge(&child.envelope());
87 node.children.push(child);
88 resolve_overflow_without_reinsertion::<_, Params>(node)
89 }
90 other => other,
91 }
92 } else {
93 unreachable!("This is a bug in rstar.")
94 }
95 }
96
recursive_insert<T, Params>( node: &mut ParentNode<T>, t: RTreeNode<T>, current_height: usize, ) -> InsertionResult<T> where T: RTreeObject, Params: RTreeParams,97 fn recursive_insert<T, Params>(
98 node: &mut ParentNode<T>,
99 t: RTreeNode<T>,
100 current_height: usize,
101 ) -> InsertionResult<T>
102 where
103 T: RTreeObject,
104 Params: RTreeParams,
105 {
106 node.envelope.merge(&t.envelope());
107 let expand_index = choose_subtree(node, &t);
108
109 if node.children.len() < expand_index {
110 // Force insertion into this node
111 node.children.push(t);
112 return resolve_overflow::<_, Params>(node, current_height);
113 }
114
115 let expand = if let RTreeNode::Parent(ref mut follow) = node.children[expand_index] {
116 recursive_insert::<_, Params>(follow, t, current_height + 1)
117 } else {
118 panic!("This is a bug in rstar.")
119 };
120
121 match expand {
122 InsertionResult::Split(child) => {
123 node.envelope.merge(&child.envelope());
124 node.children.push(child);
125 resolve_overflow::<_, Params>(node, current_height)
126 }
127 InsertionResult::Reinsert(a, b) => {
128 node.envelope = envelope_for_children(&node.children);
129 InsertionResult::Reinsert(a, b)
130 }
131 other => other,
132 }
133 }
134
choose_subtree<'b, T>(node: &mut ParentNode<T>, to_insert: &'b RTreeNode<T>) -> usize where T: RTreeObject,135 fn choose_subtree<'b, T>(node: &mut ParentNode<T>, to_insert: &'b RTreeNode<T>) -> usize
136 where
137 T: RTreeObject,
138 {
139 let all_leaves = match node.children.first() {
140 Some(RTreeNode::Leaf(_)) => return usize::max_value(),
141 Some(RTreeNode::Parent(ref data)) => data
142 .children
143 .first()
144 .map(RTreeNode::is_leaf)
145 .unwrap_or(true),
146 _ => return usize::max_value(),
147 };
148
149 let zero: <<T::Envelope as Envelope>::Point as Point>::Scalar = Zero::zero();
150 let insertion_envelope = to_insert.envelope();
151 let mut inclusion_count = 0;
152 let mut min_area = <<T::Envelope as Envelope>::Point as Point>::Scalar::max_value();
153 let mut min_index = 0;
154 for (index, child) in node.children.iter().enumerate() {
155 let envelope = child.envelope();
156 if envelope.contains_envelope(&insertion_envelope) {
157 inclusion_count += 1;
158 let area = envelope.area();
159 if area < min_area {
160 min_area = area;
161 min_index = index;
162 }
163 }
164 }
165 if inclusion_count == 0 {
166 // No inclusion found, subtree depends on overlap and area increase
167 let mut min = (zero, zero, zero);
168
169 for (index, child1) in node.children.iter().enumerate() {
170 let envelope = child1.envelope();
171 let mut new_envelope = envelope;
172 new_envelope.merge(&insertion_envelope);
173 let overlap_increase = if all_leaves {
174 // Calculate minimal overlap increase
175 let mut overlap = zero;
176 let mut new_overlap = zero;
177 for child2 in &node.children {
178 if child1 as *const _ != child2 as *const _ {
179 let child_envelope = child2.envelope();
180 let temp1 = envelope.intersection_area(&child_envelope);
181 overlap = overlap + temp1;
182 let temp2 = new_envelope.intersection_area(&child_envelope);
183 new_overlap = new_overlap + temp2;
184 }
185 }
186 new_overlap - overlap
187 } else {
188 // Don't calculate overlap increase if not all children are leaves
189 zero
190 };
191 // Calculate area increase and area
192 let area = new_envelope.area();
193 let area_increase = area - envelope.area();
194 let new_min = (overlap_increase, area_increase, area);
195 if new_min < min || index == 0 {
196 min = new_min;
197 min_index = index;
198 }
199 }
200 }
201 min_index
202 }
203
204 // Does never return a request for reinsertion
resolve_overflow_without_reinsertion<T, Params>(node: &mut ParentNode<T>) -> InsertionResult<T> where T: RTreeObject, Params: RTreeParams,205 fn resolve_overflow_without_reinsertion<T, Params>(node: &mut ParentNode<T>) -> InsertionResult<T>
206 where
207 T: RTreeObject,
208 Params: RTreeParams,
209 {
210 if node.children.len() > Params::MAX_SIZE {
211 let off_split = split::<_, Params>(node);
212 InsertionResult::Split(off_split)
213 } else {
214 InsertionResult::Complete
215 }
216 }
217
resolve_overflow<T, Params>(node: &mut ParentNode<T>, current_depth: usize) -> InsertionResult<T> where T: RTreeObject, Params: RTreeParams,218 fn resolve_overflow<T, Params>(node: &mut ParentNode<T>, current_depth: usize) -> InsertionResult<T>
219 where
220 T: RTreeObject,
221 Params: RTreeParams,
222 {
223 if Params::REINSERTION_COUNT == 0 {
224 resolve_overflow_without_reinsertion::<_, Params>(node)
225 } else if node.children.len() > Params::MAX_SIZE {
226 let nodes_for_reinsertion = get_nodes_for_reinsertion::<_, Params>(node);
227 InsertionResult::Reinsert(nodes_for_reinsertion, current_depth)
228 } else {
229 InsertionResult::Complete
230 }
231 }
232
split<T, Params>(node: &mut ParentNode<T>) -> RTreeNode<T> where T: RTreeObject, Params: RTreeParams,233 fn split<T, Params>(node: &mut ParentNode<T>) -> RTreeNode<T>
234 where
235 T: RTreeObject,
236 Params: RTreeParams,
237 {
238 let axis = get_split_axis::<_, Params>(node);
239 let zero = <<T::Envelope as Envelope>::Point as Point>::Scalar::zero();
240 debug_assert!(node.children.len() >= 2);
241 // Sort along axis
242 T::Envelope::sort_envelopes(axis, &mut node.children);
243 let mut best = (zero, zero);
244 let min_size = Params::MIN_SIZE;
245 let mut best_index = min_size;
246
247 for k in min_size..=node.children.len() - min_size {
248 let mut first_envelope = node.children[k - 1].envelope();
249 let mut second_envelope = node.children[k].envelope();
250 let (l, r) = node.children.split_at(k);
251 for child in l {
252 first_envelope.merge(&child.envelope());
253 }
254 for child in r {
255 second_envelope.merge(&child.envelope());
256 }
257
258 let overlap_value = first_envelope.intersection_area(&second_envelope);
259 let area_value = first_envelope.area() + second_envelope.area();
260 let new_best = (overlap_value, area_value);
261 if new_best < best || k == min_size {
262 best = new_best;
263 best_index = k;
264 }
265 }
266 let off_split = node.children.split_off(best_index);
267 node.envelope = envelope_for_children(&node.children);
268 RTreeNode::Parent(ParentNode::new_parent(off_split))
269 }
270
get_split_axis<T, Params>(node: &mut ParentNode<T>) -> usize where T: RTreeObject, Params: RTreeParams,271 fn get_split_axis<T, Params>(node: &mut ParentNode<T>) -> usize
272 where
273 T: RTreeObject,
274 Params: RTreeParams,
275 {
276 let mut best_goodness = <<T::Envelope as Envelope>::Point as Point>::Scalar::max_value();
277 let mut best_axis = 0;
278 let min_size = Params::MIN_SIZE;
279 let until = node.children.len() - min_size + 1;
280 for axis in 0..<T::Envelope as Envelope>::Point::DIMENSIONS {
281 // Sort children along the current axis
282 T::Envelope::sort_envelopes(axis, &mut node.children);
283 let mut first_envelope = T::Envelope::new_empty();
284 let mut second_envelope = T::Envelope::new_empty();
285 for child in &node.children[..min_size] {
286 first_envelope.merge(&child.envelope());
287 }
288 for child in &node.children[until..] {
289 second_envelope.merge(&child.envelope());
290 }
291 for k in min_size..until {
292 let mut first_modified = first_envelope;
293 let mut second_modified = second_envelope;
294 let (l, r) = node.children.split_at(k);
295 for child in l {
296 first_modified.merge(&child.envelope());
297 }
298 for child in r {
299 second_modified.merge(&child.envelope());
300 }
301
302 let perimeter_value =
303 first_modified.perimeter_value() + second_modified.perimeter_value();
304 if best_goodness > perimeter_value {
305 best_axis = axis;
306 best_goodness = perimeter_value;
307 }
308 }
309 }
310 best_axis
311 }
312
get_nodes_for_reinsertion<T, Params>(node: &mut ParentNode<T>) -> Vec<RTreeNode<T>> where T: RTreeObject, Params: RTreeParams,313 fn get_nodes_for_reinsertion<T, Params>(node: &mut ParentNode<T>) -> Vec<RTreeNode<T>>
314 where
315 T: RTreeObject,
316 Params: RTreeParams,
317 {
318 let center = node.envelope.center();
319 // Sort with increasing order so we can use Vec::split_off
320 node.children.sort_by(|l, r| {
321 let l_center = l.envelope().center();
322 let r_center = r.envelope().center();
323 l_center
324 .sub(¢er)
325 .length_2()
326 .partial_cmp(&(r_center.sub(¢er)).length_2())
327 .unwrap()
328 });
329 let num_children = node.children.len();
330 let result = node
331 .children
332 .split_off(num_children - Params::REINSERTION_COUNT);
333 node.envelope = envelope_for_children(&node.children);
334 result
335 }
336