Route past round pads by their outline, not their bounding square

A circle pad was its bounding box in both the grid and the exact check, so a
4 mm mounting hole's square corners refused legal routes 0.8 mm clear of the
real copper. It is now a 16-sided polygon whose sides touch the circle, so
the router is never closer than KiCad measures. diagnose.py takes --seed.

bench/diagnose.py

@@ -185,7 +185,7 @@ def _flood(router: GridRouter, pin, net_no: int, conns) -> tuple[int, Counter]:
 
 def diagnose(
     dsn_text: str, edge_clearance_mm: float | None, resolution: int = 2, shove: bool = False,
-    access_cost: float = 0.0, hole_to_hole_mm: float = 0.25,
+    access_cost: float = 0.0, hole_to_hole_mm: float = 0.25, seed: int | None = None,
 ) -> dict:
     dsn = parse_dsn(dsn_text)
     names = {i + 1: n.name for i, n in enumerate(dsn.nets)}
@@ -201,6 +201,7 @@ def diagnose(
         resolution=resolution,
         shove=shove,
         access_cost=access_cost,
+        seed=seed,
         # the product's configuration: net-class widths and hole spacing
         net_widths=_net_widths_board(dsn, scale),
         via_drill=_via_drill_board(dsn, scale),
@@ -276,12 +277,13 @@ def main(argv: list[str] | None = None) -> int:
     ap.add_argument("--grid-resolution", type=int, default=2, metavar="K")
     ap.add_argument("--shove", action="store_true", help="as mckicad routes")
     ap.add_argument("--access-cost", type=float, default=0.0)
+    ap.add_argument("--seed", type=int, help="route in this shuffled order, as bench.py does")
     ap.add_argument("--hole-to-hole", type=float, default=0.25, metavar="MM")
     ap.add_argument("--json", type=Path, help="also write the full table here")
     args = ap.parse_args(argv)
 
     report = diagnose(args.dsn.read_text(), args.edge_clearance, args.grid_resolution, args.shove,
-                      args.access_cost, args.hole_to_hole)
+                      args.access_cost, args.hole_to_hole, args.seed)
     for row in report["failures"]:
         extra = ""
         for w in row.get("walled", []):

src/freeroute/board/build.py

@@ -12,9 +12,10 @@ model. It mirrors what FreeRouting's ``Structure.create_board`` / ``Library`` /
 * padstacks x placement -> :class:`Pin` items
 * keepouts -> :class:`ObstacleArea` items
 
-Pad geometry: a rectangle pad becomes an exact :class:`IntBox`; a circle pad its
+Pad geometry: a rectangle pad becomes an exact :class:`IntBox`; a circle pad a
-bounding box (documented approximation pending an exact circle tile); a convex
+16-sided :class:`Simplex` drawn just outside it (its corners stand out by 2% of
-polygon pad an exact :class:`Simplex`. Every pad is placed centred on its pin
+the radius, where the bounding box's stood out by 41%); a convex polygon pad an
+exact :class:`Simplex`. Every pad is placed centred on its pin
 location, so it contains that location by construction. Component rotation is
 applied to the pin position; the pad tile itself is not rotated (irrelevant to
 the containment invariant, and pads are centre-symmetric in practice).
@@ -249,7 +250,7 @@ def _placed_pad_tile(shape: Shape, place, dsn_pin, transform: CoordinateTransfor
         r = round(transform.dsn_to_board(shape.diameter / 2))
         cx = round(transform.dsn_to_board(centre.x))
         cy = round(transform.dsn_to_board(centre.y))
-        return IntBox(cx - r, cy - r, cx + r, cy + r)
+        return _circle_tile(cx, cy, r)
     if isinstance(shape, Rectangle):
         x0, y0, x1, y1 = shape.coords[:4]
         corners = [(x0, y0), (x1, y0), (x1, y1), (x0, y1)]
@@ -281,6 +282,32 @@ def _placed_pad_tile(shape: Shape, place, dsn_pin, transform: CoordinateTransfor
     return IntBox(min(xs), min(ys), max(xs), max(ys))
 
 
+_CIRCLE_SIDES = 16
+
+
+def _circle_tile(cx: int, cy: int, r: int):
+    """A polygon around the circle, every side touching it. A square around a
+    big round pad (a mounting hole) puts phantom copper in its corners that
+    blocks legal routes past it; this stays outside the circle, so the router
+    is still never closer than KiCad measures."""
+    if r < 8:
+        return IntBox(cx - r, cy - r, cx + r, cy + r)
+    reach = r / math.cos(math.pi / _CIRCLE_SIDES)
+    corners = []
+    for k in range(_CIRCLE_SIDES):
+        a = (k + 0.5) * 2 * math.pi / _CIRCLE_SIDES
+        dx, dy = reach * math.cos(a), reach * math.sin(a)
+        # round away from the centre so the polygon never cuts into the circle
+        corners.append(IntPoint(cx + math.copysign(math.ceil(abs(dx)), dx),
+                                cy + math.copysign(math.ceil(abs(dy)), dy)))
+    corners = [IntPoint(int(p.x), int(p.y)) for p in corners]
+    for winding in (corners, corners[::-1]):
+        simplex = Simplex.from_corners(winding)
+        if not simplex.is_empty():
+            return simplex
+    return IntBox(cx - r, cy - r, cx + r, cy + r)
+
+
 def _convex_hull(pts: list[IntPoint]) -> list[IntPoint]:
     """The convex hull of ``pts`` counter-clockwise, collinear points dropped."""
     ps = sorted({(p.x, p.y) for p in pts})
@@ -310,7 +337,7 @@ def _pad_tile(shape: Shape, transform: CoordinateTransform):
         r = round(transform.dsn_to_board(shape.diameter / 2))
         cx = round(transform.dsn_to_board(shape.center_x))
         cy = round(transform.dsn_to_board(shape.center_y))
-        return IntBox(cx - r, cy - r, cx + r, cy + r)  # bounding-box approximation
+        return _circle_tile(cx, cy, r)
     if isinstance(shape, (Polygon, Path)):
         coords = shape.coords
         pts = [