3
\$\begingroup\$

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?

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

Use linters

Use rustfmt on your code to comply with style guides and a liter like clippy to further help you to implement best practices.

Test your code

I have tested this with some basic tests, and am in the process of adding some benchmarks.

Where are those tests? I don't see any. Therefore it is also hard for me to judge, whether your code really does what it's supposed to do. Use cargo's built-in test suite to write appropriate unit tests and make them part of the crate.

Code style

This

    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 }
    }

Can be written as

    pub fn new(points: &'a mut Vec<Point2D>) -> Self {
        let mut cells = HashMap::new();
        points.iter_mut().for_each(|point| {
            cells
                .entry(assign_to_cell(point))
                .or_insert(Vec::new())
                .push(point)
        });
        Self { cells }
    }

However it might be better to implement the From trait to construct the SpatialHashView from a foreign data structure:

impl<'a> SpatialHashView<'a> {
    pub fn new(cells: HashMap<CellIndex, Cell<'a>>) -> Self {
        Self { cells }
    }
    ...
}

impl<'a> From<&'a mut Vec<Point2D>> for SpatialHashView<'a> {
    fn from(points: &'a mut Vec<Point2D>) -> Self {
        let mut cells = HashMap::new();
        points.iter_mut().for_each(|point| {
            cells
                .entry(assign_to_cell(point))
                .or_insert(Vec::new())
                .push(point)
        });
        Self::new(cells)
    }
}

...

pub fn filter_nearby(point: Point2D, points: &mut Vec<Point2D>) -> Vec<&mut Point2D> {
    SpatialHashView::from(points).take_nearby_points(point)
}

In general, prefer expression-driven code over statement-by-statement code, as you see in my refactoring of filter_nearby() or e.g.:

fn assign_to_cell(point: &Point2D) -> CellIndex {
    let (x, y) = point;
    let x = x / CELL_SIZE;
    let y = y / CELL_SIZE;
    (x, y)
}

vs.

fn assign_to_cell(point: &Point2D) -> CellIndex {
    (point.0 / CELL_SIZE, point.1 / CELL_SIZE)
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.