AI Flow

//! Plane geometry shared by every stage: KiCad's rotation convention, pad shapes, arcs, outlines.

pub type Pt = (f64, f64);

/// KiCad's board rotation of a local offset (y down, positive angle = counter-clockwise on screen).
pub fn rot_kicad(px: f64, py: f64, deg: f64) -> Pt {
    let a = deg.to_radians();
    let (s, c) = a.sin_cos();
    (px * c + py * s, -px * s + py * c)
}

/// A circle as a polygon that CONTAINS the true circle: the vertices sit on a radius of
/// r / cos(pi / n), so every chord is tangent to the real arc. A polygon inscribed in the arc is
/// smaller than the copper by r (1 - cos(pi / n)), and KiCad's DRC measures the copper: with
/// 10 segments per semicircle that is 0.0012 mm on a 0.3 mm oval pad, and a 0.1989 mm clearance
/// against a 0.2 mm rule.
pub fn circle_poly(cx: f64, cy: f64, r: f64, n: usize) -> Vec<Pt> {
    let rr = r / (std::f64::consts::PI / n as f64).cos();
    (0..n).map(|k| {
        let t = 2.0 * std::f64::consts::PI * (k as f64 + 0.5) / n as f64;
        (cx + rr * t.cos(), cy + rr * t.sin())
    }).collect()
}

/// Oval pad of size sx by sy centred at the origin.
pub fn stadium_poly(sx: f64, sy: f64, n: usize) -> Vec<Pt> {
    if sx >= sy {
        let r = sy / 2.0;
        let d = (sx - sy) / 2.0;
        // circumscribed arcs (see circle_poly): the polygon contains the real copper
        let rr = r / (std::f64::consts::PI / (2 * n) as f64).cos();
        let mut pts = Vec::with_capacity(2 * n + 2);
        for k in 0..n {
            let a = -std::f64::consts::FRAC_PI_2 + std::f64::consts::PI * (k as f64 + 0.5) / n as f64;
            pts.push((d + rr * a.cos(), rr * a.sin()));
        }
        for k in 0..n {
            let a = std::f64::consts::FRAC_PI_2 + std::f64::consts::PI * (k as f64 + 0.5) / n as f64;
            pts.push((-d + rr * a.cos(), rr * a.sin()));
        }
        pts
    } else {
        stadium_poly(sy, sx, n).into_iter().map(|(x, y)| (y, x)).collect()
    }
}

/// A KiCad three-point arc (start, mid, end) sampled into a polyline including both ends.
pub fn arc_points(p0: Pt, pm: Pt, p1: Pt, max_step: f64) -> Vec<Pt> {
    let (x0, y0) = p0;
    let (xm, ym) = pm;
    let (x1, y1) = p1;
    let (ax, ay) = (xm - x0, ym - y0);
    let (bx, by) = (x1 - x0, y1 - y0);
    let d = 2.0 * (ax * by - ay * bx);
    if d.abs() < 1e-9 {
        return vec![p0, p1];
    }
    let a2 = ax * ax + ay * ay;
    let b2 = bx * bx + by * by;
    let ux = (by * a2 - ay * b2) / d;
    let uy = (ax * b2 - bx * a2) / d;
    let (cx, cy) = (x0 + ux, y0 + uy);
    let r = ux.hypot(uy);
    let t0 = (y0 - cy).atan2(x0 - cx);
    let tm = (ym - cy).atan2(xm - cx);
    let t1 = (y1 - cy).atan2(x1 - cx);
    let ccw = |a: f64, b: f64| (b - a).rem_euclid(2.0 * std::f64::consts::PI);
    let sweep = if ccw(t0, tm) <= ccw(t0, t1) { ccw(t0, t1) } else { -ccw(t1, t0) };
    let n = ((sweep.abs() * r / max_step).ceil() as usize).max(2);
    (0..=n).map(|k| {
        let t = t0 + sweep * k as f64 / n as f64;
        (cx + r * t.cos(), cy + r * t.sin())
    }).collect()
}

fn dist(a: Pt, b: Pt) -> f64 {
    (a.0 - b.0).hypot(a.1 - b.1)
}

/// Join open polylines end to end into one closed loop (the board outline).
pub fn chain_polylines(mut pieces: Vec<Vec<Pt>>, tol: f64) -> Result<Vec<Pt>, String> {
    pieces.retain(|p| p.len() >= 2);
    if pieces.is_empty() {
        return Ok(Vec::new());
    }
    let mut looped = pieces.remove(0);
    while !pieces.is_empty() {
        let end = *looped.last().unwrap();
        let mut best: Option<(usize, bool)> = None;
        for (idx, p) in pieces.iter().enumerate() {
            if dist(end, p[0]) < tol {
                best = Some((idx, false));
                break;
            }
            if dist(end, *p.last().unwrap()) < tol {
                best = Some((idx, true));
                break;
            }
        }
        let Some((idx, rev)) = best else {
            return Err(format!("Edge.Cuts outline is not one closed loop (gap at {:.3}, {:.3})", end.0, end.1));
        };
        let mut p = pieces.remove(idx);
        if rev {
            p.reverse();
        }
        looped.extend(p.into_iter().skip(1));
    }
    if looped.len() > 1 && dist(looped[0], *looped.last().unwrap()) < tol {
        looped.pop();
    }
    Ok(looped)
}

/// Chain pieces into every closed loop they form (an outer outline plus inner cutouts such as a
/// bore or a slot). A piece that cannot be continued back to its loop's start is an open outline.
pub fn chain_loops(mut pieces: Vec<Vec<Pt>>, tol: f64) -> Result<Vec<Vec<Pt>>, String> {
    pieces.retain(|p| p.len() >= 2);
    let mut loops = Vec::new();
    while !pieces.is_empty() {
        let mut looped = pieces.remove(0);
        while dist(looped[0], *looped.last().unwrap()) >= tol {
            let end = *looped.last().unwrap();
            let mut best: Option<(usize, bool)> = None;
            for (idx, p) in pieces.iter().enumerate() {
                if dist(end, p[0]) < tol {
                    best = Some((idx, false));
                    break;
                }
                if dist(end, *p.last().unwrap()) < tol {
                    best = Some((idx, true));
                    break;
                }
            }
            let Some((idx, rev)) = best else {
                return Err(format!("Edge.Cuts outline is not closed (gap at {:.3}, {:.3})", end.0, end.1));
            };
            let mut p = pieces.remove(idx);
            if rev {
                p.reverse();
            }
            looped.extend(p.into_iter().skip(1));
        }
        if looped.len() > 1 && dist(looped[0], *looped.last().unwrap()) < tol {
            looped.pop();
        }
        if looped.len() >= 3 {
            loops.push(looped);
        }
    }
    Ok(loops)
}

pub fn polygon_area(poly: &[Pt]) -> f64 {
    let n = poly.len();
    if n < 3 {
        return 0.0;
    }
    let mut a = 0.0;
    for i in 0..n {
        let (x0, y0) = poly[i];
        let (x1, y1) = poly[(i + 1) % n];
        a += x0 * y1 - x1 * y0;
    }
    a / 2.0
}

pub fn point_in_poly(x: f64, y: f64, poly: &[Pt]) -> bool {
    let mut inside = false;
    let n = poly.len();
    for k in 0..n {
        let (ax, ay) = poly[k];
        let (bx, by) = poly[(k + 1) % n];
        if (ay > y) != (by > y) && x < ax + (y - ay) * (bx - ax) / (by - ay) {
            inside = !inside;
        }
    }
    inside
}

pub fn seg_distance(x: f64, y: f64, ax: f64, ay: f64, bx: f64, by: f64) -> f64 {
    let (dx, dy) = (bx - ax, by - ay);
    let l2 = dx * dx + dy * dy;
    if l2 < 1e-12 {
        return (x - ax).hypot(y - ay);
    }
    let t = (((x - ax) * dx + (y - ay) * dy) / l2).clamp(0.0, 1.0);
    (x - (ax + t * dx)).hypot(y - (ay + t * dy))
}

/// 0 inside the polygon, else the distance to its boundary.
pub fn point_poly_distance(x: f64, y: f64, poly: &[Pt]) -> f64 {
    if point_in_poly(x, y, poly) {
        return 0.0;
    }
    let n = poly.len();
    let mut best = f64::INFINITY;
    for k in 0..n {
        let (ax, ay) = poly[k];
        let (bx, by) = poly[(k + 1) % n];
        best = best.min(seg_distance(x, y, ax, ay, bx, by));
    }
    best
}

/// Whether segments a-b and c-d cross or touch.
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 > 0.0) != (d2 > 0.0) && (d3 > 0.0) != (d4 > 0.0)) && d1 != 0.0 && d2 != 0.0 && d3 != 0.0 && d4 != 0.0
}

/// Distance from the segment a-b to a filled polygon: 0 when the segment reaches inside it anywhere
/// (an end inside, or crossing its edge), else the smallest gap between the segment and an edge.
pub fn seg_poly_distance(a: Pt, b: Pt, poly: &[Pt]) -> f64 {
    let n = poly.len();
    if n == 0 { return f64::INFINITY; }
    if point_in_poly(a.0, a.1, poly) || point_in_poly(b.0, b.1, poly) { return 0.0; }
    let mut best = f64::INFINITY;
    for k in 0..n {
        let (c, d) = (poly[k], poly[(k + 1) % n]);
        if segs_cross(a, b, c, d) { return 0.0; }
        best = best.min(seg_distance(a.0, a.1, c.0, c.1, d.0, d.1)).min(seg_distance(b.0, b.1, c.0, c.1, d.0, d.1))
            .min(seg_distance(c.0, c.1, a.0, a.1, b.0, b.1)).min(seg_distance(d.0, d.1, a.0, a.1, b.0, b.1));
    }
    best
}

/// Cheap outward growth of a polygon: every vertex pushed away from the centroid by d.
pub fn grow_poly(poly: &[Pt], d: f64) -> Vec<Pt> {
    let n = poly.len() as f64;
    let cx = poly.iter().map(|p| p.0).sum::<f64>() / n;
    let cy = poly.iter().map(|p| p.1).sum::<f64>() / n;
    poly.iter().map(|&(x, y)| {
        let (vx, vy) = (x - cx, y - cy);
        let l = vx.hypot(vy).max(1e-9);
        (x + vx / l * d, y + vy / l * d)
    }).collect()
}

pub fn thick_line_poly(a: Pt, b: Pt, hw: f64) -> Vec<Pt> {
    let (dx, dy) = (b.0 - a.0, b.1 - a.1);
    let l = dx.hypot(dy).max(1e-9);
    let (nx, ny) = (-dy / l * hw, dx / l * hw);
    vec![(a.0 + nx, a.1 + ny), (b.0 + nx, b.1 + ny), (b.0 - nx, b.1 - ny), (a.0 - nx, a.1 - ny)]
}

pub fn bbox(pts: &[Pt]) -> (f64, f64, f64, f64) {
    let mut b = (f64::INFINITY, f64::INFINITY, f64::NEG_INFINITY, f64::NEG_INFINITY);
    for &(x, y) in pts {
        b.0 = b.0.min(x);
        b.1 = b.1.min(y);
        b.2 = b.2.max(x);
        b.3 = b.3.max(y);
    }
    b
}

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

    #[test]
    fn outer_loop_and_slot_drawn_in_lines_both_close() {
        // an outer square and an inner slot, each four lines, pieces shuffled together (issue #77)
        let seg = |a: Pt, b: Pt| vec![a, b];
        let pieces = vec![
            seg((0.0, 0.0), (10.0, 0.0)), seg((4.0, 4.0), (6.0, 4.0)), seg((10.0, 0.0), (10.0, 10.0)),
            seg((6.0, 4.0), (6.0, 6.0)), seg((0.0, 10.0), (10.0, 10.0)), seg((6.0, 6.0), (4.0, 6.0)),
            seg((0.0, 10.0), (0.0, 0.0)), seg((4.0, 6.0), (4.0, 4.0)),
        ];
        let loops = chain_loops(pieces, 0.01).unwrap();
        assert_eq!(loops.len(), 2);
        let mut areas: Vec<f64> = loops.iter().map(|l| polygon_area(l).abs()).collect();
        areas.sort_by(|a, b| a.total_cmp(b));
        assert!((areas[0] - 4.0).abs() < 1e-9 && (areas[1] - 100.0).abs() < 1e-9, "{areas:?}");
        assert!(chain_loops(vec![seg((0.0, 0.0), (1.0, 0.0)), seg((1.0, 0.0), (1.0, 1.0))], 0.01).is_err(), "an open outline is refused");
    }
}