Skip to main content

qualia_core_db/domains/geospatial/
spatial.rs

1#[derive(Debug, Clone)]
2pub struct SpatialElement {
3    pub h3_index: u64,
4    pub bounds: (f64, f64, f64, f64), // (min_x, min_y, max_x, max_y)
5    pub t0: u64,
6    pub t1: u64,
7}
8
9#[derive(Debug, Clone)]
10enum QuadTreeNode {
11    Leaf { elements: Vec<SpatialElement> },
12    Internal { children: Box<[QuadTreeNode; 4]> },
13}
14
15#[derive(Debug, Clone)]
16pub struct SpatiotemporalQuadTree {
17    pub root_bounds: (f64, f64, f64, f64),
18    root: QuadTreeNode,
19    max_elements: usize,
20    max_depth: u32,
21}
22
23impl SpatiotemporalQuadTree {
24    /// Creates a default `SpatiotemporalQuadTree`.
25    pub fn new(bounds: (f64, f64, f64, f64)) -> Self {
26        Self {
27            root_bounds: bounds,
28            root: QuadTreeNode::Leaf {
29                elements: Vec::new(),
30            },
31            max_elements: 16,
32            max_depth: 8,
33        }
34    }
35
36    /// Inserts an entry; error at capacity.
37    pub fn insert(&mut self, element: SpatialElement) {
38        Self::insert_into(
39            &mut self.root,
40            self.root_bounds,
41            element,
42            0,
43            self.max_elements,
44            self.max_depth,
45        );
46    }
47
48    fn insert_into(
49        node: &mut QuadTreeNode,
50        bounds: (f64, f64, f64, f64),
51        element: SpatialElement,
52        depth: u32,
53        max_elements: usize,
54        max_depth: u32,
55    ) {
56        match node {
57            QuadTreeNode::Leaf { elements } => {
58                elements.push(element);
59                if elements.len() > max_elements && depth < max_depth {
60                    // Split the node
61                    let (min_x, min_y, max_x, max_y) = bounds;
62                    let mid_x = (min_x + max_x) / 2.0;
63                    let mid_y = (min_y + max_y) / 2.0;
64
65                    let mut top_left = Vec::new();
66                    let mut top_right = Vec::new();
67                    let mut bottom_left = Vec::new();
68                    let mut bottom_right = Vec::new();
69
70                    for el in elements.drain(..) {
71                        let (el_min_x, el_min_y, el_max_x, el_max_y) = el.bounds;
72                        // Determine which quadrants the element belongs to
73                        let left = el_min_x <= mid_x;
74                        let right = el_max_x >= mid_x;
75                        let bottom = el_min_y <= mid_y;
76                        let top = el_max_y >= mid_y;
77
78                        if left && top {
79                            top_left.push(el.clone());
80                        }
81                        if right && top {
82                            top_right.push(el.clone());
83                        }
84                        if left && bottom {
85                            bottom_left.push(el.clone());
86                        }
87                        if right && bottom {
88                            bottom_right.push(el.clone());
89                        }
90                    }
91
92                    *node = QuadTreeNode::Internal {
93                        children: Box::new([
94                            QuadTreeNode::Leaf { elements: top_left },
95                            QuadTreeNode::Leaf {
96                                elements: top_right,
97                            },
98                            QuadTreeNode::Leaf {
99                                elements: bottom_left,
100                            },
101                            QuadTreeNode::Leaf {
102                                elements: bottom_right,
103                            },
104                        ]),
105                    };
106                }
107            }
108            QuadTreeNode::Internal { children } => {
109                let (min_x, min_y, max_x, max_y) = bounds;
110                let mid_x = (min_x + max_x) / 2.0;
111                let mid_y = (min_y + max_y) / 2.0;
112
113                let (el_min_x, el_min_y, el_max_x, el_max_y) = element.bounds;
114                let left = el_min_x <= mid_x;
115                let right = el_max_x >= mid_x;
116                let bottom = el_min_y <= mid_y;
117                let top = el_max_y >= mid_y;
118
119                if left && top {
120                    Self::insert_into(
121                        &mut children[0],
122                        (min_x, mid_y, mid_x, max_y),
123                        element.clone(),
124                        depth + 1,
125                        max_elements,
126                        max_depth,
127                    );
128                }
129                if right && top {
130                    Self::insert_into(
131                        &mut children[1],
132                        (mid_x, mid_y, max_x, max_y),
133                        element.clone(),
134                        depth + 1,
135                        max_elements,
136                        max_depth,
137                    );
138                }
139                if left && bottom {
140                    Self::insert_into(
141                        &mut children[2],
142                        (min_x, min_y, mid_x, mid_y),
143                        element.clone(),
144                        depth + 1,
145                        max_elements,
146                        max_depth,
147                    );
148                }
149                if right && bottom {
150                    Self::insert_into(
151                        &mut children[3],
152                        (mid_x, min_y, max_x, mid_y),
153                        element.clone(),
154                        depth + 1,
155                        max_elements,
156                        max_depth,
157                    );
158                }
159            }
160        }
161    }
162
163    /// Queries the quadtree for elements that intersect the given spatial bounding box
164    /// and are valid within the given temporal range [t0, t1].
165    pub fn query_region(&self, x1: f64, y1: f64, x2: f64, y2: f64, t0: u64, t1: u64) -> Vec<u64> {
166        let mut results = Vec::new();
167        Self::query_node(
168            &self.root,
169            self.root_bounds,
170            (x1, y1, x2, y2),
171            t0,
172            t1,
173            &mut results,
174        );
175
176        // Remove duplicates because elements might span multiple quadrants
177        results.sort_unstable();
178        results.dedup();
179        results
180    }
181
182    fn query_node(
183        node: &QuadTreeNode,
184        bounds: (f64, f64, f64, f64),
185        query_bounds: (f64, f64, f64, f64),
186        t0: u64,
187        t1: u64,
188        results: &mut Vec<u64>,
189    ) {
190        let (qx1, qy1, qx2, qy2) = query_bounds;
191        let (bx1, by1, bx2, by2) = bounds;
192
193        // If the query region doesn't intersect the node's bounds, skip
194        if qx1 > bx2 || qx2 < bx1 || qy1 > by2 || qy2 < by1 {
195            return;
196        }
197
198        match node {
199            QuadTreeNode::Leaf { elements } => {
200                for el in elements {
201                    let overlap_x = el.bounds.0 <= qx2 && el.bounds.2 >= qx1;
202                    let overlap_y = el.bounds.1 <= qy2 && el.bounds.3 >= qy1;
203                    let overlap_t = el.t0 <= t1 && el.t1 >= t0;
204
205                    if overlap_x && overlap_y && overlap_t {
206                        results.push(el.h3_index);
207                    }
208                }
209            }
210            QuadTreeNode::Internal { children } => {
211                let mid_x = (bx1 + bx2) / 2.0;
212                let mid_y = (by1 + by2) / 2.0;
213
214                Self::query_node(
215                    &children[0],
216                    (bx1, mid_y, mid_x, by2),
217                    query_bounds,
218                    t0,
219                    t1,
220                    results,
221                );
222                Self::query_node(
223                    &children[1],
224                    (mid_x, mid_y, bx2, by2),
225                    query_bounds,
226                    t0,
227                    t1,
228                    results,
229                );
230                Self::query_node(
231                    &children[2],
232                    (bx1, by1, mid_x, mid_y),
233                    query_bounds,
234                    t0,
235                    t1,
236                    results,
237                );
238                Self::query_node(
239                    &children[3],
240                    (mid_x, by1, bx2, mid_y),
241                    query_bounds,
242                    t0,
243                    t1,
244                    results,
245                );
246            }
247        }
248    }
249}
250
251/// Embeds an H3 index into a unified 64-bit coordinate space index, commonly used in MORTON codes
252/// or spatial hashing systems where bit packing includes resolution or other contextual data.
253pub fn embed_h3_context(index: u64, resolution: u8, base_cell: u8) -> u64 {
254    // 64-bit layout: [1 bit reserved][4 bits resolution][7 bits base_cell][52 bits H3 internal]
255    let res_bits = ((resolution & 0x0F) as u64) << 59;
256    let base_bits = ((base_cell & 0x7F) as u64) << 52;
257    let index_bits = index & 0x000F_FFFF_FFFF_FFFF;
258    res_bits | base_bits | index_bits
259}
260
261#[cfg(test)]
262mod tests {
263    use super::*;
264
265    #[test]
266    fn test_query_region() {
267        let mut qt = SpatiotemporalQuadTree::new((-180.0, -90.0, 180.0, 90.0));
268
269        qt.insert(SpatialElement {
270            h3_index: 101,
271            bounds: (10.0, 10.0, 20.0, 20.0),
272            t0: 1000,
273            t1: 2000,
274        });
275
276        qt.insert(SpatialElement {
277            h3_index: 202,
278            bounds: (50.0, 50.0, 60.0, 60.0),
279            t0: 1500,
280            t1: 2500,
281        });
282
283        // Intersects first element spatially and temporally
284        let res1 = qt.query_region(15.0, 15.0, 25.0, 25.0, 1200, 1800);
285        assert_eq!(res1, vec![101]);
286
287        // Spatially intersects but temporally disjoint
288        let res2 = qt.query_region(15.0, 15.0, 25.0, 25.0, 3000, 4000);
289        assert!(res2.is_empty());
290
291        // Intersects both temporally, only second spatially
292        let res3 = qt.query_region(40.0, 40.0, 55.0, 55.0, 1500, 2000);
293        assert_eq!(res3, vec![202]);
294    }
295
296    #[test]
297    fn test_quadtree_split() {
298        let mut qt = SpatiotemporalQuadTree::new((0.0, 0.0, 100.0, 100.0));
299        qt.max_elements = 2; // Force early split
300
301        for i in 0..5 {
302            qt.insert(SpatialElement {
303                h3_index: i,
304                bounds: (
305                    10.0 + (i as f64),
306                    10.0 + (i as f64),
307                    15.0 + (i as f64),
308                    15.0 + (i as f64),
309                ),
310                t0: 100,
311                t1: 200,
312            });
313        }
314
315        let res = qt.query_region(0.0, 0.0, 50.0, 50.0, 50, 250);
316        assert_eq!(res.len(), 5);
317    }
318}