flat_spatial

KO | EN

gitlite — search

#python #hacktoberfest #react #ai #typescript #llm #android #deep-learning #linux #awesome #awesome-list #mcp #openai #open-source

(★ 37)

Flat spatial partitionning data structures in Rust

flat_spatial Latest Version Download

Download Latest Version (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# flat_spatial

[![Build Status](https://github.com/Uriopass/flat_spatial/workflows/Rust/badge.svg?branch=master)](https://github.com/Uriopass/flat_spatial/actions)
[![Crates.io](https://img.shields.io/crates/v/flat_spatial.svg)](https://crates.io/crates/flat_spatial)
[![Docs.rs](https://docs.rs/flat_spatial/badge.svg)](https://docs.rs/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 of cells (also called bins).  
Using grids or other flat structures makes for very fast updates (constant time) and
even faster queries, provided the cell size is adapted to the problem.

Picking the right cell size is very important:
 - If the cell size is too small, the grid will be too fine and the
   queries will be slow as they need to iterate over all matching cells.
 - If the cell size is too big, the grid will be too coarse and the
   queries will be slow as they need to iterate over all matching objects.

Try to pick a cell size that gives an average of 10-20 objects per cell on average.
Note that empty cells don't consume any memory, but they do consume some query time as we need to check if they exist.

MSRV: 1.60

## Grid

![](https://i.imgur.com/2rkQbxB.png)

The idea of a grid is to have a HashMap 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 grid supports dynamic capabilities such as position update
or object removal based on handles (using `slotmap`).
The position updates are lazy for better performance, so maintain() needs to be called to update the grid.

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

## AABBGrid

The aabbgrid is like a grid but it stores Axis-Aligned Bounding Boxes (AABB) instead of positions.
This implemented as a HashMap of cells which store the AABB that touches it.
For each cell an AABB touches, it is added to the cell. Try to keep the aabb sizes as small as possible.

Adding/updating/removing isn't lazy, no need to call maintain.

### Example

Here is a very basic example of the grid:

```Rust
fn main() {
    use flat_spatial::Grid;
    
    let mut g: Grid<(), [f32; 2]> = Grid::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);
}
```

flat_spatial

flat_spatial Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

flat_spatial

flat_spatial Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Download README