AI Flow: Reverse Engineering

//! A pad, its solder and the copper that leaves it are one conductor.
//!
//! The copper reader sees mask-covered copper. A pad is exposed metal under a part's end, with a fillet, a glint and often the part's shadow beside it, none of which
//! is read, so the copper stopped a few pixels short of every pad and a pad joined its own track only when a ring test round it happened to pass: on the USB hub
//! board's top 63 pins joined anything, and of 31 joins labelled by eye from the photo 9 were reproduced (scratch sample of 2026-11-10, 40 pads on an 8 x 5 grid).
//!
//! Here each pad is a seed: the footprint's pad as placed, or, on a face with no parts placed yet, a blob of exposed metal. Every seed grows outward through what
//! the photo cannot show (metal, fillet, glint, shadow, print) and stops at anything it can show to be bare laminate or a gap line. The islands it meets within
//! `REACH_PX` are the pad's copper: they are joined to each other and to the pad, and the pad's own area and the way to each island take the island's label. A pixel
//! belongs to the nearest seed, so a pin never reaches round its neighbour.
use crate::raster::Mask;
use std::collections::{HashMap, VecDeque};

/// How far from a pad's metal its copper may begin, frame pixels at 40 px/mm: 0.3 mm. On the hub board's top (development half of the labelled pads) the copper
/// read for a pad's track began 4 to 11 px from the footprint's pad: the reader's 3 px halo round bright metal, the fillet, and the part's shadow on one side.
pub const REACH_PX: u16 = 12;
/// The way from a pad to its copper is drawn this wide to each side, frame pixels: 3 px across, enough to be one piece with both ends. It crosses pixels the photo
/// does not show, so it is kept thin: drawn 5 px across it cost the CM5 0.003 and 0.007 of its copper score against the photo.
const PATH_HALF: i64 = 1;
/// On a face with no parts placed, a blob of exposed metal larger than this is not one pad: 9 mm2, a 3 mm square lug.
const MAX_BLOB_PX: usize = 14400;

/// When both ends of a part reach one island, the nearer end keeps it if the other is this much further off, frame pixels: 0.15 mm, the least clearance a board
/// house makes, so an island the far end only reaches across unseen pixels of that width is not its copper.
const NEARER_BY: u16 = 6;

/// A pad lies on an island it meets within this many pixels of its own metal: 2, the rim the reader leaves round bright metal less a pixel.
const ON_PX: u16 = 2;

/// A pad as placed, in frame pixels.
#[derive(Clone, Debug)]
pub struct Seed { pub cx: f64, pub cy: f64, pub hw: f64, pub hh: f64, pub rot_deg: f64, pub round: bool, /// the part this pad belongs to, any number that is the same for its pads
    pub part: u32 }

impl Seed {
    fn inside(&self, x: f64, y: f64) -> bool {
        let (dx, dy) = (x - self.cx, y - self.cy); let (c, s) = (self.rot_deg.to_radians().cos(), self.rot_deg.to_radians().sin());
        let (lx, ly) = (dx * c - dy * s, dx * s + dy * c);
        if self.round { (lx / self.hw.max(0.5)).powi(2) + (ly / self.hh.max(0.5)).powi(2) <= 1.0 } else { lx.abs() <= self.hw && ly.abs() <= self.hh }
    }
}

/// Seeds from pads given as (part, centre x, centre y, width, height, rotation in degrees, round), in frame pixels.
pub fn seeds_from<'a>(pads: impl Iterator<Item = (&'a str, f64, f64, f64, f64, f64, bool)>) -> Vec<Seed> {
    let mut ids: HashMap<String, u32> = HashMap::new();
    pads.map(|(part, cx, cy, w, h, rot_deg, round)| { let n = ids.len() as u32; Seed { cx, cy, hw: w / 2.0, hh: h / 2.0, rot_deg, round, part: *ids.entry(part.to_string()).or_insert(n) } }).collect()
}

/// Each pixel's seed, 1-based, 0 for none. Where two pads overlap the first keeps the pixel.
pub fn seed_map(seeds: &[Seed], w: usize, h: usize) -> Vec<u32> {
    let mut m = vec![0u32; w * h];
    for (k, s) in seeds.iter().enumerate() {
        let r = s.hw.hypot(s.hh).ceil() as i64 + 1;
        for y in (s.cy as i64 - r).max(0)..=(s.cy as i64 + r).min(h as i64 - 1) { for x in (s.cx as i64 - r).max(0)..=(s.cx as i64 + r).min(w as i64 - 1) {
            let i = y as usize * w + x as usize; if m[i] == 0 && s.inside(x as f64 + 0.5, y as f64 + 0.5) { m[i] = k as u32 + 1; } } }
    }
    m
}

/// Seeds from the photo alone: each blob of exposed metal no larger than a pad.
pub fn metal_seeds(metal: &Mask) -> Vec<u32> {
    let (lab, cs) = crate::raster::components(metal);
    let ok: Vec<bool> = std::iter::once(false).chain(cs.iter().map(|c| c.area >= 12 && c.area <= MAX_BLOB_PX)).collect();
    lab.iter().map(|l| if ok[*l as usize] { *l } else { 0 }).collect()
}

pub struct Joined { pub pads_joined: usize, pub islands_merged: usize, pub painted: Mask }

/// For each seed (1-based, entry 0 unused) its part and how many pads that part has: (part + 1, pads), (0, 0) for entry 0.
pub fn mates(seeds: &[Seed]) -> Vec<(u32, u32)> {
    let mut n: HashMap<u32, u32> = HashMap::new();
    for s in seeds { *n.entry(s.part).or_default() += 1; }
    std::iter::once((0, 0)).chain(seeds.iter().map(|s| (s.part + 1, n[&s.part]))).collect()
}

/// Join every seed to the islands it reaches. `blocked`: what the photo shows to be no copper (seen laminate, gap lines). `body`: what hides the board (parts, metal).
/// `mate`: from `mates`, or empty when the seeds are blobs of metal and nothing says which belong to one part.
///
/// Two pads of one part that reach the same island are looked at together. On a chip, a track that bends past the next pin lies within reach of both, and joined
/// to both it shorts them (four pins of the hub chip's two USB pairs on the first try): the nearer pad keeps it. The two ends of a two-pad part are never one conductor: the part would be shorted. A strip of board beside a small part's body lies within reach of both its pads,
/// and joined to both it shorted 32 of the hub board's capacitors and resistors on the first try. So an island that both pads of a two-pad part reach from much the same distance joins neither.
/// Without footprints, two blobs with nothing but part between them (a straight line from one to the other that never leaves `body`) are taken for the ends of one part.
pub fn join(labels: &mut [u32], seed: &[u32], blocked: &Mask, body: &Mask, mate: &[(u32, u32)], w: usize, h: usize) -> Joined {
    let n = w * h;
    let mut owner = vec![0u32; n]; let mut depth = vec![u16::MAX; n]; let mut parent = vec![u32::MAX; n];
    let mut q: VecDeque<usize> = VecDeque::new();
    // (seed, island) -> the pixel of the seed's region that touched it, nearest first
    let mut touch: HashMap<(u32, u32), usize> = HashMap::new();
    for i in 0..n { if seed[i] != 0 { owner[i] = seed[i]; depth[i] = 0; q.push_back(i); if labels[i] != 0 { touch.entry((seed[i], labels[i])).or_insert(i); } } }
    while let Some(i) = q.pop_front() {
        let d = depth[i]; let (x, y) = (i % w, i / w);
        // copper already read is where the growth ends; inside the pad itself it goes on, so a pad that lies on its pour is still walked out of
        if labels[i] != 0 && seed[i] == 0 { continue; }
        if d >= REACH_PX { continue; }
        for j in [if x > 0 { i - 1 } else { i }, if x + 1 < w { i + 1 } else { i }, if y > 0 { i - w } else { i }, if y + 1 < h { i + w } else { i }] {
            if j == i || owner[j] != 0 { continue; }
            if blocked.d[j] && labels[j] == 0 { continue; }
            owner[j] = owner[i]; depth[j] = d + 1; parent[j] = i as u32;
            if labels[j] != 0 { touch.entry((owner[i], labels[j])).or_insert(j); }
            q.push_back(j);
        }
    }
    // an island both ends of one part reach joins neither
    { let mut by_island: HashMap<u32, Vec<u32>> = HashMap::new(); for (s, l) in touch.keys() { by_island.entry(*l).or_default().push(*s); }
      let mut cen: HashMap<u32, (f64, f64, f64)> = HashMap::new();
      if mate.is_empty() { for i in 0..n { if seed[i] != 0 { let e = cen.entry(seed[i]).or_insert((0.0, 0.0, 0.0)); e.0 += (i % w) as f64; e.1 += (i / w) as f64; e.2 += 1.0; } } }
      let one_part = |a: u32, b: u32| -> bool {
          if !mate.is_empty() { let (pa, pb) = (mate.get(a as usize).copied().unwrap_or((0, 0)), mate.get(b as usize).copied().unwrap_or((0, 0))); return pa.0 != 0 && pa.0 == pb.0; }
          let (p, q) = (cen[&a], cen[&b]); let (p, q) = ((p.0 / p.2, p.1 / p.2), (q.0 / q.2, q.1 / q.2));
          let len = ((q.0 - p.0).powi(2) + (q.1 - p.1).powi(2)).sqrt(); if len > 200.0 { return false; }
          let steps = len.ceil().max(1.0) as usize;
          (0..=steps).all(|k| { let t = k as f64 / steps as f64; let i = (p.1 + (q.1 - p.1) * t) as usize * w + (p.0 + (q.0 - p.0) * t) as usize; seed[i] != 0 || (body.d[i] && labels[i] == 0) }) };
      // ...unless one end lies on it and the other only comes near: a pad on its pour, with the pour passing the part's other end at a clearance the photo cannot show
      let mut drop: Vec<(u32, u32)> = vec![];
      for (l, ss) in &by_island { for (k, a) in ss.iter().enumerate() { for b in &ss[k + 1..] { if !one_part(*a, *b) { continue; }
          let (da, db) = (depth[touch[&(*a, *l)]], depth[touch[&(*b, *l)]]);
          // a chip may have two pins on one pour, each lying on it: both keep it. Two pins that both only come near one track cannot both be its pin.
          let many = mate.get(*a as usize).map(|m| m.1 > 2).unwrap_or(false);
          if da + NEARER_BY <= db { drop.push((*b, *l)); } else if db + NEARER_BY <= da { drop.push((*a, *l)); } else if !(many && da <= ON_PX && db <= ON_PX) { drop.push((*a, *l)); drop.push((*b, *l)); } } } }
      touch.retain(|k, _| !drop.contains(k)); }
    // islands that share a pad are one conductor
    let max = labels.iter().copied().max().unwrap_or(0) as usize;
    let mut root: Vec<u32> = (0..=max as u32).collect();
    fn find(r: &mut [u32], x: u32) -> u32 { let mut a = x; while r[a as usize] != a { a = r[a as usize]; } let mut c = x; while r[c as usize] != a { let nx = r[c as usize]; r[c as usize] = a; c = nx; } a }
    let mut of_seed: HashMap<u32, Vec<u32>> = HashMap::new();
    let mut keys: Vec<(u32, u32)> = touch.keys().copied().collect(); keys.sort();
    for (s, l) in &keys { of_seed.entry(*s).or_default().push(*l); }
    let mut merged = 0;
    let mut seeds_sorted: Vec<u32> = of_seed.keys().copied().collect(); seeds_sorted.sort();
    // No join may put the two ends of a two-pad part on one island, however many pads lie between: each island carries the pads joined to it, and a join that would
    // bring a pad and its mate together is refused, with the pad that asked for it left off that island.
    let mate_of = |s: u32| -> Option<u32> { let m = mate.get(s as usize)?; if m.1 != 2 { return None; } (1..mate.len() as u32).find(|o| *o != s && mate[*o as usize].0 == m.0) };
    let mates_of: HashMap<u32, u32> = seeds_sorted.iter().filter_map(|s| mate_of(*s).map(|m| (*s, m))).collect();
    let mut on: HashMap<u32, Vec<u32>> = HashMap::new();
    let mut refused: Vec<(u32, u32)> = vec![];
    for s in &seeds_sorted { let ls = of_seed[s].clone(); let mut mine: Option<u32> = None;
        for l in &ls { let b = find(&mut root, *l);
            let clash = |grp: u32, with: &[u32], on: &HashMap<u32, Vec<u32>>| -> bool { let there = on.get(&grp).map(|v| v.as_slice()).unwrap_or(&[]); with.iter().any(|p| mates_of.get(p).is_some_and(|m| there.contains(m))) };
            match mine {
                None => { if clash(b, &[*s], &on) { refused.push((*s, *l)); continue; } on.entry(b).or_default().push(*s); mine = Some(b); }
                Some(a) => { let a = find(&mut root, a); if a == b { continue; }
                    let (va, vb) = (on.get(&a).cloned().unwrap_or_default(), on.get(&b).cloned().unwrap_or_default());
                    if clash(b, &va, &on) || clash(a, &vb, &on) { refused.push((*s, *l)); continue; }
                    let (keep, gone) = (a.min(b), a.max(b)); root[gone as usize] = keep; merged += 1;
                    let mut all = va; all.extend(vb); on.remove(&gone); on.insert(keep, all); mine = Some(keep); } } } }
    touch.retain(|k, _| !refused.contains(k));
    let keys: Vec<(u32, u32)> = keys.into_iter().filter(|k| !refused.contains(k)).collect();
    let mut of_seed: HashMap<u32, Vec<u32>> = HashMap::new(); for (s, l) in &keys { of_seed.entry(*s).or_default().push(*l); }
    let mut seeds_sorted: Vec<u32> = of_seed.keys().copied().collect(); seeds_sorted.sort();
    for l in labels.iter_mut() { if *l != 0 { *l = find(&mut root, *l); } }
    // the pad's own area and the way to each island it met
    let mut painted = Mask::new(w, h);
    let label_of: HashMap<u32, u32> = seeds_sorted.iter().map(|s| (*s, find(&mut root, of_seed[s][0]))).collect();
    for i in 0..n { if seed[i] != 0 { if let Some(l) = label_of.get(&seed[i]) { if labels[i] == 0 { labels[i] = *l; painted.d[i] = true; } } } }
    for (s, l) in &keys { let lab = label_of[s]; let _ = l; let mut i = touch[&(*s, *l)];
        loop { let (x, y) = ((i % w) as i64, (i / w) as i64);
            for dy in -PATH_HALF..=PATH_HALF { for dx in -PATH_HALF..=PATH_HALF { let (u, v) = (x + dx, y + dy); if u < 0 || v < 0 || u >= w as i64 || v >= h as i64 { continue; } let j = v as usize * w + u as usize;
                if labels[j] == 0 && owner[j] == *s && !blocked.d[j] { labels[j] = lab; painted.d[j] = true; } } }
            if parent[i] == u32::MAX { break; } i = parent[i] as usize; } }
    Joined { pads_joined: seeds_sorted.len(), islands_merged: merged, painted }
}

#[cfg(test)]
mod tests {
    use super::*;
    /// A pad at the left, a track that starts 8 px to its right, and a second track that passes 8 px above the pad behind a wall of seen laminate.
    fn face() -> (Vec<u32>, Vec<u32>, Mask, usize, usize) {
        let (w, h) = (120usize, 80usize);
        let mut labels = vec![0u32; w * h]; let mut blocked = Mask::new(w, h);
        for y in 36..44 { for x in 38..110 { labels[y * w + x] = 1; } }
        for y in 14..20 { for x in 5..110 { labels[y * w + x] = 2; } }
        for y in 22..26 { for x in 0..w { blocked.d[y * w + x] = true; } }
        let seed = seed_map(&[Seed { cx: 20.0, cy: 40.0, hw: 10.0, hh: 12.0, rot_deg: 0.0, round: false, part: 0 }], w, h);
        (labels, seed, blocked, w, h)
    }
    #[test]
    fn a_pad_joins_the_track_that_starts_short_of_it_and_not_the_one_behind_laminate() {
        let (mut labels, seed, blocked, w, h) = face();
        let j = join(&mut labels, &seed, &blocked, &Mask::new(w, h), &[], w, h);
        assert_eq!(j.pads_joined, 1);
        assert_eq!(labels[40 * w + 20], 1, "the pad's own area is its track's island");
        assert!((36..44).any(|y| labels[y * w + 34] == 1), "and so is the way between them");
        assert_eq!(labels[16 * w + 20], 2, "the track behind the laminate is untouched");
        assert_eq!(labels[30 * w + 60], 0, "nothing is painted where no pad is");
    }
    #[test]
    fn a_track_further_than_the_reach_is_left_alone_and_two_islands_on_one_pad_become_one() {
        let (w, h) = (160usize, 80usize);
        let mut labels = vec![0u32; w * h]; let blocked = Mask::new(w, h);
        for y in 36..44 { for x in 60..150 { labels[y * w + x] = 1; } }
        let seed = seed_map(&[Seed { cx: 20.0, cy: 40.0, hw: 10.0, hh: 12.0, rot_deg: 0.0, round: false, part: 0 }], w, h);
        let j = join(&mut labels, &seed, &blocked, &Mask::new(w, h), &[], w, h);
        assert_eq!(j.pads_joined, 0, "30 px away is not this pad's copper");
        assert_eq!(labels[40 * w + 20], 0);
        // a track to the right and a pour below, both within reach: one conductor through the pad
        for y in 36..44 { for x in 36..60 { labels[y * w + x] = 1; } }
        for y in 58..78 { for x in 5..60 { labels[y * w + x] = 2; } }
        let j = join(&mut labels, &seed, &blocked, &Mask::new(w, h), &[], w, h);
        assert_eq!((j.pads_joined, j.islands_merged), (1, 1));
        assert_eq!(labels[40 * w + 100], labels[70 * w + 30]);
    }
    #[test]
    fn a_strip_beside_a_two_pad_part_joins_neither_end() {
        // a resistor lying left to right: pads at each end, body between, and a strip of board read as copper along its lower side, within reach of both pads
        let (w, h) = (120usize, 80usize);
        let mut labels = vec![0u32; w * h]; let blocked = Mask::new(w, h); let mut body = Mask::new(w, h);
        for y in 30..50 { for x in 20..100 { body.d[y * w + x] = true; } }
        for y in 54..60 { for x in 24..96 { labels[y * w + x] = 1; } }
        for y in 34..46 { for x in 2..12 { labels[y * w + x] = 2; } }
        let pads = [Seed { cx: 28.0, cy: 40.0, hw: 8.0, hh: 10.0, rot_deg: 0.0, round: false, part: 7 }, Seed { cx: 92.0, cy: 40.0, hw: 8.0, hh: 10.0, rot_deg: 0.0, round: false, part: 7 }];
        let seed = seed_map(&pads, w, h);
        for with_footprints in [true, false] {
            let mut l = labels.clone();
            let j = join(&mut l, &seed, &blocked, &body, &if with_footprints { mates(&pads) } else { vec![] }, w, h);
            assert_eq!(j.pads_joined, 1, "only the left pad joins anything, its own track");
            assert_eq!(l[40 * w + 28], 2); assert_eq!(l[40 * w + 92], 0); assert_eq!(l[56 * w + 60], 1, "the strip is left as it was");
        }
    }
    #[test]
    fn a_track_that_bends_past_the_next_pin_of_a_chip_stays_with_its_own_pin() {
        // three pins of one chip in a row; the middle pin's track leaves upward and bends left over the first pin, 8 px above it
        let (w, h) = (140usize, 90usize);
        let mut labels = vec![0u32; w * h]; let blocked = Mask::new(w, h);
        for y in 20..26 { for x in 20..66 { labels[y * w + x] = 1; } }
        for y in 20..34 { for x in 60..66 { labels[y * w + x] = 1; } }
        let pads: Vec<Seed> = [30.0, 63.0, 96.0].iter().map(|x| Seed { cx: *x, cy: 46.0, hw: 5.0, hh: 12.0, rot_deg: 0.0, round: false, part: 3 }).collect();
        let seed = seed_map(&pads, w, h);
        join(&mut labels, &seed, &blocked, &Mask::new(w, h), &mates(&pads), w, h);
        assert_eq!(labels[46 * w + 63], 1, "the middle pin has its track");
        assert_eq!(labels[46 * w + 30], 0, "the first pin, which the track only passes, does not");
    }
    #[test]
    fn a_third_pad_cannot_join_the_two_ends_of_a_part_either() {
        // a capacitor with its own track at each end, and a chip pin lying between the two tracks, within reach of both
        let (w, h) = (160usize, 80usize);
        let mut labels = vec![0u32; w * h]; let blocked = Mask::new(w, h);
        for y in 37..43 { for x in 5..20 { labels[y * w + x] = 1; } for x in 22..70 { labels[y * w + x] = 1; } }
        for y in 37..43 { for x in 86..150 { labels[y * w + x] = 2; } }
        for y in 10..16 { for x in 5..30 { labels[y * w + x] = 1; } for x in 130..150 { labels[y * w + x] = 2; } }
        let pads = [Seed { cx: 12.0, cy: 13.0, hw: 6.0, hh: 6.0, rot_deg: 0.0, round: false, part: 1 }, Seed { cx: 140.0, cy: 13.0, hw: 6.0, hh: 6.0, rot_deg: 0.0, round: false, part: 1 },
                    Seed { cx: 78.0, cy: 40.0, hw: 4.0, hh: 6.0, rot_deg: 0.0, round: false, part: 2 }];
        // (the capacitor's pads lie on tracks 1 and 2; the chip pin at x 78 is 4 px from the end of each)
        for y in 10..16 { for x in 5..30 { labels[y * w + x] = 1; } }
        let seed = seed_map(&pads, w, h);
        join(&mut labels, &seed, &blocked, &Mask::new(w, h), &mates(&pads), w, h);
        assert_ne!(labels[40 * w + 40], labels[40 * w + 120], "the two tracks stay two islands");
        assert_ne!(labels[40 * w + 78], 0, "the chip pin still joins one of them");
    }
    #[test]
    fn a_pin_does_not_reach_round_its_neighbour() {
        // two pins 8 px apart, a track leaving the right one only, with nothing seen between: the left pin must not take it
        let (w, h) = (120usize, 80usize);
        let mut labels = vec![0u32; w * h]; let blocked = Mask::new(w, h);
        for y in 10..22 { for x in 44..52 { labels[y * w + x] = 1; } }
        let seed = seed_map(&[Seed { cx: 32.0, cy: 40.0, hw: 4.0, hh: 12.0, rot_deg: 0.0, round: false, part: 0 }, Seed { cx: 48.0, cy: 40.0, hw: 4.0, hh: 12.0, rot_deg: 0.0, round: false, part: 0 }], w, h);
        join(&mut labels, &seed, &blocked, &Mask::new(w, h), &[], w, h);
        assert_eq!(labels[40 * w + 48], 1, "the right pin has its track");
        assert_eq!(labels[40 * w + 32], 0, "the left pin has none");
    }
}