Merge feat/smooth: opt-in --smooth turns grid staircases into octilinear runs after routing

A short diagonal at a wire's end is a kink beside its pad, and the pour
refilled round it left a copper sliver (KiCad copper_sliver) on the
TerraHawk lights node. Small offsets now stay square jogs; chamfers get
the same floor.

bench/bench.py

@@ -100,13 +100,18 @@ def run_one(board, variant, seed: int, timeout: float) -> dict:
         )
         rss_mb = round(usage.ru_maxrss / 1024)
         secs = round(time.monotonic() - start, 1)
+        try:
+            with open(f"{tmp}/out.ses", encoding="utf-8") as f:
+                vias = f.read().count("(via ")
+        except OSError:
+            vias = None
     missing = NOT_ROUTED.search(err)
     zone = TO_ZONE.search(err)
     return {
         "board": name, "variant": vname, "seed": seed, "status": status,
         "unrouted": int(missing.group(1)) if missing else 0,
         "to_zone": int(zone.group(1)) if zone else 0,
-        "secs": secs, "rss_mb": rss_mb,
+        "secs": secs, "rss_mb": rss_mb, "vias": vias,
         "tail": err.strip().splitlines()[-1] if status != "ok" and err.strip() else "",
     }
 
@@ -147,6 +152,16 @@ def report(rows: list[dict], boards, variants) -> None:
                     line += (f"   {dm:+.1f} ± {se:.1f}  ({better} better, {worse} worse,"
                              f" {len(diffs) - better - worse} same)  {verdict}")
             print(line)
+    # vias, where the runs recorded them (older result files did not)
+    print("\nvias per variant, summed over boards (mean over seeds per board)\n")
+    for vname, _, _ in variants:
+        total, boards_counted = 0.0, 0
+        for bname, _, _ in boards:
+            vs = [r["vias"] for k, r in ok.items() if k[:2] == (bname, vname) and r.get("vias") is not None]
+            if vs:
+                total += sum(vs) / len(vs)
+                boards_counted += 1
+        print(f"{vname:14} {total:8.1f} vias over {boards_counted} boards")
     failed = [r for r in rows if r["status"] != "ok"]
     for r in failed:
         print(f"FAILED {r['board']} {r['variant']} seed {r['seed']}: {r['status']} {r['tail']}")

src/rpmroute/board/search_tree.py

@@ -237,3 +237,36 @@ class ShapeSearchTree:
                 if overlaps_2d(grown, other_tile):
                     return shape
         return None
+
+    def violation_pairs(self, clearance: int) -> list[tuple[TreeShape, TreeShape, bool]]:
+        """Every different-net pair sharing a layer, at least one of them
+        routed, whose coppers come closer than ``clearance``: ``(routed tile,
+        other tile, touching)``. ``touching`` is True when the coppers
+        themselves overlap (a short, or copper inside a keepout); False for a
+        clearance violation. Each pair of tiles is reported once.
+
+        :meth:`has_violation` asks whether there is one; this lists them all,
+        for a report on copper that no engine has checked.
+        """
+        pairs: list[tuple[TreeShape, TreeShape, bool]] = []
+        seen: set[tuple[int, int]] = set()
+        for shape in self.all_shapes():
+            if not shape.routed:
+                continue
+            mine = shape.exact if shape.exact is not None else shape.tile
+            grown = shape.clearance_region(clearance)
+            for other in self.overlapping(grown.bounding_box()):
+                if other is shape or other.net_no == shape.net_no:
+                    continue
+                if not (shape.layers & other.layers):
+                    continue
+                key = (min(id(shape), id(other)), max(id(shape), id(other)))
+                if key in seen:
+                    continue
+                theirs = other.exact if other.exact is not None else other.tile
+                touching = overlaps_2d(mine, theirs)
+                if not touching and (not other.clearance or not overlaps_2d(grown, theirs)):
+                    continue  # a rule area only counts an overlap
+                seen.add(key)
+                pairs.append((shape, other, touching))
+        return pairs

src/rpmroute/cli.py

@@ -25,15 +25,20 @@ from rpmroute.route.pipeline import (
     build_rooms_routing_result,
     build_routing_result,
 )
+from rpmroute.route.smooth import smooth
+from rpmroute.route.verify import verify_result
 from rpmroute.ses import write_ses
 
 #: which optional flags each engine actually implements. Anything not listed for
 #: an engine is rejected by :func:`_validate` rather than quietly ignored.
 ENGINE_OPTIONS: dict[str, frozenset[str]] = {
-    "grid": frozenset({"rip_up", "max_passes", "seed", "orders", "promote", "access", "negotiate", "rollback", "tree"}),
+    "grid": frozenset({
+        "rip_up", "max_passes", "seed", "orders", "promote", "access", "negotiate", "rollback",
+        "tree", "via_cost",
+    }),
     "exact": frozenset({
         "shove", "diagonal", "rip_up", "max_passes", "seed", "orders", "promote", "access",
-        "negotiate", "rollback", "tree", "window",
+        "negotiate", "rollback", "tree", "window", "vias", "via_cost", "smooth",
     }),
     "room": frozenset({"shove", "pack"}),
 }
@@ -53,6 +58,9 @@ _FLAG_NAMES = {
     "rollback": "--no-rollback",
     "tree": "--no-tree",
     "window": "--window-reroute",
+    "vias": "--reduce-vias",
+    "via_cost": "--via-cost",
+    "smooth": "--smooth",
 }
 
 
@@ -182,6 +190,19 @@ def build_parser() -> argparse.ArgumentParser:
         "board, where routes may share space at a price that rises where they compete; "
         "the contested cells then cost extra in the real routing (default 0: off)",
     )
+    parser.add_argument(
+        "--smooth",
+        action="store_true",
+        help="exact engine: after routing, turn grid staircases into straight and 45-degree "
+        "runs and chamfer right-angle corners; same nets, ends, vias and layers, and every "
+        "new piece of copper checked on exact shapes against the board edge, other nets "
+        "and keepouts",
+    )
+    parser.add_argument(
+        "--smooth-report",
+        action="store_true",
+        help="with --smooth (implies it): also print track length per layer before and after",
+    )
     parser.add_argument(
         "--no-rollback",
         dest="rollback",
@@ -237,6 +258,37 @@ def build_parser() -> argparse.ArgumentParser:
         metavar="MM",
         help="the first round's window margin around the stuck connection's pins (default 1.5)",
     )
+    parser.add_argument(
+        "--via-cost",
+        type=float,
+        default=None,
+        metavar="C",
+        help="grid and exact engines: what a layer change costs the search, in grid "
+        "steps of track (default 10)",
+    )
+    parser.add_argument(
+        "--reduce-vias",
+        action="store_true",
+        default=None,
+        help="exact engine: after routing, route each net that has vias again on its own "
+        "with vias made dearer, everything else held fixed; its new copper is kept only "
+        "if it fails nothing new and has fewer vias",
+    )
+    parser.add_argument(
+        "--reduce-vias-budget",
+        type=float,
+        default=0.5,
+        metavar="F",
+        help="via reduction stops starting nets once it has spent this share of the "
+        "routing's own time (default 0.5)",
+    )
+    parser.add_argument(
+        "--reduce-vias-margin",
+        type=float,
+        default=2.0,
+        metavar="MM",
+        help="how far past its pins and copper a net may go when routed again (default 2.0)",
+    )
     parser.add_argument(
         "--hole-to-hole",
         type=float,
@@ -251,6 +303,15 @@ def build_parser() -> argparse.ArgumentParser:
         metavar="J",
         help="processes for --orders (default: one per order, up to the CPU count)",
     )
+    parser.add_argument(
+        "--strict",
+        action="store_true",
+        help=(
+            "exit with status 3 when the routed copper has shorts or clearance "
+            "violations (grid and room output is checked after routing; the "
+            "session file is still written)"
+        ),
+    )
     return parser
 
 
@@ -278,6 +339,9 @@ def main(argv: list[str] | None = None) -> int:
             ("rollback", not args.rollback),
             ("tree", not args.tree_nets),
             ("window", args.window_reroute is not None),
+            ("vias", args.reduce_vias is not None),
+            ("via_cost", args.via_cost is not None),
+            ("smooth", args.smooth or args.smooth_report),
         )
         if asked
     ]
@@ -321,7 +385,12 @@ def main(argv: list[str] | None = None) -> int:
             "window_margin_mm": args.window_margin,
             "window_budget": args.window_budget,
             "window_cap": args.window_cap,
+            "reduce_vias": bool(args.reduce_vias),
+            "reduce_vias_budget": args.reduce_vias_budget,
+            "reduce_vias_margin_mm": args.reduce_vias_margin,
         }
+        if args.via_cost is not None:
+            options["via_cost"] = args.via_cost
     elif args.engine == "grid":
         options = {
             "layers": layers,
@@ -335,6 +404,8 @@ def main(argv: list[str] | None = None) -> int:
             "rollback": args.rollback,
             "tree_nets": args.tree_nets,
         }
+        if args.via_cost is not None:
+            options["via_cost"] = args.via_cost
     if args.engine == "room":
         result = build_rooms_routing_result(
             dsn, layers=layers, shove=args.shove, pack=args.pack,
@@ -363,6 +434,13 @@ def main(argv: list[str] | None = None) -> int:
     else:
         result = build_routing_result(dsn, seed=args.seed, **options)
 
+    if args.smooth or args.smooth_report:
+        report = smooth(dsn, result, edge_clearance_mm=args.edge_clearance)
+        print(f"rpmroute: {report.line()}", file=sys.stderr)
+        if args.smooth_report:
+            for row in report.table():
+                print(row, file=sys.stderr)
+
     ses_text = write_ses(dsn, result)
     missing = [u for u in result.unrouted if not u[3]]
     in_zone = [u for u in result.unrouted if u[3]]
@@ -387,14 +465,25 @@ def main(argv: list[str] | None = None) -> int:
         for net, a, b, zone in in_zone:
             print(f"  {net}: {a} to {b} (both in zone {zone})", file=sys.stderr)
 
+    flawed = False
     if args.engine != "exact":
         # These engines route on approximations and do not check the copper
-        # they write against exact shapes: a board can come out with shorts
-        # that this report would otherwise never mention.
+        # they write: check it now against the exact shapes the exact engine
+        # uses, so shorts are reported rather than shipped.
+        check = verify_result(dsn, result)
+        flawed = not check.clean
         print(
-            f"rpmroute: WARNING: the {args.engine} engine does not check its copper for "
-            "clearance or shorts; run KiCad's DRC on the result, or route with "
-            "--engine exact (the default)",
+            f"rpmroute: {args.engine} output checked on exact shapes: "
+            f"{check.shorts} short(s), {check.clearance} clearance violation(s)",
+            file=sys.stderr,
+        )
+        for kind, examples in (("short", check.short_examples), ("clearance", check.clearance_examples)):
+            for found in examples:
+                print(f"  {kind}: {found}", file=sys.stderr)
+        if flawed:
+            print(
+                f"rpmroute: WARNING: this {args.engine} routing is not DRC-clean; fix it in "
+                "KiCad or route with --engine exact (the default)",
                 file=sys.stderr,
             )
 
@@ -403,7 +492,7 @@ def main(argv: list[str] | None = None) -> int:
             f.write(ses_text)
     else:
         sys.stdout.write(ses_text)
-    return 0
+    return 3 if (flawed and args.strict) else 0
 
 
 if __name__ == "__main__":

src/rpmroute/route/exact_router.py

@@ -155,38 +155,7 @@ def route_board_exact(
     owner = _counter()
 
     # static items: pad and keepout copper (routed=False)
-    for pin in board.get_pins():
-        if pin.shape is None:
-            continue
-        box = pin.shape.bounding_box()
-        if box.is_empty():
-            continue
-        net = pin.net_nos[0] if pin.net_nos else -1
-        pin_layers = frozenset(layer for layer in pin.layers if layer in signal_layers)
-        if pin_layers:
-            # a rotated pad is checked against its outline, not its box
-            exact = pin.shape if _is_rotated(pin.shape) else None
-            tree.insert(TreeShape(next(owner), net, pin_layers, box, exact=exact))
-    for net, copper_layers, box in board.get_fixed_copper():
-        on = frozenset(layer for layer in copper_layers if layer in signal_layers)
-        if on and not box.is_empty():
-            tree.insert(TreeShape(next(owner), net, on, box))
-    for obstacle in board.get_obstacle_areas():
-        if obstacle.layer not in signal_layers:
-            continue
-        blocks = (
-            "all" if obstacle.blocks_wires and obstacle.blocks_vias
-            else "wires" if obstacle.blocks_wires else "vias"
-        )
-        for tile in obstacle.tiles:
-            box = tile.bounding_box()
-            if not box.is_empty():
-                tree.insert(
-                    TreeShape(
-                        next(owner), -1, frozenset({obstacle.layer}), box,
-                        blocks=blocks, clearance=obstacle.clearance,
-                    )
-                )
+    insert_static_copper(tree, board, signal_layers, owner)
 
     via_layers = frozenset(signal_layers)
     accepted: dict[int, _Accepted] = {}
@@ -325,6 +294,43 @@ def route_board_exact(
 # --- 45-degree (diagonal) recovery -------------------------------------------
 
 
+def insert_static_copper(tree: ShapeSearchTree, board: BasicBoard, signal_layers, owner) -> None:
+    """Index the board's pads, fixed copper and keepouts (``routed=False``) on
+    ``signal_layers``: what routed copper is checked against."""
+    for pin in board.get_pins():
+        if pin.shape is None:
+            continue
+        box = pin.shape.bounding_box()
+        if box.is_empty():
+            continue
+        net = pin.net_nos[0] if pin.net_nos else -1
+        pin_layers = frozenset(layer for layer in pin.layers if layer in signal_layers)
+        if pin_layers:
+            # a rotated pad is checked against its outline, not its box
+            exact = pin.shape if _is_rotated(pin.shape) else None
+            tree.insert(TreeShape(next(owner), net, pin_layers, box, exact=exact))
+    for net, copper_layers, box in board.get_fixed_copper():
+        on = frozenset(layer for layer in copper_layers if layer in signal_layers)
+        if on and not box.is_empty():
+            tree.insert(TreeShape(next(owner), net, on, box))
+    for obstacle in board.get_obstacle_areas():
+        if obstacle.layer not in signal_layers:
+            continue
+        blocks = (
+            "all" if obstacle.blocks_wires and obstacle.blocks_vias
+            else "wires" if obstacle.blocks_wires else "vias"
+        )
+        for tile in obstacle.tiles:
+            box = tile.bounding_box()
+            if not box.is_empty():
+                tree.insert(
+                    TreeShape(
+                        next(owner), -1, frozenset({obstacle.layer}), box,
+                        blocks=blocks, clearance=obstacle.clearance,
+                    )
+                )
+
+
 def _octilinear_candidates(a: IntPoint, b: IntPoint) -> list[list[IntPoint]]:
     """Octilinear (0/45/90/135-degree) polylines from ``a`` to ``b``.
 

src/rpmroute/route/pipeline.py

@@ -22,6 +22,7 @@ from rpmroute.ses import RoutedVia, RoutedWire, RoutingResult, write_ses
 from .exact_router import ExactRouteResult, route_board_exact
 from .grid_router import RouteResult, route_board
 from .room_router import route_board_rooms
+from .vias import reduce_vias as reduce_vias_stage
 from .window import window_reroute as window_reroute_stage
 
 __all__ = ["route", "route_dsn_board", "build_routing_result"]
@@ -124,6 +125,7 @@ def route_dsn_board(
     hole_to_hole_mm: float = 0.25,
     rollback: bool = True,
     tree_nets: bool = True,
+    via_cost: float = 10.0,
 ) -> tuple[RouteResult, int, list[str]]:
     """Route a parsed :class:`DsnBoard`; return the board-unit result, the scale,
     and the layer names. ``layers`` restricts routing to those signal-layer
@@ -153,6 +155,7 @@ def route_dsn_board(
         net_widths=_net_widths_board(dsn, scale),
         via_drill=_via_drill_board(dsn, scale),
         hole_to_hole=_mm_to_board(dsn, scale, hole_to_hole_mm) or 0,
+        via_cost=via_cost,
     )
     return result, scale, [layer.name for layer in dsn.layers]
 
@@ -206,6 +209,7 @@ def build_routing_result(
     hole_to_hole_mm: float = 0.25,
     rollback: bool = True,
     tree_nets: bool = True,
+    via_cost: float = 10.0,
 ) -> RoutingResult:
     """Route ``dsn`` (grid track) and convert to a DSN-unit RoutingResult."""
     route, scale, layer_names = route_dsn_board(
@@ -217,6 +221,7 @@ def build_routing_result(
         hole_to_hole_mm=hole_to_hole_mm,
         rollback=rollback,
         tree_nets=tree_nets,
+        via_cost=via_cost,
     )
     return _to_routing_result(route, dsn, scale, layer_names)
 
@@ -244,6 +249,10 @@ def route_dsn_board_exact(
     window_margin_mm: float = 1.5,
     window_budget: float = 0.25,
     window_cap: int = 40,
+    reduce_vias: bool = False,
+    reduce_vias_budget: float = 0.5,
+    reduce_vias_margin_mm: float = 2.0,
+    via_cost: float = 10.0,
 ) -> tuple[ExactRouteResult, int, list[str]]:
     """Route a parsed :class:`DsnBoard` with the exact-geometry (orthogonal,
     DRC-verified) track; return the exact result, the scale, and layer names.
@@ -272,6 +281,7 @@ def route_dsn_board_exact(
         "net_widths": _net_widths_board(dsn, scale),
         "via_drill": _via_drill_board(dsn, scale),
         "hole_to_hole": _mm_to_board(dsn, scale, hole_to_hole_mm) or 0,
+        "via_cost": via_cost,
     }
     started = time.monotonic()
     exact = route_board_exact(
@@ -297,6 +307,18 @@ def route_dsn_board_exact(
             budget_s=max(float(window_budget), 0.0) * (time.monotonic() - started),
             max_windows=window_cap,
         )
+    if reduce_vias:
+        via_half = common["via_half"] or max(width_board // 2, 1)
+        exact.result = reduce_vias_stage(
+            dsn, exact.result, common,
+            resolution=resolution,
+            margin=_mm_to_board(dsn, scale, reduce_vias_margin_mm) or 0,
+            via_half=via_half,
+            via_drill=common["via_drill"] or 2 * via_half,
+            via_name=_via_padstack(dsn),
+            # a share of what the routing itself took
+            budget_s=max(float(reduce_vias_budget), 0.0) * (time.monotonic() - started),
+        )
     return exact, scale, [layer.name for layer in dsn.layers]
 
 
@@ -323,6 +345,10 @@ def build_exact_routing_result(
     window_margin_mm: float = 1.5,
     window_budget: float = 0.25,
     window_cap: int = 40,
+    reduce_vias: bool = False,
+    reduce_vias_budget: float = 0.5,
+    reduce_vias_margin_mm: float = 2.0,
+    via_cost: float = 10.0,
 ) -> RoutingResult:
     """Route ``dsn`` (exact track) and convert to a DSN-unit RoutingResult."""
     exact, scale, layer_names = route_dsn_board_exact(
@@ -347,6 +373,10 @@ def build_exact_routing_result(
         window_margin_mm=window_margin_mm,
         window_budget=window_budget,
         window_cap=window_cap,
+        reduce_vias=reduce_vias,
+        reduce_vias_budget=reduce_vias_budget,
+        reduce_vias_margin_mm=reduce_vias_margin_mm,
+        via_cost=via_cost,
     )
     return _to_routing_result(exact.result, dsn, scale, layer_names)
 

src/rpmroute/route/smooth.py

@@ -0,0 +1,542 @@
+"""Smoothing: a last stage that turns grid staircases into octilinear runs.
+
+The grid search moves one cell at a time along the axes, so a route that
+heads off at an angle comes out as a staircase of short legs. Nothing goes
+back over a path once it connects. This stage does, wire by wire, on the
+finished result:
+
+1. a run of legs between two of its points is replaced by the octilinear
+   shape joining them (one straight leg, or a straight leg and a 45-degree
+   one), the furthest such point first;
+2. the right-angle corners left are cut to 45-degree chamfers;
+3. legs running on in the same direction are merged.
+
+Same nets, same layers, same vias. A wire keeps its ends, every via of its
+net, every point where another wire of its net ends on it, and any leg
+across a pad of its own net that it does not end on; only what lies between
+those moves. Every new leg and corner is checked against the other nets'
+copper, pads and keepouts on the exact shapes the exact engine uses, and
+against the board edge; a wire is changed only when all of its new copper
+is clear. Fixed wiring from the DSN is not part of the result and is never
+touched; it is checked against like any other copper.
+"""
+
+from __future__ import annotations
+
+from dataclasses import dataclass, field
+import itertools
+import math
+
+from rpmroute.board import build_board
+from rpmroute.board.search_tree import ShapeSearchTree, TreeShape
+from rpmroute.dsn.model import DsnBoard
+from rpmroute.geometry import IntBox, IntPoint, overlaps_2d, segment_box, segment_slab
+from rpmroute.geometry.polyline import corner_box
+from rpmroute.ses.model import RoutingResult
+
+from .exact_router import insert_static_copper
+from .pipeline import _dsn_units_per_um, _mm_to_board, _rule_clearance_dsn, _via_half_board
+
+#: how many points ahead a staircase collapse looks from each point
+LOOKAHEAD = 64
+#: a 45-degree leg at least this many track widths long: a shorter one is a
+#: kink beside its end's pad, where a refilled pour leaves a copper sliver
+MIN_DIAGONAL_WIDTHS = 2
+
+
+@dataclass
+class Shape:
+    """What a set of wires looks like: legs, right-angle corners, length."""
+
+    segments: int = 0
+    right_angles: int = 0
+    length_mm: dict[str, float] = field(default_factory=dict)
+
+    @property
+    def total_mm(self) -> float:
+        return sum(self.length_mm.values())
+
+
+@dataclass
+class SmoothReport:
+    before: Shape
+    after: Shape
+    wires_changed: int = 0
+    wires: int = 0
+    #: True when the finished check found more violations than before and
+    #: the smoothing was thrown away (never expected; a guard)
+    reverted: bool = False
+
+    def line(self) -> str:
+        b, a = self.before, self.after
+        if self.reverted:
+            return "smoothing reverted: it would have added a clearance violation"
+        return (
+            f"smoothed {self.wires_changed} of {self.wires} wires: segments {b.segments} -> "
+            f"{a.segments}, right-angle corners {b.right_angles} -> {a.right_angles}, "
+            f"length {b.total_mm:.1f} -> {a.total_mm:.1f} mm"
+        )
+
+    def table(self) -> list[str]:
+        rows = [f"  {'layer':10} {'before mm':>10} {'after mm':>10}"]
+        for layer in sorted(set(self.before.length_mm) | set(self.after.length_mm)):
+            rows.append(
+                f"  {layer:10} {self.before.length_mm.get(layer, 0.0):>10.1f} "
+                f"{self.after.length_mm.get(layer, 0.0):>10.1f}"
+            )
+        return rows
+
+
+def _shape_of(wires, mm_per_unit: float) -> Shape:
+    """``wires``: (layer name, points) pairs in board units."""
+    out = Shape()
+    for layer, pts in wires:
+        out.segments += max(len(pts) - 1, 0)
+        out.length_mm[layer] = out.length_mm.get(layer, 0.0) + mm_per_unit * sum(
+            math.hypot(q.x - p.x, q.y - p.y) for p, q in zip(pts, pts[1:], strict=False)
+        )
+        for a, b, c in zip(pts, pts[1:], pts[2:], strict=False):
+            if (b.x - a.x) * (c.x - b.x) + (b.y - a.y) * (c.y - b.y) == 0:
+                out.right_angles += 1
+    return out
+
+
+def _sign(v: int) -> int:
+    return (v > 0) - (v < 0)
+
+
+def _octilinear(a: IntPoint, b: IntPoint) -> bool:
+    dx, dy = b.x - a.x, b.y - a.y
+    return dx == 0 or dy == 0 or abs(dx) == abs(dy)
+
+
+def _candidates(a: IntPoint, b: IntPoint) -> list[list[IntPoint]]:
+    """The octilinear ways from ``a`` to ``b``: straight when the two lie on
+    an axis or a diagonal, else the 45-degree leg first or last."""
+    if _octilinear(a, b):
+        return [[a, b]]
+    dx, dy = b.x - a.x, b.y - a.y
+    m = min(abs(dx), abs(dy))
+    sx, sy = _sign(dx), _sign(dy)
+    return [
+        [a, IntPoint(a.x + sx * m, a.y + sy * m), b],
+        [a, IntPoint(b.x - sx * m, b.y - sy * m), b],
+    ]
+
+
+def _too_short(a: IntPoint, b: IntPoint, half: int) -> bool:
+    """A slanted leg shorter than MIN_DIAGONAL_WIDTHS track widths."""
+    if a.x == b.x or a.y == b.y:
+        return False
+    return (b.x - a.x) ** 2 + (b.y - a.y) ** 2 < (MIN_DIAGONAL_WIDTHS * 2 * half) ** 2
+
+
+def _dedupe(pts: list[IntPoint]) -> list[IntPoint]:
+    out: list[IntPoint] = []
+    for p in pts:
+        if not out or (out[-1].x, out[-1].y) != (p.x, p.y):
+            out.append(p)
+    return out
+
+
+def _merge_collinear(pts: list[IntPoint], keep: set[tuple[int, int]]) -> list[IntPoint]:
+    """Drop points where the wire runs straight on, except the ones in ``keep``."""
+    pts = _dedupe(pts)
+    out = pts[:1]
+    for i in range(1, len(pts) - 1):
+        a, b, c = out[-1], pts[i], pts[i + 1]
+        straight = (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x) == 0 and (
+            (b.x - a.x) * (c.x - b.x) + (b.y - a.y) * (c.y - b.y) > 0
+        )
+        if straight and (b.x, b.y) not in keep:
+            continue
+        out.append(b)
+    if len(pts) > 1:
+        out.append(pts[-1])
+    return out
+
+
+def _on_segment(p: IntPoint, a: IntPoint, b: IntPoint, reach: int) -> IntPoint | None:
+    """The point of axis leg ``a``-``b`` within ``reach`` of ``p`` (across the
+    leg), or None. Slanted legs only count ``p`` that lies exactly on them."""
+    if a.x == b.x:
+        lo, hi = sorted((a.y, b.y))
+        if abs(p.x - a.x) <= reach and lo <= p.y <= hi:
+            return IntPoint(a.x, p.y)
+        return None
+    if a.y == b.y:
+        lo, hi = sorted((a.x, b.x))
+        if abs(p.y - a.y) <= reach and lo <= p.x <= hi:
+            return IntPoint(p.x, a.y)
+        return None
+    cross = (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x)
+    within = min(a.x, b.x) <= p.x <= max(a.x, b.x) and min(a.y, b.y) <= p.y <= max(a.y, b.y)
+    return IntPoint(p.x, p.y) if cross == 0 and within else None
+
+
+class _Smoother:
+    def __init__(self, tree, outline, edge: int, clearance: int) -> None:
+        self.tree = tree
+        self.outline = outline
+        self.edge = edge
+        self.clearance = clearance
+
+    def _inside(self, box: IntBox) -> bool:
+        return self.outline is None or self.outline.box_clear(box, self.edge)
+
+    def leg_clear(self, a: IntPoint, b: IntPoint, half: int, net: int, layer: int) -> bool:
+        if a.x == b.x or a.y == b.y:
+            box = segment_box(a, b, half)
+            return self._inside(box) and not self.tree.clearance_conflict(
+                box, net, layer, self.clearance
+            )
+        copper = segment_slab(a, b, half)
+        if not self._inside(copper.bounding_box()):
+            return False
+        # Both ways round, as the finished check counts a pair: this leg's
+        # copper grown by the clearance against the other's copper, and the
+        # other's clearance region (a box grown square, so wider at its
+        # corners) against this leg's copper.
+        grown = segment_slab(a, b, half + self.clearance)
+        for shape in self.tree.overlapping(copper.bounding_box().offset(self.clearance)):
+            if shape.net_no == net or not shape.on_layer(layer):
+                continue
+            if shape.blocks not in ("all", "wires"):
+                continue
+            theirs = shape.exact if shape.exact is not None else shape.tile
+            if not shape.clearance:
+                if overlaps_2d(copper, theirs):
+                    return False
+            elif overlaps_2d(grown, theirs) or overlaps_2d(
+                shape.clearance_region(self.clearance), copper
+            ):
+                return False
+        return True
+
+    def corner_clear(self, c: IntPoint, half: int, net: int, layer: int) -> bool:
+        box = corner_box(c, half)
+        return self._inside(box) and not self.tree.clearance_conflict(
+            box, net, layer, self.clearance
+        )
+
+    def path_clear(self, path: list[IntPoint], half: int, net: int, layer: int) -> bool:
+        """New legs and new corners of ``path`` (its ends are kept points)."""
+        if any(_too_short(p, q, half) for p, q in zip(path, path[1:], strict=False)):
+            return False
+        return all(
+            self.leg_clear(p, q, half, net, layer) for p, q in zip(path, path[1:], strict=False)
+        ) and all(self.corner_clear(c, half, net, layer) for c in path[1:-1])
+
+    def collapse(self, pts: list[IntPoint], half: int, net: int, layer: int) -> list[IntPoint]:
+        """Step 1 on one section (both ends kept): from each point, jump to
+        the furthest later point an octilinear path reaches cleanly."""
+        out = [pts[0]]
+        i, n = 0, len(pts)
+        while i < n - 1:
+            jumped = False
+            for j in range(min(n - 1, i + LOOKAHEAD), i + 1, -1):
+                for path in _candidates(pts[i], pts[j]):
+                    if self.path_clear(path, half, net, layer):
+                        out.extend(path[1:])
+                        i, jumped = j, True
+                        break
+                if jumped:
+                    break
+            if not jumped:
+                out.append(pts[i + 1])
+                i += 1
+        return out
+
+    def miter(
+        self, pts: list[IntPoint], half: int, net: int, layer: int, keep: set[tuple[int, int]]
+    ) -> list[IntPoint]:
+        """Step 2: cut each right-angle corner between two axis legs to a
+        45-degree chamfer, as long a one as fits, at least a track width."""
+        pts = list(pts)
+        i = 1
+        while i < len(pts) - 1:
+            a, c, b = pts[i - 1], pts[i], pts[i + 1]
+            if (c.x, c.y) in keep or not (
+                (a.x == c.x or a.y == c.y) and (c.x == b.x or c.y == b.y)
+            ):
+                i += 1
+                continue
+            ux, uy = _sign(c.x - a.x), _sign(c.y - a.y)
+            vx, vy = _sign(b.x - c.x), _sign(b.y - c.y)
+            if ux * vx + uy * vy != 0:
+                i += 1
+                continue
+            len_in = abs(c.x - a.x) + abs(c.y - a.y)
+            len_out = abs(b.x - c.x) + abs(b.y - c.y)
+            # leave half of a leg for the corner at its other end, unless that
+            # end stays where it is anyway
+            cap_in = len_in if (a.x, a.y) in keep or i == 1 else len_in // 2
+            cap_out = len_out if (b.x, b.y) in keep or i == len(pts) - 2 else len_out // 2
+            d = min(cap_in, cap_out)
+            done = False
+            # the chamfer's leg is d * sqrt(2) long
+            while d * d * 2 >= (MIN_DIAGONAL_WIDTHS * 2 * half) ** 2:
+                p = IntPoint(c.x - ux * d, c.y - uy * d)
+                q = IntPoint(c.x + vx * d, c.y + vy * d)
+                corners = [x for x in (p, q) if (x.x, x.y) not in ((a.x, a.y), (b.x, b.y))]
+                if self.leg_clear(p, q, half, net, layer) and all(
+                    self.corner_clear(x, half, net, layer) for x in corners
+                ):
+                    pts[i : i + 1] = [p, q]
+                    pts = _dedupe(pts)
+                    done = True
+                    break
+                d = d * 3 // 4 if d * 3 // 4 < d else d - 1
+            i += 2 if done else 1
+        return pts
+
+
+def smooth(
+    dsn: DsnBoard, result: RoutingResult, *, edge_clearance_mm: float | None = None
+) -> SmoothReport:
+    """Smooth ``result``'s wires in place; return what changed."""
+    board = build_board(dsn)
+    scale = max(dsn.resolution.value, 1)
+    clearance = round(_rule_clearance_dsn(dsn) * scale)
+    edge = _mm_to_board(dsn, scale, edge_clearance_mm) or 0
+    mm_per_unit = 1 / (_dsn_units_per_um(dsn) * 1000 * scale)
+    signal_layers = [i for i, layer in enumerate(dsn.layers) if layer.is_signal]
+    layer_index = {layer.name: i for i, layer in enumerate(dsn.layers)}
+    via_layers = frozenset(signal_layers)
+    net_numbers = {n.name: i + 1 for i, n in enumerate(dsn.nets)}
+    via_half = _via_half_board(dsn, scale)
+
+    tree = ShapeSearchTree()
+    owner = itertools.count(1)
+    insert_static_copper(tree, board, signal_layers, owner)
+
+    def to_points(wire) -> list[IntPoint]:
+        c = wire.coords
+        return [IntPoint(round(c[i] * scale), round(c[i + 1] * scale)) for i in range(0, len(c) - 1, 2)]
+
+    # own-net pads per (net, layer): legs across one the wire does not end on stay
+    pads: dict[tuple[int, int], list[IntBox]] = {}
+    for pin in board.get_pins():
+        if pin.shape is None or not pin.net_nos:
+            continue
+        box = pin.shape.bounding_box()
+        for layer in pin.layers:
+            pads.setdefault((pin.net_nos[0], layer), []).append(box)
+
+    # every routed wire and via into the tree, each wire under owners of its own
+    wires: list[tuple[int, object, int, int, list[IntPoint], list[int]]] = []
+    for net in result.nets:
+        net_no = net_numbers.get(net.name)
+        if net_no is None:
+            continue
+        for wire in net.wires:
+            layer = layer_index.get(wire.layer)
+            if layer is None or layer not in signal_layers or wire.fixed:
+                continue
+            half = max(round(wire.width * scale / 2), 1)
+            pts = to_points(wire)
+            wires.append((net_no, wire, layer, half, pts, _insert(tree, owner, pts, half, net_no, layer)))
+        for via in net.vias:
+            vh = via_half or max(round(max((w.width for w in net.wires), default=0) * scale / 2), 1)
+            x, y = round(via.x * scale), round(via.y * scale)
+            tree.insert(TreeShape(
+                next(owner), net_no, via_layers, IntBox(x - vh, y - vh, x + vh, y + vh), routed=True,
+            ))
+
+    before_pairs = len(tree.violation_pairs(clearance))
+    before = _shape_of(
+        [(dsn.layers[w[2]].name, w[4]) for w in wires], mm_per_unit
+    )
+
+    # the points of each net another of its wires or a via meets
+    joints: dict[int, list[IntPoint]] = {}
+    for net in result.nets:
+        net_no = net_numbers.get(net.name)
+        if net_no is None:
+            continue
+        for via in net.vias:
+            joints.setdefault(net_no, []).append(IntPoint(round(via.x * scale), round(via.y * scale)))
+    for net_no, _wire, _layer, _half, pts, _owners in wires:
+        joints.setdefault(net_no, []).extend((pts[0], pts[-1]))
+
+    pins_of: dict[int, list] = {}
+    for pin in board.get_pins():
+        if pin.shape is not None and pin.net_nos:
+            pins_of.setdefault(pin.net_nos[0], []).append(pin)
+    vias_of = {
+        net_numbers[net.name]: [IntPoint(round(v.x * scale), round(v.y * scale)) for v in net.vias]
+        for net in result.nets
+        if net.name in net_numbers
+    }
+    by_net: dict[int, list[int]] = {}
+    for k, w in enumerate(wires):
+        by_net.setdefault(w[0], []).append(k)
+
+    smoother = _Smoother(tree, board.outline, edge, clearance)
+    changed = 0
+    originals = []
+    for net_no, ks in by_net.items():
+        groups_before = _pad_groups(
+            [wires[k] for k in ks], pins_of.get(net_no, []), vias_of.get(net_no, [])
+        )
+        undo = []
+        for k in ks:
+            _, wire, layer, half, pts, owners = wires[k]
+            if len(pts) < 3:
+                continue
+            keep_pts, keep = _kept_points(
+                pts, joints.get(net_no, []), half, pads.get((net_no, layer), [])
+            )
+            new = _merge_collinear(keep_pts, keep)
+            out: list[IntPoint] = [new[0]]
+            start = 0
+            for i in range(1, len(new)):
+                if (new[i].x, new[i].y) in keep or i == len(new) - 1:
+                    section = smoother.collapse(new[start : i + 1], half, net_no, layer)
+                    out.extend(section[1:])
+                    start = i
+            out = smoother.miter(_merge_collinear(out, keep), half, net_no, layer, keep)
+            out = _merge_collinear(out, keep)
+            if [(p.x, p.y) for p in out] == [(p.x, p.y) for p in pts]:
+                continue
+            # the wire's own old copper is the same net and never in the way,
+            # so it can go once the new copper is in
+            for oid in owners:
+                tree.remove_owner(oid)
+            new_owners = _insert(tree, owner, out, half, net_no, layer)
+            undo.append((k, wires[k], list(wire.coords)))
+            wire.coords = [v / scale for p in out for v in (p.x, p.y)]
+            wires[k] = (net_no, wire, layer, half, out, new_owners)
+        if not undo:
+            continue
+        groups_after = _pad_groups(
+            [wires[k] for k in ks], pins_of.get(net_no, []), vias_of.get(net_no, [])
+        )
+        if groups_after != groups_before:
+            # a pad lost (or gained) its way to the rest of the net: keep the
+            # net as it was routed
+            for k, old, coords in reversed(undo):
+                for oid in wires[k][5]:
+                    tree.remove_owner(oid)
+                old[1].coords = coords
+                wires[k] = (*old[:5], _insert(tree, owner, old[4], old[3], net_no, old[2]))
+            continue
+        originals.extend((old[1], coords) for _k, old, coords in undo)
+        changed += len(undo)
+
+    report = SmoothReport(
+        before=before,
+        after=_shape_of([(dsn.layers[w[2]].name, w[4]) for w in wires], mm_per_unit),
+        wires_changed=changed,
+        wires=len(wires),
+    )
+    if changed and len(tree.violation_pairs(clearance)) > before_pairs:
+        for wire, coords in originals:
+            wire.coords = coords
+        report.after, report.wires_changed, report.reverted = before, 0, True
+    return report
+
+
+def _insert(tree, owner, pts, half, net_no, layer) -> list[int]:
+    """A wire's copper into ``tree`` as the exact engine models it: legs (on
+    their exact slab when slanted) and a square at each inner corner."""
+    on = frozenset({layer})
+    owners = []
+    for a, b in zip(pts, pts[1:], strict=False):
+        oid = next(owner)
+        if a.x == b.x or a.y == b.y:
+            tree.insert(TreeShape(oid, net_no, on, segment_box(a, b, half), routed=True))
+        else:
+            slab = segment_slab(a, b, half)
+            tree.insert(TreeShape(
+                oid, net_no, on, slab.bounding_box(), routed=True, exact=slab, seg=("slab", a, b, half),
+            ))
+        owners.append(oid)
+    for c in pts[1:-1]:
+        oid = next(owner)
+        tree.insert(TreeShape(oid, net_no, on, corner_box(c, half), routed=True))
+        owners.append(oid)
+    return owners
+
+
+def _kept_points(
+    pts: list[IntPoint], joints: list[IntPoint], half: int, own_pads: list[IntBox]
+) -> tuple[list[IntPoint], set[tuple[int, int]]]:
+    """The wire with a point added wherever another wire of its net or a via
+    meets it, and the set of points that must stay: those, its ends, and the
+    ends of any leg across an own-net pad it does not end on."""
+    keep = {(pts[0].x, pts[0].y), (pts[-1].x, pts[-1].y)}
+    out = [pts[0]]
+    for a, b in zip(pts, pts[1:], strict=False):
+        hits = []
+        for j in joints:
+            p = _on_segment(j, a, b, half)
+            if p is not None:
+                hits.append(p)
+                keep.add((p.x, p.y))
+        hits.sort(key=lambda p: abs(p.x - a.x) + abs(p.y - a.y))
+        out.extend(h for h in hits if (h.x, h.y) not in ((a.x, a.y), (b.x, b.y)))
+        out.append(b)
+    end_pads = [box for box in own_pads if _in(pts[0], box) or _in(pts[-1], box)]
+    for box in own_pads:
+        if any(box is e for e in end_pads):
+            continue
+        for a, b in zip(out, out[1:], strict=False):
+            if segment_box(a, b, 0).overlaps(box):
+                keep.add((a.x, a.y))
+                keep.add((b.x, b.y))
+    return _dedupe(out), keep
+
+
+def _near(p: IntPoint, pts: list[IntPoint], reach: int) -> bool:
+    """Whether ``p`` lies on the copper of the wire through ``pts`` (``reach``
+    its half width), squared at the corners as the copper is modelled."""
+    for a, b in zip(pts, pts[1:], strict=False):
+        dx, dy = b.x - a.x, b.y - a.y
+        n2 = dx * dx + dy * dy
+        t = 0.0 if n2 == 0 else max(0.0, min(1.0, ((p.x - a.x) * dx + (p.y - a.y) * dy) / n2))
+        cx, cy = a.x + t * dx, a.y + t * dy
+        if math.hypot(p.x - cx, p.y - cy) <= reach + 1:
+            return True
+    return False
+
+
+def _pad_groups(wires, pins, vias) -> set[frozenset[int]]:
+    """Which of a net's pads its copper joins, as groups of pad indices: a
+    wire's end on a pad, on another wire, or on a via; a via on a pad."""
+    parent = list(range(len(pins) + len(wires) + len(vias)))
+
+    def find(x: int) -> int:
+        while parent[x] != x:
+            parent[x] = parent[parent[x]]
+            x = parent[x]
+        return x
+
+    def join(x: int, y: int) -> None:
+        parent[find(x)] = find(y)
+
+    boxes = [p.shape.bounding_box() for p in pins]
+    w0, v0 = len(pins), len(pins) + len(wires)
+    for i, (_n, _w, layer, half, pts, _o) in enumerate(wires):
+        for end in (pts[0], pts[-1]):
+            for j, pin in enumerate(pins):
+                if layer in pin.layers and _in(end, boxes[j]):
+                    join(w0 + i, j)
+            for k, (_n2, _w2, layer2, half2, pts2, _o2) in enumerate(wires):
+                if k != i and layer2 == layer and _near(end, pts2, half2):
+                    join(w0 + i, w0 + k)
+            for v, loc in enumerate(vias):
+                if (end.x, end.y) == (loc.x, loc.y) or _near(loc, pts, half):
+                    join(w0 + i, v0 + v)
+    for v, loc in enumerate(vias):
+        for j in range(len(pins)):
+            if _in(loc, boxes[j]):
+                join(v0 + v, j)
+    groups: dict[int, set[int]] = {}
+    for j in range(len(pins)):
+        groups.setdefault(find(j), set()).add(j)
+    return {frozenset(g) for g in groups.values()}
+
+
+def _in(p: IntPoint, box: IntBox) -> bool:
+    return box.ll.x <= p.x <= box.ur.x and box.ll.y <= p.y <= box.ur.y

src/rpmroute/route/verify.py

@@ -0,0 +1,151 @@
+"""Check routed copper that no engine has checked.
+
+The exact engine verifies every connection against exact pad and copper
+shapes before it accepts it. The grid and room engines do not: they route on
+approximations, and their output can short or crowd another net with nothing
+in their report to say so. :func:`verify_result` puts a finished
+:class:`RoutingResult` through the same exact geometry the exact engine uses
+(its pads, fixed copper and keepouts, wires as boxes or slanted slabs, vias as
+their pads) and lists what it finds.
+
+A violation is a pair of different-net coppers on a shared layer, at least one
+of them routed, closer than the board's clearance rule. It is a short when the
+coppers themselves overlap (or routed copper sits inside a keepout), else a
+clearance violation. Pairs are counted per routed segment or via, as KiCad's
+DRC counts per item pair; pads already too close to each other in the design
+are not the router's and are not counted.
+"""
+
+from __future__ import annotations
+
+from dataclasses import dataclass, field
+import itertools
+
+from rpmroute.board import build_board
+from rpmroute.board.search_tree import ShapeSearchTree, TreeShape
+from rpmroute.dsn.model import DsnBoard
+from rpmroute.geometry import IntBox, IntPoint, segment_box, segment_slab
+from rpmroute.geometry.polyline import corner_box
+from rpmroute.ses.model import RoutingResult
+
+from .exact_router import insert_static_copper
+from .pipeline import _dsn_units_per_um, _rule_clearance_dsn, _via_half_board
+
+# examples kept per kind; the counts are always complete
+MAX_EXAMPLES = 5
+
+
+@dataclass
+class Violation:
+    """One offending pair: the routed copper's net, what it came too close
+    to, the layer, and roughly where (mm, DSN coordinates)."""
+
+    net: str
+    other: str
+    layer: str
+    x_mm: float
+    y_mm: float
+
+    def __str__(self) -> str:
+        return f"{self.net} x {self.other} on {self.layer} at ({self.x_mm:.2f}, {self.y_mm:.2f}) mm"
+
+
+@dataclass
+class VerifyReport:
+    shorts: int = 0
+    clearance: int = 0
+    short_examples: list[Violation] = field(default_factory=list)
+    clearance_examples: list[Violation] = field(default_factory=list)
+
+    @property
+    def clean(self) -> bool:
+        return not (self.shorts or self.clearance)
+
+
+def verify_result(dsn: DsnBoard, result: RoutingResult) -> VerifyReport:
+    """Check ``result``'s copper against ``dsn``'s pads, keepouts and each
+    other, with the board's clearance rule."""
+    board = build_board(dsn)
+    scale = max(dsn.resolution.value, 1)
+    clearance = round(_rule_clearance_dsn(dsn) * scale)
+    signal_layers = [i for i, layer in enumerate(dsn.layers) if layer.is_signal]
+    layer_index = {layer.name: i for i, layer in enumerate(dsn.layers)}
+    via_layers = frozenset(signal_layers)
+    net_numbers = {n.name: i + 1 for i, n in enumerate(dsn.nets)}
+    names = {number: name for name, number in net_numbers.items()}
+
+    tree = ShapeSearchTree()
+    owner = itertools.count(1)
+    insert_static_copper(tree, board, signal_layers, owner)
+    static_names: dict[int, str] = {}
+    for shape in tree.all_shapes():
+        static_names[shape.owner] = "keepout" if shape.net_no == -1 else f"pad of {names.get(shape.net_no, '?')}"
+
+    via_default = _via_half_board(dsn, scale)
+    for net in result.nets:
+        net_no = net_numbers.get(net.name)
+        if net_no is None:
+            continue
+        for wire in net.wires:
+            layer = layer_index.get(wire.layer)
+            if layer is None or layer not in signal_layers:
+                continue
+            half = max(round(wire.width * scale / 2), 1)
+            pts = [
+                IntPoint(round(wire.coords[i] * scale), round(wire.coords[i + 1] * scale))
+                for i in range(0, len(wire.coords) - 1, 2)
+            ]
+            on = frozenset({layer})
+            for a, b in zip(pts, pts[1:], strict=False):
+                oid = next(owner)
+                if a.x == b.x or a.y == b.y:
+                    tree.insert(TreeShape(oid, net_no, on, segment_box(a, b, half), routed=True))
+                else:  # a 45-degree or slanted segment, on its exact copper
+                    slab = segment_slab(a, b, half)
+                    tree.insert(TreeShape(
+                        oid, net_no, on, slab.bounding_box(), routed=True,
+                        exact=slab, seg=("slab", a, b, half),
+                    ))
+                # the round end where it meets the next segment, with this one
+                tree.insert(TreeShape(oid, net_no, on, corner_box(b, half), routed=True))
+        for via in net.vias:
+            half = via_default or max(round(_wire_width(net) * scale / 2), 1)
+            x, y = round(via.x * scale), round(via.y * scale)
+            tree.insert(TreeShape(
+                next(owner), net_no, via_layers, IntBox(x - half, y - half, x + half, y + half), routed=True,
+            ))
+
+    mm_per_unit = 1 / (_dsn_units_per_um(dsn) * 1000 * scale)
+    # one entry per pair of items, however many of their tiles meet; a short
+    # if any of them overlap
+    by_pair: dict[tuple[int, int], tuple[TreeShape, TreeShape, bool]] = {}
+    for shape, other, touching in tree.violation_pairs(clearance):
+        key = (min(shape.owner, other.owner), max(shape.owner, other.owner))
+        seen = by_pair.get(key)
+        if seen is None or (touching and not seen[2]):
+            by_pair[key] = (shape, other, touching)
+
+    report = VerifyReport()
+    for shape, other, touching in by_pair.values():
+        layer = min(shape.layers & other.layers)
+        box = shape.tile.intersection(other.tile.offset(clearance))
+        if box.is_empty():
+            box = shape.tile
+        what = names.get(other.net_no, "?") if other.routed else static_names.get(other.owner, "?")
+        found = Violation(
+            names.get(shape.net_no, "?"), what, dsn.layers[layer].name,
+            (box.ll.x + box.ur.x) / 2 * mm_per_unit, (box.ll.y + box.ur.y) / 2 * mm_per_unit,
+        )
+        if touching:
+            report.shorts += 1
+            if len(report.short_examples) < MAX_EXAMPLES:
+                report.short_examples.append(found)
+        else:
+            report.clearance += 1
+            if len(report.clearance_examples) < MAX_EXAMPLES:
+                report.clearance_examples.append(found)
+    return report
+
+
+def _wire_width(net) -> float:
+    return max((w.width for w in net.wires), default=0.0)

src/rpmroute/route/vias.py

@@ -0,0 +1,128 @@
+"""Via reduction: a last stage that routes each net again with vias made dear.
+
+The main search prices a layer change at a few millimetres of track, which
+is right while the board is crowded and wrong once it is routed: a net that
+hopped layers to slip past a route can often stay on one layer around it.
+So each net that has vias is ripped and routed again on its own, everything
+else held as fixed copper, with the via cost raised; the new copper is kept
+only if the net loses no connection and ends with fewer vias.
+
+It reuses the window stage's board: the net's own items and copper, and of
+everything else only what lies near the box the net is routed in. The nets
+with the most vias go first, and no new net starts once ``budget_s`` is
+spent.
+"""
+
+from __future__ import annotations
+
+import time
+from typing import Any
+
+from rpmroute.board import build_board
+from rpmroute.dsn import DsnBoard
+from rpmroute.geometry import IntBox
+
+from .exact_router import route_board_exact
+from .grid_router import RouteResult
+from .window import Copper, _inside, _item_box, _open, _window_board
+
+
+def _net_box(copper: Copper, pins: list, grow: int) -> IntBox | None:
+    wires, vias = copper
+    points = [p for _layer, path in wires for p in path] + list(vias) + pins
+    if not points:
+        return None
+    xs, ys = [p.x for p in points], [p.y for p in points]
+    return IntBox(min(xs) - grow, min(ys) - grow, max(xs) + grow, max(ys) + grow)
+
+
+def reduce_vias(
+    dsn: DsnBoard,
+    result: RouteResult,
+    route_args: dict[str, Any],
+    *,
+    resolution: int,
+    margin: int,
+    via_half: int,
+    via_drill: int,
+    via_name: str,
+    via_cost_factor: float = 8.0,
+    budget_s: float | None = None,
+) -> RouteResult:
+    """Route each net with vias again with vias ``via_cost_factor`` times dearer;
+    keep a net's new copper only when it fails nothing new and has fewer vias.
+
+    ``route_args`` are the exact engine's settings for the whole board.
+    ``margin`` grows the box around the net's pins and copper that it is
+    routed in, so it may go round what it used to hop over."""
+    started = time.monotonic()
+    copper: dict[int, Copper] = {
+        net: (list(result.wires.get(net, [])), list(result.vias.get(net, [])))
+        for net in set(result.wires) | set(result.vias)
+    }
+    todo = sorted((n for n, c in copper.items() if c[1]), key=lambda n: -len(set(copper[n][1])))
+    if not todo:
+        return result
+    default_half = result.half_width
+    half = dict(result.net_half)
+    failed = list(result.failed)
+    base = build_board(dsn)
+    base_items = [(item, _item_box(item)) for item in base.get_items()]
+    layers = route_args.get("layers") or [
+        i for i, layer in enumerate(base.layer_structure.arr) if layer.is_signal
+    ]
+    pins_of: dict[int, list] = {}
+    for pin in base.get_pins():
+        for net in pin.net_nos:
+            pins_of.setdefault(net, []).append(pin.location)
+    context = 2 * (route_args["trace_width"] + route_args["clearance"]) + 2 * via_half + (
+        route_args.get("edge_clearance") or 0
+    )
+    args = dict(route_args)
+    args["via_cost"] = float(route_args.get("via_cost", 10.0)) * via_cost_factor
+
+    changed = False
+    for net in todo:
+        if budget_s is not None and time.monotonic() - started >= budget_s:
+            break
+        old_vias = len(set(copper[net][1]))
+        window = _net_box(copper[net], pins_of.get(net, []), margin)
+        if window is None:
+            continue
+        before = _open(f for f in failed if f[0] == net)
+        view = IntBox(window.ll.x - context, window.ll.y - context,
+                      window.ur.x + context, window.ur.y + context)
+        keep = set(copper) - {net}
+        board = _window_board(base, base_items, view, {net}, copper, keep, half,
+                              default_half, via_half, via_drill, layers, via_name)
+        sub = route_board_exact(
+            board, **args, resolution=resolution, only_nets=frozenset({net}), bounds=window,
+        ).result
+        after = _open(f for f in sub.failed if f[0] == net)
+        new = (sub.wires.get(net, []), sub.vias.get(net, []))
+        if len(after) > len(before) or len(set(new[1])) >= old_vias:
+            continue
+        # the board left out what lies away from the box, so copper reaching
+        # out of it was never checked against that
+        if (new[0] or new[1]) and not _inside(new, window):
+            continue
+        copper[net] = (list(new[0]), list(new[1]))
+        half.pop(net, None)
+        if net in sub.net_half:
+            half[net] = sub.net_half[net]
+        failed = [f for f in failed if f[0] != net] + [f for f in sub.failed if f[0] == net]
+        changed = True
+
+    if not changed:
+        return result
+    out = RouteResult(default_half)
+    for net, (wires, vias) in copper.items():
+        for layer, path in wires:
+            out.add_wire(net, layer, path)
+        for location in dict.fromkeys(vias):
+            out.add_via(net, location)
+    out.failed = failed
+    out.unrouted = len(_open(failed))
+    out.net_half = half
+    out.narrowed = list(result.narrowed)
+    return out

tests/route/test_reduce_vias.py

@@ -0,0 +1,123 @@
+"""Via reduction: each net with vias is routed again with vias made dear,
+kept only when it fails nothing new and has fewer vias."""
+
+from __future__ import annotations
+
+from rpmroute.board import build_board
+from rpmroute.dsn import parse_dsn
+from rpmroute.geometry import IntPoint
+from rpmroute.route.grid_router import RouteResult
+from rpmroute.route.pipeline import (
+    _rule_clearance_dsn,
+    _rule_width_dsn,
+    _via_half_board,
+    route_dsn_board_exact,
+)
+from rpmroute.route.vias import reduce_vias
+
+VIA = "Via[0-1]_600:300_um"
+
+
+def _board(second_on_bottom: bool = False) -> str:
+    """Two pads 14 mm apart on an empty two-layer board; the second on the
+    bottom layer when ``second_on_bottom``."""
+    p2_stack = "Bot_Pad" if second_on_bottom else "Top_Pad"
+    return f"""(pcb "vias.dsn"
+  (parser (string_quote ") (space_in_quoted_tokens on) (host_cad "t") (host_version "1"))
+  (resolution um 10)
+  (unit um)
+  (structure
+    (layer F.Cu (type signal) (property (index 0)))
+    (layer B.Cu (type signal) (property (index 1)))
+    (boundary (path pcb 0  0 0  20000 0  20000 -10000  0 -10000  0 0))
+    (via "{VIA}")
+    (rule (width 200) (clearance 200))
+  )
+  (library
+    (padstack Top_Pad (shape (rect F.Cu -300 -300 300 300)) (attach off))
+    (padstack Bot_Pad (shape (rect B.Cu -300 -300 300 300)) (attach off))
+    (padstack "{VIA}" (shape (circle F.Cu 600)) (shape (circle B.Cu 600)) (attach off))
+    (image TOP (pin Top_Pad 1 0 0))
+    (image SECOND (pin {p2_stack} 1 0 0))
+  )
+  (placement
+    (component TOP (place P1 3000 -5000 front 0))
+    (component SECOND (place P2 17000 -5000 front 0))
+  )
+  (network
+    (net N (pins P1-1 P2-1))
+    (class default (rule (width 200) (clearance 200)))
+  )
+  (wiring)
+)
+"""
+
+
+def _route_args(dsn) -> dict:
+    scale = max(dsn.resolution.value, 1)
+    return {
+        "heuristic_weight": 1.0,
+        "via_half": _via_half_board(dsn, scale),
+        "edge_clearance": None,
+        "trace_width": round(_rule_width_dsn(dsn) * scale),
+        "clearance": round(_rule_clearance_dsn(dsn) * scale),
+        "layers": None,
+        "max_passes": 10,
+        "rip_up": True,
+        "shove": False,
+        "diagonal": False,
+        "rollback": True,
+        "tree_nets": True,
+        "net_widths": {},
+        "via_drill": None,
+        "hole_to_hole": 0,
+        "via_cost": 10.0,
+    }
+
+
+def _reduce(text: str, result: RouteResult) -> RouteResult:
+    dsn = parse_dsn(text)
+    args = _route_args(dsn)
+    return reduce_vias(
+        dsn, result, args, resolution=1, margin=20000,
+        via_half=args["via_half"], via_drill=2 * args["via_half"], via_name=VIA,
+    )
+
+
+def _pins(text: str) -> tuple[IntPoint, IntPoint]:
+    pins = {p.component_ref: p.location for p in build_board(parse_dsn(text)).get_pins()}
+    return pins["P1"], pins["P2"]
+
+
+def test_a_needless_via_pair_is_routed_out():
+    text = _board()
+    a, b = _pins(text)
+    # a detour: down to the bottom layer and back up, for no reason
+    v1, v2 = IntPoint(a.x + 40000, a.y), IntPoint(b.x - 40000, b.y)
+    detour = RouteResult(1000)
+    detour.add_wire(1, 0, [a, v1])
+    detour.add_via(1, v1)
+    detour.add_wire(1, 1, [v1, v2])
+    detour.add_via(1, v2)
+    detour.add_wire(1, 0, [v2, b])
+    out = _reduce(text, detour)
+    assert out.failed == []
+    assert sum(len(v) for v in out.vias.values()) == 0
+    assert out.wires.get(1)
+
+
+def test_a_needed_via_stays():
+    text = _board(second_on_bottom=True)
+    exact, _scale, _layers = route_dsn_board_exact(parse_dsn(text), resolution=1)
+    routed = exact.result
+    assert routed.failed == []
+    vias_before = sum(len(set(v)) for v in routed.vias.values())
+    assert vias_before >= 1
+    out = _reduce(text, routed)
+    assert out.failed == []
+    assert sum(len(set(v)) for v in out.vias.values()) == vias_before
+
+
+def test_the_flag_runs_the_stage_end_to_end():
+    exact, _scale, _layers = route_dsn_board_exact(parse_dsn(_board()), resolution=1, reduce_vias=True)
+    assert exact.result.failed == []

tests/route/test_smooth.py

@@ -0,0 +1,162 @@
+"""Smoothing: staircases become octilinear runs, corners are chamfered, and
+nothing it keeps (ends, vias, joints, pads it crosses) moves."""
+
+from __future__ import annotations
+
+from rpmroute.dsn import parse_dsn
+from rpmroute.route.smooth import smooth
+from rpmroute.route.verify import verify_result
+from rpmroute.ses.model import RoutedVia, RoutedWire, RoutingResult
+
+VIA = "Via[0-1]_600:300_um"
+
+
+def _board(extra_pads: str = "", extra_places: str = "", nets: str = "") -> str:
+    """A 30 x 30 mm two-layer board, units um, 0.2 mm track and clearance.
+    A1 at (2, -2) mm and A2 at (22, -22) mm are net SIG."""
+    return f"""(pcb "smooth.dsn"
+  (parser (string_quote ") (space_in_quoted_tokens on) (host_cad "t") (host_version "1"))
+  (resolution um 10)
+  (unit um)
+  (structure
+    (layer F.Cu (type signal) (property (index 0)))
+    (layer B.Cu (type signal) (property (index 1)))
+    (boundary (path pcb 0  0 0  30000 0  30000 -30000  0 -30000  0 0))
+    (via "{VIA}")
+    (rule (width 200) (clearance 200))
+  )
+  (library
+    (padstack P (shape (rect F.Cu -300 -300 300 300)) (attach off))
+    (padstack "{VIA}" (shape (circle F.Cu 600)) (shape (circle B.Cu 600)) (attach off))
+    (image PAD (pin P 1 0 0))
+    {extra_pads}
+  )
+  (placement
+    (component PAD (place A1 2000 -2000 front 0) (place A2 22000 -22000 front 0) {extra_places})
+  )
+  (network
+    (net SIG (pins A1-1 A2-1))
+    {nets}
+    (class default (rule (width 200) (clearance 200)))
+  )
+  (wiring)
+)
+"""
+
+
+def _staircase(a, b, step):
+    """Points from ``a`` to ``b`` (DSN um) in alternating x and y steps."""
+    (x, y), (bx, by) = a, b
+    pts = [(x, y)]
+    sx = step if bx > x else -step
+    sy = step if by > y else -step
+    while (x, y) != (bx, by):
+        if x != bx:
+            x = x + sx if abs(bx - x) > step else bx
+            pts.append((x, y))
+        if y != by:
+            y = y + sy if abs(by - y) > step else by
+            pts.append((x, y))
+    return pts
+
+
+def _wire(pts, layer="F.Cu", fixed=False):
+    return RoutedWire(layer=layer, width=200, coords=[v for p in pts for v in p], fixed=fixed)
+
+
+def _points(wire):
+    c = wire.coords
+    return [(round(c[i]), round(c[i + 1])) for i in range(0, len(c), 2)]
+
+
+def _result(*wires, vias=(), net="SIG"):
+    result = RoutingResult()
+    for w in wires:
+        result.add_wire(net, w)
+    for x, y in vias:
+        result.net(net, create=True).vias.append(RoutedVia(padstack=VIA, x=x, y=y))
+    return result
+
+
+def test_a_staircase_becomes_one_diagonal():
+    dsn = parse_dsn(_board())
+    stair = _staircase((2000, -2000), (22000, -22000), 1000)
+    result = _result(_wire(stair))
+    report = smooth(dsn, result)
+    pts = _points(result.nets[0].wires[0])
+    assert pts == [(2000, -2000), (22000, -22000)]
+    assert report.wires_changed == 1 and report.after.right_angles == 0
+    assert report.after.total_mm < report.before.total_mm
+    assert verify_result(dsn, result).clean
+
+
+def test_a_pad_in_the_way_is_gone_round():
+    # another net's pad sits on the diagonal shortcut of an L-shaped route
+    dsn = parse_dsn(_board(extra_places="(place B1 12000 -12000 front 0) (place B2 28000 -28000 front 0)",
+                           nets="(net OTHER (pins B1-1 B2-1))"))
+    result = _result(_wire([(2000, -2000), (22000, -2000), (22000, -22000)]))
+    report = smooth(dsn, result)
+    pts = _points(result.nets[0].wires[0])
+    assert pts[0] == (2000, -2000) and pts[-1] == (22000, -22000)
+    assert report.wires_changed == 1  # the corner is chamfered, short of the pad
+    assert verify_result(dsn, result).clean
+
+
+def test_a_joint_and_a_via_stay():
+    dsn = parse_dsn(_board(extra_places="(place A3 22000 -2000 front 0)",
+                           nets="").replace("(pins A1-1 A2-1)", "(pins A1-1 A2-1 A3-1)"))
+    stair = _staircase((2000, -2000), (22000, -22000), 1000)
+    joint = stair[11]  # A3's leg ends here, on the staircase
+    leg = _wire([(22000, -2000), (joint[0], -2000), joint])
+    via = stair[25]
+    result = _result(_wire(stair), leg, vias=[via])
+    smooth(dsn, result)
+    pts = _points(result.nets[0].wires[0])
+    assert joint in pts and via in pts
+    assert pts[0] == (2000, -2000) and pts[-1] == (22000, -22000)
+    assert verify_result(dsn, result).clean
+
+
+def test_the_board_edge_is_kept_clear_of():
+    # a staircase hugging the top edge: a chamfer may not push copper over it
+    dsn = parse_dsn(_board(extra_places="(place A3 22000 -500 front 0)").replace(
+        "(pins A1-1 A2-1)", "(pins A1-1 A3-1)"))
+    wire = _wire([(2000, -2000), (2000, -500), (22000, -500)])
+    result = _result(wire)
+    smooth(dsn, result, edge_clearance_mm=0.3)
+    for _x, y in _points(result.nets[0].wires[0]):
+        assert -y >= 300 + 100  # half width + edge clearance from y = 0
+
+
+def test_fixed_wiring_is_left_alone():
+    dsn = parse_dsn(_board())
+    stair = _staircase((2000, -2000), (22000, -22000), 1000)
+    result = _result(_wire(stair, fixed=True))
+    report = smooth(dsn, result)
+    assert _points(result.nets[0].wires[0]) == stair
+    assert report.wires == 0
+
+
+def test_a_detour_with_nothing_in_its_way_is_straightened():
+    dsn = parse_dsn(_board(extra_places="(place A3 22000 -2000 front 0)").replace(
+        "(pins A1-1 A2-1)", "(pins A3-1 A2-1)"))
+    # a U out to x = 12 mm and back, with nothing between its ends
+    result = _result(_wire([(22000, -2000), (12000, -2000), (12000, -22000), (22000, -22000)]))
+    report = smooth(dsn, result)
+    assert _points(result.nets[0].wires[0]) == [(22000, -2000), (22000, -22000)]
+    assert (report.before.right_angles, report.after.right_angles) == (2, 0)
+    assert verify_result(dsn, result).clean
+
+
+def test_a_jog_too_small_for_a_long_diagonal_stays_square():
+    # a 0.1 mm jog halfway: its 45-degree leg would be shorter than two track
+    # widths, a kink beside the copper that leaves pour slivers
+    dsn = parse_dsn(_board(extra_places="(place A3 2100 -22000 front 0)").replace(
+        "(pins A1-1 A2-1)", "(pins A1-1 A3-1)"))
+    wire = [(2000, -2000), (2000, -12000), (2100, -12000), (2100, -22000)]
+    result = _result(_wire(wire))
+    smooth(dsn, result)
+    pts = _points(result.nets[0].wires[0])
+    for a, b in zip(pts, pts[1:], strict=False):
+        if a[0] != b[0] and a[1] != b[1]:
+            assert (b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2 >= (2 * 200) ** 2

tests/route/test_verify_output.py

@@ -0,0 +1,42 @@
+"""verify_result: copper no engine checked is checked on exact shapes."""
+
+from pathlib import Path
+
+from rpmroute.dsn import parse_dsn
+from rpmroute.route.verify import verify_result
+from rpmroute.ses.model import RoutedWire, RoutingResult
+
+FIXTURE = Path(__file__).parents[1] / "dsn" / "fixtures" / "crossing_2net.dsn"
+# rule: 2000 um wide traces, 2000 um clearance; NET_A runs along y = -40000
+A = RoutedWire(layer="Top", width=2000, coords=[2000, -40000, 198000, -40000])
+
+
+def _check(b_wire):
+    result = RoutingResult()
+    result.add_wire("NET_A", A)
+    result.add_wire("NET_B", b_wire)
+    return verify_result(parse_dsn(FIXTURE.read_text()), result)
+
+
+def test_a_crossing_on_one_layer_is_a_short():
+    report = _check(RoutedWire(layer="Top", width=2000, coords=[100000, -15000, 100000, -65000]))
+    assert report.shorts == 1 and report.clearance == 0
+    found = report.short_examples[0]
+    assert {found.net, found.other} == {"NET_A", "NET_B"} and found.layer == "Top"
+    assert abs(found.x_mm - 100.0) < 1.5 and abs(found.y_mm + 40.0) < 1.5
+
+
+def test_copper_closer_than_the_rule_is_a_clearance_violation():
+    # edges 1500 um apart against a 2000 um rule
+    report = _check(RoutedWire(layer="Top", width=2000, coords=[50000, -36500, 150000, -36500]))
+    assert report.shorts == 0 and report.clearance == 1
+
+
+def test_exactly_the_clearance_apart_is_clean():
+    report = _check(RoutedWire(layer="Top", width=2000, coords=[50000, -36000, 150000, -36000]))
+    assert report.clean
+
+
+def test_a_crossing_on_another_layer_is_clean():
+    report = _check(RoutedWire(layer="Bottom", width=2000, coords=[100000, -15000, 100000, -65000]))
+    assert report.clean

tests/test_cli.py

@@ -82,9 +82,23 @@ def test_cli_default_engine_is_exact(tmp_path):
 
 
 @pytest.mark.parametrize("engine", ["grid", "room"])
-def test_unchecked_engines_say_so(tmp_path, capsys, engine):
+def test_unchecked_engines_are_checked_after_routing(tmp_path, capsys, engine):
     assert main([str(FIXTURE), "--engine", engine, "-do", str(tmp_path / "out.ses")]) == 0
-    assert "does not check its copper" in capsys.readouterr().err
+    assert f"{engine} output checked on exact shapes: 0 short(s), 0 clearance" in capsys.readouterr().err
+
+
+def test_strict_fails_a_run_whose_copper_is_not_clean(tmp_path, monkeypatch, capsys):
+    from rpmroute import cli
+    from rpmroute.route.verify import VerifyReport, Violation
+
+    bad = VerifyReport(shorts=1, short_examples=[Violation("A", "B", "F.Cu", 1.0, 2.0)])
+    monkeypatch.setattr(cli, "verify_result", lambda dsn, result: bad)
+    out = tmp_path / "out.ses"
+    assert main([str(FIXTURE), "--engine", "grid", "-do", str(out)]) == 0
+    assert main([str(FIXTURE), "--engine", "grid", "--strict", "-do", str(out)]) == 3
+    assert out.exists()  # the session is still written
+    err = capsys.readouterr().err
+    assert "short: A x B on F.Cu at (1.00, 2.00) mm" in err and "not DRC-clean" in err
 
 
 def test_the_exact_engine_does_not_warn(tmp_path, capsys):
@@ -174,6 +188,9 @@ def test_cli_supported_combinations_are_accepted(tmp_path):
         "rollback": ["--no-rollback"],
         "tree": ["--no-tree"],
         "window": ["--window-reroute", "1"],
+        "vias": ["--reduce-vias"],
+        "via_cost": ["--via-cost", "40"],
+        "smooth": ["--smooth"],
     }
     for engine, options in ENGINE_OPTIONS.items():
         for option in options: