1#[derive(Debug, Clone)]
2pub struct SpatialElement {
3 pub h3_index: u64,
4 pub bounds: (f64, f64, f64, f64), 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 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 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 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 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 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 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 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
251pub fn embed_h3_context(index: u64, resolution: u8, base_cell: u8) -> u64 {
254 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 let res1 = qt.query_region(15.0, 15.0, 25.0, 25.0, 1200, 1800);
285 assert_eq!(res1, vec![101]);
286
287 let res2 = qt.query_region(15.0, 15.0, 25.0, 25.0, 3000, 4000);
289 assert!(res2.is_empty());
290
291 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; 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}