aabb/
lib.rs

1//! # AABB - Hilbert R-tree Spatial Index
2//!
3//! A Rust library providing a simple and efficient Hilbert R-tree implementation 
4//! for spatial queries on axis-aligned bounding boxes (AABBs).
5//!
6//! ## Features
7//!
8//! - **Hilbert Curve Ordering**: Uses Hilbert space-filling curve for improved spatial locality
9//! - **AABB Intersection Queries**: Fast rectangular bounding box intersection testing
10//! - **Simple API**: Easy to use with minimal setup
11//! - **Static Optimization**: Efficient for static or infrequently-modified spatial data
12//! 
13//!
14//! ## Quick Start
15//!
16//! ```rust
17//! use aabb::prelude::*;
18//!
19//! // Create a new spatial index
20//! let mut tree = AABB::new();
21//!
22//! // Add some bounding boxes (min_x, min_y, max_x, max_y)
23//! tree.add(0.0, 0.0, 2.0, 2.0);    // Box 0: large box
24//! tree.add(1.0, 1.0, 3.0, 3.0);    // Box 1: overlapping box
25//! tree.add(5.0, 5.0, 6.0, 6.0);    // Box 2: distant box
26//! tree.add(1.5, 1.5, 2.5, 2.5);    // Box 3: small box inside others
27//!
28//! // Build the spatial index (required before querying)
29//! tree.build();
30//!
31//! // Query for boxes intersecting a region
32//! let mut results = Vec::new();
33//! // minx, miny, maxx, maxy
34//! tree.query_intersecting(1.2, 1.2, 2.8, 2.8, &mut results);
35//!
36//! // Results contains indices of intersecting boxes
37//! println!("Found {} intersecting boxes: {:?}", results.len(), results);
38//! // Output: Found 3 intersecting boxes: [0, 1, 3]
39//!
40//! // Query for boxes intersecting with an already-indexed item (no self-intersection)
41//! let _ = tree.query_intersecting_id(0, &mut results);
42//! println!("Boxes intersecting with box 0: {:?}", results);
43//! // Output: Boxes intersecting with box 0: [1, 3]
44//!
45//! // You can reuse the results vector for multiple queries
46//! tree.query_intersecting(4.0, 4.0, 7.0, 7.0, &mut results);
47//! println!("Found {} boxes in distant region: {:?}", results.len(), results);
48//! // Output: Found 1 boxes in distant region: [2]
49//!
50//! // Point queries - find boxes containing a specific point
51//! tree.query_point(1.8, 1.8, &mut results);
52//! println!("Point (1.8, 1.8) is in boxes: {:?}", results);
53//!
54//! // Containment queries - find boxes that contain a rectangle
55//! tree.query_contain(1.2, 1.2, 1.8, 1.8, &mut results);
56//! println!("Boxes containing rectangle: {:?}", results);
57//!
58//! // K-limited queries - find first K intersecting boxes for performance
59//! tree.query_intersecting_k(0.0, 0.0, 3.0, 3.0, 2, &mut results);
60//! println!("First 2 intersecting boxes: {:?}", results);
61//!
62//! // K-nearest neighbor queries - use k=1 for single nearest
63//! tree.query_nearest_k(2.0, 2.0, 1, &mut results);
64//! println!("Nearest box to (2.0, 2.0): {:?}", results);
65//!
66//! // Distance-based queries - find boxes in circular region
67//! tree.query_circle(1.5, 1.5, 2.0, &mut results);
68//! println!("Boxes in circle: {:?}", results);
69//!
70//! // K-nearest neighbor queries
71//! tree.query_nearest_k(2.0, 2.0, 2, &mut results);
72//! println!("2 nearest boxes to (2.0, 2.0): {:?}", results);
73//!
74//! // Directional queries - find boxes in rectangle's movement path
75//! // Start with rectangle (1.5, 1.5) x (2.5, 2.5) and move right by distance 3
76//! tree.query_in_direction(1.5, 1.5, 2.5, 2.5, 1.0, 0.0, 3.0, &mut results);
77//! println!("Boxes intersecting movement path: {:?}", results);
78//!
79//! // Directional K-nearest queries - find K nearest boxes in movement path
80//! tree.query_in_direction_k(1.5, 1.5, 2.5, 2.5, 1.0, 0.0, 2, 3.0, &mut results);
81//! println!("2 nearest boxes in movement path: {:?}", results);
82//!
83//! ```
84//!
85//! ## Available Query Methods
86//!
87//! ### Basic Spatial Queries
88//! - [`query_intersecting`] `(f64, i32)` - Find boxes that intersect a rectangle
89//! - [`query_intersecting_id`] `(f64, i32)` - Find boxes that intersect an already-indexed item
90//! - [`query_intersecting_k`] `(f64, i32)` - Find first K intersecting boxes
91//! - [`query_point`] `(f64, i32)` - Find boxes that contain a point
92//! - [`query_contain`] `(f64, i32)` - Find boxes that contain a rectangle  
93//! - [`query_contained_within`] `(f64, i32)` - Find boxes contained within a rectangle
94//!
95//! ### Distance-Based Queries
96//! - [`query_nearest_k`] `(f64)` - Find K nearest boxes to a point (use k=1 for single nearest)
97//! - [`query_circle`] `(f64)` - Find boxes intersecting a circular region
98//!
99//! ### Directional Queries  
100//! - [`query_in_direction`] `(f64)` - Find boxes intersecting a rectangle's movement path
101//! - [`query_in_direction_k`] `(f64)` - Find K nearest boxes intersecting a rectangle's movement path
102//!
103//! [`query_intersecting`]: HilbertRTree::query_intersecting
104//! [`query_intersecting_id`]: HilbertRTree::query_intersecting_id
105//! [`query_intersecting_k`]: HilbertRTree::query_intersecting_k
106//! [`query_point`]: HilbertRTree::query_point
107//! [`query_contain`]: HilbertRTree::query_contain
108//! [`query_contained_within`]: HilbertRTree::query_contained_within
109//! [`query_nearest_k`]: HilbertRTree::query_nearest_k
110//! [`query_circle`]: HilbertRTree::query_circle
111//! [`query_in_direction`]: HilbertRTree::query_in_direction
112//! [`query_in_direction_k`]: HilbertRTree::query_in_direction_k
113//!
114//! ## How It Works
115//!
116//! The Hilbert R-tree stores bounding boxes in a flat array and sorts them by their 
117//! Hilbert curve index (computed from box centers). This provides good spatial locality 
118//! for most spatial queries while maintaining a simple, cache-friendly data structure.
119//!
120//! The Hilbert curve is a space-filling curve that maps 2D coordinates to a 1D sequence
121//! while preserving spatial locality - points that are close in 2D space tend to be 
122//! close in the 1D Hilbert ordering.
123
124/// Core Hilbert R-tree spatial index data structure (flat sorted version)
125#[doc(hidden)]
126pub mod hilbert_rtree_leg;
127/// Hierarchical Hilbert R-tree spatial index (flatbush-inspired)
128pub mod hilbert_rtree;
129/// Hierarchical Hilbert R-tree spatial index for i32 coordinates (memory-efficient)
130pub mod hilbert_rtree_i32;
131/// Integration tests for the library
132#[doc(hidden)]
133pub mod integration_test;
134/// Comparison tests between both implementations
135#[doc(hidden)]
136pub mod comparison_tests;
137/// Component tests for granular method testing
138#[doc(hidden)]
139pub mod component_tests;
140/// Component tests for HilbertRTreeI32
141#[doc(hidden)]
142pub mod component_tests_i32;
143/// Legacy query tests
144#[doc(hidden)]
145pub mod test_legacy_query;
146/// Point-specific optimization tests
147#[doc(hidden)]
148pub mod test_point_optimizations;
149/// Prelude for convenient imports
150pub mod prelude;
151
152#[doc(hidden)]
153pub use hilbert_rtree_leg::HilbertRTreeLeg;
154pub use hilbert_rtree::HilbertRTree;
155pub use hilbert_rtree_i32::HilbertRTreeI32;
156
157pub use prelude::{AABB, AABBI32};
158
159/// Add two unsigned 64-bit integers
160pub fn add(left: u64, right: u64) -> u64 {
161    left + right
162}
163
164#[cfg(test)]
165mod tests {
166    use super::*;
167
168    #[test]
169    fn it_works() {
170        let result = add(2, 2);
171        assert_eq!(result, 4);
172    }
173}
aabb/lib.rs

aabb/
lib.rs
