Expand description
Spatial indexing for efficient geometric queries.
Provides a simple linear-scan spatial index suitable for small to medium object counts (<1000). For larger datasets, consumers should implement tree-based structures (BVH, R-tree, Octree) using the same API patterns.
§Design
The spatial index is deliberately simple: a flat Vec of (key, AABB) pairs
with linear-scan queries. This outperforms tree-based structures for small N
due to cache locality and zero overhead.
For larger N (>1000), tree-based indices amortize O(log n) queries, but for typical bin-packing/nesting instances (10-500 items), linear scan wins.
§References
- Ericson (2005), “Real-Time Collision Detection”, Ch. 6 (BVH)
- Akenine-Möller et al. (2018), “Real-Time Rendering”, Ch. 25.1 (Spatial Indexing)
Structs§
- Spatial
Index2D - A linear-scan 2D spatial index.
- Spatial
Index3D - A linear-scan 3D spatial index.