spatial-neighbors 0.1.2

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

use std::ops::Range;
use crate::SpatialPartitioner;
use crate::util::in_range;

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

    size: (u32, u32),
    cell_size: (f64, f64),
    x: Range<f64>,
    y: Range<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: Range<f64>, y: Range<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,
            cell_size: ((x.end - x.start) as f64 / size.0 as f64, (y.end - y.start) as f64 / size.1 as f64),
            x,
            y,
            count: 0,
        }
    }

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

        (x, y)
    }

    fn index_to_pos(&self, position: (u32, u32)) -> (f64, f64) {
        let x = self.cell_size.0 * position.0 as f64 + self.x.start;
        let y = self.cell_size.1 * position.1 as f64 + self.y.start;

        (x, y)
    }
}

impl<Data: Clone> SpatialPartitioner<Data> for Grid<Data> {
    fn insert(&mut self, position: (f64, f64), data: Data) {
        if position.0 < self.x.start || position.0 >= self.x.end || position.1 < self.y.start || position.1 >= self.y.end {
            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.end - self.x.start) as f64 / self.size.0 as f64)).ceil().min(self.size.0 as f64) as i32;
        let radius_y = (radius / ((self.y.end - self.y.start) 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) => {
                        if elements.len() > 4 {
                            let pos = self.index_to_pos((x as u32, y as u32));

                            if in_range(position, (pos.0 + self.cell_size.0, pos.1), radius)
                                && in_range(position, (pos.0 + self.cell_size.0, pos.1 + self.cell_size.1), radius)
                                && in_range(position, (pos.0, pos.1), radius)
                                && in_range(position, (pos.0, pos.1 + self.cell_size.1), radius) {
                                for element in elements {
                                    data.push(element.1.clone());
                                }

                                continue;
                            }
                        }

                        for element in elements {
                            if in_range(element.0, position, radius) {
                                data.push(element.1.clone());
                            }
                        }
                    }
                };
            }
        }

        data
    }
}