Struct flat_spatial::densegrid::DenseGrid

pub struct DenseGrid<O: Copy> { /* fields omitted */ }

DenseGrid is a point-based spatial partitioning structure that uses a simple Vec which acts as a grid instead of a tree. It is Dense because all cells within the bounding rectangle of the inserted points must be allocated, even if they are empty.

Fast queries

In theory, DenseGrid 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. It is also memory hungry since all empty cells have to be allocated.

Dynamicity

DenseGrid'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 if the objects don't move too much. ¹

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 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::DenseGrid;
let mut g: DenseGrid<()> = DenseGrid::new(10);
let handle = g.insert([0.0, 0.0], ());
// Use handle however you want

Examples

Here is a basic example that shows most of its capabilities:

use flat_spatial::DenseGrid;

let mut g: DenseGrid<i32> = DenseGrid::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

Schema

Here is a schema showing a bit more visually how the structure works

---

1. If an object goes out of the boundaries, then the boundary has to grow. Therefore, all cells have to be reallocated and all the points have to be reinserted. This can be solved in constant time using a SparseGrid, which has yet to be implemented. ↩

Implementations

impl<O: Copy> DenseGrid<O>

pub fn new(cell_size: i32) -> Self

Creates an empty grid that will center itself on the first coordinate given.
The cell size should be about the same magnitude as your queries size.

pub fn new_centered(cell_size: i32, size: i32) -> Self

Creates a new grid centered on zero with width and height defined by size.
The cell size should be about the same magnitude as your queries size.

Note that the size is counted in cells and not in absolute units (!)

pub fn new_rect(cell_size: i32, x: i32, y: i32, w: i32, h: i32) -> Self

Creates a new grid with a custom rect defining its boundaries.
The cell size should be about the same magnitude as your queries size.

Note that the coordinates are counted in cells and not in absolute units (!)

pub fn insert(&mut self, pos: impl Into<Point2<f32>>, obj: O) -> DenseGridHandle

Inserts a new object with a position and an associated object Returns the unique and stable handle to be used with get_obj May reallocate the grid if pos is out of the boundary

Example

use flat_spatial::DenseGrid;
let mut g: DenseGrid<()> = DenseGrid::new(10);
let h = g.insert([5.0, 3.0], ());

pub fn set_position(
    &mut self,
    handle: DenseGridHandle,
    pos: impl Into<Point2<f32>>
)

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.
May reallocate the grid if pos is out of the boundary.

Example

use flat_spatial::DenseGrid;
let mut g: DenseGrid<()> = DenseGrid::new(10);
let h = g.insert([5.0, 3.0], ());
g.set_position(h, [3.0, 3.0]);

pub fn remove(&mut self, handle: DenseGridHandle)

Lazily removes an object from the grid. This won't be taken into account until maintain() is called.

Example

use flat_spatial::DenseGrid;
let mut g: DenseGrid<()> = DenseGrid::new(10);
let h = g.insert([5.0, 3.0], ());
g.remove(h);

pub fn maintain(&mut self)

Maintains the world, updating all the positions (and moving them to corresponding cells) and removing necessary objects. Runs in linear time O(C + O) where C is the number of cells and O the number of objects.

Example

use flat_spatial::DenseGrid;
let mut g: DenseGrid<()> = DenseGrid::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());

pub fn handles<'a>(&'a self) -> impl Iterator<Item = DenseGridHandle> + 'a

Iterate over all handles

pub fn cells(&self) -> &Vec<DenseGridCell>

Read access to the cells

pub fn get(&self, id: DenseGridHandle) -> Option<(Point2<f32>, &O)>

Returns a reference to the associated object and its position, using the handle.

Example

use flat_spatial::DenseGrid;
let mut g: DenseGrid<i32> = DenseGrid::new(10);
let h = g.insert([5.0, 3.0], 42);
assert_eq!(g.get(h), Some(([5.0, 3.0].into(), &42)));

pub fn get_mut(&mut self, id: DenseGridHandle) -> Option<(Point2<f32>, &mut O)>

Returns a mutable reference to the associated object and its position, using the handle.

Example

use flat_spatial::DenseGrid;
let mut g: DenseGrid<i32> = DenseGrid::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 query_around(
    &self,
    pos: impl Into<Point2<f32>>,
    radius: f32
) -> impl Iterator<Item = (DenseGridHandle, Point2<f32>)> + '_

Queries for all objects around a position within a certain radius. Try to keep the radius asked and the cell size of similar magnitude for better performance.

Example

use flat_spatial::DenseGrid;

let mut g: DenseGrid<()> = DenseGrid::new(10);
let a = g.insert([0.0, 0.0], ());

let around: Vec<_> = g.query_around([2.0, 2.0], 5.0).map(|(id, _pos)| id).collect();
 
assert_eq!(vec![a], around);

pub fn query_aabb(
    &self,
    aa: impl Into<Point2<f32>>,
    bb: impl Into<Point2<f32>>
) -> impl Iterator<Item = (DenseGridHandle, Point2<f32>)> + '_

Queries for all objects in an aabb (aka a rect). Try to keep the rect's width/height of similar magnitudes to the cell size for better performance.

Example

use flat_spatial::DenseGrid;

let mut g: DenseGrid<()> = DenseGrid::new(10);
let a = g.insert([0.0, 0.0], ());

let around: Vec<_> = g.query_aabb([-1.0, -1.0], [1.0, 1.0]).map(|(id, _pos)| id).collect();
 
assert_eq!(vec![a], around);

pub fn get_cell(
    &mut self,
    pos: impl Into<Point2<f32>>
) -> &Vec<(DenseGridHandle, Point2<f32>)>

Allows to look directly at what's in a cell covering a specific position

Example

use flat_spatial::DenseGrid;

let mut g: DenseGrid<()> = DenseGrid::new(10);
let a = g.insert([2.0, 2.0], ());

let around = g.get_cell([1.0, 1.0]);

assert_eq!(&vec![(a, [2.0, 2.0].into())], around);

pub fn get_rect(&self) -> (i32, i32, i32, i32)

Returns the (x, y, width, height) tuple representing the current allocated rect (x, y) are in absolute units and (width, height) are in cells

pub fn len(&self) -> usize

Returns the number of objects currently available (removals that were not confirmed with maintain() are still counted)

pub fn is_empty(&self) -> bool

Checks if the grid contains objects or not (removals that were not confirmed with maintain() are still counted)

Trait Implementations

impl<O: Clone + Copy> Clone for DenseGrid<O>

fn clone(&self) -> DenseGrid<O>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.