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.

src/rpmroute/cli.py

@@ -25,6 +25,7 @@ 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
 
@@ -37,7 +38,7 @@ ENGINE_OPTIONS: dict[str, frozenset[str]] = {
     }),
     "exact": frozenset({
         "shove", "diagonal", "rip_up", "max_passes", "seed", "orders", "promote", "access",
-        "negotiate", "rollback", "tree", "window", "vias", "via_cost",
+        "negotiate", "rollback", "tree", "window", "vias", "via_cost", "smooth",
     }),
     "room": frozenset({"shove", "pack"}),
 }
@@ -59,6 +60,7 @@ _FLAG_NAMES = {
     "window": "--window-reroute",
     "vias": "--reduce-vias",
     "via_cost": "--via-cost",
+    "smooth": "--smooth",
 }
 
 
@@ -188,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",
@@ -326,6 +341,7 @@ def main(argv: list[str] | None = None) -> int:
             ("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
     ]
@@ -418,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]]

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

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/test_cli.py

@@ -190,6 +190,7 @@ def test_cli_supported_combinations_are_accepted(tmp_path):
         "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: