Adom Fields

//! Separate pieces of one net's copper (0.10.3, issue 22). Two same-net fills KiCad keeps 0.14 mm apart are two
//! conductors, joined only through other layers; on a 0.2 mm grid both put copper into the cells along the gap, and the
//! solve used to join them, inventing a neck. Here the pieces come from the board's geometry, not from pixels: per net
//! and layer, the fills, tracks, pads and via rings that touch or overlap are united into pieces (exact distance tests,
//! with a bucket grid so a board of thousands of items stays fast). Each solve cell then belongs to the piece with most
//! copper in it, and neighbouring cells conduct only within one piece. A cell where two pieces met is reported, since
//! one of them lost that cell's copper there (finer --pitch resolves both).
use crate::board::Board;
use std::collections::HashMap;

const EPS: f64 = 1e-4; // mm: copper this close is touching

fn seg_dist(p: (f64, f64), a: (f64, f64), b: (f64, f64)) -> f64 {
    let (dx, dy) = (b.0 - a.0, b.1 - a.1); let l2 = dx * dx + dy * dy;
    let t = if l2 == 0.0 { 0.0 } else { (((p.0 - a.0) * dx + (p.1 - a.1) * dy) / l2).clamp(0.0, 1.0) };
    (p.0 - a.0 - t * dx).hypot(p.1 - a.1 - t * dy)
}
fn seg_seg(a: (f64, f64), b: (f64, f64), c: (f64, f64), d: (f64, f64)) -> f64 {
    let cr = |o: (f64, f64), p: (f64, f64), q: (f64, f64)| (p.0 - o.0) * (q.1 - o.1) - (p.1 - o.1) * (q.0 - o.0);
    let (d1, d2, d3, d4) = (cr(c, d, a), cr(c, d, b), cr(a, b, c), cr(a, b, d));
    if d1 * d2 < 0.0 && d3 * d4 < 0.0 { return 0.0; }
    seg_dist(a, c, d).min(seg_dist(b, c, d)).min(seg_dist(c, a, b)).min(seg_dist(d, a, b))
}
fn inside(p: (f64, f64), poly: &[(f64, f64)]) -> bool {
    let mut c = false; let n = poly.len();
    for i in 0..n { let (a, b) = (poly[i], poly[(i + n - 1) % n]); 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; } }
    c
}

/// An item of copper: a polygon, or a stroke (a track; a via ring is a stroke of zero length)
enum Item<'a> { Poly(&'a [(f64, f64)]), Stroke((f64, f64), (f64, f64), f64) }
impl Item<'_> {
    fn bbox(&self) -> [f64; 4] { match self {
        Item::Poly(p) => [p.iter().map(|q| q.0).fold(f64::MAX, f64::min), p.iter().map(|q| q.1).fold(f64::MAX, f64::min), p.iter().map(|q| q.0).fold(f64::MIN, f64::max), p.iter().map(|q| q.1).fold(f64::MIN, f64::max)],
        Item::Stroke(a, b, w) => [a.0.min(b.0) - w / 2.0, a.1.min(b.1) - w / 2.0, a.0.max(b.0) + w / 2.0, a.1.max(b.1) + w / 2.0] } }
}
fn touch(x: &Item, y: &Item) -> bool {
    match (x, y) {
        (Item::Stroke(a, b, w), Item::Stroke(c, d, v)) => seg_seg(*a, *b, *c, *d) <= (w + v) / 2.0 + EPS,
        (Item::Stroke(a, b, w), Item::Poly(p)) | (Item::Poly(p), Item::Stroke(a, b, w)) => { if inside(*a, p) || inside(*b, p) { return true; } let n = p.len(); (0..n).any(|i| seg_seg(*a, *b, p[i], p[(i + 1) % n]) <= w / 2.0 + EPS) }
        (Item::Poly(p), Item::Poly(q)) => { if p.iter().any(|v| inside(*v, q)) || q.iter().any(|v| inside(*v, p)) { return true; } let (n, m) = (p.len(), q.len());
            // edges of q bucketed by x so a long fill outline is not tested edge against edge everywhere
            let qe: Vec<((f64, f64), (f64, f64))> = (0..m).map(|j| (q[j], q[(j + 1) % m])).collect();
            (0..n).any(|i| { let (a, b) = (p[i], p[(i + 1) % n]); let (lo, hi) = (a.0.min(b.0) - EPS, a.0.max(b.0) + EPS); let (ylo, yhi) = (a.1.min(b.1) - EPS, a.1.max(b.1) + EPS);
                qe.iter().any(|(c, d)| c.0.max(d.0) >= lo && c.0.min(d.0) <= hi && c.1.max(d.1) >= ylo && c.1.min(d.1) <= yhi && seg_seg(a, b, *c, *d) <= EPS) }) }
    }
}

fn find(p: &mut Vec<usize>, x: usize) -> usize { let mut r = x; while p[r] != r { r = p[r]; } let mut y = x; while p[y] != r { let n = p[y]; p[y] = r; y = n; } r }

/// The pieces of one net on one layer: (items, piece of each item). Items: fills, pad polygons, tracks, via rings.
fn pieces_of<'a>(b: &'a Board, net: &str, layer: &str) -> (Vec<Item<'a>>, Vec<usize>) {
    let mut items: Vec<Item> = Vec::new();
    for p in b.polys.iter().chain(b.pad_polys.iter()).filter(|p| p.net == net && p.layer == layer && p.pts.len() > 2) { items.push(Item::Poly(&p.pts)); }
    for f in b.fills.iter().filter(|f| f.net == net && f.layer == layer && f.outer.len() > 2) { items.push(Item::Poly(&f.outer)); }
    for t in b.tracks.iter().filter(|t| t.net == net && t.layer == layer) { items.push(Item::Stroke(t.a, t.b, t.w)); }
    let real = b.copper.is_empty() || b.copper.iter().any(|c| c == layer);
    if real { for v in b.vias.iter().filter(|v| v.net == net) { items.push(Item::Stroke((v.x, v.y), (v.x, v.y), v.size)); } }
    let n = items.len(); let mut par: Vec<usize> = (0..n).collect();
    // candidate pairs from a 1 mm bucket grid over the items' boxes
    let bb: Vec<[f64; 4]> = items.iter().map(|i| i.bbox()).collect();
    let mut buckets: HashMap<(i64, i64), Vec<usize>> = HashMap::new();
    for (i, x) in bb.iter().enumerate() { for gx in (x[0] - EPS).floor() as i64..=(x[2] + EPS).floor() as i64 { for gy in (x[1] - EPS).floor() as i64..=(x[3] + EPS).floor() as i64 { buckets.entry((gx, gy)).or_default().push(i); } } }
    let mut tested: std::collections::HashSet<(usize, usize)> = Default::default();
    for v in buckets.values() { for (k, &i) in v.iter().enumerate() { for &j in &v[k + 1..] {
        let (a, z) = (i.min(j), i.max(j)); if find(&mut par, a) == find(&mut par, z) || !tested.insert((a, z)) { continue; }
        if bb[a][0] > bb[z][2] + EPS || bb[z][0] > bb[a][2] + EPS || bb[a][1] > bb[z][3] + EPS || bb[z][1] > bb[a][3] + EPS { continue; }
        if touch(&items[a], &items[z]) { let (ra, rz) = (find(&mut par, a), find(&mut par, z)); par[ra] = rz; }
    } } }
    let piece: Vec<usize> = (0..n).map(|i| find(&mut par, i)).collect();
    (items, piece)
}

/// Per solve cell of one net on one layer: the dominant piece's copper fraction, its piece (u32::MAX: no copper), and the
/// cells where two pieces met. `mask` is the net's fine copper mask (the raster's, so drills and pours are as solved).
pub fn cells(b: &Board, net: &str, layer: &str, mask: &[u8], fw: usize, fh: usize, res: f64, x0: f64, y0: f64, pool: usize) -> (Vec<f32>, Vec<u32>, Vec<(usize, usize)>) {
    let (gw, gh) = (fw / pool, fh / pool);
    let (items, piece) = pieces_of(b, net, layer);
    let distinct: std::collections::BTreeSet<usize> = piece.iter().copied().collect();
    // one piece (the usual case): plain fractions, nothing to keep apart
    if distinct.len() <= 1 {
        let mut f = vec![0f32; gw * gh]; let mut c = vec![u32::MAX; gw * gh];
        for r in 0..gh { for col in 0..gw { let mut s = 0u32; for i in 0..pool { for j in 0..pool { s += mask[(r * pool + i) * fw + col * pool + j] as u32; } } if s > 0 { f[r * gw + col] = s as f32 / (pool * pool) as f32; c[r * gw + col] = 0; } } }
        return (f, c, vec![]);
    }
    // label each copper pixel with the piece of the item covering its centre (the nearest item when none does, e.g. a
    // pour the raster filled itself)
    let mut lab = vec![u32::MAX; fw * fh];
    for (k, it) in items.iter().enumerate() {
        let x = it.bbox(); let (c0, c1) = ((((x[0] - x0) / res).floor().max(0.0)) as usize, (((x[2] - x0) / res).ceil().max(0.0) as usize).min(fw));
        let (r0, r1) = ((((x[1] - y0) / res).floor().max(0.0)) as usize, (((x[3] - y0) / res).ceil().max(0.0) as usize).min(fh));
        for r in r0..r1 { for c in c0..c1 { let i = r * fw + c; if mask[i] == 0 || lab[i] != u32::MAX { continue; }
            let p = (x0 + (c as f64 + 0.5) * res, y0 + (r as f64 + 0.5) * res);
            let hit = match it { Item::Poly(q) => inside(p, q), Item::Stroke(a, z, w) => seg_dist(p, *a, *z) <= w / 2.0 + res * 0.71 };
            if hit { lab[i] = piece[k] as u32; } } }
    }
    // copper no item claims (a raster-filled pour, a rounding edge): take a labelled neighbour's piece, spreading outward
    let mut frontier: Vec<usize> = (0..fw * fh).filter(|i| lab[*i] != u32::MAX).collect();
    while !frontier.is_empty() { let mut next = Vec::new(); for i in frontier { let (r, c) = (i / fw, i % fw); for j in [if r > 0 { Some(i - fw) } else { None }, if r + 1 < fh { Some(i + fw) } else { None }, if c > 0 { Some(i - 1) } else { None }, if c + 1 < fw { Some(i + 1) } else { None }].into_iter().flatten() { if mask[j] != 0 && lab[j] == u32::MAX { lab[j] = lab[i]; next.push(j); } } } frontier = next; }
    let mut f = vec![0f32; gw * gh]; let mut cp = vec![u32::MAX; gw * gh]; let mut met = Vec::new();
    for r in 0..gh { for col in 0..gw {
        let mut count: Vec<(u32, u32)> = Vec::new();
        for i in 0..pool { for j in 0..pool { let l = lab[(r * pool + i) * fw + col * pool + j]; if l == u32::MAX { continue; } match count.iter_mut().find(|x| x.0 == l) { Some(x) => x.1 += 1, None => count.push((l, 1)) } } }
        if let Some(best) = count.iter().max_by_key(|x| (x.1, std::cmp::Reverse(x.0))) { f[r * gw + col] = best.1 as f32 / (pool * pool) as f32; cp[r * gw + col] = best.0; if count.len() > 1 { met.push((r, col)); } }
    } }
    // and where two pieces sit in neighbouring cells: the edge the grid used to bridge
    for r in 0..gh { for col in 0..gw { let i = r * gw + col; if cp[i] == u32::MAX { continue; }
        let right = col + 1 < gw && cp[i + 1] != u32::MAX && cp[i + 1] != cp[i]; let down = r + 1 < gh && cp[i + gw] != u32::MAX && cp[i + gw] != cp[i];
        if (right || down) && !met.contains(&(r, col)) { met.push((r, col)); } } }
    (f, cp, met)
}

#[cfg(test)] mod tests {
    use super::*;
    use crate::board::Poly;
    fn rect(x0: f64, y0: f64, x1: f64, y1: f64) -> Vec<(f64, f64)> { vec![(x0, y0), (x1, y0), (x1, y1), (x0, y1)] }
    #[test] fn two_fills_apart_stay_apart_and_touching_ones_join() {
        let mut b = Board::default();
        b.polys = vec![Poly { net: "V".into(), layer: "F.Cu".into(), pts: rect(0.0, 0.0, 5.0, 2.0) }, Poly { net: "V".into(), layer: "F.Cu".into(), pts: rect(5.14, 0.0, 10.0, 2.0) }];
        let (_, p) = pieces_of(&b, "V", "F.Cu"); assert_ne!(p[0], p[1]);
        b.polys[1].pts = rect(5.0, 0.0, 10.0, 2.0); let (_, p) = pieces_of(&b, "V", "F.Cu"); assert_eq!(p[0], p[1]);
        // a track across the gap joins them
        b.polys[1].pts = rect(5.14, 0.0, 10.0, 2.0); b.tracks.push(crate::board::Track { net: "V".into(), layer: "F.Cu".into(), a: (4.0, 1.0), b: (6.0, 1.0), w: 0.25 });
        let (_, p) = pieces_of(&b, "V", "F.Cu"); assert_eq!(p[0], p[1]);
    }
    #[test] fn cells_keep_the_gap() {
        let mut b = Board::default();
        b.polys = vec![Poly { net: "V".into(), layer: "F.Cu".into(), pts: rect(0.0, 0.0, 1.0, 1.0) }, Poly { net: "V".into(), layer: "F.Cu".into(), pts: rect(1.14, 0.0, 2.2, 1.0) }];
        // a 0.1 mm mask of the two fills with the gap closed (as a coarse raster would see it), pooled by 2 to 0.2 mm cells
        let (fw, fh, res) = (22, 10, 0.1); let mask = vec![1u8; fw * fh];
        let (f, c, met) = cells(&b, "V", "F.Cu", &mask, fw, fh, res, 0.0, 0.0, 2);
        let (gw, _) = (fw / 2, fh / 2);
        assert!(f.iter().all(|x| *x > 0.0));
        assert_ne!(c[0], c[gw - 1]); // the two ends are different pieces
        let changes = (0..gw - 1).filter(|k| c[*k] != c[k + 1]).count(); assert_eq!(changes, 1); // one boundary between them
        assert!(!met.is_empty());
    }
}