5 releases
0.1.4 | Nov 14, 2022 |
---|---|
0.1.3 | Nov 14, 2022 |
0.1.2 | May 11, 2022 |
0.1.1 | May 6, 2022 |
0.1.0 | May 6, 2022 |
#478 in Data structures
7,937 downloads per month
Used in 8 crates
(2 directly)
580KB
971 lines
rtree.rs
A fast R-tree for Rust. Ported from an implementation that's designed for Tile38.
Features
- Optimized for fast inserts and updates. Ideal for both static and moving data.
- Standard
insert
,remove
, andsearch
operations - Includes
nearby
function for performing nearest neighbors (kNN) iterations - Supports integers or floats for coordinates.
f32
,f64
,u64
, etc. - Allows for multiple dimensions using const generics.
Examples
Add points
use rtree_rs::{RTree, Rect};
let mut tr = RTree::new();
// Insert some points
tr.insert(Rect::new_point([-112.0078, 33.4373]), "PHX");
tr.insert(Rect::new_point([-118.4071, 33.9425]), "LAX");
tr.insert(Rect::new_point([-73.7822, 40.6441]), "JFK");
// Search a rectangle
for item in tr.search(Rect::new([-112.1, 33.4], [-112.0, 33.5])) {
println!("{}", item.data);
}
// OUTPUT:
// PHX
Add retangles
tr.insert(Rect::new([10, 10], [20, 20]), "R1");
tr.insert(Rect::new([15, 12], [18, 24]), "R2");
Multiple dimensions
tr.insert(Rect::new([10, 10, 10], [20, 20, 20]), "R1");
tr.insert(Rect::new_point([15, 12, 24]), "P1");
Algorithms
This implementation is a variant of the original paper:
R-TREES. A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING
Inserting
From the root to the leaf, the rectangles which will incur the least enlargement are chosen. Ties go to rectangles with the smallest area.
When a rectangle does not incur any enlargement at all, it's chosen immediately and without further checks of other rectangles in the same node.
Splitting
This implementation attempts to minimize intensive operations such as pre-sorting the children and comparing overlaps & area sizes. The desire is to do simple single axis distance calculation on each child only once, with a target 50/50 chance that the child might be moved in-memory.
When a rect has reached it's max number of entries it's largest axis is calculated and the rect is split into two smaller rects, named left
and right
. Each child rects is then evaluated to determine which smaller rect it should be placed into. Two values, min-dist
and max-dist
, are calcuated for each child.
min-dist
is the distance from the parent's minumum value of it's largest axis to the child's minumum value of the parent largest axis.max-dist
is the distance from the parent's maximum value of it's largest axis to the child's maximum value of the parent largest axis.
When the min-dist
is less than max-dist
then the child is placed into the left
rect, otherwise the child is placed into the right
rect.
If either left or right has fewer than the minimum allowable entries, then it will take enough entries from the other rectangle to ensure that the minumum is reached. The chosen ones are based on the distance of the farthest edge to the other rectangle's axis.
Finally, the child rectangles are sorted in their parent node by the minimum x value.
Deleting
Similar to the original algorithm. A target rect is deleted directly. When the number of children in a rectangle falls below the minumum allowed, that child is removed from the tree and all of it's leaf items are re-inserted into the tree starting at the root.
Searching
Same as the original algorithm.
Performance
On my 2021 Macbook M1 Max.
cd bench
cargo run --release
insert: 1,000,000 ops in 347ms, 2,880,185/sec, 347 ns/op
search-item: 1,000,000 ops in 370ms, 2,700,423/sec, 370 ns/op
search-1%: 10,000 ops in 31ms, 321,916/sec, 3106 ns/op
search-5%: 10,000 ops in 233ms, 42,739/sec, 23397 ns/op
search-10%: 10,000 ops in 704ms, 14,195/sec, 70442 ns/op
remove-half: 500,000 ops in 170ms, 2,937,350/sec, 340 ns/op
reinsert-half: 500,000 ops in 169ms, 2,945,730/sec, 339 ns/op
search-item: 1,000,000 ops in 434ms, 2,304,059/sec, 434 ns/op
search-1%: 10,000 ops in 34ms, 287,740/sec, 3475 ns/op
remove-all: 1,000,000 ops in 363ms, 2,751,735/sec, 363 ns/op