maplibre/legacy/
grid_index.rs

1//! Translated from https://github.com/maplibre/maplibre-native/blob/4add9ea/src/mbgl/util/grid_index.hpp
2
3use std::{collections::HashSet, f64};
4
5use crate::{
6    euclid::{Box2D, Point2D},
7    legacy::ScreenSpace,
8};
9
10/// maplibre/maplibre-native#4add9ea original name: Circle
11#[derive(Default, Clone, Copy, Debug)]
12pub struct Circle<T> {
13    pub center: Point2D<T, ScreenSpace>,
14    pub radius: T,
15}
16
17impl<T> Circle<T> {
18    /// maplibre/maplibre-native#4add9ea original name: new
19    pub fn new(center: Point2D<T, ScreenSpace>, radius: T) -> Circle<T> {
20        Self { center, radius }
21    }
22}
23
24impl<T: PartialEq> PartialEq for Circle<T> {
25    /// maplibre/maplibre-native#4add9ea original name: eq
26    fn eq(&self, other: &Self) -> bool {
27        self.center == other.center && self.radius == other.radius
28    }
29}
30
31impl<T: PartialEq> Eq for Circle<T> {}
32
33/// maplibre/maplibre-native#4add9ea original name: GridIndex
34pub struct GridIndex<T: Clone> {
35    width: f64,
36    height: f64,
37    x_cell_count: usize,
38    y_cell_count: usize,
39    x_scale: f64,
40    y_scale: f64,
41    estimated_elements_per_cell: usize,
42    box_elements: Vec<(T, Box2D<f64, ScreenSpace>)>,
43    circle_elements: Vec<(T, Circle<f64>)>,
44    box_cells: Vec<Vec<u32>>,
45    circle_cells: Vec<Vec<u32>>,
46}
47
48impl<T: Clone> GridIndex<T> {
49    /// maplibre/maplibre-native#4add9ea original name: new
50    pub fn new(width: f64, height: f64, cell_size: u32) -> Self {
51        let x_cell_count = (width / cell_size as f64).ceil() as usize;
52        let y_cell_count = (height / cell_size as f64).ceil() as usize;
53
54        assert!(width > 0.0);
55        assert!(height > 0.0);
56        Self {
57            width,
58            height,
59            x_cell_count,
60            y_cell_count,
61            x_scale: x_cell_count as f64 / width,
62            y_scale: y_cell_count as f64 / height,
63            estimated_elements_per_cell: 0,
64            box_elements: vec![],
65            circle_elements: vec![],
66            box_cells: vec![vec![]; x_cell_count * y_cell_count],
67            circle_cells: vec![vec![]; x_cell_count * y_cell_count],
68        }
69    }
70
71    /// Set the expected number of elements per cell to avoid small re-allocations for populated cells
72    /// maplibre/maplibre-native#4add9ea original name: reserve
73    pub fn reserve(&mut self, value: usize) {
74        self.estimated_elements_per_cell = value;
75    }
76
77    /// maplibre/maplibre-native#4add9ea original name: insert
78    pub fn insert(&mut self, t: T, bbox: Box2D<f64, ScreenSpace>) {
79        assert!(self.box_elements.len() < u32::MAX as usize);
80        let uid = self.box_elements.len() as u32;
81
82        let cx1 = self.convert_to_x_cell_coord(bbox.min.x);
83        let cy1 = self.convert_to_y_cell_coord(bbox.min.y);
84        let cx2 = self.convert_to_x_cell_coord(bbox.max.x);
85        let cy2 = self.convert_to_y_cell_coord(bbox.max.y);
86
87        for x in cx1..=cx2 {
88            for y in cy1..=cy2 {
89                let cell = &mut self.box_cells[self.x_cell_count * y + x];
90                if self.estimated_elements_per_cell > 0 && cell.is_empty() {
91                    cell.reserve(self.estimated_elements_per_cell);
92                }
93                cell.push(uid);
94            }
95        }
96
97        self.box_elements.push((t, bbox));
98    }
99
100    /// maplibre/maplibre-native#4add9ea original name: insert_circle
101    pub fn insert_circle(&mut self, t: T, circle: Circle<f64>) {
102        assert!(self.circle_elements.len() < u32::MAX as usize);
103        let uid = self.circle_elements.len() as u32;
104
105        let cx1 = self.convert_to_x_cell_coord(circle.center.x - circle.radius);
106        let cy1 = self.convert_to_y_cell_coord(circle.center.y - circle.radius);
107        let cx2 = self.convert_to_x_cell_coord(circle.center.x + circle.radius);
108        let cy2 = self.convert_to_y_cell_coord(circle.center.y + circle.radius);
109
110        for x in cx1..=cx2 {
111            for y in cy1..=cy2 {
112                let cell = &mut self.circle_cells[self.x_cell_count * y + x];
113                if self.estimated_elements_per_cell > 0 && cell.is_empty() {
114                    cell.reserve(self.estimated_elements_per_cell);
115                }
116                cell.push(uid);
117            }
118        }
119
120        self.circle_elements.push((t, circle));
121    }
122
123    /// maplibre/maplibre-native#4add9ea original name: query
124    pub fn query(&self, query_box: &Box2D<f64, ScreenSpace>) -> Vec<T> {
125        let mut result = Vec::new();
126        self.query_internal(query_box, |t, bbox| -> bool {
127            result.push(t);
128            false
129        });
130        result
131    }
132
133    /// maplibre/maplibre-native#4add9ea original name: query_with_boxes
134    pub fn query_with_boxes(
135        &self,
136        query_box: &Box2D<f64, ScreenSpace>,
137    ) -> Vec<(T, Box2D<f64, ScreenSpace>)> {
138        let mut result = Vec::new();
139        self.query_internal(query_box, |t, bbox| -> bool {
140            result.push((t, bbox));
141            false
142        });
143        result
144    }
145
146    /// maplibre/maplibre-native#4add9ea original name: hit_test
147    pub fn hit_test<F>(&self, query_box: &Box2D<f64, ScreenSpace>, predicate: Option<F>) -> bool
148    where
149        F: Fn(&T) -> bool,
150    {
151        let mut hit = false;
152        self.query_internal(query_box, |t, _| -> bool {
153            if let Some(predicate) = &predicate {
154                if predicate(&t) {
155                    hit = true;
156                    true
157                } else {
158                    false
159                }
160            } else {
161                hit = true;
162                true
163            }
164        });
165        hit
166    }
167
168    /// maplibre/maplibre-native#4add9ea original name: hit_test_circle
169    pub fn hit_test_circle<F>(&self, circle: &Circle<f64>, predicate: Option<F>) -> bool
170    where
171        F: Fn(&T) -> bool,
172    {
173        let mut hit = false;
174        self.query_internal_circles(circle, |t, _| -> bool {
175            if let Some(predicate) = &predicate {
176                if predicate(&t) {
177                    hit = true;
178                    true
179                } else {
180                    false
181                }
182            } else {
183                hit = true;
184                true
185            }
186        });
187        hit
188    }
189
190    /// maplibre/maplibre-native#4add9ea original name: empty
191    pub fn empty(&self) -> bool {
192        self.box_elements.is_empty() && self.circle_elements.is_empty()
193    }
194}
195
196impl<T: Clone> GridIndex<T> {
197    /// maplibre/maplibre-native#4add9ea original name: no_intersection
198    fn no_intersection(&self, query_box: &Box2D<f64, ScreenSpace>) -> bool {
199        query_box.max.x < 0.0
200            || query_box.min.x >= self.width
201            || query_box.max.y < 0.0
202            || query_box.min.y >= self.height
203    }
204
205    /// maplibre/maplibre-native#4add9ea original name: complete_intersection
206    fn complete_intersection(&self, query_box: &Box2D<f64, ScreenSpace>) -> bool {
207        query_box.min.x <= 0.0
208            && query_box.min.y <= 0.0
209            && self.width <= query_box.max.x
210            && self.height <= query_box.max.y
211    }
212
213    /// maplibre/maplibre-native#4add9ea original name: convert_to_box
214    fn convert_to_box(circle: &Circle<f64>) -> Box2D<f64, ScreenSpace> {
215        Box2D::new(
216            Point2D::new(
217                circle.center.x - circle.radius,
218                circle.center.y - circle.radius,
219            ),
220            Point2D::new(
221                circle.center.x + circle.radius,
222                circle.center.y + circle.radius,
223            ),
224        )
225    }
226
227    /// maplibre/maplibre-native#4add9ea original name: query_internal
228    fn query_internal<F>(&self, query_bbox: &Box2D<f64, ScreenSpace>, mut result_fn: F)
229    where
230        F: FnMut(T, Box2D<f64, ScreenSpace>) -> bool,
231    {
232        let mut seen_boxes = HashSet::new();
233        let mut seen_circles = HashSet::new();
234
235        if self.no_intersection(query_bbox) {
236            return;
237        } else if self.complete_intersection(query_bbox) {
238            for element in &self.box_elements {
239                if result_fn(element.0.clone(), element.1) {
240                    return;
241                }
242            }
243            for element in &self.circle_elements {
244                if result_fn(element.0.clone(), Self::convert_to_box(&element.1)) {
245                    return;
246                }
247            }
248            return;
249        }
250
251        let cx1 = self.convert_to_x_cell_coord(query_bbox.min.x);
252        let cy1 = self.convert_to_y_cell_coord(query_bbox.min.y);
253        let cx2 = self.convert_to_x_cell_coord(query_bbox.max.x);
254        let cy2 = self.convert_to_y_cell_coord(query_bbox.max.y);
255
256        let mut cell_index;
257        for x in cx1..=cx2 {
258            for y in cy1..=cy2 {
259                cell_index = self.x_cell_count * y + x;
260                // Look up other boxes
261                for uid in &self.box_cells[cell_index] {
262                    if !seen_boxes.contains(&uid) {
263                        seen_boxes.insert(uid);
264
265                        let pair = &self.box_elements[*uid as usize];
266                        let bbox = pair.1;
267                        if Self::boxes_collide(query_bbox, &bbox) && result_fn(pair.0.clone(), bbox)
268                        {
269                            return;
270                        }
271                    }
272                }
273
274                // Look up circles
275                for uid in &self.circle_cells[cell_index] {
276                    if !seen_circles.contains(&uid) {
277                        seen_circles.insert(uid);
278
279                        let pair = &self.circle_elements[*uid as usize];
280                        let bcircle = &pair.1;
281                        if Self::circle_and_box_collide(bcircle, query_bbox)
282                            && result_fn(pair.0.clone(), Self::convert_to_box(bcircle))
283                        {
284                            return;
285                        }
286                    }
287                }
288            }
289        }
290    }
291
292    /// maplibre/maplibre-native#4add9ea original name: query_internal_circles
293    fn query_internal_circles<F>(&self, query_bcircle: &Circle<f64>, mut result_fn: F)
294    where
295        F: FnMut(T, Box2D<f64, ScreenSpace>) -> bool,
296    {
297        let mut seen_boxes = HashSet::new();
298        let mut seen_circles = HashSet::new();
299
300        let query_bbox = Self::convert_to_box(query_bcircle);
301        if self.no_intersection(&query_bbox) {
302            return;
303        } else if self.complete_intersection(&query_bbox) {
304            for element in &self.box_elements {
305                if result_fn(element.0.clone(), element.1) {
306                    return;
307                }
308            }
309            for element in &self.circle_elements {
310                if result_fn(element.0.clone(), Self::convert_to_box(&element.1)) {
311                    return;
312                }
313            }
314        }
315
316        let cx1 = self.convert_to_x_cell_coord(query_bcircle.center.x - query_bcircle.radius);
317        let cy1 = self.convert_to_y_cell_coord(query_bcircle.center.y - query_bcircle.radius);
318        let cx2 = self.convert_to_x_cell_coord(query_bcircle.center.x + query_bcircle.radius);
319        let cy2 = self.convert_to_y_cell_coord(query_bcircle.center.y + query_bcircle.radius);
320
321        let mut cell_index;
322        for x in cx1..=cx2 {
323            for y in cy1..=cy2 {
324                cell_index = self.x_cell_count * y + x;
325                // Look up boxes
326                for uid in &self.box_cells[cell_index] {
327                    if !seen_boxes.contains(&uid) {
328                        seen_boxes.insert(uid);
329
330                        let pair = &self.box_elements[*uid as usize];
331                        let bbox = pair.1;
332                        if Self::circle_and_box_collide(query_bcircle, &bbox)
333                            && result_fn(pair.0.clone(), bbox)
334                        {
335                            return;
336                        }
337                    }
338                }
339
340                // Look up other circles
341                for uid in &self.circle_cells[cell_index] {
342                    if !seen_circles.contains(&uid) {
343                        seen_circles.insert(uid);
344
345                        let pair = &self.circle_elements[*uid as usize];
346                        let bcircle = &pair.1;
347                        if Self::circles_collide(query_bcircle, bcircle)
348                            && result_fn(pair.0.clone(), Self::convert_to_box(bcircle))
349                        {
350                            return;
351                        }
352                    }
353                }
354            }
355        }
356    }
357
358    /// maplibre/maplibre-native#4add9ea original name: convert_to_x_cell_coord
359    fn convert_to_x_cell_coord(&self, x: f64) -> usize {
360        f64::max(
361            0.0,
362            f64::min((self.x_cell_count - 1) as f64, f64::floor(x * self.x_scale)),
363        ) as usize
364    }
365
366    /// maplibre/maplibre-native#4add9ea original name: convert_to_y_cell_coord
367    fn convert_to_y_cell_coord(&self, y: f64) -> usize {
368        f64::max(
369            0.0,
370            f64::min((self.y_cell_count - 1) as f64, f64::floor(y * self.y_scale)),
371        ) as usize
372    }
373
374    /// maplibre/maplibre-native#4add9ea original name: boxes_collide
375    fn boxes_collide(first: &Box2D<f64, ScreenSpace>, second: &Box2D<f64, ScreenSpace>) -> bool {
376        first.min.x <= second.max.x
377            && first.min.y <= second.max.y
378            && first.max.x >= second.min.x
379            && first.max.y >= second.min.y
380    }
381
382    /// maplibre/maplibre-native#4add9ea original name: circles_collide
383    fn circles_collide(first: &Circle<f64>, second: &Circle<f64>) -> bool {
384        let dx = second.center.x - first.center.x;
385        let dy = second.center.y - first.center.y;
386        let both_radii = first.radius + second.radius;
387        (both_radii * both_radii) > (dx * dx + dy * dy)
388    }
389
390    /// maplibre/maplibre-native#4add9ea original name: circle_and_box_collide
391    fn circle_and_box_collide(circle: &Circle<f64>, box_: &Box2D<f64, ScreenSpace>) -> bool {
392        let half_rect_width = (box_.max.x - box_.min.x) / 2.0;
393        let dist_x = (circle.center.x - (box_.min.x + half_rect_width)).abs();
394        if dist_x > (half_rect_width + circle.radius) {
395            return false;
396        }
397
398        let half_rect_height = (box_.max.y - box_.min.y) / 2.0;
399        let dist_y = (circle.center.y - (box_.min.y + half_rect_height)).abs();
400        if dist_y > (half_rect_height + circle.radius) {
401            return false;
402        }
403
404        if dist_x <= half_rect_width || dist_y <= half_rect_height {
405            return true;
406        }
407
408        let dx = dist_x - half_rect_width;
409        let dy = dist_y - half_rect_height;
410        (dx * dx + dy * dy) <= (circle.radius * circle.radius)
411    }
412}
413
414#[cfg(test)]
415mod tests {
416    use super::*;
417
418    #[test]
419    /// maplibre/maplibre-native#4add9ea original name: indexes_features
420    fn indexes_features() {
421        let mut grid = GridIndex::<i16>::new(100.0, 100.0, 10);
422        grid.insert(
423            0,
424            Box2D::new(Point2D::new(4.0, 10.0), Point2D::new(6.0, 30.0)),
425        );
426        grid.insert(
427            1,
428            Box2D::new(Point2D::new(4.0, 10.0), Point2D::new(30.0, 12.0)),
429        );
430        grid.insert(
431            2,
432            Box2D::new(Point2D::new(-10.0, 30.0), Point2D::new(5.0, 35.0)),
433        );
434
435        assert_eq!(
436            grid.query(&Box2D::new(
437                Point2D::new(4.0, 10.0),
438                Point2D::new(5.0, 11.0)
439            )),
440            vec![0i16, 1]
441        );
442        assert_eq!(
443            grid.query(&Box2D::new(
444                Point2D::new(24.0, 10.0),
445                Point2D::new(25.0, 11.0)
446            )),
447            vec![1i16]
448        );
449        let vec1: Vec<i16> = vec![];
450        assert_eq!(
451            grid.query(&Box2D::new(
452                Point2D::new(40.0, 40.0),
453                Point2D::new(100.0, 100.0)
454            )),
455            vec1
456        );
457        assert_eq!(
458            grid.query(&Box2D::new(
459                Point2D::new(-6.0, 0.0),
460                Point2D::new(3.0, 100.0)
461            )),
462            vec![2i16]
463        );
464        assert_eq!(
465            grid.query(&Box2D::new(
466                Point2D::new(-1000.0, -1000.0),
467                Point2D::new(1000.0, 1000.0)
468            )),
469            vec![0i16, 1, 2]
470        );
471    }
472    #[test]
473    /// maplibre/maplibre-native#4add9ea original name: duplicate_keys
474    fn duplicate_keys() {
475        let mut grid = GridIndex::<i16>::new(100.0, 100.0, 10);
476        const KEY: i16 = 123;
477        grid.insert(
478            KEY,
479            Box2D::new(Point2D::new(3.0, 4.0), Point2D::new(4.0, 4.0)),
480        );
481        grid.insert(
482            KEY,
483            Box2D::new(Point2D::new(13.0, 13.0), Point2D::new(14.0, 14.0)),
484        );
485        grid.insert(
486            KEY,
487            Box2D::new(Point2D::new(23.0, 23.0), Point2D::new(24.0, 24.0)),
488        );
489
490        assert_eq!(
491            grid.query(&Box2D::new(
492                Point2D::new(0.0, 0.0),
493                Point2D::new(30.0, 30.0)
494            )),
495            vec![KEY, KEY, KEY]
496        );
497    }
498
499    /// maplibre/maplibre-native#4add9ea original name: i16_closure
500    fn i16_closure() {}
501
502    #[test]
503    /// maplibre/maplibre-native#4add9ea original name: circle_circle
504    fn circle_circle() {
505        let mut grid = GridIndex::<i16>::new(100.0, 100.0, 10);
506        grid.insert_circle(0, Circle::new(Point2D::new(50.0, 50.0), 10.0));
507        grid.insert_circle(1, Circle::new(Point2D::new(60.0, 60.0), 15.0));
508        grid.insert_circle(2, Circle::new(Point2D::new(-10.0, 110.0), 20.0));
509
510        assert!(grid.hit_test_circle::<Box<dyn Fn(&i16) -> bool>>(
511            &Circle::new(Point2D::new(55.0, 55.0), 2.0),
512            None
513        ));
514        assert!(!grid.hit_test_circle::<Box<dyn Fn(&i16) -> bool>>(
515            &Circle::new(Point2D::new(10.0, 10.0), 10.0),
516            None
517        ));
518        assert!(grid.hit_test_circle::<Box<dyn Fn(&i16) -> bool>>(
519            &Circle::new(Point2D::new(0.0, 100.0), 10.0),
520            None
521        ));
522        assert!(grid.hit_test_circle::<Box<dyn Fn(&i16) -> bool>>(
523            &Circle::new(Point2D::new(80.0, 60.0), 10.0),
524            None
525        ));
526    }
527
528    #[test]
529    /// maplibre/maplibre-native#4add9ea original name: circle_box
530    fn circle_box() {
531        let mut grid = GridIndex::<i16>::new(100.0, 100.0, 10);
532        grid.insert_circle(0, Circle::new(Point2D::new(50.0, 50.0), 10.0));
533        grid.insert_circle(1, Circle::new(Point2D::new(60.0, 60.0), 15.0));
534        grid.insert_circle(2, Circle::new(Point2D::new(-10.0, 110.0), 20.0));
535
536        assert_eq!(
537            grid.query(&Box2D::new(
538                Point2D::new(45.0, 45.0),
539                Point2D::new(55.0, 55.0)
540            )),
541            vec![0, 1]
542        );
543        let vec1: Vec<i16> = vec![];
544        assert_eq!(
545            grid.query(&Box2D::new(
546                Point2D::new(0.0, 0.0),
547                Point2D::new(30.0, 30.0)
548            )),
549            vec1
550        );
551        assert_eq!(
552            grid.query(&Box2D::new(
553                Point2D::new(0.0, 80.0),
554                Point2D::new(20.0, 100.0)
555            )),
556            vec![2]
557        );
558    }
559
560    #[test]
561    /// maplibre/maplibre-native#4add9ea original name: indexes_features_overflow
562    fn indexes_features_overflow() {
563        let mut grid = GridIndex::<i16>::new(5000.0, 5000.0, 25);
564        grid.insert(
565            0,
566            Box2D::new(Point2D::new(4500.0, 4500.0), Point2D::new(4900.0, 4900.0)),
567        );
568        assert_eq!(
569            grid.query(&Box2D::new(
570                Point2D::new(4000.0, 4000.0),
571                Point2D::new(5000.0, 5000.0)
572            )),
573            vec![0]
574        );
575    }
576}
maplibre/legacy/grid_index.rs

maplibre/legacy/
grid_index.rs
