facett-geomap/src/osm2d/cluster.rs
//! **Pin clustering for the 2D NAVIGATOR** — the piece the pin overlay was
//! missing. Pins are already labelled, stably-identified, hit-testable and glued
//! to their `(lon, lat)` through the f64 [`MercatorCamera`](super::MercatorCamera)
//! lane; what they had no answer for was **density**. Zoom out over a city and
//! several hundred markers pile into a few hundred pixels: overlapping teardrops,
//! unreadable labels, and a click that resolves to whichever pin happened to be
//! painted last. Every serious 2D navigator answers this the same way — collapse
//! co-located markers into ONE badge carrying the count, and split it back apart
//! as you zoom in.
//!
//! ## The design
//!
//! **Screen-space grid clustering.** Pins are binned into a fixed-pixel lattice
//! *after* projection, not into a geographic grid. That is the property that
//! makes it feel right: the clustering threshold is "these markers would visually
//! collide", which is a screen distance, so the same lattice works at every zoom
//! and every latitude (a geographic grid clusters far too aggressively near the
//! poles, where Mercator stretches).
//!
//! **Deterministic.** Bins are walked in row-major order and members in input
//! order, so the same pins + camera always produce the same clusters in the same
//! order — a golden/robot oracle can assert exact contents, and a cluster's id is
//! stable frame to frame.
//!
//! **Singles stay singles.** A bin holding exactly one pin yields that pin
//! unchanged, with its own stable id — so a lone marker never turns into a "1"
//! badge and its click still resolves to the real pin id.
//!
//! **The cluster's anchor is the centroid of its members**, in screen space, so
//! the badge sits visually where the group is rather than on an arbitrary lattice
//! corner.
//!
//! ## Cost
//!
//! One pass over the pins with an `O(1)` bin index each — `O(n)` total, no
//! sorting, no distance matrix. `benches/heavy_navigator.rs` measures it against
//! the point-grid cull on the same frame.
use std::collections::HashMap;
/// How wide a clustering bin is, in **screen pixels**. Two pins closer than this
/// would overlap their ~13 px markers, so they collapse. Chosen as roughly three
/// marker widths: tight enough that a cluster badge really is hiding a pile, wide
/// enough that adjacent-but-readable markers stay separate.
pub const CLUSTER_BIN_PX: f32 = 44.0;
/// One drawable marker after clustering: either a single pin or a group.
#[derive(Clone, Debug, PartialEq)]
pub struct ClusterNode {
/// Where to draw it — screen pixels (the centroid of the members).
pub pos: egui::Pos2,
/// How many pins it stands for. `1` = a real single pin.
pub count: usize,
/// **Stable id.** For a single, the pin's own id — so a click resolves exactly
/// as it did before clustering existed. For a group, a deterministic
/// `cluster:<n>@<first member id>` derived from its *first member in input
/// order*, so the id does not churn between frames while the group is stable.
pub id: String,
/// The label to draw: the pin's label for a single, the count for a group.
pub label: String,
/// Indices into the source pin slice, in input order. A click on a group can
/// use these to zoom to the members' bounds instead of selecting one.
pub members: Vec<usize>,
}
impl ClusterNode {
/// Is this a real single pin (not a collapsed group)?
#[must_use]
pub fn is_single(&self) -> bool {
self.count == 1
}
}
/// Cluster already-projected pins into screen-space bins of `bin_px`.
///
/// `projected` is `(screen position, pin id, pin label)` in **input order** —
/// the caller has already run the f64 `to_px` lane and dropped off-screen pins,
/// so this function is pure screen-space geometry and is directly testable with
/// no camera.
///
/// Returns one [`ClusterNode`] per occupied bin, in deterministic (row-major bin,
/// then input) order. `bin_px <= 0` disables clustering: every pin comes back as
/// its own single, unchanged.
#[must_use]
pub fn cluster_projected(
projected: &[(egui::Pos2, String, String)],
bin_px: f32,
) -> Vec<ClusterNode> {
if projected.is_empty() {
return Vec::new();
}
if bin_px <= 0.0 {
return projected
.iter()
.enumerate()
.map(|(i, (pos, id, label))| ClusterNode {
pos: *pos,
count: 1,
id: id.clone(),
label: label.clone(),
members: vec![i],
})
.collect();
}
// Bin index → member indices, plus the bin's first-seen order so the output is
// deterministic regardless of HashMap iteration order.
let mut bins: HashMap<(i32, i32), Vec<usize>> = HashMap::new();
let mut order: Vec<(i32, i32)> = Vec::new();
for (i, (pos, _, _)) in projected.iter().enumerate() {
let key = ((pos.x / bin_px).floor() as i32, (pos.y / bin_px).floor() as i32);
let slot = bins.entry(key).or_default();
if slot.is_empty() {
order.push(key);
}
slot.push(i);
}
// Row-major over the bins actually occupied — a stable, camera-independent
// ordering (first-seen order would depend on the input order alone, which is
// also stable, but row-major reads naturally top-left → bottom-right).
order.sort_unstable_by_key(|&(gx, gy)| (gy, gx));
order
.into_iter()
.map(|key| {
let members = bins.remove(&key).expect("every ordered key was inserted");
let n = members.len();
if n == 1 {
let i = members[0];
let (pos, id, label) = &projected[i];
return ClusterNode {
pos: *pos,
count: 1,
id: id.clone(),
label: label.clone(),
members,
};
}
// Centroid of the members, so the badge sits where the pile is.
let (mut sx, mut sy) = (0.0f32, 0.0f32);
for &i in &members {
sx += projected[i].0.x;
sy += projected[i].0.y;
}
let inv = 1.0 / n as f32;
let first_id = &projected[members[0]].1;
ClusterNode {
pos: egui::pos2(sx * inv, sy * inv),
count: n,
id: format!("cluster:{n}@{first_id}"),
label: n.to_string(),
members,
}
})
.collect()
}
/// The **geographic bounds** of a cluster's members — what "click a cluster to
/// zoom into it" needs. Returns `[lon_min, lat_min, lon_max, lat_max]`, or `None`
/// for an empty member list.
#[must_use]
pub fn member_lonlat_bbox(members: &[usize], pins: &[super::Pin]) -> Option<[f64; 4]> {
let mut it = members.iter().filter_map(|&i| pins.get(i)).map(|p| p.lonlat);
let (lon0, lat0) = it.next()?;
let mut bbox = [lon0, lat0, lon0, lat0];
for (lon, lat) in it {
bbox[0] = bbox[0].min(lon);
bbox[1] = bbox[1].min(lat);
bbox[2] = bbox[2].max(lon);
bbox[3] = bbox[3].max(lat);
}
Some(bbox)
}
#[cfg(test)]
mod tests {
use super::*;
use egui::pos2;
fn p(x: f32, y: f32, id: &str) -> (egui::Pos2, String, String) {
(pos2(x, y), id.to_string(), id.to_string())
}
#[test]
fn empty_input_yields_no_clusters() {
assert!(cluster_projected(&[], CLUSTER_BIN_PX).is_empty());
}
/// A lone marker must stay a real pin — same id, same label, same position —
/// so its click still resolves to the pin and it never renders as a "1" badge.
#[test]
fn a_lone_pin_stays_a_single_with_its_own_id() {
let out = cluster_projected(&[p(100.0, 100.0, "Storgatan 1")], CLUSTER_BIN_PX);
assert_eq!(out.len(), 1);
assert!(out[0].is_single());
assert_eq!(out[0].id, "Storgatan 1");
assert_eq!(out[0].label, "Storgatan 1");
assert_eq!(out[0].pos, pos2(100.0, 100.0));
assert_eq!(out[0].members, vec![0]);
}
/// The core contract, at the boundary: pins closer than one bin collapse;
/// pins further apart than one bin do not. Swept across the bin edge so this
/// is not a single-value test.
#[test]
fn pins_collapse_exactly_when_they_share_a_bin() {
// Anchor at the centre of bin (2,2) so a small offset cannot cross an edge.
let bin = CLUSTER_BIN_PX;
let base = pos2(bin * 2.5, bin * 2.5);
for &dx in &[0.0f32, 1.0, 5.0, bin * 0.4] {
let out = cluster_projected(
&[p(base.x, base.y, "a"), p(base.x + dx, base.y, "b")],
bin,
);
assert_eq!(out.len(), 1, "offset {dx} is inside one bin → one cluster");
assert_eq!(out[0].count, 2);
}
for &dx in &[bin * 1.5, bin * 3.0, bin * 40.0] {
let out = cluster_projected(
&[p(base.x, base.y, "a"), p(base.x + dx, base.y, "b")],
bin,
);
assert_eq!(out.len(), 2, "offset {dx} spans bins → two singles");
assert!(out.iter().all(ClusterNode::is_single));
}
}
/// A group's badge sits at the CENTROID of its members, not on a lattice
/// corner — otherwise the count floats away from the pile it describes.
#[test]
fn a_group_anchors_on_its_members_centroid() {
let bin = CLUSTER_BIN_PX;
let (x, y) = (bin * 4.1, bin * 4.1);
let out = cluster_projected(
&[p(x, y, "a"), p(x + 10.0, y, "b"), p(x + 20.0, y, "c")],
bin,
);
assert_eq!(out.len(), 1);
assert_eq!(out[0].count, 3);
assert_eq!(out[0].label, "3", "the badge shows the count");
assert!((out[0].pos.x - (x + 10.0)).abs() < 1e-4, "centroid x");
assert!((out[0].pos.y - y).abs() < 1e-4, "centroid y");
assert_eq!(out[0].members, vec![0, 1, 2], "members keep input order");
}
/// DETERMINISM (FC-7): the same input must give byte-identical output every
/// time. The grouping runs through a `HashMap`, so without the explicit
/// row-major sort the cluster ORDER would follow hash iteration and the
/// oracle below would flap. 64 repeats.
#[test]
fn clustering_is_deterministic_over_repeats() {
let bin = CLUSTER_BIN_PX;
let pins: Vec<_> = (0..200)
.map(|i| {
let x = (i % 20) as f32 * 17.0;
let y = (i / 20) as f32 * 23.0;
p(x, y, &format!("pin-{i}"))
})
.collect();
let first = cluster_projected(&pins, bin);
assert!(first.len() > 1 && first.len() < pins.len(), "a real mix of singles and groups");
for _ in 0..64 {
assert_eq!(cluster_projected(&pins, bin), first, "clustering must not depend on hash order");
}
// Row-major: the output reads top-left → bottom-right.
for w in first.windows(2) {
let (a, b) = (w[0].pos, w[1].pos);
assert!(b.y > a.y - CLUSTER_BIN_PX || (b.y - a.y).abs() < CLUSTER_BIN_PX, "row-major order");
}
}
/// CONSERVATION: every pin is accounted for exactly once. A clusterer that
/// drops or double-counts markers is worse than none — the count badge would
/// lie. Swept over several densities.
#[test]
fn every_pin_is_in_exactly_one_cluster() {
for n in [1usize, 2, 17, 250, 3000] {
let pins: Vec<_> = (0..n)
.map(|i| {
let x = ((i * 37) % 800) as f32;
let y = ((i * 53) % 600) as f32;
p(x, y, &format!("p{i}"))
})
.collect();
let out = cluster_projected(&pins, CLUSTER_BIN_PX);
let total: usize = out.iter().map(|c| c.count).sum();
assert_eq!(total, n, "n={n}: counts sum to the input size");
let mut seen: Vec<usize> = out.iter().flat_map(|c| c.members.iter().copied()).collect();
seen.sort_unstable();
seen.dedup();
assert_eq!(seen.len(), n, "n={n}: every index appears exactly once");
assert_eq!(out.iter().map(|c| c.members.len()).sum::<usize>(), n, "no index appears twice");
}
}
/// Clustering must be DISABLEABLE, and disabling it must be lossless — every
/// pin comes back as itself, in input order, with its own id.
#[test]
fn a_non_positive_bin_disables_clustering_losslessly() {
let pins: Vec<_> = (0..50).map(|i| p(1.0, 1.0, &format!("p{i}"))).collect();
for bin in [0.0f32, -1.0] {
let out = cluster_projected(&pins, bin);
assert_eq!(out.len(), 50, "bin {bin}: nothing collapses");
assert!(out.iter().all(ClusterNode::is_single));
for (i, c) in out.iter().enumerate() {
assert_eq!(c.id, format!("p{i}"));
assert_eq!(c.members, vec![i]);
}
}
// ...and with clustering ON the same all-co-located set is ONE badge.
let on = cluster_projected(&pins, CLUSTER_BIN_PX);
assert_eq!(on.len(), 1);
assert_eq!(on[0].count, 50);
}
/// A cluster id is stable while its membership is, and distinguishes groups
/// of different size at the same place — so `state_json` can report it and a
/// robot can assert on it.
#[test]
fn cluster_ids_are_stable_and_size_distinguishing() {
let bin = CLUSTER_BIN_PX;
let two = cluster_projected(&[p(50.0, 50.0, "a"), p(52.0, 50.0, "b")], bin);
let three =
cluster_projected(&[p(50.0, 50.0, "a"), p(52.0, 50.0, "b"), p(54.0, 50.0, "c")], bin);
assert_eq!(two[0].id, "cluster:2@a");
assert_eq!(three[0].id, "cluster:3@a");
assert_ne!(two[0].id, three[0].id, "a different pile is a different id");
}
#[test]
fn member_bbox_spans_the_group_and_is_none_when_empty() {
let pins = vec![
super::super::Pin::new(17.6, 59.6, "a"),
super::super::Pin::new(17.8, 59.4, "b"),
super::super::Pin::new(17.7, 59.9, "c"),
];
let bbox = member_lonlat_bbox(&[0, 1, 2], &pins).unwrap();
assert!((bbox[0] - 17.6).abs() < 1e-9 && (bbox[2] - 17.8).abs() < 1e-9);
assert!((bbox[1] - 59.4).abs() < 1e-9 && (bbox[3] - 59.9).abs() < 1e-9);
assert_eq!(member_lonlat_bbox(&[], &pins), None);
// Out-of-range indices are skipped, not panicked on.
assert_eq!(member_lonlat_bbox(&[99], &pins), None);
}
}