# packed_spatial_index
[](https://github.com/Filyus/packed_spatial_index/actions/workflows/ci.yml)
[](https://crates.io/crates/packed_spatial_index)
[](https://docs.rs/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.
```rust
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.
```toml
[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 persisted SoA byte format.
- 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`,
`contains_point`, and `from_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.
## Querying
Searches take a `Box2D` or `Box3D` and return indices into the item list you
added to the builder. Result order is intentionally unspecified.
### `search`
Allocates a fresh `Vec<usize>` and returns all overlaps. This is the simplest
choice for one-off queries.
```rust
# use packed_spatial_index::{Box2D, Index2DBuilder};
# 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>(())
```
### `search_into`
Reuses your result `Vec`, clearing it before writing new hits.
```rust
# use packed_spatial_index::{Box2D, Index2DBuilder};
# 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 mut results = Vec::new();
index.search_into(Box2D::new(0.0, 0.0, 2.0, 2.0), &mut results);
assert_eq!(results, vec![0]);
# Ok::<(), packed_spatial_index::BuildError>(())
```
### `search_with`
Reuses both the result buffer and the internal traversal stack through a
`SearchWorkspace`. This is the best fit for hot query loops.
```rust
# use packed_spatial_index::{Box2D, Index2DBuilder, SearchWorkspace};
# 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 mut workspace = SearchWorkspace::new();
let hits = index.search_with(Box2D::new(0.0, 0.0, 2.0, 2.0), &mut workspace);
assert_eq!(hits, &[0]);
# Ok::<(), packed_spatial_index::BuildError>(())
```
### `any`
Checks whether at least one item overlaps the query.
```rust
# use packed_spatial_index::{Box2D, Index2DBuilder};
# 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 query = Box2D::new(0.0, 0.0, 2.0, 2.0);
assert!(index.any(query));
# Ok::<(), packed_spatial_index::BuildError>(())
```
### `first`
Returns one matching item index found by traversal.
```rust
# use packed_spatial_index::{Box2D, Index2DBuilder};
# 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 query = Box2D::new(0.0, 0.0, 2.0, 2.0);
assert_eq!(index.first(query), Some(0));
# Ok::<(), packed_spatial_index::BuildError>(())
```
### `visit`
Calls your visitor for each match and lets it stop early with
`ControlFlow::Break`.
```rust
# use packed_spatial_index::{Box2D, Index2DBuilder};
use std::ops::ControlFlow;
#
# 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 query = Box2D::new(0.0, 0.0, 2.0, 2.0);
let first_even = index.visit(query, |item| {
if item % 2 == 0 {
ControlFlow::Break(item)
} else {
ControlFlow::Continue(())
}
});
assert_eq!(first_even, ControlFlow::Break(0));
# Ok::<(), packed_spatial_index::BuildError>(())
```
### `extent`
`extent()` returns the total box covering every item, or `None` for an empty
index.
```rust
# use packed_spatial_index::{Box2D, Index2DBuilder};
# 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()?;
assert_eq!(index.extent(), Some(Box2D::new(0.0, 0.0, 6.0, 6.0)));
let empty = Index2DBuilder::new(0).finish()?;
assert_eq!(empty.extent(), None);
# Ok::<(), packed_spatial_index::BuildError>(())
```
### Nearest Neighbors
Nearest-neighbor queries are exact over boxes. Distance is zero when the point is
inside a box, otherwise it is the Euclidean distance to the nearest point on the
box.
### `neighbors`
Returns the nearest item indices with no distance limit.
```rust
# use packed_spatial_index::{Box2D, Index2DBuilder, Point2D};
# 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 point = Point2D::new(5.5, 5.5);
let nearest = index.neighbors(point, 1);
assert_eq!(nearest, vec![1]);
# Ok::<(), packed_spatial_index::BuildError>(())
```
### `neighbors_within`
Returns nearest item indices within a maximum distance.
```rust
# use packed_spatial_index::{Box2D, Index2DBuilder, Point2D};
# 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 point = Point2D::new(5.5, 5.5);
let nearby = index.neighbors_within(point, 8, 2.0);
assert_eq!(nearby, vec![1]);
# Ok::<(), packed_spatial_index::BuildError>(())
```
### `neighbors_into`
Reuses your result `Vec` for repeated KNN queries.
```rust
# use packed_spatial_index::{Box2D, Index2DBuilder, Point2D};
# 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 mut results = Vec::new();
index.neighbors_into(Point2D::new(5.5, 5.5), 4, f64::INFINITY, &mut results);
assert_eq!(results, vec![1, 0]);
# Ok::<(), packed_spatial_index::BuildError>(())
```
### `neighbors_with`
Reuses both result and queue buffers through a `NeighborWorkspace`.
```rust
# use packed_spatial_index::{Box2D, Index2DBuilder, NeighborWorkspace, Point2D};
# 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 mut workspace = NeighborWorkspace::new();
let hits = index.neighbors_with(Point2D::new(5.5, 5.5), 4, f64::INFINITY, &mut workspace);
assert_eq!(hits, &[1, 0]);
# Ok::<(), packed_spatial_index::BuildError>(())
```
### `visit_neighbors`
Visits `(index, distance_squared)` pairs in nearest-first order and can stop
early with `ControlFlow::Break`.
```rust
# use packed_spatial_index::{Box2D, Index2DBuilder, Point2D};
use std::ops::ControlFlow;
#
# 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()?;
ControlFlow::Break(item)
} else {
ControlFlow::Continue(())
}
});
assert_eq!(close, ControlFlow::Break(1));
# Ok::<(), packed_spatial_index::BuildError>(())
```
Results are returned in nondecreasing distance order. Ties between equal-distance
items are not stable across index layouts.
## Common Tasks
### Find boxes that contain a point
Search with a zero-size query box at that point. Box overlap is inclusive, so
items touching the point are included.
```rust
# use packed_spatial_index::{Box2D, Index2DBuilder, Point2D};
# let mut builder = Index2DBuilder::new(2);
# builder.add(Box2D::new(0.0, 0.0, 2.0, 2.0));
# builder.add(Box2D::new(5.0, 5.0, 6.0, 6.0));
# let index = builder.finish()?;
let point = Point2D::new(1.0, 1.0);
assert_eq!(index.search(Box2D::from_point(point)), vec![0]);
# Ok::<(), packed_spatial_index::BuildError>(())
```
For 3D, use `Box3D::from_point(point)` in the same way.
### Keep payloads outside the index
The index returns item indices. Store your own payloads in the same order as the
boxes you add to the builder.
```rust
# use packed_spatial_index::{Box2D, Index2DBuilder};
let payloads = ["park", "station"];
let boxes = [
Box2D::new(0.0, 0.0, 2.0, 2.0),
Box2D::new(5.0, 5.0, 6.0, 6.0),
];
let mut builder = Index2DBuilder::new(boxes.len());
for bounds in boxes {
builder.add(bounds);
}
let index = builder.finish()?;
let names: Vec<_> = index
.search(Box2D::new(0.0, 0.0, 3.0, 3.0))
.into_iter()
.map(|item| payloads[item])
.collect();
assert_eq!(names, vec!["park"]);
# Ok::<(), packed_spatial_index::BuildError>(())
```
### Choose a query method
- Use `search` for simple one-off queries.
- Use `search_with` or `neighbors_with` inside tight loops.
- Use `any`, `first`, `visit`, or `visit_neighbors` when you can stop early.
- Use `Index2DView` or `Index3DView` when loading persisted bytes without
allocating an owned index.
## Builder
```rust
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:
```rust
# 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:
```rust
# 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:
```rust
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:
```rust
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`](FORMAT.md).
## Examples
Runnable examples cover the public paths:
```bash
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
```
## Benchmarking Layout
Performance-related code lives under `benches`:
- `benches/*.rs` are Criterion benchmark suites run with `cargo bench`.
- `benches/tools` is a local developer package for quick comparisons of encoder
variants, sort strategies, node sizes, parallel builds, and SoA layouts.
The local tools use the hidden `bench-internals` feature and are excluded from
the published crate.
```bash
cargo run --release --manifest-path benches/tools/Cargo.toml --bin sortkey_quality_2d
cargo run --release --manifest-path benches/tools/Cargo.toml --bin node_size_3d
```
## Features
Runtime acceleration 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.
- `bench-internals`: hidden support API for this crate's own benchmarks and
local performance tools. It is not enabled by default and is not part of the
stable user-facing API.
Minimal build:
```bash
cargo build --no-default-features
```
SIMD-only or parallel-only builds:
```bash
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/performance-tool 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.
| Full build | 70.18 ms | 8.95 ms | 3.18 ms serial / 2.20 ms parallel | - |
| Search batch | 555.83 us | 341.56 us | 416.15 us | 128.64 us |
| Serialize built tree (fresh buffer) | - | - | 407.64 us | 689.42 us |
| Serialize built tree (reused buffer) | 131.93 us | - | 68.78 us | 140.21 us |
| Load owned tree | 740.23 us | - | 607.62 us | 935.51 us |
| Load zero-copy view | - | - | 37.59 us | n/a |
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:
| `flatgeobuf2d_bench`, seed `0xF6B` | 341.56 us | 416.15 us | 128.64 us |
| `index2d_bench`, seed `0xB0B` | 643.85 us | 311.72 us | 126.21 us |
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.
| Hilbert encode | production 2D LUT vs 3D nibble LUT | 739.90 us | 983.42 us | 0.75x |
| Build | planar XY | 2.7433 ms | 4.5660 ms | 0.60x |
| Build | uniform XYZ | 3.4270 ms | 5.1252 ms | 0.67x |
| Search batch | planar XY | 466.41 us | 636.37 us | 0.73x |
| Search batch | uniform XYZ | 495.82 us | 391.32 us | 1.27x |
| Top-1 | planar XY | 973.85 us | 1.2445 ms | 0.78x |
| Top-10 | planar XY | 1.9378 ms | 2.5625 ms | 0.76x |
| Top-1 | uniform XYZ | 1.0028 ms | 1.8530 ms | 0.54x |
| Top-10 | uniform XYZ | 2.0221 ms | 4.1143 ms | 0.49x |
| Serialize built tree (fresh buffer) | 407.64 us | 562.55 us | 0.72x |
| Serialize built tree (reused buffer) | 68.78 us | 96.51 us | 0.71x |
| Load owned tree | 607.62 us | 819.04 us | 0.74x |
| Load zero-copy view | 37.59 us | 37.66 us | 1.00x |
| Serialize built tree (fresh buffer) | 689.42 us | 973.17 us | 0.71x |
| Serialize built tree (reused buffer) | 140.21 us | 240.51 us | 0.58x |
| Load owned tree | 935.51 us | 1.3083 ms | 0.72x |
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.
| Search batch | uniform XYZ | `Index3D` 389.13 us | `SimdIndex3D` 129.08 us | 3.01x |
| Search batch | flat Z | `Index3D` 1.8443 ms | `SimdIndex3D` 1.1514 ms | 1.60x |
| Build `finish_simd` | uniform XYZ, 200k boxes | serial 10.632 ms | parallel 6.5412 ms | 1.63x |
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:
```bash
cargo bench --bench index2d_bench --no-default-features --features parallel,simd,bench-internals
cargo bench --bench index3d_bench --no-default-features --features parallel,simd,bench-internals
cargo bench --bench persistence_knn2d_bench --no-default-features --features simd,bench-internals
cargo bench --bench persistence_knn3d_bench --no-default-features --features simd,bench-internals
cargo bench --bench flatgeobuf2d_bench --no-default-features --features parallel,simd,bench-internals
```
## 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.