rstar/rtree.rs
1use crate::algorithm::nearest_neighbor;
2use crate::algorithm::nearest_neighbor::NearestNeighborDistance2Iterator;
3use crate::algorithm::nearest_neighbor::NearestNeighborIterator;
4use crate::algorithm::removal;
5use crate::algorithm::selection_functions::*;
6use crate::envelope::Envelope;
7use crate::node::ParentNode;
8use crate::object::{PointDistance, RTreeObject};
9use crate::params::{verify_parameters, DefaultParams, InsertionStrategy, RTreeParams};
10use crate::{algorithm::iterators::*, object::Distance};
11
12use crate::algorithm::bulk_load;
13use core::ops::ControlFlow;
14
15#[cfg(not(test))]
16use alloc::vec::Vec;
17
18#[cfg(feature = "serde")]
19use serde::{Deserialize, Serialize};
20
21impl<T, Params> Default for RTree<T, Params>
22where
23 T: RTreeObject,
24 Params: RTreeParams,
25{
26 fn default() -> Self {
27 Self::new_with_params()
28 }
29}
30
31/// An n-dimensional r-tree data structure.
32///
33/// # R-Trees
34/// R-Trees are data structures containing multi-dimensional objects like points, rectangles
35/// or polygons. They are optimized for retrieving the nearest neighbor at any point.
36///
37/// R-trees can efficiently find answers to queries like "Find the nearest point of a polygon",
38/// "Find all police stations within a rectangle" or "Find the 10 nearest restaurants, sorted
39/// by their distances". Compared to a naive implementation for these scenarios that runs
40/// in `O(n)` for `n` inserted elements, r-trees reduce this time to `O(log(n))`.
41///
42/// However, creating an r-tree is time consuming
43/// and runs in `O(n * log(n))`. Thus, r-trees are suited best if many queries and only few
44/// insertions are made. `rstar` also supports [bulk loading](RTree::bulk_load),
45/// which cuts down the constant factors when creating an r-tree significantly compared to
46/// sequential insertions.
47///
48/// R-trees are also _dynamic_: points can be inserted and removed from an existing tree.
49///
50/// ## Partitioning heuristics
51/// The inserted objects are internally partitioned into several boxes which should have small
52/// overlap and volume. This is done heuristically. While the originally proposed heuristic focused
53/// on fast insertion operations, the resulting r-trees were often suboptimally structured. Another
54/// heuristic, called `R*-tree` (r-star-tree), was proposed to improve the tree structure at the cost of
55/// longer insertion operations and is currently the crate's only implemented
56/// [InsertionStrategy].
57///
58/// # Usage
59/// The items inserted into an r-tree must implement the [RTreeObject]
60/// trait. To support nearest neighbor queries, implement the [PointDistance]
61/// trait. Some useful geometric primitives that implement the above traits can be found in the
62/// [crate::primitives] module. Several primitives in the [`geo-types`](https://docs.rs/geo-types/) crate also
63/// implement these traits.
64///
65/// ## Example
66/// ```
67/// use rstar::RTree;
68///
69/// let mut tree = RTree::new();
70/// tree.insert([0.1, 0.0f32]);
71/// tree.insert([0.2, 0.1]);
72/// tree.insert([0.3, 0.0]);
73///
74/// assert_eq!(tree.nearest_neighbor([0.4, -0.1]), Some(&[0.3, 0.0]));
75/// tree.remove(&[0.3, 0.0]);
76/// assert_eq!(tree.nearest_neighbor([0.4, 0.3]), Some(&[0.2, 0.1]));
77///
78/// assert_eq!(tree.size(), 2);
79/// // &RTree implements IntoIterator!
80/// for point in &tree {
81/// println!("Tree contains a point {:?}", point);
82/// }
83/// ```
84///
85/// ## Supported point types
86/// All types implementing the [Point] trait can be used as underlying point type.
87/// By default, fixed size arrays can be used as points.
88///
89/// # Associating Data with Geometries
90/// Users wishing to store associated data with geometries can use [crate::primitives::GeomWithData].
91///
92/// # Runtime and Performance
93/// The runtime of query operations (e.g. `nearest neighbor` or `contains`) is usually
94/// `O(log(n))`, where `n` refers to the number of elements contained in the r-tree.
95/// A naive sequential algorithm would take `O(n)` time. However, r-trees incur higher
96/// build up times: inserting an element into an r-tree costs `O(log(n))` time.
97///
98/// Most of the selection methods, meaning those with names beginning with `locate_`,
99/// return iterators which are driven externally and can therefore be combined into
100/// more complex pipelines using the combinators defined on the [`Iterator`] trait.
101///
102/// This flexiblity does come at the cost of temporary heap allocations required
103/// to keep track of the iteration state. Alternative methods using internal iteration
104/// are provided to avoid this overhead, their names ending in `_int` or `_int_mut`.
105///
106/// They use a callback-based interface to pass the selected objects on to the caller
107/// thereby being able to use the stack to keep track of the state required for
108/// traversing the tree.
109///
110/// # Tree Traversal
111/// For advanced use cases and debugging, the internal tree structure can be traversed
112/// using the [`root`](RTree::root) method. This provides access to the tree's hierarchical
113/// structure of parent nodes and leaf nodes.
114///
115/// The tree follows a hierarchical structure where:
116/// - The root is always a [`ParentNode`]
117/// - Each [`ParentNode`] contains children that can be either leaf nodes or more parent nodes
118/// - Leaf nodes contain the actual data items inserted into the tree
119///
120/// Common traversal patterns include:
121/// - **Top-down traversal**: Starting from the root and recursively visiting children
122/// - **Bottom-up processing**: Processing leaf nodes first, then aggregating results upward
123///
124/// See the [`root`](RTree::root) method documentation for a complete traversal example.
125///
126/// # Bulk loading
127/// In many scenarios, insertion is only carried out once for many points. In this case,
128/// [RTree::bulk_load] will be considerably faster. Its total run time
129/// is still `O(nlog(n))`, i.e. `O(log(n))` per element inserted, but the scaling
130/// factor is, on average, significantly improved compared with performing single
131/// insertion n times in a row. **Note the performance caveat
132/// related to the computation of the envelope**.
133///
134/// # Element distribution
135/// The tree's performance heavily relies on the spatial distribution of its elements.
136/// Best performance is achieved if:
137/// * No element is inserted more than once
138/// * The overlapping area of elements is as small as
139/// possible.
140///
141/// For the edge case that all elements are overlapping (e.g, one and the same element
142/// is contained `n` times), the performance of most operations usually degrades to `O(n)`.
143///
144/// # Type Parameters
145/// * `T`: The type of objects stored in the r-tree.
146/// * `Params`: Compile time parameters that change the r-tree's internal layout. Refer to the
147/// [RTreeParams] trait for more information.
148///
149/// # Defining methods generic over r-trees
150/// If a library defines a method that should be generic over the r-tree type signature, make
151/// sure to include both type parameters like this:
152/// ```
153/// # use rstar::{RTree,RTreeObject, RTreeParams};
154/// pub fn generic_rtree_function<T, Params>(tree: &mut RTree<T, Params>)
155/// where
156/// T: RTreeObject,
157/// Params: RTreeParams
158/// {
159/// // ...
160/// }
161/// ```
162/// Otherwise, any user of `generic_rtree_function` would be forced to use
163/// a tree with default parameters.
164///
165/// # (De)Serialization
166/// Enable the `serde` feature for [Serde](https://crates.io/crates/serde) support.
167///
168/// ## Further reading
169/// For more information refer to the [wikipedia article](https://en.wikipedia.org/wiki/R-tree).
170///
171#[derive(Clone)]
172#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
173#[cfg_attr(
174 feature = "serde",
175 serde(bound(
176 serialize = "T: Serialize, T::Envelope: Serialize",
177 deserialize = "T: Deserialize<'de>, T::Envelope: Deserialize<'de>"
178 ))
179)]
180pub struct RTree<T, Params = DefaultParams>
181where
182 Params: RTreeParams,
183 T: RTreeObject,
184{
185 root: ParentNode<T>,
186 size: usize,
187 _params: ::core::marker::PhantomData<Params>,
188}
189
190struct DebugHelper<'a, T, Params>
191where
192 T: RTreeObject + ::core::fmt::Debug + 'a,
193 Params: RTreeParams + 'a,
194{
195 rtree: &'a RTree<T, Params>,
196}
197
198impl<T, Params> ::core::fmt::Debug for DebugHelper<'_, T, Params>
199where
200 T: RTreeObject + ::core::fmt::Debug,
201 Params: RTreeParams,
202{
203 fn fmt(&self, formatter: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
204 formatter.debug_set().entries(self.rtree.iter()).finish()
205 }
206}
207
208impl<T, Params> ::core::fmt::Debug for RTree<T, Params>
209where
210 Params: RTreeParams,
211 T: RTreeObject + ::core::fmt::Debug,
212{
213 fn fmt(&self, formatter: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
214 formatter
215 .debug_struct("RTree")
216 .field("size", &self.size)
217 .field("items", &DebugHelper { rtree: self })
218 .finish()
219 }
220}
221
222impl<T> RTree<T>
223where
224 T: RTreeObject,
225{
226 /// Creates a new, empty r-tree.
227 ///
228 /// The created r-tree is configured with [default parameters](DefaultParams).
229 pub fn new() -> Self {
230 Self::new_with_params()
231 }
232
233 /// Creates a new r-tree with some elements already inserted.
234 ///
235 /// This method should be the preferred way for creating r-trees. It both
236 /// runs faster and yields an r-tree with better internal structure that
237 /// improves query performance.
238 ///
239 /// This method implements the overlap minimizing top-down bulk loading algorithm (OMT)
240 /// as described in [this paper by Lee and Lee (2003)](http://ceur-ws.org/Vol-74/files/FORUM_18.pdf).
241 ///
242 /// # Runtime
243 /// Bulk loading runs in `O(n * log(n))`, where `n` is the number of loaded
244 /// elements.
245 ///
246 /// # Note
247 /// The envelope of each element will be accessed many times during loading. If that computation
248 /// is expensive, **consider memoizing it** using [`CachedEnvelope`][crate::primitives::CachedEnvelope].
249 pub fn bulk_load(elements: Vec<T>) -> Self {
250 Self::bulk_load_with_params(elements)
251 }
252}
253
254impl<T, Params> RTree<T, Params>
255where
256 Params: RTreeParams,
257 T: RTreeObject,
258{
259 /// Creates a new, empty r-tree.
260 ///
261 /// The tree's compile time parameters must be specified. Refer to the
262 /// [RTreeParams] trait for more information and a usage example.
263 pub fn new_with_params() -> Self {
264 verify_parameters::<T, Params>();
265 RTree {
266 root: ParentNode::new_root::<Params>(),
267 size: 0,
268 _params: Default::default(),
269 }
270 }
271
272 /// Creates a new r-tree with some given elements and configurable parameters.
273 ///
274 /// For more information refer to [RTree::bulk_load]
275 /// and [RTreeParams].
276 pub fn bulk_load_with_params(elements: Vec<T>) -> Self {
277 Self::new_from_bulk_loading(elements, bulk_load::bulk_load_sequential::<_, Params>)
278 }
279
280 /// Returns the number of objects in an r-tree.
281 ///
282 /// # Example
283 /// ```
284 /// use rstar::RTree;
285 ///
286 /// let mut tree = RTree::new();
287 /// assert_eq!(tree.size(), 0);
288 /// tree.insert([0.0, 1.0, 2.0]);
289 /// assert_eq!(tree.size(), 1);
290 /// tree.remove(&[0.0, 1.0, 2.0]);
291 /// assert_eq!(tree.size(), 0);
292 /// ```
293 pub fn size(&self) -> usize {
294 self.size
295 }
296
297 pub(crate) fn size_mut(&mut self) -> &mut usize {
298 &mut self.size
299 }
300
301 /// Returns an iterator over all elements contained in the tree.
302 ///
303 /// The order in which the elements are returned is not specified.
304 ///
305 /// # Example
306 /// ```
307 /// use rstar::RTree;
308 /// let tree = RTree::bulk_load(vec![(0.0, 0.1), (0.3, 0.2), (0.4, 0.2)]);
309 /// for point in tree.iter() {
310 /// println!("This tree contains point {:?}", point);
311 /// }
312 /// ```
313 pub fn iter(&self) -> RTreeIterator<'_, T> {
314 RTreeIterator::new(&self.root, SelectAllFunc)
315 }
316
317 /// Returns an iterator over all mutable elements contained in the tree.
318 ///
319 /// The order in which the elements are returned is not specified.
320 ///
321 /// *Note*: It is a logic error to change an inserted item's position or dimensions. This
322 /// method is primarily meant for own implementations of [RTreeObject]
323 /// which can contain arbitrary additional data.
324 /// If the position or location of an inserted object need to change, you will need to [RTree::remove]
325 /// and reinsert it.
326 ///
327 pub fn iter_mut(&mut self) -> RTreeIteratorMut<'_, T> {
328 RTreeIteratorMut::new(&mut self.root, SelectAllFunc)
329 }
330
331 /// Returns all elements contained in an [Envelope].
332 ///
333 /// Usually, an envelope is an [axis aligned bounding box](crate::AABB). This
334 /// method can be used to retrieve all elements that are fully contained within an envelope.
335 ///
336 /// # Example
337 /// ```
338 /// use rstar::{RTree, AABB};
339 /// let mut tree = RTree::bulk_load(vec![
340 /// [0.0, 0.0],
341 /// [0.0, 1.0],
342 /// [1.0, 1.0]
343 /// ]);
344 /// let half_unit_square = AABB::from_corners([0.0, 0.0], [0.5, 1.0]);
345 /// let unit_square = AABB::from_corners([0.0, 0.0], [1.0, 1.0]);
346 /// let elements_in_half_unit_square = tree.locate_in_envelope(half_unit_square);
347 /// let elements_in_unit_square = tree.locate_in_envelope(unit_square);
348 /// assert_eq!(elements_in_half_unit_square.count(), 2);
349 /// assert_eq!(elements_in_unit_square.count(), 3);
350 /// ```
351 pub fn locate_in_envelope(&self, envelope: T::Envelope) -> LocateInEnvelope<'_, T> {
352 LocateInEnvelope::new(&self.root, SelectInEnvelopeFunction::new(envelope))
353 }
354
355 /// Mutable variant of [locate_in_envelope](#method.locate_in_envelope).
356 pub fn locate_in_envelope_mut(&mut self, envelope: T::Envelope) -> LocateInEnvelopeMut<'_, T> {
357 LocateInEnvelopeMut::new(&mut self.root, SelectInEnvelopeFunction::new(envelope))
358 }
359
360 /// Variant of [`locate_in_envelope`][Self::locate_in_envelope] using internal iteration.
361 pub fn locate_in_envelope_int<'a, V, B>(
362 &'a self,
363 envelope: T::Envelope,
364 mut visitor: V,
365 ) -> ControlFlow<B>
366 where
367 V: FnMut(&'a T) -> ControlFlow<B>,
368 {
369 select_nodes(
370 self.root(),
371 &SelectInEnvelopeFunction::new(envelope),
372 &mut visitor,
373 )
374 }
375
376 /// Mutable variant of [`locate_in_envelope_mut`][Self::locate_in_envelope_mut].
377 pub fn locate_in_envelope_int_mut<'a, V, B>(
378 &'a mut self,
379 envelope: T::Envelope,
380 mut visitor: V,
381 ) -> ControlFlow<B>
382 where
383 V: FnMut(&'a mut T) -> ControlFlow<B>,
384 {
385 select_nodes_mut(
386 self.root_mut(),
387 &SelectInEnvelopeFunction::new(envelope),
388 &mut visitor,
389 )
390 }
391
392 /// Returns a draining iterator over all elements contained in the tree.
393 ///
394 /// The order in which the elements are returned is not specified.
395 ///
396 /// See
397 /// [drain_with_selection_function](#method.drain_with_selection_function)
398 /// for more information.
399 pub fn drain(&mut self) -> DrainIterator<'_, T, SelectAllFunc, Params> {
400 self.drain_with_selection_function(SelectAllFunc)
401 }
402
403 /// Draining variant of [locate_in_envelope](#method.locate_in_envelope).
404 pub fn drain_in_envelope(
405 &mut self,
406 envelope: T::Envelope,
407 ) -> DrainIterator<'_, T, SelectInEnvelopeFunction<T>, Params> {
408 let sel = SelectInEnvelopeFunction::new(envelope);
409 self.drain_with_selection_function(sel)
410 }
411
412 /// Returns all elements whose envelope intersects a given envelope.
413 ///
414 /// Any element fully contained within an envelope is also returned by this method. Two
415 /// envelopes that "touch" each other (e.g. by sharing only a common corner) are also
416 /// considered to intersect. Usually, an envelope is an [axis aligned bounding box](crate::AABB).
417 /// This method will return all elements whose AABB has some common area with
418 /// a given AABB.
419 ///
420 /// # Example
421 /// ```
422 /// use rstar::{RTree, AABB};
423 /// use rstar::primitives::Rectangle;
424 ///
425 /// let left_piece = AABB::from_corners([0.0, 0.0], [0.4, 1.0]);
426 /// let right_piece = AABB::from_corners([0.6, 0.0], [1.0, 1.0]);
427 /// let middle_piece = AABB::from_corners([0.25, 0.0], [0.75, 1.0]);
428 ///
429 /// let mut tree = RTree::<Rectangle<_>>::bulk_load(vec![
430 /// left_piece.into(),
431 /// right_piece.into(),
432 /// middle_piece.into(),
433 /// ]);
434 ///
435 /// let elements_intersecting_left_piece = tree.locate_in_envelope_intersecting(left_piece);
436 /// // The left piece should not intersect the right piece!
437 /// assert_eq!(elements_intersecting_left_piece.count(), 2);
438 /// let elements_intersecting_middle = tree.locate_in_envelope_intersecting(middle_piece);
439 /// // Only the middle piece intersects all pieces within the tree
440 /// assert_eq!(elements_intersecting_middle.count(), 3);
441 ///
442 /// let large_piece = AABB::from_corners([-100., -100.], [100., 100.]);
443 /// let elements_intersecting_large_piece = tree.locate_in_envelope_intersecting(large_piece);
444 /// // Any element that is fully contained should also be returned:
445 /// assert_eq!(elements_intersecting_large_piece.count(), 3);
446 /// ```
447 pub fn locate_in_envelope_intersecting(
448 &self,
449 envelope: T::Envelope,
450 ) -> LocateInEnvelopeIntersecting<'_, T> {
451 LocateInEnvelopeIntersecting::new(
452 &self.root,
453 SelectInEnvelopeFuncIntersecting::new(envelope),
454 )
455 }
456
457 /// Mutable variant of [locate_in_envelope_intersecting](#method.locate_in_envelope_intersecting)
458 pub fn locate_in_envelope_intersecting_mut(
459 &mut self,
460 envelope: T::Envelope,
461 ) -> LocateInEnvelopeIntersectingMut<'_, T> {
462 LocateInEnvelopeIntersectingMut::new(
463 &mut self.root,
464 SelectInEnvelopeFuncIntersecting::new(envelope),
465 )
466 }
467
468 /// Variant of [`locate_in_envelope_intersecting`][Self::locate_in_envelope_intersecting] using internal iteration.
469 pub fn locate_in_envelope_intersecting_int<'a, V, B>(
470 &'a self,
471 envelope: T::Envelope,
472 mut visitor: V,
473 ) -> ControlFlow<B>
474 where
475 V: FnMut(&'a T) -> ControlFlow<B>,
476 {
477 select_nodes(
478 self.root(),
479 &SelectInEnvelopeFuncIntersecting::new(envelope),
480 &mut visitor,
481 )
482 }
483
484 /// Mutable variant of [`locate_in_envelope_intersecting_int`][Self::locate_in_envelope_intersecting_int].
485 pub fn locate_in_envelope_intersecting_int_mut<'a, V, B>(
486 &'a mut self,
487 envelope: T::Envelope,
488 mut visitor: V,
489 ) -> ControlFlow<B>
490 where
491 V: FnMut(&'a mut T) -> ControlFlow<B>,
492 {
493 select_nodes_mut(
494 self.root_mut(),
495 &SelectInEnvelopeFuncIntersecting::new(envelope),
496 &mut visitor,
497 )
498 }
499
500 /// Locates elements in the r-tree defined by a selection function.
501 ///
502 /// Refer to the documentation of [`SelectionFunction`] for
503 /// more information.
504 ///
505 /// Usually, other `locate` methods should cover most common use cases. This method is only required
506 /// in more specific situations.
507 pub fn locate_with_selection_function<S: SelectionFunction<T>>(
508 &self,
509 selection_function: S,
510 ) -> SelectionIterator<'_, T, S> {
511 SelectionIterator::new(&self.root, selection_function)
512 }
513
514 /// Mutable variant of [`locate_with_selection_function`](#method.locate_with_selection_function).
515 pub fn locate_with_selection_function_mut<S: SelectionFunction<T>>(
516 &mut self,
517 selection_function: S,
518 ) -> SelectionIteratorMut<'_, T, S> {
519 SelectionIteratorMut::new(&mut self.root, selection_function)
520 }
521
522 /// Returns all possible intersecting objects of this and another tree.
523 ///
524 /// This will return all objects whose _envelopes_ intersect. No geometric intersection
525 /// checking is performed.
526 pub fn intersection_candidates_with_other_tree<'a, U>(
527 &'a self,
528 other: &'a RTree<U>,
529 ) -> IntersectionIterator<'a, T, U>
530 where
531 U: RTreeObject<Envelope = T::Envelope>,
532 {
533 IntersectionIterator::new(self.root(), other.root())
534 }
535
536 /// Returns the tree's root node.
537 ///
538 /// For some algorithms and use cases, knowledge of the tree's internal structure may be required.
539 /// For these cases, this method serves as an entry point, allowing flexible iteration and
540 /// aggregation strategies. The examples below demonstrate two different traversal
541 /// approaches: top-down (pre-order: process parent then children) and bottom-up (post-order:
542 /// process children then parent). Post-order is essential when parent values depend on
543 /// already-computed child values, such as recomputing envelopes from child data.
544 ///
545 /// # Examples
546 ///
547 /// ```
548 /// use rstar::{RTree, RTreeNode, ParentNode};
549 /// use rstar::primitives::GeomWithData;
550 ///
551 /// type PointWithLabel = GeomWithData<[f32; 2], String>;
552 ///
553 /// // Top-down traversal: Start from root, recurse down to leaves
554 /// fn paths_top_down(tree: &RTree<PointWithLabel>) -> Vec<String> {
555 /// let mut node_counter = 0;
556 ///
557 /// fn traverse(
558 /// parent: &ParentNode<PointWithLabel>,
559 /// path: String,
560 /// paths: &mut Vec<String>,
561 /// node_counter: &mut usize
562 /// ) {
563 /// for child in parent.children() {
564 /// *node_counter += 1;
565 /// let child_path = if path.is_empty() {
566 /// format!("Node{}", *node_counter)
567 /// } else {
568 /// format!("{} -> Node{}", path, *node_counter)
569 /// };
570 ///
571 /// match child {
572 /// RTreeNode::Leaf(item) => {
573 /// // Record the complete path to this leaf
574 /// paths.push(format!("{} -> Leaf({})", child_path, item.data));
575 /// }
576 /// RTreeNode::Parent(child_parent) => {
577 /// // Continue building the path downward
578 /// traverse(child_parent, child_path, paths, node_counter);
579 /// }
580 /// }
581 /// }
582 /// }
583 ///
584 /// let mut paths = Vec::new();
585 /// traverse(tree.root(), "Node0".to_string(), &mut paths, &mut node_counter);
586 /// paths
587 /// }
588 ///
589 /// // Bottom-up traversal: Aggregate child envelopes into parents (post-order)
590 /// // NB: this is a contrived example showing manual envelope aggregation
591 /// fn aggregate_envelopes_bottom_up(tree: &RTree<PointWithLabel>) -> Vec<(String, f32, f32)> {
592 /// use rstar::{Envelope, AABB, RTreeObject};
593 /// let mut results = Vec::new();
594 ///
595 /// // Returns the envelope computed from this node's children
596 /// fn visit_bottom_up(
597 /// node: &RTreeNode<PointWithLabel>,
598 /// results: &mut Vec<(String, f32, f32)>
599 /// ) -> AABB<[f32; 2]> {
600 /// match node {
601 /// RTreeNode::Leaf(item) => {
602 /// // Leaf envelope is just the item's point
603 /// let env = item.envelope();
604 /// let lower = env.lower();
605 /// let upper = env.upper();
606 /// results.push((format!("Leaf({})", item.data), lower[0], upper[0]));
607 /// env
608 /// }
609 /// RTreeNode::Parent(parent) => {
610 /// // Compute this parent's envelope as union of children's envelopes
611 /// let mut parent_env = AABB::new_empty();
612 ///
613 /// // Merge all children's envelopes
614 /// for child in parent.children() {
615 /// let child_env = visit_bottom_up(child, results);
616 /// parent_env.merge(&child_env);
617 /// }
618 ///
619 /// let lower = parent_env.lower();
620 /// let upper = parent_env.upper();
621 /// results.push((String::from("Parent"), lower[0], upper[0]));
622 ///
623 /// parent_env
624 /// }
625 /// }
626 /// }
627 ///
628 /// // Start traversal from root wrapped as RTreeNode
629 /// let root_node = RTreeNode::Parent(tree.root().clone());
630 /// visit_bottom_up(&root_node, &mut results);
631 ///
632 /// results
633 /// }
634 ///
635 /// // Create a tree with 8 points
636 /// let mut tree = RTree::new();
637 /// for i in 0..8 {
638 /// let point = [i as f32, 0.0];
639 /// let label = format!("L{}", i);
640 /// tree.insert(PointWithLabel::new(point, label));
641 /// }
642 ///
643 /// let paths_down = paths_top_down(&tree);
644 /// let envelopes = aggregate_envelopes_bottom_up(&tree);
645 ///
646 /// // Top-down traversal visits all 8 leaves
647 /// assert_eq!(paths_down.len(), 8);
648 ///
649 /// // Verify all leaves are present in top-down traversal
650 /// for i in 0..8 {
651 /// let leaf_pattern = format!("Leaf(L{})", i);
652 /// assert!(paths_down.iter().any(|p| p.contains(&leaf_pattern)));
653 /// }
654 ///
655 /// // Top-down paths start from root
656 /// assert!(paths_down[0].starts_with("Node0"));
657 ///
658 /// // Bottom-up traversal processes leaves first, then parents
659 /// // Verify all 8 leaves are present with their x-coordinates
660 /// let leaves: Vec<_> = envelopes.iter()
661 /// .filter(|(name, _, _)| name.starts_with("Leaf"))
662 /// .collect();
663 /// assert_eq!(leaves.len(), 8);
664 ///
665 /// // The last element is the root parent with envelope containing all points
666 /// let (_, min_x, max_x) = envelopes.last().unwrap();
667 /// assert_eq!(*min_x, 0.0); // Root envelope spans from 0.0 (leftmost point)
668 /// assert_eq!(*max_x, 7.0); // to 7.0 (rightmost point)
669 /// ```
670 pub fn root(&self) -> &ParentNode<T> {
671 &self.root
672 }
673
674 pub(crate) fn root_mut(&mut self) -> &mut ParentNode<T> {
675 &mut self.root
676 }
677
678 fn new_from_bulk_loading(
679 elements: Vec<T>,
680 root_loader: impl Fn(Vec<T>) -> ParentNode<T>,
681 ) -> Self {
682 verify_parameters::<T, Params>();
683 let size = elements.len();
684 let root = if size == 0 {
685 ParentNode::new_root::<Params>()
686 } else {
687 root_loader(elements)
688 };
689 RTree {
690 root,
691 size,
692 _params: Default::default(),
693 }
694 }
695
696 /// Removes and returns a single element from the tree. The element to remove is specified
697 /// by a [`SelectionFunction`].
698 ///
699 /// See also: [`RTree::remove`], [`RTree::remove_at_point`]
700 ///
701 pub fn remove_with_selection_function<F>(&mut self, function: F) -> Option<T>
702 where
703 F: SelectionFunction<T>,
704 {
705 removal::DrainIterator::new(self, function).take(1).last()
706 }
707
708 /// Drain elements selected by a [`SelectionFunction`]. Returns an
709 /// iterator that successively removes selected elements and returns
710 /// them. This is the most generic drain API, see also:
711 /// [`RTree::drain_in_envelope_intersecting`],
712 /// [`RTree::drain_within_distance`].
713 ///
714 /// # Remarks
715 ///
716 /// This API is similar to `Vec::drain_filter`, but stopping the
717 /// iteration would stop the removal. However, the returned iterator
718 /// must be properly dropped. Leaking this iterator leads to a leak
719 /// amplification, where all the elements in the tree are leaked.
720 pub fn drain_with_selection_function<F>(
721 &mut self,
722 function: F,
723 ) -> DrainIterator<'_, T, F, Params>
724 where
725 F: SelectionFunction<T>,
726 {
727 removal::DrainIterator::new(self, function)
728 }
729
730 /// Drains elements intersecting the `envelope`. Similar to
731 /// `locate_in_envelope_intersecting`, except the elements are removed
732 /// and returned via an iterator.
733 pub fn drain_in_envelope_intersecting(
734 &mut self,
735 envelope: T::Envelope,
736 ) -> DrainIterator<'_, T, SelectInEnvelopeFuncIntersecting<T>, Params> {
737 let selection_function = SelectInEnvelopeFuncIntersecting::new(envelope);
738 self.drain_with_selection_function(selection_function)
739 }
740}
741
742impl<T, Params> RTree<T, Params>
743where
744 Params: RTreeParams,
745 T: PointDistance,
746{
747 /// Returns a single object that covers a given point.
748 ///
749 /// Method [contains_point](PointDistance::contains_point)
750 /// is used to determine if a tree element contains the given point.
751 ///
752 /// If multiple elements contain the given point, any of them is returned.
753 pub fn locate_at_point(&self, point: <T::Envelope as Envelope>::Point) -> Option<&T> {
754 self.locate_all_at_point(point).next()
755 }
756
757 /// Mutable variant of [RTree::locate_at_point].
758 pub fn locate_at_point_mut(
759 &mut self,
760 point: <T::Envelope as Envelope>::Point,
761 ) -> Option<&mut T> {
762 self.locate_all_at_point_mut(point).next()
763 }
764
765 /// Variant of [`locate_at_point`][Self::locate_at_point] using internal iteration.
766 pub fn locate_at_point_int(&self, point: <T::Envelope as Envelope>::Point) -> Option<&T> {
767 match self.locate_all_at_point_int(point, ControlFlow::Break) {
768 ControlFlow::Break(node) => Some(node),
769 ControlFlow::Continue(()) => None,
770 }
771 }
772
773 /// Mutable variant of [`locate_at_point_int`][Self::locate_at_point_int].
774 pub fn locate_at_point_int_mut(
775 &mut self,
776 point: <T::Envelope as Envelope>::Point,
777 ) -> Option<&mut T> {
778 match self.locate_all_at_point_int_mut(point, ControlFlow::Break) {
779 ControlFlow::Break(node) => Some(node),
780 ControlFlow::Continue(()) => None,
781 }
782 }
783
784 /// Locate all elements containing a given point.
785 ///
786 /// Method [PointDistance::contains_point] is used
787 /// to determine if a tree element contains the given point.
788 /// # Example
789 /// ```
790 /// use rstar::RTree;
791 /// use rstar::primitives::Rectangle;
792 ///
793 /// let tree = RTree::bulk_load(vec![
794 /// Rectangle::from_corners([0.0, 0.0], [2.0, 2.0]),
795 /// Rectangle::from_corners([1.0, 1.0], [3.0, 3.0])
796 /// ]);
797 ///
798 /// assert_eq!(tree.locate_all_at_point([1.5, 1.5]).count(), 2);
799 /// assert_eq!(tree.locate_all_at_point([0.0, 0.0]).count(), 1);
800 /// assert_eq!(tree.locate_all_at_point([-1., 0.0]).count(), 0);
801 /// ```
802 pub fn locate_all_at_point(
803 &self,
804 point: <T::Envelope as Envelope>::Point,
805 ) -> LocateAllAtPoint<'_, T> {
806 LocateAllAtPoint::new(&self.root, SelectAtPointFunction::new(point))
807 }
808
809 /// Mutable variant of [`locate_all_at_point`][Self::locate_all_at_point].
810 pub fn locate_all_at_point_mut(
811 &mut self,
812 point: <T::Envelope as Envelope>::Point,
813 ) -> LocateAllAtPointMut<'_, T> {
814 LocateAllAtPointMut::new(&mut self.root, SelectAtPointFunction::new(point))
815 }
816
817 /// Variant of [`locate_all_at_point`][Self::locate_all_at_point] using internal iteration.
818 pub fn locate_all_at_point_int<'a, V, B>(
819 &'a self,
820 point: <T::Envelope as Envelope>::Point,
821 mut visitor: V,
822 ) -> ControlFlow<B>
823 where
824 V: FnMut(&'a T) -> ControlFlow<B>,
825 {
826 select_nodes(&self.root, &SelectAtPointFunction::new(point), &mut visitor)
827 }
828
829 /// Mutable variant of [`locate_all_at_point_int`][Self::locate_all_at_point_int].
830 pub fn locate_all_at_point_int_mut<'a, V, B>(
831 &'a mut self,
832 point: <T::Envelope as Envelope>::Point,
833 mut visitor: V,
834 ) -> ControlFlow<B>
835 where
836 V: FnMut(&'a mut T) -> ControlFlow<B>,
837 {
838 select_nodes_mut(
839 &mut self.root,
840 &SelectAtPointFunction::new(point),
841 &mut visitor,
842 )
843 }
844
845 /// Removes an element containing a given point.
846 ///
847 /// The removed element, if any, is returned. If multiple elements cover the given point,
848 /// only one of them is removed and returned.
849 ///
850 /// # Example
851 /// ```
852 /// use rstar::RTree;
853 /// use rstar::primitives::Rectangle;
854 ///
855 /// let mut tree = RTree::bulk_load(vec![
856 /// Rectangle::from_corners([0.0, 0.0], [2.0, 2.0]),
857 /// Rectangle::from_corners([1.0, 1.0], [3.0, 3.0])
858 /// ]);
859 ///
860 /// assert!(tree.remove_at_point([1.5, 1.5]).is_some());
861 /// assert!(tree.remove_at_point([1.5, 1.5]).is_some());
862 /// assert!(tree.remove_at_point([1.5, 1.5]).is_none());
863 ///```
864 pub fn remove_at_point(&mut self, point: <T::Envelope as Envelope>::Point) -> Option<T> {
865 let removal_function = SelectAtPointFunction::new(point);
866 self.remove_with_selection_function(removal_function)
867 }
868}
869
870impl<T, Params> RTree<T, Params>
871where
872 Params: RTreeParams,
873 T: RTreeObject + PartialEq,
874{
875 /// Returns `true` if a given element is equal (`==`) to an element in the
876 /// r-tree.
877 ///
878 /// This method will only work correctly if two equal elements also have the
879 /// same envelope.
880 ///
881 /// # Example
882 /// ```
883 /// use rstar::RTree;
884 ///
885 /// let mut tree = RTree::new();
886 /// assert!(!tree.contains(&[0.0, 2.0]));
887 /// tree.insert([0.0, 2.0]);
888 /// assert!(tree.contains(&[0.0, 2.0]));
889 /// ```
890 pub fn contains(&self, t: &T) -> bool {
891 self.locate_in_envelope(t.envelope()).any(|e| e == t)
892 }
893
894 /// Removes and returns an element of the r-tree equal (`==`) to a given element.
895 ///
896 /// If multiple elements equal to the given elements are contained in the tree, only
897 /// one of them is removed and returned.
898 ///
899 /// This method will only work correctly if two equal elements also have the
900 /// same envelope.
901 ///
902 /// # Example
903 /// ```
904 /// use rstar::RTree;
905 ///
906 /// let mut tree = RTree::new();
907 /// tree.insert([0.0, 2.0]);
908 /// // The element can be inserted twice just fine
909 /// tree.insert([0.0, 2.0]);
910 /// assert!(tree.remove(&[0.0, 2.0]).is_some());
911 /// assert!(tree.remove(&[0.0, 2.0]).is_some());
912 /// assert!(tree.remove(&[0.0, 2.0]).is_none());
913 /// ```
914 pub fn remove(&mut self, t: &T) -> Option<T> {
915 let removal_function = SelectEqualsFunction::new(t);
916 self.remove_with_selection_function(removal_function)
917 }
918}
919
920impl<T, Params> RTree<T, Params>
921where
922 Params: RTreeParams,
923 T: PointDistance,
924{
925 /// Returns the nearest neighbor for a given point.
926 ///
927 /// The distance is calculated by calling
928 /// [PointDistance::distance_2]
929 ///
930 /// # Example
931 /// ```
932 /// use rstar::RTree;
933 /// let tree = RTree::bulk_load(vec![
934 /// [0.0, 0.0],
935 /// [0.0, 1.0],
936 /// ]);
937 /// assert_eq!(tree.nearest_neighbor([-1., 0.0]), Some(&[0.0, 0.0]));
938 /// assert_eq!(tree.nearest_neighbor([0.0, 2.0]), Some(&[0.0, 1.0]));
939 /// ```
940 pub fn nearest_neighbor(&self, query_point: <T::Envelope as Envelope>::Point) -> Option<&T> {
941 self.nearest_neighbor_with_distance_2(query_point)
942 .map(|(neighbor, _)| neighbor)
943 }
944
945 /// Returns the nearest neighbor for a given point with distance squared.
946 ///
947 /// The distance is calculated by calling
948 /// [PointDistance::distance_2]
949 ///
950 /// # Example
951 /// ```
952 /// use rstar::RTree;
953 /// let tree = RTree::bulk_load(vec![
954 /// [0.0, 0.0],
955 /// [0.0, 1.0],
956 /// ]);
957 /// assert_eq!(tree.nearest_neighbor_with_distance_2([-1., 0.0]), Some((&[0.0, 0.0], 1.0)));
958 /// assert_eq!(tree.nearest_neighbor_with_distance_2([0.0, 2.0]), Some((&[0.0, 1.0], 1.0)));
959 /// ```
960 pub fn nearest_neighbor_with_distance_2(
961 &self,
962 query_point: <T::Envelope as Envelope>::Point,
963 ) -> Option<(&T, Distance<T>)> {
964 if self.size > 0 {
965 // The single-nearest-neighbor retrieval may in rare cases return None due to
966 // rounding issues. The iterator will still work, though.
967 nearest_neighbor::nearest_neighbor_with_distance_2(&self.root, query_point.clone())
968 .or_else(|| {
969 self.nearest_neighbor_iter_with_distance_2(query_point)
970 .next()
971 })
972 } else {
973 None
974 }
975 }
976
977 /// Returns the nearest neighbors for a given point.
978 ///
979 /// The distance is calculated by calling
980 /// [PointDistance::distance_2]
981 ///
982 /// All returned values will have the exact same distance from the given query point.
983 /// Returns an empty `Vec` if the tree is empty.
984 ///
985 /// # Example
986 /// ```
987 /// use rstar::RTree;
988 /// let tree = RTree::bulk_load(vec![
989 /// [0.0, 0.0],
990 /// [0.0, 1.0],
991 /// [1.0, 0.0],
992 /// ]);
993 ///
994 /// // A single nearest neighbor
995 /// assert_eq!(tree.nearest_neighbors(&[0.01, 0.01]), &[&[0.0, 0.0]]);
996 ///
997 /// // Two nearest neighbors
998 /// let nearest_two = tree.nearest_neighbors(&[1.0, 1.0]);
999 /// assert_eq!(nearest_two.len(), 2);
1000 /// assert!(nearest_two.contains(&&[0.0, 1.0]));
1001 /// assert!(nearest_two.contains(&&[1.0, 0.0]));
1002 /// ```
1003 pub fn nearest_neighbors(&self, query_point: &<T::Envelope as Envelope>::Point) -> Vec<&T> {
1004 self.nearest_neighbors_with_distance_2(query_point)
1005 .map(|(neighbors, _)| neighbors)
1006 .unwrap_or_default()
1007 }
1008
1009 /// Returns the nearest neighbors for a given point with distance squared.
1010 ///
1011 /// The distance is calculated by calling
1012 /// [PointDistance::distance_2]
1013 ///
1014 /// All returned values will have the exact same distance from the given query point.
1015 /// Returns an empty `None` if the tree is empty.
1016 ///
1017 /// # Example
1018 /// ```
1019 /// use rstar::RTree;
1020 /// let tree = RTree::bulk_load(vec![
1021 /// [0.0, 0.0],
1022 /// [0.0, 1.0],
1023 /// [1.0, 0.0],
1024 /// ]);
1025 ///
1026 /// // A single nearest neighbor
1027 /// assert_eq!(tree.nearest_neighbors_with_distance_2(&[0.01, 0.01]), Some((vec![&[0.0, 0.0]], 0.0002)));
1028 ///
1029 /// // Two nearest neighbors
1030 /// let nearest_two = tree.nearest_neighbors_with_distance_2(&[1.0, 1.0]);
1031 /// assert!(nearest_two.is_some());
1032 ///
1033 /// let (neighbors, dist_2) = nearest_two.unwrap();
1034 /// assert_eq!(neighbors.len(), 2);
1035 /// assert!(neighbors.contains(&&[0.0, 1.0]));
1036 /// assert!(neighbors.contains(&&[1.0, 0.0]));
1037 /// ```
1038 pub fn nearest_neighbors_with_distance_2(
1039 &self,
1040 query_point: &<T::Envelope as Envelope>::Point,
1041 ) -> Option<(Vec<&T>, Distance<T>)> {
1042 nearest_neighbor::nearest_neighbors_with_distance_2(&self.root, query_point.clone())
1043 }
1044
1045 /// Returns all elements of the tree within a certain distance.
1046 ///
1047 /// The elements may be returned in any order. Each returned element
1048 /// will have a squared distance less or equal to the given squared distance.
1049 ///
1050 /// This method makes use of [PointDistance::distance_2_if_less_or_equal].
1051 /// If performance is critical and the distance calculation to the object is fast,
1052 /// overwriting this function may be beneficial.
1053 pub fn locate_within_distance(
1054 &self,
1055 query_point: <T::Envelope as Envelope>::Point,
1056 max_squared_radius: Distance<T>,
1057 ) -> LocateWithinDistanceIterator<'_, T> {
1058 let selection_function = SelectWithinDistanceFunction::new(query_point, max_squared_radius);
1059 LocateWithinDistanceIterator::new(self.root(), selection_function)
1060 }
1061
1062 /// Drain all elements of the tree within a certain distance.
1063 ///
1064 /// Similar to [`RTree::locate_within_distance`], but removes and
1065 /// returns the elements via an iterator.
1066 pub fn drain_within_distance(
1067 &mut self,
1068 query_point: <T::Envelope as Envelope>::Point,
1069 max_squared_radius: Distance<T>,
1070 ) -> DrainIterator<'_, T, SelectWithinDistanceFunction<T>, Params> {
1071 let selection_function = SelectWithinDistanceFunction::new(query_point, max_squared_radius);
1072 self.drain_with_selection_function(selection_function)
1073 }
1074
1075 /// Returns all elements of the tree sorted by their distance to a given point.
1076 ///
1077 /// # Runtime
1078 /// Every `next()` call runs in `O(log(n))`. Creating the iterator runs in
1079 /// `O(log(n))`.
1080 /// The [r-tree documentation](RTree) contains more information about
1081 /// r-tree performance.
1082 ///
1083 /// # Example
1084 /// ```
1085 /// use rstar::RTree;
1086 /// let tree = RTree::bulk_load(vec![
1087 /// [0.0, 0.0],
1088 /// [0.0, 1.0],
1089 /// ]);
1090 ///
1091 /// let nearest_neighbors = tree.nearest_neighbor_iter([0.5, 0.0]).collect::<Vec<_>>();
1092 /// assert_eq!(nearest_neighbors, vec![&[0.0, 0.0], &[0.0, 1.0]]);
1093 /// ```
1094 pub fn nearest_neighbor_iter(
1095 &self,
1096 query_point: <T::Envelope as Envelope>::Point,
1097 ) -> NearestNeighborIterator<'_, T> {
1098 nearest_neighbor::NearestNeighborIterator::new(&self.root, query_point)
1099 }
1100
1101 /// Returns `(element, distance^2)` tuples of the tree sorted by their distance to a given point.
1102 ///
1103 /// The distance is calculated by calling
1104 /// [PointDistance::distance_2].
1105 #[deprecated(note = "Please use nearest_neighbor_iter_with_distance_2 instead")]
1106 pub fn nearest_neighbor_iter_with_distance(
1107 &self,
1108 query_point: <T::Envelope as Envelope>::Point,
1109 ) -> NearestNeighborDistance2Iterator<'_, T> {
1110 nearest_neighbor::NearestNeighborDistance2Iterator::new(&self.root, query_point)
1111 }
1112
1113 /// Returns `(element, distance^2)` tuples of the tree sorted by their distance to a given point.
1114 ///
1115 /// The distance is calculated by calling
1116 /// [PointDistance::distance_2].
1117 pub fn nearest_neighbor_iter_with_distance_2(
1118 &self,
1119 query_point: <T::Envelope as Envelope>::Point,
1120 ) -> NearestNeighborDistance2Iterator<'_, T> {
1121 nearest_neighbor::NearestNeighborDistance2Iterator::new(&self.root, query_point)
1122 }
1123
1124 /// Removes the nearest neighbor for a given point and returns it.
1125 ///
1126 /// The distance is calculated by calling
1127 /// [PointDistance::distance_2].
1128 ///
1129 /// # Example
1130 /// ```
1131 /// use rstar::RTree;
1132 /// let mut tree = RTree::bulk_load(vec![
1133 /// [0.0, 0.0],
1134 /// [0.0, 1.0],
1135 /// ]);
1136 /// assert_eq!(tree.pop_nearest_neighbor([0.0, 0.0]), Some([0.0, 0.0]));
1137 /// assert_eq!(tree.pop_nearest_neighbor([0.0, 0.0]), Some([0.0, 1.0]));
1138 /// assert_eq!(tree.pop_nearest_neighbor([0.0, 0.0]), None);
1139 /// ```
1140 pub fn pop_nearest_neighbor(
1141 &mut self,
1142 query_point: <T::Envelope as Envelope>::Point,
1143 ) -> Option<T> {
1144 if let Some(neighbor) = self.nearest_neighbor(query_point) {
1145 let removal_function = SelectByAddressFunction::new(neighbor.envelope(), neighbor);
1146 self.remove_with_selection_function(removal_function)
1147 } else {
1148 None
1149 }
1150 }
1151}
1152
1153impl<T, Params> RTree<T, Params>
1154where
1155 T: RTreeObject,
1156 Params: RTreeParams,
1157{
1158 /// Inserts a new element into the r-tree.
1159 ///
1160 /// If the element is already present in the tree, it will now be present twice.
1161 ///
1162 /// # Runtime
1163 /// This method runs in `O(log(n))`.
1164 /// The [r-tree documentation](RTree) contains more information about
1165 /// r-tree performance.
1166 pub fn insert(&mut self, t: T) {
1167 Params::DefaultInsertionStrategy::insert(self, t);
1168 self.size += 1;
1169 }
1170}
1171
1172impl<T, Params> IntoIterator for RTree<T, Params>
1173where
1174 T: RTreeObject,
1175 Params: RTreeParams,
1176{
1177 type IntoIter = IntoIter<T>;
1178 type Item = T;
1179
1180 fn into_iter(self) -> Self::IntoIter {
1181 IntoIter::new(self.root)
1182 }
1183}
1184
1185impl<'a, T, Params> IntoIterator for &'a RTree<T, Params>
1186where
1187 T: RTreeObject,
1188 Params: RTreeParams,
1189{
1190 type IntoIter = RTreeIterator<'a, T>;
1191 type Item = &'a T;
1192
1193 fn into_iter(self) -> Self::IntoIter {
1194 self.iter()
1195 }
1196}
1197
1198impl<'a, T, Params> IntoIterator for &'a mut RTree<T, Params>
1199where
1200 T: RTreeObject,
1201 Params: RTreeParams,
1202{
1203 type IntoIter = RTreeIteratorMut<'a, T>;
1204 type Item = &'a mut T;
1205
1206 fn into_iter(self) -> Self::IntoIter {
1207 self.iter_mut()
1208 }
1209}
1210
1211#[cfg(test)]
1212mod test {
1213 use super::RTree;
1214 use crate::algorithm::rstar::RStarInsertionStrategy;
1215 use crate::params::RTreeParams;
1216 use crate::test_utilities::{create_random_points, SEED_1};
1217 use crate::DefaultParams;
1218
1219 struct TestParams;
1220 impl RTreeParams for TestParams {
1221 const MIN_SIZE: usize = 10;
1222 const MAX_SIZE: usize = 20;
1223 const REINSERTION_COUNT: usize = 1;
1224 type DefaultInsertionStrategy = RStarInsertionStrategy;
1225 }
1226
1227 #[test]
1228 fn test_remove_capacity() {
1229 pub struct WeirdParams;
1230
1231 impl RTreeParams for WeirdParams {
1232 const MIN_SIZE: usize = 1;
1233 const MAX_SIZE: usize = 10;
1234 const REINSERTION_COUNT: usize = 1;
1235 type DefaultInsertionStrategy = RStarInsertionStrategy;
1236 }
1237
1238 let mut items: Vec<[f32; 2]> = Vec::new();
1239 for i in 0..2 {
1240 items.push([i as f32, i as f32]);
1241 }
1242 let mut tree: RTree<_, WeirdParams> = RTree::bulk_load_with_params(items);
1243 assert_eq!(tree.remove(&[1.0, 1.0]).unwrap(), [1.0, 1.0]);
1244 }
1245
1246 #[test]
1247 fn test_create_rtree_with_parameters() {
1248 let tree: RTree<[f32; 2], TestParams> = RTree::new_with_params();
1249 assert_eq!(tree.size(), 0);
1250 }
1251
1252 #[test]
1253 fn test_insert_single() {
1254 let mut tree: RTree<_> = RTree::new();
1255 tree.insert([0.02f32, 0.4f32]);
1256 assert_eq!(tree.size(), 1);
1257 assert!(tree.contains(&[0.02, 0.4]));
1258 assert!(!tree.contains(&[0.3, 0.2]));
1259 }
1260
1261 #[test]
1262 fn test_insert_many() {
1263 const NUM_POINTS: usize = 1000;
1264 let points = create_random_points(NUM_POINTS, SEED_1);
1265 let mut tree = RTree::new();
1266 for p in &points {
1267 tree.insert(*p);
1268 tree.root.sanity_check::<DefaultParams>(true);
1269 }
1270 assert_eq!(tree.size(), NUM_POINTS);
1271 for p in &points {
1272 assert!(tree.contains(p));
1273 }
1274 }
1275
1276 #[test]
1277 fn test_fmt_debug() {
1278 let tree = RTree::bulk_load(vec![[0, 1], [0, 1]]);
1279 let debug: String = format!("{:?}", tree);
1280 assert_eq!(debug, "RTree { size: 2, items: {[0, 1], [0, 1]} }");
1281 }
1282
1283 #[test]
1284 fn test_default() {
1285 let tree: RTree<[f32; 2]> = Default::default();
1286 assert_eq!(tree.size(), 0);
1287 }
1288
1289 #[cfg(feature = "serde")]
1290 #[test]
1291 fn test_serialization() {
1292 use crate::test_utilities::create_random_integers;
1293
1294 use serde_json;
1295 const SIZE: usize = 20;
1296 let points = create_random_integers::<[i32; 2]>(SIZE, SEED_1);
1297 let tree = RTree::bulk_load(points.clone());
1298 let json = serde_json::to_string(&tree).expect("Serializing tree failed");
1299 let parsed: RTree<[i32; 2]> =
1300 serde_json::from_str(&json).expect("Deserializing tree failed");
1301 assert_eq!(parsed.size(), SIZE);
1302 for point in &points {
1303 assert!(parsed.contains(point));
1304 }
1305 }
1306
1307 #[test]
1308 fn test_bulk_load_crash() {
1309 let bulk_nodes = vec![
1310 [570.0, 1080.0, 89.0],
1311 [30.0, 1080.0, 627.0],
1312 [1916.0, 1080.0, 68.0],
1313 [274.0, 1080.0, 790.0],
1314 [476.0, 1080.0, 895.0],
1315 [1557.0, 1080.0, 250.0],
1316 [1546.0, 1080.0, 883.0],
1317 [1512.0, 1080.0, 610.0],
1318 [1729.0, 1080.0, 358.0],
1319 [1841.0, 1080.0, 434.0],
1320 [1752.0, 1080.0, 696.0],
1321 [1674.0, 1080.0, 705.0],
1322 [136.0, 1080.0, 22.0],
1323 [1593.0, 1080.0, 71.0],
1324 [586.0, 1080.0, 272.0],
1325 [348.0, 1080.0, 373.0],
1326 [502.0, 1080.0, 2.0],
1327 [1488.0, 1080.0, 1072.0],
1328 [31.0, 1080.0, 526.0],
1329 [1695.0, 1080.0, 559.0],
1330 [1663.0, 1080.0, 298.0],
1331 [316.0, 1080.0, 417.0],
1332 [1348.0, 1080.0, 731.0],
1333 [784.0, 1080.0, 126.0],
1334 [225.0, 1080.0, 847.0],
1335 [79.0, 1080.0, 819.0],
1336 [320.0, 1080.0, 504.0],
1337 [1714.0, 1080.0, 1026.0],
1338 [264.0, 1080.0, 229.0],
1339 [108.0, 1080.0, 158.0],
1340 [1665.0, 1080.0, 604.0],
1341 [496.0, 1080.0, 231.0],
1342 [1813.0, 1080.0, 865.0],
1343 [1200.0, 1080.0, 326.0],
1344 [1661.0, 1080.0, 818.0],
1345 [135.0, 1080.0, 229.0],
1346 [424.0, 1080.0, 1016.0],
1347 [1708.0, 1080.0, 791.0],
1348 [1626.0, 1080.0, 682.0],
1349 [442.0, 1080.0, 895.0],
1350 ];
1351
1352 let nodes = vec![
1353 [1916.0, 1060.0, 68.0],
1354 [1664.0, 1060.0, 298.0],
1355 [1594.0, 1060.0, 71.0],
1356 [225.0, 1060.0, 846.0],
1357 [1841.0, 1060.0, 434.0],
1358 [502.0, 1060.0, 2.0],
1359 [1625.5852, 1060.0122, 682.0],
1360 [1348.5273, 1060.0029, 731.08124],
1361 [316.36127, 1060.0298, 418.24515],
1362 [1729.3253, 1060.0023, 358.50134],
1363 ];
1364 let mut tree = RTree::bulk_load(bulk_nodes);
1365 for node in nodes {
1366 // Bulk loading will create nodes larger than Params::MAX_SIZE,
1367 // which is intentional and not harmful.
1368 tree.insert(node);
1369 tree.root().sanity_check::<DefaultParams>(false);
1370 }
1371 }
1372}