packed_spatial_index

A packed static spatial index for 2D and 3D axis-aligned bounding boxes (AABBs), in the style of flatbush / static_aabb2d_index. Pack the boxes into a Hilbert R-tree once, then run many queries over it with SIMD:

• range / intersection search
• nearest neighbors (kNN) from a point or a box
• ray casts (all hits or the closest)
• spatial joins between two indexes
• region / culling — 2D triangle / convex-polygon and 3D view-frustum queries that prune to the true shape: ~1.5–7× fewer hits and ~2–14× faster than the bounding-box workaround (synthetic 200k-box bench)

Builds and SIMD searches run faster than comparable Rust indexes (benchmarks), and the same bytes load back as zero-copy, mmap-friendly views. A file can also carry an optional per-item payload and file-level metadata, and a streaming reader can query a large or remote index without loading the whole file.

Live WASM demo

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.13"

When to use it

Use this crate when your geometry is static or rebuilt in batches, you can key results by insertion-order index into your own payload array, and you want a compact in-memory (or mmap'd) index with reusable buffers for high query throughput. It is not a dynamic R-tree — there are no insert/delete operations after finish().

Performance

Built for throughput on static geometry: fast builds, SIMD range / kNN / raycast (AVX2 / AVX-512), and reusable query buffers for tight loops. The Performance page has the full benchmarks against static_aabb2d_index, FlatGeobuf and the bvh crate, showing where it leads and where it doesn't.

Queries at a glance

Every in-memory f64 query (range, kNN, raycast, join) exists on Index2D / Index3D, the simd-feature SimdIndex2D / SimdIndex3D, and the zero-copy views. The compact f32 indexes and the streaming reader cover a subset (see the coverage matrix). Range/ray results are item indices in insertion order; result order is unspecified. For a boolean "any overlap?" reach for any (no allocation, stops at the first hit) rather than search(..).is_empty(); search returns an owned Vec, so in hot loops reuse a buffer (search_into / search_with) or fold with visit. See the guide and docs.rs for full per-method docs.

# use packed_spatial_index::{Index2DBuilder, Box2D, Point2D, Ray2D};
# let mut b = Index2DBuilder::new(2);
# b.add(Box2D::new(0.0, 0.0, 1.0, 1.0));
# b.add(Box2D::new(5.0, 5.0, 6.0, 6.0));
# let index = b.finish()?;
let overlaps = index.search(Box2D::new(0.0, 0.0, 2.0, 2.0)); // range query
let nearest = index.neighbors(Point2D::new(5.5, 5.5), 1);    // kNN
let hit = index.raycast_closest(Ray2D::new(Point2D::new(-1.0, 0.5), 1.0, 0.0, 10.0));
assert_eq!(overlaps, vec![0]);
assert_eq!(nearest, vec![1]);
assert_eq!(hit, Some((0, 1.0)));
# Ok::<(), packed_spatial_index::BuildError>(())

Types at a glance

• Geometry: Box2D, Box3D (inclusive overlaps / contains / contains_point / from_point), Point2D, Point3D, Ray2D, Ray3D, Triangle2D / ConvexPolygon2D (2D region queries), Frustum3D (3D culling).
• Builders: Index2DBuilder, Index3DBuilder — finish (scalar f64), finish_simd (SoA + SIMD), finish_f32 (compact scalar f32), finish_simd_f32 (compact f32 + SIMD).
• Indexes: Index2D / Index3D (scalar f64), SimdIndex2D / SimdIndex3D (SIMD f64), Index2DF32 / Index3DF32 (half-memory scalar f32), SimdIndex2DF32 / SimdIndex3DF32 (half-memory f32 + SIMD).
• Views: zero-copy Index2DView / Index3DView (and SIMD / f32 view variants) over serialized bytes.
• Streaming: StreamIndex2D / StreamIndex3D (and compact StreamIndex2DF32 / StreamIndex3DF32) query a serialized index over a RangeReader without loading it whole (stream feature). A windowed query over a 100 MB index served from object storage costs only a handful of range reads. See the Cloudflare Worker + R2 example.
• Workspaces: SearchWorkspace / NeighborWorkspace reuse buffers in loops.
• Sorting / errors: SortKey2D / SortKey3D (default Hilbert), BoundsError, BuildError, LoadError.

A full coverage matrix (which index type answers which query, and why some cells are empty by design) is in the guide.

Serialization & metadata

to_bytes / from_bytes round-trip an index; the serialize() builder adds the optional pieces — one opaque payload blob per item and descriptive metadata (coordinate reference system, payload content type, attribution):

# use packed_spatial_index::{Box2D, Index2DBuilder, read_metadata};
# let mut b = Index2DBuilder::new(1);
# b.add(Box2D::new(0.0, 0.0, 1.0, 1.0));
# let index = b.finish()?;
let bytes = index
    .serialize()
    .crs("EPSG:4326")
    .payloads(&[b"feature-0".as_slice()])
    .to_bytes()?;

// Read the metadata back without loading the index.
assert_eq!(read_metadata(&bytes)?.crs.as_deref(), Some("EPSG:4326"));
# Ok::<(), Box<dyn std::error::Error>>(())

The metadata is opaque (the crate stores the strings you give it, verbatim). Pair query results with their payloads via the zero-copy views or the streaming reader — see Persistence and the binary format.

When every record is the same size, .records(stride, ..) (or .triangles(..) for Triangle2D / Triangle3D, and the compact Triangle2DF32 / Triangle3DF32) stores a fixed-width payload: no offset table, so the file is smaller, a streamed query reads one fewer time, and a view can borrow the records as a zero-copy typed slice. A triangle payload plus the index over each triangle's bounding box (Index3D::from_triangles) is a streamable mesh BVH; raycast finds candidates and Ray3D::closest_triangle does the exact hit (the f32 records test 8 at a time with simd). See the raycast_mesh example.

For half the box bytes in memory and on the wire, build the same thing on the compact f32 index: Index3DF32::from_triangles(..).serialize().triangles(..) then stream it with StreamIndex3DF32 — f32-storage alone, no simd needed. The stored f32 boxes are rounded outward, so range and ray results are a conservative superset; search_exact refines them against your f64 boxes.

Features

Serialization, metadata, and the scalar indexes are always available — no feature required.

cargo build --no-default-features                      # minimal: scalar + serialize + metadata
cargo build --no-default-features --features simd      # SIMD only

Documentation

• Guide — recipes, choosing a query method, builder configuration, examples, WASM demo.
• Persistence — serialize / load / zero-copy views, querying large or on-disk indexes via mmap, and streaming queries over a RangeReader (local file or remote object).
• Performance — benchmarks vs static_aabb2d_index, FlatGeobuf, and the bvh crate.
• Binary format — the PSINDEX on-disk layout.
• API reference — docs.rs/packed_spatial_index.

Limitations

• Static: rebuild when the dataset changes; no insert/delete.
• Results are item indices, not stored payloads; result order is unspecified.
• f32-storage indexes store outward-rounded boxes — plain range search may return extra near-boundary hits; use search_exact / neighbors_exact (with your source f64 boxes) for exact results, and prefer f64 indexes for exact queries with many hits.

Safety

The public API is safe Rust; unsafe is confined to narrow, audited paths (validated unaligned reads, repr(C) bulk copies, gated x86-64 SIMD). Serialized input is treated as untrusted: the in-memory loaders validate the whole buffer before use, and the streaming reader validates pointers and payload offsets as it follows them, with per-query cost limits to bound broad queries. See SAFETY.md for the memory-safety and untrusted-input hardening details.

Status

Pre-1.0: the API and on-disk format may still change between minor releases. The crate is covered by unit, property and fuzz tests across the feature matrix, but it has not yet been proven in production. Validate it for your workload before you depend on it.

Feedback

Built something with it? I'd love to hear about it! Start a discussion with your use case, your numbers or any rough edges, and file an issue for bugs. Real-world reports are what push it toward 1.0.

AI usage note

AI assistance is part of my development process for this project. I guide the architecture, review generated output carefully, and take responsibility for the crate as published.

License

Licensed under the Apache License, Version 2.0.