AI Flow: Reverse Engineering

//! Chip passives, body first. The body of a small capacitor (tan) or resistor (dark, reddish) is found as one connected blob and
//! fitted with an oriented rectangle. Which way the part lies is read from what lies just beyond the two pairs of opposite sides:
//! a solder end looks paler than this part's own tan body, or brighter than its own dark one. The package comes from the body's
//! own length and width, the place is the body's centre. So two parts side by side stay two parts: nothing is paired across a gap.
//!
//! The colour thresholds are each photo's own (`Levels`). The board surface and the bright level come from `tone`. The photo is then
//! read once strictly at a sweep of saturation floors; the bodies that pass (`calibrate`) give this photo's tan hue, the saturation
//! between its solder ends and its bodies, and how bright its bodies and ends are, and the photo is read again at those. A photo with
//! too few such bodies is read at the CM5's numbers scaled by its own bright level, and its candidates say so.
//! Hue, saturation and value are OpenCV's 8-bit ones (H 0..180, S and V 0..255).
use crate::board::{to_mm, to_px, RES};
use crate::geom::{self, P};
use crate::tone;
use image::RgbImage;
use serde_json::{json, Value};
use std::f64::consts::FRAC_PI_2;

/// (package, length, width, share of the length that shows as body between the ends), mm.
pub const PK: &[(&str, f64, f64, f64)] = &[("0201", 0.60, 0.30, 0.45), ("0402", 1.00, 0.50, 0.50), ("0603", 1.60, 0.80, 0.58), ("0805", 2.00, 1.25, 0.62), ("1206", 3.20, 1.60, 0.70)];
/// KiCad footprint name endings, in the order of `PK`.
const METRIC: [&str; 5] = ["0201_0603Metric", "0402_1005Metric", "0603_1608Metric", "0805_2012Metric", "1206_3216Metric"];
/// Two rectangles are one part when they share more than this much of the smaller one.
pub const OVERLAP: f64 = 0.12;
/// A body this many times a passive's own package area is another part. A part's own solder (both ends and their fillets, which the
/// older detector can read as one pale body) stays under four times its package; a pad, a pin row or a moulding it sits in is well over.
pub const BIG: f64 = 5.0;
/// A moulding fills at least this much of its rectangle. Shadows that run round several parts read as one dark body too, but fill less.
pub const SOLID: f64 = 2.0 / 3.0;

/// HSV of one pixel exactly as OpenCV's 8-bit BGR2HSV gives it: H 0..180, S and V 0..255, fixed point with a 12-bit shift.
pub fn hsv8(r: u8, g: u8, b: u8) -> (u8, u8, u8) {
    let (r, g, b) = (r as i32, g as i32, b as i32);
    let v = r.max(g).max(b); let d = v - r.min(g).min(b);
    if v == 0 { return (0, 0, 0); }
    let s = (d * ((255 << 12) as f64 / v as f64).round_ties_even() as i32 + (1 << 11)) >> 12;
    if d == 0 { return (0, s as u8, v as u8); }
    let h = if v == r { g - b } else if v == g { b - r + 2 * d } else { r - g + 4 * d };
    let h = (h * ((180 << 12) as f64 / (6.0 * d as f64)).round_ties_even() as i32 + (1 << 11)) >> 12;
    ((if h < 0 { h + 180 } else { h }) as u8, s as u8, v as u8)
}

/// The thresholds one photo is read at.
#[derive(Clone, Debug)]
pub struct Levels {
    /// hue of a tan body, lowest and highest
    pub tan_hue: (u8, u8),
    /// a tan body is at least this saturated and this bright; a dark body is darker than `dark_v` and no further round the hue circle than `dark_hue`
    pub tan_s: f64, pub tan_v: f64, pub dark_v: f64, pub dark_hue: u8,
    /// a solder end is brighter than this, and brighter than its own dark body by `dark_dv`
    pub end_v: f64, pub dark_dv: f64,
    /// how many of this photo's own bodies the levels were measured on; 0 when they are the scaled CM5 numbers
    pub bodies: usize,
}

/// The CM5 photos' numbers (everypin pair, 2026-11-08), which every photo was read at before: tan hue 4 to 22 and saturation from 78,
/// dark hue up to 16. Used only when a photo shows too few bodies of its own to measure (`MIN_BODIES`).
const CM5_TAN_HUE: (u8, u8) = (4, 22); const CM5_TAN_S: f64 = 78.0; const CM5_DARK_HUE: u8 = 16;
/// The CM5's value thresholds as shares of that photo's bright level (247 on its bottom face, where 195 of its 224 passives are):
/// a tan body from 140, an end from 120, an end 35 brighter than its dark body.
const BODY_V: f64 = 140.0 / 247.0; const END_V: f64 = 120.0 / 247.0; const DARK_DV: f64 = 35.0 / 247.0;
/// An end of a tan body is this much less saturated than the body itself. Relative to the part; 15 of 255 was read on the CM5 photos.
const END_DS: f64 = 15.0;
/// The saturation floors the calibration pass tries, and its widest tan hue and lowest value (as a share of the bright level): wide
/// enough for the tan of the CM5 (hue 9 to 17), the Driver (12 to 18, value down to 85 of 190) and board 10 (19 to 24).
const SWEEP_S: [f64; 6] = [50.0, 64.0, 78.0, 92.0, 106.0, 120.0]; const SWEEP_HUE: (u8, u8) = (4, 28); const SWEEP_V: f64 = 0.45;
/// Two strict readings whose centres lie within this (0.15 mm, in board-image pixels) are one body read at two floors.
const SAME_BODY: f64 = 0.15 * RES;
/// A photo's own levels need at least this many strictly read bodies.
pub const MIN_BODIES: usize = 5;
/// Where the saturation floor sits between the photo's ends and its bodies (0 at the ends' median, 1 at the lower quartile of the
/// bodies' own lower quartiles), and the value floor as a share of the bodies' median value. Chosen on the CM5, Driver and the
/// left half of board 10 (2026-11-10): 0.85 and 0.77 put the CM5 bottom at 77.8 and 137, next to the 78 and 140 it was read at by hand.
/// Between 0.85 and 1.0 the count of right sizes over those boards does not move (205 to 206 of 347 chips).
const S_BETWEEN: f64 = 0.85; const V_OF_BODY: f64 = 0.77;
/// The tan hue window is the middle nine tenths of the bodies' own hues with this much to spare either side (a body's pixels spread
/// more than the bodies' medians do). A dark body's hue stops at the 95th percentile itself: on the CM5 the shadow round a part
/// begins right above its tan. Both chosen on the same three boards.
const HUE_SPARE: f64 = 6.0;
/// An end is brighter than this share of the photo's median end.
const V_OF_END: f64 = 0.6;

impl Levels {
    /// The CM5's numbers scaled to a photo's bright level.
    pub fn scaled(bright: f64) -> Levels {
        Levels { tan_hue: CM5_TAN_HUE, tan_s: CM5_TAN_S, tan_v: BODY_V * bright, dark_v: BODY_V * bright, dark_hue: CM5_DARK_HUE, end_v: END_V * bright, dark_dv: DARK_DV * bright, bodies: 0 }
    }
    pub fn json(&self) -> Value {
        let r = |v: f64| (v * 10.0).round() / 10.0;
        json!({"tanHue": [self.tan_hue.0, self.tan_hue.1], "tanSaturation": r(self.tan_s), "tanValue": r(self.tan_v), "darkValue": r(self.dark_v), "darkHue": self.dark_hue,
               "endValue": r(self.end_v), "endOverDark": r(self.dark_dv), "bodies": self.bodies,
               "from": if self.bodies > 0 { "this photo's own bodies and ends" } else { "too few bodies to measure: the CM5's numbers scaled by this photo's bright level" }})
    }
}

/// How sure a body must be: an end share on both sides, that much more than across, and a size error under `cost`.
#[derive(Clone, Copy, Debug)]
pub struct Gate { pub ends: f64, pub over: f64, pub cost: f64 }
/// What `find` asks of a body.
pub const READ: Gate = Gate { ends: 0.22, over: 0.12, cost: 0.75 };
/// What the calibration pass asks: only a body with clear ends and a size close to a package teaches the photo's levels.
pub const STRICT: Gate = Gate { ends: 0.5, over: 0.4, cost: 0.4 };

/// The photo as the detector reads it: 8-bit HSV per pixel, whether the pixel is board surface, and the photo's bright level.
pub struct Px { pub w: usize, pub h: usize, pub hsv: Vec<[u8; 3]>, pub board: Vec<bool>, pub bright: f64 }

impl Px {
    /// Board is the photo's own dominant hue (`tone::of`).
    pub fn of(img: &RgbImage) -> Px {
        let hsv: Vec<[u8; 3]> = img.pixels().map(|p| { let (h, s, v) = hsv8(p[0], p[1], p[2]); [h, s, v] }).collect();
        let t = tone::of(&hsv);
        Px { w: img.width() as usize, h: img.height() as usize, hsv, board: t.board, bright: t.bright }
    }
    /// A tan capacitor body.
    fn tan(&self, i: usize, lv: &Levels) -> bool { let [h, s, v] = self.hsv[i]; (lv.tan_hue.0..=lv.tan_hue.1).contains(&h) && s as f64 >= lv.tan_s && v as f64 >= lv.tan_v && !self.board[i] }
    /// A dark body; the shadow round a part is greener than this.
    fn dark(&self, i: usize, lv: &Levels) -> bool { let [h, _, v] = self.hsv[i]; (v as f64) < lv.dark_v && h <= lv.dark_hue && !self.board[i] }
    /// The pixels of a 6 x 5 grid of points: from `f0` to `f1` along (ux, uy) from (cx, cy), `half` to either side across. Points off the photo are left out.
    fn grid(&self, cx: f64, cy: f64, ux: f64, uy: f64, f0: f64, f1: f64, half: f64) -> Vec<usize> {
        let (vx, vy) = (-uy, ux); let mut o = Vec::with_capacity(30);
        for f in lin(f0, f1, 6) { for q in lin(-half, half, 5) {
            let (x, y) = ((cx + f * ux + q * vx).round_ties_even(), (cy + f * uy + q * vy).round_ties_even());
            if x >= 0.0 && y >= 0.0 && (x as usize) < self.w && (y as usize) < self.h { o.push(y as usize * self.w + x as usize); }
        } }
        o
    }
}

/// `n` evenly spaced values from `a` to `b`, both included (the last is `b` itself, as numpy's linspace has it).
fn lin(a: f64, b: f64, n: usize) -> impl Iterator<Item = f64> { let st = (b - a) / (n - 1) as f64; (0..n).map(move |k| if k == n - 1 { b } else { k as f64 * st + a }) }

fn median(mut v: Vec<f64>) -> f64 {
    if v.is_empty() { return 0.0; }
    v.sort_by(|a, b| a.partial_cmp(b).unwrap()); let n = v.len();
    if n % 2 == 1 { v[n / 2] } else { (v[n / 2 - 1] + v[n / 2]) / 2.0 }
}

/// Opening by a 2 x 2 square, which drops single pixels and one-pixel lines. Written as OpenCV runs it with its default anchor, so the
/// result lies one pixel down and to the right of the mask it came from; `Passive::centre` takes that pixel back out.
pub fn open2(m: &[bool], w: usize, h: usize) -> Vec<bool> {
    let at = |v: &[bool], x: i64, y: i64, out: bool| if x < 0 || y < 0 { out } else { v[y as usize * w + x as usize] };
    let pass = |v: &[bool], all: bool| -> Vec<bool> { (0..w * h).map(|i| { let (x, y) = ((i % w) as i64, (i / w) as i64);
        let q = [at(v, x - 1, y - 1, all), at(v, x, y - 1, all), at(v, x - 1, y, all), v[i]];
        if all { q.iter().all(|b| *b) } else { q.iter().any(|b| *b) } }).collect() };
    pass(&pass(m, true), false)
}

/// 4-connected blobs of a mask as lists of pixels, in the order their first pixel is met row by row.
pub fn blobs(m: &[bool], w: usize, h: usize) -> Vec<Vec<(u32, u32)>> {
    let mut seen = vec![false; w * h]; let mut out = vec![]; let mut st = vec![];
    for s in 0..w * h {
        if !m[s] || seen[s] { continue; }
        seen[s] = true; st.push(s); let mut px = vec![];
        while let Some(i) = st.pop() {
            let (x, y) = (i % w, i / w); px.push((x as u32, y as u32));
            let mut go = |j: usize| if m[j] && !seen[j] { seen[j] = true; st.push(j); };
            if x > 0 { go(i - 1); } if x + 1 < w { go(i + 1); } if y > 0 { go(i - w); } if y + 1 < h { go(i + w); }
        }
        out.push(px);
    }
    out
}

/// Minimum-area rectangle round a set of points: (centre, (w, h), angle in degrees), the angle in -90..0 and w the extent along it,
/// as OpenCV's minAreaRect reports. One side lies along an edge of the convex hull; each hull edge is tried with exact unit vectors
/// and no trigonometry, so an upright rectangle comes out with whole and half numbers.
pub fn min_area_rect(pts: &[P]) -> (P, (f64, f64), f64) {
    let hull = geom::hull(pts);
    if hull.len() < 3 {
        // a point or a line: no area, the length along the line
        let (a, b) = (hull.first().copied().unwrap_or((0.0, 0.0)), hull.last().copied().unwrap_or((0.0, 0.0)));
        return (((a.0 + b.0) / 2.0, (a.1 + b.1) / 2.0), (geom::dist(a, b), 0.0), -90.0);
    }
    let mut best: Option<(f64, f64, P, (f64, f64), f64)> = None; // area, turn from upright, centre, size, angle
    for i in 0..hull.len() {
        let (a, b) = (hull[i], hull[(i + 1) % hull.len()]);
        let l = geom::dist(a, b); let (ux, uy) = ((b.0 - a.0) / l, (b.1 - a.1) / l);
        let (mut u0, mut u1, mut v0, mut v1) = (f64::MAX, f64::MIN, f64::MAX, f64::MIN);
        for q in &hull { let (u, v) = (q.0 * ux + q.1 * uy, -q.0 * uy + q.1 * ux); u0 = u0.min(u); u1 = u1.max(u); v0 = v0.min(v); v1 = v1.max(v); }
        let (eu, ev) = (u1 - u0, v1 - v0); let (mu, mv) = ((u0 + u1) / 2.0, (v0 + v1) / 2.0);
        let c = (mu * ux - mv * uy, mu * uy + mv * ux);
        let a180 = uy.atan2(ux).to_degrees().rem_euclid(180.0);
        let (size, ang) = if a180 < 90.0 { ((ev, eu), a180 - 90.0) } else { ((eu, ev), a180 - 180.0) };
        let turn = (90.0 - a180.rem_euclid(90.0)).rem_euclid(90.0);
        // of rectangles of one area OpenCV's rotating calipers keep the last they come to, turning away from upright
        let better = match &best { None => true, Some(k) => { let tol = 1e-9 * k.0.max(1.0); eu * ev < k.0 - tol || (eu * ev <= k.0 + tol && turn > k.1) } };
        if better { best = Some((eu * ev, turn, c, size, ang)); }
    }
    let k = best.unwrap(); (k.2, k.3, k.4)
}

/// The four corners of a rectangle given as (centre, (length, width), degrees).
pub fn corners(c: P, size: (f64, f64), deg: f64) -> [P; 4] {
    let (co, si) = (deg.to_radians().cos(), deg.to_radians().sin()); let (a, b) = (size.0 / 2.0, size.1 / 2.0);
    [(-a, -b), (a, -b), (a, b), (-a, b)].map(|(u, v)| (c.0 + u * co - v * si, c.1 + u * si + v * co))
}

/// Area two convex polygons share: the first is cut by each side of the second in turn.
pub fn shared_area(a: &[P], b: &[P]) -> f64 {
    let turn = |p: &[P]| (0..p.len()).map(|i| { let (q, r) = (p[i], p[(i + 1) % p.len()]); q.0 * r.1 - r.0 * q.1 }).sum::<f64>();
    let sign = if turn(b) >= 0.0 { 1.0 } else { -1.0 };
    let mut poly: Vec<P> = a.to_vec();
    for i in 0..b.len() {
        let (p, q) = (b[i], b[(i + 1) % b.len()]);
        let side = |r: P| sign * ((q.0 - p.0) * (r.1 - p.1) - (q.1 - p.1) * (r.0 - p.0));
        let mut next = vec![];
        for k in 0..poly.len() {
            let (c, d) = (poly[k], poly[(k + 1) % poly.len()]); let (sc, sd) = (side(c), side(d));
            if sc >= 0.0 { next.push(c); }
            if (sc > 0.0 && sd < 0.0) || (sc < 0.0 && sd > 0.0) { let t = sc / (sc - sd); next.push((c.0 + t * (d.0 - c.0), c.1 + t * (d.1 - c.1))); }
        }
        poly = next; if poly.len() < 3 { return 0.0; }
    }
    geom::polygon_area(&poly)
}

/// A body blob: its rectangle in pixels, w along the angle (radians).
#[derive(Clone, Copy, Debug)]
pub struct Body { pub cx: f64, pub cy: f64, pub w: f64, pub h: f64, pub ang: f64 }

/// Blobs of a mask that could be a body: between `amin` and `amax` pixels, at least 3 pixels across, filling `fill` of their rectangle.
pub fn bodies(mask: &[bool], w: usize, h: usize, amin: usize, amax: usize, fill: f64) -> Vec<Body> {
    let mut out = vec![];
    for b in blobs(&open2(mask, w, h), w, h) {
        if b.len() < amin || b.len() > amax { continue; }
        let pts: Vec<P> = b.iter().map(|q| (q.0 as f64, q.1 as f64)).collect();
        let (c, (bw, bh), ang) = min_area_rect(&pts);
        if bw.min(bh) < 3.0 || b.len() as f64 / (bw * bh + 1.0) < fill { continue; }
        out.push(Body { cx: c.0, cy: c.1, w: bw, h: bh, ang: ang.to_radians() });
    }
    out
}

/// One chip passive. `x`, `y` are in the opened mask's pixels (see `open2`); `rot` is the image angle of its length, clockwise on screen.
#[derive(Clone, Debug)]
pub struct Passive { pub kind: &'static str, pub x: f64, pub y: f64, pub rot: f64, pub pk: usize, pub q: f64, pub body_mm: (f64, f64), pub cost: f64,
                     /// the smaller end share along the part, the larger one across it, and the body's (length, width, angle) in pixels and radians
                     pub ends: f64, pub across: f64, pub axis: (f64, f64, f64),
                     /// read at the photo's own levels (false: at the scaled CM5 numbers)
                     pub own_levels: bool }

impl Passive {
    /// The body centre in board-image pixels, a pixel's middle at +0.5: the opening's one pixel taken back out.
    pub fn centre(&self) -> P { (self.x - 0.5, self.y - 0.5) }
    /// The package outline in board-image pixels.
    pub fn outline(&self) -> [P; 4] { corners(self.centre(), (PK[self.pk].1 * RES, PK[self.pk].2 * RES), self.rot) }
    pub fn area_mm2(&self) -> f64 { PK[self.pk].1 * PK[self.pk].2 }
    /// How sure the reading is, 0.45 to 1: how much clearer the ends are along the part than across it, and how close the body is
    /// to its package. A reading at another board's levels counts a fifth less. Not a measured probability: the scale was laid out
    /// on the left half of board 10 so that 0.5 keeps what a person would look at first.
    pub fn confidence(&self) -> f64 {
        let c = 0.45 + 0.35 * ((self.ends - self.across) / 0.6).min(1.0) + 0.2 * (1.0 - self.cost / READ.cost).clamp(0.0, 1.0);
        if self.own_levels { c } else { 0.8 * c }
    }
}

/// A body's read angle within this many degrees of square or diagonal is taken as square or diagonal.
const SQUARE_WITHIN: f64 = 22.5;

/// The body gives the place and the width; the ends only say which way the part lies. An end is judged against this part's own
/// body: less colour than a tan body, brighter than a dark one. Both ends must show along one axis and not along the other, and the
/// body's size must be near a package's; otherwise the body is no part.
pub fn part(b: &Body, px: &Px, kind: &'static str, lv: &Levels, gate: &Gate) -> Option<Passive> {
    let tan = kind == "tan"; let mut ax = vec![];
    for (l, w, ang) in [(b.w, b.h, b.ang), (b.h, b.w, b.ang + FRAC_PI_2)] { // l = body size along the tried axis
        let (ux, uy) = (ang.cos(), ang.sin()); let half = (w * 0.38).max(2.0);
        let own = px.grid(b.cx, b.cy, ux, uy, -l * 0.3, l * 0.3, w * 0.3);
        let bs = median(own.iter().map(|i| px.hsv[*i][1] as f64).collect()); let bv = median(own.iter().map(|i| px.hsv[*i][2] as f64).collect());
        let end = |i: usize| { let [_, s, v] = px.hsv[i]; !px.board[i] && v as f64 > lv.end_v && if tan { (s as f64) < bs - END_DS } else { v as f64 > bv + lv.dark_dv } };
        let e = [1.0, -1.0].map(|s: f64| { let g = px.grid(b.cx, b.cy, s * ux, s * uy, l / 2.0 + 1.5, l / 2.0 + 7.0, half); g.iter().filter(|i| end(**i)).count() as f64 / g.len().max(1) as f64 });
        ax.push((e[0].min(e[1]), e[0].max(e[1]), l, w, ang));
    }
    let i = if ax[0].0 >= ax[1].0 { 0 } else { 1 }; let (me, _, l, w, ang) = ax[i]; let other = ax[1 - i].1;
    if me < gate.ends || me - other < gate.over { return None; }
    let (wid, ln) = (w / RES, l / RES);
    // the body shows a little narrower than the part
    let cost = |q: &(&str, f64, f64, f64)| (wid * 1.15 / q.2).ln().abs() + (ln / (q.3 * q.1)).ln().abs();
    let pk = (0..PK.len()).fold(0, |a, k| if cost(&PK[k]) < cost(&PK[a]) { k } else { a });
    if cost(&PK[pk]) > gate.cost { return None; }
    // a body a few pixels across gives a rough angle: parts sit square or on the diagonal, so the angle goes to the nearest 45
    let mut rot = ang.to_degrees().rem_euclid(180.0); let near = (rot / 45.0).round() * 45.0;
    if (rot - near).abs() <= SQUARE_WITHIN { rot = near.rem_euclid(180.0); }
    Some(Passive { kind, x: b.cx, y: b.cy, rot, pk, q: me - other + if tan { 0.5 } else { 0.0 }, body_mm: (ln, wid), cost: cost(&PK[pk]), ends: me, across: other, axis: (l, w, ang), own_levels: lv.bodies > 0 })
}

/// The value at quantile `q` of a list, between neighbours as numpy's percentile has it.
fn quantile(mut v: Vec<f64>, q: f64) -> f64 {
    if v.is_empty() { return 0.0; }
    v.sort_by(|a, b| a.partial_cmp(b).unwrap()); let at = q * (v.len() - 1) as f64; let (lo, hi) = (at.floor() as usize, at.ceil() as usize);
    v[lo] + (v[hi] - v[lo]) * (at - lo as f64)
}

/// This photo's own levels. Tan bodies are read strictly (`STRICT`) at each saturation floor of the sweep; each one that passes gives
/// the hue, saturation and value of its body and of the solder beyond its two ends. With `MIN_BODIES` or more: the hue window is
/// theirs with `HUE_SPARE` to spare, the saturation floor lies between the ends and the bodies, a body is at least `V_OF_BODY` of the
/// median body's value and an end `V_OF_END` of the median end's. A dark body is then whatever is darker than a tan one, at a hue
/// no further round than the bodies' own. With fewer, the scaled CM5 numbers.
pub fn calibrate(px: &Px) -> Levels {
    let base = Levels::scaled(px.bright);
    let (mut hue, mut sat25, mut val, mut end_s, mut end_v) = (vec![], vec![], vec![], vec![], vec![]);
    let mut seen: Vec<P> = vec![];
    for s in SWEEP_S {
        let lv = Levels { tan_hue: SWEEP_HUE, tan_s: s, tan_v: SWEEP_V * px.bright, ..base.clone() };
        let mask: Vec<bool> = (0..px.w * px.h).map(|i| px.tan(i, &lv)).collect();
        for b in bodies(&mask, px.w, px.h, 14, 9000, 0.55) {
            let Some(p) = part(&b, px, "tan", &lv, &STRICT) else { continue };
            // one sample a body: the same body passes at several floors, and is counted where it first does
            if seen.iter().any(|c: &P| geom::dist(*c, (b.cx, b.cy)) < SAME_BODY) { continue; }
            seen.push((b.cx, b.cy));
            let (l, w, ang) = p.axis; let (ux, uy) = (ang.cos(), ang.sin());
            let own = px.grid(b.cx, b.cy, ux, uy, -l * 0.3, l * 0.3, w * 0.3);
            let ends: Vec<usize> = [1.0, -1.0].iter().flat_map(|s: &f64| px.grid(b.cx, b.cy, s * ux, s * uy, l / 2.0 + 1.5, l / 2.0 + 7.0, (w * 0.38).max(2.0))).filter(|i| !px.board[*i]).collect();
            if own.is_empty() || ends.is_empty() { continue; }
            let ch = |v: &[usize], k: usize| -> Vec<f64> { v.iter().map(|i| px.hsv[*i][k] as f64).collect() };
            hue.push(median(ch(&own, 0))); sat25.push(quantile(ch(&own, 1), 0.25)); val.push(median(ch(&own, 2)));
            end_s.push(median(ch(&ends, 1))); end_v.push(median(ch(&ends, 2)));
        }
    }
    if hue.len() < MIN_BODIES { return base; }
    let (es, bs) = (median(end_s), quantile(sat25, 0.25));
    let tan_v = V_OF_BODY * median(val); let (h5, h95) = (quantile(hue.clone(), 0.05), quantile(hue.clone(), 0.95));
    Levels { tan_hue: ((h5 - HUE_SPARE).max(0.0) as u8, (h95 + HUE_SPARE).min(179.0) as u8), tan_s: (es + S_BETWEEN * (bs - es)).max(es + 10.0), tan_v, dark_v: tan_v,
             dark_hue: h95 as u8, end_v: V_OF_END * median(end_v), dark_dv: base.dark_dv, bodies: hue.len() }
}

/// Where a chip passive cannot be: a bigger part or a plated hole's pad, in board-image pixels. `area_mm2` is that part's own size.
#[derive(Clone, Debug)]
pub struct Zone { pub c: P, pub half: (f64, f64), pub deg: f64, pub round: bool, pub area_mm2: f64, pub what: String }

impl Zone {
    pub fn holds(&self, p: P) -> bool {
        let (co, si) = (self.deg.to_radians().cos(), self.deg.to_radians().sin()); let (dx, dy) = (p.0 - self.c.0, p.1 - self.c.1);
        let (u, v) = (dx * co + dy * si, -dx * si + dy * co);
        if self.round { (u / self.half.0).powi(2) + (v / self.half.1).powi(2) <= 1.0 } else { u.abs() <= self.half.0 && v.abs() <= self.half.1 }
    }
    /// Whether this zone keeps a passive out: its centre lies in the zone and the zone is `BIG` times its package.
    pub fn takes(&self, p: &Passive) -> bool { self.area_mm2 >= BIG * p.area_mm2() && self.holds(p.centre()) }
}

/// Zones from what the flow has already measured on one face, in place of a hand-made list:
/// - every body of `prep::bodies` that is not ceramic, by its own rectangle without the solder it touches (that solder is often a
///   neighbour's end): dark moulding and coloured plastic when `SOLID`, and pale bodies, which are bare pads, pin rows, solder domes and cans;
/// - every plated hole's pad, round unless the hole list says square (`holes`, this face's detect/holes-*.json, board mm): parts do stand
///   in the corners of the square round a large ring, so a square pad that is not flagged square keeps its corners open;
/// - every row of holes at a connector pitch, half a pitch to either side: a header or terminal block stands on it. `rows` index
///   `row_holes`, the top face's holes, because rows are read on the top only and a hole is in one place on both faces.
/// A tan body makes no zone: a tan blob that large is several capacitors side by side, which are the parts looked for.
pub fn zones(bodies: &[Value], holes: &[Value], rows: &[Value], row_holes: &[Value]) -> Vec<Zone> {
    let f = |v: &Value, k: &str| v[k].as_f64().unwrap_or(0.0); let mut z = vec![];
    for b in bodies {
        let (colour, c) = (b["colour"].as_str().unwrap_or(""), &b["body"]); let (l, w) = (f(c, "long"), f(c, "short"));
        if colour == "tan" || l * w <= 0.0 || (colour != "white" && f(b, "area") / (l * w) < SOLID) { continue; }
        z.push(Zone { c: (f(c, "x"), f(c, "y")), half: (l / 2.0, w / 2.0), deg: f(c, "angle"), round: false, area_mm2: l * w / (RES * RES), what: format!("{colour} body") });
    }
    for h in holes { let r = f(h, "outer_mm").max(f(h, "hole_mm")) / 2.0;
        let sq = h["square"] == json!(true);
        z.push(Zone { c: to_px(f(h, "x"), f(h, "y")), half: (r * RES, r * RES), deg: 0.0, round: !sq, area_mm2: if sq { 4.0 } else { std::f64::consts::PI } * r * r, what: "hole pad".into() }); }
    for r in rows {
        let ids: Vec<usize> = r["holes"].as_array().into_iter().flatten().filter_map(|x| x.as_u64().map(|x| x as usize)).filter(|i| *i < row_holes.len()).collect();
        let pitch = f(r, "pitch_mm");
        if ids.len() < 2 || !crate::board::PITCHES.iter().any(|p| ((pitch - p) / p).abs() < 0.03) { continue; }
        let (a, b) = (&row_holes[ids[0]], &row_holes[ids[ids.len() - 1]]);
        let (p, q) = (to_px(f(a, "x"), f(a, "y")), to_px(f(b, "x"), f(b, "y")));
        z.push(Zone { c: ((p.0 + q.0) / 2.0, (p.1 + q.1) / 2.0), half: (geom::dist(p, q) / 2.0 + pitch * RES / 2.0, pitch * RES / 2.0), deg: (q.1 - p.1).atan2(q.0 - p.0).to_degrees(), round: false, area_mm2: f64::MAX, what: "hole row".into() });
    }
    z
}

/// Every body that passes `part` on one board image at the given levels, before any is dropped.
pub fn found(px: &Px, lv: &Levels) -> Vec<Passive> {
    let mut cand = vec![];
    for (kind, amin, amax, fill) in [("tan", 14, 9000, 0.55), ("dark", 30, 12000, 0.68)] {
        let mask: Vec<bool> = (0..px.w * px.h).map(|i| if kind == "tan" { px.tan(i, lv) } else { px.dark(i, lv) }).collect();
        cand.extend(bodies(&mask, px.w, px.h, amin, amax, fill).iter().filter_map(|b| part(b, px, kind, lv, &READ)));
    }
    cand
}

/// Chip passives on one board image, best first. A candidate a zone takes is left out, and of two that overlap the better one stays.
/// Returns the passives and, for the record, what the zones took: (passive, zone).
pub fn find(img: &RgbImage, zones: &[Zone]) -> (Vec<Passive>, Vec<(Passive, String)>) { let (k, t, _) = find_with(img, zones); (k, t) }

/// As `find`, and the levels the photo was read at.
pub fn find_with(img: &RgbImage, zones: &[Zone]) -> (Vec<Passive>, Vec<(Passive, String)>, Levels) {
    let px = Px::of(img); let lv = calibrate(&px);
    let mut cand = found(&px, &lv);
    cand.sort_by(|a, b| b.q.partial_cmp(&a.q).unwrap());
    // a second reading at the scaled CM5 numbers, behind the first: it only adds where the photo's own levels found nothing, and
    // what it adds says so (`own_levels` false, a fifth less sure)
    if lv.bodies > 0 { let mut more = found(&px, &Levels::scaled(px.bright)); more.sort_by(|a, b| b.q.partial_cmp(&a.q).unwrap()); cand.extend(more); }
    let (mut kept, mut boxes, mut taken): (Vec<Passive>, Vec<[P; 4]>, Vec<(Passive, String)>) = (vec![], vec![], vec![]);
    for p in cand {
        if let Some(z) = zones.iter().find(|z| z.takes(&p)) { taken.push((p, z.what.clone())); continue; }
        let r = p.outline();
        if kept.iter().zip(&boxes).any(|(k, kr)| shared_area(&r, kr) > OVERLAP * p.area_mm2().min(k.area_mm2()) * RES * RES) { continue; }
        kept.push(p); boxes.push(r);
    }
    (kept, taken, lv)
}

/// Whether a candidate of the older detector (`parts::candidates`) describes the spot of one of these passives: its rectangle shares more
/// than `OVERLAP` of the smaller of the two, and it is not a part `BIG` times the passive's size that merely stands next to it.
pub fn same_spot(c: &Value, side: &str, found: &[Passive]) -> bool {
    if c["side"] != json!(side) { return false; }
    let g = |k: &str, i: usize| c[k][i].as_f64(); let (Some(x), Some(y), Some(l), Some(w)) = (g("pos_mm", 0), g("pos_mm", 1), g("size_mm", 0), g("size_mm", 1)) else { return false };
    // the candidate's rot is KiCad's, counter-clockwise; the image angle runs the other way
    let r = corners(to_px(x, y), (l * RES, w * RES), -c["rot"].as_f64().unwrap_or(0.0));
    found.iter().any(|p| l * w < BIG * p.area_mm2() && shared_area(&r, &p.outline()) > OVERLAP * (l * w).min(p.area_mm2()) * RES * RES)
}

/// Passives as candidates for detect/parts.json, shaped like `parts::candidates` rows: `size_mm` is the package, `body_mm` the measured body.
pub fn candidates(found: &[Passive], side: &str, start: usize) -> Vec<Value> {
    let r3 = |v: f64| (v * 1000.0).round() / 1000.0; let r2 = |v: f64| (v * 100.0).round() / 100.0;
    found.iter().enumerate().map(|(k, p)| {
        let (name, l, w, _) = PK[p.pk]; let c = p.centre(); let pos = to_mm(c.0, c.1);
        let fp = format!("{}_{}", if p.kind == "tan" { "Capacitor_SMD:C" } else { "Resistor_SMD:R" }, METRIC[p.pk]);
        // KiCad rotation is counter-clockwise on screen; the image angle runs clockwise
        let rot = (-p.rot).rem_euclid(180.0) + 0.0;
        json!({"id": format!("P{:03}", start + k + 1), "side": side, "pos_mm": [r3(pos.0), r3(pos.1)], "rot": (rot * 10.0).round() / 10.0,
               "size_mm": [l, w], "body_mm": [r2(p.body_mm.0), r2(p.body_mm.1)], "colour": p.kind, "kind": p.kind, "fits": true,
               "prefix": if p.kind == "tan" { "C" } else { "R" }, "package": name, "footprint": fp,
               "matches": [{"package": name, "footprint": fp, "error": r3(p.cost)}], "score": r2(p.q), "method": "body", "source": "body-first",
               "confidence": r2(p.confidence()), "levels": if p.own_levels { "own" } else { "scaled" }})
    }).collect()
}

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

    const MASK: Rgb<u8> = Rgb([50, 186, 140]); const SOLDER: Rgb<u8> = Rgb([200, 200, 200]);
    const TAN: Rgb<u8> = Rgb([190, 140, 100]); const DARK: Rgb<u8> = Rgb([60, 40, 35]);

    fn fill(img: &mut RgbImage, x: std::ops::Range<u32>, y: std::ops::Range<u32>, c: Rgb<u8>) { for v in y { for u in x.clone() { img.put_pixel(u, v, c); } } }
    /// A chip part lying along x: a solder end, the body, a solder end.
    fn chip(img: &mut RgbImage, x0: u32, y0: u32, end: u32, body: u32, wid: u32, c: Rgb<u8>) {
        fill(img, x0..x0 + end, y0..y0 + wid, SOLDER); fill(img, x0 + end..x0 + end + body, y0..y0 + wid, c); fill(img, x0 + end + body..x0 + 2 * end + body, y0..y0 + wid, SOLDER);
    }

    #[test]
    fn hsv_is_opencvs() {
        // (r, g, b) and what cv2.cvtColor(..., COLOR_BGR2HSV) gives for it (OpenCV 5.0.0)
        for ((r, g, b), want) in [((255, 0, 0), (0, 255, 255)), ((0, 255, 0), (60, 255, 255)), ((0, 0, 255), (120, 255, 255)), ((200, 100, 50), (10, 191, 200)), ((50, 186, 140), (80, 186, 186)),
                                  ((110, 60, 30), (11, 185, 110)), ((200, 200, 200), (0, 0, 200)), ((99, 43, 17), (10, 211, 99)), ((160, 120, 90), (13, 112, 160)), ((253, 254, 255), (105, 2, 255)),
                                  ((3, 2, 1), (15, 170, 3)), ((78, 77, 77), (0, 3, 78)), ((10, 200, 10), (60, 242, 200)), ((128, 10, 250), (135, 245, 250)), ((0, 0, 0), (0, 0, 0))] {
            assert_eq!(hsv8(r, g, b), want, "rgb {r} {g} {b}");
        }
    }

    #[test]
    fn rectangle_round_a_turned_body() {
        // every whole point inside a 40 x 16 rectangle turned 30 degrees about (100, 80)
        let (c, s) = (30f64.to_radians().cos(), 30f64.to_radians().sin()); let mut pts = vec![];
        for y in 40..120 { for x in 60..140 { let (dx, dy) = (x as f64 - 100.0, y as f64 - 80.0); let (u, v) = (dx * c + dy * s, -dx * s + dy * c);
            if u.abs() <= 20.0 && v.abs() <= 8.0 { pts.push((x as f64, y as f64)); } } }
        let (ctr, (w, h), ang) = min_area_rect(&pts);
        assert!(geom::dist(ctr, (100.0, 80.0)) < 0.6, "{ctr:?}");
        assert!((w - 16.0).abs() < 1.3 && (h - 40.0).abs() < 1.3, "{w} x {h}");
        assert!((ang + 60.0).abs() < 2.5, "{ang}"); // w lies along the angle: the short side at -60, the long one at 30
        // an upright block of pixels comes out exact, as OpenCV has it: ((4.5, 2), (4, 9), -90)
        let up: Vec<P> = (0..5).flat_map(|y| (0..10).map(move |x| (x as f64, y as f64))).collect();
        assert_eq!(min_area_rect(&up), ((4.5, 2.0), (4.0, 9.0), -90.0));
    }

    #[test]
    fn opening_and_blobs() {
        // a 2 x 2 block stays (one pixel down and right, OpenCV's default anchor), a single pixel and a one-pixel line go
        let (w, h) = (8, 8); let mut m = vec![false; w * h];
        for (x, y) in [(2, 2), (3, 2), (2, 3), (3, 3), (5, 5), (6, 2), (6, 3), (6, 4)] { m[y * w + x] = true; }
        let o = open2(&m, w, h);
        let on: Vec<(usize, usize)> = (0..w * h).filter(|i| o[*i]).map(|i| (i % w, i / w)).collect();
        assert_eq!(on, vec![(3, 3), (4, 3), (3, 4), (4, 4)]);
        // blobs join along sides only: two blocks that touch at a corner are two
        let mut m = vec![false; w * h];
        for (x, y) in [(0, 0), (1, 0), (0, 1), (1, 1), (2, 2), (3, 2), (2, 3), (3, 3)] { m[y * w + x] = true; }
        let b = blobs(&m, w, h);
        assert_eq!((b.len(), b[0].len(), b[1].len()), (2, 4, 4));
    }

    #[test]
    fn shared_area_of_rectangles() {
        let a = corners((10.0, 10.0), (8.0, 4.0), 0.0);
        assert!((shared_area(&a, &a) - 32.0).abs() < 1e-9);
        assert!((shared_area(&a, &corners((14.0, 10.0), (8.0, 4.0), 0.0)) - 16.0).abs() < 1e-9);
        assert!((shared_area(&a, &corners((10.0, 10.0), (2.0, 2.0), 10.0)) - 4.0).abs() < 1e-9);
        assert!((shared_area(&a, &corners((10.0, 10.0), (4.0, 8.0), 90.0)) - 32.0).abs() < 1e-9);
        assert_eq!(shared_area(&a, &corners((30.0, 10.0), (8.0, 4.0), 45.0)), 0.0);
    }

    #[test]
    fn two_parts_in_a_row_are_two_parts() {
        // two 0402 capacitors end to end along x, 0.2 mm apart, and an upright 0603 resistor: 40 px per mm
        let mut img = RgbImage::from_pixel(400, 300, MASK);
        chip(&mut img, 100, 100, 10, 20, 20, TAN); chip(&mut img, 148, 100, 10, 20, 20, TAN);
        fill(&mut img, 300..332, 100..112, SOLDER); fill(&mut img, 300..332, 112..152, DARK); fill(&mut img, 300..332, 152..164, SOLDER);
        let (found, taken) = find(&img, &[]);
        assert!(taken.is_empty());
        let got: Vec<(&str, &str, P, f64)> = found.iter().map(|p| (p.kind, PK[p.pk].0, p.centre(), p.rot)).collect();
        assert_eq!(found.len(), 3, "{got:?}");
        // each capacitor on its own body, none across the gap at x = 144 where two solder ends face each other
        for want in [(120.0, 110.0), (168.0, 110.0)] { assert!(got.iter().any(|g| g.0 == "tan" && g.1 == "0402" && geom::dist(g.2, want) < 0.01 && g.3 == 0.0), "{want:?} in {got:?}"); }
        assert!(got.iter().all(|g| (g.2 .0 - 144.0).abs() > 10.0), "{got:?}");
        assert!(got.iter().any(|g| g.0 == "dark" && g.1 == "0603" && geom::dist(g.2, (316.0, 132.0)) < 0.01 && g.3 == 90.0), "{got:?}");
        // as candidates: board mm, the package's size, and the fields the flow reads
        let c = candidates(&found, "top", 7);
        let a = c.iter().find(|c| c["pos_mm"] == json!([103.0, 102.75])).expect("the first capacitor at its body centre");
        assert_eq!((a["package"].as_str(), a["kind"].as_str(), a["method"].as_str(), a["side"].as_str(), a["prefix"].as_str()), (Some("0402"), Some("tan"), Some("body"), Some("top"), Some("C")));
        assert_eq!((a["size_mm"].clone(), a["rot"].as_f64(), a["fits"].clone(), a["footprint"].as_str()), (json!([1.0, 0.5]), Some(0.0), json!(true), Some("Capacitor_SMD:C_0402_1005Metric")));
        assert!(a["score"].as_f64().unwrap() > 1.0 && a["body_mm"][0].as_f64().unwrap() < 0.5);
        assert_eq!(c.iter().map(|c| c["id"].as_str().unwrap()).collect::<Vec<_>>(), ["P008", "P009", "P010"]);
        // the older detector's pairing of the two facing ends is on the same spot and loses; a big part beside them is not
        let old = |x: f64, y: f64, l: f64, w: f64| json!({"side": "top", "pos_mm": [x, y], "size_mm": [l, w], "rot": 0.0});
        assert!(same_spot(&old(103.6, 102.75, 0.7, 0.5), "top", &found));
        assert!(!same_spot(&old(103.6, 102.75, 0.7, 0.5), "bottom", &found));
        assert!(!same_spot(&old(104.0, 103.9, 5.0, 3.0), "top", &found));
    }

    #[test]
    fn a_dark_photo_is_read_at_its_own_levels() {
        // the same parts on a photo a third as bright, with a browner tan: under the CM5's numbers nothing here is tan or an end
        let (mask, solder, tan) = (Rgb([14, 60, 44]), Rgb([118, 118, 118]), Rgb([104, 62, 30]));
        let mut img = RgbImage::from_pixel(600, 300, mask);
        // white print sets the bright level well above the solder, as on the Driver photo
        fill(&mut img, 20..60, 250..280, Rgb([230, 230, 230]));
        for k in 0..8u32 { let x0 = 30 + 70 * k; fill(&mut img, x0..x0 + 10, 100..120, solder); fill(&mut img, x0 + 10..x0 + 30, 100..120, tan); fill(&mut img, x0 + 30..x0 + 40, 100..120, solder); }
        let px = Px::of(&img);
        assert!(found(&px, &Levels::scaled(px.bright)).is_empty(), "the scaled CM5 numbers find nothing on this photo");
        let lv = calibrate(&px);
        assert_eq!(lv.bodies, 8, "{lv:?}");
        let (h, s, v) = hsv8(104, 62, 30);
        assert!(lv.tan_hue.0 <= h && h <= lv.tan_hue.1 && lv.tan_s < s as f64 && lv.tan_v < v as f64 && lv.end_v < 118.0, "{lv:?}");
        let (got, _, used) = find_with(&img, &[]);
        assert_eq!((got.len(), used.bodies), (8, 8));
        assert!(got.iter().all(|p| p.kind == "tan" && PK[p.pk].0 == "0402" && p.own_levels && p.confidence() > 0.9), "{got:?}");
        // fewer bodies than MIN_BODIES: the scaled numbers, and candidates that say so
        let mut few = RgbImage::from_pixel(400, 300, MASK);
        chip(&mut few, 100, 100, 10, 20, 20, TAN); chip(&mut few, 250, 100, 10, 20, 20, TAN);
        let (got, _, used) = find_with(&few, &[]);
        assert_eq!((got.len(), used.bodies), (2, 0));
        assert!(got.iter().all(|p| !p.own_levels && p.confidence() < 0.81));
        assert_eq!(candidates(&got, "top", 0)[0]["levels"], json!("scaled"));
    }

    #[test]
    fn a_passive_inside_a_bigger_part_is_left_out() {
        let mut img = RgbImage::from_pixel(400, 300, MASK);
        chip(&mut img, 100, 100, 10, 20, 20, TAN); chip(&mut img, 250, 100, 10, 20, 20, TAN);
        let body = |colour: &str, x: f64, y: f64, l: f64, w: f64, area: f64| json!({"x": x, "y": y, "long": l + 12.0, "short": w + 12.0, "angle": 0.0, "colour": colour, "area": area,
                                                                                 "body": {"x": x, "y": y, "long": l, "short": w, "angle": 0.0}});
        // a pale body 3 x 2 mm over the first capacitor (a pin row, a bare pad): the capacitor is its marking, not a part
        let z = zones(&[body("white", 120.0, 110.0, 120.0, 80.0, 9000.0)], &[], &[], &[]);
        let (found, taken) = find(&img, &z);
        assert_eq!((found.len(), taken.len(), taken[0].1.as_str()), (1, 1, "white body"));
        assert!(geom::dist(found[0].centre(), (270.0, 110.0)) < 0.01);
        // not a zone: the part's own solder read as a pale body (under 5 packages), a tan blob, shadows that fill half their rectangle,
        // a moulding that only touches the part with its solder, and a hole row at no connector pitch
        let holes = [json!({"x": 100.0, "y": 100.0, "outer_mm": 2.0, "hole_mm": 1.0, "square": false}), json!({"x": 116.0, "y": 100.0, "outer_mm": 2.0, "hole_mm": 1.0, "square": false})];
        let z = zones(&[body("white", 120.0, 110.0, 52.0, 30.0, 1500.0), body("tan", 120.0, 110.0, 120.0, 80.0, 9000.0), body("black", 120.0, 110.0, 120.0, 80.0, 4800.0), body("black", 180.0, 110.0, 76.0, 80.0, 6000.0)],
                      &[], &[json!({"holes": [0, 1], "pitch_mm": 16.0})], &holes);
        assert_eq!(find(&img, &z).0.len(), 2);
        // a zone: a solid moulding over it, a hole's pad round it, a header row through it
        assert_eq!(find(&img, &zones(&[body("black", 120.0, 110.0, 120.0, 80.0, 9000.0)], &[], &[], &[])).0.len(), 1);
        let pad = [json!({"x": 103.0, "y": 102.75, "outer_mm": 2.0, "hole_mm": 1.0, "square": false}), json!({"x": 105.54, "y": 102.75, "outer_mm": 2.0, "hole_mm": 1.0, "square": false})];
        assert_eq!(find(&img, &zones(&[], &pad[..1], &[], &[])).1[0].1, "hole pad");
        assert_eq!(find(&img, &zones(&[], &[], &[json!({"holes": [0, 1], "pitch_mm": 2.54})], &pad)).1[0].1, "hole row");
    }
}