I have created a non-owning view of some spatial data that organises the data into cells. The data is split into a grid of cell size 100, and the key to the underlying HashMap is the index (top left corner) of the grid cell. Each grid cell contains a Vec of Point2D.
The purpose of this data structure is for efficient retrieval of nearby points for the broad phase of a collision detection algorithm where lots points are rapidly moving. It does this by returning a view of the points in the current and adjacent cells. It does not need to be the most performant algorithm in the world, but it should still be fast. It should certainly be faster than not using any broad phase stage at all. The other key requirement is that it is simple as this is for a personal learning exercise.
The easiest way to use this algorithm is to reconstruct the SpatialHashView with the new values each time it is used, however, there is a rebuild function that should be faster than new, as it can reuse the pre-allocated Vecs from the last time it was used.
I have tested this with some basic tests, and am in the process of adding some benchmarks. However, before I go too far can I please get a code review to confirm this is a sensible algorithm, there are no obvious bugs or flaws in logic, and it should be fairly performant?
use std::collections::HashMap;
use std::fmt::Debug;
const CELL_SIZE: i32 = 100;
type Point2D = (i32, i32);
type Cell<'a> = Vec<&'a mut Point2D>; //A view of points inside a grid cell
type CellIndex = (i32, i32);
fn assign_to_cell(point: &Point2D) -> CellIndex {
let (x, y) = point;
let x = x / CELL_SIZE;
let y = y / CELL_SIZE;
(x, y)
}
/// A non-owning view of the points organized by cell
pub struct SpatialHashView<'a> {
cells: HashMap<CellIndex, Cell<'a>>,
}
impl<'a> SpatialHashView<'a> {
/// Create a new view of the points, organized into cells
pub fn new(points: &'a mut Vec<Point2D>) -> Self {
let mut cells = HashMap::new();
for point in points {
let cell_index = assign_to_cell(point);
//If the cell does not exist, create it
let cell = cells.entry(cell_index).or_insert(Vec::new());
cell.push(point);
}
SpatialHashView { cells }
}
/// Empties this view and returns a new view as a vec
pub fn take_as_vec(&mut self) -> Vec<&'a mut Point2D> {
let mut points = Vec::new();
for cell in self.cells.values_mut() {
points.append(cell); //append leaves `cell` empty
}
points
}
/// Slightly faster than calling new if you have already constructed a SpatialHashView before
/// because it does not need to re-allocate the cells
pub fn rebuild(&mut self, points: Vec<&'a mut Point2D>) {
for point in points {
let cell_index = assign_to_cell(point);
//If the cell does not exist, create it (this time it likely already exists)
let cell = self.cells.entry(cell_index).or_insert(Cell::new());
if cell.contains(&point) {
//If the point is already in the cell, skip
continue;
}
else {
//If the point is not in the cell, add it
cell.push(point);
}
}
}
/// Return the cell index of adjacent cells
fn get_adjacent_cells(&self, cell_index: CellIndex) -> [CellIndex; 8] {
let (x, y) = cell_index;
[
(x - 1, y - 1),
(x, y - 1),
(x + 1, y - 1),
(x - 1, y),
(x + 1, y),
(x - 1, y + 1),
(x, y + 1),
(x + 1, y + 1),
]
}
/// Return the points in the cell and adjacent cells
/// Removes the references from this view and returns them as a vec
pub fn take_nearby_points(&mut self, point: Point2D) -> Vec<&'a mut Point2D> {
let mut nearby_points: Vec<&'a mut Point2D> = Vec::new();
let cell_index = assign_to_cell(&point);
//add points from adjacent cells
let adjacent_cells = self.get_adjacent_cells(cell_index);
for (cell_index, cell) in self.cells.iter_mut() {
if adjacent_cells.contains(cell_index) {
nearby_points.append(cell); //append leaves `cell` empty
}
}
//add points from same cell
if let Some(cell) = self.cells.get_mut(&cell_index) {
nearby_points.append(cell); //append leaves `cell` empty
}
nearby_points
}
}
/// For pretty printing
impl<'a> Debug for SpatialHashView<'a> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
for cell_index in self.cells.keys() {
writeln!(f, "cell index: {:?}", cell_index)?;
let points = self.cells.get(cell_index).unwrap();
for point in points {
writeln!(f, "\t{:?}", point)?;
}
};
Ok(())
}
}
/// This is the easiest way to use this module.
/// Return a vec of references to the points in the same cell and adjacent cells to `point`.
/// `points` is mutable so we can return mutable references to it, but it is not modified
/// in this function. It reconstructs the SpatialHashView each time, so for even better
/// performance, use the SpatialHashView directly and call `rebuild` before using.
pub fn filter_nearby(point: Point2D, points: & mut Vec<Point2D>) -> Vec<& mut Point2D> {
let mut view = SpatialHashView::new(points);
view.take_nearby_points(point)
}
One of my concerns with this is that it uses a HashMap of Vec, when perhaps using a custom HashMap would be better, with the HashMap "buckets" taking the place of the current Vec. Would this be worthwhile and easy to do?
