A fast R-tree for Rust. Ported from an implementation that's designed for Tile38.

Related tags

Geospatial rtree.rs
Overview

rtree.rs

license crates.io version documentation

A fast R-tree for Rust. Ported from an implementation that's designed for Tile38.

Cities

Features

  • Optimized for fast inserts and updates. Ideal for both static and moving data.
  • Standard insert, remove, and search 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
You might also like...
Rust crate for performing coordinate transforms
Rust crate for performing coordinate transforms

Synopsis A Rust crate use for performing coordinate transformations. The crate relies on nalgebra vectors to perform the coordinate transformations. C

Geospatial primitives and algorithms for Rust

geo Geospatial Primitives, Algorithms, and Utilities The geo crate provides geospatial primitive types such as Point, LineString, and Polygon, and pro

Rust bindings for GDAL

gdal [] GDAL bindings for Rust. So far, you can: open a raster dataset for reading/writing get size and number of bands get/set projection and geo-tra

Rust bindings for the latest stable release of PROJ

PROJ Coordinate transformation via bindings to the PROJ v7.2.1 API. Two coordinate transformation operations are currently provided: projection (and i

Geohash for Rust

Rust-Geohash Rust-Geohash is a Rust library for Geohash algorithm. Ported from node-geohash module. Documentation Docs Check the API doc at docs.rs Li

Rust read/write support for well-known text (WKT)

wkt Rust read/write support for well-known text (WKT). License Licensed under either of Apache License, Version 2.0 (LICENSE-APACHE or http://www.apac

Google Encoded Polyline encoding & decoding in Rust.

polyline Google Encoded Polyline encoding & decoding in Rust. A Note on Coordinate Order This crate uses Coordinate and LineString types from the geo-

Geocoding library for Rust.

geocoding Rust utilities to enrich addresses, cities, countries, and landmarks with geographic coordinates through third-party geocoding web services.

Rust read/write support for GPS Exchange Format (GPX)

gpx gpx is a library for reading and writing GPX (GPS Exchange Format) files. It uses the primitives provided by geo-types to allow for storage of GPS

Owner
Josh Baker
Josh Baker
An fast, offline reverse geocoder (>1,000 HTTP requests per second) in Rust.

Rust Reverse Geocoder A fast reverse geocoder in Rust. Inspired by Python reverse-geocoder. Links Crate 2.0.0 Docs 1.0.1 Docs Description rrgeo takes

Grant Miner 91 Dec 29, 2022
Fast 2D Delaunay triangulation in Rust. A port of Delaunator.

delaunator-rs A very fast static 2D Delaunay triangulation library for Rust. A port of Delaunator. Documentation Example use delaunator::{Point, trian

Vladimir Agafonkin 123 Dec 20, 2022
Fast shortest path calculations for Rust

Fast Paths The most famous algorithms used to calculate shortest paths are probably Dijkstra's algorithm and A*. However, shortest path calculation ca

Andi 226 Jan 2, 2023
Fast Geospatial Feature Storage API

Hecate OpenStreetMap Inspired Data Storage Backend Focused on Performance and GeoJSON Interchange Hecate Feature Comparison Feature Hecate ESRI MapSer

Mapbox 243 Dec 19, 2022
Blazing fast and lightweight PostGIS vector tiles server

Martin Martin is a PostGIS vector tiles server suitable for large databases. Martin is written in Rust using Actix web framework. Requirements Install

Urbica 921 Jan 7, 2023
A fast, offline, reverse geocoder

Rust Reverse Geocoder A fast reverse geocoder in Rust. Inspired by Python reverse-geocoder. Links Crate Changelog Latest Docs v2.0 Docs v1.0 Docs Desc

Grant Miner 82 Dec 3, 2022
Trees for fast location-to-value lookup.

HexTree hextree provides tree structures that represent geographic regions with H3 cells. The primary structures are: HexTreeMap: an H3 cell-to-value

Jay Kickliter 38 Dec 15, 2022
Rust implementation of the Martinez-Rueda Polygon Clipping Algorithm

Boolean operations on geo shapes This is an implementation of the Martinez-Rueda Polygon Clipping Algorithm in rust to integrate smoothly into the alr

21re 70 Nov 28, 2022
An implementation of WICG Import Maps specification

import_map A Rust implementation of WICG Import Maps specification. This crates is used in Deno project. The implementation is tested against WPT test

Deno Land 20 Nov 21, 2022
Didactic implementation of the type checker described in "Complete and Easy Bidirectional Typechecking for Higher-Rank Polymorphism" written in OCaml

bidi-higher-rank-poly Didactic implementation of the type checker described in "Complete and Easy Bidirectional Typechecking for Higher-Rank Polymorph

Søren Nørbæk 23 Oct 18, 2022