GitCorner

Code

ossartcraftvectorcraft🌐
2bc41aeb8602
use super::*;

/// Names starting with this mark a Live Paint group, together with its sources group ([`SOURCES_NAME`]).
pub const LIVE_PAINT_PREFIX: &str = "Live Paint";

/// Default name of a new Live Paint group.
pub const LIVE_PAINT_NAME: &str = "Live Paint Group";

/// The hidden child group holding the source paths.
pub const SOURCES_NAME: &str = "Live Paint Sources";

pub const FACE_NAME: &str = "Face";

pub const EDGE_NAME: &str = "Edge";

/// Is `n` a Live Paint group: an unclipped group whose name starts with [`LIVE_PAINT_PREFIX`] and
/// that holds a group named [`SOURCES_NAME`]? A plain group with such a name is not one.
pub fn is_live_paint(n: &Node) -> bool {
    matches!(n.kind, NodeKind::Group { clip: false, .. })
        && n.name.as_deref().is_some_and(|s| s.starts_with(LIVE_PAINT_PREFIX))
        && sources(n).is_some_and(|s| matches!(s.kind, NodeKind::Group { .. }))
}

/// Whether Live Paint can take `n` as it is: a Live Paint group, a path or compound path, or a
/// group of those. Type, images, symbols, blends, meshes and the rest have to be converted to
/// paths first (<https://helpx.adobe.com/illustrator/desktop/paint-and-fill/learn-painting-basics/create-live-paint-groups.html>);
/// Make and Merge refuse them rather than hide them among the group's sources.
pub fn live_paint_takes(n: &Node) -> bool {
    is_live_paint(n)
        || match &n.kind {
            NodeKind::Path { .. } | NodeKind::Compound { .. } => true,
            NodeKind::Group { children, .. } => children.iter().all(|c| live_paint_takes(c)),
            _ => false,
        }
}

fn named(n: &Node, name: &str) -> bool {
    n.name.as_deref() == Some(name)
}

/// Is `n` a Live Paint group's part named `name` ([`FACE_NAME`] or [`EDGE_NAME`]): a path with that
/// name? Type, groups and other objects drawn in the group under such a name are not parts.
fn part(n: &Node, name: &str) -> bool {
    named(n, name) && n.path_data().is_some()
}

/// Face children of a Live Paint group (paint order).
pub fn faces(group: &Node) -> Vec<&Arc<Node>> {
    group.children().map(|c| c.iter().filter(|n| part(n, FACE_NAME)).collect()).unwrap_or_default()
}

/// Edge children of a Live Paint group.
pub fn edges(group: &Node) -> Vec<&Arc<Node>> {
    group.children().map(|c| c.iter().filter(|n| part(n, EDGE_NAME)).collect()).unwrap_or_default()
}

/// The hidden sources group of a Live Paint group.
pub fn sources(group: &Node) -> Option<&Arc<Node>> {
    group.children()?.iter().find(|n| named(n, SOURCES_NAME))
}

/// Does the path (filled) contain `p`?
pub fn path_contains(path: &PathData, rule: FillRule, p: Point) -> bool {
    if path.bounds().is_none_or(|b| !b.inflate(1e-6, 1e-6).contains(p)) {
        return false;
    }
    let w = path.to_bezpath().winding(p);
    match rule {
        FillRule::EvenOdd => w % 2 != 0,
        _ => w != 0,
    }
}

/// The face of `group` under `p` (front-most).
pub fn face_at(group: &Node, p: Point) -> Option<&Arc<Node>> {
    front_face(faces(group).into_iter(), p)
}

/// The face of `group` under `p` (front-most) among its faces that are not hidden.
pub fn visible_face_at(group: &Node, p: Point) -> Option<&Arc<Node>> {
    front_face(faces(group).into_iter().filter(|f| f.visible), p)
}

/// The face of `faces` (paint order) under `p` (front-most).
fn front_face<'a>(faces: impl DoubleEndedIterator<Item = &'a Arc<Node>>, p: Point) -> Option<&'a Arc<Node>> {
    faces.rev().find(|f| f.path_data().is_some_and(|pd| path_contains(pd, FillRule::NonZero, p)))
}

/// The edge of `group` nearest to `p` within `tol`.
pub fn edge_near(group: &Node, p: Point, tol: f64) -> Option<&Arc<Node>> {
    nearest_edge(edges(group), p, tol)
}

/// The edge of `group` nearest to `p` within `tol` among its edges that are not hidden.
pub fn visible_edge_near(group: &Node, p: Point, tol: f64) -> Option<&Arc<Node>> {
    nearest_edge(edges(group).into_iter().filter(|e| e.visible), p, tol)
}

/// The edges of `group` that are not hidden and that the polyline through the points of each chunk
/// of `chunks` crosses or comes within [`LP_JOIN_TOL`] of, each once, in the group's order. Each
/// stretch of the polyline tests only the edge segments whose bounds lie near it.
pub fn visible_edges_along<'a>(group: &'a Node, chunks: &[Vec<Point>]) -> Vec<&'a Arc<Node>> {
    use kurbo::ParamCurveNearest as _;
    let shown: Vec<&Arc<Node>> = edges(group).into_iter().filter(|e| e.visible).collect();
    // Each edge segment, with the index in `shown` of its edge.
    let mut owner: Vec<usize> = vec![];
    let mut segs: Vec<(kurbo::CubicBez, bool)> = vec![];
    for (i, e) in shown.iter().enumerate() {
        for s in e.path_data().map(lp_segments).unwrap_or_default() {
            owner.push(i);
            segs.push((s, true));
        }
    }
    if segs.is_empty() {
        return vec![];
    }
    let grid = LpEdgeGrid::new(&segs);
    let close = LP_JOIN_TOL * LP_JOIN_TOL;
    let mut hit = vec![false; shown.len()];
    for chunk in chunks {
        for pair in chunk.windows(2) {
            let &[a, b] = pair else { continue };
            let line = kurbo::Line::new(a, b);
            let on_line = |p: Point| line.nearest(p, 1e-9).distance_sq <= close;
            for k in grid.near_box(Rect::from_points(a, b).inflate(LP_JOIN_TOL, LP_JOIN_TOL)) {
                let (Some((c, _)), Some(&i)) = (segs.get(k), owner.get(k)) else { continue };
                let Some(h) = hit.get_mut(i) else { continue };
                if *h {
                    continue;
                }
                let on_seg = |p: Point| c.nearest(p, 1e-9).distance_sq <= close;
                // An end of either one on the other covers a touch and a stretch that runs along
                // the edge, where no single crossing point exists. Where neither crosses the other,
                // their closest points are ends or a point of the edge where it runs parallel to
                // the drag. A crossing kurbo finds just before or after an end of the edge counts
                // only through the checks on that end.
                *h = on_seg(a)
                    || on_seg(b)
                    || on_line(c.p0)
                    || on_line(c.p3)
                    || (a != b
                        && (kurbo::PathSeg::Cubic(*c).intersect_line(line).iter().any(|x| (0.0..=1.0).contains(&x.segment_t))
                            || lp_parallel_at(c, b - a).into_iter().any(|t| on_line(kurbo::ParamCurve::eval(c, t)))));
            }
        }
    }
    shown.into_iter().zip(hit).filter_map(|(e, h)| h.then_some(e)).collect()
}

/// The parameters strictly between 0 and 1 where cubic `c` runs parallel to direction `d`: the
/// roots of the cross product of its derivative with `d`.
fn lp_parallel_at(c: &kurbo::CubicBez, d: kurbo::Vec2) -> Vec<f64> {
    let [a, b, e] = [c.p1 - c.p0, c.p2 - c.p1, c.p3 - c.p2].map(|v| v.cross(d));
    // a(1-t)² + 2b·t(1-t) + e·t², expanded in powers of t.
    kurbo::common::solve_quadratic(a, 2.0 * (b - a), a - 2.0 * b + e).into_iter().filter(|t| t.is_finite() && *t > 0.0 && *t < 1.0).collect()
}

/// The edge of `edges` nearest to `p` within `tol`.
fn nearest_edge<'a>(edges: impl IntoIterator<Item = &'a Arc<Node>>, p: Point, tol: f64) -> Option<&'a Arc<Node>> {
    let mut best: Option<(f64, &Arc<Node>)> = None;
    for e in edges {
        if let Some((.., d)) = e.path_data().and_then(|pd| pd.nearest(p))
            && d <= tol
            && best.is_none_or(|b| d < b.0)
        {
            best = Some((d, e));
        }
    }
    best.map(|b| b.1)
}

/// The greatest distance (pt) between the ends of two Live Paint edges that the Live Paint tools take
/// as one point. Every edge comes from one planar map, so their ends meet this closely.
pub const LP_JOIN_TOL: f64 = 1e-4;

/// The greatest distance (pt) between the middle of a Live Paint face's outline segment and an edge
/// it runs along. The planar map refits outlines to [`vectorcraft_pathops::DEFAULT_PRECISION`],
/// keeping each refit segment's ends, and with Gap Detection on, the faces and the edges come from
/// two maps, so an outline can lie that far off its edges between its ends.
const LP_FACE_EDGE_TOL: f64 = vectorcraft_pathops::DEFAULT_PRECISION;

/// The cell [`LP_JOIN_TOL`] wide that holds `p`, for finding the points near it; two points within
/// [`LP_JOIN_TOL`] of each other lie in the same or neighboring cells. The cast saturates, so a
/// coordinate too large or not finite does not overflow.
fn lp_cell(p: Point) -> (i64, i64) {
    ((p.x / LP_JOIN_TOL).round() as i64, (p.y / LP_JOIN_TOL).round() as i64)
}

/// The cell that holds `p` ([`lp_cell`]) and the eight cells around it.
fn lp_cells_around(p: Point) -> impl Iterator<Item = (i64, i64)> {
    let (x, y) = lp_cell(p);
    (-1..=1).flat_map(move |dx: i64| (-1..=1).map(move |dy: i64| (x.saturating_add(dx), y.saturating_add(dy))))
}

/// The stroke paint Live Paint edge `edge` draws with: the paint of its topmost stroke that is shown
/// with a paint, a weight above 0 and an opacity above 0, or [`Paint::None`] when the edge is fully
/// transparent or has no such stroke.
pub fn lp_stroke_paint(edge: &Node) -> Paint {
    if edge.opacity <= 0.0 {
        return Paint::None;
    }
    edge.appearance
        .items
        .iter()
        .rev()
        .find_map(|i| match i {
            vectorcraft_doc::appearance::AppearanceItem::Stroke(s) if s.visible && !s.paint.is_none() && s.width > 0.0 && s.opacity > 0.0 => {
                Some(s.paint.clone())
            }
            _ => None,
        })
        .unwrap_or(Paint::None)
}

/// Whether Live Paint edge `edge` draws no stroke ([`lp_stroke_paint`] is [`Paint::None`]).
fn unstroked(edge: &Node) -> bool {
    lp_stroke_paint(edge).is_none()
}

/// The segments of `pd`.
fn lp_segments(pd: &PathData) -> Vec<kurbo::CubicBez> {
    pd.subpaths.iter().flat_map(|sp| (0..sp.segment_count()).map(|i| sp.segment(i))).collect()
}

/// The faces of Live Paint group `group` that a flood from face `start` reaches, `start` first:
/// `start`, and each face that shares with a face already reached an edge that is hidden or draws
/// no stroke. Hidden faces are not reached and do not pass the flood on. A face runs along the parts
/// of the edge segments its outline segments lie on ([`lp_lies_on`]) or overlap ([`lp_overlap`]).
/// Two faces share an edge where those parts overlap along more than [`LP_FACE_EDGE_TOL`], or, where
/// both outlines lie within [`LP_JOIN_TOL`] of the edge, along more than half the shorter part. So
/// two faces that a Gap Detection gap parts on the same side of an edge, whose parts only touch, do
/// not share it, and two faces whose shared edge is shorter than [`LP_FACE_EDGE_TOL`] do. Empty when
/// `start` is not a face of `group` that is not hidden.
pub fn flood_faces(group: &Node, start: NodeId) -> Vec<NodeId> {
    use kurbo::{ParamCurve, ParamCurveArclen};
    use std::collections::{HashMap, HashSet};
    let shown: Vec<&Arc<Node>> = faces(group).into_iter().filter(|f| f.visible).collect();
    if !shown.iter().any(|f| f.id == start) {
        return vec![];
    }
    // Each edge segment, and whether a flood crosses it.
    let edge_segs: Vec<(kurbo::CubicBez, bool)> = edges(group)
        .into_iter()
        .flat_map(|e| {
            let cross = !e.visible || unstroked(e);
            e.path_data().map(lp_segments).unwrap_or_default().into_iter().map(move |s| (s, cross))
        })
        .collect();
    // The faces along each edge segment a flood crosses, each with the part of the segment it runs
    // along (from and to, in the segment's own parameter). A face outline segment usually lies on
    // one edge segment, stroked or not ([`lp_lies_on`]); one that does not (a piece of an edge
    // segment where a Gap Detection line meets it, the line itself, or an outline segment that spans
    // several edge segments) is measured against the edge segments a flood crosses that its bounds
    // meet ([`lp_overlap`]). Each part also records whether its outline segment lies within
    // [`LP_JOIN_TOL`] of it ([`lp_close`]).
    let all: Vec<(kurbo::CubicBez, bool)> = edge_segs.iter().map(|&(s, _)| (s, true)).collect();
    let all_grid = LpEdgeGrid::new(&all);
    let mut along: HashMap<usize, Vec<(NodeId, f64, f64, bool)>> = HashMap::new();
    let mut pieces: Vec<(kurbo::CubicBez, NodeId)> = vec![];
    for f in &shown {
        for piece in f.path_data().map(lp_segments).unwrap_or_default() {
            let m = piece.eval(0.5);
            let bounds = kurbo::ParamCurveExtrema::bounding_box(&piece).inflate(LP_FACE_EDGE_TOL, LP_FACE_EDGE_TOL);
            // The edge segment the outline segment lies on whose middle is nearest its own.
            let on = all_grid
                .near_box(bounds)
                .into_iter()
                .filter_map(|k| edge_segs.get(k).and_then(|(s, cross)| lp_lies_on(s, &piece).map(|part| (k, s, *cross, part))))
                .min_by(|x, y| (x.1.eval(0.5) - m).hypot().total_cmp(&(y.1.eval(0.5) - m).hypot()));
            match on {
                Some((k, s, cross, (from, to))) => {
                    if cross {
                        along.entry(k).or_default().push((f.id, from, to, lp_close(s, from, to, &piece)));
                    }
                }
                None => pieces.push((piece, f.id)),
            }
        }
    }
    if !pieces.is_empty() {
        let grid = LpEdgeGrid::new(&edge_segs);
        for (piece, id) in pieces {
            let bounds = kurbo::ParamCurveExtrema::bounding_box(&piece).inflate(LP_FACE_EDGE_TOL, LP_FACE_EDGE_TOL);
            for k in grid.near_box(bounds) {
                if let Some((s, true)) = edge_segs.get(k)
                    && let Some((a, c)) = lp_overlap(s, &piece)
                {
                    along.entry(k).or_default().push((id, a, c, lp_close(s, a, c, &piece)));
                }
            }
        }
    }
    let mut next: HashMap<NodeId, Vec<NodeId>> = HashMap::new();
    // Sorted by where each part starts, a part is compared only with the parts after it that start
    // before it ends. Two parts that overlap along [`LP_FACE_EDGE_TOL`] or less join only when both
    // lie within [`LP_JOIN_TOL`] of the edge and the overlap is more than half the shorter part: an
    // edge that short is shared, while an outline that only crosses it lies off it.
    for (k, on) in &mut along {
        let Some((s, _)) = edge_segs.get(*k) else { continue };
        on.sort_by(|x, y| x.1.total_cmp(&y.1));
        for (i, &(a, a0, a1, a_close)) in on.iter().enumerate() {
            for &(c, c0, c1, c_close) in on.iter().skip(i + 1).take_while(|x| x.1 < a1) {
                let (from, to) = (a0.max(c0), a1.min(c1));
                let len = |x: f64, y: f64| s.subsegment(x..y).arclen(1e-6);
                let shared = if a != c && from < to { len(from, to) } else { 0.0 };
                let short_shared = a_close && c_close && shared > 0.5 * len(a0, a1).min(len(c0, c1));
                if shared > 0.0 && (shared > LP_FACE_EDGE_TOL || short_shared) {
                    next.entry(a).or_default().push(c);
                    next.entry(c).or_default().push(a);
                }
            }
        }
    }
    let mut reached = vec![start];
    let mut seen = HashSet::from([start]);
    let mut i = 0;
    while let Some(&f) = reached.get(i) {
        i += 1;
        for &n in next.get(&f).map(Vec::as_slice).unwrap_or_default() {
            if seen.insert(n) {
                reached.push(n);
            }
        }
    }
    reached
}

/// The part of edge segment `s` that outline segment `piece` runs along, as (from, to) in `s`'s
/// own parameter, or None when they share no length. The part runs between the ends of `s` that lie
/// within [`LP_FACE_EDGE_TOL`] of `piece` and the ends of `piece` that lie within [`LP_JOIN_TOL`] of
/// `s` (the map keeps the ends of an outline segment it refits), and its middle lies within
/// [`LP_FACE_EDGE_TOL`] of `piece`, where the two run along each other ([`lp_runs_along`]). When no
/// end of `piece` lies on `s`, `piece` must lie within [`LP_JOIN_TOL`] of the part ([`lp_close`]). So
/// two segments that only cross or touch, or that only lie near each other, share nothing.
fn lp_overlap(s: &kurbo::CubicBez, piece: &kurbo::CubicBez) -> Option<(f64, f64)> {
    use kurbo::{ParamCurve, ParamCurveNearest};
    let on_piece = |p: Point| piece.nearest(p, 1e-9).distance_sq.sqrt() <= LP_FACE_EDGE_TOL;
    let mut ts: Vec<f64> = [(s.p0, 0.0), (s.p3, 1.0)].into_iter().filter(|(p, _)| on_piece(*p)).map(|(_, t)| t).collect();
    let mut piece_end_on = false;
    for p in [piece.p0, piece.p3] {
        let n = s.nearest(p, 1e-9);
        if n.distance_sq.sqrt() <= LP_JOIN_TOL {
            ts.push(n.t);
            piece_end_on = true;
        }
    }
    let from = ts.iter().copied().fold(f64::INFINITY, f64::min);
    let to = ts.iter().copied().fold(f64::NEG_INFINITY, f64::max);
    if from >= to {
        return None;
    }
    let mid = (from + to) / 2.0;
    let n = piece.nearest(s.eval(mid), 1e-9);
    let along = if piece_end_on { lp_runs_along(s, from, to, piece, mid, n.t) } else { lp_close(s, from, to, piece) };
    (n.distance_sq.sqrt() <= LP_FACE_EDGE_TOL && along).then_some((from, to))
}

/// The part of edge segment `s` that outline segment `piece` lies on as a whole, as (from, to) in
/// `s`'s own parameter: both ends of `piece` lie within [`LP_JOIN_TOL`] of `s`, its middle lies
/// within [`LP_FACE_EDGE_TOL`] of `s`, and the two run along each other ([`lp_runs_along`]).
fn lp_lies_on(s: &kurbo::CubicBez, piece: &kurbo::CubicBez) -> Option<(f64, f64)> {
    use kurbo::{ParamCurve, ParamCurveNearest};
    let (a, c, m) = (s.nearest(piece.p0, 1e-9), s.nearest(piece.p3, 1e-9), s.nearest(piece.eval(0.5), 1e-9));
    let (from, to) = (a.t.min(c.t), a.t.max(c.t));
    let near = a.distance_sq.sqrt() <= LP_JOIN_TOL && c.distance_sq.sqrt() <= LP_JOIN_TOL && m.distance_sq.sqrt() <= LP_FACE_EDGE_TOL;
    (near && lp_runs_along(s, from, to, piece, m.t, 0.5)).then_some((from, to))
}

/// Whether outline segment `piece` runs along the part of edge segment `s` from `from` to `to`
/// rather than crossing it: it lies within [`LP_JOIN_TOL`] of that part ([`lp_close`]), or the two
/// run the same way or opposite ways at `ts` on `s` and `tp` on `piece` ([`lp_parallel`]).
fn lp_runs_along(s: &kurbo::CubicBez, from: f64, to: f64, piece: &kurbo::CubicBez, ts: f64, tp: f64) -> bool {
    lp_close(s, from, to, piece) || lp_parallel(s, ts, piece, tp)
}

/// Whether outline segment `piece` lies within [`LP_JOIN_TOL`] of edge segment `s` at the ends and
/// the middle of the part of `s` from `from` to `to`.
fn lp_close(s: &kurbo::CubicBez, from: f64, to: f64, piece: &kurbo::CubicBez) -> bool {
    use kurbo::{ParamCurve, ParamCurveNearest};
    [from, (from + to) / 2.0, to].into_iter().all(|t| piece.nearest(s.eval(t), 1e-9).distance_sq.sqrt() <= LP_JOIN_TOL)
}

/// Whether segment `s` at parameter `ts` and segment `piece` at parameter `tp` run the same way or
/// opposite ways: the sine of the angle between their directions there is at most 0.2. False where
/// either has no direction.
fn lp_parallel(s: &kurbo::CubicBez, ts: f64, piece: &kurbo::CubicBez, tp: f64) -> bool {
    use kurbo::{ParamCurve, ParamCurveDeriv};
    let (u, v) = (s.deriv().eval(ts).to_vec2(), piece.deriv().eval(tp).to_vec2());
    let n = u.hypot() * v.hypot();
    n > 0.0 && u.cross(v).abs() <= 0.2 * n
}

/// Most grid cells one edge segment is listed in by [`LpEdgeGrid`]; a longer one is tried for
/// every point.
const LP_GRID_SPAN: i64 = 1024;

/// The farthest cell from the grid's origin, on each axis, that [`LpEdgeGrid`] numbers a point in.
const LP_GRID_LIMIT: f64 = 1_048_576.0;

/// The edge segments a flood crosses, by the cells of a square grid (about one cell per segment)
/// that their bounds, widened by [`LP_FACE_EDGE_TOL`], cover.
struct LpEdgeGrid {
    origin: Point,
    cell: f64,
    /// Segment indices by cell.
    cells: std::collections::HashMap<(i64, i64), Vec<usize>>,
    /// Segments whose bounds cover more than [`LP_GRID_SPAN`] cells, near every point.
    wide: Vec<usize>,
}

impl LpEdgeGrid {
    /// The grid of the segments of `edges` that a flood crosses (those marked true).
    fn new(edges: &[(kurbo::CubicBez, bool)]) -> Self {
        let boxes: Vec<(usize, Rect)> = edges
            .iter()
            .enumerate()
            .filter(|(_, e)| e.1)
            .map(|(k, (s, _))| (k, kurbo::ParamCurveExtrema::bounding_box(s).inflate(LP_FACE_EDGE_TOL, LP_FACE_EDGE_TOL)))
            .collect();
        let all = boxes.iter().map(|b| b.1).reduce(|a, c| a.union(c)).unwrap_or_default();
        let side = (boxes.len() as f64).sqrt().ceil().max(1.0);
        let cell = all.width().max(all.height()) / side;
        let cell = if cell.is_finite() && cell > LP_FACE_EDGE_TOL { cell } else { LP_FACE_EDGE_TOL };
        let mut grid = Self { origin: all.origin(), cell, cells: std::collections::HashMap::new(), wide: vec![] };
        for (k, b) in boxes {
            let ((x0, y0), (x1, y1)) = (grid.cell_of(Point::new(b.x0, b.y0)), grid.cell_of(Point::new(b.x1, b.y1)));
            if (x1 - x0 + 1).saturating_mul(y1 - y0 + 1) > LP_GRID_SPAN {
                grid.wide.push(k);
                continue;
            }
            for x in x0..=x1 {
                for y in y0..=y1 {
                    grid.cells.entry((x, y)).or_default().push(k);
                }
            }
        }
        grid
    }

    /// The cell `p` is in, counted from the origin (at most [`LP_GRID_LIMIT`] cells away on each
    /// axis).
    fn cell_of(&self, p: Point) -> (i64, i64) {
        let at = |v: f64, o: f64| ((v - o) / self.cell).floor().clamp(-LP_GRID_LIMIT, LP_GRID_LIMIT) as i64;
        (at(p.x, self.origin.x), at(p.y, self.origin.y))
    }

    /// The segments whose widened bounds may meet `r`, each once, in ascending order. When `r`
    /// covers more than [`LP_GRID_SPAN`] cells, every listed segment is returned.
    fn near_box(&self, r: Rect) -> Vec<usize> {
        let ((x0, y0), (x1, y1)) = (self.cell_of(Point::new(r.x0, r.y0)), self.cell_of(Point::new(r.x1, r.y1)));
        let mut out: Vec<usize> = self.wide.clone();
        if (x1 - x0 + 1).saturating_mul(y1 - y0 + 1) > LP_GRID_SPAN {
            out.extend(self.cells.values().flatten());
        } else {
            for x in x0..=x1 {
                for y in y0..=y1 {
                    out.extend(self.cells.get(&(x, y)).into_iter().flatten());
                }
            }
        }
        out.sort_unstable();
        out.dedup();
        out
    }
}

/// The edges of Live Paint group `group` that are not hidden and are joined to edge `start` through
/// edges that draw with stroke paint `paint` ([`lp_stroke_paint`]), `start` first: `start`, and each
/// edge that draws with that stroke paint and has an end (the first or last point of one of its subpaths) within [`LP_JOIN_TOL`] of an
/// end of an edge already reached.
/// Empty when `start` is not an edge of `group` that is not hidden.
pub fn connected_edges(group: &Node, start: NodeId, paint: &Paint) -> Vec<NodeId> {
    connected_edges_through(group, start, paint, &[])
}

/// [`connected_edges`], with the edges in `through` counted as drawing with stroke paint `paint`
/// whatever paint they draw with now.
pub fn connected_edges_through(group: &Node, start: NodeId, paint: &Paint, through: &[NodeId]) -> Vec<NodeId> {
    use std::collections::{HashMap, HashSet};
    let es: Vec<&Arc<Node>> =
        edges(group).into_iter().filter(|e| e.visible && (e.id == start || through.contains(&e.id) || lp_stroke_paint(e) == *paint)).collect();
    // The first and last points of each subpath of each edge.
    let ends: Vec<Vec<Point>> = es
        .iter()
        .map(|e| {
            let Some(pd) = e.path_data() else { return vec![] };
            pd.subpaths
                .iter()
                .filter_map(|sp| {
                    let n = sp.segment_count();
                    (n > 0).then(|| [sp.segment(0).p0, sp.segment(n - 1).p3])
                })
                .flatten()
                .collect()
        })
        .collect();
    let mut at: HashMap<(i64, i64), Vec<(Point, usize)>> = HashMap::new();
    for (i, pts) in ends.iter().enumerate() {
        for &p in pts {
            at.entry(lp_cell(p)).or_default().push((p, i));
        }
    }
    let Some(first) = es.iter().position(|e| e.id == start) else { return vec![] };
    let mut reached = vec![first];
    let mut seen = HashSet::from([first]);
    let mut k = 0;
    while let Some(&i) = reached.get(k) {
        k += 1;
        for &p in ends.get(i).map(Vec::as_slice).unwrap_or_default() {
            for c in lp_cells_around(p) {
                for &(q, j) in at.get(&c).map(Vec::as_slice).unwrap_or_default() {
                    if (q - p).hypot() <= LP_JOIN_TOL && seen.insert(j) {
                        reached.push(j);
                    }
                }
            }
        }
    }
    reached.into_iter().filter_map(|i| es.get(i).map(|e| e.id)).collect()
}

/// The visible Live Paint group with a face under `p` that is not hidden (front-most in paint order).
pub fn live_paint_at(doc: &Document, p: Point) -> Option<NodeId> {
    live_paint_at_where(doc, p, |id| doc.is_visible(id))
}

/// [`live_paint_at`] among the Live Paint groups for which `takes` is true.
pub(super) fn live_paint_at_where(doc: &Document, p: Point, takes: impl Fn(NodeId) -> bool) -> Option<NodeId> {
    let mut hit = None;
    doc.walk(|n| {
        if is_live_paint(n) && visible_face_at(n, p).is_some() && takes(n.id) {
            hit = Some(n.id);
        }
    });
    hit
}

/// Paths, compound paths (as one shape) of a subtree in paint order; guides, clipping paths and
/// hidden objects are skipped. Live Paint groups contribute their faces and edges.
pub fn leaf_shapes<'a>(n: &'a Node, out: &mut Vec<&'a Node>) {
    collect_leaves(n, false, out);
}

/// [`leaf_shapes`]; with `builder` (the Shape Builder's inputs), a Live Paint group contributes
/// only its filled faces and its stroked edges, and locked objects contribute nothing.
fn collect_leaves<'a>(n: &'a Node, builder: bool, out: &mut Vec<&'a Node>) {
    collect_members(n, builder, out);
    if builder {
        out.retain(|m| m.visible && !m.locked);
    }
}

/// The leaves the Shape Builder takes from `n` ([`collect_leaves`]), in paint order, with each
/// hidden or locked object it skips in its place.
pub fn builder_members(n: &Node) -> Vec<&Node> {
    let mut out = vec![];
    collect_members(n, true, &mut out);
    out
}

/// [`collect_leaves`] with, for `builder`, each hidden or locked object in place of what it holds.
fn collect_members<'a>(n: &'a Node, builder: bool, out: &mut Vec<&'a Node>) {
    if !n.visible && !builder {
        return;
    }
    if builder && (!n.visible || n.locked) {
        out.push(n);
        return;
    }
    if n.extras().shaper.is_some() {
        for c in n.children().into_iter().flatten().skip(1) {
            collect_members(c, builder, out);
        }
        return;
    }
    match &n.kind {
        NodeKind::Path { guide: true, .. } | NodeKind::Path { clipping: true, .. } => {}
        NodeKind::Path { .. } | NodeKind::Compound { .. } => out.push(n),
        NodeKind::Group { .. } if builder && is_live_paint(n) => {
            out.extend(faces(n).into_iter().filter(|f| !f.visible || f.locked || (f.opacity > 0.0 && f.appearance.has_drawn_fill())).map(|f| &**f));
            out.extend(edges(n).into_iter().filter(|e| !e.visible || e.locked || (e.opacity > 0.0 && e.appearance.has_drawn_stroke())).map(|e| &**e));
        }
        NodeKind::Group { children, .. } | NodeKind::Layer { children, .. } => {
            for c in children {
                collect_members(c, builder, out);
            }
        }
        _ => {}
    }
}

/// Filled outline of a path or compound path node.
pub fn node_outline(n: &Node) -> Option<(PathData, FillRule)> {
    match &n.kind {
        NodeKind::Path { path, rule, .. } => Some((path.clone(), *rule)),
        NodeKind::Compound { children, rule } => {
            let subs = children.iter().filter_map(|c| c.path_data()).flat_map(|p| p.subpaths.iter().cloned()).collect();
            Some((PathData::new(subs), *rule))
        }
        _ => None,
    }
}

/// How far (pt) a piece of the planar map may lie from `outline`, the outline it follows, to be
/// matched to it or cut out of it: a ten-thousandth of the outline's larger side, at least 0.05.
/// The map's pieces follow the outlines to within a few hundredths of a point.
pub fn outline_snap(outline: &PathData) -> f64 {
    outline.bounds().map_or(0.05, |b| (b.width().max(b.height()) / 2000.0).max(0.25) * 0.2)
}

/// The outlines of `leaves` as they are drawn ([`node_outline`]), in their order, for
/// [`BuilderMap::stroke_at`]. A leaf without an outline, and one inside a Live Paint group or a
/// Shaper Group (which make their own paths), gets an empty outline, so no stroke of it splits.
pub fn drawn_outlines(doc: &Document, leaves: &[&Node]) -> Vec<PathData> {
    let in_live_group = |id: NodeId| {
        let mut up = doc.parent_of(id);
        while let Some(p) = up {
            if doc.node(p).is_some_and(|n| is_live_paint(n) || n.extras().shaper.is_some()) {
                return true;
            }
            up = doc.parent_of(p);
        }
        false
    };
    leaves.iter().map(|l| if in_live_group(l.id) { None } else { node_outline(l) }.map_or_else(PathData::default, |o| o.0)).collect()
}

/// Pathfinder shapes for the given roots (back → front by the order given), keyed by leaf index,
/// with the leaves they came from.
pub fn shapes_for<'a>(doc: &'a Document, roots: &[NodeId]) -> (Vec<po::Shape>, Vec<&'a Node>) {
    shapes_of(doc, roots, false)
}

/// [`shapes_for`]; with `builder`, the leaves [`collect_leaves`] takes for the Shape Builder, and
/// nothing from a root in a locked or hidden group or layer.
fn shapes_of<'a>(doc: &'a Document, roots: &[NodeId], builder: bool) -> (Vec<po::Shape>, Vec<&'a Node>) {
    let mut lv = vec![];
    for id in roots {
        if let Some(n) = doc.node(*id)
            && (!builder || doc.is_editable(*id))
        {
            collect_leaves(n, builder, &mut lv);
        }
    }
    let mut shapes = vec![];
    let mut used = vec![];
    for l in lv {
        if let Some((p, r)) = node_outline(l)
            && !p.is_empty()
            && p.subpaths.iter().all(|s| s.anchors.iter().all(|a| a.p.x.is_finite() && a.p.y.is_finite()))
        {
            shapes.push(po::Shape::new(p, r, used.len() as u64));
            used.push(l);
        }
    }
    (shapes, used)
}

/// Shape Builder inputs: [`shapes_for`], with the open subpaths of filled paths closed where that
/// encloses an area (the fill bounds a region, as if an invisible edge closed it) when
/// `open_filled_as_closed`. Unfilled open paths and straight lines stay open and cut the regions
/// they cross, and so do filled open paths without `open_filled_as_closed`. A path, face or edge
/// counts as filled or stroked when any of its fill or stroke rows draws
/// ([`vectorcraft_doc::Appearance::has_drawn_fill`], [`vectorcraft_doc::Appearance::has_drawn_stroke`]),
/// whichever row is on top. A Live Paint group contributes its filled faces as shapes and its
/// stroked edges as open lines; its unfilled faces, its edges without a stroke, and its faces and
/// edges whose own opacity is 0 are left out. Locked objects, and objects in a locked group or
/// layer, give nothing.
pub fn shape_builder_shapes<'a>(doc: &'a Document, roots: &[NodeId], open_filled_as_closed: bool) -> (Vec<po::Shape>, Vec<&'a Node>) {
    let (mut shapes, leaves) = shapes_of(doc, roots, true);
    for (s, l) in shapes.iter_mut().zip(&leaves) {
        if named(l, EDGE_NAME) && doc.parent_of(l.id).and_then(|p| doc.node(p)).is_some_and(is_live_paint) {
            // A closed edge opens at its first anchor and keeps its closing segment.
            let start = BTreeSet::from([0]);
            s.path.subpaths = s.path.subpaths.iter().flat_map(|sp| sp.cut_at(&start)).collect();
            continue;
        }
        if !open_filled_as_closed || !l.appearance.has_drawn_fill() {
            continue;
        }
        for sp in s.path.subpaths.iter_mut().filter(|sp| !sp.closed) {
            sp.closed = po::encloses_area(sp);
        }
    }
    (shapes, leaves)
}

/// A planar-map face with its outline and bounds, ready for hit tests.
pub type Face = (po::Region, BezPath, Rect);

pub(super) fn faces_of(regions: Vec<po::Region>) -> Vec<Face> {
    regions
        .into_iter()
        .filter_map(|r| {
            let bp = r.path.to_bezpath();
            let b = r.path.bounds()?;
            Some((r, bp, b))
        })
        .collect()
}

thread_local! {
    /// The Shape Builder maps built on this thread ([`maps_built`]).
    pub(super) static MAPS_BUILT: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
    /// The Shape Builder merges computed on this thread ([`merges_computed`]).
    pub(super) static MERGES_COMPUTED: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
}