Struct flat_spatial::grid::Grid
source · pub struct Grid<O, V2: Vec2> { /* private fields */ }
Expand description
Grid is a point-based spatial partitioning structure that uses a generic storage of cells which acts as a grid instead of a tree.
Fast queries
In theory, Grid should be faster than a quadtree/r-tree because it has no log costs
(calculating the cells around a point is trivial).
However, it only works if the cell size is adapted to the problem, much like how a tree has to
be balanced to be efficient.
Dynamicity
Grid’s big advantage is that it is dynamic, supporting lazy positions updates and object removal in constant time. Once objects are in, there is almost no allocation happening.
Compare that to most immutable spatial partitioning structures out there, which pretty much require to rebuild the entire tree every time.
A SlotMap
is used for objects managing, adding a level of indirection between points and objects.
SlotMap
is used because removal doesn’t alter handles given to the user, while still having constant time access.
However it requires O to be copy, but SlotMap's
author stated that they were working on a similar
map where Copy isn’t required.
About object management
In theory, you don’t have to use the object management directly, you can make your custom
Handle -> Object map by specifying “()
” to be the object type.
(This can be useful if your object is not Copy)
Since ()
is zero sized, it should probably optimize away a lot of the object management code.
Examples
Here is a basic example that shows most of its capabilities:
use flat_spatial::Grid;
let mut g: Grid<i32, [f32; 2]> = Grid::new(10); // Creates a new grid with a cell width of 10 with an integer as extra data
let a = g.insert([0.0, 0.0], 0); // Inserts a new element with data: 0
{
let mut before = g.query_around([0.0, 0.0], 5.0).map(|(id, _pos)| id); // Queries for objects around a given point
assert_eq!(before.next(), Some(a));
assert_eq!(g.get(a).unwrap().1, &0);
}
let b = g.insert([0.0, 0.0], 1); // Inserts a new element, assigning a new unique and stable handle, with data: 1
g.remove(a); // Removes a value using the handle given by `insert`
// This won't have an effect until g.maintain() is called
g.maintain(); // Maintains the grid, which applies all removals and position updates (not needed for insertions)
assert_eq!(g.handles().collect::<Vec<_>>(), vec![b]); // We check that the "a" object has been removed
let after: Vec<_> = g.query_around([0.0, 0.0], 5.0).map(|(id, _pos)| id).collect(); // And that b is query-able
assert_eq!(after, vec![b]);
assert_eq!(g.get(b).unwrap().1, &1); // We also check that b still has his data associated
assert_eq!(g.get(a), None); // But that a doesn't exist anymore
Implementations§
source§impl<O: Copy, V2: Vec2> Grid<O, V2>
impl<O: Copy, V2: Vec2> Grid<O, V2>
sourcepub fn new(cell_size: i32) -> Self
pub fn new(cell_size: i32) -> Self
Creates an empty grid.
The cell size should be about the same magnitude as your queries size.
sourcepub fn insert(&mut self, pos: V2, obj: O) -> GridHandle
pub fn insert(&mut self, pos: V2, obj: O) -> GridHandle
Inserts a new object with a position and an associated object
Returns the unique and stable handle to be used with get_obj
sourcepub fn set_position(&mut self, handle: GridHandle, pos: V2)
pub fn set_position(&mut self, handle: GridHandle, pos: V2)
Lazily sets the position of an object (if it is not marked for deletion). This won’t be taken into account until maintain() is called.
sourcepub fn remove(&mut self, handle: GridHandle) -> Option<O>
pub fn remove(&mut self, handle: GridHandle) -> Option<O>
Lazily removes an object from the grid. This won’t be taken into account until maintain() is called.
Example
use flat_spatial::Grid;
let mut g: Grid<(), [f32; 2]> = Grid::new(10);
let h = g.insert([5.0, 3.0], ());
g.remove(h);
sourcepub fn remove_maintain(&mut self, handle: GridHandle) -> Option<O>
pub fn remove_maintain(&mut self, handle: GridHandle) -> Option<O>
Directly removes an object from the grid. This is equivalent to remove() then maintain() but is much faster (O(1))
Example
use flat_spatial::Grid;
let mut g: Grid<(), [f32; 2]> = Grid::new(10);
let h = g.insert([5.0, 3.0], ());
g.remove(h);
sourcepub fn clear(&mut self) -> impl Iterator<Item = (V2, O)>
pub fn clear(&mut self) -> impl Iterator<Item = (V2, O)>
Clear all objects from the grid. Returns the objects and their positions.
sourcepub fn maintain(&mut self)
pub fn maintain(&mut self)
Maintains the world, updating all the positions (and moving them to corresponding cells) and removing necessary objects and empty cells. Runs in linear time O(N) where N is the number of objects.
Example
use flat_spatial::Grid;
let mut g: Grid<(), [f32; 2]> = Grid::new(10);
let h = g.insert([5.0, 3.0], ());
g.remove(h);
assert!(g.get(h).is_some());
g.maintain();
assert!(g.get(h).is_none());
sourcepub fn handles(&self) -> impl Iterator<Item = GridHandle> + '_
pub fn handles(&self) -> impl Iterator<Item = GridHandle> + '_
Iterate over all handles
sourcepub fn get(&self, id: GridHandle) -> Option<(V2, &O)>
pub fn get(&self, id: GridHandle) -> Option<(V2, &O)>
Returns a reference to the associated object and its position, using the handle.
Example
use flat_spatial::Grid;
let mut g: Grid<i32, [f32; 2]> = Grid::new(10);
let h = g.insert([5.0, 3.0], 42);
assert_eq!(g.get(h), Some(([5.0, 3.0], &42)));
sourcepub fn get_mut(&mut self, id: GridHandle) -> Option<(V2, &mut O)>
pub fn get_mut(&mut self, id: GridHandle) -> Option<(V2, &mut O)>
Returns a mutable reference to the associated object and its position, using the handle.
Example
use flat_spatial::Grid;
let mut g: Grid<i32, [f32; 2]> = Grid::new(10);
let h = g.insert([5.0, 3.0], 42);
*g.get_mut(h).unwrap().1 = 56;
assert_eq!(g.get(h).unwrap().1, &56);
sourcepub fn storage(&self) -> &SparseStorage<GridCell<V2>>
pub fn storage(&self) -> &SparseStorage<GridCell<V2>>
The underlying storage
pub fn query_around( &self, pos: V2, radius: f32 ) -> impl Iterator<Item = CellObject<V2>> + '_
pub fn query_aabb( &self, ll_: V2, ur_: V2 ) -> impl Iterator<Item = CellObject<V2>> + '_
pub fn query_aabb_visitor( &self, ll_: V2, ur_: V2, visitor: impl FnMut(CellObject<V2>) )
sourcepub fn query(&self, ll: V2, ur: V2) -> impl Iterator<Item = CellObject<V2>> + '_
pub fn query(&self, ll: V2, ur: V2) -> impl Iterator<Item = CellObject<V2>> + '_
Queries for all objects in the cells intersecting an axis-aligned rectangle defined by lower left (ll) and upper right (ur) Try to keep the rect’s width/height of similar magnitudes to the cell size for better performance.
Example
use flat_spatial::Grid;
let mut g: Grid<(), [f32; 2]> = Grid::new(10);
let a = g.insert([0.0, 0.0], ());
let b = g.insert([5.0, 5.0], ());
let around: Vec<_> = g.query([-1.0, -1.0].into(), [1.0, 1.0].into()).map(|(id, _pos)| id).collect();
assert_eq!(vec![a, b], around);
sourcepub fn query_visitor(&self, ll: V2, ur: V2, visitor: impl FnMut(CellObject<V2>))
pub fn query_visitor(&self, ll: V2, ur: V2, visitor: impl FnMut(CellObject<V2>))
query_visitor is similar to query, but uses a visitor function to be slightly more performant.