Struct flat_spatial::aabbgrid::AABBGrid
source · pub struct AABBGrid<O: Copy, AB: AABB> { /* private fields */ }
Expand description
AABBGrid
is a generic aabb-based spatial partitioning structure that uses a generic storage of cells which acts as a
grid instead of a tree.
Fast queries
In theory, AABBGrid
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
AABBGrid's
allows eager removals and position updates, however for big aabbs (spanning many cells)
this can be expensive, so beware.
Use this grid for mostly static objects with the occasional removal/position update if needed.
A SlotMap
is used for objects managing, adding a level of indirection between aabbs 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.
use flat_spatial::AABBGrid;
use euclid::default::Rect;
let mut g: AABBGrid<(), Rect<f32>> = AABBGrid::new(10);
let handle = g.insert(Rect::new([0.0, 0.0].into(), [10.0, 10.0].into()), ());
// Use handle however you want
Implementations§
source§impl<O: Copy, AB: AABB> AABBGrid<O, AB>
impl<O: Copy, AB: AABB> AABBGrid<O, AB>
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, aabb: AB, obj: O) -> AABBGridHandle
pub fn insert(&mut self, aabb: AB, obj: O) -> AABBGridHandle
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_aabb(&mut self, handle: AABBGridHandle, aabb: AB)
pub fn set_aabb(&mut self, handle: AABBGridHandle, aabb: AB)
Updates the aabb of an object.
sourcepub fn remove(&mut self, handle: AABBGridHandle) -> Option<O>
pub fn remove(&mut self, handle: AABBGridHandle) -> Option<O>
Removes an object from the grid.
sourcepub fn handles(&self) -> impl Iterator<Item = AABBGridHandle> + '_
pub fn handles(&self) -> impl Iterator<Item = AABBGridHandle> + '_
Iterate over all handles
sourcepub fn get(&self, id: AABBGridHandle) -> Option<&StoreObject<O, AB>>
pub fn get(&self, id: AABBGridHandle) -> Option<&StoreObject<O, AB>>
Returns a reference to the associated object and its position, using the handle.
sourcepub fn get_mut(&mut self, id: AABBGridHandle) -> Option<&mut StoreObject<O, AB>>
pub fn get_mut(&mut self, id: AABBGridHandle) -> Option<&mut StoreObject<O, AB>>
Returns a mutable reference to the associated object and its position, using the handle.
sourcepub fn storage(&self) -> &SparseStorage<AABBGridCell>
pub fn storage(&self) -> &SparseStorage<AABBGridCell>
The underlying storage
sourcepub fn query(
&self,
aabb: AB
) -> impl Iterator<Item = (AABBGridHandle, &AB, &O)> + '_
pub fn query( &self, aabb: AB ) -> impl Iterator<Item = (AABBGridHandle, &AB, &O)> + '_
Queries for objects intersecting a given AABB.
sourcepub fn query_broad(&self, bbox: AB) -> impl Iterator<Item = AABBGridHandle> + '_
pub fn query_broad(&self, bbox: AB) -> impl Iterator<Item = AABBGridHandle> + '_
Queries for all objects in the cells intersecting the given AABB
sourcepub fn query_visitor(
&self,
aabb: AB,
visitor: impl FnMut(AABBGridHandle, &AB, &O)
)
pub fn query_visitor( &self, aabb: AB, visitor: impl FnMut(AABBGridHandle, &AB, &O) )
Queries for objects intersecting a given AABB. Uses a visitor for slightly better performance.
sourcepub fn query_broad_visitor(&self, bbox: AB, visitor: impl FnMut(AABBGridHandle))
pub fn query_broad_visitor(&self, bbox: AB, visitor: impl FnMut(AABBGridHandle))
Queries for all objects in the cells intersecting the given AABB Uses a visitor for slightly better performance.