spatial-neighbors 0.1.0

Simple to use implementation of certain Spatial-Partitioning Algorithms | DataStructures
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

use crate::SpatialPartitioner;
use crate::util::in_range;

pub struct Grid<Data: Clone> {
    cells: Vec<Vec<((f64, f64), Data)>>,

    size: (u32, u32),
    x: (f64, f64),
    y: (f64, f64),

    count: usize,
}

impl<Data: Clone> Grid<Data> {
    ///
    /// # Arguments
    ///
    /// * `x`: (min_x, max_x) defines the area in wich points can be inserted
    /// * `y`: (min_y, max_y) defines the area in wich points can be inserted
    /// * `size`: (count_x, count_y) defines how many cell should be present
    ///
    pub fn new(x: (f64, f64), y: (f64, f64), size: (u32, u32)) -> Grid<Data> {
        let mut cells = Vec::new();

        for i in 0..(size.0 * size.1) {
            cells.insert(i as usize, Vec::new());
        };

        Grid {
            cells,
            size,
            x,
            y,
            count: 0,
        }
    }

    fn pos_to_index(&self, position: (f64, f64)) -> (u32, u32) {
        let x = (((position.0 - self.x.0) as f32 / (self.x.1 - self.x.0) as f32) * self.size.0 as f32).floor() as u32;
        let y = (((position.1 - self.y.0) as f32 / (self.y.1 - self.y.0) as f32) * self.size.1 as f32).floor() as u32;

        (x, y)
    }
}

impl<Data: Clone> SpatialPartitioner<Data> for Grid<Data> {
    fn insert(&mut self, position: (f64, f64), data: Data) {
        if position.0 < self.x.0 || position.0 >= self.x.1 || position.1 < self.y.0 || position.1 >= self.y.1 {
            panic!("tried to insert position into SpatialHash which was out of bounce")
        }

        self.insert_unchecked(position, data);
    }

    fn insert_unchecked(&mut self, position: (f64, f64), data: Data) {
        let index_position = self.pos_to_index(position);

        self.cells.get_mut((index_position.0 + (index_position.1 * self.size.0)) as usize).unwrap().push((position, data));
        self.count += 1;
    }

    fn count(&self) -> usize {
        self.count
    }

    fn clear(&mut self) {
        self.count = 0;
        self.cells.iter_mut().for_each(|cell| cell.clear())
    }

    fn in_circle(&self, position: (f64, f64), radius: f64) -> Vec<Data> {
        let radius_x = (radius / ((self.x.1 - self.x.0) as f64 / self.size.0 as f64)).ceil().min(self.size.0 as f64) as i32;
        let radius_y = (radius / ((self.y.1 - self.y.0) as f64 / self.size.1 as f64)).ceil().min(self.size.1 as f64) as i32;

        let index_position = self.pos_to_index(position);

        let mut data = Vec::new();

        for x in -radius_x..(radius_x + 1) {
            for y in -radius_y..(radius_y + 1) {
                let x = index_position.0 as i32 + x;
                let y = index_position.1 as i32 + y;

                if x < 0 || x >= self.size.0 as i32 || y < 0 || y >= self.size.1 as i32 {
                    continue;
                }

                let index = x + (y * self.size.0 as i32);

                match self.cells.get(index as usize) {
                    None => {}
                    Some(elements) => {
                        for element in elements {
                            if in_range(element.0, position, radius) {
                                data.push(element.1.clone());
                            }
                        }
                    }
                };
            }
        }

        data
    }
}