API Documentation

The sparse_spatial_hash library provides a high-performance spatial indexing data structure for C++20. It divides space into a grid of cells and uses a hash map to store only occupied cells, making it memory-efficient for large, sparse worlds.

Core Classes

`grid_config<N>`

Configuration structure for spatial grids.

Field	Type	Description
`cell_size`	`std::array<float, N>`	Size of each cell in each dimension
`world_size`	`std::array<float, N>`	Total world size in each dimension
`topology_type`	`topology`	Boundary behavior (bounded, toroidal, infinite)

grid_config<3> cfg{
    .cell_size = {10.0f, 10.0f, 10.0f},
    .world_size = {1000.0f, 1000.0f, 1000.0f},
    .topology_type = topology::bounded
};

`sparse_spatial_hash<Entity, N>`

The main grid class for spatial indexing.

Template Parameters:

Parameter	Description
`Entity`	Your entity type (e.g., `Particle`, `GameObject`)
`N`	Number of dimensions (typically 2 or 3)
`Float`	Floating-point type (default: `float`)
`Index`	Index type (default: `std::size_t`)
`Hash`	Cell hash function (default: `cell_hash<N>`)
`Allocator`	Allocator type (default: `std::allocator`)

`position_accessor<Entity, N>`

Trait for extracting position from your entity type.

template<>
struct spatial::position_accessor<Particle, 3> {
    static float get(const Particle& p, std::size_t dim) {
        switch(dim) {
            case 0: return p.x;
            case 1: return p.y;
            case 2: return p.z;
            default: return 0.0f;
        }
    }
};

Note: If your entity stores position as std::array<float, N>, the default implementation works automatically.

Topology Types

Type	Behavior	Use Case
`topology::bounded`	Coordinates clamped to `[0, world_size]`	Rooms, arenas, bounded worlds
`topology::toroidal`	Coordinates wrap around (periodic)	N-body simulations, Pac-Man-style worlds
`topology::infinite`	No bounds checking, grid grows	Procedural worlds, expanding universes

Core Operations

Building the Grid

Method	Complexity	Description
`rebuild(entities)`	O(n)	Full rebuild from entity container
`update(entities)`	O(k)	Incremental update (k = entities that changed cells)
`clear()`	O(1)	Remove all entities

Querying

Method	Description
`query_radius(r, x, y, z)`	Returns indices of entities in cells intersecting query sphere
`query_cell(cx, cy, cz)`	Returns indices of entities in specific cell
`for_each_pair(entities, radius, callback)`	Invokes callback for all pairs within radius

Important: query_radius returns candidates - entities in cells that intersect the query sphere. Always filter by exact distance for precision:

auto candidates = grid.query_radius(radius, x, y, z);
for (auto idx : candidates) {
    float dist = compute_distance(entities[idx], query_point);
    if (dist < radius) {
        // True neighbor
    }
}

Statistics

Method	Description
`entity_count()`	Total entities in grid
`cell_count()`	Number of occupied cells
`stats()`	Returns `grid_stats` with detailed metrics

auto stats = grid.stats();
// stats.occupied_cells
// stats.avg_entities_per_cell
// stats.occupancy_ratio
// stats.max_entities_in_cell

Performance Characteristics

Operation	Complexity	Typical Performance
Build	O(n)	14.7M entities/second
Incremental Update	O(k)	29.2M entities/second
Query Radius	O(cells × entities/cell)	Sub-microsecond for typical queries
For Each Pair	O(n × avg_neighbors)	Optimized for collision detection

Memory Usage

Sparse storage: Only occupied cells use memory
Typical: 100MB for 10M particles in 10000³ world
Comparison: 60,000× less memory than equivalent dense grid

Full Reference

For complete API documentation with all method signatures and complexity guarantees: