AI Flow: Routing

//! Exact geometry. Coordinates are integer nanometres on the board; distances are f64 nanometres.

pub type P = (i64, i64);
pub const NM: f64 = 1e6; // nanometres per millimetre
pub const SQRT2: f64 = std::f64::consts::SQRT_2;
/// How far under a clearance copper may land by coordinate rounding alone, nm. KiCad tolerates about
/// 500 nm (it flagged 0.1991 against 0.2 on the benchmark C). His benchmark C's 0.2 mm stub down the middle of U5.9
/// sits exactly 0.200 mm from both neighbours; without this, a few nm of rounding called it illegal.
pub const DRC_TOL: f64 = 400.0;

pub fn mm(v: f64) -> i64 {
    (v * NM).round() as i64
}
pub fn to_mm(v: i64) -> f64 {
    v as f64 / NM
}

#[derive(Clone, Copy, Debug, PartialEq)]
pub struct V(pub f64, pub f64);

impl From<P> for V {
    fn from(p: P) -> V {
        V(p.0 as f64, p.1 as f64)
    }
}

#[inline]
pub fn dot(a: V, b: V) -> f64 {
    a.0 * b.0 + a.1 * b.1
}
#[inline]
pub fn sub(a: V, b: V) -> V {
    V(a.0 - b.0, a.1 - b.1)
}
#[inline]
pub fn hypot(a: V) -> f64 {
    (a.0 * a.0 + a.1 * a.1).sqrt()
}

pub fn pt_seg(p: V, a: V, b: V) -> f64 {
    let ab = sub(b, a);
    let l2 = dot(ab, ab);
    if l2 <= 0.0 {
        return hypot(sub(p, a));
    }
    let t = (dot(sub(p, a), ab) / l2).clamp(0.0, 1.0);
    hypot(sub(p, V(a.0 + ab.0 * t, a.1 + ab.1 * t)))
}

fn orient(a: V, b: V, c: V) -> f64 {
    (b.0 - a.0) * (c.1 - a.1) - (b.1 - a.1) * (c.0 - a.0)
}

pub fn seg_cross(a: V, b: V, c: V, d: V) -> bool {
    let (o1, o2, o3, o4) = (orient(a, b, c), orient(a, b, d), orient(c, d, a), orient(c, d, b));
    (o1 > 0.0) != (o2 > 0.0) && (o3 > 0.0) != (o4 > 0.0)
}

pub fn seg_seg(a: V, b: V, c: V, d: V) -> f64 {
    if seg_cross(a, b, c, d) {
        return 0.0;
    }
    pt_seg(a, c, d).min(pt_seg(b, c, d)).min(pt_seg(c, a, b)).min(pt_seg(d, a, b))
}

pub fn in_poly(p: V, pts: &[V]) -> bool {
    let mut inside = false;
    let n = pts.len();
    let mut j = n.wrapping_sub(1);
    for i in 0..n {
        let (a, b) = (pts[i], pts[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 {
            inside = !inside;
        }
        j = i;
    }
    inside
}

/// Copper or a hole, as an exact outline. `Poly` carries an outward inflation (zero for most).
#[derive(Clone, Debug)]
pub enum Shape {
    Circle { c: V, r: f64 },
    Capsule { a: V, b: V, r: f64 },
    Poly { pts: Vec<V>, r: f64 },
    /// Several outlines that are one piece of copper: a custom pad's anchor and its primitives.
    Multi(Vec<Shape>),
}

impl Shape {
    /// Edge-to-edge distance from a zero-width segment to this outline; 0 when they touch.
    pub fn dist_seg(&self, a: V, b: V) -> f64 {
        match self {
            Shape::Circle { c, r } => (pt_seg(*c, a, b) - r).max(0.0),
            Shape::Capsule { a: p, b: q, r } => (seg_seg(a, b, *p, *q) - r).max(0.0),
            Shape::Poly { pts, r } => {
                if in_poly(a, pts) || in_poly(b, pts) {
                    return 0.0;
                }
                let n = pts.len();
                let mut d = f64::INFINITY;
                for i in 0..n {
                    d = d.min(seg_seg(a, b, pts[i], pts[(i + 1) % n]));
                    if d <= 0.0 {
                        return 0.0;
                    }
                }
                (d - r).max(0.0)
            }
            Shape::Multi(v) => v.iter().map(|s| s.dist_seg(a, b)).fold(f64::INFINITY, f64::min),
        }
    }
    pub fn dist_pt(&self, p: V) -> f64 {
        self.dist_seg(p, p)
    }
    /// Edge-to-edge distance between two outlines.
    pub fn dist_shape(&self, o: &Shape) -> f64 {
        match o {
            Shape::Circle { c, r } => (self.dist_pt(*c) - r).max(0.0),
            Shape::Capsule { a, b, r } => (self.dist_seg(*a, *b) - r).max(0.0),
            Shape::Poly { pts, r } => match self {
                Shape::Poly { pts: mine, r: mr } => {
                    if pts.iter().any(|p| in_poly(*p, mine)) || mine.iter().any(|p| in_poly(*p, pts)) {
                        return 0.0;
                    }
                    let mut d = f64::INFINITY;
                    let n = pts.len();
                    let m = mine.len();
                    for i in 0..n {
                        for j in 0..m {
                            d = d.min(seg_seg(pts[i], pts[(i + 1) % n], mine[j], mine[(j + 1) % m]));
                        }
                    }
                    (d - r - mr).max(0.0)
                }
                _ => o.dist_shape(self),
            },
            Shape::Multi(v) => v.iter().map(|s| self.dist_shape(s)).fold(f64::INFINITY, f64::min),
        }
    }
    pub fn bbox(&self) -> (f64, f64, f64, f64) {
        match self {
            Shape::Circle { c, r } => (c.0 - r, c.1 - r, c.0 + r, c.1 + r),
            Shape::Capsule { a, b, r } => (a.0.min(b.0) - r, a.1.min(b.1) - r, a.0.max(b.0) + r, a.1.max(b.1) + r),
            Shape::Poly { pts, r } => {
                let mut bb = (f64::MAX, f64::MAX, f64::MIN, f64::MIN);
                for p in pts {
                    bb = (bb.0.min(p.0), bb.1.min(p.1), bb.2.max(p.0), bb.3.max(p.1));
                }
                (bb.0 - r, bb.1 - r, bb.2 + r, bb.3 + r)
            }
            Shape::Multi(v) => {
                let mut bb = (f64::MAX, f64::MAX, f64::MIN, f64::MIN);
                for s in v {
                    let b = s.bbox();
                    bb = (bb.0.min(b.0), bb.1.min(b.1), bb.2.max(b.2), bb.3.max(b.3));
                }
                bb
            }
        }
    }
    /// Largest value of `ux*x + uy*y` over the outline, for tangent lines in any direction.
    pub fn support(&self, ux: f64, uy: f64) -> f64 {
        let len = (ux * ux + uy * uy).sqrt();
        match self {
            Shape::Circle { c, r } => ux * c.0 + uy * c.1 + r * len,
            Shape::Capsule { a, b, r } => (ux * a.0 + uy * a.1).max(ux * b.0 + uy * b.1) + r * len,
            Shape::Poly { pts, r } => pts.iter().map(|p| ux * p.0 + uy * p.1).fold(f64::MIN, f64::max) + r * len,
            Shape::Multi(v) => v.iter().map(|s| s.support(ux, uy)).fold(f64::MIN, f64::max),
        }
    }
    pub fn center(&self) -> V {
        let b = self.bbox();
        V((b.0 + b.2) / 2.0, (b.1 + b.3) / 2.0)
    }
}

/// Rotate a local point the way KiCad does (y down, positive angle counter-clockwise on screen).
pub fn rot(x: f64, y: f64, deg: f64) -> (f64, f64) {
    if deg == 0.0 {
        return (x, y);
    }
    let (s, c) = deg.to_radians().sin_cos();
    (x * c + y * s, -x * s + y * c)
}

pub fn arc_points(s: V, m: V, e: V, step_nm: f64) -> Vec<V> {
    let d = 2.0 * (s.0 * (m.1 - e.1) + m.0 * (e.1 - s.1) + e.0 * (s.1 - m.1));
    if d.abs() < 1.0 {
        return vec![s, e];
    }
    let sq = |p: V| p.0 * p.0 + p.1 * p.1;
    let ux = (sq(s) * (m.1 - e.1) + sq(m) * (e.1 - s.1) + sq(e) * (s.1 - m.1)) / d;
    let uy = (sq(s) * (e.0 - m.0) + sq(m) * (s.0 - e.0) + sq(e) * (m.0 - s.0)) / d;
    let r = ((s.0 - ux).powi(2) + (s.1 - uy).powi(2)).sqrt();
    let a0 = (s.1 - uy).atan2(s.0 - ux);
    let am = (m.1 - uy).atan2(m.0 - ux);
    let a1 = (e.1 - uy).atan2(e.0 - ux);
    let tau = std::f64::consts::TAU;
    let norm = |x: f64| ((x % tau) + tau) % tau;
    let ccw_m = norm(am - a0);
    let ccw_e = norm(a1 - a0);
    let sweep = if ccw_m <= ccw_e { ccw_e } else { ccw_e - tau };
    let n = ((sweep.abs() * r / step_nm).ceil() as usize).clamp(2, 64);
    (0..=n)
        .map(|i| {
            let a = a0 + sweep * i as f64 / n as f64;
            V(ux + r * a.cos(), uy + r * a.sin())
        })
        .collect()
}