AABB - Hilbert R-tree Spatial Index

A Rust library providing a simple and efficient Hilbert R-tree implementation for spatial queries on axis-aligned bounding boxes (AABBs).

Features

Hilbert Curve Ordering: Uses Hilbert space-filling curve for improved spatial locality (inspired by Flatbush algorithm)
AABB Intersection Queries: Fast rectangular bounding box intersection testing
Zero-Copy: Single contiguous buffer layout - safe for parallel queries with no allocations per query
Simple API: Easy to use with minimal setup
Static Optimization: Efficient for static or infrequently-modified spatial data

Usage

Add this to your Cargo.toml:

[dependencies]
aabb = "0.6"

Basic Example

use aabb::prelude::*;

fn main() {
    let mut tree = AABB::with_capacity(3);
    
    // Add bounding boxes (min_x, min_y, max_x, max_y)
    tree.add(0.0, 0.0, 1.0, 1.0);
    tree.add(0.5, 0.5, 1.5, 1.5);
    tree.add(2.0, 2.0, 3.0, 3.0);
    
    // Build the spatial index
    tree.build();
    
    // Query for intersecting boxes
    let mut results = Vec::new();
    // bbox: xmin, ymin, xmax, ymax 
    tree.query_intersecting(0.7, 0.7, 1.3, 1.3, &mut results);
    
    println!("Found {} intersecting boxes", results.len());
    // Results contains indices of boxes that intersect the query
}

How it Works

The Hilbert R-tree stores bounding boxes in a flat array and sorts them by their Hilbert curve index (computed from box centers). This provides good spatial locality for most spatial queries while maintaining a simple, cache-friendly data structure.

API Reference

Construction

HilbertRTree::new() or AABB::new() - Create a new empty tree
HilbertRTree::with_capacity(capacity) or AABB::with_capacity(capacity) - Create a new tree with preallocated capacity
HilbertRTreeI32::new() or AABBI32::new() - Create a new empty tree
HilbertRTreeI32::with_capacity(capacity) or AABBI32::with_capacity(capacity) - Create a new tree with preallocated capacity
add(min_x, min_y, max_x, max_y) - (f64, i32) Add a bounding box
build() - (f64, i32) the spatial index (required before querying)

Queries

Basic Spatial Queries

query_intersecting(min_x, min_y, max_x, max_y, results) (f64, i32) - Find boxes that intersect a rectangle
query_intersecting_k(min_x, min_y, max_x, max_y, k, results) (f64, i32) - Find first K intersecting boxes
query_point(x, y, results) (f64, i32) - Find boxes that contain a point
query_contain(min_x, min_y, max_x, max_y, results) (f64, i32) - Find boxes that contain a rectangle
query_contained_within(min_x, min_y, max_x, max_y, results) (f64, i32) - Find boxes contained within a rectangle

Distance-Based Queries

query_nearest_k(x, y, k, results) (f64) - Find K nearest boxes to a point
query_circle(center_x, center_y, radius, results) (f64) - Find boxes intersecting a circular region

Directional Queries

query_in_direction(rect_min_x, rect_min_y, rect_max_x, rect_max_y, direction_x, direction_y, distance, results) (f64) - Find boxes intersecting a rectangle's movement path
query_in_direction_k(rect_min_x, rect_min_y, rect_max_x, rect_max_y, direction_x, direction_y, k, distance, results) (f64) - Find K nearest boxes intersecting a rectangle's movement path

Examples

Minimal examples for each query method are available in the examples/ directory:

query_intersecting - Find boxes intersecting a rectangle
query_intersecting_k - Find K first intersecting boxes
query_point - Find boxes containing a point
query_contain - Find boxes containing a rectangle
query_contained_within - Find boxes inside a rectangle
query_nearest - Find the single nearest box
query_nearest_k - Find K nearest boxes
query_circle - Find boxes in a circular region
query_in_direction - Find boxes in a movement path
query_in_direction_k - Find K nearest in a movement path

Run any example with:

cargo run --example query_point

Performance

Cache-Friendly: Flat array storage with Hilbert curve ordering for good spatial locality
Static Optimization: Optimized for static or infrequently-modified spatial data

Environment:
- OS: Ubuntu 24.04.3 LTS
- Processor: Intel Core i5-1240P
- Kernel: Linux 6.8.0-86-generic 
- CPU Frequency: ~1773-3500 MHz

Building index with 1000000 items...
Index built in 116.58ms (f64)
Index built in 88.07ms (i32)

Running query benchmarks:
-----------------------
HilbertRTree::query_intersecting(f64)
1000 searches 10%: 246ms
1000 searches 1%: 19ms
1000 searches 0.01%: 2ms

-----------------------
HilbertRTreeI32::query_intersecting(i32)
1000 searches 10%: 169ms
1000 searches 1%: 10ms
1000 searches 0.01%: 0ms

Running neighbor benchmarks:
-----------------------
query_nearest_k(f64)
1000 searches of 100 neighbors: 21ms
1 searches of 1000000 neighbors: 123ms
100000 searches of 1 neighbors: 888ms

License

This project is licensed under the MIT License.

aabb 0.6.3