AABB - Hilbert R-tree Spatial Index

A Rust library providing 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.7"

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
}

Point Cloud Example

use aabb::prelude::*;

fn main() {
    let mut tree = AABB::with_capacity(4);
    
    // Add points using the convenient add_point() method
    tree.add_point(0.0, 0.0);
    tree.add_point(1.0, 1.0);
    tree.add_point(2.0, 2.0);
    tree.add_point(5.0, 5.0);
    
    // Build the spatial index
    tree.build();
    
    // Query for points within a circular region (optimized for point data)
    let mut results = Vec::new();
    tree.query_circle_points(0.0, 0.0, 2.5, &mut results);
    
    println!("Found {} points within radius 2.5", results.len());
    
    // Find K nearest points
    let mut results = Vec::new();
    tree.query_nearest_k_points(0.0, 0.0, 2, &mut results);
    println!("Found {} nearest points", results.len());
}

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.

Hilbert Curve Spatial Ordering

The Hilbert space-filling curve is a continuous fractal curve that visits every cell in a 2D grid exactly once, maintaining proximity in space:

The curve preserves spatial locality - points close to each other in 2D space tend to be close along the Hilbert curve order. This property makes the flat array layout extremely cache-friendly for spatial queries.

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
• add_point(x, y) - (f64) Add a point (convenience method - internally stores as (x, y, x, y))
• build() - (f64, i32) Build the spatial index (required before querying)
• get(item_id) - (f64, i32) Retrieve the bounding box for an item by its ID
• get_point(item_id) - (f64) Retrieve a point as (x, y) for items added with add_point()
• save(path) - (f64, i32) Save the built tree to a file for fast loading later
• load(path) - (f64, i32) Load a previously saved tree from a file

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_id(item_id, results) (f64, i32) - Find boxes that intersect with a specific item already in the tree (by ID), excluding the item itself
• 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

Point-Specific Optimized Queries

• query_nearest_k_points(x, y, k, results) (f64) - Find K nearest points (stored as (x, x, y, y)), sorted by distance
• query_circle_points(center_x, center_y, radius, results) (f64) - Find points within a circular region (optimized for point data)

Note: Point-specific methods assume all items in the tree are stored as degenerate boxes (points) where min_x == max_x and min_y == max_y. For mixed data (both points and boxes), use the general methods instead.

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_id - Find boxes intersecting a specific item already in the tree (by ID)
• 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_k - Find K nearest boxes
• query_circle - Find boxes in a circular region
• query_circle_points - Find points in a circular region (optimized)
• query_nearest_k_points - Find K nearest points (optimized)
• 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
> cargo bench --bench profile_bench
> cargo bench --bench profile_bench_i32

Box Tree Queries (f64)
================
build box tree 1000000 items:        76.65ms
query_intersecting (100% coverage) - 1000 queries:     2390.735µs/query
query_intersecting (50% coverage)  - 1000 queries:      436.450µs/query
query_intersecting (10% coverage)  - 1000 queries:       98.460µs/query
query_intersecting (1% coverage)   - 1000 queries:       17.832µs/query
query_intersecting (0.01% coverage)- 1000 queries:        2.668µs/query
query_nearest_k (1000 searches of 100 neighbors):        13.868µs/query
query_nearest_k (1 search of 1000000 neighbors):        110.456ms/query
query_nearest_k (100000 searches of 1 neighbor):          5.297µs/query
query_nearest_k k=1 - 1000 queries:          6.315µs/query
query_nearest_k k=10 - 1000 queries:         6.580µs/query
query_nearest_k k=100 - 1000 queries:       13.783µs/query
query_nearest_k k=1000 - 100 queries:       86.150µs/query
query_point - 10000 queries:                       1.083µs/query
query_intersecting_k k=100 - 10000 queries:        1.886µs/query
query_contain - 1000 queries:                      2.027µs/query
query_contained_within - 1000 queries:             2.947µs/query
query_circle - 1000 queries (radius=5):          49.666µs/query
query_in_direction - 1000 queries:               13.243µs/query
query_in_direction_k k=50 - 1000 queries:        20.865µs/query

Point Cloud Queries
===================
build point cloud 1000000 points:                  71.33ms
query_circle_points - 1000 queries (radius=5):     30.001µs/query
query_nearest_k_points k=1 - 1000 queries:          2.955µs/query
query_nearest_k_points k=10 - 1000 queries:         4.333µs/query
query_nearest_k_points k=100 - 1000 queries:       12.038µs/query
query_nearest_k_points k=1000 - 100 queries:       76.387µs/query


Box Tree Queries (i32)
================
build box tree 1000000 items:        55.19ms
query_intersecting (100% coverage) - 1000 queries:     1676.877µs/query
query_intersecting (50% coverage)  - 1000 queries:      262.290µs/query
query_intersecting (50% coverage)  - 1000 queries:       55.554µs/query
query_intersecting (1% coverage)   - 1000 queries:        7.253µs/query
query_intersecting (0.01% coverage)- 1000 queries:        0.768µs/query
query_intersecting_k k=100 - 10000 queries:               0.564µs/query
query_point - 10000 queries:                  0.449µs/query
query_contain - 1000 queries:                 0.279µs/query
query_contained_within - 1000 queries:        1.604µs/query
query_intersecting_id - 1000 queries:         0.307µs/query

Related Projects

AABB is part of the open-sourced Nest2D projects collection.