KiCad - the KiCad Bridge

//! SVG artwork to filled polygons in millimetres, in pure Rust: paths (every command,
//! curves and arcs flattened), rect, circle, ellipse, polygon and polyline, nested group
//! transforms, the root viewBox and its physical width/height. Holes (a subpath inside
//! another, by containment depth, which is what both fill rules give for ordinary logo
//! art) are joined to their outline by a zero-width cut, the way KiCad's own fractured
//! polygons are, because a KiCad `gr_poly` has no holes.

use quick_xml::events::Event;
use quick_xml::Reader;

pub type Pt = (f64, f64);

/// 2D affine matrix [a b c d e f]: x' = a x + c y + e, y' = b x + d y + f.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Mat(pub [f64; 6]);

impl Mat {
    pub const ID: Mat = Mat([1.0, 0.0, 0.0, 1.0, 0.0, 0.0]);
    pub fn mul(&self, o: &Mat) -> Mat {
        let [a, b, c, d, e, f] = self.0;
        let [a2, b2, c2, d2, e2, f2] = o.0;
        Mat([a * a2 + c * b2, b * a2 + d * b2, a * c2 + c * d2, b * c2 + d * d2, a * e2 + c * f2 + e, b * e2 + d * f2 + f])
    }
    pub fn apply(&self, p: Pt) -> Pt {
        let [a, b, c, d, e, f] = self.0;
        (a * p.0 + c * p.1 + e, b * p.0 + d * p.1 + f)
    }
    fn scale_factor(&self) -> f64 {
        let [a, b, c, d, _, _] = self.0;
        ((a * d - b * c).abs()).sqrt().max(1e-12)
    }
}

fn numbers(s: &str) -> Vec<f64> {
    let mut out = Vec::new();
    let b = s.as_bytes();
    let mut i = 0;
    while i < b.len() {
        let c = b[i] as char;
        if c.is_ascii_digit() || c == '-' || c == '+' || c == '.' {
            let start = i;
            let mut seen_dot = c == '.';
            let mut seen_e = false;
            i += 1;
            while i < b.len() {
                let d = b[i] as char;
                if d.is_ascii_digit() {
                    i += 1;
                } else if d == '.' && !seen_dot && !seen_e {
                    seen_dot = true;
                    i += 1;
                } else if (d == 'e' || d == 'E') && !seen_e {
                    seen_e = true;
                    i += 1;
                    if i < b.len() && (b[i] == b'-' || b[i] == b'+') {
                        i += 1;
                    }
                } else {
                    break;
                }
            }
            if let Ok(v) = s[start..i].parse::<f64>() {
                out.push(v);
            }
        } else {
            i += 1;
        }
    }
    out
}

/// An SVG `transform` attribute.
pub fn parse_transform(s: &str) -> Mat {
    let mut m = Mat::ID;
    let mut rest = s;
    while let Some(open) = rest.find('(') {
        let name = rest[..open].trim().trim_start_matches(',').trim();
        let Some(close) = rest[open..].find(')') else { break };
        let args = numbers(&rest[open + 1..open + close]);
        let t = match (name, args.as_slice()) {
            ("matrix", [a, b, c, d, e, f]) => Mat([*a, *b, *c, *d, *e, *f]),
            ("translate", [x]) => Mat([1.0, 0.0, 0.0, 1.0, *x, 0.0]),
            ("translate", [x, y]) => Mat([1.0, 0.0, 0.0, 1.0, *x, *y]),
            ("scale", [s]) => Mat([*s, 0.0, 0.0, *s, 0.0, 0.0]),
            ("scale", [sx, sy]) => Mat([*sx, 0.0, 0.0, *sy, 0.0, 0.0]),
            ("rotate", [a]) => {
                let (s, c) = a.to_radians().sin_cos();
                Mat([c, s, -s, c, 0.0, 0.0])
            }
            ("rotate", [a, cx, cy]) => {
                let (s, c) = a.to_radians().sin_cos();
                Mat([1.0, 0.0, 0.0, 1.0, *cx, *cy]).mul(&Mat([c, s, -s, c, 0.0, 0.0])).mul(&Mat([1.0, 0.0, 0.0, 1.0, -cx, -cy]))
            }
            ("skewX", [a]) => Mat([1.0, 0.0, a.to_radians().tan(), 1.0, 0.0, 0.0]),
            ("skewY", [a]) => Mat([1.0, a.to_radians().tan(), 0.0, 1.0, 0.0, 0.0]),
            _ => Mat::ID,
        };
        m = m.mul(&t);
        rest = &rest[open + close + 1..];
    }
    m
}

fn steps_for(len: f64, tol: f64) -> usize {
    ((len / tol).sqrt().ceil() as usize).clamp(4, 96)
}

fn cubic(p0: Pt, p1: Pt, p2: Pt, p3: Pt, tol: f64, out: &mut Vec<Pt>) {
    let len = dist(p0, p1) + dist(p1, p2) + dist(p2, p3);
    let n = steps_for(len, tol);
    for i in 1..=n {
        let t = i as f64 / n as f64;
        let u = 1.0 - t;
        let (a, b, c, d) = (u * u * u, 3.0 * u * u * t, 3.0 * u * t * t, t * t * t);
        out.push((a * p0.0 + b * p1.0 + c * p2.0 + d * p3.0, a * p0.1 + b * p1.1 + c * p2.1 + d * p3.1));
    }
}

fn quad(p0: Pt, p1: Pt, p2: Pt, tol: f64, out: &mut Vec<Pt>) {
    let n = steps_for(dist(p0, p1) + dist(p1, p2), tol);
    for i in 1..=n {
        let t = i as f64 / n as f64;
        let u = 1.0 - t;
        out.push((u * u * p0.0 + 2.0 * u * t * p1.0 + t * t * p2.0, u * u * p0.1 + 2.0 * u * t * p1.1 + t * t * p2.1));
    }
}

fn dist(a: Pt, b: Pt) -> f64 {
    ((a.0 - b.0).powi(2) + (a.1 - b.1).powi(2)).sqrt()
}

/// SVG elliptical arc (endpoint parameterisation, F.6.5 of the SVG spec), flattened.
#[allow(clippy::too_many_arguments)]
fn arc(p0: Pt, rx: f64, ry: f64, phi_deg: f64, large: bool, sweep: bool, p1: Pt, tol: f64, out: &mut Vec<Pt>) {
    let (mut rx, mut ry) = (rx.abs(), ry.abs());
    if rx < 1e-12 || ry < 1e-12 || dist(p0, p1) < 1e-12 {
        out.push(p1);
        return;
    }
    let (s, c) = phi_deg.to_radians().sin_cos();
    let (dx, dy) = ((p0.0 - p1.0) / 2.0, (p0.1 - p1.1) / 2.0);
    let (x1, y1) = (c * dx + s * dy, -s * dx + c * dy);
    let lam = (x1 * x1) / (rx * rx) + (y1 * y1) / (ry * ry);
    if lam > 1.0 {
        rx *= lam.sqrt();
        ry *= lam.sqrt();
    }
    let num = rx * rx * ry * ry - rx * rx * y1 * y1 - ry * ry * x1 * x1;
    let den = rx * rx * y1 * y1 + ry * ry * x1 * x1;
    let mut k = (num / den).max(0.0).sqrt();
    if large == sweep {
        k = -k;
    }
    let (cx1, cy1) = (k * rx * y1 / ry, -k * ry * x1 / rx);
    let (cx, cy) = (c * cx1 - s * cy1 + (p0.0 + p1.0) / 2.0, s * cx1 + c * cy1 + (p0.1 + p1.1) / 2.0);
    let ang = |ux: f64, uy: f64, vx: f64, vy: f64| {
        let d = (ux * vx + uy * vy) / ((ux * ux + uy * uy).sqrt() * (vx * vx + vy * vy).sqrt());
        let a = d.clamp(-1.0, 1.0).acos();
        if ux * vy - uy * vx < 0.0 { -a } else { a }
    };
    let t1 = ang(1.0, 0.0, (x1 - cx1) / rx, (y1 - cy1) / ry);
    let mut dt = ang((x1 - cx1) / rx, (y1 - cy1) / ry, (-x1 - cx1) / rx, (-y1 - cy1) / ry);
    if !sweep && dt > 0.0 {
        dt -= 2.0 * std::f64::consts::PI;
    } else if sweep && dt < 0.0 {
        dt += 2.0 * std::f64::consts::PI;
    }
    let n = steps_for(rx.max(ry) * dt.abs(), tol).max((dt.abs() / 0.2).ceil() as usize).min(180);
    for i in 1..=n {
        let t = t1 + dt * i as f64 / n as f64;
        let (st, ct) = t.sin_cos();
        out.push((c * rx * ct - s * ry * st + cx, s * rx * ct + c * ry * st + cy));
    }
    if let Some(l) = out.last_mut() {
        *l = p1;
    }
}

/// A path's `d` as closed rings (every subpath is closed for filling).
pub fn path_rings(d: &str, tol: f64) -> Vec<Vec<Pt>> {
    let mut rings: Vec<Vec<Pt>> = Vec::new();
    let mut cur: Vec<Pt> = Vec::new();
    let (mut p, mut start) = ((0.0, 0.0), (0.0, 0.0));
    let mut last_ctrl: Option<(char, Pt)> = None;
    // tokenise into commands and their numbers
    let mut cmds: Vec<(char, Vec<f64>)> = Vec::new();
    let mut buf = String::new();
    let mut cmd: Option<char> = None;
    for ch in d.chars() {
        if ch.is_ascii_alphabetic() && ch != 'e' && ch != 'E' {
            if let Some(c) = cmd {
                cmds.push((c, numbers(&buf)));
            }
            buf.clear();
            cmd = Some(ch);
        } else {
            buf.push(ch);
        }
    }
    if let Some(c) = cmd {
        cmds.push((c, numbers(&buf)));
    }
    let flush = |cur: &mut Vec<Pt>, rings: &mut Vec<Vec<Pt>>| {
        if cur.len() >= 3 {
            rings.push(std::mem::take(cur));
        } else {
            cur.clear();
        }
    };
    for (c, args) in cmds {
        let rel = c.is_ascii_lowercase();
        let base = |p: Pt, x: f64, y: f64| if rel { (p.0 + x, p.1 + y) } else { (x, y) };
        match c.to_ascii_uppercase() {
            'M' => {
                flush(&mut cur, &mut rings);
                for (i, xy) in args.chunks(2).enumerate() {
                    if xy.len() < 2 {
                        break;
                    }
                    p = base(p, xy[0], xy[1]);
                    if i == 0 {
                        start = p;
                    }
                    cur.push(p);
                }
                last_ctrl = None;
            }
            'L' => {
                for xy in args.chunks(2).filter(|c| c.len() == 2) {
                    p = base(p, xy[0], xy[1]);
                    cur.push(p);
                }
                last_ctrl = None;
            }
            'H' => {
                for x in &args {
                    p = (if rel { p.0 + x } else { *x }, p.1);
                    cur.push(p);
                }
                last_ctrl = None;
            }
            'V' => {
                for y in &args {
                    p = (p.0, if rel { p.1 + y } else { *y });
                    cur.push(p);
                }
                last_ctrl = None;
            }
            'C' => {
                for a in args.chunks(6).filter(|c| c.len() == 6) {
                    let (c1, c2, e) = (base(p, a[0], a[1]), base(p, a[2], a[3]), base(p, a[4], a[5]));
                    cubic(p, c1, c2, e, tol, &mut cur);
                    last_ctrl = Some(('C', c2));
                    p = e;
                }
            }
            'S' => {
                for a in args.chunks(4).filter(|c| c.len() == 4) {
                    let c1 = match last_ctrl {
                        Some(('C', q)) => (2.0 * p.0 - q.0, 2.0 * p.1 - q.1),
                        _ => p,
                    };
                    let (c2, e) = (base(p, a[0], a[1]), base(p, a[2], a[3]));
                    cubic(p, c1, c2, e, tol, &mut cur);
                    last_ctrl = Some(('C', c2));
                    p = e;
                }
            }
            'Q' => {
                for a in args.chunks(4).filter(|c| c.len() == 4) {
                    let (c1, e) = (base(p, a[0], a[1]), base(p, a[2], a[3]));
                    quad(p, c1, e, tol, &mut cur);
                    last_ctrl = Some(('Q', c1));
                    p = e;
                }
            }
            'T' => {
                for a in args.chunks(2).filter(|c| c.len() == 2) {
                    let c1 = match last_ctrl {
                        Some(('Q', q)) => (2.0 * p.0 - q.0, 2.0 * p.1 - q.1),
                        _ => p,
                    };
                    let e = base(p, a[0], a[1]);
                    quad(p, c1, e, tol, &mut cur);
                    last_ctrl = Some(('Q', c1));
                    p = e;
                }
            }
            'A' => {
                for a in args.chunks(7).filter(|c| c.len() == 7) {
                    let e = base(p, a[5], a[6]);
                    arc(p, a[0], a[1], a[2], a[3] != 0.0, a[4] != 0.0, e, tol, &mut cur);
                    p = e;
                }
                last_ctrl = None;
            }
            'Z' => {
                flush(&mut cur, &mut rings);
                p = start;
                cur.push(p);
                last_ctrl = None;
            }
            _ => {}
        }
    }
    flush(&mut cur, &mut rings);
    for r in rings.iter_mut() {
        dedup_ring(r);
    }
    rings.retain(|r| r.len() >= 3 && area(r).abs() > 1e-12);
    rings
}

fn dedup_ring(r: &mut Vec<Pt>) {
    r.dedup_by(|a, b| dist(*a, *b) < 1e-9);
    while r.len() > 1 && dist(r[0], *r.last().unwrap()) < 1e-9 {
        r.pop();
    }
}

pub fn area(r: &[Pt]) -> f64 {
    let mut s = 0.0;
    for i in 0..r.len() {
        let (a, b) = (r[i], r[(i + 1) % r.len()]);
        s += a.0 * b.1 - b.0 * a.1;
    }
    s / 2.0
}

fn inside(p: Pt, r: &[Pt]) -> bool {
    let mut c = false;
    let mut j = r.len() - 1;
    for i in 0..r.len() {
        let (a, b) = (r[i], r[j]);
        if (a.1 > p.1) != (b.1 > p.1) && p.0 < (b.0 - a.0) * (p.1 - a.1) / (b.1 - a.1) + a.0 {
            c = !c;
        }
        j = i;
    }
    c
}

fn ellipse_ring(cx: f64, cy: f64, rx: f64, ry: f64, tol: f64) -> Vec<Pt> {
    let n = steps_for(2.0 * std::f64::consts::PI * rx.max(ry), tol).max(24).min(180);
    (0..n).map(|i| {
        let t = 2.0 * std::f64::consts::PI * i as f64 / n as f64;
        (cx + rx * t.cos(), cy + ry * t.sin())
    }).collect()
}

fn unit_mm(v: &str) -> Option<f64> {
    let v = v.trim();
    let num: String = v.chars().take_while(|c| c.is_ascii_digit() || *c == '.' || *c == '-' || *c == 'e' || *c == '+').collect();
    let x: f64 = num.parse().ok()?;
    let unit = v[num.len()..].trim();
    Some(x * match unit {
        "mm" => 1.0,
        "cm" => 10.0,
        "in" => 25.4,
        "pt" => 25.4 / 72.0,
        "pc" => 25.4 / 6.0,
        "" | "px" => 25.4 / 96.0,
        _ => return None,
    })
}

/// The parsed artwork: filled rings in SVG user units with the user-unit to mm factor
/// and the artwork's bounding box.
#[derive(Debug, Clone)]
pub struct Art {
    pub rings: Vec<Vec<Pt>>,
    pub mm_per_unit: f64,
    pub skipped: Vec<String>,
}

fn attr(e: &quick_xml::events::BytesStart, name: &str) -> Option<String> {
    e.attributes().flatten().find(|a| a.key.as_ref() == name.as_bytes()).and_then(|a| a.unescape_value().ok().map(|v| v.to_string()))
}

fn style_prop(style: &str, key: &str) -> Option<String> {
    style.split(';').find_map(|kv| {
        let (k, v) = kv.split_once(':')?;
        (k.trim() == key).then(|| v.trim().to_string())
    })
}

/// Parse SVG text into filled rings (user units, root viewBox applied).
pub fn parse_svg(text: &str, tol_mm: f64) -> Result<Art, String> {
    let mut reader = Reader::from_str(text);
    let mut stack: Vec<(Mat, bool)> = vec![(Mat::ID, true)];
    let mut rings = Vec::new();
    let mut skipped = Vec::new();
    let mut mm_per_unit = 25.4 / 96.0;
    let mut seen_root = false;
    let mut defs_depth = 0usize;
    loop {
        let ev = reader.read_event().map_err(|e| format!("SVG parse error: {e}"))?;
        let (e, empty) = match &ev {
            Event::Start(e) => (e.clone(), false),
            Event::Empty(e) => (e.clone(), true),
            Event::End(e) => {
                let name = String::from_utf8_lossy(e.name().as_ref()).to_string();
                if name == "defs" || name == "clipPath" || name == "mask" || name == "symbol" {
                    defs_depth = defs_depth.saturating_sub(1);
                }
                if stack.len() > 1 {
                    stack.pop();
                }
                continue;
            }
            Event::Eof => break,
            _ => continue,
        };
        let name = String::from_utf8_lossy(e.local_name().as_ref()).to_string();
        let (parent, parent_fill) = *stack.last().unwrap();
        let mut m = parent;
        if let Some(t) = attr(&e, "transform") {
            m = m.mul(&parse_transform(&t));
        }
        let style = attr(&e, "style").unwrap_or_default();
        let fill = attr(&e, "fill").or_else(|| style_prop(&style, "fill"));
        let filled = match fill.as_deref() {
            Some("none") | Some("transparent") => false,
            Some(_) => true,
            None => parent_fill,
        };
        if name == "svg" && !seen_root {
            seen_root = true;
            let vb = attr(&e, "viewBox").map(|v| numbers(&v)).filter(|v| v.len() == 4 && v[2] > 0.0 && v[3] > 0.0);
            let w = attr(&e, "width").and_then(|w| unit_mm(&w));
            let h = attr(&e, "height").and_then(|h| unit_mm(&h));
            if let Some(vb) = &vb {
                m = m.mul(&Mat([1.0, 0.0, 0.0, 1.0, -vb[0], -vb[1]]));
                mm_per_unit = match (w, h) {
                    (Some(w), _) => w / vb[2],
                    (None, Some(h)) => h / vb[3],
                    _ => 25.4 / 96.0,
                };
            } else if let Some(w) = w {
                let raw = attr(&e, "width").and_then(|w| numbers(&w).first().copied()).unwrap_or(0.0);
                if raw > 0.0 {
                    mm_per_unit = w / raw;
                }
            }
        }
        if matches!(name.as_str(), "defs" | "clipPath" | "mask" | "symbol") && !empty {
            defs_depth += 1;
        }
        let tol = tol_mm / mm_per_unit.max(1e-9) / m.scale_factor();
        let num = |k: &str| attr(&e, k).and_then(|v| numbers(&v).first().copied());
        let mut local: Vec<Vec<Pt>> = Vec::new();
        if defs_depth == 0 && filled {
            match name.as_str() {
                "path" => local = path_rings(&attr(&e, "d").unwrap_or_default(), tol),
                "rect" => {
                    let (x, y, w, h) = (num("x").unwrap_or(0.0), num("y").unwrap_or(0.0), num("width").unwrap_or(0.0), num("height").unwrap_or(0.0));
                    let rx = num("rx").or(num("ry")).unwrap_or(0.0).min(w / 2.0);
                    let ry = num("ry").or(num("rx")).unwrap_or(0.0).min(h / 2.0);
                    if w > 0.0 && h > 0.0 {
                        if rx > 0.0 && ry > 0.0 {
                            let d = format!("M{} {} H{} A{rx} {ry} 0 0 1 {} {} V{} A{rx} {ry} 0 0 1 {} {} H{} A{rx} {ry} 0 0 1 {} {} V{} A{rx} {ry} 0 0 1 {} {} Z",
                                x + rx, y, x + w - rx, x + w, y + ry, y + h - ry, x + w - rx, y + h, x + rx, x, y + h - ry, y + ry, x + rx, y);
                            local = path_rings(&d, tol);
                        } else {
                            local.push(vec![(x, y), (x + w, y), (x + w, y + h), (x, y + h)]);
                        }
                    }
                }
                "circle" => {
                    let r = num("r").unwrap_or(0.0);
                    if r > 0.0 {
                        local.push(ellipse_ring(num("cx").unwrap_or(0.0), num("cy").unwrap_or(0.0), r, r, tol));
                    }
                }
                "ellipse" => {
                    let (rx, ry) = (num("rx").unwrap_or(0.0), num("ry").unwrap_or(0.0));
                    if rx > 0.0 && ry > 0.0 {
                        local.push(ellipse_ring(num("cx").unwrap_or(0.0), num("cy").unwrap_or(0.0), rx, ry, tol));
                    }
                }
                "polygon" | "polyline" => {
                    let v = numbers(&attr(&e, "points").unwrap_or_default());
                    let r: Vec<Pt> = v.chunks(2).filter(|c| c.len() == 2).map(|c| (c[0], c[1])).collect();
                    if r.len() >= 3 {
                        local.push(r);
                    }
                }
                "text" | "image" | "use" => skipped.push(format!("<{name}> is not imported (convert text to paths first)")),
                _ => {}
            }
        }
        for r in local {
            rings.push(r.into_iter().map(|p| m.apply(p)).collect::<Vec<_>>());
        }
        if !empty {
            stack.push((m, filled));
        }
    }
    if !seen_root {
        return Err("not an SVG document (no <svg> element)".into());
    }
    Ok(Art { rings, mm_per_unit, skipped })
}

/// Group rings into filled outlines with their holes (by containment depth) and fracture
/// every hole into its outline. Returns simple polygons.
pub fn fill_polygons(rings: &[Vec<Pt>]) -> Vec<Vec<Pt>> {
    let n = rings.len();
    let depth: Vec<usize> = (0..n).map(|i| (0..n).filter(|&j| j != i && area(&rings[j]).abs() > area(&rings[i]).abs() && inside(rings[i][0], &rings[j])).count()).collect();
    let mut out = Vec::new();
    for i in 0..n {
        if depth[i] % 2 == 1 {
            continue;
        }
        let mut outer = rings[i].clone();
        if area(&outer) < 0.0 {
            outer.reverse();
        }
        let mut holes: Vec<Vec<Pt>> = (0..n)
            .filter(|&j| depth[j] == depth[i] + 1 && inside(rings[j][0], &rings[i]))
            .map(|j| {
                let mut h = rings[j].clone();
                if area(&h) > 0.0 {
                    h.reverse();
                }
                h
            })
            .collect();
        holes.sort_by(|a, b| {
            let mx = |r: &Vec<Pt>| r.iter().map(|p| p.0).fold(f64::MIN, f64::max);
            mx(b).partial_cmp(&mx(a)).unwrap_or(std::cmp::Ordering::Equal)
        });
        for h in &holes {
            outer = bridge(&outer, h, &holes);
        }
        out.push(outer);
    }
    out
}

fn segs_cross(a: Pt, b: Pt, c: Pt, d: Pt) -> bool {
    let o = |p: Pt, q: Pt, r: Pt| (q.0 - p.0) * (r.1 - p.1) - (q.1 - p.1) * (r.0 - p.0);
    let (d1, d2, d3, d4) = (o(c, d, a), o(c, d, b), o(a, b, c), o(a, b, d));
    ((d1 > 1e-12 && d2 < -1e-12) || (d1 < -1e-12 && d2 > 1e-12)) && ((d3 > 1e-12 && d4 < -1e-12) || (d3 < -1e-12 && d4 > 1e-12))
}

/// Join `hole` into `outer` through the closest mutually visible vertex pair.
fn bridge(outer: &[Pt], hole: &[Pt], all_holes: &[Vec<Pt>]) -> Vec<Pt> {
    let hi = (0..hole.len()).max_by(|&a, &b| hole[a].0.partial_cmp(&hole[b].0).unwrap_or(std::cmp::Ordering::Equal)).unwrap_or(0);
    let m = hole[hi];
    let visible = |p: Pt| -> bool {
        let edges = |r: &[Pt]| (0..r.len()).map(move |i| (r[i], r[(i + 1) % r.len()])).collect::<Vec<_>>();
        edges(outer).iter().chain(all_holes.iter().flat_map(|h| edges(h)).collect::<Vec<_>>().iter()).all(|(a, b)| !segs_cross(m, p, *a, *b))
    };
    let mut order: Vec<usize> = (0..outer.len()).collect();
    order.sort_by(|&a, &b| dist(outer[a], m).partial_cmp(&dist(outer[b], m)).unwrap_or(std::cmp::Ordering::Equal));
    let oi = order.iter().copied().find(|&i| visible(outer[i])).unwrap_or(order[0]);
    let mut r = Vec::with_capacity(outer.len() + hole.len() + 2);
    r.extend_from_slice(&outer[..=oi]);
    for k in 0..=hole.len() {
        r.push(hole[(hi + k) % hole.len()]);
    }
    r.push(outer[oi]);
    r.extend_from_slice(&outer[oi + 1..]);
    r
}

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

    #[test]
    fn a_square_with_a_hole_becomes_one_fractured_polygon_in_mm() {
        let svg = r#"<svg xmlns="http://www.w3.org/2000/svg" width="10mm" height="10mm" viewBox="0 0 100 100">
            <path d="M0 0 H100 V100 H0 Z M25 25 v50 h50 v-50 z" fill-rule="evenodd"/>
            <g transform="translate(200,0)"><circle cx="10" cy="10" r="5"/></g>
            <rect x="0" y="0" width="5" height="5" fill="none"/>
            <text>hi</text></svg>"#;
        let art = parse_svg(svg, 0.05).unwrap();
        assert!((art.mm_per_unit - 0.1).abs() < 1e-12);
        assert_eq!(art.rings.len(), 3);
        assert!(art.skipped.iter().any(|s| s.contains("text")));
        let polys = fill_polygons(&art.rings);
        assert_eq!(polys.len(), 2, "the square (with its hole joined) and the circle");
        let sq = polys.iter().find(|p| p.len() < 20).unwrap();
        assert!((area(sq).abs() - (10000.0 - 2500.0)).abs() < 1e-6, "{}", area(sq));
        let circle = polys.iter().find(|p| p.len() >= 20).unwrap();
        assert!(circle.iter().all(|p| p.0 > 200.0));
    }

    #[test]
    fn curves_and_arcs_flatten_to_their_ends() {
        let r = path_rings("M0 0 C10 0 10 10 0 10 Q-5 5 0 0 Z", 0.01);
        assert_eq!(r.len(), 1);
        let r = path_rings("M0 0 A5 5 0 0 1 10 0 L10 1 L0 1 Z", 0.01);
        let top = r[0].iter().map(|p| p.1).fold(f64::MAX, f64::min);
        assert!((top + 5.0).abs() < 0.05, "a half circle above the chord reaches y=-5, got {top}");
        assert_eq!(parse_transform("rotate(90)").apply((1.0, 0.0)).1.round(), 1.0);
    }
}