GitCorner

Code

ossartcraftvectorcraft🌐
2bc41aeb8602
use vectorcraft_pathops::addons::pathtools as pt;

use super::common::{dist_to_polyline, ids_json, path_mut, path_of, points_param, poly_bounds, subpath_len, target_paths};
use super::{
    Anchor, BezPath, CubicBez, NodeId, ParamCurve, ParamCurveNearest, PathData, Point, Rect, Result, Session, SimplifyOptions, SubPath, Value, json,
    number_or, po,
};

// ---------- Smooth ----------

/// The spread (points) of the Gaussian the Smooth tool smooths a path along its length with before
/// refitting it, as a share of the tool's reach: a third, so each point is averaged with the stretch
/// of path within the reach on either side of it. VectorCraft's own value.
const SMOOTH_SPREAD: f64 = 1.0 / 3.0;

/// The degrees by which a path must turn at an anchor, and over the tool's reach and twice its reach
/// on either side of it, for the Smooth tool to keep the anchor as a corner ([`smooth_corners`]): a
/// turn of more than 57.5°, an angle inside the corner of less than 122.5°. VectorCraft's own value,
/// the same on every drag and at any Fidelity.
const SMOOTH_CORNER_DEG: f64 = 57.5;

/// Most pieces a curved segment is cut into evenly, and most more pieces near each of its ends, to
/// measure lengths along it in [`smooth_corners`].
const CORNER_PIECES: usize = 64;

/// The control polygon's length of `c`, which is at least its length.
fn polygon_len(c: CubicBez) -> f64 {
    c.p0.distance(c.p1) + c.p1.distance(c.p2) + c.p2.distance(c.p3)
}

/// The places (0 to 1, in order, without 0 and with 1) on the curved segment `c` that
/// [`smooth_corners`] measures it at: up to [`CORNER_PIECES`] evenly spaced, and near each end, over
/// a stretch at least three times `reach` long where the segment is that long, up to as many more
/// that are no more than `reach` / 8 apart along the control polygon, and as many again in each
/// stretch twice as long after it until the pieces reach three times `reach`. The turns over `reach` and
/// twice `reach` from an anchor are then measured along the curve however long the segment is.
fn corner_places(c: CubicBez, reach: f64) -> Vec<f64> {
    let piece = reach / 8.0;
    let pieces = |len: f64| if piece > 0.0 { (len / piece).ceil().clamp(1.0, CORNER_PIECES as f64) as usize } else { 1 };
    let k = pieces(polygon_len(c)).max(4);
    let mut places: Vec<f64> = (1..=k).map(|j| j as f64 / k as f64).collect();
    if piece > 0.0 {
        for from_start in [true, false] {
            // The stretch from the end: halved until its control polygon is at most six reaches long.
            let first = 1.0 / k as f64;
            let mut t = first;
            let part = |t: f64| if from_start { c.subsegment(0.0..t) } else { c.subsegment(1.0 - t..1.0) };
            for _ in 0..60 {
                if polygon_len(part(t)) <= 6.0 * reach {
                    break;
                }
                t /= 2.0;
            }
            let side = |u: f64| if from_start { u } else { 1.0 - u };
            let m = pieces(polygon_len(part(t)));
            let mut fine: Vec<f64> = (1..=m).map(|j| t * j as f64 / m as f64).collect();
            // Then the stretches twice as long in turn, cut as finely, up to the first even place, until
            // the pieces reach three reaches from the end, so twice the reach is measured along the curve
            // where a handle that does not reach out makes the curve start more slowly than its polygon.
            let mut covered = 0.0;
            let mut at = c.eval(side(0.0));
            for u in &fine {
                let q = c.eval(side(*u));
                covered += at.distance(q);
                at = q;
            }
            let (mut from, mut levels) = (t, 0);
            while covered < 3.0 * reach && from < first && levels < 60 {
                let to = (2.0 * from).min(first);
                let piece_len = polygon_len(if from_start { c.subsegment(from..to) } else { c.subsegment(1.0 - to..1.0 - from) });
                let m = pieces(piece_len);
                for j in 1..=m {
                    let u = from + (to - from) * j as f64 / m as f64;
                    let q = c.eval(side(u));
                    covered += at.distance(q);
                    at = q;
                    fine.push(u);
                }
                (from, levels) = (to, levels + 1);
            }
            places.extend(fine.into_iter().map(side));
        }
    }
    places.retain(|u| *u > 0.0 && *u <= 1.0);
    places.sort_by(f64::total_cmp);
    places.dedup();
    places
}

/// The degrees between the directions `u` and `v`, `None` when either has no length or is not a
/// number.
fn turn_between(u: kurbo::Vec2, v: kurbo::Vec2) -> Option<f64> {
    let (lu, lv) = (u.hypot(), v.hypot());
    if !(lu.is_finite() && lv.is_finite() && lu > 1e-12 && lv > 1e-12) {
        return None;
    }
    let deg = u.cross(v).atan2(u.dot(v)).abs().to_degrees();
    deg.is_finite().then_some(deg)
}

/// Which anchors of `anchors` (a closed path when `closed`) the Smooth tool keeps as corners: those
/// where the path turns by more than [`SMOOTH_CORNER_DEG`] at the anchor itself, between the
/// direction it arrives along and the one it leaves along, and also over `reach` and over twice
/// `reach` on either side of it, between the direction from the point that far back along the path
/// to the anchor and the direction from the anchor to the point that far ahead. The points are taken
/// no farther than the ends of an open path, and no more than an eighth of the way round a closed
/// one. A jag or a bump smaller than the reach turns sharply at its anchor but not over twice the
/// reach, and an anchor in the middle of a tight curve turns over the reach but not at the anchor, so
/// neither is kept. An open path's first and last anchors are never corners.
fn smooth_corners(anchors: &[Anchor], closed: bool, reach: f64) -> Vec<bool> {
    let n = anchors.len();
    let mut corners = vec![false; n];
    if n < 2 || (n < 3 && !closed) {
        return corners;
    }
    // The distances on either side the turn is measured over: one reach and two, no more than an
    // eighth of the way round a closed path. Over that much of a circle the path turns by 45°, so a
    // loop shorter than the reach is not all corners, while a square's or a triangle's corners still are.
    let mut spans = [reach, 2.0 * reach];
    // The lengths along the path ahead and back, measured once when an anchor needs them.
    let (mut ahead, mut back) = (None, None);
    if closed {
        let total = ahead.get_or_insert_with(|| walk_blocks(anchors, closed, true, reach)).first().map_or(0.0, |lens| lens.iter().take(n).sum());
        if !(total.is_finite() && total > 0.0) {
            return corners;
        }
        spans = spans.map(|r| r.min(total / 8.0));
    }
    for (i, flag) in corners.iter_mut().enumerate() {
        if !closed && (i == 0 || i == n - 1) {
            continue;
        }
        let (prev, a, next) = (anchors[(i + n - 1) % n], anchors[i], anchors[(i + 1) % n]);
        let arrive = [a.p - a.h_in, a.p - prev.h_out, a.p - prev.p].into_iter().find(|d| d.hypot() > 1e-12).unwrap_or_default();
        let leave = [a.h_out - a.p, next.h_in - a.p, next.p - a.p].into_iter().find(|d| d.hypot() > 1e-12).unwrap_or_default();
        if !turn_between(arrive, leave).is_some_and(|t| t > SMOOTH_CORNER_DEG) {
            continue;
        }
        let back = back.get_or_insert_with(|| walk_blocks(anchors, closed, false, reach));
        let [Some(back_near), Some(back_far)] = spans.map(|r| point_along(anchors, closed, (i, false), r, back, reach)) else { continue };
        let ahead = ahead.get_or_insert_with(|| walk_blocks(anchors, closed, true, reach));
        let [Some(ahead_near), Some(ahead_far)] = spans.map(|r| point_along(anchors, closed, (i, true), r, ahead, reach)) else { continue };
        *flag = [(back_near, ahead_near, spans[0]), (back_far, ahead_far, spans[1])]
            .into_iter()
            .all(|(back, ahead, r)| r <= 0.0 || turn_between(a.p - back, ahead - a.p).is_some_and(|t| t > SMOOTH_CORNER_DEG));
    }
    corners
}

/// The lengths [`walk`] measures along the segments of `anchors`, in the order a walk ahead
/// (`forward`) or back passes them, twice round, starting at the first anchor ahead or the last
/// anchor back, and added up in blocks: element `l` holds the lengths of each run of 2^`l`
/// segments that starts at a multiple of 2^`l`. Each block adds up only its own segments, so a short
/// stretch keeps its length next to very long ones. The segment past an open path's end has no
/// length.
fn walk_blocks(anchors: &[Anchor], closed: bool, forward: bool, reach: f64) -> Vec<Vec<f64>> {
    let n = anchors.len();
    let lens: Vec<f64> =
        (0..n).map(|k| walk(anchors, closed, (if forward { k } else { n - 1 - k }, forward), [f64::INFINITY; 2], reach, 1).1).collect();
    let mut blocks = vec![(0..2 * n).map(|k| lens[k % n]).collect::<Vec<f64>>()];
    while let Some(last) = blocks.last().filter(|b| b.len() > 1) {
        let next = last.as_chunks::<2>().0.iter().map(|[a, b]| a + b).collect();
        blocks.push(next);
    }
    blocks
}

/// The point `dist` along the path `anchors` from anchor `from.0`, ahead when `from.1` and back
/// otherwise, as [`walk`] finds it: an open path's end for a distance beyond the end, and `None`
/// when a length is not a number or is too large to add. The walk skips whole blocks of `blocks`
/// ([`walk_blocks`] in the same direction) that end no more than `dist` along the path, so a path of
/// very many short segments is not walked one segment at a time from each anchor.
fn point_along(anchors: &[Anchor], closed: bool, from: (usize, bool), dist: f64, blocks: &[Vec<f64>], reach: f64) -> Option<Point> {
    let (n, (i, forward)) = (anchors.len(), from);
    let start = if forward { i } else { n - 1 - i };
    let end = start
        + if closed {
            n
        } else if forward {
            n - 1 - i
        } else {
            i
        };
    let (mut pos, mut gone) = (start, 0.0);
    // The largest block that starts at `pos`, stays within the walk and ends within `dist`, until
    // none does; a block whose length is not a number is never skipped.
    while let Some((size, len)) = blocks.iter().enumerate().rev().find_map(|(l, lens)| {
        let size = 1usize << l;
        let len = lens.get(pos >> l).copied()?;
        (pos % size == 0 && pos + size <= end && gone + len <= dist).then_some((size, len))
    }) {
        pos += size;
        gone += len;
    }
    let at = if forward { pos % n } else { n - 1 - pos % n };
    walk(anchors, closed, (at, forward), [(dist - gone).max(0.0); 2], reach, n).0[0]
}

/// A walk along the path `anchors` from anchor `from.0`, ahead when `from.1` and back otherwise,
/// past no more than `segments` segments, measured along the lines between each curved segment's
/// points at [`corner_places`]. It gives the points at the distances `to` (in order, the nearer
/// first), an open path's end for one beyond the end, and `None` for one it did not reach within
/// `segments` segments, and the length it walked. Both points are `None` when it meets a length that
/// is not a number or is too large to add, and the length is then infinite.
fn walk(anchors: &[Anchor], closed: bool, from: (usize, bool), to: [f64; 2], reach: f64, segments: usize) -> ([Option<Point>; 2], f64) {
    let (n, forward) = (anchors.len(), from.1);
    let Some(mut here) = anchors.get(from.0).map(|a| a.p) else { return ([None; 2], 0.0) };
    let (mut at, mut gone) = (from.0, 0.0);
    let mut found: [Option<Point>; 2] = [None; 2];
    let mut at_end = false;
    'segments: for _ in 0..segments {
        let next = match (forward, closed) {
            (true, _) if at + 1 < n => at + 1,
            (true, true) => 0,
            (false, _) if at > 0 => at - 1,
            (false, true) => n - 1,
            _ => {
                at_end = true;
                break;
            }
        };
        let (a, b) = (anchors[at], anchors[next]);
        let c = if forward { CubicBez::new(a.p, a.h_out, b.h_in, b.p) } else { CubicBez::new(a.p, a.h_in, b.h_out, b.p) };
        let places = if c.p1 == c.p0 && c.p2 == c.p3 { vec![1.0] } else { corner_places(c, reach) };
        for u in places {
            let q = if u >= 1.0 { c.p3 } else { c.eval(u) };
            let d = here.distance(q);
            if !(d.is_finite() && (gone + d).is_finite()) {
                return ([None; 2], f64::INFINITY);
            }
            for (slot, &dist) in found.iter_mut().zip(&to) {
                if slot.is_none() && gone + d >= dist {
                    let t = if d > 0.0 { ((dist - gone) / d).clamp(0.0, 1.0) } else { 1.0 };
                    *slot = Some(here.lerp(q, t));
                }
            }
            gone += d;
            here = q;
            if found.iter().all(Option::is_some) {
                break 'segments;
            }
        }
        at = next;
    }
    // An open path that ends after the last segment walked ends there too.
    if !closed && at == if forward { n - 1 } else { 0 } {
        at_end = true;
    }
    (found.map(|p| p.or(at_end.then_some(here))), gone)
}

/// Whether `a` and `b` are the same anchors, to within a rounding error.
fn same_anchors(a: &[Anchor], b: &[Anchor]) -> bool {
    let near = |p: Point, q: Point| p.distance(q) <= 1e-9;
    a.len() == b.len() && a.iter().zip(b).all(|(x, y)| near(x.p, y.p) && near(x.h_in, y.h_in) && near(x.h_out, y.h_out))
}

/// [`refit_run`] of the open run `anchors` cut at its anchors marked in `corners`: each part between
/// two corners is smoothed and refitted on its own, so each corner keeps its place and the direction
/// the path arrives and leaves along. `free` applies to the run's first and last anchors only.
fn refit_split(anchors: &[Anchor], corners: &[bool], tol: f64, sigma: f64, free: [bool; 2]) -> Vec<Anchor> {
    let last = anchors.len().saturating_sub(1);
    let mut cuts: Vec<usize> = (1..last).filter(|&i| corners.get(i).copied().unwrap_or(false)).collect();
    if cuts.is_empty() {
        return refit_run(anchors, tol, sigma, free);
    }
    cuts.insert(0, 0);
    cuts.push(last);
    let mut out: Vec<Anchor> = Vec::with_capacity(anchors.len());
    for w in cuts.windows(2) {
        let (a, b) = (w[0], w[1]);
        let part = refit_run(&anchors[a..=b], tol, sigma, [free[0] && a == 0, free[1] && b == last]);
        match out.pop() {
            // The corner ends one part and starts the next: it keeps its place, and takes the handle
            // in from the part before and the handle out from the part after.
            Some(end) => {
                let mut rest = part.into_iter();
                if let Some(start) = rest.next() {
                    out.push(Anchor::with_handles(anchors[a].p, end.h_in, start.h_out));
                }
                out.extend(rest);
            }
            None => out.extend(part),
        }
    }
    out
}

/// The options the Smooth tool refits with: the path smoothed along its length by a Gaussian of
/// spread `sigma` (none at 0), then refitted within `tol` of that and within twice the distance the
/// smoothing moved it. The tool cuts the path at its corners first ([`smooth_corners`]), so within a
/// part the refit keeps a corner only where the path turns back on itself. `free` says whether
/// the start and the end of the stretch refitted are ends of an open path, whose direction then
/// follows the smoothed path within the reach rather than the first or last segment.
fn refit_options(tol: f64, sigma: f64, free: [bool; 2]) -> SimplifyOptions {
    SimplifyOptions {
        tolerance: tol,
        corner_angle_deg: 179.0,
        straight_lines: false,
        smooth: sigma,
        smooth_moved_only: true,
        free_start: free[0],
        free_end: free[1],
    }
}

/// Smooth and refit the anchors of an open run `a[lo..=hi]` keeping its end points and outer handles.
/// `free` says whether its first and last anchors are ends of an open path: the curve leaving or
/// arriving at such an end can turn.
fn refit_run(anchors: &[Anchor], tol: f64, sigma: f64, free: [bool; 2]) -> Vec<Anchor> {
    let piece = PathData::single(SubPath::new(anchors.to_vec(), false));
    let fitted = po::simplify_with(&piece, &refit_options(tol, sigma, free));
    let Some(mut out) = fitted.subpaths.into_iter().next().map(|s| s.anchors).filter(|a| a.len() >= 2) else { return anchors.to_vec() };
    let (f, l) = (anchors[0], anchors[anchors.len() - 1]);
    let last = out.len() - 1;
    out[0].p = f.p;
    out[0].h_in = f.h_in;
    out[last].p = l.p;
    out[last].h_out = l.h_out;
    for a in &mut out {
        *a = Anchor::with_handles(a.p, a.h_in, a.h_out);
    }
    out.into_vec()
}

/// Distance (points) from an anchor within which a smoothed closed path starts at that anchor
/// instead of at a new one split in beside it.
const START_SNAP: f64 = 1e-3;

/// Distance (points) within which two points of a smoothed closed path count as equally near its
/// old start.
const START_TIE: f64 = 1e-6;

/// Where `p` lies along the closed `orig` from its first anchor: the segment index and parameter of
/// the point of `orig` nearest `p`, the first such point in its order. Sorts after every finite place
/// when there is none.
fn place_along(orig: &SubPath, p: Point) -> (usize, f64) {
    let mut best: Option<(f64, usize, f64)> = None;
    for j in 0..orig.anchors.len() {
        let hit = orig.segment(j).nearest(p, 1e-9);
        if hit.distance_sq.is_finite() && hit.t.is_finite() && best.is_none_or(|(d, ..)| hit.distance_sq < d) {
            best = Some((hit.distance_sq, j, hit.t));
        }
    }
    best.map_or((usize::MAX, f64::INFINITY), |(_, j, t)| (j, t))
}

/// The closed `sp` started at the point on it nearest `start`: at the anchor there, or at a new
/// anchor split into the segment there, which leaves the outline as it is. Of points equally near
/// `start`, the one earliest along `orig` (the path before smoothing) from its first anchor is used,
/// then the first in `sp`'s order. An open `sp`, or one with no segment or no finite nearest point,
/// is returned as it is.
fn start_nearest(mut sp: SubPath, start: Point, orig: &SubPath) -> SubPath {
    let n = sp.anchors.len();
    if !sp.closed || n < 2 {
        return sp;
    }
    // (distance, place along `orig` once a tie needs it, segment of `sp`, parameter)
    type Best = (f64, Option<(usize, f64)>, usize, f64);
    let mut best: Option<Best> = None;
    for i in 0..n {
        let c = sp.segment(i);
        let hit = c.nearest(start, 1e-9);
        if !hit.distance_sq.is_finite() || !hit.t.is_finite() {
            continue;
        }
        let d = hit.distance_sq.sqrt();
        match &mut best {
            None => best = Some((d, None, i, hit.t)),
            Some((bd, bplace, bi, bt)) if (d - *bd).abs() <= START_TIE => {
                let held = *bplace.get_or_insert_with(|| place_along(orig, sp.segment(*bi).eval(*bt)));
                let place = place_along(orig, c.eval(hit.t));
                if place.0 < held.0 || (place.0 == held.0 && place.1 < held.1) {
                    best = Some((d, Some(place), i, hit.t));
                }
            }
            Some((bd, ..)) if d < *bd => best = Some((d, None, i, hit.t)),
            Some(_) => {}
        }
    }
    let Some((_, _, i, t)) = best else { return sp };
    let c = sp.segment(i);
    let at = c.eval(t);
    let first = if at.distance(c.p0) <= START_SNAP {
        i
    } else if at.distance(c.p3) <= START_SNAP {
        (i + 1) % n
    } else {
        let mid = if sp.segment_is_line(i) {
            Anchor::corner(at)
        } else {
            let (l, r) = (c.subsegment(0.0..t), c.subsegment(t..1.0));
            sp.anchors[i].h_out = l.p1;
            sp.anchors[(i + 1) % n].h_in = r.p2;
            Anchor::with_handles(at, l.p2, r.p1)
        };
        sp.anchors.insert(i + 1, mid);
        i + 1
    };
    sp.anchors.rotate_left(first);
    sp
}

/// Pieces of curve that one Smooth drag measures against the drag while it searches the segments
/// under it ([`reach_samples`]), shared equally by the curved segments that come within its reach,
/// each of which gets at least one: enough to search 300,000 pt of curve within the default reach
/// of the drag.
const MAX_REACH_PIECES: usize = 1 << 17;

/// The box around the control points of `s`, which holds all of `s`.
fn control_box(s: CubicBez) -> Rect {
    Rect::from_points(s.p0, s.p1).union_pt(s.p2).union_pt(s.p3)
}

/// The stretches of the drag `pts` (stretch `k` runs from `pts[k]` to the next point; a drag of one
/// point has the point as its only stretch).
fn drag_stretches(pts: &[Point]) -> Vec<usize> {
    (0..pts.len().saturating_sub(1).max(1)).collect()
}

/// The stretches of the drag `pts` among `of` whose bounds come within `radius` of `r` on both
/// axes: every stretch within `radius` of a point in `r`, and perhaps a few more.
fn stretches_near(pts: &[Point], of: &[usize], r: Rect, radius: f64) -> Vec<usize> {
    let r = r.inflate(radius, radius);
    of.iter()
        .copied()
        .filter(|&k| {
            let Some(&a) = pts.get(k) else { return false };
            let b = pts.get(k + 1).copied().unwrap_or(a);
            a.x.min(b.x) <= r.x1 && a.x.max(b.x) >= r.x0 && a.y.min(b.y) <= r.y1 && a.y.max(b.y) >= r.y0
        })
        .collect()
}

/// The distance from `q` to the nearest of the stretches `of` of the drag `pts`.
fn dist_to_stretches(pts: &[Point], of: &[usize], q: Point) -> f64 {
    of.iter()
        .filter_map(|&k| {
            let a = *pts.get(k)?;
            Some(dist_to_polyline(&[a, pts.get(k + 1).copied().unwrap_or(a)], q))
        })
        .fold(f64::INFINITY, f64::min)
}

/// The place on `s` (0 to 1) nearest to the stretches `of` of the drag `pts`, and its distance from
/// them. For each stretch the nearest place is at one of the stretch's ends, at an end of `s`, or
/// where `s` crosses the stretch's line or stops moving toward or away from it.
fn nearest_to_stretches(s: CubicBez, pts: &[Point], of: &[usize]) -> (f64, f64) {
    let (c1, c2, c3) = (3.0 * (s.p1 - s.p0), 3.0 * ((s.p2 - s.p1) - (s.p1 - s.p0)), (s.p3 - s.p0) - 3.0 * (s.p2 - s.p1));
    let mut best = (0.5, f64::INFINITY);
    for &k in of {
        let Some(&a) = pts.get(k) else { continue };
        let b = pts.get(k + 1).copied().unwrap_or(a);
        let mut places: Vec<f64> = vec![0.0, 1.0, s.nearest(a, 1e-9).t, s.nearest(b, 1e-9).t];
        let d = b - a;
        if d.hypot() > 1e-12 {
            let (f0, f1, f2, f3) = (d.cross(s.p0 - a), d.cross(c1), d.cross(c2), d.cross(c3));
            places.extend(kurbo::common::solve_cubic(f0, f1, f2, f3));
            places.extend(kurbo::common::solve_quadratic(f1, 2.0 * f2, 3.0 * f3));
        }
        for u in places.into_iter().filter(|u| (0.0..=1.0).contains(u)) {
            let dist = dist_to_polyline(&[a, b], s.eval(u));
            if dist < best.1 {
                best = (u, dist);
            }
        }
    }
    best
}

/// How many curved segments of `pd` may come within `radius` of the drag `pts`.
fn segments_in_reach(pd: &PathData, pts: &[Point], radius: f64) -> usize {
    let all = drag_stretches(pts);
    pd.subpaths
        .iter()
        .map(|sp| {
            (0..sp.segment_count())
                .filter(|&i| {
                    !vectorcraft_tools::draw2::segment_is_straight(sp, i) && !stretches_near(pts, &all, control_box(sp.segment(i)), radius).is_empty()
                })
                .count()
        })
        .sum()
}

/// Samples along the part of `c` from `t0` to `t1`, in order: (t, whether the point there is within
/// `radius` of the stretches `of` of the drag `pts`). A piece no stretch comes near gives one sample
/// out of reach; the others are halved until their control polygon is no longer than half the
/// reach, or until `budget` pieces have been measured, and then give one sample: in reach at the
/// piece's middle or at its place nearest the drag when either is in reach, otherwise out of reach
/// at its middle. Each piece measures only the stretches near
/// the piece it was cut from, so a long drag along a long curve costs about one pass over the drag
/// per halving, plus the stretches near each piece.
fn reach_samples(c: CubicBez, (t0, t1): (f64, f64), (pts, of): (&[Point], &[usize]), radius: f64, budget: &mut usize, out: &mut Vec<(f64, bool)>) {
    *budget = budget.saturating_sub(1);
    let s = c.subsegment(t0..t1);
    let mid = 0.5 * (t0 + t1);
    let near = stretches_near(pts, of, control_box(s), radius);
    if near.is_empty() {
        out.push((mid, false));
        return;
    }
    let len = s.p0.distance(s.p1) + s.p1.distance(s.p2) + s.p2.distance(s.p3);
    if len <= (radius / 2.0).max(1e-3) || *budget == 0 || mid <= t0 || mid >= t1 {
        // The piece's middle, or the place on it nearest the drag when the middle is out of reach.
        let sample = if dist_to_stretches(pts, &near, c.eval(mid)) <= radius {
            (mid, true)
        } else {
            let (u, dist) = nearest_to_stretches(s, pts, &near);
            if dist <= radius { (t0 + u * (t1 - t0), true) } else { (mid, false) }
        };
        out.push(sample);
        return;
    }
    reach_samples(c, (t0, mid), (pts, &near), radius, budget, out);
    reach_samples(c, (mid, t1), (pts, &near), radius, budget, out);
}

/// `sp` cut where the reach `radius` of the drag `pts` crosses its curved segments, and whether each
/// anchor of the result is in reach. An anchor in reach is added in the middle of each stretch of a
/// segment in reach that does not run on from one of the segment's anchors in reach, and an anchor
/// out of reach in the middle of each stretch out of reach between two stretches in reach, so that a
/// stretch in reach is smoothed even when the segment's anchors are not, and the stretches between
/// stay as they are. A segment is searched no more than half the reach apart where it comes within
/// the reach of the drag ([`reach_samples`]), measuring up to `share` pieces of each segment.
fn mark_reached(sp: &SubPath, pts: &[Point], radius: f64, share: usize) -> (SubPath, Vec<bool>) {
    let near = |q: Point| dist_to_polyline(pts, q) <= radius;
    let n = sp.anchors.len();
    let marked: Vec<bool> = sp.anchors.iter().map(|a| near(a.p)).collect();
    let mut places = vec![];
    let all = drag_stretches(pts);
    for i in 0..sp.segment_count() {
        if vectorcraft_tools::draw2::segment_is_straight(sp, i) {
            continue;
        }
        let c = sp.segment(i);
        let (mut samples, mut budget) = (vec![], share);
        reach_samples(c, (0.0, 1.0), (pts, &all), radius, &mut budget, &mut samples);
        // Stretches of samples alike, in order: (in reach, first, last).
        let mut runs: Vec<(bool, usize, usize)> = vec![];
        for (k, s) in samples.iter().enumerate() {
            match runs.last_mut() {
                Some(r) if r.0 == s.1 => r.2 = k,
                _ => runs.push((s.1, k, k)),
            }
        }
        let last = samples.len().saturating_sub(1);
        let (start, end) = (marked[i], marked[(i + 1) % n]);
        for (j, &(reached, first, to)) in runs.iter().enumerate() {
            let mid = samples[(first + to) / 2].0;
            let joined = (first == 0 && start) || (to == last && end);
            if reached && !joined {
                places.push((i, mid));
            }
            // A gap with reach on both sides: the segment's anchor or a stretch on each side.
            let before = if j == 0 { start } else { runs[j - 1].0 };
            let after = runs.get(j + 1).map_or(end, |r| r.0);
            if !reached && before && after {
                places.push((i, mid));
            }
        }
    }
    // A place on one of the segment's ends would name that anchor rather than add one.
    places.retain(|(_, t)| (1e-5..=1.0 - 1e-5).contains(t));
    if places.is_empty() {
        return (sp.clone(), marked);
    }
    let (out, added) = pt::insert_at(sp, &places);
    // The anchors already there keep their marks. A new anchor split off at a sample in reach can
    // land a rounding error farther away than the sample.
    let mut kept = marked.into_iter();
    let marked = out
        .anchors
        .iter()
        .enumerate()
        .map(|(j, a)| if added.contains(&j) { dist_to_polyline(pts, a.p) <= radius + 1e-9 * radius.max(1.0) } else { kept.next().unwrap_or(false) })
        .collect();
    (out, marked)
}

/// `sp` with the anchors in the drag's reach smoothed and refitted, `None` when none are in reach.
/// A closed path whose first anchor is in reach starts at the point of the refitted path nearest
/// that anchor's place (VectorCraft's own rule).
fn smooth_subpath(sp: &SubPath, pts: &[Point], radius: f64, share: usize, tol: f64, sigma: f64) -> Option<SubPath> {
    if sp.anchors.len() < 2 {
        return None;
    }
    let near = &|q: Point| dist_to_polyline(pts, q) <= radius;
    // A drag along a segment smooths it even when its anchors are out of reach.
    let (sp, marked) = mark_reached(sp, pts, radius, share);
    let sp = &sp;
    if !marked.iter().any(|m| *m) {
        return None;
    }
    if sp.closed {
        let start = sp.anchors[0].p;
        let Some(k) = marked.iter().position(|m| !m) else {
            let corners = smooth_corners(&sp.anchors.contiguous(), true, radius);
            let Some(c) = corners.iter().position(|c| *c) else {
                // Everything is in range and nothing is a corner: smooth the whole closed path,
                // across its start too.
                let f = po::simplify_with(&PathData::single(sp.clone()), &refit_options(tol, sigma, [false; 2]));
                return f.subpaths.into_iter().next().map(|r| start_nearest(r, start, sp));
            };
            // Cut the path open at a corner, which then ends the last part as well as starting the first.
            let mut open = sp.anchors.to_vec();
            open.rotate_left(c);
            let mut cut = corners;
            cut.rotate_left(c);
            open.push(open[0]);
            cut.push(true);
            let mut res = refit_split(&open, &cut, tol, sigma, [false; 2]);
            if same_anchors(&res, &open) {
                return None;
            }
            let l = res.pop()?;
            if let Some(r0) = res.first_mut() {
                *r0 = Anchor::with_handles(r0.p, l.h_in, r0.h_out);
            }
            // The path starts where it did when the refit keeps an anchor there, and otherwise at its
            // point nearest there.
            return Some(start_nearest(SubPath::new(res, true), start, sp));
        };
        // Rotate so an untouched anchor comes first, duplicate it at the end and treat as open.
        let mut open = sp.anchors.to_vec();
        open.rotate_left(k);
        let mut m = marked.clone();
        m.rotate_left(k);
        open.push(open[0]);
        m.push(false);
        let mut res = smooth_open(&open, &m, near, tol, sigma, radius, false);
        if same_anchors(&res, &open) {
            return None;
        }
        let l = res.pop()?;
        if let Some(r0) = res.first_mut() {
            r0.h_in = l.h_in;
        }
        // With k = 0 the first anchor is out of reach and still starts the result.
        let res = SubPath::new(res, true);
        return Some(if k == 0 { res } else { start_nearest(res, start, sp) });
    }
    let anchors = sp.anchors.contiguous();
    let res = smooth_open(&anchors, &marked, near, tol, sigma, radius, true);
    (!same_anchors(&res, &anchors)).then(|| SubPath::new(res, false))
}

/// The segment `c`, which ends in the drag's reach (`near`) and starts outside it, split where it
/// enters the reach: the part outside, then the part in reach. `None` when no more than a sliver
/// is outside.
fn split_at_reach(c: CubicBez, near: &dyn Fn(Point) -> bool) -> Option<(CubicBez, CubicBez)> {
    const STEPS: u32 = 32;
    let step = 1.0 / f64::from(STEPS);
    // Back from the end in reach to the first sample outside, then halving to the crossing.
    let outside = (1..=STEPS).map(|i| 1.0 - f64::from(i) * step).find(|t| !near(c.eval(*t)))?;
    let (mut lo, mut hi) = (outside, outside + step);
    for _ in 0..20 {
        let mid = (lo + hi) / 2.0;
        if near(c.eval(mid)) {
            hi = mid;
        } else {
            lo = mid;
        }
    }
    // A straight segment's parts stay straight, their handles on their ends.
    let straight = c.p1 == c.p0 && c.p2 == c.p3;
    let part = |range| {
        let s = c.subsegment(range);
        if straight { CubicBez::new(s.p0, s.p0, s.p3, s.p3) } else { s }
    };
    (hi > 0.02).then(|| (part(0.0..hi), part(hi..1.0)))
}

/// `anchors` with each run of `marked` ones smoothed by a Gaussian of spread `sigma` and refitted
/// within `tol`, together with the stretch of the segments leading into the run that is in the
/// drag's reach (`near`): a short drag smooths what is under it, and the rest of a long segment next
/// to it stays as it was (#1512). With `open`, `anchors` are an open path, and the curve at its first
/// or last anchor turns with the smoothing when a run's refit reaches that anchor; a run's other ends,
/// and those of the open run a closed path is cut into, keep their direction. Each run keeps its
/// corners ([`smooth_corners`] within `radius`, the tool's reach, measured within the run), and a run
/// whose refit changes nothing stays as it was.
fn smooth_open(anchors: &[Anchor], marked: &[bool], near: &dyn Fn(Point) -> bool, tol: f64, sigma: f64, radius: f64, open: bool) -> Vec<Anchor> {
    let n = anchors.len();
    let mut runs = vec![];
    let mut i = 0;
    while i < n {
        if marked[i] {
            let a = i;
            while i + 1 < n && marked[i + 1] {
                i += 1;
            }
            runs.push((a, i));
        }
        i += 1;
    }
    let mut out = anchors.to_vec();
    for (a, b) in runs.into_iter().rev() {
        let lo = a.saturating_sub(1);
        let hi = (b + 1).min(n - 1);
        if hi == lo {
            continue;
        }
        let mut piece = out[lo..=hi].to_vec();
        // The anchors outside the reach, kept with the part of their segment that is outside.
        let (mut head, mut tail) = (None, None);
        if hi > b
            && let [.., inner, outer] = piece.as_mut_slice()
            && let Some((far, reach)) = split_at_reach(CubicBez::new(outer.p, outer.h_in, inner.h_out, inner.p), near)
        {
            inner.h_out = reach.p2;
            tail = Some(Anchor { h_in: far.p1, ..*outer });
            *outer = Anchor::with_handles(far.p3, reach.p1, far.p2);
        }
        if lo < a
            && let [outer, inner, ..] = piece.as_mut_slice()
            && let Some((far, reach)) = split_at_reach(CubicBez::new(outer.p, outer.h_out, inner.h_in, inner.p), near)
        {
            inner.h_in = reach.p2;
            head = Some(Anchor { h_out: far.p1, ..*outer });
            *outer = Anchor::with_handles(far.p3, far.p2, reach.p1);
        }
        let free = [open && lo == 0 && head.is_none(), open && hi == n - 1 && tail.is_none()];
        let corners = smooth_corners(&piece, false, radius);
        let new = refit_split(&piece, &corners, tol, sigma, free);
        if same_anchors(&new, &piece) {
            continue;
        }
        out.splice(lo..=hi, head.into_iter().chain(new).chain(tail));
    }
    out
}

pub(super) fn smooth_region(s: &mut Session, p: &Value) -> Result<Value> {
    const C: &str = "path.smoothRegion";
    let pts = points_param(p, "points", C)?;
    let radius = number_or(p, "radius", 12.0, C)?.max(0.0);
    let tol = number_or(p, "fidelity", 2.5, C)?.clamp(vectorcraft_tools::draw2::SMOOTH_MIN_TOLERANCE, vectorcraft_tools::draw2::SMOOTH_MAX_TOLERANCE);
    let sigma = radius * SMOOTH_SPREAD;
    let st = s.doc()?;
    let mut plan = vec![];
    let (mut before, mut after) = (0, 0);
    let mut paths = vec![];
    for id in target_paths(&st.doc, &st.selection, poly_bounds(&pts, radius)) {
        paths.push((id, path_of(&st.doc, id)?.0));
    }
    // Each curved segment in reach gets the same share of the search, whatever order they come in.
    let in_reach: usize = paths.iter().map(|(_, pd)| segments_in_reach(pd, &pts, radius)).sum();
    let share = (MAX_REACH_PIECES / in_reach.max(1)).max(1);
    for (id, pd) in paths {
        let mut changed = false;
        let subs: Vec<SubPath> = pd
            .subpaths
            .iter()
            .map(|sp| match smooth_subpath(sp, &pts, radius, share, tol, sigma) {
                Some(n) if n != *sp && n.anchors.len() >= 2 => {
                    changed = true;
                    n
                }
                _ => sp.clone(),
            })
            .collect();
        if changed {
            let np = PathData::new(subs);
            before += pd.anchor_count();
            after += np.anchor_count();
            plan.push((id, np));
        }
    }
    if plan.is_empty() {
        return Ok(json!({ "ids": [], "before": 0, "after": 0 }));
    }
    let ids: Vec<NodeId> = plan.iter().map(|(id, _)| *id).collect();
    s.edit("Smooth", |d, sel| {
        for (id, np) in plan {
            *path_mut(d, id)? = np;
            // The smoothed path has new anchors, so the old anchor and segment indices are
            // dropped and the path stays selected whole.
            sel.anchors.remove(&id);
            sel.segments.remove(&id);
        }
        Ok(())
    })?;
    let mut v = ids_json(&ids);
    v["before"] = json!(before);
    v["after"] = json!(after);
    Ok(v)
}

// ---------- Join tool ----------

/// Most open subpaths the Join tool compares pairwise for crossings before it only joins ends.
const MAX_TRIM_SUBPATHS: usize = 64;

/// One end of an open subpath that runs on past where it crosses another: the part kept, which
/// ends at the crossing, and the part past it.
struct Overhang {
    kept: SubPath,
    cut: SubPath,
}

impl Overhang {
    fn at(&self) -> Option<Point> {
        self.kept.anchors.last().map(|a| a.p)
    }
}

/// The overhangs of `sp` at its first and last crossing (`places`: subpath, segment, t, in order).
/// A crossing on an end anchor leaves no overhang there.
fn overhangs(sp: &SubPath, places: &[(usize, usize, f64)]) -> Vec<Overhang> {
    let mut out = vec![];
    for (place, at_start) in [(places.first(), true), (places.last(), false)] {
        let Some(&(_, seg, t)) = place else { continue };
        let (split, marks) = pt::insert_at(sp, &[(seg, t)]);
        let Ok([first, second]) = <[SubPath; 2]>::try_from(split.cut_at(&marks)) else { continue };
        let (mut kept, cut) = if at_start { (second, first) } else { (first, second) };
        if at_start {
            kept.reverse();
        }
        out.push(Overhang { kept, cut });
    }
    out
}

/// Does the scrub `pts` (`scrub` as a path) cross `cut` or pass within `tol` of it?
fn scrubbed(cut: &SubPath, pts: &[Point], scrub: &PathData, tol: f64) -> bool {
    let pd = PathData::single(cut.clone());
    pt::crossings(&[&pd, scrub], false).is_some_and(|c| c.first().is_some_and(|v| !v.is_empty()))
        || cut.anchors.iter().any(|a| dist_to_polyline(pts, a.p) <= tol)
        || pts.iter().any(|q| pd.nearest(*q).is_some_and(|n| n.4 <= tol))
}

/// Two crossing open subpaths, each `(path, subpath)`, trimmed and joined at the crossing.
struct TrimJoin {
    a: (NodeId, usize),
    b: (NodeId, usize),
    joined: SubPath,
}

/// #5844: two open subpaths among `ids` that cross, where the scrub runs over the part of each
/// that overhangs the crossing, trimmed at the crossing and joined there with a corner. When
/// several pairs or ends qualify, the one trimming the least wins.
fn trim_join(d: &vectorcraft_doc::Document, ids: &[NodeId], pts: &[Point], tol: f64) -> Result<Option<TrimJoin>> {
    let mut open = vec![];
    for &id in ids {
        let (pd, _) = path_of(d, id)?;
        open.extend(pd.subpaths.into_iter().enumerate().filter(|(_, sp)| !sp.closed && sp.anchors.len() >= 2).map(|(si, sp)| (id, si, sp)));
    }
    if open.len() > MAX_TRIM_SUBPATHS {
        return Ok(None);
    }
    let scrub = PathData::single(SubPath::polyline(pts, false));
    let mut best: Option<(f64, TrimJoin)> = None;
    for (i, (ida, sa, a)) in open.iter().enumerate() {
        for (idb, sb, b) in open.iter().skip(i + 1) {
            let (pa, pb) = (PathData::single(a.clone()), PathData::single(b.clone()));
            let Some(places) = pt::crossings(&[&pa, &pb], false) else { continue };
            let (Some(on_a), Some(on_b)) = (places.first(), places.get(1)) else { continue };
            let (oa, ob) = (overhangs(a, on_a), overhangs(b, on_b));
            for x in oa.iter().filter(|o| scrubbed(&o.cut, pts, &scrub, tol)) {
                for y in ob.iter().filter(|o| scrubbed(&o.cut, pts, &scrub, tol)) {
                    let (Some(xa), Some(ya)) = (x.at(), y.at()) else { continue };
                    let trimmed = subpath_len(&x.cut) + subpath_len(&y.cut);
                    if xa.distance(ya) > 1e-2 || best.as_ref().is_some_and(|b| b.0 <= trimmed) {
                        continue;
                    }
                    // `x` ends at the crossing; `y`, reversed, starts there: one corner anchor.
                    let mut joined = x.kept.clone();
                    let mut rest = y.kept.clone();
                    rest.reverse();
                    let (Some(last), Some(first)) = (joined.anchors.last_mut(), rest.anchors.first()) else { continue };
                    *last =
                        Anchor { p: last.p, h_in: last.h_in, h_out: first.h_out + (last.p - first.p), kind: vectorcraft_geom::AnchorKind::Corner };
                    joined.anchors.extend(rest.anchors.into_iter().skip(1));
                    best = Some((trimmed, TrimJoin { a: (*ida, *sa), b: (*idb, *sb), joined }));
                }
            }
        }
    }
    Ok(best.map(|(_, t)| t))
}

pub(super) fn join_scrub(s: &mut Session, p: &Value) -> Result<Value> {
    const C: &str = "path.joinScrub";
    let pts = points_param(p, "points", C)?;
    let tol = number_or(p, "tolerance", 12.0, C)?.max(0.0);
    let st = s.doc()?;
    let targets = target_paths(&st.doc, &st.selection, poly_bounds(&pts, tol));
    // Paths that cross with their ends scrubbed are trimmed there and joined (#5844).
    if let Some(TrimJoin { a: (ida, sa), b: (idb, sb), joined }) = trim_join(&st.doc, &targets, &pts, tol)? {
        s.edit("Join", |d, sel| {
            let missing = || crate::EngineError::Other("Join: a subpath went missing".into());
            *path_mut(d, ida)?.subpaths.get_mut(sa).ok_or_else(missing)? = joined;
            let pbm = path_mut(d, idb)?;
            if sb >= pbm.subpaths.len() {
                return Err(missing());
            }
            pbm.subpaths.remove(sb);
            if ida != idb && pbm.is_empty() {
                d.remove(idb)?;
            }
            sel.set([ida]);
            Ok(())
        })?;
        return Ok(json!({ "id": ida.0 }));
    }
    // Open endpoints near the scrub, ordered along it: (order, id, subpath, at_start).
    let poly = {
        let mut bp = BezPath::new();
        bp.move_to(pts[0]);
        for q in &pts[1..] {
            bp.line_to(*q);
        }
        bp
    };
    let order = |q: Point| -> f64 {
        poly.segments()
            .enumerate()
            .map(|(i, sg)| (i as f64 + sg.nearest(q, 1e-6).t, sg.nearest(q, 1e-6).distance_sq))
            .min_by(|a, b| a.1.total_cmp(&b.1))
            .map_or(0.0, |x| x.0)
    };
    let (first_pt, last_pt) = (pts.first().copied(), pts.last().copied());
    let mut ends: Vec<(f64, NodeId, usize, bool, Point)> = vec![];
    for id in targets {
        let (pd, _) = path_of(&st.doc, id)?;
        for (si, sp) in pd.subpaths.iter().enumerate() {
            if sp.closed || sp.anchors.len() < 2 {
                continue;
            }
            for (start, a) in [(true, sp.anchors[0].p), (false, sp.anchors[sp.anchors.len() - 1].p)] {
                let on_scrub = dist_to_polyline(&pts, a) <= tol;
                let near_start = first_pt.is_some_and(|p| a.distance(p) <= tol);
                let near_end = last_pt.is_some_and(|p| a.distance(p) <= tol);
                if !on_scrub && !near_start && !near_end {
                    continue;
                }
                let ord = if on_scrub {
                    order(a)
                } else if near_start && (!near_end || first_pt.is_some_and(|p| a.distance(p) <= a.distance(last_pt.unwrap_or(p)))) {
                    -1.0
                } else {
                    1e30
                };
                ends.push((ord, id, si, start, a));
            }
        }
    }
    ends.sort_by(|a, b| a.0.total_cmp(&b.0));
    if ends.len() < 2 {
        return Ok(json!({ "id": null }));
    }
    let (_, ida, sa, starta, pa) = ends[0];
    let (_, idb, sb, startb, pb) = ends[1];
    let mid = pa.midpoint(pb);
    let merge = pa.distance(pb) <= tol;
    s.edit("Join", |d, sel| {
        if ida == idb && sa == sb {
            let path = path_mut(d, ida)?;
            let sp = &mut path.subpaths[sa];
            if merge
                && sp.anchors.len() > 2
                && let Some(l) = sp.anchors.pop()
            {
                let d0 = mid - sp.anchors[0].p;
                sp.anchors[0].translate(d0);
                sp.anchors[0].h_in = l.h_in + (mid - l.p);
            }
            sp.closed = true;
            sel.set([ida]);
            return Ok(());
        }
        let (pdb, _) = path_of(d, idb)?;
        let mut x = path_of(d, ida)?.0.subpaths[sa].clone();
        let mut y = pdb.subpaths[sb].clone();
        if starta {
            x.reverse();
        }
        if !startb {
            y.reverse();
        }
        if merge
            && !y.anchors.is_empty()
            && let Some(last) = x.anchors.last_mut()
        {
            let yf = y.anchors.remove(0);
            let lp = last.p;
            last.translate(mid - lp);
            last.h_out = yf.h_out + (mid - yf.p);
            *last = Anchor::with_handles(last.p, last.h_in, last.h_out);
        }
        x.anchors.extend(y.anchors);
        if ida == idb {
            let path = path_mut(d, ida)?;
            path.subpaths[sa] = x;
            path.subpaths.remove(sb);
        } else {
            path_mut(d, ida)?.subpaths[sa] = x;
            let pbm = path_mut(d, idb)?;
            pbm.subpaths.remove(sb);
            if pbm.is_empty() {
                d.remove(idb)?;
            }
        }
        sel.set([ida]);
        Ok(())
    })?;
    Ok(json!({ "id": ida.0 }))
}

#[cfg(test)]
mod tests {
    use super::*;

    /// A closed ring of four smooth anchors round (100, 100) with radius 50.
    fn ring() -> SubPath {
        let k = 0.5523 * 50.0;
        let a = |x: f64, y: f64, dx: f64, dy: f64| Anchor::with_handles(Point::new(x, y), Point::new(x - dx, y - dy), Point::new(x + dx, y + dy));
        SubPath::new(vec![a(150.0, 100.0, 0.0, k), a(100.0, 150.0, -k, 0.0), a(50.0, 100.0, 0.0, -k), a(100.0, 50.0, k, 0.0)], true)
    }

    /// A start between two anchors of a curve splits that curve there into two that trace it, and the
    /// new anchor comes first.
    #[test]
    fn start_nearest_splits_a_curve_where_it_passes_the_start() {
        let sp = ring();
        let old = sp.segment(0);
        let start = old.eval(0.3) + (old.eval(0.3) - Point::new(100.0, 100.0)) * 0.1;
        let out = start_nearest(sp.clone(), start, &sp);
        assert!(out.closed && out.anchors.len() == 5, "{out:?}");
        let t = old.nearest(start, 1e-9).t;
        assert!(out.anchors[0].p.distance(old.eval(t)) < 1e-9, "{out:?}");
        let (head, rest) = (out.segment(4), out.segment(0));
        for k in 0..=8 {
            let u = f64::from(k) / 8.0;
            assert!(head.eval(u).distance(old.eval(t * u)) < 1e-9);
            assert!(rest.eval(u).distance(old.eval(t + (1.0 - t) * u)) < 1e-9);
        }
        for i in 1..4 {
            assert_eq!(out.segment(i), sp.segment(i), "segment {i} stays");
        }
    }

    /// A start within [`START_SNAP`] of an anchor starts the ring at that anchor, with no anchor added.
    #[test]
    fn start_nearest_starts_at_an_anchor_near_the_start() {
        let sp = ring();
        let out = start_nearest(sp.clone(), Point::new(50.0, 100.0 + START_SNAP / 2.0), &sp);
        let mut want = sp.anchors.clone();
        want.rotate_left(2);
        assert_eq!(out.anchors, want);
    }

    /// A start on a straight side of a triangle adds a corner point there without handles, and the
    /// sides stay straight.
    #[test]
    fn start_nearest_splits_a_line_with_a_corner_point() {
        let sp = SubPath::polyline(&[Point::new(0.0, 0.0), Point::new(100.0, 0.0), Point::new(50.0, 80.0)], true);
        let out = start_nearest(sp.clone(), Point::new(40.0, -5.0), &sp);
        let want: Vec<Point> = [(40.0, 0.0), (100.0, 0.0), (50.0, 80.0), (0.0, 0.0)].map(|(x, y)| Point::new(x, y)).to_vec();
        assert!(out.anchors.len() == 4 && out.anchors.iter().zip(&want).all(|(a, w)| a.p.distance(*w) < 1e-9), "{out:?}");
        assert!((0..4).all(|i| out.segment_is_line(i)), "{out:?}");
    }

    /// A ring whose last anchor lies on its first keeps its first anchor first, and gets no third
    /// anchor at that place.
    #[test]
    fn start_nearest_keeps_the_first_of_two_anchors_on_one_place() {
        let p = [(0.0, 0.0), (100.0, 0.0), (50.0, 80.0), (0.0, 0.0)].map(|(x, y)| Point::new(x, y));
        let sp = SubPath::polyline(&p, true);
        assert_eq!(start_nearest(sp.clone(), p[0], &sp), sp);
    }

    /// Of points equally near the start, the one earliest along the path before smoothing from its
    /// first anchor comes first, whatever the smoothed path's order. The center of a square is equally
    /// near the middle of each side. The square before smoothing starts at (-50, -50), so the middle
    /// of its first side, (0, -50), comes first, though the smoothed copy starts at (50, 50).
    #[test]
    fn start_nearest_breaks_a_tie_by_the_order_before_smoothing() {
        let p = [(-50.0, -50.0), (50.0, -50.0), (50.0, 50.0), (-50.0, 50.0)].map(|(x, y)| Point::new(x, y));
        let orig = SubPath::polyline(&p, true);
        let mut sp = orig.clone();
        sp.anchors.rotate_left(2);
        let out = start_nearest(sp, Point::new(0.0, 0.0), &orig);
        assert!(out.closed && out.anchors.len() == 5, "{out:?}");
        assert!(out.anchors[0].p.distance(Point::new(0.0, -50.0)) < 1e-9, "{out:?}");
        assert!(out.anchors[1].p.distance(p[1]) < 1e-9, "{out:?}");
    }

    /// An open path, and a start that is not a number, leave the path as it is.
    #[test]
    fn start_nearest_leaves_an_open_path_or_a_start_without_a_place() {
        let open = SubPath { closed: false, ..ring() };
        assert_eq!(start_nearest(open.clone(), Point::new(100.0, 50.0), &ring()), open);
        assert_eq!(start_nearest(ring(), Point::new(f64::NAN, 0.0), &ring()), ring());
    }

    /// Searching a curve 1,000,000 pt long under a drag of 1,000 points along it measures no more
    /// pieces than the budget it is given, and a search with none left gives one sample.
    #[test]
    fn searching_a_segment_under_a_drag_stays_within_its_budget() {
        let c = CubicBez::new(Point::new(0.0, 0.0), Point::new(300000.0, 0.0), Point::new(700000.0, 0.0), Point::new(1000000.0, 0.0));
        let pts: Vec<Point> = (0..1000).map(|i| Point::new(f64::from(i) * 1000.0, 0.0)).collect();
        let all = drag_stretches(&pts);
        let mut budget = MAX_REACH_PIECES;
        let (mut first, mut second) = (vec![], vec![]);
        reach_samples(c, (0.0, 1.0), (&pts, &all), 12.0, &mut budget, &mut first);
        reach_samples(c, (0.0, 1.0), (&pts, &all), 12.0, &mut budget, &mut second);
        assert!(first.len() <= MAX_REACH_PIECES, "{} samples", first.len());
        assert_eq!((budget, second.len()), (0, 1), "the budget is spent, so the next search gives one sample");
    }

    /// A small piece of curve is measured only against the few stretches of a drag of 100,000
    /// points that come near it, and a drag of one point has that point as its stretch.
    #[test]
    fn a_small_piece_is_measured_against_the_stretches_near_it() {
        let pts: Vec<Point> = (0..100_000).map(|i| Point::new(f64::from(i) * 5.0, 0.0)).collect();
        let all = drag_stretches(&pts);
        let near = stretches_near(&pts, &all, Rect::new(1000.0, 3.0, 1004.0, 6.0), 12.0);
        assert_eq!(near, (197..=203).collect::<Vec<_>>());
        assert!((dist_to_stretches(&pts, &near, Point::new(1002.0, 5.0)) - 5.0).abs() < 1e-12);
        let one = [Point::new(10.0, 10.0)];
        assert_eq!(drag_stretches(&one), vec![0]);
        assert!((dist_to_stretches(&one, &[0], Point::new(13.0, 14.0)) - 5.0).abs() < 1e-12);
    }

    fn polyline(pts: &[(f64, f64)]) -> Vec<Anchor> {
        pts.iter().map(|&(x, y)| Anchor::corner(Point::new(x, y))).collect()
    }

    /// Anchors on one point, anchors that are not numbers or are too far out to measure, and a
    /// zigzag of 100,001 anchors 1 pt high give no corner and do not fail; a square's four anchors
    /// are its corners, and an open path's ends never are.
    #[test]
    fn corners_are_found_only_where_the_path_turns_at_and_around_an_anchor() {
        assert_eq!(smooth_corners(&polyline(&[(5.0, 5.0); 4]), false, 12.0), vec![false; 4]);
        assert_eq!(smooth_corners(&polyline(&[(0.0, 0.0), (f64::NAN, 1.0), (10.0, 0.0)]), false, 12.0), vec![false; 3]);
        assert_eq!(smooth_corners(&polyline(&[(0.0, 0.0), (1e308, 0.0), (1e308, 1e308), (-1e308, 0.0)]), true, 12.0), vec![false; 4]);
        let zigzag: Vec<(f64, f64)> = (0..=100_000).map(|i| (f64::from(i), f64::from(i % 2))).collect();
        assert!(!smooth_corners(&polyline(&zigzag), false, 12.0).contains(&true));
        let square = polyline(&[(0.0, 0.0), (100.0, 0.0), (100.0, 100.0), (0.0, 100.0)]);
        assert_eq!(smooth_corners(&square, true, 12.0), vec![true; 4]);
        assert_eq!(smooth_corners(&square, false, 12.0), vec![false, true, true, false]);
        assert_eq!(smooth_corners(&square, false, 0.0), vec![false, true, true, false], "with no reach the turn at the anchor decides");
        assert_eq!(smooth_corners(&square[..2], false, 12.0), vec![false; 2]);
    }

    /// A 90° bump 400 pt high cut into 1 pt segments, between two long straight segments: with a reach
    /// of 10 pt, and of 300 pt, where twice the reach passes the bump's 566 segments on each side, its
    /// top is a corner, and with a reach of 1,000 pt its top is not one, as the path turns by about 51°
    /// over that reach. The turns into and between 1 pt segments that follow two segments 1e16 pt long
    /// are corners too.
    #[test]
    fn a_bump_of_many_short_segments_is_a_corner_where_it_turns_over_the_reach() {
        let side = 400.0 * std::f64::consts::SQRT_2;
        let steps = side.ceil() as usize;
        let mut pts = vec![(-3000.0, 0.0)];
        pts.extend((0..steps).map(|j| {
            let f = j as f64 / steps as f64;
            (-400.0 + 400.0 * f, 400.0 * f)
        }));
        pts.extend((0..=steps).map(|j| {
            let f = j as f64 / steps as f64;
            (400.0 * f, 400.0 - 400.0 * f)
        }));
        pts.push((3000.0, 0.0));
        let anchors = polyline(&pts);
        let top = steps + 1;
        assert_eq!(anchors[top].p, Point::new(0.0, 400.0));
        assert!(smooth_corners(&anchors, false, 10.0)[top]);
        assert!(smooth_corners(&anchors, false, 300.0)[top]);
        let long = polyline(&[(0.0, 0.0), (1e16, 0.0), (0.0, 0.0), (0.0, 1.0), (1.0, 1.0), (1.0, 2.0)]);
        let corners = smooth_corners(&long, false, 0.5);
        assert!(corners[2] && corners[3] && corners[4], "{corners:?}");
        assert!(!smooth_corners(&anchors, false, 1000.0)[top]);
    }

    /// A 60° corner between two curved segments 1,000 pt long is found at a reach of 2 pt as it is
    /// when each segment is cut into a thousand pieces: the turns over the reach are measured along the
    /// curve near the anchor, not along a chord much longer than the reach.
    #[test]
    fn a_corner_between_long_curves_is_measured_along_them() {
        // The curves arrive along x and leave at 60° to it, each bending away from the other.
        let d = kurbo::Vec2::from_angle(-60f64.to_radians());
        let side = kurbo::Vec2::new(-d.y, d.x) * 1000.0;
        let v = Point::new(0.0, 0.0);
        let a = Anchor::with_handles(Point::new(-1000.0, 1000.0), Point::new(-1000.0, 1000.0), Point::new(-300.0, 1000.0));
        let b = Anchor::with_handles(v, Point::new(-300.0, 0.0), v + d * 300.0);
        let end = v + d * 1000.0 + side;
        let c = Anchor::with_handles(end, v + d * 300.0 + side, end);
        let long = [a, b, c];
        let fine: Vec<Anchor> = {
            let sp = SubPath::new(long.to_vec(), false);
            let mut pts = vec![];
            for i in 0..2 {
                let s = sp.segment(i);
                for j in 0..1000 {
                    let p = s.subsegment(f64::from(j) / 1000.0..f64::from(j + 1) / 1000.0);
                    if j == 0 && i == 0 {
                        pts.push(Anchor::with_handles(p.p0, p.p0, p.p1));
                    } else if let Some(last) = pts.last_mut() {
                        *last = Anchor::with_handles(last.p, last.h_in, p.p1);
                    }
                    pts.push(Anchor::with_handles(p.p3, p.p2, p.p3));
                }
            }
            pts
        };
        let at_v = |anchors: &[Anchor]| {
            let corners = smooth_corners(anchors, false, 2.0);
            anchors.iter().zip(corners).find(|(x, _)| x.p == v).map(|(_, c)| c)
        };
        assert_eq!(at_v(&fine), Some(true), "cut finely, the anchor is a corner");
        assert_eq!(at_v(&long), Some(true));
    }

    /// A line that meets a curve leaving with no handle, turning by 58° at the anchor and by about
    /// 57.53° over twice a reach of 0.02 pt: the anchor is a corner, measured either way along the path,
    /// as the stretch measured finely near the anchor covers twice the reach along the curve.
    #[test]
    fn a_corner_next_to_a_curve_without_a_handle_is_kept() {
        let at = 58f64.to_radians();
        let prev = Anchor::corner(Point::new(-100.0 * at.cos(), -100.0 * at.sin()));
        let v = Point::new(0.0, 0.0);
        let a = Anchor::with_handles(v, v, v);
        let end = Point::new(600.0, 600.0);
        let next = Anchor::with_handles(end, Point::new(200.0, 0.0), end);
        assert_eq!(smooth_corners(&[prev, a, next], false, 0.02), vec![false, true, false]);
        let back = |x: Anchor| Anchor::with_handles(x.p, x.h_out, x.h_in);
        assert_eq!(smooth_corners(&[back(next), back(a), back(prev)], false, 0.02), vec![false, true, false]);
    }

    /// A jagged closed path whose length is less than twice the reach: its jags are not corners,
    /// while a triangle that small keeps its three.
    #[test]
    fn a_small_jagged_loop_has_no_corners() {
        let ring: Vec<(f64, f64)> = (0..16)
            .map(|i| {
                let (a, r) = (f64::from(i) / 16.0 * std::f64::consts::TAU, if i % 2 == 0 { 3.0 } else { 2.0 });
                (r * a.cos(), r * a.sin())
            })
            .collect();
        let jags = polyline(&ring);
        let sp = SubPath::new(jags.clone(), true);
        assert!(subpath_len(&sp) < 24.0);
        assert!(smooth_corners(&jags, true, 1e-6).iter().all(|c| *c), "each jag turns sharply at its anchor");
        assert_eq!(smooth_corners(&jags, true, 12.0), vec![false; 16]);
        assert_eq!(smooth_corners(&polyline(&[(0.0, 0.0), (6.0, 0.0), (3.0, 5.196)]), true, 12.0), vec![true; 3]);
    }
}