a770fa5a5e5f
region.rs
//! Planar regions: find the closed boundary around a point from a soup of curves (HATCH pick
//! points, BOUNDARY, REGION).
//!
//! The curves arrive as polylines. Segments are split at every crossing, vertices merged within
//! a tolerance, and the face to the left of the edge hit by a ray from the point is traced by
//! always taking the sharpest left turn.
//!
//! Islands are the connected groups of curves that lie inside that face without touching its
//! boundary; each one contributes the outline of its outside (traced the same way, clockwise
//! around the group), so a square drawn as four separate lines is as much an island as a closed
//! polyline.
use std::collections::HashMap;
use crate::{Bounds2, Line, Vec2, line_line, point_in_polygon, shoelace};
/// Upper bound on input segments (keeps the quadratic split bounded on hostile input).
pub const MAX_SEGMENTS: usize = 60_000;
/// Upper bound on islands reported for one boundary (hostile input with many tiny shapes).
pub const MAX_ISLANDS: usize = 4096;
/// Upper bound on open curve ends considered for closing gaps, and on the pairs compared.
const MAX_GAP_ENDS: usize = 50_000;
const MAX_GAP_PAIRS: usize = 5_000_000;
/// The closed boundary around a point and the islands inside it.
#[derive(Clone, Debug, PartialEq)]
pub struct Boundary {
/// Counter-clockwise outer loop.
pub outer: Vec<Vec2>,
/// Groups of curves inside `outer` that don't touch it and don't surround the point.
pub islands: Vec<Island>,
/// Indices into the input polylines that make up `outer`, ascending.
pub outer_sources: Vec<usize>,
}
/// One island: the outside outline of a connected group of curves.
#[derive(Clone, Debug, PartialEq)]
pub struct Island {
/// Counter-clockwise outline (dangling ends removed).
pub outline: Vec<Vec2>,
/// Indices into the input polylines that make up the group, ascending.
pub sources: Vec<usize>,
}
#[expect(
clippy::cast_possible_truncation,
reason = "Rounded tolerance-bin coordinates intentionally use the defined saturating f64-to-i64 conversion."
)]
fn key(p: Vec2, origin: Vec2, q: f64) -> (i64, i64) {
// The drawing may be georeferenced far from (0, 0). Quantizing absolute
// coordinates saturates i64 and aliases distinct vertices into one key.
// Shift to the bounds origin before converting to tolerance-sized bins.
(((p.x - origin.x) / q).round() as i64, ((p.y - origin.y) / q).round() as i64)
}
struct Graph {
pts: Vec<Vec2>,
adj: Vec<Vec<usize>>,
/// (graph vertex, input polyline) for every input segment: which curve touches which group.
src: Vec<(usize, usize)>,
/// The input polyline of every edge (lower vertex index first).
edge_src: HashMap<(usize, usize), usize>,
}
/// Records the crossing of segments `i` and `j`, if any, as split parameters on both.
fn split_pair(segs: &[(Vec2, Vec2)], splits: &mut [Vec<f64>], i: usize, j: usize) {
let (Some(si), Some(sj)) = (segs.get(i), segs.get(j)) else { return };
let li = Line::new(si.0, si.1);
let lj = Line::new(sj.0, sj.1);
if let Some(x) = line_line(&li, &lj) {
if let Some(v) = splits.get_mut(i) {
v.push(li.param_of(x).clamp(0.0, 1.0));
}
if let Some(v) = splits.get_mut(j) {
v.push(lj.param_of(x).clamp(0.0, 1.0));
}
}
}
/// Upper bound on candidate-pair *visits*. Every visit counts, including repeats of a pair that shares several grid
/// cells, not only the distinct pairs actually tested. A long segment replicated across many
/// cells makes the same pair reappear in each, so a budget on distinct pairs alone leaves the
/// repeated work unbounded (CWE-407).
const MAX_PAIR_VISITS: u64 = 60_000_000;
/// Upper bound on distinct segment pairs tested for a crossing.
const MAX_PAIRS_TESTED: usize = 20_000_000;
/// Split parameters of every segment (always `0` and `1`, plus every crossing), found with a uniform grid.
fn pair_splits(segs: &[(Vec2, Vec2)], bb: &Bounds2) -> Option<Vec<Vec<f64>>> {
pair_splits_limited(segs, bb, MAX_PAIR_VISITS, MAX_PAIRS_TESTED)
}
/// `pair_splits` with explicit budgets: `None` once more than `max_visits` candidate pairs were visited
/// or more than `max_pairs` distinct pairs were tested.
#[expect(
clippy::cast_precision_loss,
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
reason = "At most 60,000 segments and 512 grid cells bound the numeric conversions; cell coordinates are clamped before casting."
)]
fn pair_splits_limited(segs: &[(Vec2, Vec2)], bb: &Bounds2, max_visits: u64, max_pairs: usize) -> Option<Vec<Vec<f64>>> {
let n = segs.len();
let cells = ((n as f64).sqrt().ceil() as usize).clamp(1, 512);
let cw = (bb.width() / cells as f64).max(1e-12);
let ch = (bb.height() / cells as f64).max(1e-12);
let cell = |p: Vec2| {
(
((p.x - bb.min.x) / cw).floor().clamp(0.0, (cells - 1) as f64) as usize,
((p.y - bb.min.y) / ch).floor().clamp(0.0, (cells - 1) as f64) as usize,
)
};
// Cell lists in a flat grid, indexed `gx * cells + gy`; each list is in ascending segment order.
let mut grid: Vec<Vec<usize>> = vec![Vec::new(); cells * cells];
// The lowest cell of each segment's cell range; the lowest cell two segments share is the
// componentwise maximum of their two.
let mut low: Vec<(usize, usize)> = vec![(0, 0); n];
let mut is_long = vec![false; n];
let mut long: Vec<usize> = Vec::new();
for (i, (a, b)) in segs.iter().enumerate() {
let (x0, y0) = cell(a.min(*b));
let (x1, y1) = cell(a.max(*b));
if let Some(l) = low.get_mut(i) {
*l = (x0, y0);
}
if (x1 - x0 + 1) * (y1 - y0 + 1) > 4096 {
// Very long segment: too many cells to register in; it is tested against every segment below.
long.push(i);
if let Some(f) = is_long.get_mut(i) {
*f = true;
}
continue;
}
for gx in x0..=x1 {
for gy in y0..=y1 {
if let Some(list) = grid.get_mut(gx * cells + gy) {
list.push(i);
}
}
}
}
let mut splits: Vec<Vec<f64>> = vec![vec![0.0, 1.0]; n];
let mut tested: usize = 0;
let mut visits: u64 = 0;
for (c, list) in grid.iter().enumerate() {
let (gx, gy) = (c / cells, c % cells);
for (k, &i) in list.iter().enumerate() {
let Some(&(ix, iy)) = low.get(i) else { continue };
for &j in list.iter().skip(k + 1) {
visits += 1;
if visits > max_visits {
return None;
}
let Some(&(jx, jy)) = low.get(j) else { continue };
// A pair sharing several cells is tested once, in the lowest cell both occupy.
if i == j || gx != ix.max(jx) || gy != iy.max(jy) {
continue;
}
split_pair(segs, &mut splits, i, j);
tested += 1;
if tested > max_pairs {
return None;
}
}
}
}
// A long segment is in no cell list. Two long segments are tested once, from the lower index.
for &i in &long {
for j in 0..n {
if i == j || (j < i && is_long.get(j).copied().unwrap_or(false)) {
continue;
}
split_pair(segs, &mut splits, i, j);
tested += 1;
if tested > max_pairs {
return None;
}
}
}
Some(splits)
}
fn build(polys: &[Vec<Vec2>], tol: f64) -> Option<Graph> {
build_with(polys, tol, pair_splits)
}
/// `build` with the crossing search injected, so tests can run the old and the new search on the same input.
fn build_with(polys: &[Vec<Vec2>], tol: f64, find_splits: impl Fn(&[(Vec2, Vec2)], &Bounds2) -> Option<Vec<Vec<f64>>>) -> Option<Graph> {
let mut segs: Vec<(Vec2, Vec2)> = Vec::new();
let mut owner: Vec<usize> = Vec::new();
for (k, pl) in polys.iter().enumerate() {
for w in pl.windows(2) {
if let [a, b] = w
&& a.is_finite()
&& b.is_finite()
&& !a.near(*b, tol)
{
segs.push((*a, *b));
owner.push(k);
}
}
if segs.len() > MAX_SEGMENTS {
return None;
}
}
if segs.is_empty() || segs.len() > MAX_SEGMENTS {
return None;
}
let bb = Bounds2::from_points(segs.iter().flat_map(|(a, b)| [*a, *b]));
let n = segs.len();
let splits = find_splits(&segs, &bb)?;
let mut g = Graph { pts: Vec::new(), adj: Vec::new(), src: Vec::with_capacity(n), edge_src: HashMap::new() };
let mut index: HashMap<(i64, i64), usize> = HashMap::new();
let mut vid = |p: Vec2, g: &mut Graph| -> usize {
let k = key(p, bb.min, tol);
*index.entry(k).or_insert_with(|| {
g.pts.push(p);
g.adj.push(Vec::new());
g.pts.len() - 1
})
};
for (i, (a, b)) in segs.iter().enumerate() {
let mut ts = splits.get(i).cloned().unwrap_or_default();
ts.sort_by(f64::total_cmp);
ts.dedup_by(|x, y| (*x - *y).abs() < 1e-12);
let line = Line::new(*a, *b);
let first = vid(*a, &mut g);
if let Some(k) = owner.get(i) {
g.src.push((first, *k));
}
for w in ts.windows(2) {
if let [t0, t1] = w {
let u = vid(line.at(*t0), &mut g);
let v = vid(line.at(*t1), &mut g);
if u != v {
if let Some(k) = owner.get(i) {
g.edge_src.entry((u.min(v), u.max(v))).or_insert(*k);
}
if let Some(l) = g.adj.get_mut(u)
&& !l.contains(&v)
{
l.push(v);
}
if let Some(l) = g.adj.get_mut(v)
&& !l.contains(&u)
{
l.push(u);
}
}
}
}
}
Some(g)
}
/// The graph of the curves with gaps of up to `gap` between open ends bridged: each open end
/// joins the nearest other open end within reach.
fn build_gap(polys: &[Vec<Vec2>], tol: f64, gap: f64) -> Option<Graph> {
let mut g = build(polys, tol.max(1e-12))?;
if !(gap.is_finite() && gap > tol) {
return Some(g);
}
let mut ends: Vec<(Vec2, usize)> =
g.adj.iter().enumerate().filter(|(_, ns)| ns.len() == 1).filter_map(|(u, _)| Some((*g.pts.get(u)?, u))).take(MAX_GAP_ENDS).collect();
ends.sort_by(|a, b| a.0.x.total_cmp(&b.0.x));
let mut joined = vec![false; ends.len()];
let mut budget = MAX_GAP_PAIRS;
for i in 0..ends.len() {
let (Some(&(pu, u)), Some(false)) = (ends.get(i), joined.get(i).copied()) else { continue };
let lo = ends.partition_point(|e| e.0.x < pu.x - gap);
let mut best: Option<(f64, usize)> = None;
for (j, &(pv, v)) in ends.iter().enumerate().skip(lo) {
if pv.x > pu.x + gap || budget == 0 {
break;
}
budget -= 1;
if j == i || joined.get(j).copied().unwrap_or(true) || g.adj.get(u).is_some_and(|l| l.contains(&v)) {
continue;
}
let d = pu.dist(pv);
if d <= gap && best.is_none_or(|(bd, _)| d < bd) {
best = Some((d, j));
}
}
let Some((_, j)) = best else { continue };
let Some(&(_, v)) = ends.get(j) else { continue };
let owner = g.adj.get(u).and_then(|l| l.first()).and_then(|w| g.edge_src.get(&(u.min(*w), u.max(*w))).copied());
if let Some(l) = g.adj.get_mut(u) {
l.push(v);
}
if let Some(l) = g.adj.get_mut(v) {
l.push(u);
}
if let Some(k) = owner {
g.edge_src.insert((u.min(v), u.max(v)), k);
}
if let Some(f) = joined.get_mut(i) {
*f = true;
}
if let Some(f) = joined.get_mut(j) {
*f = true;
}
}
Some(g)
}
/// Trace the face left of half-edge u→v (vertex indices), giving up after `max_steps` edges.
fn trace(g: &Graph, u0: usize, v0: usize, max_steps: usize) -> Option<Vec<usize>> {
let (mut u, mut v) = (u0, v0);
let mut out = vec![u];
for _ in 0..max_steps {
out.push(v);
let pv = *g.pts.get(v)?;
let back = (*g.pts.get(u)? - pv).angle();
let mut best: Option<(f64, usize)> = None;
for &w in g.adj.get(v)? {
if w == u && g.adj.get(v).is_some_and(|l| l.len() > 1) {
continue;
}
let a = (*g.pts.get(w)? - pv).angle();
let mut cw = crate::norm_angle(back - a);
if cw < 1e-12 {
cw = crate::TAU;
}
if best.is_none_or(|(b, _)| cw < b) {
best = Some((cw, w));
}
}
let (_, w) = best?;
u = v;
v = w;
if u == u0 && v == v0 {
out.pop();
return Some(out);
}
}
None
}
fn points(g: &Graph, ids: &[usize]) -> Option<Vec<Vec2>> {
ids.iter().map(|&i| g.pts.get(i).copied()).collect()
}
/// The face around `p`, as vertex indices (counter-clockwise).
#[expect(clippy::many_single_char_names, reason = "Ray/edge traversal keeps conventional graph and point notation.")]
fn outer_face(g: &Graph, p: Vec2) -> Option<Vec<usize>> {
// Try hits along a ray to +X from nearest outward, so nested faces resolve to the innermost.
let mut hits: Vec<(f64, usize, usize)> = Vec::new();
for (u, ns) in g.adj.iter().enumerate() {
for &v in ns {
if u >= v {
continue;
}
let (Some(a), Some(b)) = (g.pts.get(u), g.pts.get(v)) else { continue };
if (a.y > p.y) != (b.y > p.y) {
let x = a.x + (b.x - a.x) * (p.y - a.y) / (b.y - a.y);
if x > p.x {
hits.push((x, u, v));
}
}
}
}
hits.sort_by(|x, y| x.0.total_cmp(&y.0));
let max_steps = g.pts.len().saturating_mul(2).max(16);
for (_, a, b) in hits.into_iter().take(64) {
let (pa, pb) = (*g.pts.get(a)?, *g.pts.get(b)?);
let (u, v) = if (pb - pa).cross(p - pa) > 0.0 { (a, b) } else { (b, a) };
if let Some(ids) = trace(g, u, v, max_steps)
&& ids.len() >= 3
&& let Some(lp) = points(g, &ids)
&& shoelace(&lp) > 0.0
&& point_in_polygon(&lp, p)
{
return Some(ids);
}
}
None
}
/// Connected component id of every vertex.
fn components(g: &Graph) -> Vec<usize> {
let mut comp = vec![usize::MAX; g.pts.len()];
let mut next = 0;
let mut stack = Vec::new();
for start in 0..g.pts.len() {
if comp.get(start).is_none_or(|c| *c != usize::MAX) {
continue;
}
stack.push(start);
while let Some(u) = stack.pop() {
match comp.get_mut(u) {
Some(c) if *c == usize::MAX => *c = next,
_ => continue,
}
stack.extend(g.adj.get(u).into_iter().flatten().copied());
}
next += 1;
}
comp
}
/// The graph without dangling ends: vertices of degree one are removed until none remain, so
/// only edges on cycles are left.
fn prune(g: &Graph) -> Graph {
let mut adj = g.adj.clone();
let mut stack: Vec<usize> = (0..adj.len()).filter(|&u| adj.get(u).is_some_and(|l| l.len() == 1)).collect();
while let Some(u) = stack.pop() {
let Some(l) = adj.get_mut(u) else { continue };
if l.len() != 1 {
continue;
}
let ns = std::mem::take(l);
for v in ns {
if let Some(lv) = adj.get_mut(v) {
lv.retain(|&w| w != u);
if lv.len() == 1 {
stack.push(v);
}
}
}
}
Graph { pts: g.pts.clone(), adj, src: Vec::new(), edge_src: HashMap::new() }
}
/// The outline of the outside of a group of curves on cycles, traced counter-clockwise from its
/// leftmost (then lowest) vertex `u`, giving up after `steps` edges.
fn outside(core: &Graph, u: usize, steps: usize) -> Option<Vec<Vec2>> {
let pu = *core.pts.get(u)?;
// Every neighbour lies to the right of the leftmost vertex; the one turned furthest
// counter-clockwise has the outside of the group on its left.
let signed = |w: &usize| {
core.pts.get(*w).map(|q| {
let a = (*q - pu).angle();
if a > crate::PI { a - crate::TAU } else { a }
})
};
let w = core.adj.get(u).into_iter().flatten().filter_map(|w| Some((signed(w)?, *w))).max_by(|a, b| a.0.total_cmp(&b.0)).map(|(_, w)| w)?;
let mut lp = trace(core, u, w, steps).and_then(|ids| points(core, &ids))?;
lp.reverse();
Some(lp)
}
/// Outlines of the groups of curves inside the face `outer` (vertex indices into `g`).
#[expect(
clippy::float_cmp,
clippy::many_single_char_names,
reason = "Exact x equality is required for the deterministic lexicographic tie-break; graph equations keep their conventional short names."
)]
fn islands(g: &Graph, outer: &[usize], p: Vec2) -> Option<Vec<Island>> {
let comp = components(g);
let outer_comp: std::collections::HashSet<usize> = outer.iter().filter_map(|&i| comp.get(i).copied()).collect();
let outer_pts = points(g, outer)?;
let ob = Bounds2::from_points(outer_pts.iter().copied());
let core = prune(g);
// Leftmost (then lowest) vertex still on a cycle, per component.
let mut start: HashMap<usize, usize> = HashMap::new();
let mut edges: HashMap<usize, usize> = HashMap::new();
for (u, ns) in core.adj.iter().enumerate() {
let (Some(&c), Some(q)) = (comp.get(u), core.pts.get(u)) else { continue };
if ns.is_empty() || outer_comp.contains(&c) {
continue;
}
*edges.entry(c).or_default() += ns.len();
let e = start.entry(c).or_insert(u);
if let Some(b) = core.pts.get(*e)
&& (q.x < b.x || (q.x == b.x && q.y < b.y))
{
*e = u;
}
}
let mut sources: HashMap<usize, Vec<usize>> = HashMap::new();
for &(v, k) in &g.src {
if let Some(&c) = comp.get(v)
&& start.contains_key(&c)
{
sources.entry(c).or_default().push(k);
}
}
let mut starts: Vec<(usize, usize)> = start.into_iter().collect();
starts.sort_unstable();
let mut out = Vec::new();
// Each containment test scans a whole polygon, accepted or not: they share one allowance of
// polygon edges, and the search ends when it is spent.
let mut edges_left: usize = 100_000_000;
for (c, u) in starts {
if out.len() >= MAX_ISLANDS {
break;
}
let Some(&pu) = core.pts.get(u) else { continue };
if !ob.contains(pu) {
continue;
}
let left = edges_left.checked_sub(outer_pts.len())?;
edges_left = left;
if !point_in_polygon(&outer_pts, pu) {
continue;
}
let steps = edges.get(&c).copied().unwrap_or(0).saturating_add(4);
let Some(lp) = outside(&core, u, steps) else { continue };
let area = shoelace(&lp);
let ib = Bounds2::from_points(lp.iter().copied());
if lp.len() < 3 || !area.is_finite() || area <= 0.0 || !ob.contains_box(&ib) {
continue;
}
let left = edges_left.checked_sub(lp.len())?;
edges_left = left;
if point_in_polygon(&lp, p) {
continue;
}
let mut src = sources.remove(&c).unwrap_or_default();
src.sort_unstable();
src.dedup();
out.push(Island { outline: lp, sources: src });
}
Some(out)
}
/// The point of the nearest other curve within `snap` of the end `e` of curve `i`, as (curve,
/// segment, parameter, point). `None` when the end touches a curve, or none is near. `Err` when
/// the budget of segment checks runs out.
#[expect(clippy::many_single_char_names, reason = "Nearest-point search keeps conventional i/j/k/a/b/t/q/d geometry notation.")]
fn nearest_curve(polys: &[Vec<Vec2>], i: usize, e: Vec2, snap: f64, tol: f64, budget: &mut usize) -> Result<Option<(usize, usize, f64, Vec2)>, ()> {
let mut best: Option<(f64, usize, usize, f64, Vec2)> = None;
let mut touching = false;
for (j, other) in polys.iter().enumerate() {
if j == i {
continue;
}
// A curve with no segment costs a visit too, so many of them can't multiply the searches.
if other.len() < 2 {
*budget = budget.checked_sub(1).ok_or(())?;
}
for (k, w) in other.windows(2).enumerate() {
if *budget == 0 {
return Err(());
}
*budget -= 1;
let [a, b] = w else { continue };
if !(a.is_finite() && b.is_finite())
|| e.x < a.x.min(b.x) - snap
|| e.x > a.x.max(b.x) + snap
|| e.y < a.y.min(b.y) - snap
|| e.y > a.y.max(b.y) + snap
{
continue;
}
let line = Line::new(*a, *b);
let t = line.param_of(e).clamp(0.0, 1.0);
let q = line.at(t);
let d = q.dist(e);
if d <= tol {
touching = true;
} else if d <= snap && best.is_none_or(|(bd, ..)| d < bd) {
best = Some((d, j, k, t, q));
}
}
}
Ok(best.filter(|_| !touching).map(|(_, j, k, t, q)| (j, k, t, q)))
}
/// The curves with each open end that stops within `snap` of another curve moved onto that
/// curve (which gains a vertex there), so the two meet exactly. A curve that is flattened
/// into chords (an ellipse, a spline) lies up to the flattening tolerance off the true curve,
/// so a line that ends on the true curve can stop just short of the chords.
#[expect(clippy::many_single_char_names, reason = "Endpoint snapping keeps conventional polyline, segment and point notation.")]
pub fn snap_ends(polys: &[Vec<Vec2>], snap: f64, tol: f64) -> Vec<Vec<Vec2>> {
let mut out: Vec<Vec<Vec2>> = polys.to_vec();
if !(snap.is_finite() && snap > tol) {
return out;
}
// build() refuses this input anyway; don't spend ends x segments work on it.
let total: usize = polys.iter().map(|p| p.len().saturating_sub(1)).sum();
if total > MAX_SEGMENTS {
return out;
}
// (target polyline, segment index, parameter on it, the point) for every vertex to insert.
let mut inserts: Vec<(usize, usize, f64, Vec2)> = Vec::new();
let mut budget = MAX_GAP_PAIRS;
'ends: for (i, pl) in polys.iter().enumerate() {
let (Some(&first), Some(&last)) = (pl.first(), pl.last()) else { continue };
if pl.len() < 2 || first.near(last, tol) {
continue;
}
for at_end in [false, true] {
let e = if at_end { last } else { first };
if !e.is_finite() {
continue;
}
let Ok(near) = nearest_curve(polys, i, e, snap, tol, &mut budget) else { break 'ends };
let Some((j, k, t, q)) = near else { continue };
let Some(slot) = out.get_mut(i).and_then(|v| if at_end { v.last_mut() } else { v.first_mut() }) else { continue };
*slot = q;
let ends = polys.get(j).and_then(|o| o.get(k).zip(o.get(k + 1)));
if let Some((&a, &b)) = ends
&& !q.near(a, tol)
&& !q.near(b, tol)
{
inserts.push((j, k, t, q));
}
}
}
// Later segments and larger parameters first, so earlier indices stay valid.
inserts.sort_by(|x, y| y.0.cmp(&x.0).then(y.1.cmp(&x.1)).then(y.2.total_cmp(&x.2)));
for (j, k, _, q) in inserts {
if let Some(v) = out.get_mut(j)
&& k < v.len()
{
v.insert(k + 1, q);
}
}
out
}
/// The closed loop enclosing `p`, counter-clockwise, or `None`.
pub fn enclosing_loop(polys: &[Vec<Vec2>], p: Vec2, tol: f64) -> Option<Vec<Vec2>> {
enclosing_loop_gap(polys, p, tol, 0.0)
}
/// [`enclosing_loop`], with gaps of up to `gap` between curve ends closed (HPGAPTOL).
pub fn enclosing_loop_gap(polys: &[Vec<Vec2>], p: Vec2, tol: f64, gap: f64) -> Option<Vec<Vec2>> {
let g = build_gap(polys, tol, gap)?;
points(&g, &outer_face(&g, p)?)
}
/// The closed loop enclosing `p` plus the islands inside it, or `None` when `p` isn't enclosed.
pub fn boundary_at(polys: &[Vec<Vec2>], p: Vec2, tol: f64) -> Option<Boundary> {
boundary_at_gap(polys, p, tol, 0.0)
}
/// [`boundary_at`], with gaps of up to `gap` between curve ends closed (HPGAPTOL).
pub fn boundary_at_gap(polys: &[Vec<Vec2>], p: Vec2, tol: f64, gap: f64) -> Option<Boundary> {
let g = build_gap(polys, tol, gap)?;
let ids = outer_face(&g, p)?;
let outer = points(&g, &ids)?;
let islands = islands(&g, &ids, p)?;
let mut outer_sources: Vec<usize> =
ids.iter().zip(ids.iter().cycle().skip(1)).filter_map(|(&u, &v)| g.edge_src.get(&(u.min(v), u.max(v))).copied()).collect();
outer_sources.sort_unstable();
outer_sources.dedup();
Some(Boundary { outer, islands, outer_sources })
}
/// The outside outline of curves that together enclose an area (counter-clockwise, dangling
/// ends removed), or `None` when they enclose nothing or form more than one separate group.
/// Gaps of up to `gap` between curve ends are closed (HPGAPTOL).
#[expect(clippy::float_cmp, reason = "Exact x equality is required for the deterministic lexicographic tie-break.")]
pub fn outline(polys: &[Vec<Vec2>], tol: f64, gap: f64) -> Option<Vec<Vec2>> {
let g = build_gap(polys, tol, gap)?;
let core = prune(&g);
let comp = components(&core);
let mut start: Option<usize> = None;
let mut group: Option<usize> = None;
let mut edges = 0usize;
for (u, ns) in core.adj.iter().enumerate() {
if ns.is_empty() {
continue;
}
let c = comp.get(u).copied()?;
if group.is_some_and(|g| g != c) {
return None;
}
group = Some(c);
edges = edges.saturating_add(ns.len());
let q = core.pts.get(u)?;
if start.and_then(|s| core.pts.get(s)).is_none_or(|b| q.x < b.x || (q.x == b.x && q.y < b.y)) {
start = Some(u);
}
}
let lp = outside(&core, start?, edges.saturating_add(4))?;
(lp.len() >= 3 && shoelace(&lp) > 0.0).then_some(lp)
}
/// A point strictly inside a closed polygon (either orientation), for re-finding the face a
/// loop encloses: the middle of the widest span of a horizontal line through it.
pub fn interior_point(poly: &[Vec2]) -> Option<Vec2> {
let b = Bounds2::from_points(poly.iter().copied().filter(|p| p.is_finite()));
if poly.len() < 3 || b.is_empty() || b.height() <= 0.0 {
return None;
}
let mut best: Option<(f64, Vec2)> = None;
for f in [0.5, 0.381_966, 0.618_034, 0.25, 0.75] {
let y = b.min.y + b.height() * f;
let mut xs: Vec<f64> = Vec::new();
for (a, c) in poly.iter().zip(poly.iter().cycle().skip(1)) {
if (a.y > y) != (c.y > y) {
xs.push(a.x + (c.x - a.x) * (y - a.y) / (c.y - a.y));
}
}
xs.sort_by(f64::total_cmp);
for [x0, x1] in xs.as_chunks::<2>().0 {
let width = x1 - x0;
if width.is_finite() && best.is_none_or(|(bw, _)| width > bw) {
best = Some((width, Vec2::new((x0 + x1) / 2.0, y)));
}
}
}
best.filter(|(w, _)| *w > 0.0).map(|(_, p)| p)
}
#[cfg(test)]
mod tests {
use super::*;
fn square(x0: f64, y0: f64, s: f64) -> Vec<Vec2> {
vec![Vec2::new(x0, y0), Vec2::new(x0 + s, y0), Vec2::new(x0 + s, y0 + s), Vec2::new(x0, y0 + s), Vec2::new(x0, y0)]
}
/// The crossing search before the lowest-shared-cell rule: a `HashSet` of tested pairs over a `HashMap` grid.
fn pair_splits_oracle(segs: &[(Vec2, Vec2)], bb: &Bounds2, max_visits: u64, max_pairs: usize) -> Option<Vec<Vec<f64>>> {
let n = segs.len();
let cells = ((n as f64).sqrt().ceil() as usize).clamp(1, 512);
let cw = (bb.width() / cells as f64).max(1e-12);
let ch = (bb.height() / cells as f64).max(1e-12);
let cell = |p: Vec2| {
(
((p.x - bb.min.x) / cw).floor().clamp(0.0, (cells - 1) as f64) as usize,
((p.y - bb.min.y) / ch).floor().clamp(0.0, (cells - 1) as f64) as usize,
)
};
let mut grid: HashMap<(usize, usize), Vec<usize>> = HashMap::new();
let mut long: Vec<usize> = Vec::new();
for (i, (a, b)) in segs.iter().enumerate() {
let (x0, y0) = cell(a.min(*b));
let (x1, y1) = cell(a.max(*b));
if (x1 - x0 + 1) * (y1 - y0 + 1) > 4096 {
long.push(i);
continue;
}
for gx in x0..=x1 {
for gy in y0..=y1 {
grid.entry((gx, gy)).or_default().push(i);
}
}
}
let mut splits: Vec<Vec<f64>> = vec![vec![0.0, 1.0]; n];
let mut tested = std::collections::HashSet::new();
let mut visits: u64 = 0;
for list in grid.values() {
for (k, &i) in list.iter().enumerate() {
for &j in list.iter().skip(k + 1) {
visits += 1;
if visits > max_visits {
return None;
}
if i == j || !tested.insert((i.min(j), i.max(j))) {
continue;
}
split_pair(segs, &mut splits, i, j);
if tested.len() > max_pairs {
return None;
}
}
}
}
for &i in &long {
for j in 0..n {
if i == j || !tested.insert((i.min(j), i.max(j))) {
continue;
}
split_pair(segs, &mut splits, i, j);
if tested.len() > max_pairs {
return None;
}
}
}
Some(splits)
}
struct Rng(u64);
impl Rng {
fn next(&mut self) -> u64 {
self.0 ^= self.0 << 13;
self.0 ^= self.0 >> 7;
self.0 ^= self.0 << 17;
self.0
}
fn unit(&mut self) -> f64 {
(self.next() >> 11) as f64 / (1u64 << 53) as f64
}
}
/// Random segments: short ones, some long ones, and some on a coarse lattice (shared ends, overlaps).
fn random_segments(r: &mut Rng, n: usize, size: f64, long_every: u64) -> Vec<(Vec2, Vec2)> {
let mut out = Vec::new();
for _ in 0..n {
let a = Vec2::new(r.unit() * size, r.unit() * size);
let seg = match r.next() % 4 {
0 if long_every > 0 && r.next().is_multiple_of(long_every) => (
Vec2::new(r.unit() * size * 0.02, r.unit() * size * 0.02),
Vec2::new(size * (0.98 + r.unit() * 0.02), size * (0.98 + r.unit() * 0.02)),
),
1 => {
let q = |r: &mut Rng| (r.next() % 9) as f64 * size / 8.0;
(Vec2::new(q(r), q(r)), Vec2::new(q(r), q(r)))
}
_ => (a, a + Vec2::new((r.unit() - 0.5) * size * 0.1, (r.unit() - 0.5) * size * 0.1)),
};
if !seg.0.near(seg.1, 1e-9) {
out.push(seg);
}
}
out
}
fn sorted_bits(splits: &[Vec<f64>]) -> Vec<Vec<u64>> {
splits
.iter()
.map(|v| {
let mut v = v.clone();
v.sort_by(f64::total_cmp);
v.iter().map(|x| x.to_bits()).collect()
})
.collect()
}
fn bounds_of(segs: &[(Vec2, Vec2)]) -> Bounds2 {
Bounds2::from_points(segs.iter().flat_map(|(a, b)| [*a, *b]))
}
fn assert_same_search(segs: &[(Vec2, Vec2)], max_visits: u64, max_pairs: usize) {
let bb = bounds_of(segs);
let old = pair_splits_oracle(segs, &bb, max_visits, max_pairs);
let new = pair_splits_limited(segs, &bb, max_visits, max_pairs);
assert_eq!(old.as_deref().map(sorted_bits), new.as_deref().map(sorted_bits), "n={} visits<={max_visits} pairs<={max_pairs}", segs.len());
}
#[test]
fn pair_search_matches_oracle_with_budgets() {
// Small inputs in few cells: many pairs share several cells. Sweeping each budget over
// 0..=400 crosses its exhaustion point for most seeds, including the exact boundary.
for seed in 1..=150u64 {
let mut r = Rng(seed.wrapping_mul(0x9E37_79B9_7F4A_7C15) | 1);
let n = 2 + (r.next() % 28) as usize;
let segs = random_segments(&mut r, n, 100.0, 0);
if segs.is_empty() {
continue;
}
for v in 0..=400u64 {
assert_same_search(&segs, v, usize::MAX);
}
for p in 0..=400usize {
assert_same_search(&segs, u64::MAX, p);
}
assert_same_search(&segs, 60_000_000, 20_000_000);
}
}
#[test]
fn pair_search_matches_oracle_with_long_segments() {
// Around 5000 segments give a 71x71 grid, so a diagonal covers more than 4096 cells and takes the long path.
for seed in 1..=3u64 {
let mut r = Rng(seed.wrapping_mul(0xD1B5_4A32_D192_ED03) | 1);
let n = 5_000 + (r.next() % 500) as usize;
let segs = random_segments(&mut r, n, 1000.0, 40);
let bb = bounds_of(&segs);
let cells = ((segs.len() as f64).sqrt().ceil() as usize).clamp(1, 512);
assert!(cells >= 64, "grid too coarse to reach the long path");
assert_same_search(&segs, 60_000_000, 20_000_000);
// Budgets exhausted in the cell phase (visits, then pairs).
assert_same_search(&segs, 3_000, 20_000_000);
assert_same_search(&segs, 60_000_000, 200);
assert!(pair_splits_limited(&segs, &bb, 3_000, 20_000_000).is_none());
assert!(pair_splits_limited(&segs, &bb, 60_000_000, 200).is_none());
let (cw, ch) = ((bb.width() / cells as f64).max(1e-12), (bb.height() / cells as f64).max(1e-12));
let span = |a: f64, b: f64, o: f64, w: f64| {
(((b.max(a) - o) / w).floor().min((cells - 1) as f64) - ((b.min(a) - o) / w).floor().max(0.0) + 1.0) as usize
};
let long = segs.iter().filter(|(a, b)| span(a.x, b.x, bb.min.x, cw) * span(a.y, b.y, bb.min.y, ch) > 4096).count();
assert!(long > 0, "seed {seed}: no segment takes the long path");
}
}
#[test]
fn build_matches_oracle_on_random_drawings() {
for seed in 1..=60u64 {
let mut r = Rng(seed.wrapping_mul(0xA076_1D64_78BD_642F) | 1);
let n = 5 + (r.next() % 400) as usize;
let polys: Vec<Vec<Vec2>> = random_segments(&mut r, n, 100.0, 0).into_iter().map(|(a, b)| vec![a, b]).collect();
let old = build_with(&polys, 1e-6, |s, bb| pair_splits_oracle(s, bb, MAX_PAIR_VISITS, MAX_PAIRS_TESTED));
let new = build(&polys, 1e-6);
let (Some(old), Some(new)) = (old, new) else { panic!("seed {seed}: build failed") };
assert_eq!(old.pts, new.pts, "seed {seed}");
assert_eq!(old.adj, new.adj, "seed {seed}");
assert_eq!(old.src, new.src, "seed {seed}");
assert_eq!(old.edge_src, new.edge_src, "seed {seed}");
}
}
#[test]
#[expect(clippy::cast_precision_loss, reason = "The test generates 17,000 segments, so every grid index is exact as f64.")]
fn long_segment_crossing_in_unsampled_cell_is_split() {
// A diagonal long enough to skip the grid, and a short segment crossing it in a cell the old coarse sampling missed.
let mut polys = vec![vec![Vec2::new(0.0, 0.0), Vec2::new(1000.0, 1000.0)], vec![Vec2::new(11.0, 12.0), Vec2::new(12.0, 11.0)]];
for i in 0..17_000usize {
let x = 600.0 + (i % 130) as f64 * 2.0;
let y = 100.0 + (i / 130) as f64 * 2.0;
polys.push(vec![Vec2::new(x, y), Vec2::new(x + 1.0, y)]);
}
let g = build(&polys, 1e-6).unwrap();
let hit = g.pts.iter().position(|p| p.near(Vec2::new(11.5, 11.5), 1e-6)).unwrap();
assert_eq!(g.adj[hit].len(), 4);
}
#[test]
fn finds_square_around_point() {
let l = enclosing_loop(&[square(0.0, 0.0, 10.0)], Vec2::new(5.0, 5.0), 1e-9).unwrap();
assert!((shoelace(&l) - 100.0).abs() < 1e-9);
}
#[test]
fn boundaries_at_large_world_coordinates_keep_distinct_vertices() {
// Absolute-position / tolerance is beyond i64::MAX for this normal
// georeferenced drawing; the old key collapsed every square corner.
let origin = 1e12;
let outline = square(origin, origin, 100.0);
let picked = Vec2::new(origin + 50.0, origin + 50.0);
let found = enclosing_loop(&[outline], picked, 1e-9).expect("large-coordinate boundary");
assert_eq!(found.len(), 4);
assert!((shoelace(&found) - 10_000.0).abs() < 1e-5);
// Island detection uses the same graph and must preserve its loop.
let result = boundary_at(&[square(origin, origin, 100.0)], picked, 1e-9).expect("boundary with islands");
assert_eq!(result.outer.len(), 4);
assert!(result.islands.is_empty());
}
#[test]
fn crossing_lines_make_faces() {
// A square cut by a diagonal: the face is a triangle.
let polys = vec![square(0.0, 0.0, 10.0), vec![Vec2::new(0.0, 0.0), Vec2::new(10.0, 10.0)]];
let l = enclosing_loop(&polys, Vec2::new(7.0, 2.0), 1e-9).unwrap();
assert!((shoelace(&l) - 50.0).abs() < 1e-9);
}
#[test]
fn overlapping_separate_lines() {
// Four separate lines that overshoot each other (typical hand drafting).
let polys = vec![
vec![Vec2::new(-1.0, 0.0), Vec2::new(11.0, 0.0)],
vec![Vec2::new(10.0, -1.0), Vec2::new(10.0, 6.0)],
vec![Vec2::new(11.0, 5.0), Vec2::new(-1.0, 5.0)],
vec![Vec2::new(0.0, 6.0), Vec2::new(0.0, -1.0)],
];
let l = enclosing_loop(&polys, Vec2::new(3.0, 3.0), 1e-9).unwrap();
assert!((shoelace(&l) - 50.0).abs() < 1e-9);
}
#[test]
fn open_shape_has_no_boundary() {
let polys = vec![vec![Vec2::new(0.0, 0.0), Vec2::new(10.0, 0.0), Vec2::new(10.0, 10.0)]];
assert!(enclosing_loop(&polys, Vec2::new(5.0, 2.0), 1e-9).is_none());
assert!(enclosing_loop(&[], Vec2::ZERO, 1e-9).is_none());
}
#[test]
fn innermost_of_nested() {
let polys = vec![square(0.0, 0.0, 10.0), square(2.0, 2.0, 2.0)];
let l = enclosing_loop(&polys, Vec2::new(3.0, 3.0), 1e-9).unwrap();
assert!((shoelace(&l) - 4.0).abs() < 1e-9);
let outer = enclosing_loop(&polys, Vec2::new(8.0, 8.0), 1e-9).unwrap();
assert!((shoelace(&outer) - 100.0).abs() < 1e-9);
}
fn lines_of(poly: &[Vec2]) -> Vec<Vec<Vec2>> {
poly.windows(2).map(<[Vec2]>::to_vec).collect()
}
#[test]
fn island_from_separate_lines() {
// Issue #106: a square drawn as four separate lines inside a rectangle is an island.
let mut polys = vec![square(0.0, 0.0, 20.0)];
polys.extend(lines_of(&square(5.0, 5.0, 5.0)));
let b = boundary_at(&polys, Vec2::new(2.0, 2.0), 1e-9).unwrap();
assert!((shoelace(&b.outer) - 400.0).abs() < 1e-9);
assert_eq!(b.islands.len(), 1);
let isl = &b.islands[0];
assert!((shoelace(&isl.outline) - 25.0).abs() < 1e-9, "counter-clockwise square");
assert_eq!(isl.outline.len(), 4);
assert_eq!(isl.sources, vec![1, 2, 3, 4]);
// The same square as one closed polyline: same island.
let b2 = boundary_at(&[square(0.0, 0.0, 20.0), square(5.0, 5.0, 5.0)], Vec2::new(2.0, 2.0), 1e-9).unwrap();
assert_eq!(b2.islands.len(), 1);
assert_eq!(b2.islands[0].sources, vec![1]);
// Picking inside the square gives the square, with no islands.
let inner = boundary_at(&polys, Vec2::new(7.0, 7.0), 1e-9).unwrap();
assert!((shoelace(&inner.outer) - 25.0).abs() < 1e-9);
assert!(inner.islands.is_empty());
}
#[test]
fn island_outline_ignores_dangling_ends_and_inner_edges() {
let mut polys = vec![square(0.0, 0.0, 20.0)];
polys.extend(lines_of(&square(5.0, 5.0, 5.0)));
polys.push(vec![Vec2::new(10.0, 10.0), Vec2::new(13.0, 12.0)]); // tail sticking out
polys.push(vec![Vec2::new(5.0, 5.0), Vec2::new(10.0, 10.0)]); // diagonal inside
let b = boundary_at(&polys, Vec2::new(2.0, 2.0), 1e-9).unwrap();
assert_eq!(b.islands.len(), 1);
assert!((shoelace(&b.islands[0].outline) - 25.0).abs() < 1e-9);
assert_eq!(b.islands[0].sources, vec![1, 2, 3, 4, 5, 6]);
}
#[test]
fn open_curves_and_attached_lines_are_not_islands() {
let polys = vec![
square(0.0, 0.0, 20.0),
// An open U inside the region.
vec![Vec2::new(5.0, 10.0), Vec2::new(5.0, 5.0), Vec2::new(10.0, 5.0), Vec2::new(10.0, 10.0)],
// A closed shape touching the outer boundary is part of the boundary, not an island.
vec![Vec2::new(20.0, 15.0), Vec2::new(15.0, 15.0), Vec2::new(15.0, 20.0)],
];
let b = boundary_at(&polys, Vec2::new(2.0, 2.0), 1e-9).unwrap();
assert!(b.islands.is_empty());
assert!((shoelace(&b.outer) - 375.0).abs() < 1e-9);
}
#[test]
fn nested_islands_and_outside_curves() {
let mut polys = vec![square(0.0, 0.0, 20.0)];
polys.extend(lines_of(&square(4.0, 4.0, 10.0)));
polys.extend(lines_of(&square(6.0, 6.0, 2.0)));
polys.extend(lines_of(&square(30.0, 0.0, 5.0))); // outside the region
let b = boundary_at(&polys, Vec2::new(2.0, 2.0), 1e-9).unwrap();
let mut areas: Vec<f64> = b.islands.iter().map(|i| shoelace(&i.outline)).collect();
areas.sort_by(f64::total_cmp);
assert_eq!(areas.len(), 2);
assert!((areas[0] - 4.0).abs() < 1e-9 && (areas[1] - 100.0).abs() < 1e-9);
// Between the island and the nested one: the island is the boundary, the nested square
// its island.
let mid = boundary_at(&polys, Vec2::new(5.0, 5.0), 1e-9).unwrap();
assert!((shoelace(&mid.outer) - 100.0).abs() < 1e-9);
assert_eq!(mid.islands.len(), 1);
}
#[test]
fn hostile_input_does_not_panic() {
let nan = Vec2::new(f64::NAN, 0.0);
let inf = Vec2::new(f64::INFINITY, 1.0);
let mut polys = vec![square(0.0, 0.0, 20.0), vec![nan, inf, Vec2::new(5.0, 5.0)], vec![Vec2::new(3.0, 3.0); 3]];
polys.extend(lines_of(&square(5.0, 5.0, 5.0)));
let b = boundary_at(&polys, Vec2::new(2.0, 2.0), 1e-9).unwrap();
assert_eq!(b.islands.len(), 1);
assert!(boundary_at(&polys, Vec2::new(f64::NAN, 2.0), 1e-9).is_none());
// Many islands stay bounded.
let mut many = vec![square(-1.0, -1.0, 200.0)];
for i in 0..80 {
for j in 0..80 {
many.push(square(f64::from(i) * 2.0, f64::from(j) * 2.0, 1.0));
}
}
let b = boundary_at(&many, Vec2::new(-0.5, -0.5), 1e-9).unwrap();
assert!(b.islands.len() <= MAX_ISLANDS);
}
#[test]
fn outer_sources_outline_and_interior_point() {
// A square cut by a diagonal: the triangle picked is made of the square and the diagonal;
// a far-away line takes no part.
let polys = vec![square(0.0, 0.0, 10.0), vec![Vec2::new(0.0, 0.0), Vec2::new(10.0, 10.0)], vec![Vec2::new(30.0, 0.0), Vec2::new(40.0, 0.0)]];
let b = boundary_at(&polys, Vec2::new(7.0, 2.0), 1e-9).unwrap();
assert_eq!(b.outer_sources, vec![0, 1]);
// Four separate lines: one outline; an open U and two separate squares have none.
let l = outline(&lines_of(&square(5.0, 5.0, 5.0)), 1e-9, 0.0).unwrap();
assert!((shoelace(&l) - 25.0).abs() < 1e-9);
assert!(outline(&[vec![Vec2::new(0.0, 0.0), Vec2::new(1.0, 0.0), Vec2::new(1.0, 1.0)]], 1e-9, 0.0).is_none());
assert!(outline(&[square(0.0, 0.0, 1.0), square(5.0, 5.0, 1.0)], 1e-9, 0.0).is_none());
// An L shape: the point is inside, also for a clockwise loop.
let l_shape =
vec![Vec2::new(0.0, 0.0), Vec2::new(10.0, 0.0), Vec2::new(10.0, 1.0), Vec2::new(1.0, 1.0), Vec2::new(1.0, 10.0), Vec2::new(0.0, 10.0)];
let p = interior_point(&l_shape).unwrap();
assert!(point_in_polygon(&l_shape, p));
let rev: Vec<Vec2> = l_shape.iter().rev().copied().collect();
assert!(point_in_polygon(&rev, interior_point(&rev).unwrap()));
assert!(interior_point(&[Vec2::ZERO, Vec2::new(1.0, 0.0)]).is_none());
assert!(interior_point(&[Vec2::new(f64::NAN, 0.0); 4]).is_none());
}
#[test]
fn gap_tolerance_closes_small_gaps() {
// Four lines with 0.5 gaps at two corners.
let polys = vec![
vec![Vec2::new(0.0, 0.0), Vec2::new(9.5, 0.0)],
vec![Vec2::new(10.0, 0.0), Vec2::new(10.0, 10.0)],
vec![Vec2::new(10.0, 10.0), Vec2::new(0.0, 10.0)],
vec![Vec2::new(0.0, 10.0), Vec2::new(0.0, 0.5)],
];
let p = Vec2::new(5.0, 5.0);
assert!(enclosing_loop(&polys, p, 1e-9).is_none());
assert!(enclosing_loop_gap(&polys, p, 1e-9, 0.25).is_none(), "gap larger than the tolerance");
let l = enclosing_loop_gap(&polys, p, 1e-9, 0.6).unwrap();
assert!((shoelace(&l) - 100.0).abs() < 1e-9, "{}", shoelace(&l));
let b = boundary_at_gap(&polys, p, 1e-9, 0.6).unwrap();
assert_eq!(b.outer_sources, vec![0, 1, 2, 3]);
assert!(outline(&polys, 1e-9, 0.6).is_some());
// Hostile gaps.
assert!(enclosing_loop_gap(&polys, p, 1e-9, f64::NAN).is_none());
assert!(enclosing_loop_gap(&polys, p, 1e-9, f64::INFINITY).is_none());
}
#[test]
fn line_ending_just_short_of_a_chord_is_joined_to_it() {
// A strip between two verticals and a flattened arc that bows below the ends of the
// verticals by 0.05 (the verticals stop on the true curve, the chord is lower).
let top = vec![Vec2::new(0.0, 10.0), Vec2::new(2.0, 10.0)];
let left = vec![Vec2::new(0.0, 10.0), Vec2::new(0.0, 0.05)];
let right = vec![Vec2::new(2.0, 10.0), Vec2::new(2.0, 0.05)];
let chord = vec![Vec2::new(-5.0, 0.0), Vec2::new(5.0, 0.0)];
let polys = vec![top, left, right, chord];
let p = Vec2::new(1.0, 5.0);
assert!(enclosing_loop(&polys, p, 1e-9).is_none());
let snapped = snap_ends(&polys, 0.1, 1e-9);
let l = enclosing_loop(&snapped, p, 1e-9).unwrap();
assert!((shoelace(&l) - 20.0).abs() < 1e-6, "{}", shoelace(&l));
// Too far away: left alone.
assert_eq!(snap_ends(&polys, 0.01, 1e-9), polys);
}
#[test]
#[expect(clippy::cast_precision_loss, reason = "The test is capped at MAX_SEGMENTS (60,000), so every generated coordinate is exact as f64.")]
fn snap_ends_skips_input_over_the_segment_cap() {
let mut polys: Vec<Vec<Vec2>> = (0..=MAX_SEGMENTS)
.map(|i| {
let x = i as f64 * 10.0;
vec![Vec2::new(x, 0.0), Vec2::new(x, 1.0)]
})
.collect();
polys.push(vec![Vec2::new(0.0, 1.05), Vec2::new(5.0, 1.05)]);
assert_eq!(snap_ends(&polys, 0.1, 1e-9), polys);
}
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.