facett-core/src/legibility.rs
//! **Legibility at scale** — the shared screen-space toolbox that makes a 100 000-node
//! graph (or a 1 000 000-pin map) something a human can actually *read*.
//!
//! Speed and legibility are different problems and they need different cures. The GPU
//! cloud lane ([`crate::render::gpu::graphcloud`], feature `wgpu`) answers "the frame
//! takes 33 ms" by not tessellating on the CPU. It does **nothing** for "there are
//! 40 000 labels stacked on 400 pixels and 900 000 edges have merged into one grey
//! rectangle". That is this module.
//!
//! Three primitives, all pure (no egui painting, no GPU), all deterministic, all
//! headless-testable:
//!
//! | primitive | the defect it cures |
//! |---|---|
//! | [`ScreenGrid`] | hover/pick that linear-scans every node on every mouse move |
//! | [`place_labels`] | labels that overplot into unreadable mush |
//! | [`thin_edges`] | a hairball where every pixel is saturated and structure is invisible |
//!
//! # The honesty fields
//!
//! The map side (`facett-geomap`'s `PointGrid`) shipped with a doc comment promising
//! "the cost scales with what is on screen, not the dataset size" — and it did not: the
//! lattice spanned the whole world, so a regional dataset collapsed into a corner of it
//! and a city-block query still swept 11 000-point cells. **Nothing was red**, because
//! the claim was prose.
//!
//! So every structure here reports the work it actually did as DATA:
//! [`NearestHit::candidates`] (points distance-tested), [`LabelPlacement::considered`]
//! / [`LabelPlacement::collision_tests`], [`EdgeThinResult::peak_density_before`] /
//! [`EdgeThinResult::peak_density`]. A test asserts on those numbers instead of on a
//! sentence, and the same lie cannot be told twice.
//!
//! # Determinism
//!
//! Every function is a pure function of its inputs, ordered by explicit sort keys that
//! end in the input index — never by `HashMap` iteration. Two identical frames produce
//! byte-identical output, so a golden/robot oracle can assert exact contents (FC-7).
use egui::{Pos2, Rect, Vec2};
// ─────────────────────────────────────────────────────────────────────────────
// 1. ScreenGrid — the screen-space spatial index for picking + hover
// ─────────────────────────────────────────────────────────────────────────────
/// The average number of points a bin should hold. The lattice is sized from the
/// data's bounding box and the point count so this holds *at any extent* — which is
/// exactly the property `facett-geomap`'s world-spanning lattice did not have.
const TARGET_PER_CELL: f32 = 8.0;
/// A uniform **screen-space** bin lattice over a set of projected points, for
/// `O(neighbourhood)` nearest / rect queries.
///
/// # Why a second grid, when `facett-geomap::PointGrid` exists (L5)
///
/// They index different spaces for different lifetimes and are not
/// interchangeable. `PointGrid` bins `f64` **Mercator world** units and is built
/// **once per dataset** — it survives pan/zoom because world coordinates do.
/// `ScreenGrid` bins `f32` **screen pixels** and is rebuilt when the projection
/// changes, because a screen coordinate is only meaningful for one camera. A graph
/// pane picks in screen space (a chip's hit radius is a pixel radius, not a world
/// radius), and a *label* collision is by definition a pixel collision — so this is
/// the lattice both of those want. The sizing *discipline* (span the DATA bbox, not
/// some fixed universe) is the shared lesson, and it is applied here from the start.
///
/// Empty input builds an empty grid whose queries return nothing — never a panic and
/// never a divide by zero.
#[derive(Clone, Debug)]
pub struct ScreenGrid {
/// Min corner of the indexed bounding box.
origin: Pos2,
/// Bin edge length in px (always `> 0`).
cell: f32,
cols: usize,
rows: usize,
/// Row-major `cols × rows` buckets of point indices, each in ascending order.
bins: Vec<Vec<u32>>,
len: usize,
}
/// What a [`ScreenGrid::nearest`] probe found — and, crucially, **how much work it
/// did** to find it. `candidates` is the anti-lie field: a linear scan reports
/// `candidates == len`, an honest index reports a small neighbourhood.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct NearestHit {
/// Index into the `points` slice the grid was built from.
pub index: u32,
/// Distance in px from the probe to that point.
pub dist: f32,
/// How many points were actually distance-tested to produce this answer.
pub candidates: usize,
}
impl ScreenGrid {
/// Build a lattice over `points`, auto-sizing the bin so the average occupancy is
/// [`TARGET_PER_CELL`] **over the data's own bounding box**.
#[must_use]
pub fn build(points: &[Pos2]) -> Self {
Self::build_inner(points, None)
}
/// Build with an explicit bin edge in px — for label/edge lattices where the cell
/// must match a known collision scale rather than the point density.
#[must_use]
pub fn build_with_cell(points: &[Pos2], cell: f32) -> Self {
Self::build_inner(points, Some(cell))
}
fn build_inner(points: &[Pos2], forced_cell: Option<f32>) -> Self {
let finite = |p: &Pos2| p.x.is_finite() && p.y.is_finite();
let mut min = Pos2::new(f32::INFINITY, f32::INFINITY);
let mut max = Pos2::new(f32::NEG_INFINITY, f32::NEG_INFINITY);
let mut n_finite = 0usize;
for p in points.iter().filter(|p| finite(p)) {
n_finite += 1;
min.x = min.x.min(p.x);
min.y = min.y.min(p.y);
max.x = max.x.max(p.x);
max.y = max.y.max(p.y);
}
if n_finite == 0 {
return Self {
origin: Pos2::ZERO,
cell: 1.0,
cols: 0,
rows: 0,
bins: Vec::new(),
len: points.len(),
};
}
// A degenerate extent (every point identical, or one point) still has to build
// a finite, lossless grid — so the span is floored, never zero.
let span_x = (max.x - min.x).max(1.0);
let span_y = (max.y - min.y).max(1.0);
let cell = match forced_cell {
Some(c) if c.is_finite() && c > 0.0 => c,
_ => {
let target_cells = (n_finite as f32 / TARGET_PER_CELL).max(1.0);
// Square-ish bins: area / target_cells, side = sqrt.
((span_x * span_y) / target_cells).sqrt().max(1e-3)
}
};
// Cap the lattice so a pathological cell/extent ratio cannot allocate the world.
const MAX_CELLS: usize = 1 << 22;
let mut cols = ((span_x / cell).ceil() as usize + 1).max(1);
let mut rows = ((span_y / cell).ceil() as usize + 1).max(1);
let mut cell = cell;
while cols.saturating_mul(rows) > MAX_CELLS {
cell *= 2.0;
cols = ((span_x / cell).ceil() as usize + 1).max(1);
rows = ((span_y / cell).ceil() as usize + 1).max(1);
}
let mut bins: Vec<Vec<u32>> = vec![Vec::new(); cols * rows];
for (i, p) in points.iter().enumerate() {
if !finite(p) {
continue;
}
let gx = (((p.x - min.x) / cell).floor() as isize).clamp(0, cols as isize - 1) as usize;
let gy = (((p.y - min.y) / cell).floor() as isize).clamp(0, rows as isize - 1) as usize;
bins[gy * cols + gx].push(i as u32);
}
Self { origin: min, cell, cols, rows, bins, len: points.len() }
}
/// How many points were indexed (including non-finite ones, which are stored
/// nowhere and can never be returned by a query).
#[must_use]
pub fn len(&self) -> usize {
self.len
}
/// Is the index empty?
#[must_use]
pub fn is_empty(&self) -> bool {
self.len == 0
}
/// `(cols, rows)` of the lattice.
#[must_use]
pub fn dims(&self) -> (usize, usize) {
(self.cols, self.rows)
}
/// The bin edge in px.
#[must_use]
pub fn cell(&self) -> f32 {
self.cell
}
/// The **fullest bin's** occupancy — the locality oracle. A lattice laid over the
/// wrong extent collapses the whole dataset into a handful of bins and this number
/// approaches `len`; a correctly-sized one keeps it near [`TARGET_PER_CELL`].
#[must_use]
pub fn max_occupancy(&self) -> usize {
self.bins.iter().map(Vec::len).max().unwrap_or(0)
}
fn cell_of(&self, p: Pos2) -> (isize, isize) {
(
((p.x - self.origin.x) / self.cell).floor() as isize,
((p.y - self.origin.y) / self.cell).floor() as isize,
)
}
/// Every indexed point whose bin overlaps `r`, appended to `out` in ascending
/// index order. `out` is **not** cleared (so a caller can accumulate); the return
/// value is how many were appended.
///
/// This is a bin-granular query: it can return points just outside `r` (same bin),
/// never miss one inside it. Callers that need exactness re-test the returned
/// points — which is cheap, because there are few.
pub fn query_rect(&self, r: Rect, out: &mut Vec<u32>) -> usize {
if self.cols == 0 || self.rows == 0 {
return 0;
}
let (x0, y0) = self.cell_of(r.min);
let (x1, y1) = self.cell_of(r.max);
let x0 = x0.clamp(0, self.cols as isize - 1) as usize;
let x1 = x1.clamp(0, self.cols as isize - 1) as usize;
let y0 = y0.clamp(0, self.rows as isize - 1) as usize;
let y1 = y1.clamp(0, self.rows as isize - 1) as usize;
// A rect entirely off one side of the lattice clamps to an edge band; reject it
// outright so an off-screen query costs nothing rather than sweeping the edge.
if r.max.x < self.origin.x
|| r.max.y < self.origin.y
|| r.min.x > self.origin.x + self.cols as f32 * self.cell
|| r.min.y > self.origin.y + self.rows as f32 * self.cell
{
return 0;
}
let before = out.len();
for gy in y0..=y1 {
for gx in x0..=x1 {
out.extend_from_slice(&self.bins[gy * self.cols + gx]);
}
}
out[before..].sort_unstable();
out.len() - before
}
/// The **nearest** indexed point to `probe` within `max_dist` px, or `None`.
///
/// Expanding-ring search from the probe's own bin outward: a ring is only visited
/// while it could still contain something closer than the best found so far, so the
/// cost tracks the local density and the search radius — **not** the dataset size.
/// That claim is checkable: [`NearestHit::candidates`] reports exactly how many
/// points were distance-tested.
///
/// Ties resolve to the lowest index, so the answer is deterministic.
#[must_use]
pub fn nearest(&self, points: &[Pos2], probe: Pos2, max_dist: f32) -> Option<NearestHit> {
if self.cols == 0 || self.rows == 0 || !probe.x.is_finite() || !probe.y.is_finite() {
return None;
}
let max_dist = if max_dist.is_finite() && max_dist > 0.0 { max_dist } else { return None };
let (cx, cy) = self.cell_of(probe);
let max_ring = ((max_dist / self.cell).ceil() as isize).max(0);
let mut best: Option<(u32, f32)> = None;
let mut candidates = 0usize;
for ring in 0..=max_ring {
// Nothing in ring r can be nearer than (r-1)·cell (the probe may sit at the
// far corner of its own bin). Once that floor exceeds the best hit, stop.
if let Some((_, d)) = best && (ring as f32 - 1.0) * self.cell > d {
break;
}
let visit = |gx: isize, gy: isize, best: &mut Option<(u32, f32)>, cand: &mut usize| {
if gx < 0 || gy < 0 || gx >= self.cols as isize || gy >= self.rows as isize {
return;
}
for &i in &self.bins[gy as usize * self.cols + gx as usize] {
let Some(p) = points.get(i as usize) else { continue };
*cand += 1;
let d = probe.distance(*p);
if d > max_dist {
continue;
}
match best {
Some((bi, bd)) if *bd < d || (*bd == d && *bi <= i) => {}
_ => *best = Some((i, d)),
}
}
};
if ring == 0 {
visit(cx, cy, &mut best, &mut candidates);
} else {
for gx in (cx - ring)..=(cx + ring) {
visit(gx, cy - ring, &mut best, &mut candidates);
visit(gx, cy + ring, &mut best, &mut candidates);
}
for gy in (cy - ring + 1)..=(cy + ring - 1) {
visit(cx - ring, gy, &mut best, &mut candidates);
visit(cx + ring, gy, &mut best, &mut candidates);
}
}
}
best.map(|(index, dist)| NearestHit { index, dist, candidates })
}
}
// ─────────────────────────────────────────────────────────────────────────────
// 2. Label collision — the half of the MapLibre lesson the pins were missing
// ─────────────────────────────────────────────────────────────────────────────
/// One label that *wants* to be drawn. The caller has already projected the anchor
/// and measured the text.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct LabelCandidate {
/// Where the label's box is centred if it gets its first choice, in screen px.
pub anchor: Pos2,
/// Measured text extent in px (`galley.size()`).
pub size: Vec2,
/// Higher wins a contested pixel. Degree, centrality, zoom-importance — the
/// caller's ranking. Ties break to the lower input index, so it is deterministic.
pub priority: f32,
/// Never suppressed: the selection, the hovered node, a search hit. Pinned labels
/// are placed before everything else and are placed even if they must overlap
/// another pinned label (the user asked for exactly these).
pub pinned: bool,
}
impl LabelCandidate {
/// A plain unpinned candidate.
#[must_use]
pub fn new(anchor: Pos2, size: Vec2, priority: f32) -> Self {
Self { anchor, size, priority, pinned: false }
}
/// Mark as never-suppressed (selection / hover / search hit).
#[must_use]
pub fn pinned(mut self, on: bool) -> Self {
self.pinned = on;
self
}
}
/// A label that won its pixels.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct PlacedLabel {
/// Index into the candidate slice.
pub index: usize,
/// The box it occupies, in screen px — **already** offset to whichever alternate
/// position was free. Paint the text centred in this rect.
pub rect: Rect,
/// Which position in the ladder was taken: `0` = the anchor itself, `1..` = an
/// alternate. A frame where everything is `0` had no contention.
pub slot: u8,
}
/// The outcome of one frame's label placement, with the work it did.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct LabelPlacement {
/// The labels to draw, in placement order (pinned first, then priority desc,
/// then input index) — deterministic.
pub placed: Vec<PlacedLabel>,
/// Candidates that lost every position in the ladder.
pub suppressed: usize,
/// Candidates that were even looked at — an off-viewport candidate is rejected
/// before any collision work, so this is the "cost tracks the screen" witness.
pub considered: usize,
/// Rect-vs-rect overlap tests performed. A quadratic placer reports `~n²/2`; the
/// grid-backed one reports a small multiple of `considered`.
pub collision_tests: usize,
}
impl LabelPlacement {
/// The fraction of considered labels that got drawn, `0.0..=1.0`.
#[must_use]
pub fn density(&self) -> f32 {
if self.considered == 0 { 0.0 } else { self.placed.len() as f32 / self.considered as f32 }
}
/// `state_json`-friendly summary (the observable a robot/matrix row asserts on).
#[must_use]
pub fn state_json(&self) -> serde_json::Value {
serde_json::json!({
"placed": self.placed.len(),
"suppressed": self.suppressed,
"considered": self.considered,
"collision_tests": self.collision_tests,
})
}
}
/// How aggressive the placer is.
#[derive(Clone, Copy, Debug)]
pub struct PlaceOpts {
/// Extra padding around each label box in px, so neighbours do not merely *touch*.
pub pad: f32,
/// Try alternate positions (below / above / right / left of the anchor) when the
/// first choice collides — Mapbox's "variable label placement". Off = one shot.
pub variable: bool,
/// Suppress labels whose box is not fully inside the viewport. Off = a label may
/// hang over the edge (still clipped by the painter).
pub clip_to_viewport: bool,
/// **Work budget** — stop considering candidates after this many on-screen ones.
/// `0` = unlimited.
///
/// A screen has a hard ceiling on how many labels can physically fit
/// (`viewport area / label area`); past a few multiples of it, every further
/// candidate is a guaranteed rejection that still pays for a collision query. At
/// 30 000 on-screen nodes that tail was measured at tens of milliseconds per frame
/// — a legibility cure that costs the frame rate is not a cure.
///
/// Because candidates are walked in **priority order**, truncating takes the tail,
/// never the labels the user cares about: the pinned ones and the highest-ranked
/// ones are already placed before the budget runs out. Truncated candidates are
/// neither placed nor counted as suppressed — they were never considered — so
/// `placed + suppressed == considered` still holds exactly.
pub max_considered: usize,
/// **Density ceiling** — stop PLACING after this many labels, however many more
/// would still physically fit. `0` = unlimited (only collision decides).
///
/// Collision alone answers "do these two share pixels?", and the honest answer on a
/// dense map is that a great many labels do not — so the placer packs them shoulder
/// to shoulder and the result is a legible *text field* with a map somewhere behind
/// it. MEASURED on korp-ui over Stockholm at zoom 12.7 (1258×728 canvas): **255**
/// non-overlapping street names — one per 3 591 px² — and the picture was still
/// unreadable. Every pair passed the collision test. (That pane published no ink
/// figure; the box coverage that goes with those 255 is a lower bound of ~32 %, and
/// the honest end-to-end measurement is in
/// `facett_map::layer::LABEL_MIN_PX2_EACH`.)
///
/// So the second law is areal, and it is the caller's to set from its own pane:
/// `max_placed = viewport.area() / min_px²_per_label`. Cartographic practice puts
/// that divisor in the low tens of thousands of px²; see
/// `facett_map::layer::LABEL_MIN_PX2_EACH` for the shipped derivation.
///
/// **Pinned labels are exempt** — they are the answer to the user's click, and a
/// budget must not eat the one label that was asked for.
///
/// Candidates dropped by the budget WERE considered (they were walked, ranked and
/// looked at), so they count as [`suppressed`](LabelPlacement::suppressed) and
/// `placed + suppressed == considered` still holds exactly. Because the walk is in
/// priority order, the budget takes the tail — never the place names.
pub max_placed: usize,
}
impl Default for PlaceOpts {
fn default() -> Self {
Self { pad: 2.0, variable: true, clip_to_viewport: false, max_considered: 0, max_placed: 0 }
}
}
/// **Greedy screen-space label collision.** Walks the candidates in priority order and
/// gives each the first box in its ladder that no already-placed label occupies.
///
/// This is the same discipline `facett-geomap`'s pin clustering applies to *markers*,
/// applied to *text*: the threshold is "these would visually collide", which is a
/// screen distance, so it works at every zoom and latitude without a second tuning.
/// The difference is what happens on a collision — a pile of markers **merges** into a
/// count badge (no information is lost, it is summarised), while a pile of labels can
/// only **drop** the losers, because overlapping text is strictly less readable than
/// one label. Hence the priority: the caller decides who is worth reading.
///
/// Cost: one [`ScreenGrid`] over the anchors plus a bin-local overlap test per
/// candidate — `O(considered)` with a small constant, not `O(n²)`.
#[must_use]
pub fn place_labels(cands: &[LabelCandidate], viewport: Rect, opts: PlaceOpts) -> LabelPlacement {
let mut out = LabelPlacement::default();
if cands.is_empty() {
return out;
}
// Order: pinned first, then priority descending, then input index. The final key is
// the index, so the order is total and no HashMap/float tie can perturb it.
let mut order: Vec<usize> = (0..cands.len()).collect();
order.sort_by(|&a, &b| {
let (ca, cb) = (&cands[a], &cands[b]);
cb.pinned
.cmp(&ca.pinned)
.then(cb.priority.total_cmp(&ca.priority))
.then(a.cmp(&b))
});
// The occupancy lattice: bins sized to the widest label so a box spans at most a
// 2×2 neighbourhood and the overlap test stays local.
let max_w = cands.iter().map(|c| c.size.x + 2.0 * opts.pad).fold(1.0f32, f32::max);
let max_h = cands.iter().map(|c| c.size.y + 2.0 * opts.pad).fold(1.0f32, f32::max);
let cell = max_w.max(max_h).max(1.0);
let cols = ((viewport.width() / cell).ceil() as usize + 2).max(1);
let rows = ((viewport.height() / cell).ceil() as usize + 2).max(1);
let mut bins: Vec<Vec<u32>> = vec![Vec::new(); cols * rows];
let mut placed_rects: Vec<Rect> = Vec::with_capacity(cands.len());
// The lattice covers the viewport, but a label box may hang OFF it (its anchor is
// allowed within half a box of the edge, and variable placement pushes further).
// Bin indices are therefore CLAMPED into range, never skipped: a rect that pokes
// outside is registered in the edge bin instead of nowhere. Skipping was a real
// bug — two labels overlapping only in the region beyond the lattice consulted no
// shared bin, collided, and both drew. The pixel oracle caught it at peak 2.
let bin_of = |p: Pos2| -> (usize, usize) {
let gx = ((p.x - viewport.min.x) / cell).floor();
let gy = ((p.y - viewport.min.y) / cell).floor();
(
(gx.max(0.0) as usize).min(cols - 1),
(gy.max(0.0) as usize).min(rows - 1),
)
};
for &i in &order {
if opts.max_considered > 0 && out.considered >= opts.max_considered {
break;
}
let c = &cands[i];
if !c.anchor.x.is_finite() || !c.anchor.y.is_finite() {
out.suppressed += 1;
continue;
}
let half = (c.size + Vec2::splat(2.0 * opts.pad)) * 0.5;
// Off-viewport candidates cost nothing: rejected before any collision work.
if !viewport.expand2(half).contains(c.anchor) {
continue;
}
out.considered += 1;
// ── THE DENSITY CEILING ──────────────────────────────────────────────
// Asked AFTER `considered` is incremented and BEFORE any collision work, so
// the budget costs nothing per rejected candidate and the accounting still
// closes (`placed + suppressed == considered`). A pinned label is exempt.
if !c.pinned && opts.max_placed > 0 && out.placed.len() >= opts.max_placed {
out.suppressed += 1;
continue;
}
// The ladder: the anchor, then four displaced alternates (Mapbox variable
// placement). A pinned label takes its anchor unconditionally.
let ladder: &[Vec2] = if opts.variable {
&[
Vec2::ZERO,
Vec2::new(0.0, 1.0),
Vec2::new(0.0, -1.0),
Vec2::new(1.0, 0.0),
Vec2::new(-1.0, 0.0),
]
} else {
&[Vec2::ZERO]
};
let mut chosen: Option<(Rect, u8)> = None;
for (slot, dir) in ladder.iter().enumerate() {
let centre = c.anchor + Vec2::new(dir.x * (half.x * 2.0 + 1.0), dir.y * (half.y * 2.0 + 1.0));
let r = Rect::from_center_size(centre, half * 2.0);
if opts.clip_to_viewport && !viewport.contains_rect(r) {
continue;
}
if c.pinned && slot == 0 {
chosen = Some((r, 0));
break;
}
// Bin-local overlap test — only the ≤ 3×3 neighbourhood is consulted.
let (bx0, by0) = bin_of(r.min);
let (bx1, by1) = bin_of(r.max);
let mut collides = false;
'scan: for gy in by0..=by1 {
for gx in bx0..=bx1 {
for &pi in &bins[gy * cols + gx] {
out.collision_tests += 1;
if placed_rects[pi as usize].intersects(r) {
collides = true;
break 'scan;
}
}
}
}
if !collides {
chosen = Some((r, slot as u8));
break;
}
}
match chosen {
Some((rect, slot)) => {
let pi = placed_rects.len() as u32;
placed_rects.push(rect);
let (bx0, by0) = bin_of(rect.min);
let (bx1, by1) = bin_of(rect.max);
for gy in by0..=by1 {
for gx in bx0..=bx1 {
bins[gy * cols + gx].push(pi);
}
}
out.placed.push(PlacedLabel { index: i, rect, slot });
}
None => out.suppressed += 1,
}
}
out
}
/// The **pixel oracle** for a label placement: the highest number of label boxes
/// covering any single pixel of `viewport`, computed by actually rasterizing the boxes
/// into a coverage buffer at `scale` px per sample.
///
/// `1` means no two labels share a pixel — the thing "collision avoidance" claims. An
/// unthinned frame of the same data reports the true pile depth, so the assertion has
/// somewhere to go red from. Independent of the placer's own bookkeeping on purpose:
/// it reads the *result*, not the algorithm.
#[must_use]
pub fn max_label_overlap(rects: &[Rect], viewport: Rect, scale: f32) -> u32 {
let scale = if scale.is_finite() && scale > 0.0 { scale } else { 1.0 };
let w = ((viewport.width() / scale).ceil() as usize).clamp(1, 4096);
let h = ((viewport.height() / scale).ceil() as usize).clamp(1, 4096);
let mut cover = vec![0u32; w * h];
let mut peak = 0u32;
// Nearest-pixel-centre coverage (`round`, not floor/ceil). A rasterizer lights the
// pixels whose centres the box covers, so two boxes with a real gap between them
// land on disjoint pixels. floor/ceil would inflate every box by up to a pixel on
// each side and report a phantom overlap for merely *adjacent* labels — an oracle
// that fires on correct output is worse than no oracle.
for r in rects {
let x0 = (((r.min.x - viewport.min.x) / scale).round() as isize).clamp(0, w as isize) as usize;
let x1 = (((r.max.x - viewport.min.x) / scale).round() as isize).clamp(0, w as isize) as usize;
let y0 = (((r.min.y - viewport.min.y) / scale).round() as isize).clamp(0, h as isize) as usize;
let y1 = (((r.max.y - viewport.min.y) / scale).round() as isize).clamp(0, h as isize) as usize;
for y in y0..y1 {
for x in x0..x1 {
let c = &mut cover[y * w + x];
*c += 1;
peak = peak.max(*c);
}
}
}
peak
}
// ─────────────────────────────────────────────────────────────────────────────
// 3. Density-aware edge thinning — the hairball cure
// ─────────────────────────────────────────────────────────────────────────────
/// How many direction buckets an edge's angle is quantized into. Edges are thinned
/// *within* a direction bucket, so a bundle of near-parallel filaments collapses while
/// an edge crossing them at a different angle survives — the structure that makes a
/// hairball readable is exactly the structure that differs in direction.
const DIR_BUCKETS: usize = 4;
/// Thinning knobs.
#[derive(Clone, Copy, Debug)]
pub struct EdgeThinOpts {
/// Lattice bin edge in px. Density is measured, and the keep-quota applied, per
/// `(bin, direction)` bucket.
pub cell: f32,
/// How many edges survive per `(bin, direction)` bucket. `0` keeps none (other
/// than the always-keeps); a large value keeps everything.
pub keep_per_bucket: usize,
}
impl Default for EdgeThinOpts {
fn default() -> Self {
Self { cell: 24.0, keep_per_bucket: 3 }
}
}
/// The outcome of one frame's edge thinning, with the density it actually achieved.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct EdgeThinResult {
/// Indices of the edges to draw, ascending — so the paint order (and therefore the
/// over-draw) is identical to the unthinned pass minus the dropped ones.
pub keep: Vec<u32>,
/// How many were dropped.
pub dropped: usize,
/// Edges considered (on-viewport). Off-screen edges are rejected first, so the
/// cost tracks the screen.
pub considered: usize,
/// Peak segments-per-bin **before** thinning — how black the worst pixel was.
pub peak_density_before: usize,
/// Peak segments-per-bin **after**. The measurable claim: this is bounded by
/// `keep_per_bucket · DIR_BUCKETS` plus the always-keeps.
pub peak_density: usize,
}
impl EdgeThinResult {
/// `state_json`-friendly summary.
#[must_use]
pub fn state_json(&self) -> serde_json::Value {
serde_json::json!({
"kept": self.keep.len(),
"dropped": self.dropped,
"considered": self.considered,
"peak_density_before": self.peak_density_before,
"peak_density": self.peak_density,
})
}
}
/// A **monotonic `u32` key** for an `f32`: `a <= b` iff `key(a) <= key(b)` for every
/// finite value (and NaN sorts last). Lets a hot sort use plain integer ordering
/// instead of a float comparator, which is both faster and immune to the
/// already-sorted-input trap that made the edge bench read 9x cheaper than reality.
#[inline]
fn monotonic_key(v: f32) -> u32 {
let b = v.to_bits();
if b & 0x8000_0000 != 0 { !b } else { b ^ 0x8000_0000 }
}
/// Walk the lattice bins a segment crosses (clamped to the `cols × rows` viewport
/// lattice), calling `f` with each row-major bin index. A cheap DDA at cell
/// resolution — the ink a segment deposits, not just where its midpoint fell.
fn walk_bins(
a: Pos2,
b: Pos2,
origin: Pos2,
cell: f32,
cols: usize,
rows: usize,
mut f: impl FnMut(usize),
) {
let inv = 1.0 / cell;
let (ax, ay) = ((a.x - origin.x) * inv, (a.y - origin.y) * inv);
let (bx, by) = ((b.x - origin.x) * inv, (b.y - origin.y) * inv);
let steps = ((bx - ax).abs().max((by - ay).abs()).ceil() as usize).clamp(1, 8192);
// INCREMENTAL stepping: one add per axis per step. The obvious `t = s/steps` +
// lerp form costs a divide and two multiply-adds per step, and this walk is the
// whole cost of `thin_edges` (it is proportional to the ink, not the edge count) —
// 120 000 viewport-spanning segments cross ~55 cells each, i.e. ~6600000 steps per
// frame, so the per-step constant is the number that matters.
let inv_steps = 1.0 / steps as f32;
let (dx, dy) = ((bx - ax) * inv_steps, (by - ay) * inv_steps);
let (mut x, mut y) = (ax, ay);
let (fcols, frows) = (cols as f32, rows as f32);
let mut last = usize::MAX;
for _ in 0..=steps {
if x >= 0.0 && y >= 0.0 && x < fcols && y < frows {
let idx = y as usize * cols + x as usize;
if idx != last {
f(idx);
last = idx;
}
}
x += dx;
y += dy;
}
}
/// **Density-aware edge thinning — an ink budget per screen cell.**
///
/// Every on-screen segment is walked across the viewport lattice at `cell` resolution
/// and its ink is charged to each bin it crosses, per quantized direction. An edge is
/// drawn only if **every** bin along its path still has room in its
/// `keep_per_bucket` quota for that direction; otherwise it is dropped. Edges flagged
/// in `always` (the selected path, a highlighted cycle, the hovered node's incident
/// edges) are drawn unconditionally, and are charged to the budget so they crowd out
/// bulk edges rather than adding on top of them.
///
/// Two design choices worth stating, because the obvious alternatives are worse:
///
/// - **Charge the whole path, not the midpoint.** Binning an edge by its midpoint is
/// cheap and wrong: a long edge crossing the pane deposits ink over hundreds of
/// cells while being quota-charged to one. A hairball of long edges would then pass
/// every counter while rendering exactly as black as before — and the pixel oracle
/// ([`edge_ink_profile`]) is what catches that, which is why this function is
/// written to satisfy the *pixels* and not the bookkeeping.
/// - **Quota per direction.** A pile of near-parallel filaments is redundant; an edge
/// crossing them at another angle is the structure you are trying to see. Quantizing
/// into [`DIR_BUCKETS`] means a saturated bin still admits a transversal edge.
///
/// And why not "just draw fewer edges at random": a uniform 1-in-k sample thins the
/// sparse regions exactly as hard as the dense ones, destroying the readable parts of
/// the graph to fix the unreadable parts. An ink budget leaves a sparse region
/// completely untouched — a bin under quota keeps everything — and only bites where the
/// pane was already saturated.
///
/// `weight` ranks who gets the budget first (edge weight, betweenness, whatever the
/// caller has); pass an empty slice for "all equal", in which case the lower index
/// wins. Fully deterministic: one global sort ending in the edge index, and a dense
/// lattice rather than a `HashMap`, so nothing depends on hash order.
#[must_use]
pub fn thin_edges(
segments: &[(Pos2, Pos2)],
weight: &[f32],
always: &[bool],
viewport: Rect,
opts: EdgeThinOpts,
) -> EdgeThinResult {
let mut out = EdgeThinResult::default();
if segments.is_empty() {
return out;
}
let cell = if opts.cell.is_finite() && opts.cell > 0.0 { opts.cell } else { 24.0 };
let cols = ((viewport.width() / cell).ceil() as usize + 1).clamp(1, 8192);
let rows = ((viewport.height() / cell).ceil() as usize + 1).clamp(1, 8192);
let origin = viewport.min;
let finite = |p: Pos2| p.x.is_finite() && p.y.is_finite();
let dir_of = |a: Pos2, b: Pos2| -> usize {
let folded = (b.y - a.y).atan2(b.x - a.x).rem_euclid(std::f32::consts::PI);
(((folded / std::f32::consts::PI) * DIR_BUCKETS as f32).floor() as usize).min(DIR_BUCKETS - 1)
};
// Which edges are even on screen — the cost-tracks-the-screen gate.
let mut on_screen: Vec<u32> = Vec::with_capacity(segments.len());
for (i, &(a, b)) in segments.iter().enumerate() {
if finite(a) && finite(b) && viewport.intersects(Rect::from_two_pos(a, b)) {
on_screen.push(i as u32);
}
}
out.considered = on_screen.len();
if out.considered == 0 {
return out;
}
let w = |i: u32| weight.get(i as usize).copied().unwrap_or(0.0);
let keep_always = |i: u32| always.get(i as usize).copied().unwrap_or(false);
// Budget order: the always-keeps first (they are non-negotiable and must charge
// the budget before anyone else spends it), then heaviest-first, ties to the lower
// index — a total order, so the survivors are a pure function of the input.
//
// The keys are MATERIALIZED into an integer triple and sorted with `sort_unstable`
// rather than compared through closures. The comparator version measured 47 ms for
// 120 000 edges against 5 ms for 100 000 — a 9x gap that was not the data. The
// 100 000 arm had an EMPTY weight slice, so every key compared equal, the input was
// already index-ordered, and the merge sort detected one long run and ran in O(n).
// In other words the cheap-looking arm was measuring a best case that no real caller
// ever hits, and the honest cost was hiding behind four bounds-checked slice reads
// per comparison. `sort_unstable` on a plain `(u8, u32, u32)` has no such trap, and
// the index in the last position keeps the order total (so `sort_unstable`'s lack of
// stability cannot change the result).
let mut order: Vec<(u8, u32, u32)> = on_screen
.iter()
.map(|&i| (u8::from(!keep_always(i)), !monotonic_key(w(i)), i))
.collect();
order.sort_unstable();
let order: Vec<u32> = order.into_iter().map(|(_, _, i)| i).collect();
// ONE DDA walk per segment. The obvious implementation walks three times — once to
// measure the before-density, once to spend the budget, once to measure the
// after-density — and the walk IS the cost of this function (it is proportional to
// the ink, not to the edge count). All three are folded into the single pass below:
// `before` is charged unconditionally, `occ`/`after` only when the edge survives.
let quota = opts.keep_per_bucket as u32;
let mut occ = vec![0u32; cols * rows * DIR_BUCKETS];
let mut before = vec![0u32; cols * rows];
let mut after = vec![0u32; cols * rows];
let (mut peak_before, mut peak_after) = (0u32, 0u32);
let mut keep: Vec<u32> = Vec::with_capacity(order.len());
let mut path: Vec<usize> = Vec::new();
for &i in &order {
let (a, b) = segments[i as usize];
let d = dir_of(a, b);
path.clear();
walk_bins(a, b, origin, cell, cols, rows, |idx| path.push(idx));
for &idx in &path {
before[idx] += 1;
peak_before = peak_before.max(before[idx]);
}
let forced = keep_always(i);
let fits = forced || (quota > 0 && path.iter().all(|&idx| occ[idx * DIR_BUCKETS + d] < quota));
if !fits {
continue;
}
for &idx in &path {
occ[idx * DIR_BUCKETS + d] += 1;
after[idx] += 1;
peak_after = peak_after.max(after[idx]);
}
keep.push(i);
}
keep.sort_unstable();
out.dropped = out.considered - keep.len();
out.peak_density_before = peak_before as usize;
out.peak_density = peak_after as usize;
out.keep = keep;
out
}
/// The **pixel oracle** for edge legibility: rasterize the segments into a `w × h`
/// coverage buffer over `viewport` and return `(lit_px, peak_hits, saturated_px)` —
/// how much of the pane has ink, the deepest pile on one pixel, and how many pixels are
/// covered `>= saturate` times (i.e. are pure hairball, carrying no structure).
///
/// A readable frame has a small `saturated_px`; a hairball's is most of the pane. This
/// reads the *rendered result*, so it is red when the thinning silently stops working
/// even if every counter in [`EdgeThinResult`] still looks plausible.
#[must_use]
pub fn edge_ink_profile(
segments: &[(Pos2, Pos2)],
keep: &[u32],
viewport: Rect,
saturate: u32,
) -> (usize, u32, usize) {
let w = (viewport.width().ceil() as usize).clamp(1, 2048);
let h = (viewport.height().ceil() as usize).clamp(1, 2048);
let mut cover = vec![0u32; w * h];
let mut peak = 0u32;
let mut plot = |x: isize, y: isize, peak: &mut u32| {
if x < 0 || y < 0 || x >= w as isize || y >= h as isize {
return;
}
let c = &mut cover[y as usize * w + x as usize];
*c += 1;
*peak = (*peak).max(*c);
};
for &i in keep {
let Some(&(a, b)) = segments.get(i as usize) else { continue };
let (ax, ay) = (a.x - viewport.min.x, a.y - viewport.min.y);
let (bx, by) = (b.x - viewport.min.x, b.y - viewport.min.y);
if !(ax.is_finite() && ay.is_finite() && bx.is_finite() && by.is_finite()) {
continue;
}
let steps = ((bx - ax).abs().max((by - ay).abs()).ceil() as usize).clamp(1, 4096);
for s in 0..=steps {
let t = s as f32 / steps as f32;
plot((ax + (bx - ax) * t) as isize, (ay + (by - ay) * t) as isize, &mut peak);
}
}
let lit = cover.iter().filter(|&&c| c > 0).count();
let sat = cover.iter().filter(|&&c| c >= saturate).count();
(lit, peak, sat)
}
// ─────────────────────────────────────────────────────────────────────────────
// 4. The per-frame PLAN — the one place a graph pane asks "what do I draw?"
// ─────────────────────────────────────────────────────────────────────────────
/// Everything a pane knows about the frame it is about to paint, already projected to
/// screen px. Index-aligned slices rather than a trait, so a pane with a completely
/// different node type (egui `Color32` chips, `vello` colours, map pins) fills them in
/// without adopting anyone else's model.
///
/// A short slice is treated as "all default": pass `&[]` for `label_priority` and every
/// label ranks equal, `&[]` for `edge_always` and no edge is protected.
pub struct FrameInput<'a> {
/// Node centres in screen px.
pub centres: &'a [Pos2],
/// Measured label box per node, in px. An entry of `Vec2::ZERO` (or a short slice)
/// means "this node has no label" and it is not offered to the placer.
pub label_size: &'a [Vec2],
/// Ranking for contested pixels. Higher wins.
pub label_priority: &'a [f32],
/// Labels that must never be dropped (selection / hover / search hit).
pub label_pinned: &'a [bool],
/// Edges as `(from, to)` node indices.
pub edges: &'a [(u32, u32)],
/// Edges that must never be thinned (the lit trace, a highlighted cycle).
pub edge_always: &'a [bool],
/// Ranking inside a saturated cell. Higher survives.
pub edge_weight: &'a [f32],
/// The pane rect in screen px. Everything outside it is rejected before any work,
/// which is what makes the frame cost track the screen and not the dataset.
pub viewport: Rect,
}
/// Which legibility cures to apply this frame. All-off is the historical painter.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct FrameOpts {
pub thin_labels: bool,
pub thin_edges: bool,
pub label_pad: f32,
pub edge_cell: f32,
pub keep_per_bucket: usize,
}
impl Default for FrameOpts {
fn default() -> Self {
Self { thin_labels: false, thin_edges: false, label_pad: 2.0, edge_cell: 24.0, keep_per_bucket: 3 }
}
}
impl FrameOpts {
/// Both cures on, default tuning.
#[must_use]
pub fn legible() -> Self {
Self { thin_labels: true, thin_edges: true, ..Self::default() }
}
/// Nothing enabled?
#[must_use]
pub fn is_off(&self) -> bool {
!self.thin_labels && !self.thin_edges
}
}
/// The plan: exactly which edges to stroke and exactly where each surviving label goes.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct FramePlan {
/// Edge indices to draw, ascending. `None` = thinning off, draw them all.
pub edges: Option<Vec<u32>>,
/// Label placements. `None` = thinning off, paint them all as before.
pub labels: Option<LabelPlacement>,
pub report: FrameReport,
}
/// The observable summary of one frame's legibility work — what a `state_json` /
/// testmatrix row asserts on.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct FrameReport {
pub labels_placed: usize,
pub labels_suppressed: usize,
pub labels_considered: usize,
pub edges_drawn: usize,
pub edges_thinned: usize,
pub edges_considered: usize,
pub edge_peak_before: usize,
pub edge_peak_after: usize,
}
impl FrameReport {
/// `state_json` fragment.
#[must_use]
pub fn state_json(&self) -> serde_json::Value {
serde_json::json!({
"labels_placed": self.labels_placed,
"labels_suppressed": self.labels_suppressed,
"labels_considered": self.labels_considered,
"edges_drawn": self.edges_drawn,
"edges_thinned": self.edges_thinned,
"edges_considered": self.edges_considered,
"edge_peak_before": self.edge_peak_before,
"edge_peak_after": self.edge_peak_after,
})
}
}
/// **Plan one frame.** The single entry point every graph/map pane calls to decide what
/// is legible enough to draw. Pure: no `Ui`, no painter, no GPU — so the whole decision
/// is unit-testable and benchable without a window, and two panes cannot drift into
/// two different definitions of "readable".
#[must_use]
pub fn plan_frame(input: &FrameInput<'_>, opts: FrameOpts) -> FramePlan {
let mut plan = FramePlan::default();
if opts.thin_edges {
let segs: Vec<(Pos2, Pos2)> = input
.edges
.iter()
.map(|&(a, b)| {
match (input.centres.get(a as usize), input.centres.get(b as usize)) {
(Some(&pa), Some(&pb)) => (pa, pb),
// A dangling endpoint draws nothing anyway; park it off-screen so
// index alignment with the caller's edge list survives.
_ => (Pos2::new(f32::NAN, f32::NAN), Pos2::new(f32::NAN, f32::NAN)),
}
})
.collect();
let res = thin_edges(
&segs,
input.edge_weight,
input.edge_always,
input.viewport,
EdgeThinOpts { cell: opts.edge_cell, keep_per_bucket: opts.keep_per_bucket },
);
plan.report.edges_drawn = res.keep.len();
plan.report.edges_thinned = res.dropped;
plan.report.edges_considered = res.considered;
plan.report.edge_peak_before = res.peak_density_before;
plan.report.edge_peak_after = res.peak_density;
plan.edges = Some(res.keep);
} else {
plan.report.edges_drawn = input.edges.len();
plan.report.edges_considered = input.edges.len();
}
if opts.thin_labels {
let cands: Vec<LabelCandidate> = input
.centres
.iter()
.enumerate()
.map(|(i, &c)| {
let size = input.label_size.get(i).copied().unwrap_or(Vec2::ZERO);
LabelCandidate {
// A zero-size label is parked far off-viewport (FINITE, so it reads
// as "not on screen" rather than as a malformed candidate): it is
// never considered and never counted as suppressed.
anchor: if size.x > 0.0 && size.y > 0.0 {
c
} else {
Pos2::new(f32::MAX * 0.5, f32::MAX * 0.5)
},
size,
priority: input.label_priority.get(i).copied().unwrap_or(0.0),
pinned: input.label_pinned.get(i).copied().unwrap_or(false),
}
})
.collect();
// Budget the placement at 8x what the viewport could physically hold. Past
// that every candidate is a certain rejection, and candidates are in priority
// order, so the tail that gets dropped is the tail nobody would have read.
let (mut lw, mut lh) = (f32::MAX, f32::MAX);
for sz in input.label_size.iter().filter(|s| s.x > 0.0 && s.y > 0.0) {
lw = lw.min(sz.x);
lh = lh.min(sz.y);
}
let capacity = if lw.is_finite() && lh.is_finite() && lw > 0.0 && lh > 0.0 {
((input.viewport.width() / lw) * (input.viewport.height() / lh)).ceil() as usize
} else {
0
};
let p = place_labels(
&cands,
input.viewport,
PlaceOpts {
pad: opts.label_pad,
variable: true,
clip_to_viewport: false,
max_considered: capacity.saturating_mul(8).max(2048),
// The graph frame planner has its own capacity model (`capacity`
// above); the areal budget is the MAP's answer to the same question
// and is set by that caller, so it stays off here.
max_placed: 0,
},
);
plan.report.labels_placed = p.placed.len();
plan.report.labels_suppressed = p.suppressed;
plan.report.labels_considered = p.considered;
plan.labels = Some(p);
}
plan
}
#[cfg(test)]
mod tests {
use super::*;
use egui::{pos2, vec2};
fn lattice(n: usize, span: f32) -> Vec<Pos2> {
let side = (n as f32).sqrt().ceil() as usize;
(0..n)
.map(|i| {
let (r, c) = (i / side, i % side);
pos2(c as f32 / side as f32 * span, r as f32 / side as f32 * span)
})
.collect()
}
// ── ScreenGrid ───────────────────────────────────────────────────────────
#[test]
fn empty_and_degenerate_inputs_are_lossless_not_panics() {
let g = ScreenGrid::build(&[]);
assert!(g.is_empty());
assert_eq!(g.nearest(&[], pos2(0.0, 0.0), 10.0), None);
// Every point identical → one finite bin, and the probe still resolves.
let pts = vec![pos2(5.0, 5.0); 100];
let g = ScreenGrid::build(&pts);
let hit = g.nearest(&pts, pos2(5.0, 5.0), 1.0).expect("degenerate extent still answers");
assert_eq!(hit.index, 0, "ties resolve to the lowest index");
// Non-finite points are indexed nowhere and can never be returned.
let pts = vec![pos2(f32::NAN, 0.0), pos2(3.0, 3.0)];
let g = ScreenGrid::build(&pts);
assert_eq!(g.nearest(&pts, pos2(3.0, 3.0), 1.0).map(|h| h.index), Some(1));
}
/// The nearest-point answer must be the SAME as a brute-force linear scan, at
/// every size and probe. If it were not, the index would be a fast wrong answer.
#[test]
fn nearest_agrees_with_brute_force_everywhere() {
for n in [1usize, 7, 500, 5000] {
let pts = lattice(n, 900.0);
let g = ScreenGrid::build(&pts);
for k in 0..40 {
let probe = pos2((k * 37 % 900) as f32 + 0.5, (k * 53 % 900) as f32 + 0.5);
let max_d = 200.0;
let brute = pts
.iter()
.enumerate()
.map(|(i, p)| (i as u32, probe.distance(*p)))
.filter(|&(_, d)| d <= max_d)
.min_by(|a, b| a.1.total_cmp(&b.1).then(a.0.cmp(&b.0)));
let got = g.nearest(&pts, probe, max_d);
match (brute, got) {
(None, None) => {}
(Some((bi, bd)), Some(h)) => {
assert!(
(h.dist - bd).abs() < 1e-4,
"n={n} probe={probe:?}: grid {} vs brute {bd}",
h.dist
);
assert_eq!(h.index, bi, "n={n}: same winner as the linear scan");
}
(b, g2) => panic!("n={n} probe={probe:?}: brute={b:?} grid={g2:?}"),
}
}
}
}
/// **THE claim, as data.** A hover probe must cost what is under the cursor, not
/// what is in the dataset. `candidates` is the points actually distance-tested;
/// a linear scan reports `n`. This is the assertion `facett-geomap`'s `PointGrid`
/// did not have, which is why its lattice could span the world for months.
#[test]
fn hover_cost_tracks_the_neighbourhood_not_the_dataset() {
let mut seen: Vec<(usize, usize)> = Vec::new();
for n in [1000usize, 10_000, 100_000, 1_000_000] {
let pts = lattice(n, 4000.0);
let g = ScreenGrid::build(&pts);
let hit = g.nearest(&pts, pos2(2000.0, 2000.0), 12.0).expect("a hit near the middle");
// ABSOLUTE bound: one hover probe touches a neighbourhood, full stop.
assert!(
hit.candidates <= 128,
"n={n}: examined {} points for one hover probe",
hit.candidates
);
// The lattice spans the DATA, so occupancy stays near the target however
// large or small the extent is — the bug `PointGrid` had.
assert!(
g.max_occupancy() <= 64,
"n={n}: fullest bin holds {} (lattice mis-sized over the extent)",
g.max_occupancy()
);
seen.push((n, hit.candidates));
}
// THE claim: the cost does not follow the dataset. n grows 1000×; a linear
// scan's candidate count would grow 1000× with it.
let (n0, c0) = seen[0];
let (n1, c1) = *seen.last().unwrap();
assert!(
c1 <= c0 * 2,
"dataset {n0} -> {n1} (×{}) but probe cost {c0} -> {c1}",
n1 / n0
);
}
#[test]
fn query_rect_is_a_superset_of_the_true_contents_and_sorted() {
let pts = lattice(2000, 800.0);
let g = ScreenGrid::build(&pts);
let r = Rect::from_min_max(pos2(100.0, 100.0), pos2(180.0, 180.0));
let mut out = Vec::new();
g.query_rect(r, &mut out);
assert!(out.windows(2).all(|w| w[0] <= w[1]), "ascending index order");
for (i, p) in pts.iter().enumerate() {
if r.contains(*p) {
assert!(out.contains(&(i as u32)), "point {i} inside the rect must be returned");
}
}
assert!(out.len() < pts.len() / 4, "a small rect returns a small slice, got {}", out.len());
// A rect entirely off the lattice costs nothing.
let mut off = Vec::new();
assert_eq!(g.query_rect(Rect::from_min_max(pos2(-9e3, -9e3), pos2(-8e3, -8e3)), &mut off), 0);
}
// ── labels ───────────────────────────────────────────────────────────────
fn viewport() -> Rect {
Rect::from_min_size(pos2(0.0, 0.0), vec2(800.0, 600.0))
}
/// **THE pixel oracle.** Rasterize the placed boxes: no pixel may be covered
/// twice. The same candidates placed *without* collision avoidance pile up — so
/// the assertion has a demonstrated failure mode, in-test, rather than a promise.
#[test]
fn placed_labels_never_share_a_pixel_and_the_unthinned_control_does() {
// 400 labels crammed into a 200×150 patch — a guaranteed pile.
let cands: Vec<LabelCandidate> = (0..400)
.map(|i| {
let x = 100.0 + ((i * 17) % 200) as f32;
let y = 100.0 + ((i * 29) % 150) as f32;
LabelCandidate::new(pos2(x, y), vec2(46.0, 12.0), (400 - i) as f32)
})
.collect();
let out = place_labels(&cands, viewport(), PlaceOpts::default());
let placed: Vec<Rect> = out.placed.iter().map(|p| p.rect).collect();
assert_eq!(
max_label_overlap(&placed, viewport(), 1.0),
1,
"collision avoidance: no pixel carries two labels"
);
assert!(out.suppressed > 0, "a real pile must actually suppress losers");
assert!(!out.placed.is_empty(), "and must still draw the winners");
// NEGATIVE CONTROL — the pre-fix behaviour: paint every candidate at its
// anchor. The identical oracle reports a deep pile, so a placer that silently
// degraded to "place everything" cannot pass the assertion above.
let unthinned: Vec<Rect> = cands
.iter()
.map(|c| Rect::from_center_size(c.anchor, c.size))
.collect();
let control = max_label_overlap(&unthinned, viewport(), 1.0);
assert!(control >= 5, "the control must overplot badly, got peak {control}");
}
/// Priority is honoured: with a hard collision, the higher-priority label wins the
/// pixels. A placer that ignored priority would drop the important label.
#[test]
fn higher_priority_wins_a_contested_pixel() {
let cands = vec![
LabelCandidate::new(pos2(400.0, 300.0), vec2(60.0, 14.0), 1.0),
LabelCandidate::new(pos2(402.0, 301.0), vec2(60.0, 14.0), 9.0),
];
let opts = PlaceOpts { variable: false, ..PlaceOpts::default() };
let out = place_labels(&cands, viewport(), opts);
assert_eq!(out.placed.len(), 1);
assert_eq!(out.placed[0].index, 1, "the priority-9 label is the one drawn");
assert_eq!(out.suppressed, 1);
}
/// A pinned label (selection / hover / search hit) is NEVER suppressed, even when
/// it collides — it outranks priority entirely, and two pinned labels both draw
/// rather than one silently vanishing.
#[test]
fn pinned_labels_are_never_suppressed() {
let opts = PlaceOpts { variable: false, ..PlaceOpts::default() };
// A pinned label beats a much higher-priority ordinary one at the same pixels.
let cands = vec![
LabelCandidate::new(pos2(400.0, 300.0), vec2(60.0, 14.0), 100.0),
LabelCandidate::new(pos2(401.0, 300.0), vec2(60.0, 14.0), 0.0).pinned(true),
];
let out = place_labels(&cands, viewport(), opts);
assert_eq!(out.placed.len(), 1);
assert_eq!(out.placed[0].index, 1, "the pinned label is the one drawn");
assert_eq!(out.suppressed, 1, "the ordinary label lost, as it must");
// Two pinned labels on the same pixels: BOTH draw. The user asked for exactly
// these two, so suppressing either is the wrong answer.
let both = vec![
LabelCandidate::new(pos2(400.0, 300.0), vec2(60.0, 14.0), 0.0).pinned(true),
LabelCandidate::new(pos2(401.0, 300.0), vec2(60.0, 14.0), 0.0).pinned(true),
];
let out = place_labels(&both, viewport(), opts);
assert_eq!(out.placed.len(), 2, "pinned labels are never dropped");
assert_eq!(out.suppressed, 0);
}
/// Variable placement really buys coverage: the same crowd places strictly more
/// labels when alternates are allowed. Otherwise the ladder is dead code.
#[test]
fn variable_placement_places_more_than_one_shot() {
let cands: Vec<LabelCandidate> = (0..120)
.map(|i| {
let x = 100.0 + ((i * 23) % 300) as f32;
let y = 100.0 + ((i * 31) % 200) as f32;
LabelCandidate::new(pos2(x, y), vec2(40.0, 12.0), i as f32)
})
.collect();
let one = place_labels(&cands, viewport(), PlaceOpts { variable: false, ..Default::default() });
let var = place_labels(&cands, viewport(), PlaceOpts { variable: true, ..Default::default() });
assert!(
var.placed.len() > one.placed.len(),
"variable placement {} vs one-shot {}",
var.placed.len(),
one.placed.len()
);
let rects: Vec<Rect> = var.placed.iter().map(|p| p.rect).collect();
assert_eq!(max_label_overlap(&rects, viewport(), 1.0), 1, "and still collision-free");
}
/// Off-viewport labels are never considered — the "cost tracks the screen" claim,
/// as data. 100 000 candidates, 20 on screen ⇒ `considered` is 20.
#[test]
fn offscreen_labels_cost_nothing() {
let mut cands: Vec<LabelCandidate> = (0..20)
.map(|i| LabelCandidate::new(pos2(20.0 + i as f32 * 35.0, 300.0), vec2(24.0, 12.0), 1.0))
.collect();
cands.extend((0..100_000).map(|i| {
LabelCandidate::new(pos2(50_000.0 + i as f32, -40_000.0), vec2(24.0, 12.0), 1.0)
}));
let out = place_labels(&cands, viewport(), PlaceOpts::default());
assert_eq!(out.considered, 20, "only the on-screen candidates were considered");
assert_eq!(out.suppressed, 0);
assert!(
out.collision_tests < 400,
"bin-local tests, not quadratic: {} tests",
out.collision_tests
);
}
/// Determinism (FC-7): 64 repeats are byte-identical.
#[test]
fn label_placement_is_deterministic() {
let cands: Vec<LabelCandidate> = (0..300)
.map(|i| {
LabelCandidate::new(
pos2(((i * 41) % 700) as f32, ((i * 67) % 500) as f32),
vec2(38.0, 12.0),
// Deliberate priority ties, so only the index tiebreak saves it.
(i % 5) as f32,
)
})
.collect();
let first = place_labels(&cands, viewport(), PlaceOpts::default());
for _ in 0..64 {
assert_eq!(place_labels(&cands, viewport(), PlaceOpts::default()), first);
}
}
// ── edge thinning ────────────────────────────────────────────────────────
fn hairball(n: usize) -> Vec<(Pos2, Pos2)> {
let mut s = 0x2545_F491_4F6C_DD1Du64;
let mut next = move || {
s ^= s << 13;
s ^= s >> 7;
s ^= s << 17;
(s >> 11) as f32 / (1u64 << 53) as f32
};
(0..n)
.map(|_| {
(
pos2(next() * 800.0, next() * 600.0),
pos2(next() * 800.0, next() * 600.0),
)
})
.collect()
}
/// **THE pixel oracle for edges.** A 20 000-edge hairball saturates the pane; after
/// thinning the saturated-pixel count collapses. Both numbers come from
/// rasterizing the actual segments, and the unthinned control is measured in the
/// same test — so "the hairball is readable now" is a comparison, not a claim.
#[test]
fn thinning_collapses_saturated_ink_and_the_control_proves_it_was_saturated() {
let segs = hairball(20_000);
let vp = viewport();
let all: Vec<u32> = (0..segs.len() as u32).collect();
let (lit_before, peak_before, sat_before) = edge_ink_profile(&segs, &all, vp, 4);
let out = thin_edges(&segs, &[], &[], vp, EdgeThinOpts::default());
let (lit_after, peak_after, sat_after) = edge_ink_profile(&segs, &out.keep, vp, 4);
assert!(sat_before > 10_000, "the control hairball must really be saturated: {sat_before}");
assert!(
sat_after * 4 < sat_before,
"thinning must cut saturated pixels hard: {sat_before} -> {sat_after}"
);
assert!(peak_after < peak_before, "peak pile {peak_before} -> {peak_after}");
assert!(lit_after > 0 && lit_after < lit_before, "still draws a graph: {lit_before} -> {lit_after}");
// The counters agree with the pixels.
assert!(out.peak_density < out.peak_density_before);
assert_eq!(out.keep.len() + out.dropped, out.considered);
}
/// A SPARSE region is not touched. Random subsampling would thin it anyway; this
/// is the property that makes density-aware thinning worth the code.
#[test]
fn a_sparse_graph_loses_no_edges() {
let segs: Vec<(Pos2, Pos2)> = (0..12)
.map(|i| {
let y = 40.0 + i as f32 * 45.0;
(pos2(30.0, y), pos2(760.0, y + 6.0))
})
.collect();
let out = thin_edges(&segs, &[], &[], viewport(), EdgeThinOpts::default());
assert_eq!(out.dropped, 0, "nothing to thin in a sparse graph");
assert_eq!(out.keep.len(), segs.len());
}
/// Flagged edges (path / cycle / hover) survive the densest bucket.
#[test]
fn always_keep_edges_survive_any_density() {
let segs = hairball(5000);
let mut always = vec![false; segs.len()];
for i in (0..segs.len()).step_by(500) {
always[i] = true;
}
let out = thin_edges(&segs, &[], &always, viewport(), EdgeThinOpts { cell: 24.0, keep_per_bucket: 0 });
for (i, &f) in always.iter().enumerate() {
if f {
assert!(out.keep.contains(&(i as u32)), "flagged edge {i} was thinned away");
}
}
assert_eq!(out.keep.len(), always.iter().filter(|&&f| f).count(), "quota 0 keeps only the flagged");
}
/// Weight ranks the survivors — the heaviest edge in a bucket is the one kept.
#[test]
fn the_heaviest_edge_in_a_bucket_is_the_survivor() {
// Four parallel, near-identical segments in one bin + direction bucket.
let segs: Vec<(Pos2, Pos2)> = (0..4)
.map(|i| (pos2(100.0, 100.0 + i as f32), pos2(140.0, 100.0 + i as f32)))
.collect();
let weight = vec![0.1, 0.2, 9.0, 0.3];
let out = thin_edges(&segs, &weight, &[], viewport(), EdgeThinOpts { cell: 24.0, keep_per_bucket: 1 });
assert_eq!(out.keep, vec![2], "the weight-9 edge is the one drawn");
}
/// Determinism (FC-7): the survivors are a pure function of the input, not of
/// `HashMap` bucket order. 64 repeats.
#[test]
fn edge_thinning_is_deterministic() {
let segs = hairball(4000);
let weight: Vec<f32> = (0..segs.len()).map(|i| (i % 7) as f32).collect();
let first = thin_edges(&segs, &weight, &[], viewport(), EdgeThinOpts::default());
for _ in 0..64 {
assert_eq!(thin_edges(&segs, &weight, &[], viewport(), EdgeThinOpts::default()), first);
}
assert!(first.keep.windows(2).all(|w| w[0] < w[1]), "ascending, so paint order is preserved");
}
/// Off-viewport edges are rejected before any work.
#[test]
fn offscreen_edges_cost_nothing() {
let mut segs = hairball(50);
segs.extend((0..50_000).map(|i| {
(pos2(-90_000.0 - i as f32, -90_000.0), pos2(-89_000.0 - i as f32, -89_000.0))
}));
let out = thin_edges(&segs, &[], &[], viewport(), EdgeThinOpts::default());
assert_eq!(out.considered, 50, "only on-screen edges were considered");
}
}