[−][src]Struct flat_spatial::shapegrid::ShapeGrid
ShapeGrid is a generic shape-based spatial partitioning structure that uses a generic storage of cells which acts as a grid instead of a tree.
Fast queries
In theory, ShapeGrid 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
ShapeGrid's allows eager removals and position updates, however for big shapes (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 shapes 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 managment
In theory, you don't have to use the object managment 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 managment code.
use flat_spatial::ShapeGrid; use flat_spatial::shape::Circle; let mut g: ShapeGrid<(), Circle> = ShapeGrid::new(10); let handle = g.insert(Circle { center: [0.0, 0.0].into(), radius: 3.0, }, ()); // Use handle however you want
Examples
Here is a basic example that shows most of its capabilities:
use flat_spatial::ShapeGrid; use flat_spatial::shape::Circle; let mut g: ShapeGrid<i32, Circle> = ShapeGrid::new(10); // Creates a new grid with a cell width of 10 with an integer as extra data let a = g.insert(Circle { center: [2.0, 2.0].into(), radius: 3.0, }, 0); // Inserts a new circle with data: 0 { let mut before = g.query_around([0.0, 0.0], 5.0).map(|(id, _shape, _obj)| id); // Queries for circles intersecting around a given point assert_eq!(before.next(), Some(a)); assert_eq!(g.get(a).unwrap().1, &0); } let b = g.insert(Circle { center: [1.0, 1.0].into(), radius: 3.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` 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, _shape, _obj)| 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!(g.get(a).is_none()); // But that a doesn't exist anymore
Implementations
impl<S: Shape, ST: Storage<ShapeGridCell>, O: Copy> ShapeGrid<O, S, ST>
[src]
pub fn new(cell_size: i32) -> Self
[src]
Creates an empty grid.
The cell size should be about the same magnitude as your queries size.
pub fn with_storage(st: ST) -> Self
[src]
Creates an empty grid.
The cell size should be about the same magnitude as your queries size.
pub fn insert(&mut self, shape: S, obj: O) -> ShapeGridHandle
[src]
Inserts a new object with a position and an associated object Returns the unique and stable handle to be used with get_obj
Example
use flat_spatial::{ShapeGrid, shape::Circle}; let mut g: ShapeGrid<(), Circle> = ShapeGrid::new(10); let h = g.insert(Circle { center: [2.0, 2.0].into(), radius: 3.0, }, ());
pub fn set_shape(&mut self, handle: ShapeGridHandle, shape: S)
[src]
Updates the shape of an object.
Example
use flat_spatial::{ShapeGrid, shape::Circle}; let mut g: ShapeGrid<(), Circle> = ShapeGrid::new(10); let h = g.insert(Circle { center: [2.0, 2.0].into(), radius: 3.0, }, ()); g.set_shape(h, Circle { center: [61.0, 35.0].into(), radius: 8.0, });
pub fn remove(&mut self, handle: ShapeGridHandle) -> Option<O>
[src]
Removes an object from the grid.
Example
use flat_spatial::{ShapeGrid, shape::Circle}; let mut g: ShapeGrid<(), Circle> = ShapeGrid::new(10); let h = g.insert(Circle { center: [2.0, 2.0].into(), radius: 3.0, }, ()); g.remove(h);
pub fn handles(&self) -> impl Iterator<Item = ShapeGridHandle> + '_
[src]
Iterate over all handles
pub fn objects(&self) -> impl Iterator<Item = &O> + '_
[src]
Iterate over all objects
pub fn get(&self, id: ShapeGridHandle) -> Option<(&S, &O)>
[src]
Returns a reference to the associated object and its position, using the handle.
Example
use flat_spatial::{ShapeGrid, shape::Circle}; let mut g: ShapeGrid<i32, [f32; 2]> = ShapeGrid::new(10); let h = g.insert([5.0, 3.0], 42); assert_eq!(g.get(h), Some((&[5.0, 3.0], &42)));
pub fn get_mut(&mut self, id: ShapeGridHandle) -> Option<(&S, &mut O)>
[src]
Returns a mutable reference to the associated object and its position, using the handle.
Example
use flat_spatial::{ShapeGrid, shape::Circle}; let mut g: ShapeGrid<i32, [f32; 2]> = ShapeGrid::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);
pub fn storage(&self) -> &ST
[src]
The underlying storage
pub fn query<QS: Shape + Intersect<S> + 'static>(
&self,
shape: QS
) -> impl Iterator<Item = (ShapeGridHandle, &S, &O)> + '_
[src]
&self,
shape: QS
) -> impl Iterator<Item = (ShapeGridHandle, &S, &O)> + '_
Queries for objects intersecting a given shape.
Example
use flat_spatial::{ShapeGrid, shape::Circle}; let mut g: ShapeGrid<(), Circle> = ShapeGrid::new(10); let a = g.insert(Circle { center: [2.0, 2.0].into(), radius: 3.0, }, ()); let b = g.insert(Circle { center: [5.0, 2.0].into(), radius: 3.0, }, ()); let around: Vec<_> = g.query(Circle { center: [0.0, 0.0].into(), radius: 10.0, }).map(|(id, _shape, _obj)| id).collect(); assert_eq!(vec![a, b], around);
pub fn query_broad<QS: Shape + 'static>(
&self,
shape: QS
) -> impl Iterator<Item = ShapeGridHandle> + '_
[src]
&self,
shape: QS
) -> impl Iterator<Item = ShapeGridHandle> + '_
Queries for all objects in the cells intersecting the given shape
Exampley
use flat_spatial::{ShapeGrid, shape::Circle}; let mut g: ShapeGrid<(), Circle> = ShapeGrid::new(10); let a = g.insert(Circle { center: [5.0, 5.0].into(), radius: 1.0, }, ()); let around: Vec<_> = g.query_broad(Circle { center: [0.0, 0.0].into(), radius: 1.0, }).collect(); assert_eq!(vec![a], around); // a is given even if it doesn't intersect, because this only looks at the cells
pub fn len(&self) -> usize
[src]
Returns the number of objects currently available (removals that were not confirmed with maintain() are still counted)
pub fn is_empty(&self) -> bool
[src]
Checks if the grid contains objects or not (removals that were not confirmed with maintain() are still counted)
impl<S: Shape, ST: Storage<ShapeGridCell>, O: Copy> ShapeGrid<O, S, ST> where
Circle: Intersect<S>,
[src]
Circle: Intersect<S>,
pub fn query_around(
&self,
pos: impl Into<Point2<f32>>,
radius: f32
) -> impl Iterator<Item = (ShapeGridHandle, &S, &O)> + '_
[src]
&self,
pos: impl Into<Point2<f32>>,
radius: f32
) -> impl Iterator<Item = (ShapeGridHandle, &S, &O)> + '_
Queries for objects around a point, same as querying a circle at pos with a given radius.
Trait Implementations
impl<O: Clone + Copy, S: Clone + Shape, ST: Clone + Storage<ShapeGridCell>> Clone for ShapeGrid<O, S, ST>
[src]
Auto Trait Implementations
impl<O, S, ST> RefUnwindSafe for ShapeGrid<O, S, ST> where
O: RefUnwindSafe,
S: RefUnwindSafe,
ST: RefUnwindSafe,
O: RefUnwindSafe,
S: RefUnwindSafe,
ST: RefUnwindSafe,
impl<O, S, ST> Send for ShapeGrid<O, S, ST> where
O: Send,
S: Send,
ST: Send,
O: Send,
S: Send,
ST: Send,
impl<O, S, ST> Sync for ShapeGrid<O, S, ST> where
O: Sync,
S: Sync,
ST: Sync,
O: Sync,
S: Sync,
ST: Sync,
impl<O, S, ST> Unpin for ShapeGrid<O, S, ST> where
O: Unpin,
S: Unpin,
ST: Unpin,
O: Unpin,
S: Unpin,
ST: Unpin,
impl<O, S, ST> UnwindSafe for ShapeGrid<O, S, ST> where
O: UnwindSafe,
S: UnwindSafe,
ST: UnwindSafe,
O: UnwindSafe,
S: UnwindSafe,
ST: UnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
pub fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
pub fn to_owned(&self) -> T
[src]
pub fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
pub fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,