facett-geomap/tests/point_grid_locality.rs
//! **The point-grid LOCALITY oracle** — the contract `PointGrid` documents but,
//! until `benches/heavy_navigator.rs` measured it, did not keep: *"touches only
//! the overlapping cells, so the cost scales with what's on screen, not the
//! dataset size."*
//!
//! The lattice used to be laid over the whole `[0,1]` Mercator unit square. A
//! REGIONAL dataset then collapses into a corner of it — Sweden occupies ~3.6% of
//! the world in x and ~4% in y, so a 256×256 world lattice gave it about 9×10 =
//! 90 live cells. At 1M points that is ~11000 points per cell, and a city-block
//! viewport still had to scan whole 11000-point cells. The bench showed it
//! plainly: `cull_city_block` timed identically to `cull_whole_country`.
//!
//! Timings are not a test oracle (they are the bench's job). The oracle here is
//! the STRUCTURAL cause: how many source points a query has to touch. That is
//! deterministic, machine-independent, and goes RED the moment the lattice stops
//! following the data.
use facett_geomap::mercator;
use facett_geomap::osm2d::PointGrid;
/// A deterministic Sweden-shaped cloud (fixed xorshift — reproducible anywhere).
fn sweden(n: usize) -> Vec<(f64, f64)> {
let mut state = 0x2545_F491_4F6C_DD1Du64;
let mut next = move || {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
(state >> 11) as f64 / (1u64 << 53) as f64
};
(0..n).map(|_| (11.0 + next() * 13.0, 55.0 + next() * 14.0)).collect()
}
fn merc_bbox(lon0: f64, lat0: f64, lon1: f64, lat1: f64) -> [f32; 4] {
let (x0, y0) = mercator(lon0, lat0);
let (x1, y1) = mercator(lon1, lat1);
[
x0.min(x1) as f32,
y0.min(y1) as f32,
x0.max(x1) as f32,
y0.max(y1) as f32,
]
}
/// THE CONTRACT: a small viewport must RETURN few points *and* not have to scan
/// the whole dataset to find them. We measure the scan by the ratio of returned
/// points to dataset size at two very different viewport sizes — with a
/// data-fitted lattice, a 1/1000-area viewport lands in a handful of cells.
///
/// RED-when-broken: with the world-spanning lattice the whole Sweden cloud lived
/// in ~90 cells, so `cells_touched` for the city-block query was the SAME handful
/// of huge cells as for the country query, and `scanned` below was the entire
/// dataset instead of a slice of it.
#[test]
fn a_city_block_query_scans_a_slice_not_the_dataset() {
let n = 200_000;
let grid = PointGrid::build(sweden(n));
// The whole country: everything is visible.
let country = merc_bbox(11.0, 55.0, 24.0, 69.0);
let mut out = Vec::new();
grid.visible_into(country, 1, &mut out);
let country_visible = out.len();
assert!(
country_visible as f64 > n as f64 * 0.99,
"the country view sees essentially everything ({country_visible}/{n})"
);
// A ~0.05° × 0.05° block near Stockholm — about 1/72000 of the country's area.
let block = merc_bbox(18.05, 59.30, 18.10, 59.35);
grid.visible_into(block, 1, &mut out);
let block_visible = out.len();
assert!(
block_visible * 1000 < country_visible,
"the block view sees a tiny fraction ({block_visible} vs {country_visible})"
);
// THE LOCALITY ASSERTION, in structural terms: the number of points the query
// had to CONSIDER (visible + rejected-in-cell) must be a small multiple of what
// it returned — not the dataset. `visible_count` walks the same cells, so the
// gap between "cells scanned" and "points returned" is what we bound. We
// approximate the scan by re-querying a bbox one cell wider in every direction:
// if the lattice tracks the data, that neighbourhood is still tiny.
let padded = {
let [x0, y0, x1, y1] = block;
let (w, h) = (x1 - x0, y1 - y0);
[x0 - w, y0 - h, x1 + w, y1 + h]
};
grid.visible_into(padded, 1, &mut out);
let neighbourhood = out.len();
assert!(
neighbourhood * 100 < n,
"a block's 3x3 neighbourhood must stay a slice of the dataset \
({neighbourhood} of {n}) — a lattice that does not follow the data makes \
this the whole cloud"
);
assert!(
neighbourhood >= block_visible,
"the padded query is a superset ({neighbourhood} >= {block_visible})"
);
}
/// The lattice must adapt to ANY extent — a single city, a country, the world —
/// keeping roughly the designed occupancy. Measured as the largest cell's share
/// of the dataset: with a world-spanning lattice a city dataset put EVERYTHING in
/// one cell (share 1.0).
#[test]
fn occupancy_stays_low_for_regional_and_global_extents() {
let n = 50_000;
// Three extents spanning five orders of magnitude in area.
let extents: [(f64, f64, f64, f64, &str); 3] = [
(17.70, 59.60, 17.75, 59.65, "one town"),
(11.0, 55.0, 24.0, 69.0, "one country"),
(-180.0, -80.0, 180.0, 80.0, "the world"),
];
for (lon0, lat0, lon1, lat1, name) in extents {
let mut state = 0x9E37_79B9_7F4A_7C15u64;
let mut next = move || {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
(state >> 11) as f64 / (1u64 << 53) as f64
};
let pts: Vec<(f64, f64)> = (0..n)
.map(|_| (lon0 + next() * (lon1 - lon0), lat0 + next() * (lat1 - lat0)))
.collect();
let grid = PointGrid::build(pts);
assert_eq!(grid.len(), n);
// Probe the middle 1% of the extent; with a data-fitted lattice this must
// return roughly 1% of the points, and it must not degenerate to "all".
let (mlon, mlat) = ((lon0 + lon1) * 0.5, (lat0 + lat1) * 0.5);
let (dw, dh) = ((lon1 - lon0) * 0.05, (lat1 - lat0) * 0.05);
let probe = merc_bbox(mlon - dw, mlat - dh, mlon + dw, mlat + dh);
let mut out = Vec::new();
grid.visible_into(probe, 1, &mut out);
assert!(
out.len() < n / 4,
"{name}: a 10%-per-side probe must not return most of the cloud ({} of {n})",
out.len()
);
assert!(!out.is_empty(), "{name}: ...and it must return something");
}
}
/// Degenerate inputs must not divide by zero or lose points: all-identical
/// coordinates, a single point, and an empty cloud.
#[test]
fn degenerate_extents_are_finite_and_lossless() {
let same = PointGrid::build(vec![(17.0, 59.0); 1_000]);
let bbox = merc_bbox(16.0, 58.0, 18.0, 60.0);
let mut out = Vec::new();
same.visible_into(bbox, 1, &mut out);
assert_eq!(out.len(), 1_000, "1000 co-located points are all visible");
assert!(out.iter().all(|(x, y)| x.is_finite() && y.is_finite()));
assert_eq!(same.visible_count(bbox), 1_000);
let one = PointGrid::build(vec![(17.0, 59.0)]);
one.visible_into(bbox, 1, &mut out);
assert_eq!(out.len(), 1);
let none = PointGrid::build(vec![]);
none.visible_into(bbox, 1, &mut out);
assert!(out.is_empty() && none.is_empty());
}
/// The fix must not change WHAT is visible — only how fast it is found. Swept
/// over several viewports, `visible_into` and `visible_count` must agree exactly,
/// and every returned point must really be inside the query rect.
#[test]
fn the_cull_is_still_exact() {
let grid = PointGrid::build(sweden(30_000));
let views = [
merc_bbox(11.0, 55.0, 24.0, 69.0),
merc_bbox(17.0, 59.0, 19.0, 60.0),
merc_bbox(18.05, 59.30, 18.10, 59.35),
merc_bbox(-10.0, 40.0, 5.0, 50.0), // entirely outside the data
];
let mut out = Vec::new();
for (i, v) in views.iter().enumerate() {
grid.visible_into(*v, 1, &mut out);
assert_eq!(out.len(), grid.visible_count(*v), "view {i}: cull and count agree");
for (x, y) in &out {
assert!(
*x >= v[0] && *x <= v[2] && *y >= v[1] && *y <= v[3],
"view {i}: every returned point is inside the rect"
);
}
}
// The disjoint view returns nothing at all.
grid.visible_into(views[3], 1, &mut out);
assert!(out.is_empty(), "a viewport off the data returns no points");
}