Crate packed_spatial_index

Expand description

Packed static spatial index for 2D and 3D axis-aligned bounding boxes.

The canonical flow is Index2DBuilder -> Index2D -> Index2D::search. With the simd feature, Index2DBuilder::finish_simd and Index3DBuilder::finish_simd build SimdIndex2D and SimdIndex3D, which share the same query API backed by SoA layouts and SIMD traversal. Indexes also serialize with to_bytes and load back as owned indexes or as zero-copy views (Index2DView, Index3DView).

§Queries

Every query is a method on the index types (Index2D / Index3D, the SIMD indexes, and the zero-copy views), so docs.rs lists them on each type’s page (e.g. Index2D); the only crate-level free items are small distance helpers such as haversine_distance_2d. Range and ray results are item indices in insertion order.

Range / intersection — search (plus search_into / search_with / lazy search_iter), any, first, visit.
Nearest neighbors — from a point neighbors (plus _within / _into / _with / visit_neighbors) or from a box neighbors_of_box and its variants; or under a custom distance metric with neighbors_metric (e.g. great-circle distance via haversine_distance_2d).
Ray segment — raycast (all hits), raycast_closest (nearest box entered), and visit_raycast.
Spatial join — join / join_with between two indexes, self_join / self_join_with within one.
Region / culling — prune to a non-box shape instead of its bounding box: 2D triangle search_triangle and convex polygon search_polygon on Index2D, 3D view frustum search_frustum on Index3D (each with any_* / visit_* / _into, and on the zero-copy Index2DView / Index3DView).

§Quick Start

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

assert_eq!(index.search(Box2D::new(0.0, 0.0, 2.0, 2.0)), vec![0]);

§Cargo Features

parallel (default): adaptive parallel builds through rayon.
simd (default): SIMD search/raycast through wide and x86-64 AVX-512.
f32-storage: compact f32-storage SIMD indexes.
stream: query a serialized index over a RangeReader (local file or remote object) without loading the whole file. No extra dependencies.
async: query over an AsyncRangeReader for async I/O sources (browser / edge worker over HTTP range or object storage). Implies stream.

Structs§

Box2D: Axis-aligned 2D box stored as (min_x, min_y, max_x, max_y).
Box3D: Axis-aligned 3D box stored as (min_x, min_y, min_z, max_x, max_y, max_z).
ConvexPolygon2D: A convex polygon in 2D, given as vertices in order (CW or CCW). The query predicates assume convexity; a non-convex polygon yields unspecified results.
FileMetadata: Descriptive metadata read from a file’s META chunk. Every field is an opaque string the writer supplied; this crate does not interpret them (e.g. the CRS is whatever identifier the producer chose, such as "EPSG:4326").
FileReaderstream and (Unix or Windows): A RangeReader over a local file using positioned reads.
Frustum3D: A 3D frustum as six inward-pointing half-space planes.
Index2D: Finished static read-only index.
Index2DBuilder: Builder for Index2D and, with the simd feature, SimdIndex2D.
Index2DF32f32-storage: Compact scalar f32-storage 2D index: the same outward-rounded f32 boxes as SimdIndex2DF32 (half the box memory of Index2D), queried without SIMD. Built natively in f32 (no transient f64 tree). Range and ray results are a conservative superset of the f64 index (every exact hit, plus a few near-boundary false positives from outward rounding).
Index2DView: Zero-copy read-only view over bytes produced by Index2D::to_bytes.
Index3D: Finished static read-only 3D index.
Index3DBuilder: Builder for Index3D and, with the simd feature, SimdIndex3D.
Index3DF32f32-storage: Compact scalar f32-storage 3D index: the same outward-rounded f32 boxes as SimdIndex3DF32 (half the box memory of Index3D), queried without SIMD. Built natively in f32 (no transient f64 tree), so peak build memory is the f32 tree, not f64. Range and ray results are a conservative superset of the f64 index (every exact hit, plus a few near-boundary false positives from the outward rounding).
Index3DView: Zero-copy read-only view over bytes produced by Index3D::to_bytes.
NeighborWorkspace: Reusable buffers for allocation-free repeated nearest-neighbor searches.
Point2D: 2D point used by nearest-neighbor searches.
Point3D: 3D point used by nearest-neighbor searches.
Ray2D: Finite 2D ray segment used by raycast searches.
Ray3D: Finite 3D ray segment used by raycast searches.
Search2DIter: Lazy iterator over the items intersecting a query box, returned by Index2D::search_iter.
Search3DIter: Lazy iterator over the items intersecting a query box, returned by Index3D::search_iter.
SearchWorkspace: Reusable buffers for allocation-free repeated searches.
Serializer2D: Builder for Index2D serialization, created by Index2D::serialize.
Serializer2DF32f32-storage: Serialization builder for Index2DF32, created by Index2DF32::serialize. Writes f32 box records plus an optional per-item payload and descriptive metadata; the f32-box counterpart of Serializer2D.
Serializer3D: Builder for Index3D serialization, created by Index3D::serialize. The 3D counterpart of Serializer2D: optional per-item payloads, the streaming-tuned interleaved layout, and descriptive metadata (CRS / content type / attribution), read back with read_metadata.
Serializer3DF32f32-storage: Serialization builder for Index3DF32, created by Index3DF32::serialize. Writes f32 box records plus an optional per-item payload and descriptive metadata; the f32-box counterpart of Serializer3D.
SimdIndex2Dsimd: Finished read-only SIMD index.
SimdIndex2DF32f32-storage and simd: Finished read-only f32-storage SIMD index.
SimdIndex2DF32Viewf32-storage and simd: Zero-copy read-only view over bytes produced by SimdIndex2DF32::to_bytes.
SimdIndex2DViewsimd: Zero-copy SIMD view over bytes produced by SimdIndex2D::to_bytes or Index2D::to_bytes.
SimdIndex3Dsimd: Finished read-only SIMD 3D index.
SimdIndex3DF32f32-storage and simd: Finished read-only f32-storage 3D SIMD index.
SimdIndex3DF32Viewf32-storage and simd: Zero-copy read-only view over bytes produced by SimdIndex3DF32::to_bytes.
SimdIndex3DViewsimd: Zero-copy SIMD view over bytes produced by SimdIndex3D::to_bytes or Index3D::to_bytes.
SliceReaderstream: A RangeReader over an in-memory byte buffer (&[u8], Vec<u8>, a memory map, …). Reads are bounds-checked copies out of the buffer.
StreamDirectorystream: A reusable, reader-independent streaming directory.
StreamIndex2Dstream: Streaming reader for a 2D f64 packed spatial index.
StreamIndex2DF32stream: Streaming reader for a compact f32 2D index — the bytes of SimdIndex2DF32 / Index2DF32. Half the box bytes on the wire of StreamIndex2D; results are a conservative superset (the stored f32 boxes are rounded outward). Behind the stream feature.
StreamIndex3Dstream: Streaming reader for a 3D f64 packed spatial index.
StreamIndex3DF32stream: Streaming reader for a compact f32 3D index. The 3D counterpart of StreamIndex2DF32 (24-byte box record). Behind the stream feature.
StreamLimitsstream: Per-query cost limits for a streaming index.
Triangle2D: A 2D triangle: three vertices [x, y]. repr(C), unpadded, so a slice casts to and from the on-disk fixed-width payload with no copy.
Triangle2DF32: A 2D triangle: three vertices [x, y]. repr(C), unpadded, so a slice casts to and from the on-disk fixed-width payload with no copy.
Triangle3D: A 3D triangle: three vertices [x, y, z]. repr(C), unpadded, so a slice casts to and from the on-disk fixed-width payload with no copy.
Triangle3DF32: A 3D triangle: three vertices [x, y, z]. repr(C), unpadded, so a slice casts to and from the on-disk fixed-width payload with no copy.
TriangleHit: A ray-triangle intersection: the index of the hit triangle in the queried slice, and the ray parameter t in direction-length units (the same t convention as crate::Ray3D). Returned by crate::Ray3D::closest_triangle.

Enums§

BoundsError: Error returned by Box2D::try_new and Box3D::try_new for invalid coordinate bounds.
BuildError: Build error for finishing an index.
ClipSpaceZ: The normalized-device-coordinate depth range a projection matrix targets, for Frustum3D::from_view_projection. D3D12, Vulkan, Metal and WebGPU clip z to [0, 1] (the modern default); OpenGL and WebGL clip it to [-1, 1]. Only the near plane differs between the two conventions. There is deliberately no silent default on the constructor — the convention is not recoverable from the matrix, so every caller states it — but ClipSpaceZ::default() is the modern ZeroToOne if you need one.
LoadError: Error returned when loading an index from bytes.
PayloadError: Error returned when serializing an index together with item payloads.
SortKey2D: Which key to use when sorting boxes before packing the tree.
SortKey3D: Which key to use when sorting 3D boxes before packing the tree.
StreamErrorstream: Error returned by the streaming reader.

Constants§

DEFAULT_NODE_SIZE: Default maximum number of children per tree node.
DEFAULT_PARALLEL_MIN_ITEMSparallel: Minimum index size at which parallel(true) enables rayon.
EARTH_RADIUS_M: Mean Earth radius in meters (IUGG), a reasonable default for haversine_distance_2d.

Traits§

AsyncRangeReaderasync and stream: Async counterpart of RangeReader: read a byte range, returning a future.
RangeReaderstream: A source of bytes addressable by absolute offset.
Triangle2: A 2D triangle record (f64 or f32 vertices). Implemented by Triangle2D and Triangle2DF32; sealed, so the set of record types is fixed.
Triangle3: A 3D triangle record (f64 or f32 vertices). Implemented by Triangle3D and Triangle3DF32; sealed, so the set of record types is fixed.

Functions§

haversine_distance_2d: Great-circle (haversine) distance in meters from a (lon, lat) query point (degrees) to the closest point of bounds, a lon/lat AABB in degrees.
read_metadata: Read the optional descriptive metadata from a serialized index, without loading the index. Returns an empty FileMetadata when there is no META chunk.