GitCorner

Code

ossartcraftvectorcraft🌐
2bc41aeb8602
#[cfg(test)]
use super::PathData;
use super::{BezPath, LayoutOptions, PathEl, Point, Rect, Shape};

/// A flattened text wrap shape: (polygons, offset, invert).
pub(super) type FlatWrap = (Vec<Vec<Point>>, f64, bool);

/// One cell of a flattened area-type frame (the whole frame, or one row/column of it).
pub(super) struct Region {
    /// The cell (frame bounds, or a grid cell of them).
    pub(super) cell: Rect,
    /// Inset applied inside the frame edges.
    inset: f64,
    pub(super) polys: std::sync::Arc<[Vec<Point>]>,
    /// The frame is its own bounding rectangle (spans need no polygon intersection).
    pub(super) rect: bool,
    /// Text Wrap shapes.
    pub(super) wraps: std::sync::Arc<[FlatWrap]>,
    /// Vertical alignment: how far below the top-aligned position the first line starts.
    pub(super) shift: f64,
    /// Vertical justification: extra space added between consecutive lines.
    pub(super) gap: f64,
}

/// The largest magnitude a coordinate of a frame, a text wrap shape or the path of type on a path
/// may have (points), control points included. A frame or path with a larger coordinate, or a
/// coordinate that isn't finite, holds no text, and a text wrap shape with one is ignored.
const MAX_COORD: f64 = 1e9;

/// Are the coordinates of `path`, control points included, finite and within [`MAX_COORD`]?
pub(super) fn in_range(path: &BezPath) -> bool {
    let near = |p: &Point| p.x.abs() <= MAX_COORD && p.y.abs() <= MAX_COORD;
    path.elements().iter().all(|el| match el {
        PathEl::MoveTo(p) | PathEl::LineTo(p) => near(p),
        PathEl::QuadTo(a, p) => near(a) && near(p),
        PathEl::CurveTo(a, b, p) => near(a) && near(b) && near(p),
        PathEl::ClosePath => true,
    })
}

/// Flattened closed polygons of a path; `None` when it isn't [`in_range`].
fn polygons(path: &BezPath) -> Option<Vec<Vec<Point>>> {
    if !in_range(path) {
        return None;
    }
    let mut polys: Vec<Vec<Point>> = Vec::new();
    kurbo::flatten(path, 0.1, |el| match el {
        PathEl::MoveTo(p) => polys.push(vec![p]),
        PathEl::LineTo(p) => {
            if let Some(v) = polys.last_mut() {
                v.push(p);
            }
        }
        _ => {}
    });
    polys.retain(|p| p.len() >= 3);
    Some(polys)
}

/// Inside intervals (even-odd) of the horizontal line at `y` through `polys`.
fn poly_intervals(polys: &[Vec<Point>], y: f64) -> Vec<(f64, f64)> {
    let mut xs = Vec::new();
    for poly in polys {
        for i in 0..poly.len() {
            let a = poly[i];
            let b = poly[(i + 1) % poly.len()];
            if (a.y <= y) != (b.y <= y) {
                xs.push(a.x + (y - a.y) / (b.y - a.y) * (b.x - a.x));
            }
        }
    }
    xs.sort_by(f64::total_cmp);
    xs.as_chunks::<2>().0.iter().map(|c| (c[0], c[1])).collect()
}

/// The part of the horizontal line at `y` closer than `r` to the segment `a`–`b`: the line's
/// intersection with the segment's two end disks and the band between them, which together make
/// a convex shape, so the result is one interval.
fn near_segment(a: Point, b: Point, y: f64, r: f64) -> Option<(f64, f64)> {
    if y <= a.y.min(b.y) - r || y >= a.y.max(b.y) + r {
        return None;
    }
    let (mut lo, mut hi) = (f64::INFINITY, f64::NEG_INFINITY);
    for p in [a, b] {
        let h = r * r - (y - p.y) * (y - p.y);
        if h > 0.0 {
            lo = lo.min(p.x - h.sqrt());
            hi = hi.max(p.x + h.sqrt());
        }
    }
    let d = b - a;
    let len = d.hypot();
    if len > 0.0 {
        let n = kurbo::Vec2::new(-d.y, d.x) * (r / len);
        let band = [a + n, b + n, b - n, a - n];
        for i in 0..4 {
            let (p, q) = (band[i], band[(i + 1) % 4]);
            if (p.y <= y) != (q.y <= y) {
                let x = p.x + (y - p.y) / (q.y - p.y) * (q.x - p.x);
                lo = lo.min(x);
                hi = hi.max(x);
            }
        }
    }
    (hi > lo).then_some((lo, hi))
}

/// The x at which some point of the band `top..bottom` (`top <= bottom`) is closer than `r` to the
/// segment `a`–`b`. The points closer than `r` to the segment make a convex shape, so within the
/// band its leftmost and rightmost points lie on the band's top or bottom or beside an end of the
/// segment inside the band, and the result is one interval.
fn near_segment_in_band(a: Point, b: Point, top: f64, bottom: f64, r: f64) -> Option<(f64, f64)> {
    let ends = [a, b].into_iter().filter(|p| p.y >= top && p.y <= bottom).map(|p| (p.x - r, p.x + r));
    let (lo, hi) = [near_segment(a, b, top, r), near_segment(a, b, bottom, r)]
        .into_iter()
        .flatten()
        .chain(ends)
        .fold((f64::INFINITY, f64::NEG_INFINITY), |(lo, hi), (c, d)| (lo.min(c), hi.max(d)));
    (hi > lo).then_some((lo, hi))
}

/// [`band_intervals`] less every x at which some point of the band `top..bottom` is closer than
/// `inset` to an edge of `polys` (holes included), measured from the edge itself. A stretch of an
/// edge that contours meet along bounds no part of the shape, so the inset does not apply beside it.
fn band_inset_intervals(polys: &[Vec<Point>], top: f64, bottom: f64, inset: f64) -> Vec<(f64, f64)> {
    let iv = band_intervals(polys, top, bottom);
    if inset <= 0.0 || iv.is_empty() {
        return iv;
    }
    if !inset.is_finite() {
        return vec![];
    }
    let (top, bottom) = (top.min(bottom), top.max(bottom));
    let edges = boundary_segments(polys, |lo, hi| hi > top - inset && lo < bottom + inset);
    let near = edges.into_iter().filter_map(|(a, b)| near_segment_in_band(a, b, top, bottom, inset));
    subtract_intervals(&iv, &union_intervals(near.collect()))
}

/// The stretches of the edges of `polys` that bound the shape (even-odd), among the edges whose y
/// range `lo..hi` `keep` accepts. Edges that lie exactly along one line and overlap there (contours
/// that meet along an edge, however each one divides it) count by parity, as in
/// [`slant_boundaries`]: a stretch that an even number of them cover has the shape on both sides
/// and is left out. Edges of no length are left out. At most [`MAX_EDGE_PAIRS`] pairs are compared;
/// edges left unpaired count whole.
fn boundary_segments(polys: &[Vec<Point>], keep: impl Fn(f64, f64) -> bool) -> Vec<(Point, Point)> {
    fn root(parent: &mut [usize], mut i: usize) -> usize {
        while parent[i] != i {
            parent[i] = parent[parent[i]];
            i = parent[i];
        }
        i
    }
    let mut edges: Vec<(Point, Point)> = polys
        .iter()
        .flat_map(|p| (0..p.len()).map(move |i| (p[i], p[(i + 1) % p.len()])))
        .filter(|&(a, b)| a != b && keep(a.y.min(b.y), a.y.max(b.y)))
        .collect();
    // Edges along one line overlap in x, so only edges whose x ranges overlap are compared.
    edges.sort_by(|u, v| u.0.x.min(u.1.x).total_cmp(&v.0.x.min(v.1.x)));
    let mut parent: Vec<usize> = (0..edges.len()).collect();
    let mut pairs = 0;
    'edges: for (i, &(p, q)) in edges.iter().enumerate() {
        // The x ranges of edges along one line can differ by rounding, as in `slant_boundaries`.
        let scale = p.x.abs().max(p.y.abs()).max(q.x.abs()).max(q.y.abs()).max(1.0);
        let x1 = p.x.max(q.x) + 4.0 * f64::EPSILON * scale;
        for (j, &(r, s)) in edges.iter().enumerate().skip(i + 1).take_while(|(_, o)| o.0.x.min(o.1.x) <= x1) {
            pairs += 1;
            if pairs > MAX_EDGE_PAIRS {
                break 'edges;
            }
            if on_line_exactly(p, q, r) && on_line_exactly(p, q, s) {
                let (a, b) = (root(&mut parent, i), root(&mut parent, j));
                parent[a] = b;
            }
        }
    }
    let mut groups: Vec<(usize, usize)> = (0..edges.len()).map(|i| (root(&mut parent, i), i)).collect();
    groups.sort_unstable();
    let mut out = Vec::new();
    for run in groups.chunk_by(|a, b| a.0 == b.0) {
        if let [(_, i)] = run {
            out.push(edges[*i]);
            continue;
        }
        // The stretches an odd number of the edges cover: pairs of their ends, sorted along the
        // line by whichever coordinate changes more along it.
        let (p, q) = edges[run[0].1];
        let by_x = (q.x - p.x).abs() >= (q.y - p.y).abs();
        let mut ends: Vec<Point> = run.iter().flat_map(|&(_, i)| [edges[i].0, edges[i].1]).collect();
        ends.sort_by(|a, b| if by_x { a.x.total_cmp(&b.x) } else { a.y.total_cmp(&b.y) });
        out.extend(ends.as_chunks::<2>().0.iter().filter(|c| c[0] != c[1]).map(|c| (c[0], c[1])));
    }
    out
}

/// Union of sorted-or-not intervals.
fn union_intervals(mut v: Vec<(f64, f64)>) -> Vec<(f64, f64)> {
    v.sort_by(|a, b| a.0.total_cmp(&b.0));
    let mut out: Vec<(f64, f64)> = Vec::with_capacity(v.len());
    for (a, b) in v {
        match out.last_mut() {
            Some(l) if a <= l.1 => l.1 = l.1.max(b),
            _ => out.push((a, b)),
        }
    }
    out
}

/// `a` minus `b` (both unions of disjoint intervals, `b` sorted as [`union_intervals`] gives it).
fn subtract_intervals(a: &[(f64, f64)], b: &[(f64, f64)]) -> Vec<(f64, f64)> {
    let mut out = vec![];
    for &(mut s, e) in a {
        // Only the intervals of `b` from the first that ends after `s` to the last that starts
        // before `e` cut into this one.
        for &(c, d) in b[b.partition_point(|&(_, d)| d <= s)..].iter().take_while(|&&(c, _)| c < e) {
            if c > s {
                out.push((s, c));
            }
            s = s.max(d);
        }
        if e > s {
            out.push((s, e));
        }
    }
    out
}

/// `a` ∩ `b` (both sorted left to right, each interval starting no earlier than the one before it
/// ends, as [`union_intervals`] and [`band_intervals`] give them), left to right. It walks both
/// lists once, stepping past whichever current interval ends first (both
/// when they end together), so it looks at no more than `a.len() + b.len()` pairs.
fn intersect_intervals(a: &[(f64, f64)], b: &[(f64, f64)]) -> Vec<(f64, f64)> {
    let mut out = vec![];
    let (mut i, mut j) = (0, 0);
    while let (Some(&(s, e)), Some(&(c, d))) = (a.get(i), b.get(j)) {
        #[cfg(test)]
        INTERSECT_PAIRS.set(INTERSECT_PAIRS.get() + 1);
        let (x, y) = (s.max(c), e.min(d));
        if y > x {
            out.push((x, y));
        }
        // Ends that are equal, or not numbers, step past both, so the walk always ends.
        match e.partial_cmp(&d) {
            Some(std::cmp::Ordering::Less) => i += 1,
            Some(std::cmp::Ordering::Greater) => j += 1,
            _ => (i, j) = (i + 1, j + 1),
        }
    }
    out
}

#[cfg(test)]
thread_local! {
    /// How many pairs of intervals [`intersect_intervals`] looked at on this thread.
    static INTERSECT_PAIRS: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
}

/// The most pairs of edges [`slant_boundaries`] compares for one band.
const MAX_EDGE_PAIRS: usize = 1 << 14;

/// An edge of a frame that isn't horizontal, within a band: its lower and upper ends, its y range
/// within the band and its x range there.
type Slant = (Point, Point, (f64, f64), (f64, f64));

/// The line through two points.
type Line = (Point, Point);

/// The x at which an edge crosses a height, and the line it was found along (`None` when it is
/// the edge's end).
type Crossing = (f64, Option<Line>);

/// The x of the line through `p` and `q` (not horizontal) at `y`.
fn line_x(p: Point, q: Point, y: f64) -> f64 {
    p.x + (y - p.y) / (q.y - p.y) * (q.x - p.x)
}

/// `a + b` as its rounded value and the rounding error, which sum to it exactly.
fn two_sum(a: f64, b: f64) -> (f64, f64) {
    let s = a + b;
    let v = s - a;
    (s, (a - (s - v)) + (b - v))
}

/// `a * b` as its rounded value and the rounding error, which sum to it exactly (unless the error
/// is too small for a normal f64).
fn two_product(a: f64, b: f64) -> (f64, f64) {
    let p = a * b;
    (p, a.mul_add(b, -p))
}

/// Does `r` lie exactly on the line through `p` and `q`? The cross product `(q - p) × (r - p)` is
/// summed without rounding: two points apart by a single unit in the last place are never on one
/// line.
fn on_line_exactly(p: Point, q: Point, r: Point) -> bool {
    let left = (q.x - p.x) * (r.y - p.y);
    let right = (q.y - p.y) * (r.x - p.x);
    // Rounding moves the product difference by less than this, so a larger one is not zero.
    if (left - right).abs() > 4.0 * f64::EPSILON * (left.abs() + right.abs()) {
        return false;
    }
    let (dx, dy, ex, ey) = (two_sum(q.x, -p.x), two_sum(q.y, -p.y), two_sum(r.x, -p.x), two_sum(r.y, -p.y));
    let mut terms = [0.0; 16];
    for (k, (a, b)) in [dx.0, dx.1].into_iter().flat_map(|a| [ey.0, ey.1].map(|b| (a, b))).enumerate() {
        (terms[2 * k], terms[2 * k + 1]) = two_product(a, b);
    }
    for (k, (a, b)) in [dy.0, dy.1].into_iter().flat_map(|a| [ex.0, ex.1].map(|b| (a, b))).enumerate() {
        (terms[8 + 2 * k], terms[9 + 2 * k]) = two_product(-a, b);
    }
    // The terms added into an expansion: parts of increasing size that don't overlap, whose sum is
    // the exact sum of the terms and which keeps no zero part, so it is empty only when that sum is
    // zero.
    let (mut parts, mut len) = ([0.0; 16], 0);
    for t in terms {
        let (mut sum, mut kept) = (t, 0);
        for i in 0..len {
            let (s, err) = two_sum(sum, parts[i]);
            if err != 0.0 {
                parts[kept] = err;
                kept += 1;
            }
            sum = s;
        }
        if sum != 0.0 {
            parts[kept] = sum;
            kept += 1;
        }
        len = kept;
    }
    len == 0
}

/// The x ranges within a band at which the edges `slants` bound the frame, and the line each edge
/// lies along (the same two points for every edge it is paired with). Edges that lie exactly along
/// one line and overlap there (contours that meet along an edge, however each one divides it) count
/// by parity: a stretch of the line that an even number of them cover has the frame on both sides.
/// Edges that are parallel but apart, however little, are not paired. At most [`MAX_EDGE_PAIRS`]
/// pairs are compared; edges left unpaired still count as boundaries, which can make a line shorter
/// at a seam but never puts it outside the frame. The flag is false when the limit left edges
/// unpaired. `slants` is reordered, and the lines follow its new order.
fn slant_boundaries(slants: &mut [Slant]) -> (Vec<(f64, f64)>, bool, Vec<Line>) {
    fn root(parent: &mut [usize], mut i: usize) -> usize {
        while parent[i] != i {
            parent[i] = parent[parent[i]];
            i = parent[i];
        }
        i
    }
    // Edges along one line overlap in x, so only edges whose x ranges overlap are compared.
    slants.sort_by(|u, v| u.3.0.total_cmp(&v.3.0));
    let mut parent: Vec<usize> = (0..slants.len()).collect();
    let mut pairs = 0;
    'edges: for (i, &(p, q, _, (_, x1))) in slants.iter().enumerate() {
        // The x ranges of edges along one line, each found from its own ends, can differ by
        // rounding (a few units in the last place of the coordinates).
        let scale = p.x.abs().max(p.y.abs()).max(q.x.abs()).max(q.y.abs()).max(1.0);
        let tol = 4.0 * f64::EPSILON * scale;
        for (j, &(r, s, ..)) in slants.iter().enumerate().skip(i + 1).take_while(|(_, o)| o.3.0 <= x1 + tol) {
            pairs += 1;
            if pairs > MAX_EDGE_PAIRS {
                break 'edges;
            }
            if on_line_exactly(p, q, r) && on_line_exactly(p, q, s) {
                let (a, b) = (root(&mut parent, i), root(&mut parent, j));
                parent[a] = b;
            }
        }
    }
    let mut groups: Vec<(usize, usize)> = (0..slants.len()).map(|i| (root(&mut parent, i), i)).collect();
    groups.sort_unstable();
    let mut out = Vec::new();
    let mut lines: Vec<Line> = slants.iter().map(|s| (s.0, s.1)).collect();
    for run in groups.chunk_by(|a, b| a.0 == b.0) {
        if let [(_, i)] = run {
            out.push(slants[*i].3);
            continue;
        }
        // The stretches an odd number of the edges cover: pairs of their sorted y ends.
        let (p, q, ..) = slants[run[0].1];
        for &(_, i) in run {
            lines[i] = (p, q);
        }
        let mut ys: Vec<f64> = run.iter().flat_map(|&(_, i)| [slants[i].2.0, slants[i].2.1]).collect();
        ys.sort_by(f64::total_cmp);
        for c in ys.as_chunks::<2>().0.iter().filter(|c| c[1] > c[0]) {
            let (s, t) = (line_x(p, q, c[0]), line_x(p, q, c[1]));
            out.push((s.min(t), s.max(t)));
        }
    }
    (out, pairs <= MAX_EDGE_PAIRS, lines)
}

/// The most pieces a line's band is cut into to keep it inside an Invert Wrap shape grown by its
/// offset, when [`grown_band`] gives up, or out of a wrap shape shrunk by its offset.
const INVERT_WRAP_PIECES: f64 = 64.0;

/// The edges of `polys` that reach into the band `top..bottom` (`top <= bottom`), leaving out those
/// that only touch its top or bottom: the horizontal ones as (y, x0, x1) and the others as
/// [`Slant`]s.
fn band_edges(polys: &[Vec<Point>], top: f64, bottom: f64) -> (Vec<(f64, f64, f64)>, Vec<Slant>) {
    let mut flats: Vec<(f64, f64, f64)> = Vec::new();
    let mut slants: Vec<Slant> = Vec::new();
    for poly in polys {
        for (i, &a) in poly.iter().enumerate() {
            let b = poly[(i + 1) % poly.len()];
            let (lo, hi) = (a.y.min(b.y), a.y.max(b.y));
            if hi <= top || lo >= bottom {
                continue;
            }
            if a.y == b.y {
                flats.push((a.y, a.x.min(b.x), a.x.max(b.x)));
            } else {
                let (p, q) = if a.y < b.y { (a, b) } else { (b, a) };
                let ys = (lo.max(top), hi.min(bottom));
                let (s, t) = (line_x(p, q, ys.0), line_x(p, q, ys.1));
                slants.push((p, q, ys, (s.min(t), s.max(t))));
            }
        }
    }
    (flats, slants)
}

/// Inside intervals (even-odd) of `polys` over the whole band `top..bottom`: the intervals at the
/// middle of the band minus every x at which an edge lies within the band. A vertical line at any
/// other x meets no edge inside the band, so it is inside over the whole band exactly when it is
/// inside at the middle. An edge that only touches the top or bottom of the band leaves the band's
/// width alone, and so does a stretch of an edge that contours meet along (one that an even number
/// of edges cover).
fn band_intervals(polys: &[Vec<Point>], top: f64, bottom: f64) -> Vec<(f64, f64)> {
    let (top, bottom) = (top.min(bottom), top.max(bottom));
    let (edges, _, mut xs) = band_boundaries(polys, top, bottom);
    // The edges of contours that meet along an edge cross the middle of the band at the same x,
    // since each is crossed on the line through the same two points: the intervals on either side
    // join there (an edge that bounds the shape there is still subtracted). Crossings of other edges
    // that round to the same x join only when both lie exactly at that x. Intervals with any gap
    // between them stay apart.
    let y = (top + bottom) * 0.5;
    xs.sort_by(|a, b| a.0.total_cmp(&b.0).then_with(|| line_order(a.1, b.1)));
    let mut mid: Vec<(f64, f64)> = Vec::new();
    let mut last: Option<Line> = None;
    for &[(s, ks), (t, kt)] in xs.as_chunks::<2>().0 {
        match mid.last_mut() {
            Some(prev) if s <= prev.1 && ((ks.is_some() && last == ks) || (exactly_at(last, s, y) && exactly_at(ks, s, y))) => prev.1 = prev.1.max(t),
            _ => mid.push((s, t)),
        }
        last = kt;
    }
    subtract_intervals(&mid, &edges)
}

/// An order of the lines crossings of the band's middle were found along, which keeps crossings
/// along one line next to each other; a crossing at an edge's end (`None`) comes first.
fn line_order(a: Option<Line>, b: Option<Line>) -> std::cmp::Ordering {
    let key = |l: Option<Line>| l.map_or([f64::NEG_INFINITY; 4], |(p, q)| [p.x, p.y, q.x, q.y]);
    key(a).iter().zip(key(b)).fold(std::cmp::Ordering::Equal, |o, (u, v)| o.then(u.total_cmp(&v)))
}

/// Does a crossing of the height `y` at `x`, found along `line` (or at an edge's end when `None`),
/// lie exactly at `x`?
fn exactly_at(line: Option<Line>, x: f64, y: f64) -> bool {
    line.is_none_or(|(p, q)| on_line_exactly(p, q, Point::new(x, y)))
}

/// The x at which `polys` (even-odd) is inside somewhere in the band `top..bottom`, sorted and
/// disjoint: the intervals at the middle of the band and every x at which an edge lies within the
/// band. A vertical line at any other x meets no edge inside the band, so it is inside somewhere in
/// the band exactly when it is inside at the middle. Edges that contours meet along, which bound no
/// part of the shape, are left out as in [`band_intervals`]. When [`MAX_EDGE_PAIRS`] leaves edges
/// unpaired, `admit` keeps only the intervals at the middle, which the shape holds; otherwise every
/// edge counts, which can only widen the result.
fn band_cover(polys: &[Vec<Point>], top: f64, bottom: f64, admit: bool) -> Vec<(f64, f64)> {
    let (top, bottom) = (top.min(bottom), top.max(bottom));
    let mut iv = poly_intervals(polys, (top + bottom) * 0.5);
    let (edges, paired, _) = band_boundaries(polys, top, bottom);
    if paired || !admit {
        iv.extend(edges);
    }
    iv.retain(|e| e.1 > e.0);
    union_intervals(iv)
}

/// [`band_cover`] with `admit`, plus the x of every horizontal edge that lies along the top or
/// bottom of the band (`top < bottom`), counted by parity as in [`band_boundaries`]: the x at which
/// the shape or its outline meets the closed band.
fn band_cover_closed(polys: &[Vec<Point>], top: f64, bottom: f64) -> Vec<(f64, f64)> {
    let mut iv = band_cover(polys, top, bottom, true);
    for y in [top, bottom] {
        let mut xs: Vec<f64> = polys
            .iter()
            .flat_map(|poly| poly.iter().zip(poly.iter().cycle().skip(1)))
            .filter(|(a, b)| a.y == y && b.y == y)
            .flat_map(|(a, b)| [a.x, b.x])
            .collect();
        xs.sort_by(f64::total_cmp);
        iv.extend(xs.as_chunks::<2>().0.iter().map(|c| (c[0], c[1])));
    }
    iv.retain(|e| e.1 > e.0);
    union_intervals(iv)
}

/// Every x at which an edge of `polys` bounds the shape within the band `top..bottom`
/// (`top <= bottom`), sorted and disjoint, leaving out edges that only touch the top or bottom of
/// the band, stretches of edges that an even number of edges cover, and vertical edges. The flag is
/// false when [`MAX_EDGE_PAIRS`] left edges unpaired, which can only add to the result. Last, the x
/// at which the edges cross the middle of the band (even-odd, as [`poly_intervals`] finds them),
/// unsorted, each found along the line [`slant_boundaries`] gives its edge, with that line (`None`
/// for a crossing at an edge's end).
fn band_boundaries(polys: &[Vec<Point>], top: f64, bottom: f64) -> (Vec<(f64, f64)>, bool, Vec<Crossing>) {
    let (mut flats, mut slants) = band_edges(polys, top, bottom);
    let (mut edges, paired, lines) = slant_boundaries(&mut slants);
    let y = (top + bottom) * 0.5;
    let mut xs: Vec<Crossing> =
        slants.iter().zip(&lines).filter(|((p, q, ..), _)| p.y <= y && y < q.y).map(|(_, &(p, q))| (line_x(p, q, y), Some((p, q)))).collect();
    // When the middle is the band's bottom (a band of no height), the edges that start there cross
    // it but are not in the band: they cross it at their lower end.
    if y == bottom {
        let starts = polys.iter().flat_map(|poly| poly.iter().zip(poly.iter().cycle().skip(1)));
        xs.extend(starts.filter(|(a, b)| a.y != b.y && a.y.min(b.y) == y).map(|(a, b)| (if a.y < b.y { a.x } else { b.x }, None)));
    }
    // The x covered by an odd number of the horizontal edges at one height: pairs of their
    // sorted ends.
    flats.sort_by(|p, q| p.0.total_cmp(&q.0));
    for run in flats.chunk_by(|p, q| p.0 == q.0) {
        let mut xs: Vec<f64> = run.iter().flat_map(|&(_, a, b)| [a, b]).collect();
        xs.sort_by(f64::total_cmp);
        edges.extend(xs.as_chunks::<2>().0.iter().map(|c| (c[0], c[1])));
    }
    // A vertical edge covers a single x: where it bounds the shape, the band's middle already
    // ends at it or an edge of some width meets it, so it is left out (vertical seams join).
    edges.retain(|e| e.1 > e.0);
    (union_intervals(edges), paired, xs)
}

/// The largest magnitude a text wrap offset may have (points), the bound the Text Wrap commands
/// and `.ai` import keep too.
const MAX_WRAP_OFFSET: f64 = 1000.0;

/// A wrap object's offset as layout uses it: within [`MAX_WRAP_OFFSET`] either way, and 0 when it
/// is not a number.
fn wrap_offset(offset: f64) -> f64 {
    if offset.is_nan() { 0.0 } else { offset.clamp(-MAX_WRAP_OFFSET, MAX_WRAP_OFFSET) }
}

/// The x at which some point of the band `top..bottom` (`top <= bottom`) is inside `polys`
/// (even-odd) and farther than `d` (> 0) from every edge of it, holes included: the cover of the
/// shape shrunk by `d`. The band is cut into pieces (at most [`INVERT_WRAP_PIECES`] even ones, and
/// at every anchor's height and `d` above and below it when there are at most that many of those);
/// in each piece, an x is left out when the shape is nowhere in the piece there, or when the whole
/// piece there lies within `d` of one edge. A piece where several edges together cover it keeps
/// its x, so the result can be wider than the shrunk shape, never narrower, and never wider than
/// the shape's own cover of the band.
fn eroded_cover(polys: &[Vec<Point>], top: f64, bottom: f64, d: f64) -> Vec<(f64, f64)> {
    // A point `d` from an edge, up to rounding, counts as near it, so a band that only touches the
    // shrunk shape is left whole.
    let r = d * (1.0 + 1e-12);
    let span = |p: &[Point]| p.iter().fold((f64::INFINITY, f64::NEG_INFINITY), |(lo, hi), q| (lo.min(q.y), hi.max(q.y)));
    // The shrunk shape lies more than `d` below the shape's top and above its bottom, so a band
    // outside that holds none of it; within it, only contours that come within `d` of the band
    // count (the others neither cross it nor bound the shape near it).
    let (lo, hi) = polys.iter().map(|p| span(p)).fold((f64::INFINITY, f64::NEG_INFINITY), |(a, b), (c, e)| (a.min(c), b.max(e)));
    if bottom <= lo + r || top >= hi - r {
        return vec![];
    }
    let near_band: Vec<Vec<Point>> = polys
        .iter()
        .filter(|p| {
            let (lo, hi) = span(p);
            hi >= top - r && lo <= bottom + r
        })
        .cloned()
        .collect();
    let polys = near_band.as_slice();
    let pieces = ((bottom - top) * 4.0 / d).ceil().clamp(1.0, INVERT_WRAP_PIECES);
    let mut cuts: Vec<f64> = (0..=pieces as usize).map(|k| top + (bottom - top) * k as f64 / pieces).collect();
    if bottom > top {
        let mut anchors: Vec<f64> = polys.iter().flatten().flat_map(|p| [p.y - d, p.y, p.y + d]).filter(|&y| y > top && y < bottom).collect();
        anchors.sort_by(f64::total_cmp);
        anchors.dedup();
        if anchors.len() <= INVERT_WRAP_PIECES as usize {
            cuts.extend(anchors);
            cuts.sort_by(f64::total_cmp);
            cuts.dedup();
        }
    }
    // A stretch of an edge that contours meet along bounds no part of the shape, so the shape is
    // not shrunk beside it.
    let edges = boundary_segments(polys, |lo, hi| hi > top - r && lo < bottom + r);
    let mut out = Vec::new();
    // A band of no height keeps its two equal cuts: one piece of no height, measured at its y.
    for w in cuts.windows(2) {
        let (a, b) = (w[0], w[1]);
        let cover = band_cover(polys, a, b, false);
        if cover.is_empty() {
            continue;
        }
        // The points closer than `d` to an edge make a convex shape, so a vertical line within
        // the piece lies in it when both its ends do.
        let near = edges.iter().filter_map(|&(s, t)| {
            let (u, v) = (near_segment(s, t, a, r)?, near_segment(s, t, b, r)?);
            let (x, y) = (u.0.max(v.0), u.1.min(v.1));
            (y > x).then_some((x, y))
        });
        out.extend(subtract_intervals(&cover, &union_intervals(near.collect())));
    }
    union_intervals(out)
}

/// The most steps [`grown_band`] takes for one band and one wrap shape: edges, pairs of edges and
/// pairs of grown pieces looked at, and pieces looked at for each x it tests.
const MAX_INVERT_WRAP_WORK: usize = 1 << 20;

#[cfg(test)]
thread_local! {
    /// How many steps [`grown_band`] took on this thread.
    static GROWN_BAND_WORK: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
}

/// Adds `n` to `work`; false when that passes [`MAX_INVERT_WRAP_WORK`].
fn spend(work: &mut usize, n: usize) -> bool {
    *work = work.saturating_add(n);
    #[cfg(test)]
    GROWN_BAND_WORK.set(GROWN_BAND_WORK.get().saturating_add(n));
    *work <= MAX_INVERT_WRAP_WORK
}

/// The x of the edge `p`–`q` (not horizontal) at `y`: the x of its end at that end's height.
fn edge_x(p: Point, q: Point, y: f64) -> f64 {
    if y == p.y {
        p.x
    } else if y == q.y {
        q.x
    } else {
        line_x(p, q, y)
    }
}

/// A trapezoid with a horizontal top and bottom: its top and bottom heights, then the x of its left
/// edge at each of them, then the x of its right edge at each of them.
type Trapezoid = (f64, f64, f64, f64, f64, f64);

/// The shape `polys` (even-odd) between the heights `y0..y1` (`y0 < y1`) as trapezoids with
/// horizontal tops and bottoms, cut at each anchor's height and wherever two edges cross, whose union
/// (each trapezoid with its outline) is the shape with its outline there. Edges that lie along one
/// another give trapezoids that touch, and contours that cancel each other give none. `None` when
/// [`MAX_INVERT_WRAP_WORK`] runs out.
fn trapezoids(polys: &[Vec<Point>], y0: f64, y1: f64, work: &mut usize) -> Option<Vec<Trapezoid>> {
    let mut edges: Vec<(Point, Point)> = polys
        .iter()
        .flat_map(|p| (0..p.len()).map(move |i| (p[i], p[(i + 1) % p.len()])))
        .filter(|(a, b)| a.y != b.y && a.y.max(b.y) > y0 && a.y.min(b.y) < y1)
        .map(|(a, b)| if a.y < b.y { (a, b) } else { (b, a) })
        .collect();
    if !spend(work, edges.len()) {
        return None;
    }
    edges.sort_by(|u, v| u.0.y.total_cmp(&v.0.y));
    let mut ys: Vec<f64> = edges.iter().flat_map(|(p, q)| [p.y, q.y]).filter(|&y| y > y0 && y < y1).chain([y0, y1]).collect();
    ys.sort_by(f64::total_cmp);
    ys.dedup();
    let mut out = Vec::new();
    let (mut next, mut active) = (0, Vec::new());
    for w in ys.windows(2) {
        let (a, b) = (w[0], w[1]);
        // The edges that span the slab `a..b`: every anchor's height is a cut, so an edge that
        // starts at or above `a` and ends below it reaches `b`.
        while let Some(&e) = edges.get(next).filter(|e| e.0.y <= a) {
            active.push(e);
            next += 1;
        }
        active.retain(|e: &(Point, Point)| e.1.y >= b);
        if !spend(work, active.len()) {
            return None;
        }
        // The heights within the slab at which two edges cross: their order left to right differs
        // at its top and bottom.
        let mut cuts = vec![a, b];
        let ends: Vec<(f64, f64)> = active.iter().map(|&(p, q)| (edge_x(p, q, a), edge_x(p, q, b))).collect();
        let mut order: Vec<usize> = (0..ends.len()).collect();
        order.sort_by(|&i, &j| ends[i].0.total_cmp(&ends[j].0).then(ends[i].1.total_cmp(&ends[j].1)));
        if order.windows(2).any(|w| ends[w[0]].1 > ends[w[1]].1) {
            if !spend(work, ends.len() * ends.len()) {
                return None;
            }
            for (i, &(sa, sb)) in ends.iter().enumerate() {
                for &(ta, tb) in &ends[i + 1..] {
                    let (da, db) = (sa - ta, sb - tb);
                    if da * db < 0.0 {
                        let y = a + (b - a) * (da / (da - db));
                        if y > a && y < b {
                            cuts.push(y);
                        }
                    }
                }
            }
            cuts.sort_by(f64::total_cmp);
            cuts.dedup();
        }
        for c in cuts.windows(2) {
            let (c, d) = (c[0], c[1]);
            // No two edges cross within `c..d`, so their order at its middle holds throughout, and
            // the shape (even-odd) lies between the first and second, the third and fourth, and so on.
            let mid = (c + d) * 0.5;
            let mut xs: Vec<(f64, f64, f64)> = active.iter().map(|&(p, q)| (line_x(p, q, mid), edge_x(p, q, c), edge_x(p, q, d))).collect();
            if !spend(work, xs.len()) {
                return None;
            }
            xs.sort_by(|u, v| u.0.total_cmp(&v.0));
            for pair in xs.as_chunks::<2>().0 {
                let ((_, l0, l1), (_, r0, r1)) = (pair[0], pair[1]);
                if r0 > l0 || r1 > l1 {
                    out.push((c, d, l0, l1, r0, r1));
                }
            }
        }
    }
    Some(out)
}

/// A convex polygon as its lower and upper outlines (the least and the greatest y at each x), each
/// left to right from its least x to its greatest, with its x range and y range.
struct Convex {
    lower: Vec<Point>,
    upper: Vec<Point>,
    xs: (f64, f64),
    ys: (f64, f64),
}

impl Convex {
    /// The convex hull of `pts`.
    fn hull(mut pts: Vec<Point>) -> Convex {
        let cross = |o: Point, a: Point, b: Point| (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
        let chain = |pts: &[Point], turns: fn(f64) -> bool| {
            let mut out: Vec<Point> = Vec::with_capacity(pts.len());
            for &p in pts {
                while let [.., o, a] = out[..] {
                    if turns(cross(o, a, p)) {
                        break;
                    }
                    out.pop();
                }
                out.push(p);
            }
            // The points at the greatest x after the first are on the other outline.
            while let [.., a, b] = out[..] {
                if a.x != b.x {
                    break;
                }
                out.pop();
            }
            out
        };
        pts.sort_by(|p, q| p.x.total_cmp(&q.x).then(p.y.total_cmp(&q.y)));
        let lower = chain(&pts, |c| c > 0.0);
        pts.sort_by(|p, q| p.x.total_cmp(&q.x).then(q.y.total_cmp(&p.y)));
        let upper = chain(&pts, |c| c < 0.0);
        let xs = (lower.first().map_or(f64::NAN, |p| p.x), lower.last().map_or(f64::NAN, |p| p.x));
        let ys = (lower.iter().fold(f64::INFINITY, |m, p| m.min(p.y)), upper.iter().fold(f64::NEG_INFINITY, |m, p| m.max(p.y)));
        Convex { lower, upper, xs, ys }
    }

    /// The y range of the polygon at `x`, within its x range.
    fn at(&self, x: f64) -> (f64, f64) {
        (chain_y(&self.lower, x), chain_y(&self.upper, x))
    }
}

/// The y of the outline `chain` (left to right, no two points at one x) at `x`, within its x range.
fn chain_y(chain: &[Point], x: f64) -> f64 {
    let i = chain.partition_point(|p| p.x < x);
    match (i.checked_sub(1).and_then(|h| chain.get(h)), chain.get(i)) {
        (Some(p), Some(q)) => p.y + (x - p.x) / (q.x - p.x) * (q.y - p.y),
        (None, Some(q)) => q.y,
        (Some(p), None) => p.y,
        (None, None) => f64::NAN,
    }
}

/// The x at which some segment of `a` and some segment of `b` (outlines left to right) are at the
/// same y, strictly between the ends of the x range they share.
fn chain_crossings(a: &[Point], b: &[Point], out: &mut Vec<f64>, work: &mut usize) -> bool {
    for s in a.windows(2) {
        let first = b.partition_point(|q| q.x <= s[0].x).saturating_sub(1);
        for t in b[first..].windows(2).take_while(|t| t[0].x < s[1].x) {
            if !spend(work, 1) {
                return false;
            }
            let (x0, x1) = (s[0].x.max(t[0].x), s[1].x.min(t[1].x));
            if x1 <= x0 {
                continue;
            }
            let (d0, d1) = (chain_y(s, x0) - chain_y(t, x0), chain_y(s, x1) - chain_y(t, x1));
            if d0 * d1 < 0.0 {
                out.push(x0 + (x1 - x0) * (d0 / (d0 - d1)));
            }
        }
    }
    true
}

/// The x within `lo..hi` at which the shape `polys` (even-odd) grown by `off` (> 0) across and
/// along holds every height of the band `top..bottom` (`top <= bottom`): the x whose vertical line
/// across the band has each of its points within `off`, across and along, of the shape or its
/// outline. The shape from `off` above the band to `off` below it, and on to the nearest anchors
/// past those heights, is cut into [`trapezoids`]; each
/// grown by `off` is a convex polygon, and the line at an x lies in their union when the y ranges
/// they give at that x join up across the band. Those ranges change only at the polygons' corners
/// and where their outlines cross each other or the band's top or bottom, so the line is tested
/// once between each two of those x. `None` when that takes more than [`MAX_INVERT_WRAP_WORK`]
/// steps.
fn grown_band(polys: &[Vec<Point>], off: f64, top: f64, bottom: f64, (lo, hi): (f64, f64)) -> Option<Vec<(f64, f64)>> {
    let mut work = 0;
    // The trapezoids reach on to the nearest anchor past `off` above and below the band, so that
    // the shape's outline exactly `off` from the band counts.
    let (y0, y1) = (top - off, bottom + off);
    let ys = || polys.iter().flatten().map(|p| p.y);
    let below = ys().filter(|&y| y < y0).fold(f64::NEG_INFINITY, f64::max);
    let above = ys().filter(|&y| y > y1).fold(f64::INFINITY, f64::min);
    let traps = trapezoids(polys, if below.is_finite() { below } else { y0 }, if above.is_finite() { above } else { y1 }, &mut work)?;
    let mut grown: Vec<Convex> = traps
        .into_iter()
        .filter(|&(_, _, l0, l1, r0, r1)| l0.min(l1) - off < hi && r0.max(r1) + off > lo)
        .map(|(y0, y1, l0, l1, r0, r1)| {
            let corners = [(l0, y0), (r0, y0), (l1, y1), (r1, y1)];
            let pts = corners
                .into_iter()
                .flat_map(|(x, y)| [(-off, -off), (off, -off), (-off, off), (off, off)].map(|(dx, dy)| Point::new(x + dx, y + dy)));
            Convex::hull(pts.collect())
        })
        .collect();
    grown.sort_by(|p, q| p.xs.0.total_cmp(&q.xs.0));
    // The x at which the line's place among the polygons can change.
    let mut xs = vec![lo, hi];
    for (j, p) in grown.iter().enumerate() {
        xs.extend(p.lower.iter().chain(&p.upper).map(|v| v.x));
        for chain in [&p.lower, &p.upper] {
            for s in chain.windows(2) {
                for y in [top, bottom] {
                    let (d0, d1) = (s[0].y - y, s[1].y - y);
                    if d0 * d1 < 0.0 {
                        xs.push(s[0].x + (s[1].x - s[0].x) * (d0 / (d0 - d1)));
                    }
                }
            }
        }
        let ((_, x1), (y0, y1)) = (p.xs, p.ys);
        for q in grown[j + 1..].iter().take_while(|q| q.xs.0 < x1) {
            if !spend(&mut work, 1) {
                return None;
            }
            let (v0, v1) = q.ys;
            if v0 <= y1
                && y0 <= v1
                && !(chain_crossings(&p.upper, &q.lower, &mut xs, &mut work) && chain_crossings(&q.upper, &p.lower, &mut xs, &mut work))
            {
                return None;
            }
        }
    }
    xs.retain(|&x| x >= lo && x <= hi);
    xs.sort_by(f64::total_cmp);
    xs.dedup();
    // Test the line between each two of those x, walking left to right with the polygons whose x
    // range holds it.
    let mut out: Vec<(f64, f64)> = Vec::new();
    let (mut next, mut active, mut ranges): (usize, Vec<&Convex>, Vec<(f64, f64)>) = (0, Vec::new(), Vec::new());
    for w in xs.windows(2) {
        let x = (w[0] + w[1]) * 0.5;
        while let Some(p) = grown.get(next).filter(|p| p.xs.0 <= x) {
            active.push(p);
            next += 1;
        }
        active.retain(|p| p.xs.1 >= x);
        if !spend(&mut work, active.len()) {
            return None;
        }
        ranges.clear();
        ranges.extend(active.iter().map(|p| p.at(x)));
        ranges.sort_by(|u, v| u.0.total_cmp(&v.0));
        // The line is held from the band's top to `reach`, up to the first range that starts past
        // it; a band of no height is held when a range reaches it.
        let (mut reach, mut met) = (top, false);
        for &(a, b) in &ranges {
            if a > reach {
                break;
            }
            reach = reach.max(b);
            met |= b >= top;
        }
        if met && reach >= bottom {
            match out.last_mut() {
                Some(l) if l.1 >= w[0] => l.1 = w[1],
                _ => out.push((w[0], w[1])),
            }
        }
    }
    Some(out)
}

impl Region {
    pub(super) fn cells(path: &BezPath, opts: &LayoutOptions, wrap: &[vectorcraft_doc::WrapShape]) -> Vec<Region> {
        // A frame out of range has no cells, and a wrap shape out of range is left out.
        let Some(polys) = polygons(path) else { return vec![] };
        // Every cell shares one copy of the frame's polygons and one copy of the text wrap shapes.
        let polys: std::sync::Arc<[Vec<Point>]> = polys.into();
        let wraps: std::sync::Arc<[FlatWrap]> = wrap
            .iter()
            .filter_map(|w| Some((polygons(&w.path.to_bezpath())?, wrap_offset(w.wrap.offset), w.wrap.invert)))
            .filter(|w| !w.0.is_empty())
            .collect();
        let bbox = path.bounding_box();
        let rect = polys.len() == 1 && {
            let area: f64 = polys[0].iter().zip(polys[0].iter().cycle().skip(1)).map(|(a, b)| a.x * b.y - b.x * a.y).sum::<f64>().abs() * 0.5;
            (area - bbox.area()).abs() <= bbox.area() * 1e-6 + 1e-9
        };
        let max = vectorcraft_doc::AreaOptions::MAX_ROWS_COLUMNS;
        let (rows, cols) = (opts.rows.clamp(1, max), opts.columns.clamp(1, max));
        let gutter = opts.gutter.max(0.0);
        let row_gutter = opts.row_gutter.unwrap_or(opts.gutter).max(0.0);
        let cw = ((bbox.width() - gutter * (cols - 1) as f64) / cols as f64).max(0.0);
        let rh = ((bbox.height() - row_gutter * (rows - 1) as f64) / rows as f64).max(0.0);
        let mut out = Vec::with_capacity(rows * cols);
        // Text Flow: down each column, then across (by columns, the default), or across each row,
        // then down (by rows).
        let by_rows = opts.flow == vectorcraft_doc::TextFlow::Rows;
        let (outer, inner) = if by_rows { (rows, cols) } else { (cols, rows) };
        for o in 0..outer {
            for i in 0..inner {
                let (r, c) = if by_rows { (o, i) } else { (i, o) };
                let x0 = bbox.x0 + c as f64 * (cw + gutter);
                let y0 = bbox.y0 + r as f64 * (rh + row_gutter);
                let cell = if rows * cols == 1 { bbox } else { Rect::new(x0, y0, x0 + cw, y0 + rh) };
                out.push(Region { cell, inset: opts.inset.max(0.0), polys: polys.clone(), rect, wraps: wraps.clone(), shift: 0.0, gap: 0.0 });
            }
        }
        out
    }

    pub(super) fn top(&self) -> f64 {
        self.cell.y0 + self.inset
    }
    pub(super) fn bottom(&self) -> f64 {
        self.cell.y1 - self.inset
    }

    /// `iv` minus every x at which a wrap object lies somewhere in the band `top..bottom` (or the x
    /// inside it over the whole band, for Invert Wrap). A positive offset grows each wrap shape
    /// vertically and horizontally; a negative one shrinks it by that distance from its edges
    /// (holes included), so text runs that far into the object, or stays that far inside it for
    /// Invert Wrap. Along the line, the text also keeps the inset beside each wrap object
    /// (outside it, or inside it for Invert Wrap); above and below a wrap object only its offset
    /// applies.
    fn wrapped(&self, mut iv: Vec<(f64, f64)>, top: f64, bottom: f64) -> Vec<(f64, f64)> {
        let (top, bottom) = (top.min(bottom), top.max(bottom));
        let inset = self.inset;
        for (polys, off, invert) in self.wraps.iter() {
            if iv.is_empty() {
                break;
            }
            let grow = |v: Vec<(f64, f64)>| union_intervals(v.into_iter().map(|(a, b)| (a - off, b + off)).collect());
            let shrink = |v: Vec<(f64, f64)>| v.into_iter().map(|(a, b)| (a + inset, b - inset)).filter(|(a, b)| b > a).collect::<Vec<_>>();
            let pad = |v: Vec<(f64, f64)>| union_intervals(v.into_iter().map(|(a, b)| (a - inset, b + inset)).collect());
            iv = if *off < 0.0 {
                // Invert Wrap keeps the x at which the shape shrunk by the offset holds the whole
                // band; otherwise the text leaves out the x at which the shrunk shape lies
                // somewhere in the band.
                if *invert {
                    intersect_intervals(&iv, &shrink(band_inset_intervals(polys, top, bottom, -off)))
                } else {
                    subtract_intervals(&iv, &pad(eroded_cover(polys, top, bottom, -off)))
                }
            } else if let Some(held) = (*invert && *off > 0.0)
                .then(|| iv.first().zip(iv.last()).and_then(|(f, l)| grown_band(polys, *off, top, bottom, (f.0 - inset, l.1 + inset))))
                .flatten()
            {
                // The x at which the shape grown by the offset holds the whole band.
                intersect_intervals(&iv, &shrink(held))
            } else if *invert {
                // With no offset, or when measuring the grown shape exactly takes more than
                // [`MAX_INVERT_WRAP_WORK`] steps, the band is cut into pieces, which can leave a line
                // shorter than the grown shape allows, never longer.
                //
                // Each height of a piece `y0..y1` is within the offset of some height from `y0`
                // plus the offset to `y1` less the offset, so an x the shape holds at all of those
                // heights is inside the grown shape over the piece. In
                // a piece less than twice the offset tall, each height of the piece is within the
                // offset of every height from `y1` less the offset to `y0` plus the offset, so an x
                // the shape holds at any of them is. Text within the offset of such an x, for every
                // piece, stays inside the grown shape; finer pieces give it more of that room.
                //
                // The band is also cut at every height an offset above or below an anchor of the
                // shape (when there are at most [`INVERT_WRAP_PIECES`] of them). Within a piece
                // between such cuts, no anchor enters or leaves the offset window of any of its
                // heights, so where two parts of the shape bridge a gap together (one within the
                // offset above and one below), the heights from `y1` less the offset to `y0` plus
                // the offset reach from one to the other, and the horizontal edges they end at
                // count.
                let pieces = if *off > 0.0 { ((bottom - top) * 4.0 / off).ceil().clamp(1.0, INVERT_WRAP_PIECES) } else { 1.0 };
                let mut cuts: Vec<f64> = (0..=pieces as usize).map(|k| top + (bottom - top) * k as f64 / pieces).collect();
                // A band of no height stays one piece: no anchor lies strictly inside it, and
                // removing the repeated cut would leave no piece.
                if *off > 0.0 && bottom > top {
                    let mut anchors: Vec<f64> =
                        polys.iter().flatten().flat_map(|p| [p.y - off, p.y + off]).filter(|&y| y > top && y < bottom).collect();
                    anchors.sort_by(f64::total_cmp);
                    anchors.dedup();
                    if anchors.len() <= INVERT_WRAP_PIECES as usize {
                        cuts.extend(anchors);
                        cuts.sort_by(f64::total_cmp);
                        cuts.dedup();
                    }
                }
                for w in cuts.windows(2) {
                    let (a, b) = (w[0] + off, w[1] - off);
                    let held = if a <= b { band_intervals(polys, a, b) } else { band_cover_closed(polys, b, a) };
                    iv = intersect_intervals(&iv, &shrink(grow(held)));
                    if iv.is_empty() {
                        break;
                    }
                }
                iv
            } else {
                subtract_intervals(&iv, &pad(grow(band_cover(polys, top - off, bottom + off, false))))
            };
        }
        iv
    }

    /// Widest horizontal span inside the frame (and the cell) over the band `top..bottom`.
    pub(super) fn span(&self, top: f64, bottom: f64) -> Option<(f64, f64)> {
        self.spans(top, bottom).into_iter().max_by(|x, y| (x.1 - x.0).total_cmp(&(y.1 - y.0)))
    }

    /// Every horizontal span inside the frame (and the cell) over the band `top..bottom`, left to
    /// right (text wraps on both sides of an object).
    pub(super) fn spans(&self, top: f64, bottom: f64) -> Vec<(f64, f64)> {
        // The inset from the cell's edges; `band_inset_intervals` already keeps it from the frame's
        // edges and `wrapped` beside the wrap objects.
        let clip = |(a, b): (f64, f64)| {
            let (a, b) = (a.max(self.cell.x0 + self.inset), b.min(self.cell.x1 - self.inset));
            (b > a).then_some((a, b))
        };
        let plain = self.polys.is_empty() || self.rect;
        if plain && self.wraps.is_empty() {
            return (self.cell.width() > 0.0).then_some((self.cell.x0, self.cell.x1)).and_then(clip).into_iter().collect();
        }
        let fb = if top.is_nan() || bottom.is_nan() {
            return vec![];
        } else if plain {
            self.cell
        } else {
            self.polys.iter().flatten().fold(Rect::new(f64::MAX, f64::MAX, f64::MIN, f64::MIN), |r, p| r.union_pt(*p))
        };
        // `max` then `min` rather than `clamp`, which panics on a frame less than 2e-4 tall.
        let clamp = |y: f64| if plain { y } else { y.max(fb.y0 + 1e-4).min(fb.y1 - 1e-4) };
        let free = if plain { vec![(self.cell.x0, self.cell.x1)] } else { band_inset_intervals(&self.polys, clamp(top), clamp(bottom), self.inset) };
        // Wrap objects split lines: keep what is free of them over the whole band.
        let free = if self.wraps.is_empty() { free } else { self.wrapped(free, clamp(top), clamp(bottom)) };
        free.into_iter().filter_map(clip).collect()
    }
}

/// The 10,000 cells of a frame in 100 rows and 100 columns share one copy of the frame's polygons
/// and one copy of the text wrap shapes.
#[cfg(test)]
#[test]
fn the_cells_of_a_frame_share_its_polygons_and_the_wrap_shapes() {
    let frame = kurbo::Circle::new((0.0, 0.0), 1000.0).to_path(0.1);
    let square = PathData::from_bezpath(&Rect::new(-10.0, -10.0, 10.0, 10.0).to_path(0.1));
    let wrap = vectorcraft_doc::WrapShape { path: square, wrap: Default::default() };
    let cells = Region::cells(&frame, &LayoutOptions { rows: 100, columns: 100, ..LayoutOptions::default() }, &[wrap]);
    assert_eq!(cells.len(), 10_000);
    let first = &cells[0];
    assert!(!first.polys.is_empty() && !first.wraps.is_empty());
    assert!(cells.iter().all(|c| c.polys.as_ptr() == first.polys.as_ptr() && c.wraps.as_ptr() == first.wraps.as_ptr()));
}

/// A path with one closed subpath through each list of points.
#[cfg(test)]
fn closed(subpaths: &[&[(f64, f64)]]) -> BezPath {
    let mut path = BezPath::new();
    for pts in subpaths {
        path.move_to(pts[0]);
        for &p in &pts[1..] {
            path.line_to(p);
        }
        path.close_path();
    }
    path
}

/// The spans of every cell of `path` over the band `top..bottom`.
#[cfg(test)]
fn cell_spans(path: &BezPath, opts: &LayoutOptions, wrap: &[vectorcraft_doc::WrapShape], top: f64, bottom: f64) -> Vec<Vec<(f64, f64)>> {
    Region::cells(path, opts, wrap).iter().map(|c| c.spans(top, bottom)).collect()
}

#[cfg(test)]
fn assert_spans(got: &[(f64, f64)], want: &[(f64, f64)]) {
    assert_eq!(got.len(), want.len(), "{got:?} != {want:?}");
    for (g, w) in got.iter().zip(want) {
        assert!((g.0 - w.0).abs() < 1e-9 && (g.1 - w.1).abs() < 1e-9, "{got:?} != {want:?}");
    }
}

/// A line stays inside a frame whose right edge pinches in to a point between any fixed heights of
/// the line's band, with or without text wrap shapes elsewhere.
#[cfg(test)]
#[test]
fn a_line_stays_inside_a_frame_that_pinches_in_within_its_band() {
    let notch =
        |tip: (f64, f64), (y0, y1): (f64, f64)| closed(&[&[(0.0, 0.0), (100.0, 0.0), (100.0, y0), tip, (100.0, y1), (100.0, 100.0), (0.0, 100.0)]]);
    let far = PathData::from_bezpath(&Rect::new(300.0, 0.0, 310.0, 100.0).to_path(0.1));
    let far = vectorcraft_doc::WrapShape { path: far, wrap: Default::default() };
    for (frame, x) in
        [(notch((60.0, 47.5), (45.0, 50.0)), 60.0), (notch((70.0, 42.0), (41.0, 43.0)), 70.0), (notch((80.0, 59.0), (58.0, 60.0)), 80.0)]
    {
        for wrap in [&[][..], std::slice::from_ref(&far)] {
            let cells = Region::cells(&frame, &LayoutOptions::default(), wrap);
            assert_spans(&cells[0].spans(40.0, 60.0), &[(0.0, x)]);
            assert_eq!(cells[0].span(40.0, 60.0), Some((0.0, x)));
        }
    }
}

/// A line stays clear of a wrap object whose tip reaches into its band between any fixed heights of
/// the band, with or without an offset, and inside an Invert Wrap object whose edge pinches in
/// there. Invert Wrap with an offset keeps the lines it kept beside a straight edge.
#[cfg(test)]
#[test]
fn a_line_stays_clear_of_a_wrap_object_that_reaches_into_its_band() {
    let frame = Rect::new(0.0, 0.0, 100.0, 100.0).to_path(0.1);
    let spans = |shape: &[(f64, f64)], offset: f64, invert: bool| {
        let path = PathData::from_bezpath(&closed(&[shape]));
        let wrap = vectorcraft_doc::WrapShape { path, wrap: vectorcraft_doc::TextWrap { offset, invert } };
        let cells = Region::cells(&frame, &LayoutOptions::default(), &[wrap]);
        assert!(cells[0].rect);
        cells[0].spans(40.0, 60.0)
    };
    assert_spans(&spans(&[(100.0, 45.0), (40.0, 47.5), (100.0, 50.0)], 0.0, false), &[(0.0, 40.0)]);
    assert_spans(&spans(&[(100.0, 47.0), (40.0, 47.5), (100.0, 48.0)], 1.0, false), &[(0.0, 39.0)]);
    // Two contours that cancel each other (even-odd) hold no area and leave the line whole.
    let band: &[(f64, f64)] = &[(0.0, 45.0), (100.0, 45.0), (100.0, 55.0), (0.0, 55.0)];
    let path = PathData::from_bezpath(&closed(&[band, band]));
    let wrap = vectorcraft_doc::WrapShape { path, wrap: vectorcraft_doc::TextWrap { offset: 0.0, invert: false } };
    assert_spans(&Region::cells(&frame, &LayoutOptions::default(), &[wrap])[0].spans(40.0, 60.0), &[(0.0, 100.0)]);
    let notch = [(0.0, 0.0), (100.0, 0.0), (100.0, 45.0), (60.0, 47.5), (100.0, 50.0), (100.0, 100.0), (0.0, 100.0)];
    assert_spans(&spans(&notch, 0.0, true), &[(0.0, 60.0)]);
    let triangle = [(0.0, 0.0), (100.0, 100.0), (0.0, 100.0)];
    assert_spans(&spans(&triangle, 5.0, true), &[(0.0, 50.0)]);
    assert_spans(&spans(&triangle, 15.0, true), &[(0.0, 70.0)]);
    // An Invert Wrap shape that steps sideways within the band keeps the room its offset bridges.
    let upper: &[(f64, f64)] = &[(0.0, 0.0), (40.0, 0.0), (40.0, 50.0), (0.0, 50.0)];
    let lower: &[(f64, f64)] = &[(45.0, 50.0), (85.0, 50.0), (85.0, 100.0), (45.0, 100.0)];
    let path = PathData::from_bezpath(&closed(&[upper, lower]));
    let wrap = vectorcraft_doc::WrapShape { path, wrap: vectorcraft_doc::TextWrap { offset: 5.0, invert: true } };
    assert_spans(&Region::cells(&frame, &LayoutOptions::default(), &[wrap])[0].spans(40.0, 60.0), &[(40.0, 45.0)]);
    // An Invert Wrap shape of two parts whose offsets meet across the gap between them (45.25 + 5
    // reaches past 55.125 - 5) keeps the whole line.
    let upper: &[(f64, f64)] = &[(0.0, 0.0), (100.0, 0.0), (100.0, 45.25), (0.0, 45.25)];
    let lower: &[(f64, f64)] = &[(0.0, 55.125), (100.0, 55.125), (100.0, 100.0), (0.0, 100.0)];
    let path = PathData::from_bezpath(&closed(&[upper, lower]));
    let wrap = vectorcraft_doc::WrapShape { path, wrap: vectorcraft_doc::TextWrap { offset: 5.0, invert: true } };
    assert_spans(&Region::cells(&frame, &LayoutOptions::default(), &[wrap])[0].spans(40.0, 60.0), &[(0.0, 100.0)]);
    // A gap the offsets do not bridge (45 + 5 stops short of 55.125 - 5) holds no line.
    let upper: &[(f64, f64)] = &[(0.0, 0.0), (100.0, 0.0), (100.0, 45.0), (0.0, 45.0)];
    let path = PathData::from_bezpath(&closed(&[upper, lower]));
    let wrap = vectorcraft_doc::WrapShape { path, wrap: vectorcraft_doc::TextWrap { offset: 5.0, invert: true } };
    assert!(Region::cells(&frame, &LayoutOptions::default(), &[wrap])[0].spans(40.0, 60.0).is_empty());
    // A band of no height keeps Invert Wrap and its offset.
    let strip: &[(f64, f64)] = &[(20.0, 0.0), (40.0, 0.0), (40.0, 100.0), (20.0, 100.0)];
    let path = PathData::from_bezpath(&closed(&[strip]));
    let wrap = vectorcraft_doc::WrapShape { path, wrap: vectorcraft_doc::TextWrap { offset: 5.0, invert: true } };
    assert_spans(&Region::cells(&frame, &LayoutOptions::default(), &[wrap])[0].spans(50.0, 50.0), &[(15.0, 45.0)]);
}

/// The spans of a 100 pt square frame over the band `top..bottom` with one wrap object through
/// `contours` (even-odd).
#[cfg(test)]
fn wrap_spans(contours: &[&[(f64, f64)]], offset: f64, invert: bool, top: f64, bottom: f64) -> Vec<(f64, f64)> {
    let frame = Rect::new(0.0, 0.0, 100.0, 100.0).to_path(0.1);
    let wrap = vectorcraft_doc::WrapShape { path: PathData::from_bezpath(&closed(contours)), wrap: vectorcraft_doc::TextWrap { offset, invert } };
    Region::cells(&frame, &LayoutOptions::default(), &[wrap])[0].spans(top, bottom)
}

/// A negative offset lets text run into a wrap object by that distance, across and along the
/// line: beside a square, the line reaches 5 pt into it, and a line whose band reaches no more than
/// 5 pt into its top or bottom runs across it.
#[cfg(test)]
#[test]
fn negative_wrap_offset_insets_rectangle_on_both_axes() {
    let square: &[(f64, f64)] = &[(40.0, 40.0), (60.0, 40.0), (60.0, 60.0), (40.0, 60.0)];
    assert_spans(&wrap_spans(&[square], -5.0, false, 44.0, 50.0), &[(0.0, 45.0), (55.0, 100.0)]);
    assert_spans(&wrap_spans(&[square], -5.0, false, 30.0, 45.0), &[(0.0, 100.0)]);
    assert_spans(&wrap_spans(&[square], -5.0, false, 55.0, 70.0), &[(0.0, 100.0)]);
    assert_spans(&wrap_spans(&[square], -5.0, false, 30.0, 46.0), &[(0.0, 45.0), (55.0, 100.0)]);
    // The most an offset may take away is 1000 pt, and an offset that is not a number is 0.
    assert_spans(&wrap_spans(&[square], f64::NEG_INFINITY, false, 44.0, 50.0), &[(0.0, 100.0)]);
    assert_spans(&wrap_spans(&[square], f64::NAN, false, 44.0, 50.0), &[(0.0, 40.0), (60.0, 100.0)]);
}

/// A negative offset is measured from a sloped edge itself (10 pt across the edge of a triangle is
/// 10√2 pt along the line), and from the edges of a hole too.
#[cfg(test)]
#[test]
fn negative_wrap_offset_insets_sloped_shape_and_hole() {
    let triangle: &[(f64, f64)] = &[(0.0, 0.0), (100.0, 100.0), (0.0, 100.0)];
    assert_spans(&wrap_spans(&[triangle], -10.0, false, 40.0, 60.0), &[(0.0, 10.0), (60.0 - 10.0 * std::f64::consts::SQRT_2, 100.0)]);
    let outer: &[(f64, f64)] = &[(20.0, 20.0), (80.0, 20.0), (80.0, 80.0), (20.0, 80.0)];
    let hole: &[(f64, f64)] = &[(40.0, 40.0), (60.0, 40.0), (60.0, 60.0), (40.0, 60.0)];
    assert_spans(&wrap_spans(&[outer, hole], -5.0, false, 48.0, 52.0), &[(0.0, 25.0), (35.0, 65.0), (75.0, 100.0)]);
}

/// With Invert Wrap, a negative offset keeps the text that far inside the object, along and across
/// the line.
#[cfg(test)]
#[test]
fn negative_invert_wrap_keeps_only_eroded_interior() {
    let square: &[(f64, f64)] = &[(40.0, 40.0), (60.0, 40.0), (60.0, 60.0), (40.0, 60.0)];
    assert_spans(&wrap_spans(&[square], -5.0, true, 46.0, 54.0), &[(45.0, 55.0)]);
    assert!(wrap_spans(&[square], -5.0, true, 42.0, 48.0).is_empty());
    let triangle: &[(f64, f64)] = &[(0.0, 0.0), (100.0, 100.0), (0.0, 100.0)];
    assert_spans(&wrap_spans(&[triangle], -10.0, true, 40.0, 60.0), &[(10.0, 40.0 - 10.0 * std::f64::consts::SQRT_2)]);
}

/// A negative offset at least half as large as a wrap object is wide leaves nothing of it: text
/// runs across it, and with Invert Wrap no text fits inside it.
#[cfg(test)]
#[test]
fn negative_offset_erases_narrow_wrap_shape() {
    let strip: &[(f64, f64)] = &[(40.0, 0.0), (48.0, 0.0), (48.0, 100.0), (40.0, 100.0)];
    for offset in [-4.0, -5.0, -1000.0] {
        assert_spans(&wrap_spans(&[strip], offset, false, 40.0, 60.0), &[(0.0, 100.0)]);
        assert!(wrap_spans(&[strip], offset, true, 40.0, 60.0).is_empty(), "offset {offset}");
    }
    // A band of no height.
    assert_spans(&wrap_spans(&[strip], -1.0, false, 50.0, 50.0), &[(0.0, 41.0), (47.0, 100.0)]);
}

/// A negative offset never keeps text farther from a wrap object than an offset of 0 does, on a
/// shape whose edges meet at many angles.
#[cfg(test)]
#[test]
fn negative_offset_never_wraps_more_than_no_offset() {
    let star: Vec<(f64, f64)> = (0..40)
        .map(|k| {
            let (r, a) = (if k % 2 == 0 { 40.0 } else { 15.0 }, f64::from(k) * std::f64::consts::PI / 20.0);
            (50.0 + r * a.cos(), 50.0 + r * a.sin())
        })
        .collect();
    for (top, bottom) in [(10.0, 22.0), (44.0, 56.0), (30.0, 31.0), (70.0, 90.0)] {
        for invert in [false, true] {
            let zero = wrap_spans(&[star.as_slice()], 0.0, invert, top, bottom);
            let neg = wrap_spans(&[star.as_slice()], -3.0, invert, top, bottom);
            let width = |v: &[(f64, f64)]| v.iter().map(|(a, b)| b - a).sum::<f64>();
            if invert {
                assert!(width(&neg) <= width(&zero) + 1e-9, "{top}..{bottom}: {neg:?} {zero:?}");
            } else {
                assert!(width(&neg) >= width(&zero) - 1e-9, "{top}..{bottom}: {neg:?} {zero:?}");
            }
        }
    }
}

/// A hole that starts and ends inside a line's band splits the line, and a band below the hole, or
/// one that only touches it, keeps the whole width.
#[cfg(test)]
#[test]
fn a_hole_inside_a_band_splits_the_line() {
    let frame = closed(&[&[(0.0, 0.0), (100.0, 0.0), (100.0, 100.0), (0.0, 100.0)], &[(40.0, 52.0), (60.0, 52.0), (60.0, 58.0), (40.0, 58.0)]]);
    let cells = Region::cells(&frame, &LayoutOptions::default(), &[]);
    assert!(!cells[0].rect);
    assert_spans(&cells[0].spans(40.0, 60.0), &[(0.0, 40.0), (60.0, 100.0)]);
    assert_spans(&cells[0].spans(60.0, 80.0), &[(0.0, 100.0)]);
    // A band that only touches the hole at its top or bottom keeps the whole width.
    assert_spans(&cells[0].spans(58.0, 78.0), &[(0.0, 100.0)]);
    assert_spans(&cells[0].spans(32.0, 52.0), &[(0.0, 100.0)]);
    // A band given bottom first covers the same heights.
    assert_spans(&cells[0].spans(60.0, 40.0), &[(0.0, 40.0), (60.0, 100.0)]);
    assert!(cells[0].spans(f64::NAN, 60.0).is_empty());
}

/// Lines run across an edge two contours share (a horizontal one over the part both cover) and
/// stop at the part only one covers (a step).
#[cfg(test)]
#[test]
fn lines_cross_an_edge_two_contours_share() {
    let seam = closed(&[&[(0.0, 0.0), (100.0, 0.0), (100.0, 50.0), (0.0, 50.0)], &[(0.0, 50.0), (100.0, 50.0), (100.0, 100.0), (0.0, 100.0)]]);
    let cells = Region::cells(&seam, &LayoutOptions::default(), &[]);
    assert!(!cells[0].rect);
    assert_spans(&cells[0].spans(40.0, 60.0), &[(0.0, 100.0)]);
    let step = closed(&[&[(0.0, 0.0), (100.0, 0.0), (100.0, 50.0), (0.0, 50.0)], &[(0.0, 50.0), (50.0, 50.0), (50.0, 100.0), (0.0, 100.0)]]);
    let cells = Region::cells(&step, &LayoutOptions::default(), &[]);
    assert_spans(&cells[0].spans(40.0, 60.0), &[(0.0, 50.0)]);
    // Contours that meet along a seam that bends within the band, one drawn each way along it.
    let bent = closed(&[
        &[(0.0, 0.0), (50.0, 0.0), (70.0, 47.5), (50.0, 100.0), (0.0, 100.0)],
        &[(50.0, 0.0), (100.0, 0.0), (100.0, 100.0), (50.0, 100.0), (70.0, 47.5)],
    ]);
    let cells = Region::cells(&bent, &LayoutOptions::default(), &[]);
    assert_spans(&cells[0].spans(40.0, 60.0), &[(0.0, 100.0)]);
    // Contours side by side, meeting along a vertical edge.
    let side = closed(&[&[(0.0, 0.0), (50.0, 0.0), (50.0, 100.0), (0.0, 100.0)], &[(50.0, 0.0), (100.0, 0.0), (100.0, 100.0), (50.0, 100.0)]]);
    let cells = Region::cells(&side, &LayoutOptions::default(), &[]);
    assert_spans(&cells[0].spans(40.0, 60.0), &[(0.0, 100.0)]);
    // The same, with an extra anchor on one side of the shared edge.
    let split =
        closed(&[&[(0.0, 0.0), (50.0, 0.0), (50.0, 50.0), (50.0, 100.0), (0.0, 100.0)], &[(50.0, 0.0), (100.0, 0.0), (100.0, 100.0), (50.0, 100.0)]]);
    let cells = Region::cells(&split, &LayoutOptions::default(), &[]);
    assert_spans(&cells[0].spans(40.0, 60.0), &[(0.0, 100.0)]);
    // A slanted shared edge with an extra anchor on one side.
    let slanted =
        closed(&[&[(0.0, 0.0), (40.0, 0.0), (50.0, 50.0), (60.0, 100.0), (0.0, 100.0)], &[(40.0, 0.0), (100.0, 0.0), (100.0, 100.0), (60.0, 100.0)]]);
    let cells = Region::cells(&slanted, &LayoutOptions::default(), &[]);
    assert_spans(&cells[0].spans(40.0, 60.0), &[(0.0, 100.0)]);
    // Slanted edges of two contours 1e-7 pt apart are not one edge: the line stops at each.
    let near =
        closed(&[&[(0.0, 0.0), (40.0, 0.0), (60.0, 100.0), (0.0, 100.0)], &[(40.0 + 1e-7, 0.0), (100.0, 0.0), (100.0, 100.0), (60.0 + 1e-7, 100.0)]]);
    let cells = Region::cells(&near, &LayoutOptions::default(), &[]);
    assert_spans(&cells[0].spans(40.0, 60.0), &[(0.0, 48.0), (52.0 + 1e-7, 100.0)]);
    // The same 1e-6 pt apart, 1e8 pt from the origin.
    let (x, y) = (1e8, 1e8);
    let far = closed(&[
        &[(x, y), (x + 40.0, y), (x + 60.0, y + 100.0), (x, y + 100.0)],
        &[(x + 40.0 + 1e-6, y), (x + 100.0, y), (x + 100.0, y + 100.0), (x + 60.0 + 1e-6, y + 100.0)],
    ]);
    let cells = Region::cells(&far, &LayoutOptions::default(), &[]);
    let spans = cells[0].spans(y + 40.0, y + 60.0);
    assert!(spans.len() == 2 && spans[0].1 < x + 48.001 && spans[1].0 > x + 51.999, "{spans:?}");
    // A real gap of 0.01 pt between contours far from the origin stays a gap.
    let x = 1e8;
    let apart = closed(&[
        &[(x, 0.0), (x + 50.0, 0.0), (x + 50.0, 100.0), (x, 100.0)],
        &[(x + 50.01, 0.0), (x + 100.0, 0.0), (x + 100.0, 100.0), (x + 50.01, 100.0)],
    ]);
    let cells = Region::cells(&apart, &LayoutOptions::default(), &[]);
    assert_spans(&cells[0].spans(40.0, 60.0), &[(x, x + 50.0), (x + 50.01, x + 100.0)]);
    // So does a gap of 1e-7 pt between vertical edges there, a few units of rounding wide.
    let apart = closed(&[
        &[(x, 0.0), (x + 50.0, 0.0), (x + 50.0, 100.0), (x, 100.0)],
        &[(x + 50.0 + 1e-7, 0.0), (x + 100.0, 0.0), (x + 100.0, 100.0), (x + 50.0 + 1e-7, 100.0)],
    ]);
    let cells = Region::cells(&apart, &LayoutOptions::default(), &[]);
    assert_spans(&cells[0].spans(40.0, 60.0), &[(x, x + 50.0), (x + 50.0 + 1e-7, x + 100.0)]);
}

/// Slanted edges of two contours four units in the last place apart, or one, near the edge of the
/// canvas are not one edge: the line stops at each and keeps the gap between them.
#[cfg(test)]
#[test]
fn separate_slanted_contours_keep_a_four_ulp_gap_near_canvas_limit() {
    let x = 3_999_000.0;
    let ulp = 2f64.powi(-31);
    assert_eq!((x + ulp).to_bits(), x.to_bits() + 1);
    for gap in [4.0 * ulp, ulp] {
        let frame = closed(&[
            &[(x - 100.0, 0.0), (x, 0.0), (x + 10.0, 10.0), (x - 90.0, 10.0)],
            &[(x + gap, 0.0), (x + 100.0 + gap, 0.0), (x + 110.0 + gap, 10.0), (x + 10.0 + gap, 10.0)],
        ]);
        let cells = Region::cells(&frame, &LayoutOptions::default(), &[]);
        let spans = cells[0].spans(1.0, 9.0);
        assert_spans(&spans, &[(x - 91.0, x + 1.0), (x + 9.0 + gap, x + 101.0 + gap)]);
        assert!(spans[0].1 < spans[1].0, "gap {gap}: {spans:?}");
    }
}

/// Contours that share a slanted edge near the edge of the canvas, whole or divided by an anchor
/// exactly on it, hold lines across it. So do contours whose shared edge is divided where the
/// crossing found from the divided edge's own ends rounds to another x than the whole edge's.
#[cfg(test)]
#[test]
fn shared_slanted_edge_still_joins_near_canvas_limit() {
    let x = 3_999_000.0;
    let left: &[(f64, f64)] = &[(x - 100.0, 0.0), (x, 0.0), (x + 10.0, 10.0), (x - 90.0, 10.0)];
    let whole: &[(f64, f64)] = &[(x, 0.0), (x + 100.0, 0.0), (x + 110.0, 10.0), (x + 10.0, 10.0)];
    let divided: &[(f64, f64)] = &[(x, 0.0), (x + 100.0, 0.0), (x + 110.0, 10.0), (x + 10.0, 10.0), (x + 2.5, 2.5)];
    for right in [whole, divided] {
        let cells = Region::cells(&closed(&[left, right]), &LayoutOptions::default(), &[]);
        assert_spans(&cells[0].spans(1.0, 9.0), &[(x - 91.0, x + 101.0)]);
    }
    // (0.75, 1.75) lies exactly on the edge from (0, 0) to (3, 7).
    let left: &[(f64, f64)] = &[(-100.0, 0.0), (0.0, 0.0), (3.0, 7.0), (-97.0, 7.0)];
    let right: &[(f64, f64)] = &[(0.0, 0.0), (100.0, 0.0), (103.0, 7.0), (3.0, 7.0), (0.75, 1.75)];
    let (top, bottom) = (1.404, 2.404);
    let y = (top + bottom) * 0.5;
    assert_ne!(line_x(Point::new(0.0, 0.0), Point::new(3.0, 7.0), y), line_x(Point::new(0.75, 1.75), Point::new(3.0, 7.0), y));
    let cells = Region::cells(&closed(&[left, right]), &LayoutOptions::default(), &[]);
    assert_spans(&cells[0].spans(top, bottom), &[(-100.0 + 3.0 * bottom / 7.0, 100.0 + 3.0 * top / 7.0)]);
}

/// A slanted edge and a vertical edge of two contours less than one unit in the last place apart
/// near the edge of the canvas, whose crossings of the band's middle round to the same x, are not
/// one edge: the line stops at the gap, drawn either way around.
#[cfg(test)]
#[test]
fn contours_whose_crossings_round_together_stay_apart() {
    let x = 3_999_000.0;
    let u = 2f64.powi(-31);
    assert_eq!((x + u).to_bits(), x.to_bits() + 1);
    let left: &[(f64, f64)] = &[(x - 100.0, 0.0), (x, 0.0), (x + u, 10.0), (x - 100.0, 10.0)];
    let right: &[(f64, f64)] = &[(x + u, 0.0), (x + 100.0, 0.0), (x + 100.0, 10.0), (x + u, 10.0)];
    let mirror = |c: &[(f64, f64)]| -> Vec<(f64, f64)> { c.iter().map(|&(px, py)| (px, 10.0 - py)).collect() };
    let (left_m, right_m) = (mirror(left), mirror(right));
    for frame in [closed(&[left, right]), closed(&[&right_m, &left_m])] {
        let cells = Region::cells(&frame, &LayoutOptions::default(), &[]);
        for (top, bottom) in [(8.0, 9.0), (1.0, 2.0)] {
            let spans = cells[0].spans(top, bottom);
            assert_eq!(spans.len(), 2, "{top}..{bottom}: {spans:?}");
            assert_spans(&spans, &[(x - 100.0, x + u), (x + u, x + 100.0)]);
        }
    }
}

/// Area type in two slanted contours four units in the last place apart near the edge of the canvas
/// sets no line across the gap between them.
#[cfg(test)]
#[test]
fn area_type_sets_no_line_across_a_four_ulp_gap_between_slanted_contours() {
    let x = 3_999_000.0;
    let gap = 4.0 * 2f64.powi(-31);
    let frame = closed(&[
        &[(x - 200.0, 0.0), (x, 0.0), (x + 100.0, 100.0), (x - 100.0, 100.0)],
        &[(x + gap, 0.0), (x + 200.0 + gap, 0.0), (x + 300.0 + gap, 100.0), (x + 100.0 + gap, 100.0)],
    ]);
    let style = vectorcraft_doc::CharStyle { size: 10.0, ..vectorcraft_doc::CharStyle::default() };
    let mut t = crate::TextObject::point(Point::ZERO, &"word ".repeat(400), style);
    t.kind = vectorcraft_doc::TextKind::Area { frame: PathData::from_bezpath(&frame) };
    let laid = crate::layout(crate::FontDb::global(), &t);
    assert!(!laid.lines.is_empty());
    // Each contour is 200 pt wide at any height; the two together are twice that.
    for line in &laid.lines {
        assert!(line.x1 - line.x0 < 200.0, "{} to {}", line.x0, line.x1);
    }
}

/// A frame of 200 thin slanted strips, whose edges in the band overlap in x far more than
/// [`MAX_EDGE_PAIRS`] times, holds no line in the band (no strip holds a vertical line across it).
#[cfg(test)]
#[test]
fn many_overlapping_edges_in_a_band_hold_no_line_outside_the_frame() {
    let strips: Vec<Vec<(f64, f64)>> =
        (0..200).map(|i| f64::from(i) * 2.0).map(|x| vec![(x, 0.0), (x + 1.0, 0.0), (x + 501.0, 100.0), (x + 500.0, 100.0)]).collect();
    let strips: Vec<&[(f64, f64)]> = strips.iter().map(Vec::as_slice).collect();
    let cells = Region::cells(&closed(&strips), &LayoutOptions::default(), &[]);
    assert!(cells[0].spans(40.0, 60.0).is_empty());
    assert!(!cells[0].spans(50.0, 50.0).is_empty());
}

/// A frame shorter than the band's margin at the frame's top and bottom holds no line and does
/// not panic; a rectangle keeps its inset spans, top and bottom.
#[cfg(test)]
#[test]
fn flat_frames_and_rectangles_keep_their_spans() {
    for height in [0.0, 1e-5] {
        let flat = closed(&[&[(0.0, 0.0), (10.0, 0.0), (0.0, height)], &[(20.0, 0.0), (30.0, 0.0), (20.0, height)]]);
        let cells = Region::cells(&flat, &LayoutOptions::default(), &[]);
        assert!(!cells[0].rect);
        assert!(cells[0].spans(-5.0, 5.0).iter().all(|&(a, b)| b - a < 1e-3));
    }
    let square = Rect::new(0.0, 0.0, 100.0, 100.0).to_path(0.1);
    let cells = Region::cells(&square, &LayoutOptions { inset: 10.0, ..LayoutOptions::default() }, &[]);
    assert!(cells[0].rect);
    assert_eq!((cells[0].top(), cells[0].bottom()), (10.0, 90.0));
    assert_spans(&cells[0].spans(40.0, 60.0), &[(10.0, 90.0)]);
}

/// On a triangle, the inset keeps the line 10 pt from the sloped edge, measured from the edge
/// itself (x + y <= 100 - 10√2 at the band's bottom), not 10 pt along the line.
#[cfg(test)]
#[test]
fn inset_on_a_shaped_frame_is_measured_from_its_sloped_edge() {
    let triangle = closed(&[&[(0.0, 0.0), (100.0, 0.0), (0.0, 100.0)]]);
    let inset = |inset| cell_spans(&triangle, &LayoutOptions { inset, ..LayoutOptions::default() }, &[], 40.0, 60.0);
    assert_spans(&inset(10.0)[0], &[(10.0, 40.0 - 10.0 * std::f64::consts::SQRT_2)]);
    assert_spans(&inset(0.0)[0], &[(0.0, 40.0)]);
}

/// A rectangular frame keeps its inset from each side, and its first line starts the inset below
/// its top.
#[cfg(test)]
#[test]
fn a_rectangular_frame_keeps_its_inset_from_each_side() {
    let cells = Region::cells(&Rect::new(0.0, 0.0, 100.0, 100.0).to_path(0.1), &LayoutOptions { inset: 10.0, ..LayoutOptions::default() }, &[]);
    assert!(cells[0].rect);
    assert_eq!((cells[0].top(), cells[0].bottom()), (10.0, 90.0));
    assert_spans(&cells[0].spans(40.0, 60.0), &[(10.0, 90.0)]);
}

/// The inset keeps text clear of a hole's sloped edges too.
#[cfg(test)]
#[test]
fn inset_keeps_text_clear_of_a_hole_s_sloped_edges() {
    let square = [(0.0, 0.0), (100.0, 0.0), (100.0, 100.0), (0.0, 100.0)];
    let diamond = [(50.0, 30.0), (70.0, 50.0), (50.0, 70.0), (30.0, 50.0)];
    let spans = cell_spans(&closed(&[&square, &diamond]), &LayoutOptions { inset: 5.0, ..LayoutOptions::default() }, &[], 40.0, 44.0);
    let clear = 5.0 * std::f64::consts::SQRT_2;
    assert_spans(&spans[0], &[(5.0, 36.0 - clear), (64.0 + clear, 95.0)]);
}

/// The inset is not kept beside an edge two contours share, vertical, horizontal or slanted with an
/// extra anchor on one side, and is still kept beside the part of an edge only one contour covers.
#[cfg(test)]
#[test]
fn inset_is_not_kept_beside_an_edge_two_contours_share() {
    let opts = LayoutOptions { inset: 5.0, ..LayoutOptions::default() };
    let side = closed(&[&[(0.0, 0.0), (50.0, 0.0), (50.0, 100.0), (0.0, 100.0)], &[(50.0, 0.0), (100.0, 0.0), (100.0, 100.0), (50.0, 100.0)]]);
    assert_spans(&cell_spans(&side, &opts, &[], 40.0, 44.0)[0], &[(5.0, 95.0)]);
    let seam = closed(&[&[(0.0, 0.0), (100.0, 0.0), (100.0, 50.0), (0.0, 50.0)], &[(0.0, 50.0), (100.0, 50.0), (100.0, 100.0), (0.0, 100.0)]]);
    assert_spans(&cell_spans(&seam, &opts, &[], 46.0, 54.0)[0], &[(5.0, 95.0)]);
    let slanted =
        closed(&[&[(0.0, 0.0), (40.0, 0.0), (50.0, 50.0), (60.0, 100.0), (0.0, 100.0)], &[(40.0, 0.0), (100.0, 0.0), (100.0, 100.0), (60.0, 100.0)]]);
    assert_spans(&cell_spans(&slanted, &opts, &[], 40.0, 44.0)[0], &[(5.0, 95.0)]);
    // The lower contour covers only the left half of the upper one's bottom edge: the right half
    // and the corner where they meet still keep the inset.
    let step = closed(&[&[(0.0, 0.0), (100.0, 0.0), (100.0, 50.0), (0.0, 50.0)], &[(0.0, 50.0), (50.0, 50.0), (50.0, 100.0), (0.0, 100.0)]]);
    assert_spans(&cell_spans(&step, &opts, &[], 46.0, 48.0)[0], &[(5.0, 50.0 - 21f64.sqrt())]);
}

/// A negative wrap offset does not shrink a wrap object beside an edge two of its contours share,
/// with or without Invert Wrap.
#[cfg(test)]
#[test]
fn negative_wrap_offset_does_not_shrink_beside_an_edge_two_contours_share() {
    let left: &[(f64, f64)] = &[(40.0, 40.0), (50.0, 40.0), (50.0, 60.0), (40.0, 60.0)];
    let right: &[(f64, f64)] = &[(50.0, 40.0), (60.0, 40.0), (60.0, 60.0), (50.0, 60.0)];
    assert_spans(&wrap_spans(&[left, right], -5.0, false, 44.0, 50.0), &[(0.0, 45.0), (55.0, 100.0)]);
    assert_spans(&wrap_spans(&[left, right], -5.0, true, 46.0, 54.0), &[(45.0, 55.0)]);
}

/// In a frame of columns, the inset is kept once from a column's inner edge and once from the
/// frame's sloped edge.
#[cfg(test)]
#[test]
fn inset_applies_once_at_a_column_s_edge_and_at_the_frame_s_edge() {
    let triangle = closed(&[&[(0.0, 0.0), (100.0, 0.0), (0.0, 100.0)]]);
    let spans = cell_spans(&triangle, &LayoutOptions { inset: 10.0, columns: 2, gutter: 0.0, ..LayoutOptions::default() }, &[], 10.0, 20.0);
    assert_spans(&spans[0], &[(10.0, 40.0)]);
    assert_spans(&spans[1], &[(60.0, 80.0 - 10.0 * std::f64::consts::SQRT_2)]);
}

/// An inset wider than a shaped frame leaves no room for text, whatever its size.
#[cfg(test)]
#[test]
fn an_inset_wider_than_a_shaped_frame_leaves_no_room() {
    let triangle = closed(&[&[(0.0, 0.0), (100.0, 0.0), (0.0, 100.0)]]);
    for inset in [40.0, 1e300, f64::INFINITY] {
        let cells = Region::cells(&triangle, &LayoutOptions { inset, ..LayoutOptions::default() }, &[]);
        assert!(cells[0].spans(40.0, 60.0).is_empty() && cells[0].span(40.0, 60.0).is_none(), "inset {inset}");
    }
}

/// `a` ∩ `b` by comparing every interval of `a` with every interval of `b`: the result
/// [`intersect_intervals`] is checked against.
#[cfg(test)]
fn intersect_every_pair(a: &[(f64, f64)], b: &[(f64, f64)]) -> Vec<(f64, f64)> {
    a.iter().flat_map(|&(s, e)| b.iter().map(move |&(c, d)| (s.max(c), e.min(d)))).filter(|(x, y)| y > x).collect()
}

/// The intersection of two lists of intervals, each sorted with no two overlapping, is the one
/// every pair of their intervals gives, in the same order, left to right and of positive width, for
/// every pair of such lists whose ends are among the points 0 to 6: empty lists, intervals that
/// only touch (in one list or across the two), that end together, that hold one another and that
/// overlap several others.
#[cfg(test)]
#[test]
fn intervals_intersect_as_every_pair_of_them_does() {
    // Every list is a shorter list with one more interval after its last.
    let mut lists: Vec<Vec<(f64, f64)>> = vec![vec![]];
    let mut k = 0;
    while let Some(list) = lists.get(k).cloned() {
        let from = list.last().map_or(0, |l: &(f64, f64)| l.1 as u8);
        for s in from..6 {
            for e in s + 1..=6 {
                let mut next = list.clone();
                next.push((f64::from(s), f64::from(e)));
                lists.push(next);
            }
        }
        k += 1;
    }
    assert_eq!(lists.len(), 233);
    for a in &lists {
        for b in &lists {
            let got = intersect_intervals(a, b);
            assert_eq!(got, intersect_every_pair(a, b), "{a:?} ∩ {b:?}");
            assert!(got.iter().all(|(x, y)| y > x) && got.windows(2).all(|w| w[0].1 <= w[1].0), "{got:?}");
        }
    }
}

/// Intersecting two unions of 3,000 and 2,000 intervals that interleave looks at no more than
/// 5,000 pairs of intervals, not every one of the 6,000,000 pairs.
#[cfg(test)]
#[test]
fn intersecting_intervals_looks_at_each_interval_once() {
    let a: Vec<(f64, f64)> = (0..3000).map(|i| f64::from(i) * 4.0).map(|x| (x, x + 3.0)).collect();
    let b: Vec<(f64, f64)> = (0..2000).map(|i| f64::from(i) * 6.0).map(|x| (x + 1.0, x + 5.0)).collect();
    INTERSECT_PAIRS.set(0);
    let got = intersect_intervals(&a, &b);
    assert!(INTERSECT_PAIRS.get() <= a.len() + b.len(), "{} pairs", INTERSECT_PAIRS.get());
    assert_eq!(got, intersect_every_pair(&a, &b));
    assert!(!got.is_empty());
}

/// A line in area type with an Invert Wrap comb of 500 teeth and an offset keeps a span inside
/// each tooth, left to right, and measuring the grown comb takes a few dozen steps for each tooth,
/// not one for each pair of teeth.
#[cfg(test)]
#[test]
fn a_line_inside_an_invert_wrap_comb_keeps_a_span_in_each_tooth() {
    let frame = Rect::new(0.0, 0.0, 1000.0, 100.0).to_path(0.1);
    let teeth: Vec<Vec<(f64, f64)>> =
        (0..500).map(|k| f64::from(k) * 2.0).map(|x| vec![(x, 0.0), (x + 1.0, 0.0), (x + 1.0, 100.0), (x, 100.0)]).collect();
    let teeth: Vec<&[(f64, f64)]> = teeth.iter().map(Vec::as_slice).collect();
    let path = PathData::from_bezpath(&closed(&teeth));
    let wrap = vectorcraft_doc::WrapShape { path, wrap: vectorcraft_doc::TextWrap { offset: 0.25, invert: true } };
    let cells = Region::cells(&frame, &LayoutOptions::default(), &[wrap]);
    INTERSECT_PAIRS.set(0);
    GROWN_BAND_WORK.set(0);
    let got = cells[0].spans(40.0, 60.0);
    let want: Vec<(f64, f64)> = (0..500).map(|k| f64::from(k) * 2.0).map(|x| ((x - 0.25).max(0.0), x + 1.25)).collect();
    assert_spans(&got, &want);
    // The line's one span is intersected once with the 500 spans the grown comb holds.
    assert!(INTERSECT_PAIRS.get() <= 1 + 500, "{} pairs", INTERSECT_PAIRS.get());
    assert!(GROWN_BAND_WORK.get() <= 40 * 500, "{} steps", GROWN_BAND_WORK.get());
}

/// The spans of a 120 pt wide, 100 pt tall frame over the band `top..bottom` with one Invert Wrap
/// object through `contour` and `offset`.
#[cfg(test)]
fn invert_wrap_spans(contour: &[(f64, f64)], offset: f64, top: f64, bottom: f64) -> Vec<(f64, f64)> {
    let frame = Rect::new(0.0, 0.0, 120.0, 100.0).to_path(0.1);
    let path = PathData::from_bezpath(&closed(&[contour]));
    let wrap = vectorcraft_doc::WrapShape { path, wrap: vectorcraft_doc::TextWrap { offset, invert: true } };
    Region::cells(&frame, &LayoutOptions::default(), &[wrap])[0].spans(top, bottom)
}

/// The 100 pt square whose right edge steps in to x = 80 from `y0` to `y1`, with 79 more anchors
/// along its left edge, which leave its shape as it is.
#[cfg(test)]
fn notched_square(y0: f64, y1: f64) -> Vec<(f64, f64)> {
    let mut contour = vec![(0.0, 0.0), (100.0, 0.0), (100.0, y0), (80.0, y0), (80.0, y1), (100.0, y1), (100.0, 100.0), (0.0, 100.0)];
    contour.extend((1..80).rev().map(|i| (0.0, 1.25 * f64::from(i))));
    contour
}

/// With Invert Wrap and an offset, a line beside a notch the offset fills reaches as far as the
/// grown shape does at every height of its band, however tall the band and however many anchors
/// the shape has: a notch 0.5625 pt tall with an offset of 1, and one 0.4 pt tall with an offset
/// of 0.25 over a band of 100 pt.
#[cfg(test)]
#[test]
fn invert_wrap_with_an_offset_lets_a_line_beside_a_notch_reach_the_grown_shape() {
    assert_spans(&invert_wrap_spans(&notched_square(50.5, 51.0625), 1.0, 0.0, 100.0), &[(0.0, 101.0)]);
    assert_spans(&invert_wrap_spans(&notched_square(50.6, 51.0), 0.25, 0.0, 100.0), &[(0.0, 100.25)]);
    // A band of no height in the notch, and one in a notch the offset does not fill.
    assert_spans(&invert_wrap_spans(&notched_square(50.5, 51.0625), 1.0, 50.7, 50.7), &[(0.0, 101.0)]);
    assert_spans(&invert_wrap_spans(&notched_square(50.0, 53.0), 1.0, 0.0, 100.0), &[(0.0, 81.0)]);
    assert_spans(&invert_wrap_spans(&notched_square(50.0, 53.0), 1.0, 51.5, 51.5), &[(0.0, 81.0)]);
}

/// With Invert Wrap and an offset, a line beside a notch with sloped sides reaches as far as the
/// grown shape does at the notch's tip: 1 pt above and below the tip, each side is 8 pt from it.
#[cfg(test)]
#[test]
fn invert_wrap_with_an_offset_lets_a_line_beside_a_sloped_notch_reach_the_grown_shape() {
    let notch = [(0.0, 0.0), (100.0, 0.0), (100.0, 45.15), (60.0, 50.15), (100.0, 55.15), (100.0, 100.0), (0.0, 100.0)];
    assert_spans(&invert_wrap_spans(&notch, 1.0, 40.0, 60.0), &[(0.0, 69.0)]);
    assert_spans(&invert_wrap_spans(&notch, 5.0, 40.0, 60.0), &[(0.0, 105.0)]);
}

/// With Invert Wrap and an offset, a band of no height exactly the offset past a wrap shape's
/// bottom edge or its tip still holds a line as wide as the grown edge or tip.
#[cfg(test)]
#[test]
fn invert_wrap_with_an_offset_holds_a_band_exactly_the_offset_past_the_shape() {
    let bar = [(20.0, 0.0), (60.0, 0.0), (60.0, 10.0), (20.0, 10.0)];
    assert_spans(&invert_wrap_spans(&bar, 1.0, 11.0, 11.0), &[(19.0, 61.0)]);
    assert!(invert_wrap_spans(&bar, 1.0, 11.5, 11.5).is_empty());
    let tip = [(20.0, 0.0), (80.0, 0.0), (50.0, 10.0)];
    assert_spans(&invert_wrap_spans(&tip, 1.0, 11.0, 11.0), &[(49.0, 51.0)]);
    let tip = [(20.0, 20.0), (50.0, 10.0), (80.0, 20.0)];
    assert_spans(&invert_wrap_spans(&tip, 1.0, 9.0, 9.0), &[(49.0, 51.0)]);
}

/// A wrap shape whose edges cross one another tens of thousands of times takes no more than
/// [`MAX_INVERT_WRAP_WORK`] steps to measure exactly; it is then cut into pieces, and the line
/// still stays inside the shape grown by the offset. An offset that is not a number is 0.
#[cfg(test)]
#[test]
fn invert_wrap_with_an_offset_bounds_its_work_on_a_tangled_shape() {
    let star: Vec<Point> = (0..301)
        .map(|k| f64::from(k * 150) * std::f64::consts::TAU / 301.0)
        .map(|a| Point::new(50.0 + 45.0 * a.cos(), 50.0 + 45.0 * a.sin()))
        .collect();
    GROWN_BAND_WORK.set(0);
    assert!(grown_band(std::slice::from_ref(&star), 1.0, 10.0, 90.0, (0.0, 120.0)).is_none());
    assert!(GROWN_BAND_WORK.get() <= 2 * MAX_INVERT_WRAP_WORK, "{} steps", GROWN_BAND_WORK.get());
    let contour: Vec<(f64, f64)> = star.iter().map(|p| (p.x, p.y)).collect();
    let spans = invert_wrap_spans(&contour, 1.0, 10.0, 90.0);
    assert!(spans.iter().all(|&(a, b)| a >= 4.0 && b <= 96.0), "{spans:?}");
    let square = [(40.0, 40.0), (60.0, 40.0), (60.0, 60.0), (40.0, 60.0)];
    assert_spans(&invert_wrap_spans(&square, f64::NAN, 45.0, 55.0), &invert_wrap_spans(&square, 0.0, 45.0, 55.0));
    assert_spans(&invert_wrap_spans(&square, 0.0, 45.0, 55.0), &[(40.0, 60.0)]);
}

/// Along the line, text keeps the inset beside a wrap object, around it and, with Invert Wrap,
/// inside it.
#[cfg(test)]
#[test]
fn text_keeps_the_inset_beside_a_wrap_object_along_the_line() {
    let frame = Rect::new(0.0, 0.0, 100.0, 100.0).to_path(0.1);
    let shape = PathData::from_bezpath(&Rect::new(40.0, 40.0, 60.0, 60.0).to_path(0.1));
    let opts = LayoutOptions { inset: 5.0, ..LayoutOptions::default() };
    for (invert, want) in [(false, vec![(5.0, 35.0), (65.0, 95.0)]), (true, vec![(45.0, 55.0)])] {
        let wrap = vectorcraft_doc::WrapShape { path: shape.clone(), wrap: vectorcraft_doc::TextWrap { offset: 0.0, invert } };
        assert_spans(&cell_spans(&frame, &opts, &[wrap], 45.0, 55.0)[0], &want);
    }
}