rstar

Make a breaking release to get accumulated fixes and additions out to…

Added

• Added missing re-exports of nearest neighbor iterators so they can be named in downstream crates. (PR)
• Added nearest neighbor search with distance squared: nearest_neighbor_with_distance_2 and nearest_neighbors_with_distance_2 methods (PR).
• Added root doc examples and traversal docs
• Implemented RTreeObject for Arc<T> and Rc<T>
• Added Envelope::is_empty. (PR)
• New AABB::from_center utility constructor
• New AABB::from_bounds utility constructor

Fixed

• Fix excessive memory retention in bulk_load from Vec::split_off over-capacity
• Fix transcription error in implementation of OMT bulk loading leading to nodes which are too large.

Changed

• BREAKING Made RStar methods take Point and Envelope as owned values where it makes sense (PR)
• Fix Clippy warning (surfaced in Rust 1.89) related to lifetime elision
• MSRV is now 1.85 (released on 2025-02-20 and shipped in Debian Trixie)
• Fix incorrect assertion message in verify_parameters of rstar/src/params.rs

Fix for buggy 0.12.1 release

Changed

• Reverted the change to AABB::new_empty while still avoiding overflow panics applying selections on empty trees (PR)

Added

• Provide selection methods based on internal iteration (PR)
• Add ObjectRef combinator to build tree referencing objects elsewhere (PR)

Changed

• Switched to unstable sort for envelopes and node reinsertion (PR)
• Use a more tame value for AABB::new_empty to avoid overflow panics applying selections on empty trees (PR)
• Avoid infinite recursion due to numerical instability when computing the number of clusters (PR)

Added

• Add optional support for the mint crate
• Implemented IntoIter for RTree, i.e. added a owning iterator
• Added cached envelope bulk load benchmark
• Implemented Hash for AABB, Line, and Rectangle, provided the Point used implements Hash itself
• Implemented Default for DefaultParams

Changed

• Fixed a stack overflow error in DrainIterator::next
• Clarified that the distance measure in distance_2 is not restricted to euclidean distance
• updated to heapless=0.8
• Updated CI config to use merge queue (PR)

MSRV bump and bulk-loading perf improvements

Added

• Add CachedEnvelope combinator which simplifies memoizing envelope computations. (PR)
• Point is now implemented as const generic for any length of RTreeNum array

Changed

• Increase our MSRV to Rust 1.63 following that of the geo crate. (PR)

Prepare for v0.10.0 release

Added

• Added method RTree::drain().
• Changed license field to SPDX 2.1 license expression

Changed

• fixed all clippy lint issues
• Fixed error when setting MIN_SIZE = 1 in RTreeParams and added assert for positive MIN_SIZE
• BREAKING: Removed the Copy bound from Point and Envelope. (PR)

MSRV: 1.5.1, no-std support

Changed

• Removed dependency on pdqselect (PR)
• New minimal supported rust version (MSRV): 1.51.0
• Replace all usages of std with core & alloc to make rstar fit for no_std. (PR)
• Updated heapless dependency to 0.7 to make use of const generics. (PR)

• Add RTree::drain_* methods to remove and drain selected items. (PR)
• Add trait Point for tuples containing elements of the same type, up to nine dimensions.
• Pinned pdqselect to 0.1.0 as 0.1.1 has switched to the 2021 edition

Changed

• Expose all iterator types in crate::iterators module (PR)

Added generic geomwithdata container

Added

• A generic container for a geometry and associated data: GeomWithData (PR)

Added

• RTree::nearest_neighbors method based on spade crate's implementation

Changed

• Fix floating point inconsistency in min_max_dist_2 (PR).
• BREAKING: Point::generate function now accepts a impl FnMut. Custom implementations of Point must change to accept impl FnMut instead of impl Fn. Callers of Point::generate should not require changes.
• Update CI images to Stable Rust 1.50 and 1.51
• Run clippy, rustfmt, update manifest to reflect ownership changes
• Update Criterion and rewrite deprecated benchmark functions
• Remove unused imports
• Remove executable bit from files
• Fix typos, modernize links

Changed

• Move crate ownership to the georust organization

Fixed

• Update dependencies to remove heapless 0.5, which has a known vulnerability

Fixed:

• Fixed a rare panic when calling insert (See #45)

Changed:

• Fine tuned nearest neighbor iterator inline capacity (see #39). This should boost performance in some cases.

Fixed:

• Bugfix: RTree::locate_with_selection_function_mut sometimes returned too many elements for small trees.

Changed:

• Deprecated RTree::nearest_neighbor_iter_with_distance. The name is misleading, use RTree::nearest_neighbor_iter_with_distance_2 instead.
• Some performance improvements, see #38 and #35

Added

• Added nearest_neighbor_iter_with_distance_2 #31

Changed:

• RTree::intersection_candidates_with_other_tree can now calculate intersections of trees of different item types (see #23)

Added:

• RTree::remove_with_selection_function
• RTree::pop_nearest_neighbor
• Added CHANGELOG.md