maps_engine_rust/
cluster.rs

1//! Grid-based marker clustering. Port of `cluster.ts`.
2
3use crate::geo::LonLat;
4use crate::projection::to_pixels;
5use std::collections::HashMap;
6
7/// A single cluster of markers.
8#[derive(Debug, Clone)]
9pub struct Cluster {
10    /// Cluster centroid.
11    pub center: LonLat,
12    /// Number of markers in the cluster.
13    pub count: usize,
14    /// Indices of the clustered markers in the input slice.
15    pub members: Vec<usize>,
16}
17
18/// Cluster markers with a grid of `cell_px` pixels at `zoom`.
19///
20/// Markers falling into the same grid cell are merged. Single-marker
21/// cells are returned as clusters with `count == 1`.
22pub fn cluster(markers: &[LonLat], zoom: u8, cell_px: f64) -> Vec<Cluster> {
23    let mut cells: HashMap<(i64, i64), Vec<usize>> = HashMap::new();
24    for (i, m) in markers.iter().enumerate() {
25        let (px, py) = to_pixels(m.lon, m.lat, zoom);
26        let key = ((px / cell_px).floor() as i64, (py / cell_px).floor() as i64);
27        cells.entry(key).or_default().push(i);
28    }
29    cells
30        .into_values()
31        .map(|members| {
32            let count = members.len();
33            let (slon, slat) = members.iter().fold((0.0, 0.0), |(a, b), &i| {
34                (a + markers[i].lon, b + markers[i].lat)
35            });
36            Cluster {
37                center: LonLat::new(slon / count as f64, slat / count as f64),
38                count,
39                members,
40            }
41        })
42        .collect()
43}
44
45#[cfg(test)]
46mod tests {
47    use super::*;
48
49    #[test]
50    fn distant_markers_stay_separate() {
51        let ms = vec![LonLat::new(105.0, 21.0), LonLat::new(106.0, 22.0)];
52        let c = cluster(&ms, 10, 64.0);
53        assert_eq!(c.len(), 2);
54        assert!(c.iter().all(|x| x.count == 1));
55    }
56
57    #[test]
58    fn nearby_markers_merge() {
59        let ms = vec![
60            LonLat::new(105.8500, 21.0200),
61            LonLat::new(105.8501, 21.0201),
62            LonLat::new(105.8502, 21.0199),
63        ];
64        let c = cluster(&ms, 14, 64.0);
65        assert_eq!(c.len(), 1);
66        assert_eq!(c[0].count, 3);
67        assert_eq!(c[0].members.len(), 3);
68    }
69
70    #[test]
71    fn members_cover_all_inputs() {
72        let ms: Vec<LonLat> = (0..50)
73            .map(|i| LonLat::new(105.0 + i as f64 * 0.01, 21.0))
74            .collect();
75        let c = cluster(&ms, 10, 64.0);
76        let total: usize = c.iter().map(|x| x.count).sum();
77        assert_eq!(total, 50);
78    }
79}
maps_engine_rust/cluster.rs

maps_engine_rust/
cluster.rs
