packed_spatial_index 0.5.1

Packed static spatial index for 2D and 3D AABBs with Hilbert ordering, adaptive parallel builds, and SIMD queries.
Documentation

packed_spatial_index

crates.io docs.rs Rust CI MSRV License

A fast, packed static spatial index for 2D and 3D axis-aligned bounding boxes (AABBs). It builds a packed Hilbert R-tree (in the style of flatbush / static_aabb2d_index) once, then answers many queries: range / intersection search, nearest-neighbor (kNN) from a point or a box, ray casts, and spatial joins. With the simd feature the SoA indexes use AVX2 / AVX-512 intersection tests; indexes also serialize to a stable byte format with zero-copy views (mmap-friendly).

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

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().

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_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

Features

  • parallel (default) — adaptive rayon-based parallel builds.
  • simd (default) — SoA indexes and SIMD search/raycast (wide + AVX-512).
  • f32-storage — compact f32-storage SIMD indexes (implies simd).
  • bench-internals — hidden support API for this crate's benchmarks.
cargo build --no-default-features                      # minimal
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, and querying large or on-disk indexes via mmap.
  • 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. Internally unsafe is confined to narrow, audited paths: validated unaligned little-endian reads in the byte views, bulk repr(C) byte copies during serialization on little-endian targets, and runtime-feature-gated x86-64 SIMD (AVX-512) loads/prefetch. Loaded buffers are validated before use, so malformed input returns LoadError rather than relying on caller invariants.

Status

Major API changes are not planned, but remain possible before a 1.0 release.

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.