20 releases
0.10.0 | Jan 31, 2023 |
---|---|
0.9.3 | Apr 6, 2022 |
0.9.2 | Nov 18, 2021 |
0.9.0 | Jul 7, 2021 |
0.1.0 | Nov 22, 2018 |
#29 in Data structures
100,000 downloads per month
Used in 111 crates
(28 directly)
165KB
3K
SLoC
rstar
A flexible, n-dimensional r*-tree implementation for the rust ecosystem.
Features
- A flexible r*-tree written in safe rust
- Supports custom point types
- Supports the insertion of user defined types
- Supported operations:
- Insertion
- Rectangle queries
- Nearest neighbor
- Nearest neighbor iteration
- Locate at point
- Element removal
- efficient bulk loading
- Features geometric primitives that can readily be inserted into an r-tree:
- Points (arrays with a constant size)
- Lines
- Rectangles
- Small number of dependencies
- Serde support with the
serde
feature no_std
compatible (but requiresalloc
)
Benchmarks
All benchmarks are performed on a i7-8550U CPU @ 1.80Ghz and with uniformly distributed points. The underlying point type is [f64; 2]
.
Benchmark | Tree size | Time |
---|---|---|
bulk loading | 2000 | 229.82 us |
sequentially loading | 2000 | 1.4477 ms |
nearest neighbor (bulk loaded tree) | 100k | 1.32 us |
nearest neighbor (sequential tree) | 100k | 1.56 us |
successful point lookup | 100k | 177.32 ns |
unsuccessful point lookup | 100k | 273.51 ns |
Project state
The project is being actively developed, feature requests and PRs are welcome!
Documentation
The documentation is hosted on docs.rs.
Release Checklist
The crate can be published by the rstar-publishers
team of
georust. Please follow the steps below while publishing a
new release.
- Create branch from master, say
release/<version>
. - Ensure
rstar/CHANGELOG.md
describes all the changes since last release (esp. the breaking ones). - Ensure / set
version
metadata inCargo.toml
ofrstar
to the new version. - Create PR to master, have it approved and merge.
- Checkout the updated master, go to
rstar
directory and runcargo publish
. - Create tag
<version>
and push togeorust/rstar
License
Licensed under either of
- Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
at your option.
Contribution
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.
Dependencies
~1–1.4MB
~28K SLoC