GitCorner

Code

ossartcraftvectorcraft๐ŸŒ
2bc41aeb8602
//! Artwork Cleanup's path repairs, each on one subpath and returning how much it changed (so a
//! check is the repair run on a copy): collinear anchors, duplicate anchors, tiny handles and
//! nearly closed paths; [`near_point_groups`] finds anchors to snap together, and [`rejoin`] welds
//! open pieces whose ends meet back into paths.

use std::collections::{BTreeSet, HashMap};

use kurbo::{Point, Vec2};
use vectorcraft_geom::{Anchor, AnchorKind, EPS, SubPath};

use crate::fit::{end_tangent, start_tangent};

/// The fewest anchors a subpath keeps: two when open, three when closed.
fn min_anchors(sp: &SubPath) -> usize {
    if sp.closed { 3 } else { 2 }
}

/// `a`'s handle offset `h - a.p` moved onto `p`.
fn moved(p: Point, a_p: Point, h: Point) -> Point {
    p + (h - a_p)
}

/// Remove the corner anchors (no handles, straight segments both sides) where a straight run goes
/// on in the same direction: the sine of the angle it turns there is at most `tolerance`. Open ends
/// stay, and a subpath keeps two anchors (three when closed) โ†’ how many went.
///
/// Each anchor is tested once, first to last, against the nearest anchors still kept on either
/// side. On a closed subpath, an anchor with none kept before it has the last anchor as its
/// previous neighbor, and the last anchor has the first one kept as its next neighbor. The kept
/// anchors move into place once at the end, so the work grows linearly with the number of anchors.
pub fn remove_collinear_anchors(sp: &mut SubPath, tolerance: f64) -> usize {
    let n = sp.anchors.len();
    let min = min_anchors(sp);
    if n <= min {
        return 0;
    }
    let mut keep = vec![true; n];
    let (mut left, mut first_kept, mut last_kept) = (n, None, None);
    #[cfg(test)]
    let mut work = 0;
    for i in 0..n {
        if left <= min {
            break;
        }
        #[cfg(test)]
        {
            work += 1;
        }
        // Every anchor after `i` is still there, the last one included.
        let p = last_kept.unwrap_or(n - 1);
        let q = if i + 1 < n { i + 1 } else { first_kept.unwrap_or(i) };
        let inner = sp.closed || (last_kept.is_some() && i + 1 < n);
        let (Some(prev), Some(cur), Some(next)) = (sp.anchors.get(p), sp.anchors.get(i), sp.anchors.get(q)) else { break };
        let straight = !prev.has_out() && !cur.has_in() && !cur.has_out() && !next.has_in();
        let (a, b) = (cur.p - prev.p, next.p - cur.p);
        let len = a.hypot() * b.hypot();
        if inner && straight && len > EPS && a.dot(b) > 0.0 && a.cross(b).abs() / len <= tolerance {
            if let Some(k) = keep.get_mut(i) {
                *k = false;
            }
            left -= 1;
        } else {
            first_kept.get_or_insert(i);
            last_kept = Some(i);
        }
    }
    if left < n {
        let mut kept = keep.iter();
        sp.anchors.retain(|_| kept.next().copied().unwrap_or(true));
        #[cfg(test)]
        {
            work += n;
        }
    }
    #[cfg(test)]
    COLLINEAR_WORK.with(|w| w.set(work));
    n - left
}

#[cfg(test)]
thread_local! {
    /// Anchors tested plus anchors moved by the last [`remove_collinear_anchors`] on this thread.
    static COLLINEAR_WORK: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
}

/// Merge each anchor lying within `distance` of the one before it (and a closed subpath's last
/// anchor within `distance` of its first) into that one, which keeps its in handle and takes the
/// merged anchor's out handle โ†’ how many went.
pub fn merge_duplicate_anchors(sp: &mut SubPath, distance: f64) -> usize {
    let before = sp.anchors.len();
    let mut out: Vec<Anchor> = Vec::with_capacity(before);
    for a in sp.anchors.drain(..) {
        match out.last_mut() {
            Some(l) if l.p.distance(a.p) <= distance => *l = Anchor::with_handles(l.p, l.h_in, moved(l.p, a.p, a.h_out)),
            _ => out.push(a),
        }
    }
    if sp.closed
        && out.len() > 1
        && let (Some(first), Some(last)) = (out.first(), out.last())
        && first.p.distance(last.p) <= distance
        && let Some(last) = out.pop()
        && let Some(f) = out.first_mut()
    {
        *f = Anchor::with_handles(f.p, moved(f.p, last.p, last.h_in), f.h_out);
    }
    sp.anchors = out.into();
    before - sp.anchors.len()
}

/// Retract the handles shorter than `length` (but not already on their anchor); an anchor that
/// loses a handle becomes a corner โ†’ how many handles were retracted.
pub fn retract_tiny_handles(sp: &mut SubPath, length: f64) -> usize {
    let mut count = 0;
    for a in &mut sp.anchors {
        for out in [false, true] {
            let h = if out { &mut a.h_out } else { &mut a.h_in };
            let l = h.distance(a.p);
            if l > EPS && l < length {
                *h = a.p;
                a.kind = AnchorKind::Corner;
                count += 1;
            }
        }
    }
    count
}

/// Close an open subpath of three or more anchors whose ends lie within `distance` of each other:
/// the last anchor merges into the first, which takes its in handle โ†’ whether it closed.
pub fn close_nearly_closed(sp: &mut SubPath, distance: f64) -> bool {
    let ends_meet = sp.anchors.first().zip(sp.anchors.last()).is_some_and(|(f, l)| f.p.distance(l.p) <= distance);
    if sp.closed || sp.anchors.len() < 3 || !ends_meet {
        return false;
    }
    let Some(last) = sp.anchors.pop() else { return false };
    if let Some(first) = sp.anchors.first_mut() {
        *first = Anchor::with_handles(first.p, moved(first.p, last.p, last.h_in), first.h_out);
    }
    sp.closed = true;
    true
}

/// The cell of a grid of `size`-wide squares that `p` lies in.
fn grid_cell(p: Point, size: f64) -> (i64, i64) {
    ((p.x / size).floor() as i64, (p.y / size).floor() as i64)
}

/// The cell `(x, y)` and the cells around it, each once.
fn around((x, y): (i64, i64)) -> Vec<(i64, i64)> {
    let mut out: Vec<(i64, i64)> = [-1, 0, 1].into_iter().flat_map(|dx| [-1, 0, 1].map(|dy| (x.saturating_add(dx), y.saturating_add(dy)))).collect();
    out.sort_unstable();
    out.dedup();
    out
}

/// The root of `i`'s set in the union-find forest `parent`.
fn root(parent: &mut [usize], mut i: usize) -> usize {
    while let Some(&p) = parent.get(i).filter(|&&p| p != i) {
        let up = parent.get(p).copied().unwrap_or(p);
        if let Some(slot) = parent.get_mut(i) {
            *slot = up;
        }
        i = p;
    }
    i
}

/// Groups of `points` to snap together: points within `distance` of one another (and so on, one
/// to the next) that aren't all at the same place, skipping the pairs `linked` names (such as
/// neighbouring anchors of one path). Each group lists its points in order; snapping them all to
/// the first one makes them coincide. Non-finite points and a distance that isn't a positive number
/// find nothing.
///
/// Two points are compared when their cells of a `distance`-wide grid touch. Each group grows from
/// one point at a time, which looks only at points no group has taken yet, so a cluster of points
/// all within `distance` of one another is grouped with work that grows linearly with its size.
pub fn near_point_groups(points: &[Point], distance: f64, linked: impl Fn(usize, usize) -> bool) -> Vec<Vec<usize>> {
    if !(distance > 0.0 && distance.is_finite()) {
        return vec![];
    }
    let mut cells = buckets(points, distance);
    let mut near = Near {
        distance,
        linked,
        parent: (0..points.len()).collect(),
        taken: points.iter().map(|p| !p.is_finite()).collect(),
        queue: vec![],
        #[cfg(test)]
        work: 0,
    };
    for (start, &p) in points.iter().enumerate() {
        if near.taken.get(start) != Some(&false) {
            continue;
        }
        if let Some(t) = near.taken.get_mut(start) {
            *t = true;
        }
        let mut at = Some((start, p));
        while let Some((i, p)) = at {
            near.reach(&mut cells, i, p);
            at = near.queue.pop().and_then(|j| Some((j, *points.get(j)?)));
        }
    }
    #[cfg(test)]
    NEAR_WORK.with(|w| w.set(near.work));
    // Only pairs that aren't at the same place were joined, so no group is all at one place.
    let mut groups: HashMap<usize, Vec<usize>> = HashMap::new();
    for i in 0..points.len() {
        groups.entry(root(&mut near.parent, i)).or_default().push(i);
    }
    let mut out: Vec<Vec<usize>> = groups.into_values().filter(|g| g.len() > 1).collect();
    out.sort_unstable();
    out
}

#[cfg(test)]
thread_local! {
    /// Buckets, places and points looked at by the last [`near_point_groups`] on this thread.
    static NEAR_WORK: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
}

/// The finite points of one cell of a grid that lie in one square a quarter of a cell wide, with
/// the box around them.
struct Bucket {
    lo: Point,
    hi: Point,
    /// Each place (bit for bit) and the points there that no group has taken yet, though some of
    /// them may have been taken since.
    places: Vec<(Point, Vec<usize>)>,
}

impl Bucket {
    /// Whether [`Point::distance`] puts every point here further than `distance` from `p`: one
    /// coordinate alone differs by more. The square of a `distance` of 1e-150 or more does not
    /// underflow, so the measured distance is at least that difference.
    fn beyond(&self, p: Point, distance: f64) -> bool {
        distance >= 1e-150 && [self.lo.x - p.x, p.x - self.hi.x, self.lo.y - p.y, p.y - self.hi.y].into_iter().any(|g| g > distance)
    }
}

/// The finite `points` in buckets, by grid cell.
fn buckets(points: &[Point], distance: f64) -> HashMap<(i64, i64), Vec<Bucket>> {
    let quarter = distance / 4.0;
    let mut cells: HashMap<(i64, i64), Vec<Bucket>> = HashMap::new();
    // Each bucket by its cell and square, and each place by its cell, bucket and coordinates.
    let mut bucket_at: HashMap<[i64; 4], usize> = HashMap::new();
    let mut place_at: HashMap<(usize, [i64; 2], [u64; 2]), usize> = HashMap::new();
    for (i, &p) in points.iter().enumerate().filter(|(_, p)| p.is_finite()) {
        let c = grid_cell(p, distance);
        let list = cells.entry(c).or_default();
        let square = grid_cell(p, quarter);
        let b = *bucket_at.entry([c.0, c.1, square.0, square.1]).or_insert_with(|| {
            list.push(Bucket { lo: p, hi: p, places: vec![] });
            list.len() - 1
        });
        let Some(bucket) = list.get_mut(b) else { continue };
        bucket.lo = Point::new(bucket.lo.x.min(p.x), bucket.lo.y.min(p.y));
        bucket.hi = Point::new(bucket.hi.x.max(p.x), bucket.hi.y.max(p.y));
        let at = *place_at.entry((b, [c.0, c.1], [p.x.to_bits(), p.y.to_bits()])).or_insert_with(|| {
            bucket.places.push((p, vec![]));
            bucket.places.len() - 1
        });
        if let Some((_, here)) = bucket.places.get_mut(at) {
            here.push(i);
        }
    }
    cells
}

/// The grouping behind [`near_point_groups`].
struct Near<F> {
    distance: f64,
    linked: F,
    /// The union-find forest of the groups.
    parent: Vec<usize>,
    /// Whether each point is in a group being grown or grown already (non-finite ones never are).
    taken: Vec<bool>,
    /// Points taken into the group being grown whose own neighbors are still to be looked at.
    queue: Vec<usize>,
    #[cfg(test)]
    work: usize,
}

impl<F: Fn(usize, usize) -> bool> Near<F> {
    /// Take into `i`'s group every point no group has taken yet that lies within the distance of
    /// `p`, `i`'s place, in the cells around it, at a different place and not linked to `i`.
    fn reach(&mut self, cells: &mut HashMap<(i64, i64), Vec<Bucket>>, i: usize, p: Point) {
        for c in around(grid_cell(p, self.distance)) {
            let Some(buckets) = cells.get_mut(&c) else { continue };
            buckets.retain_mut(|b| {
                #[cfg(test)]
                {
                    self.work += 1;
                }
                if !b.beyond(p, self.distance) {
                    b.places.retain_mut(|place| {
                        self.visit(i, p, place);
                        !place.1.is_empty()
                    });
                }
                !b.places.is_empty()
            });
        }
    }

    /// Take into `i`'s group the points at `place` that `i` joins, and drop the ones taken.
    fn visit(&mut self, i: usize, p: Point, (at, here): &mut (Point, Vec<usize>)) {
        #[cfg(test)]
        {
            self.work += 1;
        }
        let d = p.distance(*at);
        if !(d <= self.distance && d > 0.0) {
            return;
        }
        here.retain(|&j| {
            if self.taken.get(j) != Some(&false) {
                return false;
            }
            #[cfg(test)]
            {
                self.work += 1;
            }
            if (self.linked)(i.min(j), i.max(j)) {
                return true;
            }
            let (ri, rj) = (root(&mut self.parent, i), root(&mut self.parent, j));
            if let Some(slot) = self.parent.get_mut(ri.max(rj)) {
                *slot = ri.min(rj);
            }
            if let Some(t) = self.taken.get_mut(j) {
                *t = true;
            }
            self.queue.push(j);
            false
        });
    }
}

/// Open pieces welded into one path by [`rejoin`]: `members` index the pieces in the order they
/// run along `path`.
#[derive(Clone, Debug, PartialEq)]
pub struct Rejoined {
    pub members: Vec<usize>,
    pub path: SubPath,
}

/// One end of a piece: (piece, true for its last anchor).
type End = (usize, bool);

/// The direction pointing out of the piece at `end`.
fn outward(sp: &SubPath, last: bool) -> Option<Vec2> {
    let n = sp.segment_count();
    Some(match last {
        true => end_tangent(&sp.segment(n.checked_sub(1)?)),
        false => -start_tangent(&sp.segment(0)),
    })
}

/// Weld the open `pieces` whose ends lie within `gap` of each other back into paths: an end meets
/// at most one other, and where an end could meet several, it meets the one the path turns least
/// to go on into (then the nearest). A piece may run either way; a chain whose ends meet closes.
/// Each junction keeps the earlier piece's anchor and the later piece's out handle. Pieces that are
/// closed, have fewer than two anchors or a non-finite coordinate stay out. โ†’ the chains of two or
/// more pieces, and the single pieces that closed.
///
/// Two ends are compared when their cells of a `gap`-wide grid touch, and pairs are taken in order
/// of the turn, then the distance, then the order of the ends. Each end looks for its first
/// partner in that order among the ends still free, searching outward from the reverse of its own
/// direction, and two ends that are each other's first partner meet; these are the pairs that
/// taking every pair in that order gives.
pub fn rejoin(pieces: &[SubPath], gap: f64) -> Vec<Rejoined> {
    if !(gap >= 0.0 && gap.is_finite()) {
        return vec![];
    }
    let usable = |sp: &&SubPath| {
        !sp.closed && sp.anchors.len() >= 2 && sp.anchors.iter().all(|a| a.p.is_finite() && a.h_in.is_finite() && a.h_out.is_finite())
    };
    // Each usable end: where it is and the way out of its piece there.
    let ends: Vec<EndAt> = pieces
        .iter()
        .enumerate()
        .filter(|(_, sp)| usable(sp))
        .flat_map(|(i, sp)| [(i, sp, false), (i, sp, true)])
        .filter_map(|(i, sp, last)| {
            let a = if last { sp.anchors.last() } else { sp.anchors.first() }?;
            Some(((i, last), a.p, outward(sp, last)?))
        })
        .collect();
    let link = Weld::new(pieces, &ends, gap).link();
    chains(pieces, &link)
}

/// An end, where it lies and the unit direction pointing out of its piece there.
type EndAt = (End, Point, Vec2);

/// Where a pair of ends (`a` < `b` in the list of ends) comes in the order [`rejoin`] takes pairs:
/// the turn across the junction, the distance between the ends, `a`, the place of `b`'s grid cell
/// among the cells around `a`'s, and `b`.
type Order = (f64, f64, usize, usize, usize);

/// Whether pair `x` comes before pair `y`.
fn earlier(x: &Order, y: &Order) -> bool {
    x.0.total_cmp(&y.0).then(x.1.total_cmp(&y.1)).then((x.2, x.3, x.4).cmp(&(y.2, y.3, y.4))).is_lt()
}

/// The place of cell `to` among the cells around `from`, listed by x step and then y step from -1
/// to 1 (cells past the end of the grid repeat their neighbor; the first place counts).
fn listed_at(from: (i64, i64), to: (i64, i64)) -> usize {
    let mut steps = [-1, 0, 1].into_iter().flat_map(|dx| [-1, 0, 1].map(|dy| (from.0.saturating_add(dx), from.1.saturating_add(dy))));
    steps.position(|c| c == to).unwrap_or(9)
}

/// `angle` as an integer in the same order.
fn angle_key(angle: f64) -> i64 {
    let bits = angle.to_bits() as i64;
    bits ^ (((bits >> 63) as u64) >> 1) as i64
}

/// The angle between the directions at angles `a` and `b`, from 0 to ฯ€.
fn apart(a: f64, b: f64) -> f64 {
    let d = (a - b).abs();
    d.min(std::f64::consts::TAU - d)
}

/// How far past the turn of the best pair found so far [`Weld::first_partner`] still looks. The
/// turn [`rejoin`] measures (the arc cosine of a dot product of unit vectors) is within 1e-7 of
/// the angle between the directions, and the angles the search sorts by are within 1e-14 of it.
const TURN_SLACK: f64 = 1e-6;

/// Ends in one grid cell at one place with one outward direction (bit for bit): every other end
/// pairs with each of them at the same turn and distance.
struct Class {
    at: Point,
    angle: f64,
    /// The ends here no pair has taken yet.
    free: BTreeSet<usize>,
}

/// The pairing behind [`rejoin`].
struct Weld<'a> {
    pieces: &'a [SubPath],
    ends: &'a [EndAt],
    gap: f64,
    /// The width of the grid's cells.
    size: f64,
    classes: Vec<Class>,
    /// Each end's class.
    class_of: Vec<usize>,
    /// Each grid cell's classes with free ends, by the angle of their direction.
    cells: HashMap<(i64, i64), BTreeSet<(i64, usize)>>,
    /// Whether each end is still free.
    free: Vec<bool>,
    /// Whether each end has looked for its first partner. Another end's first partner in a class
    /// is one of the class's first three free ends, so the ends after those cannot meet next and
    /// look only once they move up.
    awake: Vec<bool>,
    /// Each awake end's first partner, and where that pair comes in the order.
    first: Vec<Option<(Order, usize)>>,
    /// The ends whose first partner each end is (some may have moved on since).
    wanted_by: Vec<Vec<usize>>,
    /// Ends to check for a partner whose first partner they are.
    todo: Vec<usize>,
    #[cfg(test)]
    work: std::cell::Cell<usize>,
}

impl<'a> Weld<'a> {
    fn new(pieces: &'a [SubPath], ends: &'a [EndAt], gap: f64) -> Self {
        let size = gap.max(1e-9);
        let (mut classes, mut class_of, mut cells) = (vec![], vec![], HashMap::new());
        let mut class_at: HashMap<((i64, i64), [u64; 4]), usize> = HashMap::new();
        for (i, &(_, p, out)) in ends.iter().enumerate() {
            let c = grid_cell(p, size);
            let k = *class_at.entry((c, [p.x, p.y, out.x, out.y].map(f64::to_bits))).or_insert_with(|| {
                let angle = out.y.atan2(out.x);
                cells.entry(c).or_insert_with(BTreeSet::new).insert((angle_key(angle), classes.len()));
                classes.push(Class { at: p, angle, free: BTreeSet::new() });
                classes.len() - 1
            });
            if let Some(class) = classes.get_mut(k) {
                class.free.insert(i);
            }
            class_of.push(k);
        }
        let n = ends.len();
        Weld {
            pieces,
            ends,
            gap,
            size,
            classes,
            class_of,
            cells,
            free: vec![true; n],
            awake: vec![false; n],
            first: vec![None; n],
            wanted_by: vec![vec![]; n],
            todo: vec![],
            #[cfg(test)]
            work: std::cell::Cell::new(0),
        }
    }

    /// The links between the ends that meet: two free ends that are each other's first partner
    /// meet, and the ends that wanted either of them look again, until no such pair is left.
    fn link(mut self) -> HashMap<End, End> {
        for k in 0..self.classes.len() {
            self.wake(k);
        }
        let mut link: HashMap<End, End> = HashMap::new();
        while let Some(v) = self.todo.pop() {
            let Some(w) = self.partner(v) else { continue };
            if self.free.get(v) != Some(&true) || self.free.get(w) != Some(&true) || self.partner(w) != Some(v) {
                continue;
            }
            let (Some(&(ev, ..)), Some(&(ew, ..))) = (self.ends.get(v), self.ends.get(w)) else { continue };
            link.insert(ev, ew);
            link.insert(ew, ev);
            self.take(v);
            self.take(w);
            for e in [v, w] {
                if let Some(&k) = self.class_of.get(e) {
                    self.wake(k);
                }
            }
            let waiting: Vec<usize> = [v, w].iter().flat_map(|&e| self.wanted_by.get_mut(e).map(std::mem::take).unwrap_or_default()).collect();
            for x in waiting {
                if self.free.get(x) == Some(&true) && matches!(self.partner(x), Some(p) if p == v || p == w) {
                    self.look(x);
                }
            }
        }
        #[cfg(test)]
        REJOIN_WORK.with(|w| w.set(self.work.get()));
        link
    }

    /// End `v`'s first partner, once it has looked.
    fn partner(&self, v: usize) -> Option<usize> {
        self.first.get(v).and_then(|f| f.as_ref()).map(|f| f.1)
    }

    /// Have the first three free ends of class `k` that have not looked for a partner look.
    fn wake(&mut self, k: usize) {
        let Some(class) = self.classes.get(k) else { return };
        let sleeping: Vec<usize> = class.free.iter().take(3).copied().filter(|&e| self.awake.get(e) == Some(&false)).collect();
        for e in sleeping {
            if let Some(a) = self.awake.get_mut(e) {
                *a = true;
            }
            self.look(e);
        }
    }

    /// Find free end `e`'s first partner, and queue `e` to check whether that end wants it too.
    fn look(&mut self, e: usize) {
        let next = self.first_partner(e);
        if let Some(list) = next.as_ref().and_then(|f| self.wanted_by.get_mut(f.1)) {
            list.push(e);
        }
        if let Some(f) = self.first.get_mut(e) {
            *f = next;
        }
        self.todo.push(e);
    }

    /// End `e` has met another: it is no longer free.
    fn take(&mut self, e: usize) {
        if let Some(f) = self.free.get_mut(e) {
            *f = false;
        }
        let Some(&k) = self.class_of.get(e) else { return };
        let Some(class) = self.classes.get_mut(k) else { return };
        class.free.remove(&e);
        if class.free.is_empty()
            && let Some(&(_, p, _)) = self.ends.get(e)
            && let Some(set) = self.cells.get_mut(&grid_cell(p, self.size))
        {
            set.remove(&(angle_key(class.angle), k));
        }
    }

    /// The free end `v` meets first, and where that pair comes in the order: the classes in the
    /// cells around `v`'s are looked at by how far their direction is from the reverse of `v`'s,
    /// until that is more than [`TURN_SLACK`] past the best turn found.
    fn first_partner(&self, v: usize) -> Option<(Order, usize)> {
        let &((piece, _), p, out) = self.ends.get(v)?;
        let toward = (-out.y).atan2(-out.x);
        let split = (angle_key(toward), 0);
        let mut best: Option<(Order, usize)> = None;
        for c in around(grid_cell(p, self.size)) {
            let Some(set) = self.cells.get(&c) else { continue };
            // Both ways round from `toward`; between them they meet every class once.
            let mut up = set.range(split..).chain(set.range(..split)).peekable();
            let mut down = set.range(..split).rev().chain(set.range(split..).rev()).peekable();
            let turn = |e: Option<&&(i64, usize)>| e.and_then(|e| self.classes.get(e.1)).map_or(f64::INFINITY, |k| apart(k.angle, toward));
            for _ in 0..set.len() {
                let (tu, td) = (turn(up.peek()), turn(down.peek()));
                if best.as_ref().is_some_and(|b| tu.min(td) > b.0.0 + TURN_SLACK) {
                    break;
                }
                let Some(&(_, k)) = (if tu <= td { up.next() } else { down.next() }) else { break };
                if let Some(pair) = self.pair_with(v, p, piece, k)
                    && best.as_ref().is_none_or(|b| earlier(&pair.0, &b.0))
                {
                    best = Some(pair);
                }
            }
        }
        best
    }

    /// The first free end of class `k` that free end `v` (at `p`, on `piece`) may meet, and where
    /// that pair comes in the order. Within a class the pairs differ only in the ends' order, so
    /// the end listed first comes first.
    fn pair_with(&self, v: usize, p: Point, piece: usize, k: usize) -> Option<(Order, usize)> {
        #[cfg(test)]
        self.work.set(self.work.get() + 1);
        let class = self.classes.get(k)?;
        if p.distance(class.at) > self.gap {
            return None;
        }
        // A piece's own two ends meet only when closing it leaves a shape (three anchors).
        let short = self.pieces.get(piece).is_none_or(|sp| sp.anchors.len() < 3);
        let u = *class.free.iter().find(|&&u| u != v && !(short && self.ends.get(u).is_some_and(|e| e.0.0 == piece)))?;
        let (a, b) = (v.min(u), v.max(u));
        let (&(_, pa, oa), &(_, pb, ob)) = (self.ends.get(a)?, self.ends.get(b)?);
        let at = listed_at(grid_cell(pa, self.size), grid_cell(pb, self.size));
        Some(((oa.dot(-ob).clamp(-1.0, 1.0).acos(), pa.distance(pb), a, at, b), u))
    }
}

#[cfg(test)]
thread_local! {
    /// Classes of ends looked at by the last [`rejoin`] on this thread.
    static REJOIN_WORK: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
}

/// Walk the links between piece ends into chains.
fn chains(pieces: &[SubPath], link: &HashMap<End, End>) -> Vec<Rejoined> {
    let mut seen = vec![false; pieces.len()];
    let mut out = vec![];
    for start in 0..pieces.len() {
        if seen.get(start) != Some(&false) || !(link.contains_key(&(start, false)) || link.contains_key(&(start, true))) {
            continue;
        }
        // A member is (piece, reversed): it comes in by end (piece, reversed) and leaves by
        // (piece, !reversed). Back up to the chain's first piece, or round to `start` in a loop.
        let mut first = (start, false);
        let mut closed = false;
        for _ in 0..pieces.len() {
            let Some(&(p, at_last)) = link.get(&first) else { break };
            // The piece before leaves by its end `at_last`.
            let prev = (p, !at_last);
            if prev.0 == start {
                closed = true;
                break;
            }
            first = prev;
        }
        let members = walk(link, first, closed, &mut seen);
        if let Some(path) = assemble(pieces, &members, closed) {
            out.push(Rejoined { members: members.iter().map(|m| m.0).collect(), path });
        }
    }
    out
}

/// The pieces of the chain that begins with `first` (piece, reversed), in order.
fn walk(link: &HashMap<End, End>, first: (usize, bool), closed: bool, seen: &mut [bool]) -> Vec<(usize, bool)> {
    let mut members = vec![];
    let mut cur = first;
    loop {
        match seen.get_mut(cur.0) {
            Some(s) if !*s => *s = true,
            _ => break,
        }
        members.push(cur);
        // A piece run forwards leaves by its last anchor.
        let Some(&(p, at_last)) = link.get(&(cur.0, !cur.1)) else { break };
        let next = (p, at_last);
        if closed && next.0 == first.0 {
            break;
        }
        cur = next;
    }
    members
}

/// The anchors of `pieces` along the chain `members`, each piece's start merged into the end before it.
fn assemble(pieces: &[SubPath], members: &[(usize, bool)], closed: bool) -> Option<SubPath> {
    if members.len() < 2 && !closed {
        return None;
    }
    let mut anchors: Vec<Anchor> = vec![];
    for &(i, reversed) in members {
        let mut sp = pieces.get(i)?.clone();
        if reversed {
            sp.reverse();
        }
        let mut rest = sp.anchors.into_iter();
        match (anchors.last_mut(), rest.next()) {
            (Some(l), Some(f)) => *l = Anchor::with_handles(l.p, l.h_in, moved(l.p, f.p, f.h_out)),
            (None, Some(f)) => anchors.push(f),
            _ => {}
        }
        anchors.extend(rest);
    }
    let mut sp = SubPath::new(anchors, false);
    if closed && !close_nearly_closed(&mut sp, f64::INFINITY) {
        sp.closed = sp.anchors.len() >= 2;
    }
    Some(sp)
}

#[cfg(test)]
mod tests;