flat_spatial

flat_spatial is a crate dedicated to dynamic spatial partitioning structures that are not based on trees (which are recursive) but on simple flat structures such as a grid/hashmap of cells.
Using grids or other flat structures makes for very fast updates (constant time) and even fast queries, provided the cell size is adapted to the problem.

DenseGrid

The idea of a dense grid is to have an array of cells which store the positions of the inserted objects.
Performing queries is as simple as looking up which cells are affected and returning their associated objects.
Since it's so simple, the dense grid supports dynamic capabilities such as position update or object removal based on handles (using slotmap).

It is recommended to have queries roughly the same size as the cell size.

SparseGrid

The SparseGrid is very similar to the DenseGrid, only that it uses a HashMap of cells instead of a vector. That way, unused space has zero overhead and no reallocation is necessary when points get out of the boundary, only when the HashMap runs out of space.

On the flip side, this makes queries/maintaining slightly slower since positions need to be hashed to find the corresponding cell.

Benchmarks

Here's some basic benchmarks of densegrid vs rstar's r-trees using criterion:

The first one adds 100'000 random points on a 500x500 square and perform n random queries of radius 5.

denseGridN means the structure is a DenseGrid where cells are of size N.

Time is shown per query, lower is better:

The second benchmark tries to change the position of n objects in a 500x500 square.

For an r-tree, it means building it up from scratch.
For a DenseGrid, set_position is used on all handles with a new random position then maintain() is called.

Time is shown per object, lower is better:

Note: In both benchmarks, r-trees and densegrids are linear in number of objects/queries. That's why it makes sense to show the average time per object/per query.

Example

Here is a very basic example of densegrid:

fn main() {
    use flat_spatial::DenseGrid;
    
    let mut g: DenseGrid<()> = DenseGrid::new(10);
    let a = g.insert([3.0, 3.0], ());
    let _b = g.insert([12.0, -8.0], ());
    
    let around: Vec<_> = g.query_around([2.0, 2.0], 5.0)
                          .map(|(id, _pos)| id)
                          .collect();
     
    assert_eq!(vec![a], around);
}