packed_spatial_index 0.7.0

Packed static spatial index (Hilbert R-tree) for 2D/3D AABBs — SIMD range, kNN, raycast, and spatial-join queries, with zero-copy and streaming serialization.
Documentation

packed_spatial_index

crates.io docs.rs Rust CI MSRV License

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

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

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 query exists on Index2D / Index3D, the simd-feature SimdIndex2D / SimdIndex3D, and the zero-copy views. Range/ray results are item indices in insertion order; result order is unspecified. See docs.rs for full per-method docs.

Query Methods
Range / intersection search, search_iter, search_into, search_with, any, first, visit
Nearest neighbors (point) neighbors, neighbors_within, neighbors_into, neighbors_with, visit_neighbors
Nearest neighbors (box) neighbors_of_box, neighbors_of_box_within, neighbors_of_box_into, neighbors_of_box_with, visit_neighbors_of_box
Ray segment raycast, raycast_into, raycast_with, raycast_closest, raycast_closest_with, visit_raycast
Spatial join join, join_with, self_join, self_join_with
Extent / exact extent, and search_exact / neighbors_exact on the f32 indexes 
# 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

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.

Features

Feature Pulls in Adds
parallel (default) rayon adaptive parallel index builds
simd (default) wide SoA indexes + SIMD search / raycast (AVX2 / AVX-512)
f32-storage (implies simd) compact f32-storage SIMD indexes
stream — query a serialized index over a RangeReader (local file or remote object) without loading it whole
async futures-util (implies stream) query over an AsyncRangeReader (browser / edge worker, HTTP range or object storage)
bench-internals — hidden support API for this crate's benchmarks

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.