facett-map/tests/big_ring_tessellation.rs
//! **A COUNTRY-SIZED RING MUST TESSELLATE — the hand-rolled ear clip cannot, and it does
//! not say so.**
//!
//! `tessellate::triangulate` is a hand-rolled ear clip: a scan for a convex vertex, an
//! O(m) point-in-triangle test inside it and an O(m) `Vec::remove` — **O(n²)** to consume a
//! ring, with the only bound `guard < n*n + 16`, which for a real coastline is
//! astronomically large. It is CORRECT (these arms measure its area and it is exact); it is
//! quadratic.
//!
//! That was invisible while the biggest ring on a korp pane was the bundled Natural Earth
//! country outline — **238 vertices**. korp's cut step `h` replaced it with the region's OWN
//! coastline, and the Swedish mainland is **295 186 vertices** at its z11 rung: ~10¹¹
//! elementary operations, i.e. a frozen window on the first frame that paints it.
//!
//! MEASURED here, release, on a 20 001-vertex concave spiral: **7.13 s** before, **84 ms**
//! after — same area to the unit, same triangle count to one degenerate.
//!
//! `earcutr` — already a dependency, already the with-holes path — is O(n log n) and does
//! the same job. The arms below are applied output, not a timing opinion: a spiral's CONVEX
//! HULL is nothing like itself, so a fan fallback would be caught by AREA, and the triangle
//! count says whether the whole ring was consumed.
use facett_map::tessellate::triangulate;
/// A closed CCW spiral of `n` vertices — deeply concave, so ear clipping is real work and a
/// convex-hull fan is a visibly different shape.
fn spiral(n: usize) -> Vec<egui::Pos2> {
let mut out = Vec::with_capacity(n + 1);
let turns = 6.0_f32;
let half = n / 2;
// Out along the spiral…
for i in 0..half {
let t = i as f32 / half as f32;
let a = t * turns * std::f32::consts::TAU;
let r = 10.0 + 90.0 * t;
out.push(egui::pos2(r * a.cos(), r * a.sin()));
}
// …and back, one unit inside, so the ring is a thin closed corridor.
for i in (0..half).rev() {
let t = i as f32 / half as f32;
let a = t * turns * std::f32::consts::TAU;
let r = 10.0 + 90.0 * t - 3.0;
out.push(egui::pos2(r * a.cos(), r * a.sin()));
}
let first = out[0];
out.push(first);
out
}
/// Twice the signed area of a triangle list, in the same units as the ring.
fn tri_area(pts: &[egui::Pos2], tris: &[[u32; 3]]) -> f64 {
let mut s = 0.0;
for &[a, b, c] in tris {
let (p, q, r) = (pts[a as usize], pts[b as usize], pts[c as usize]);
s += f64::from(
(q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x),
)
.abs()
/ 2.0;
}
s
}
/// Shoelace area of the ring itself.
fn ring_area(pts: &[egui::Pos2]) -> f64 {
let mut s = 0.0;
for i in 0..pts.len() - 1 {
s += f64::from(pts[i].x) * f64::from(pts[i + 1].y)
- f64::from(pts[i + 1].x) * f64::from(pts[i].y);
}
(s / 2.0).abs()
}
/// **★ RED on the hand-rolled clip: a 20 000-vertex concave ring must triangulate to its
/// OWN area, in a time a frame can afford.**
///
/// 20 000 is two orders of magnitude under the real mainland ring and already far past what
/// an O(n³) clip can do; if this passes, the coastline case is a matter of degree.
#[test]
fn a_twenty_thousand_vertex_ring_tessellates_to_its_own_area() {
let ring = spiral(20_000);
let want = ring_area(&ring);
let t = std::time::Instant::now();
let tris = triangulate(&ring);
let wall = t.elapsed();
let got = tri_area(&ring, &tris);
eprintln!(
"TESS {} vertices -> {} triangles in {:?} | ring area {want:.0}, triangles cover \
{got:.0} ({:.1} %)",
ring.len(),
tris.len(),
wall,
100.0 * got / want,
);
// The budget is a RELEASE budget: an unoptimised earcut is ~20x slower and a debug
// red here would be a false one. MEASURED: release 84 ms, debug ~1.7 s, against the
// 7.13 s the hand-rolled clip took in RELEASE.
let budget = if cfg!(debug_assertions) {
std::time::Duration::from_secs(5)
} else {
std::time::Duration::from_millis(500)
};
assert!(
wall < budget,
"a ring this size must tessellate in frame time, took {wall:?} (budget {budget:?}, \
debug_assertions={})",
cfg!(debug_assertions),
);
// A fan over the remainder fills the CONVEX HULL — for this spiral that is many times
// the ring's own area, so area alone separates a real triangulation from the fallback.
assert!(
(got - want).abs() / want < 0.02,
"the triangles must cover the RING, not its convex hull: {got:.0} vs {want:.0}",
);
assert!(
tris.len() >= ring.len() - 4,
"a ring of n vertices triangulates to about n-2 triangles; {} means the clip gave \
up and fanned",
tris.len(),
);
}
/// **The real-size arm lives where the real data is.** A synthetic spiral is a pathological
/// shape for ANY triangulator — a thin corridor with no fat ears — so timing earcut on a
/// 295 186-vertex spiral (MEASURED: 9.6 s, area exact) says almost nothing about a
/// coastline, which is fat and locally convex nearly everywhere. korp's
/// `tests/landmass_cut.rs::report_the_mainland_tessellation` times the ACTUAL Swedish
/// mainland ring out of `landmass.parquet`, which is the number that matters.
///
/// What this file pins is the property that is shape-independent: the hand-rolled clip is
/// quadratic and earcut is not, and the crossover is [`EARCUT_MIN_VERTICES`].
#[test]
fn the_crossover_is_declared_and_the_small_path_still_exists() {
const _: () = assert!(
facett_map::tessellate::EARCUT_MIN_VERTICES >= 64,
"the hand-rolled clip must keep the footprint-sized case it was written for",
);
const _: () = assert!(
facett_map::tessellate::EARCUT_MIN_VERTICES <= 4096,
"…and must hand over well before the quadratic term is a frame",
);
}
/// A small ring keeps triangulating exactly as it always did — the change must not move
/// the case that was already right.
#[test]
fn a_small_ring_is_unchanged() {
let sq = vec![
egui::pos2(0.0, 0.0),
egui::pos2(10.0, 0.0),
egui::pos2(10.0, 10.0),
egui::pos2(0.0, 10.0),
egui::pos2(0.0, 0.0),
];
let tris = triangulate(&sq);
let got = tri_area(&sq, &tris);
assert!((got - 100.0).abs() < 1e-3, "a 10x10 square is 100 units of triangle: {got}");
// An L, so the concave case is covered too.
let l = vec![
egui::pos2(0.0, 0.0),
egui::pos2(10.0, 0.0),
egui::pos2(10.0, 4.0),
egui::pos2(4.0, 4.0),
egui::pos2(4.0, 10.0),
egui::pos2(0.0, 10.0),
egui::pos2(0.0, 0.0),
];
let got = tri_area(&l, &triangulate(&l));
assert!((got - 64.0).abs() < 1e-3, "the L is 64 units, not its 100-unit hull: {got}");
}