rstar

Crates.iorstar
lib.rsrstar
version0.12.2
created_at2018-11-22 22:26:45.2039+00
updated_at2024-11-05 21:59:23.790625+00
descriptionAn R*-tree spatial index
homepage
repositoryhttps://github.com/georust/rstar
max_upload_size
id98213
size193,379
Michael Kirk (michaelkirk)

documentation

https://docs.rs/rstar/

README

rstar

A flexible, n-dimensional r*-tree implementation for the Rust ecosystem, suitable for use as a spatial index.

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 requires alloc)

Geometries

Primitives are provided for point, line, and rectangle geometries. The geo crate uses rstar as an efficient spatial index and provides RTreeObject implementations for storing complex geometries such as linestrings and polygons.

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.

  1. Create branch from master, say release/<version>.
  2. Ensure rstar/CHANGELOG.md describes all the changes since last release (esp. the breaking ones).
  3. Ensure / set version metadata in Cargo.toml of rstar to the new version.
  4. Create PR to master, have it approved and merge.
  5. Checkout the updated master, go to rstar directory and run cargo publish.
  6. Create tag <version> and push to georust/rstar

License

Licensed under either of

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.

Commit count: 291

cargo fmt