packed_spatial_index

packed_spatial_index is a packed static spatial index for 2D and 3D axis-aligned bounding boxes.

It is built for read-heavy workloads where the full set of boxes is known up front: build once, then run many window/intersection searches. The default Index2D and Index3D use packed Hilbert R-tree layouts. With the simd feature, SimdIndex2D and SimdIndex3D store boxes in structure-of-arrays form and use SIMD intersection checks. Scalar and SIMD indexes share the same canonical byte format for owned persistence.

use packed_spatial_index::{Index2DBuilder, Box2D};

let mut builder = Index2DBuilder::new(2);
builder.add(Box2D::new(0.0, 0.0, 1.0, 1.0));
builder.add(Box2D::new(5.0, 5.0, 6.0, 6.0));

let index = builder.finish()?;
let hits = index.search(Box2D::new(0.0, 0.0, 2.0, 2.0));

assert_eq!(hits, vec![0]);
# Ok::<(), packed_spatial_index::BuildError>(())

Installation

Requires Rust 1.89 or newer.

[dependencies]
packed_spatial_index = "0.3"

When To Use It

Use this crate when:

• your geometry is static or rebuilt in batches;
• search results can be returned as insertion-order indices into your own payload array;
• you want a compact in-memory index with reusable buffers for repeated searches;
• batch search throughput matters.

It is not a dynamic R-tree: there are no insert/delete operations after build.

Limitations

• The index is static: rebuild it when the dataset changes.
• 2D and 3D axis-aligned bounding boxes are supported.
• Search results are item indices, not stored payloads or geometries.
• Result ordering is not a stable API guarantee.
• Persistence uses canonical Index2D and Index3D byte layouts. SimdIndex2D and SimdIndex3D can save and load those same bytes, but there is no separate zero-copy SoA view format yet.
• Nearest-neighbor search is exact over indexed boxes; approximate KNN and dynamic spatial joins are out of scope for now.

Main Types

• Box2D is the public AABB type, with inclusive overlaps, contains, and contains_point helpers. Box2D::new is unchecked; use Box2D::try_new for untrusted coordinate bounds.
• Box3D and Point3D are the equivalent scalar 3D geometry types.
• Index2DBuilder builds either Index2D or, with simd, SimdIndex2D.
• Index3DBuilder builds either Index3D or, with simd, SimdIndex3D.
• Index2D is the default read-only index.
• Index3D is the scalar read-only 3D index.
• Index2DView and Index3DView are zero-copy read-only views over bytes produced by scalar or SIMD to_bytes methods.
• SimdIndex2D and SimdIndex3D are available with the simd feature and have the same search API and owned persistence API as their scalar counterparts.
• SearchWorkspace reuses result and traversal buffers.
• Point2D, Point3D, and NeighborWorkspace support nearest-neighbor searches.
• SortKey2D selects the public build ordering curve. Hilbert is the stable default.
• SortKey3D does the same for 3D. Hilbert is the stable default.

Search APIs:

• extent() returns the total item box, or None for an empty index.
• search(query) allocates and returns a Vec<usize>.
• search_into(query, &mut results) reuses a result buffer.
• search_with(query, &mut workspace) reuses result and traversal buffers.
• any(query), first(query), and visit(query, visitor) support early exit.

Nearest-neighbor APIs:

• neighbors(point, max_results) returns nearest item indices.
• neighbors_within(point, max_results, max_distance) caps the search radius.
• neighbors_into(...) and neighbors_with(...) reuse buffers.
• visit_neighbors(point, max_distance, visitor) visits (index, distance_squared) pairs.

Results are returned in nondecreasing distance order. Ties between equal-distance items are not stable across index layouts.

Builder

use packed_spatial_index::{DEFAULT_NODE_SIZE, Index2DBuilder, Box2D, SortKey2D};

let mut builder = Index2DBuilder::new(10_000)
    .node_size(DEFAULT_NODE_SIZE)
    .sort_key(SortKey2D::Hilbert);

builder.add(Box2D::new(0.0, 0.0, 1.0, 1.0));
builder.add(Box2D::new(5.0, 5.0, 6.0, 6.0));

With parallel enabled:

# use packed_spatial_index::{DEFAULT_PARALLEL_MIN_ITEMS, Index2DBuilder};
let builder = Index2DBuilder::new(100_000)
    .parallel(true)
    .parallel_min_items(DEFAULT_PARALLEL_MIN_ITEMS);

With simd enabled:

# use packed_spatial_index::{Index2DBuilder, Box2D};
let mut builder = Index2DBuilder::new(1);
builder.add(Box2D::new(0.0, 0.0, 1.0, 1.0));
let simd_index = builder.finish_simd()?;
# Ok::<(), packed_spatial_index::BuildError>(())

The same finish_simd() method is available on Index3DBuilder and returns SimdIndex3D.

3D uses the same builder/search shape:

use packed_spatial_index::{Box3D, Index3DBuilder, Point3D};

let mut builder = Index3DBuilder::new(2);
builder.add(Box3D::new(0.0, 0.0, 0.0, 1.0, 1.0, 1.0));
builder.add(Box3D::new(5.0, 5.0, 5.0, 6.0, 6.0, 6.0));

let index = builder.finish()?;
assert_eq!(
    index.search(Box3D::new(0.0, 0.0, 0.0, 2.0, 2.0, 2.0)),
    vec![0]
);
assert_eq!(index.neighbors(Point3D::new(5.5, 5.5, 5.5), 1), vec![1]);
# Ok::<(), packed_spatial_index::BuildError>(())

Persistence

Index2D and Index3D can be serialized to stable little-endian byte formats and loaded back either as owned indexes or as zero-copy views:

use packed_spatial_index::{Index2D, Index2DBuilder, Index2DView, Box2D};

let mut builder = Index2DBuilder::new(1);
builder.add(Box2D::new(0.0, 0.0, 1.0, 1.0));
let index = builder.finish()?;

let bytes = index.to_bytes();
let mut reusable = Vec::new();
index.to_bytes_into(&mut reusable);
assert_eq!(reusable, bytes);

let owned = Index2D::from_bytes(&bytes)?;
let view = Index2DView::from_bytes(&bytes)?;

assert_eq!(owned.search(Box2D::new(0.0, 0.0, 2.0, 2.0)), vec![0]);
assert_eq!(view.search(Box2D::new(0.0, 0.0, 2.0, 2.0)), vec![0]);
# Ok::<(), Box<dyn std::error::Error>>(())

3D persistence uses the same header and sections, with a dimension flag and six f64 coordinates per stored box. With the simd feature, SimdIndex2D and SimdIndex3D read and write the same canonical bytes as the scalar indexes. Loading a SIMD index is an owned load that scatters canonical box records into SoA columns. SimdIndex2DView and SimdIndex3DView borrow the same canonical bytes for zero-copy SIMD-over-AoS queries.

The binary layout is documented in FORMAT.md.

Examples

Runnable examples cover the public paths:

cargo run --example basic_2d
cargo run --example basic_3d
cargo run --example persistence_2d
cargo run --example persistence_3d
cargo run --example knn_2d
cargo run --example knn_3d
cargo run --example reuse_workspace_2d
cargo run --example reuse_workspace_3d

Feature-gated experiment examples include parallel_experiment_2d, parallel_experiment_3d, soa_experiment_2d, soa_experiment_3d, nodesize_experiment_2d, and nodesize_experiment_3d.

Features

Both features are enabled by default:

• parallel: adaptive rayon-based index builds through Index2DBuilder::parallel and Index3DBuilder::parallel.
• simd: SoA index and SIMD search paths through SimdIndex2D and SimdIndex3D, plus owned and zero-copy SIMD persistence through the canonical byte format.

Minimal build:

cargo build --no-default-features

SIMD-only or parallel-only builds:

cargo build --no-default-features --features simd
cargo build --no-default-features --features parallel

Safety

The public API is safe Rust; users do not need unsafe to build, load, search, or query neighbors.

Internally, the crate keeps unsafe limited to narrow performance-sensitive paths:

• unaligned little-endian reads for validated Index2DView and Index3DView byte buffers;
• bulk byte copies for repr(C) boxes and index sections when serializing on compatible little-endian targets;
• x86/x86_64 prefetch intrinsics used only by hidden benchmark/experimental paths;
• AVX-512 loads in the simd feature, guarded by runtime CPU feature detection.

Loaded buffers are validated before they can be searched, so malformed input is reported as LoadError instead of relying on caller-side invariants.

Performance Notes

Recent local Criterion runs, lower is better. The 2D competitor workload uses 100,000 random AABBs and 1,000 random search windows; build and search competitors are measured in the same benchmark suite on the same generated inputs. Persistence rows use the canonical byte format for 100,000 boxes.

Scalar Index2D search versus static_aabb2d_index is dataset-sensitive. Two local search runs with the same item/query counts but different generated inputs showed opposite scalar ordering:

Recent local 2D-vs-3D Criterion run. Lower latency is better. The 3D speed column is 2D latency / 3D latency, so values above 1.00x mean 3D is faster. The build workload uses 100,000 boxes with node_size = 16; search and KNN use 1,000 query windows or points.

Recent local 3D SIMD run. The speed column is scalar/serial latency divided by SIMD/parallel latency, so values above 1.00x mean the SIMD or parallel path is faster.

The short version:

• Index2D is the general-purpose path;
• SimdIndex2D and SimdIndex3D are best for heavier query batches where SIMD work amortizes well;
• scalar Index2D search versus static_aabb2d_index depends on the generated data and query distribution, while Index2D build is faster in these runs;
• Index3D build and KNN are still slower than Index2D, but uniform 3D search can be faster when Z meaningfully prunes the tree;
• SIMD persistence uses the same canonical bytes as scalar persistence; it pays an SoA gather/scatter cost but avoids a second file format;
• any is often much faster than collecting full result sets when all you need is existence;
• AVX-512 is not always the fastest path in parallel workloads because CPU frequency behavior matters.
• flatgeobuf2d_bench compares against FlatGeobuf's packed Hilbert R-tree;
• index2d_bench compares build/search paths against static_aabb2d_index;
• index3d_bench covers 3D build/search/KNN, SIMD search/build, dimension comparisons, node sizes, and hidden Morton baseline;
• persistence_knn2d_bench covers 2D scalar/SIMD persistence, loaded views, and KNN;
• persistence_knn3d_bench covers 3D scalar/SIMD persistence, loaded views, and KNN.

Run the focused benchmark suites with:

cargo bench --bench index2d_bench --no-default-features --features parallel,simd
cargo bench --bench index3d_bench --no-default-features --features parallel,simd
cargo bench --bench persistence_knn2d_bench --no-default-features --features simd
cargo bench --bench persistence_knn3d_bench --no-default-features --features simd
cargo bench --bench flatgeobuf2d_bench --no-default-features --features parallel,simd

Status

The core API is intentionally small and breaking API cleanup happens before a 1.0 release.

License

Licensed under the Apache License, Version 2.0.