Window boards: never search a connection ending outside the window

With items away from the window left off its board, a stub from the window
edge out to a rerouted net's far pin crossed copper the exact check never
saw: 38 shorts on th-eda's flight controller. A connection with an end
outside the bounds is now left unrouted, and a window whose new copper
leaves the window is refused.

bench/diagnose.py

@@ -185,7 +185,8 @@ def _flood(router: GridRouter, pin, net_no: int, conns) -> tuple[int, Counter]:
 
 def diagnose(
     dsn_text: str, edge_clearance_mm: float | None, resolution: int = 2, shove: bool = False,
-    access_cost: float = 0.0, hole_to_hole_mm: float = 0.25,
+    access_cost: float = 0.0, hole_to_hole_mm: float = 0.25, seed: int | None = None,
+    negotiate: int = 0,
 ) -> dict:
     dsn = parse_dsn(dsn_text)
     names = {i + 1: n.name for i, n in enumerate(dsn.nets)}
@@ -201,6 +202,8 @@ def diagnose(
         resolution=resolution,
         shove=shove,
         access_cost=access_cost,
+        seed=seed,
+        negotiate=negotiate,
         # the product's configuration: net-class widths and hole spacing
         net_widths=_net_widths_board(dsn, scale),
         via_drill=_via_drill_board(dsn, scale),
@@ -212,6 +215,8 @@ def diagnose(
 
     # the board as the best pass left it
     state = _fresh(seen)
+    # pins on turned pads leave along their pad's axis: replay with the same exits
+    state._axis_exits = dict(routed._axis_exits)
     conns = state._conns
     for idx, (path, a_end, b_end) in best.items():
         conns[idx].a_end, conns[idx].b_end = a_end, b_end
@@ -276,12 +281,14 @@ def main(argv: list[str] | None = None) -> int:
     ap.add_argument("--grid-resolution", type=int, default=2, metavar="K")
     ap.add_argument("--shove", action="store_true", help="as mckicad routes")
     ap.add_argument("--access-cost", type=float, default=0.0)
+    ap.add_argument("--seed", type=int, help="route in this shuffled order, as bench.py does")
+    ap.add_argument("--negotiate", type=int, default=0, metavar="N", help="as the router's --negotiate")
     ap.add_argument("--hole-to-hole", type=float, default=0.25, metavar="MM")
     ap.add_argument("--json", type=Path, help="also write the full table here")
     args = ap.parse_args(argv)
 
     report = diagnose(args.dsn.read_text(), args.edge_clearance, args.grid_resolution, args.shove,
-                      args.access_cost, args.hole_to_hole)
+                      args.access_cost, args.hole_to_hole, args.seed, args.negotiate)
     for row in report["failures"]:
         extra = ""
         for w in row.get("walled", []):

src/freeroute/board/build.py

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

src/freeroute/board/search_tree.py

@@ -18,7 +18,7 @@ from __future__ import annotations
 
 from dataclasses import dataclass
 
-from freeroute.geometry import IntBox, Simplex, overlaps_2d, segment_octagon
+from freeroute.geometry import IntBox, IntPoint, Simplex, overlaps_2d, segment_octagon, segment_slab
 
 __all__ = ["TreeShape", "ShapeSearchTree"]
 
@@ -63,7 +63,9 @@ class TreeShape:
         segment swept by ``half_width + clearance`` (exact integer superset)."""
         if self.seg is None:
             return self.tile.offset(clearance)
-        a, b, half_width = self.seg
+        a, b, half_width = self.seg[-3:]
+        if self.seg[0] == "slab":  # a slanted pin exit, at any angle
+            return segment_slab(a, b, half_width + clearance)
         return segment_octagon(a, b, half_width + clearance)
 
 
@@ -151,6 +153,25 @@ class ShapeSearchTree:
                 return True
         return False
 
+    def segment_conflict(
+        self, a: IntPoint, b: IntPoint, half_width: int, net_no: int, layer: int,
+        clearance: int, kind: str = "wire",
+    ) -> bool:
+        """:meth:`clearance_conflict` for a slanted segment, checked on its
+        exact swept copper instead of its bounding box (which would reach the
+        neighbouring pads of a pin leaving along its turned pad's axis)."""
+        copper = segment_slab(a, b, half_width)
+        grown = segment_slab(a, b, half_width + clearance)
+        for shape in self.overlapping(grown.bounding_box()):
+            if shape.net_no == net_no or not shape.on_layer(layer):
+                continue
+            if shape.blocks != "all" and shape.blocks != kind + "s":
+                continue
+            other = shape.exact if shape.exact is not None else shape.tile
+            if overlaps_2d(copper if not shape.clearance else grown, other):
+                return True
+        return False
+
     def rule_area_overlap(self, box: IntBox, layer: int, kind: str = "wire") -> bool:
         """True if ``box`` overlaps a rule area on ``layer`` that stops ``kind``."""
         for shape in self.overlapping(box):

src/freeroute/cli.py

@@ -30,8 +30,11 @@ from freeroute.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", "rollback"}),
-    "exact": frozenset({"shove", "diagonal", "rip_up", "max_passes", "seed", "orders", "promote", "access", "rollback"}),
+    "grid": frozenset({"rip_up", "max_passes", "seed", "orders", "promote", "access", "negotiate", "rollback", "tree"}),
+    "exact": frozenset({
+        "shove", "diagonal", "rip_up", "max_passes", "seed", "orders", "promote", "access",
+        "negotiate", "rollback", "tree", "window",
+    }),
     "room": frozenset({"shove", "pack"}),
 }
 
@@ -46,7 +49,10 @@ _FLAG_NAMES = {
     "orders": "--orders",
     "promote": "--promote-failures",
     "access": "--access-cost",
+    "negotiate": "--negotiate",
     "rollback": "--no-rollback",
+    "tree": "--no-tree",
+    "window": "--window-reroute",
 }
 
 
@@ -167,6 +173,14 @@ def build_parser() -> argparse.ArgumentParser:
         help="grid and exact engines: extra cost for a route to pass where it would close "
         "another pin's way out while that pin still has connections to route (default 0: off)",
     )
+    parser.add_argument(
+        "--negotiate",
+        type=int,
+        metavar="N",
+        help="grid and exact engines: before routing, N rounds of negotiation on the empty "
+        "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(
         "--no-rollback",
         dest="rollback",
@@ -175,6 +189,53 @@ def build_parser() -> argparse.ArgumentParser:
         "connections a rip-up displaces are rerouted at once and the rip-up is undone "
         "if fewer connections end up routed",
     )
+    parser.add_argument(
+        "--no-tree",
+        dest="tree_nets",
+        action="store_false",
+        help="grid and exact engines: join a multi-pin net's pins as a chain in pin "
+        "order, each connection ending on one chosen pin, as before. By default they are "
+        "paired by a minimum spanning tree and a connection may end on copper its net "
+        "has already routed",
+    )
+    parser.add_argument(
+        "--window-reroute",
+        type=int,
+        metavar="N",
+        help="exact engine: after routing, N rounds of window re-routes: around each "
+        "connection still unrouted, the nets routed wholly inside a window are ripped and "
+        "the window routed again on a finer grid, kept only if fewer connections are left "
+        "unrouted; each round doubles the window's margin (default 0: off)",
+    )
+    parser.add_argument(
+        "--window-resolution",
+        type=int,
+        default=4,
+        metavar="K",
+        help="the window re-route's grid resolution (default 4)",
+    )
+    parser.add_argument(
+        "--window-budget",
+        type=float,
+        default=0.25,
+        metavar="F",
+        help="the window re-route stops starting windows once it has spent this share "
+        "of the routing's own time (default 0.25)",
+    )
+    parser.add_argument(
+        "--window-cap",
+        type=int,
+        default=40,
+        metavar="W",
+        help="at most this many windows per round, smallest first (default 40)",
+    )
+    parser.add_argument(
+        "--window-margin",
+        type=float,
+        default=1.5,
+        metavar="MM",
+        help="the first round's window margin around the stuck connection's pins (default 1.5)",
+    )
     parser.add_argument(
         "--hole-to-hole",
         type=float,
@@ -212,7 +273,10 @@ def main(argv: list[str] | None = None) -> int:
             ("orders", args.orders is not None),
             ("promote", args.promote_failures is not None),
             ("access", args.access_cost is not None),
+            ("negotiate", args.negotiate is not None),
             ("rollback", not args.rollback),
+            ("tree", not args.tree_nets),
+            ("window", args.window_reroute is not None),
         )
         if asked
     ]
@@ -247,8 +311,15 @@ def main(argv: list[str] | None = None) -> int:
             "resolution": 2 if args.grid_resolution is None else args.grid_resolution,
             "heuristic_weight": args.heuristic_weight,
             "access_cost": args.access_cost or 0.0,
+            "negotiate": args.negotiate or 0,
             "hole_to_hole_mm": args.hole_to_hole,
             "rollback": args.rollback,
+            "tree_nets": args.tree_nets,
+            "window_reroute": args.window_reroute or 0,
+            "window_resolution": args.window_resolution,
+            "window_margin_mm": args.window_margin,
+            "window_budget": args.window_budget,
+            "window_cap": args.window_cap,
         }
     elif args.engine == "grid":
         options = {
@@ -258,8 +329,10 @@ def main(argv: list[str] | None = None) -> int:
             "edge_clearance_mm": args.edge_clearance,
             "resolution": 1 if args.grid_resolution is None else args.grid_resolution,
             "access_cost": args.access_cost or 0.0,
+            "negotiate": args.negotiate or 0,
             "hole_to_hole_mm": args.hole_to_hole,
             "rollback": args.rollback,
+            "tree_nets": args.tree_nets,
         }
     if args.engine == "room":
         result = build_rooms_routing_result(

src/freeroute/geometry/__init__.py

@@ -21,7 +21,7 @@ from .direction import Direction, IntDirection
 from .float_point import FloatPoint
 from .limits import CRIT_DOUBLE, CRIT_INT
 from .line import Line
-from .octagon import ceil_sqrt2, overlaps_2d, segment_octagon
+from .octagon import ceil_sqrt2, overlaps_2d, segment_octagon, segment_slab
 from .point import IntPoint, Point, RationalPoint, point, rational_point
 from .polygon import Polygon
 from .polygon_shape import PolygonShape
@@ -59,5 +59,6 @@ __all__ = [
     "shove_segment",
     "ceil_sqrt2",
     "segment_octagon",
+    "segment_slab",
     "overlaps_2d",
 ]

src/freeroute/geometry/octagon.py

@@ -29,7 +29,7 @@ from .line import Line
 from .point import IntPoint
 from .simplex import Simplex
 
-__all__ = ["ceil_sqrt2", "segment_octagon", "overlaps_2d"]
+__all__ = ["ceil_sqrt2", "segment_octagon", "segment_slab", "overlaps_2d"]
 
 
 def ceil_sqrt2(radius: int) -> int:
@@ -82,6 +82,46 @@ def segment_octagon(a: IntPoint, b: IntPoint, radius: int) -> Simplex:
     return Simplex.get_instance(lines)
 
 
+def segment_slab(a: IntPoint, b: IntPoint, radius: int) -> Simplex:
+    """Convex cover of segment ``a``-``b`` swept by ``radius``, at any angle.
+
+    The rectangle along the segment, ``radius`` either side, with flush ends
+    like :func:`polyline.segment_box`: the ends of a trace leg sit on a pad or
+    on the square corner tile of the next leg, which cover them. Corners are
+    rounded away from the middle and the radius gets one unit more, so the
+    side bounds never under-report, and it stays tight for a slanted segment
+    off the 45-degree lines (a pin leaving along its pad's axis on a part
+    turned 30 degrees).
+    """
+    dx, dy = b.x - a.x, b.y - a.y
+    length = math.hypot(dx, dy)
+    r = max(radius, 0) + 1
+    if length == 0:
+        return Simplex.from_corners([
+            IntPoint(a.x - r, a.y - r), IntPoint(a.x + r, a.y - r),
+            IntPoint(a.x + r, a.y + r), IntPoint(a.x - r, a.y + r),
+        ])
+    ux, uy = dx / length, dy / length
+    nx, ny = -uy, ux
+    mx, my = (a.x + b.x) / 2, (a.y + b.y) / 2
+
+    def out(x: float, y: float) -> IntPoint:
+        return IntPoint(math.ceil(x) if x >= mx else math.floor(x),
+                        math.ceil(y) if y >= my else math.floor(y))
+
+    corners = [
+        out(a.x + nx * r, a.y + ny * r),
+        out(b.x + nx * r, b.y + ny * r),
+        out(b.x - nx * r, b.y - ny * r),
+        out(a.x - nx * r, a.y - ny * r),
+    ]
+    for winding in (corners, corners[::-1]):
+        slab = Simplex.from_corners(winding)
+        if not slab.is_empty():
+            return slab
+    return Simplex(())
+
+
 def overlaps_2d(shape_a, shape_b) -> bool:
     """True if the two convex tiles share 2-D area (a real clearance overlap).
 

src/freeroute/route/exact_router.py

@@ -41,6 +41,7 @@ from freeroute.geometry import (
     Simplex,
     segment_box,
     segment_octagon,
+    segment_slab,
     shove_segment,
 )
 from freeroute.geometry.polyline import corner_box
@@ -99,10 +100,14 @@ def route_board_exact(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    negotiate: int = 0,
     rollback: bool = True,
+    tree_nets: bool = True,
     net_widths: dict[int, int] | None = None,
     via_drill: int | None = None,
     hole_to_hole: int = 0,
+    only_nets: frozenset | None = None,
+    bounds: IntBox | None = None,
 ) -> ExactRouteResult:
     """Route ``board`` orthogonally and verify the result with exact geometry.
 
@@ -134,10 +139,14 @@ def route_board_exact(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        negotiate=negotiate,
         rollback=rollback,
+        tree_nets=tree_nets,
         net_widths=net_widths,
         via_drill=via_drill,
         hole_to_hole=hole_to_hole,
+        only_nets=only_nets,
+        bounds=bounds,
     )
     edge = 0 if edge_clearance is None else edge_clearance
     outline = board.outline
@@ -191,25 +200,43 @@ def route_board_exact(
     # 25-pin supply net costs that one connection, not the whole net.
     rejected: list[tuple[int, str, str]] = []
     ends_list = result.connection_ends or [("?", "?", "")] * len(result.connections)
+    anchors_list = getattr(result, "connection_anchors", None) or [()] * len(result.connections)
     # each net is checked at the width it will be written at: its class's
     # when all of its connections went in at that, else the default
     net_half = dict(result.net_half)
-    for (net_no, wires, vias), ends in sorted(
-        zip(result.connections, ends_list, strict=False), key=lambda c: c[0][0]
+    # a connection that ended on another's copper (a T into its net's tree)
+    # dangles if that one is dropped, so it is dropped too; connections come
+    # in commit order, anchors first
+    dropped_at: set[int] = set()
+    for pos, ((net_no, wires, vias), ends, anchors) in sorted(
+        enumerate(zip(result.connections, ends_list, anchors_list, strict=False)),
+        key=lambda c: c[1][0][0],
     ):
+        if any(a in dropped_at for a in anchors):
+            dropped_at.add(pos)
+            rejected.append((net_no, *ends))
+            continue
         wire_half = net_half.get(net_no, half_width)
-        boxes = _copper_boxes(wires, vias, wire_half, via_layers, via_half)
-        wire_count = len(_copper_boxes(wires, [], wire_half, via_layers, via_half))
+        pieces = _copper_pieces(wires, vias, wire_half, via_layers, via_half)
+        boxes = [(box, box_layers) for box, box_layers, _ in pieces]
+        wire_count = len(_copper_pieces(wires, [], wire_half, via_layers, via_half))
         if any(
-            tree.clearance_conflict(
-                box, net_no, layer, clearance, "wire" if i < wire_count else "via"
+            (
+                tree.segment_conflict(*seg, wire_half, net_no, layer, clearance)
+                if seg is not None
+                else tree.clearance_conflict(
+                    box, net_no, layer, clearance, "wire" if i < wire_count else "via"
+                )
             )
-            for i, (box, box_layers) in enumerate(boxes)
+            for i, (box, box_layers, seg) in enumerate(pieces)
             for layer in box_layers
         ) or _end_in_rule_area(tree, wires, wire_half) or (
-            outline is not None and not all(outline.box_clear(b, edge) for b, _ in boxes)
+            outline is not None and not _inside_outline(
+                outline, boxes[:wire_count], vias, (via_half or wire_half) + edge, edge
+            )
         ):
             rejected.append((net_no, *ends))
+            dropped_at.add(pos)
             continue  # exact-clearance conflict -> drop (may be recovered by shove)
         acc = accepted.get(net_no)
         if acc is None:
@@ -221,16 +248,25 @@ def route_board_exact(
             v for v in dict.fromkeys(vias)
             if v not in acc.vias and not _on_fixed_via(net_no, v, fixed_vias, via_half)
         )
-        for box, box_layers in boxes:
+        for box, box_layers, seg in pieces:
             oid = next(owner)
-            tree.insert(TreeShape(oid, net_no, box_layers, box, routed=True))
+            if seg is None:
+                tree.insert(TreeShape(oid, net_no, box_layers, box, routed=True))
+            else:  # a slanted pin exit: its exact copper, rebuilt for the DRC check
+                tree.insert(TreeShape(
+                    oid, net_no, box_layers, box, routed=True,
+                    exact=segment_slab(*seg, wire_half), seg=("slab", *seg, wire_half),
+                ))
             acc.owners.append(oid)
 
     accepted_before_recovery = set(accepted)
     # a net is dropped if it has a real ratsnest (>= 2 pins on a signal layer)
     # but was not accepted — whether the grid failed to route it or its exact
     # copper conflicted.
-    dropped = sorted(_routable_nets(board, signal_layers) - set(accepted))
+    routable = _routable_nets(board, signal_layers)
+    if only_nets is not None:  # a window re-route: the other nets are not ours to route
+        routable &= set(only_nets)
+    dropped = sorted(routable - set(accepted))
 
     shoves = 0
     if shove and dropped:
@@ -255,7 +291,7 @@ def route_board_exact(
 
     if diagonal:
         outline = board.bounding_box
-        for net_no in sorted(_routable_nets(board, signal_layers)):
+        for net_no in sorted(routable):
             _diagonalize(
                 net_no, board, tree, accepted, owner, signal_layers, half_width, clearance, outline
             )
@@ -658,6 +694,27 @@ def _on_fixed_via(net_no, point, fixed_vias, via_half) -> bool:
     )
 
 
+def _copper_pieces(wires, vias, half_width, via_layers, via_half=None):
+    """Like :func:`_copper_boxes`, but a slanted wire segment (a pin leaving
+    along a turned pad's axis) comes with its end points, so it can be checked
+    on its exact copper: ``(box, layers, (a, b) or None)``."""
+    via_half = via_half or half_width
+    pieces: list[tuple[IntBox, frozenset[int], tuple | None]] = []
+    for layer, points in wires:
+        on = frozenset({layer})
+        for a, b in zip(points, points[1:], strict=False):
+            if a.x == b.x or a.y == b.y:
+                pieces.append((segment_box(a, b, half_width), on, None))
+            else:
+                pieces.append((segment_slab(a, b, half_width).bounding_box(), on, (a, b)))
+        for c in points[1:-1]:
+            pieces.append((corner_box(c, half_width), on, None))
+    for loc in vias:
+        vbox = IntBox(loc.x - via_half, loc.y - via_half, loc.x + via_half, loc.y + via_half)
+        pieces.append((vbox, via_layers, None))
+    return pieces
+
+
 def _copper_boxes(wires, vias, half_width, via_layers, via_half=None):
     via_half = via_half or half_width
     boxes: list[tuple[IntBox, frozenset[int]]] = []
@@ -670,6 +727,15 @@ def _copper_boxes(wires, vias, half_width, via_layers, via_half=None):
     return boxes
 
 
+def _inside_outline(outline, wire_boxes, vias, via_reach, edge) -> bool:
+    """Copper inside the board, ``edge`` from its outline. A via is round, as
+    the grid and KiCad take it: its square box would reach past a chamfered
+    corner where the via itself does not."""
+    return all(outline.box_clear(b, edge) for b, _ in wire_boxes) and all(
+        outline.point_clear(v, via_reach) for v in vias
+    )
+
+
 def _is_rotated(shape) -> bool:
     return isinstance(shape, Simplex) and not shape.is_int_box()
 

src/freeroute/route/grid_router.py

@@ -34,8 +34,8 @@ import random
 from freeroute.board.board import BasicBoard
 from freeroute.board.items import ConductionArea, ObstacleArea, Pin, Via
 from freeroute.geometry import IntBox, IntPoint, Simplex
-from freeroute.geometry.octagon import overlaps_2d
-from freeroute.geometry.polyline import corner_box
+from freeroute.geometry.octagon import overlaps_2d, segment_slab
+from freeroute.geometry.polyline import corner_box, segment_box
 
 __all__ = ["GridRouter", "RouteResult", "route_board"]
 
@@ -65,7 +65,7 @@ class RouteResult:
 
     __slots__ = (
         "wires", "vias", "half_width", "unrouted", "connections", "connection_ends", "failed",
-        "net_half", "narrowed",
+        "net_half", "narrowed", "connection_anchors",
     )
 
     def __init__(self, half_width: int) -> None:
@@ -79,6 +79,9 @@ class RouteResult:
         #: what each routed connection joins, and the zone both ends sit in
         #: (or ""), parallel to ``connections``
         self.connection_ends: list[tuple[str, str, str]] = []
+        #: for each routed connection, the earlier ones (positions in
+        #: ``connections``) whose copper it ended on, parallel to ``connections``
+        self.connection_anchors: list[tuple[int, ...]] = []
         #: connections left unrouted: (net_no, one end, the other end)
         self.failed: list[tuple[int, str, str]] = []
         #: half width of each net routed wider than the default (its class)
@@ -126,6 +129,10 @@ class _Connection:
         "narrow",
         "half",
         "stubs",
+        "stub_near",
+        "anchors",
+        "copper",
+        "seq",
     )
 
     def __init__(self, index: int, net_no: int, a: Pin, b: Pin) -> None:
@@ -143,6 +150,8 @@ class _Connection:
         self.halo_nodes: list[Node] = []
         # each end's stub: its layer, its copper tiles, and the nodes it claims
         self.stubs: list[tuple[int, list[IntBox], set[Node]]] = []
+        # every node its stubs come near, claimed or not (see GridRouter._stub_near)
+        self.stub_near: list[Node] = []
         # the pins and zones each end may use, and which pin the route ended
         # on (None when it ended on a zone)
         self.a_group: tuple[list[Pin], list] = ([a], [])
@@ -155,6 +164,14 @@ class _Connection:
         # routed at the default width instead; the half width it went in at
         self.narrow = False
         self.half = 0
+        # connections whose copper this one ended on (a T into its net's
+        # tree): ripping one of them leaves this one dangling
+        self.anchors: frozenset[int] = frozenset()
+        # the nodes of its committed copper (path cells, via cells on every
+        # layer), where another connection of its net may end
+        self.copper: frozenset[Node] = frozenset()
+        # commit order: a connection is always committed after its anchors
+        self.seq = 0
 
 
 class GridRouter:
@@ -180,17 +197,46 @@ class GridRouter:
         seed: int | None = None,
         route_first: frozenset | None = None,
         access_cost: float = 0.0,
+        negotiate: int = 0,
         rollback: bool = True,
         net_widths: dict[int, int] | None = None,
         via_drill: int | None = None,
         hole_to_hole: int = 0,
+        tree_nets: bool = True,
+        only_nets: frozenset | None = None,
+        bounds: IntBox | None = None,
     ) -> None:
         self.board = board
+        # A window re-route routes some nets inside part of the board: only
+        # these nets get connections, and the grid covers only ``bounds``
+        # (cells outside it do not exist, so nothing is routed there).
+        self.only_nets = frozenset(only_nets) if only_nets is not None else None
+        self._bounds = bounds
+        # connections with an end outside ``bounds``: never searched, since
+        # the grid has no cells to reach that end by
+        self._outside: set[int] = set()
+        # Multi-pin nets: pair a net's pin groups by a minimum spanning tree,
+        # and let a connection start or end on copper its net already routed
+        # (a T into the tree), not only on one chosen pin.
+        self.tree = bool(tree_nets)
+        self._dependents: dict[int, set[int]] = {}
+        self._commits = 0
+        self._plane_nets: set[int] = set()
+        self._net_conns: dict[int, list[_Connection]] = {}
         # Pin access: while a pin still has connections to route, the cells
         # its route would leave by (its end cells, the via it may need there,
         # and the clearance around both) cost other nets this much extra, so
         # they route round a fine-pitch pin's way out instead of sealing it.
         self.access_cost = max(float(access_cost), 0.0)
+        # Negotiated congestion (PathFinder): before the real routing, every
+        # connection is routed this many times on the empty board, where routes
+        # may overlap at a price that grows where they compete. The cells that
+        # stay contested keep a history cost the real routing pays, so the first
+        # routes leave room around the places later routes have no way round.
+        self.negotiate = max(int(negotiate), 0)
+        self._history: dict[Node, float] = {}
+        self._present: dict[Node, dict[int, int]] | None = None
+        self._present_cost = 0.0
         self._doorways: dict[Node, list[tuple[int, int]]] = {}
         self._pending: dict[int, int] = {}
         # Rip-up as a transaction: the connections a rip-up route crosses are
@@ -208,6 +254,12 @@ class GridRouter:
         self._escape_cells = 12
         self._crowded_cache: dict = {}
         self._trapped_cache: dict = {}
+        # pin location -> where a pin on a turned fine-pitch pad leaves its
+        # pin row along the pad's axis (None: it leaves like any other pin)
+        self._axis_exits: dict[IntPoint, IntPoint | None] = {}
+        # and the other nets' pads near each such pin, its stubs' obstacles
+        self._axis_pads: dict[IntPoint, list] = {}
+        self._part_centres: dict[int, tuple[float, float] | None] = {}
         self.heuristic_weight = max(float(heuristic_weight), 1.0)
         self.trace_width = max(trace_width, 1)
         self.clearance = max(clearance, 0)
@@ -282,6 +334,11 @@ class GridRouter:
         self.layers = list(layers)
 
         box = board.bounding_box
+        if bounds is not None:
+            box = IntBox(
+                max(box.ll.x, bounds.ll.x), max(box.ll.y, bounds.ll.y),
+                min(box.ur.x, bounds.ur.x), min(box.ur.y, bounds.ur.y),
+            )
         self.origin_x = box.ll.x
         self.origin_y = box.ll.y
         self.cols = max(1, math.ceil((box.ur.x - box.ll.x) / self.step) + 1)
@@ -299,9 +356,15 @@ class GridRouter:
         self._zone_cells: dict[int, list[Node]] = {}
         # per-connection occupancy (owner = connection index)
         self._cell_owner: dict[Node, int] = {}
-        self._via_owner: dict[Cell, int] = {}
+        # Node -> connections whose stub comes near it. A cell has one owner,
+        # and a stub claims only cells nobody owns yet, so where several pins
+        # leave side by side (a QFN turned 45 degrees: neighbours 0.35 mm apart
+        # on each axis) the cell two stubs share names only the first, and the
+        # exact check between the later stubs would never run.
+        self._stub_near: dict[Node, set[int]] = {}
         # every connection whose via covers a cell, in claim order: a via two
-        # connections share still blocks after the first of them is ripped
+        # connections share still blocks after the first of them is ripped,
+        # and a route through it must rip all of them
         self._via_claims: dict[Cell, list[int]] = {}
         # trace halos: node -> indices of the connections claiming it
         self._halo: dict[Node, list[int]] = {}
@@ -520,14 +583,19 @@ class GridRouter:
         if owner is not None and conns[owner].net_no != net_no:
             blocking = owner
         else:
-            via_owner = self._via_owner.get(cell)
-            if via_owner is not None and conns[via_owner].net_no != net_no:
-                blocking = via_owner
+            blocking = self._via_blocker(cell, net_no, conns)
         if blocking is None:
             for i in self._halo.get(node, ()):
                 if conns[i].net_no != net_no:
                     blocking = i
                     break
+        if blocking is None:
+            # another net's pin stub comes too close, though the cell it once
+            # claimed may since have been freed by a rip of its first owner
+            for i in self._stub_near.get(node, ()):
+                if conns[i].net_no != net_no:
+                    blocking = i
+                    break
         if blocking is None:
             return 0.0
         if not allow_ripup:
@@ -537,6 +605,17 @@ class GridRouter:
             return None
         return self.rip_penalty * (1 + rip_count)
 
+    def _via_others(self, cell: Cell, net_no: int, conns: list[_Connection]) -> list[int]:
+        """Connections of other nets whose via covers ``cell``: all of them,
+        since two connections of a net can share one via."""
+        return [i for i in self._via_claims.get(cell, ()) if conns[i].net_no != net_no]
+
+    def _via_blocker(self, cell: Cell, net_no: int, conns: list[_Connection]) -> int | None:
+        """The other net's via connection on ``cell`` hardest to rip (the
+        penalty and the rip cap go by it), or None."""
+        others = self._via_others(cell, net_no, conns)
+        return max(others, key=lambda i: conns[i].rip_count) if others else None
+
     def _via_cells(self, cell: Cell) -> list[Cell]:
         """The cell a via sits in plus the neighbours its copper reaches."""
         r = self.via_reach
@@ -642,6 +721,8 @@ class GridRouter:
     def _search(
         self, conn: _Connection, allow_ripup: bool, conns: list[_Connection]
     ) -> list[Node] | None:
+        if conn.index in self._outside:
+            return None
         half = self._conn_half(conn)
         self._cur_half, self._spread = half, self._spread_for(half)
         try:
@@ -658,6 +739,13 @@ class GridRouter:
             goal_cell = self._group_target(conn.a_group)
         starts = self._group_ends(conn.a_group, conn.net_no, conns, allow_ripup)
         goals = self._group_ends(conn.b_group, conn.net_no, conns, allow_ripup)
+        # either side may also start or end on copper its net already routed
+        a_tree = self._tree_ends(conn, conn.a_group)
+        b_tree = self._tree_ends(conn, conn.b_group)
+        for node in a_tree:
+            starts.setdefault(node, None)
+        for node in b_tree:
+            goals.setdefault(node, None)
         if not starts or not goals:
             return None
         # A start that is already an end joins at once, except that ending on
@@ -670,6 +758,7 @@ class GridRouter:
         ]
         if common:
             conn.a_end, conn.b_end = starts[common[0]], goals[common[0]]
+            conn.anchors = _anchors([common[0]], starts, goals, a_tree, b_tree)
             return [common[0]]
         net_no = conn.net_no
 
@@ -735,6 +824,7 @@ class GridRouter:
                 if ok:
                     path = _reconstruct(came_from, current)
                     conn.a_end, conn.b_end = starts.get(path[0]), end
+                    conn.anchors = _anchors(path, starts, goals, a_tree, b_tree)
                     return path
             cx, cy, cl = current
             base = g_score[current]
@@ -758,6 +848,8 @@ class GridRouter:
                         continue
                     if self._doorways:
                         enter += self._access(nxt, net_no)
+                    if self._history or self._present is not None:
+                        enter += self._congestion(nxt, net_no)
                 step = 1.0 if dx == 0 or dy == 0 else math.sqrt(2)
                 self._relax(
                     current, nxt, base + step + enter, goal_cell, g_score, came_from, open_heap
@@ -770,12 +862,64 @@ class GridRouter:
                     if layer == cl:
                         continue
                     nxt = (cx, cy, layer)
-                    if g_via < g_score.get(nxt, math.inf):
+                    g_layer = g_via
+                    if self._history or self._present is not None:
+                        g_layer += self._congestion(nxt, net_no)
+                    if g_layer < g_score.get(nxt, math.inf):
                         heapq.heappush(
-                            open_heap, (g_via + self._h(nxt, goal_cell), nxt, g_via, current)
+                            open_heap, (g_layer + self._h(nxt, goal_cell), nxt, g_layer, current)
                         )
         return None
 
+    def _tree_ends(self, conn: _Connection, group) -> dict[Node, frozenset[int]]:
+        """Copper its net has already routed on ``group``'s side of ``conn``: a
+        route may start or end anywhere on it. Each node maps to what a route
+        ending there relies on: the connection that laid the copper and every
+        one between it and ``group`` (routed connections of a net form a
+        forest, so that path is unique). Ripping any of them would cut the
+        route off. Empty for plane nets, which keep their drops to the plane,
+        and when tree routing is off."""
+        if not self.tree or conn.net_no in self._plane_nets:
+            return {}
+        adjacent: dict[int, list[tuple[int, _Connection]]] = {}
+        for c in self._net_conns.get(conn.net_no, ()):
+            if c is conn or not c.routed:
+                continue
+            a, b = id(c.a_group), id(c.b_group)
+            adjacent.setdefault(a, []).append((b, c))
+            adjacent.setdefault(b, []).append((a, c))
+        owners: dict[Node, frozenset[int]] = {}
+        path_to: dict[int, frozenset[int]] = {id(group): frozenset()}
+        stack = [id(group)]
+        while stack:
+            here = stack.pop()
+            for other, c in adjacent.get(here, ()):
+                if other in path_to:
+                    continue
+                path = path_to[here] | {c.index}
+                path_to[other] = path
+                stack.append(other)
+                for node in c.copper:
+                    # a walled cell's via moved into the pad: no copper there
+                    if node not in self._keepout and node not in self._via_only:
+                        owners.setdefault(node, path)
+        return owners
+
+    def _with_dependents(self, victims: list[_Connection], conns: list[_Connection]) -> list[_Connection]:
+        """``victims`` and every routed connection that ended on their copper,
+        directly or through another: ripping a route rips the routes teed onto
+        it, which would otherwise dangle. Anchors come before what hangs on
+        them, as they were committed."""
+        found = {v.index: v for v in victims}
+        stack = list(victims)
+        while stack:
+            for i in self._dependents.get(stack.pop().index, ()):
+                c = conns[i]
+                if c.routed and i not in found:
+                    found[i] = c
+                    stack.append(c)
+        return sorted(found.values(), key=lambda c: (c.seq, c.index))
+
     # --- pin stubs ----------------------------------------------------------
     # A pin rarely sits on a cell centre, so every route starts and ends with a
     # short stub from the pin to its first cell. The grid has to see that
@@ -833,30 +977,143 @@ class GridRouter:
         clearance of the pad next door, though the straight exit clears it.
         """
         end = self._cell_center(cell)
-        dx, dy = end.x - pin_location.x, end.y - pin_location.y
+        head = [pin_location]
+        start = pin_location
+        exit_point = self._axis_exits.get(pin_location)
+        if exit_point is not None:
+            # a pin on a turned fine-pitch pad first leaves along the pad's
+            # axis, past the pin row, then takes the usual L to its cell
+            head = [pin_location, exit_point]
+            start = exit_point
+        dx, dy = end.x - start.x, end.y - start.y
         if not self._orthogonal or dx == 0 or dy == 0:
-            return [pin_location, end]
-        if abs(dx) >= abs(dy):
-            return [pin_location, IntPoint(end.x, pin_location.y), end]
-        return [pin_location, IntPoint(pin_location.x, end.y), end]
+            tail = [end]
+        elif abs(dx) >= abs(dy):
+            tail = [IntPoint(end.x, start.y), end]
+        else:
+            tail = [IntPoint(start.x, end.y), end]
+        points = []
+        for point in head + tail:
+            if not points or points[-1] != point:
+                points.append(point)
+        return points if len(points) > 1 else [pin_location, end]
+
+    def _leg_shapes(self, points: list[IntPoint], half: int, grow: int = 0) -> list:
+        """A stub's copper, grown by ``grow``: a box per straight leg and per
+        inner corner, and an exact slab for a slanted leg (a pad-axis exit),
+        whose bounding box would reach the neighbouring pads."""
+        shapes: list = []
+        for a, b in zip(points, points[1:], strict=False):
+            if a == b:
+                continue
+            if a.x == b.x or a.y == b.y:
+                box = segment_box(a, b, half)
+                shapes.append(box.offset(grow) if grow else box)
+            else:
+                shapes.append(segment_slab(a, b, half + grow))
+        for c in points[1:-1]:
+            box = corner_box(c, half)
+            shapes.append(box.offset(grow) if grow else box)
+        return shapes
+
+    def _axis_exit(self, pin: Pin) -> IntPoint | None:
+        """Where a pin on a turned fine-pitch pad clears its pin row.
+
+        A QFN placed at 45 degrees has no straight exit on the grid: every
+        horizontal or vertical step from a pin passes its neighbours closer
+        than the clearance. The way out is along the pad's own axis, away
+        from the part, until an L from there to a grid cell clears every
+        other net's pad (checked on exact shapes, as the exact engine will).
+        Any angle off the grid axes counts, not just 45 degrees.
+        """
+        loc = pin.location
+        if loc in self._axis_exits:
+            return self._axis_exits[loc]
+        self._axis_exits[loc] = None
+        shape = pin.shape
+        if not isinstance(shape, Simplex) or shape.is_int_box():
+            return None
+        corners = [shape.corner_approx(i) for i in range(shape.border_line_count())]
+        edges = [(b.x - a.x, b.y - a.y) for a, b in zip(corners, corners[1:] + corners[:1], strict=False)]
+        lengths = [math.hypot(dx, dy) for dx, dy in edges]
+        if len(edges) < 3 or max(lengths) < 1.25 * min(lengths):
+            return None  # no long axis to leave along
+        dx, dy = edges[lengths.index(max(lengths))]
+        ux, uy = dx / max(lengths), dy / max(lengths)
+        if min(abs(ux), abs(uy)) < 0.17:
+            return None  # within ten degrees of a grid axis: the usual exits work
+        centre = self._part_centre(pin)
+        if centre is None:
+            return None
+        if (loc.x - centre[0]) * ux + (loc.y - centre[1]) * uy < 0:
+            ux, uy = -ux, -uy
+        reach = max((c.x - loc.x) * ux + (c.y - loc.y) * uy for c in corners)
+        h, cl = self.half_width, self.clearance
+        span = reach + h + cl + 16 * self.step
+        others = [
+            p.shape for p in self.board.get_pins()
+            if p.shape is not None and p is not pin and not set(p.net_nos) & set(pin.net_nos)
+            and set(p.layers) & set(pin.layers)
+            and abs(p.location.x - loc.x) < 2 * span and abs(p.location.y - loc.y) < 2 * span
+        ]
+        self._axis_pads[loc] = others
+        for j in range(16):
+            d = reach + h + cl + j * self.step / 2
+            exit_point = IntPoint(round(loc.x + ux * d), round(loc.y + uy * d))
+            out = segment_slab(loc, exit_point, h + cl)
+            if any(overlaps_2d(out, o) for o in others):
+                continue
+            ex, ey = self._cell_of(exit_point)
+            self._axis_exits[loc] = exit_point
+            for ddx, ddy in itertools.product((0, -1, 1), repeat=2):
+                cell = (ex + ddx, ey + ddy)
+                if not (0 <= cell[0] < self.cols and 0 <= cell[1] < self.rows):
+                    continue
+                legs = self._leg_shapes(self._stub_points(loc, cell)[1:], h, cl)
+                if not any(overlaps_2d(g, o) for g in legs for o in others):
+                    return exit_point
+            self._axis_exits[loc] = None
+        return None
+
+    def _exit_clips_a_pad(self, pin: Pin, cell: Cell) -> bool:
+        """Whether the stub from an axis exit to ``cell`` comes closer than the
+        clearance to another net's pad (exactly, as the exact engine checks):
+        the exit was chosen with one clear cell, not every cell around it."""
+        legs = self._leg_shapes(
+            self._stub_points(pin.location, cell)[1:], self._cur_half, self.clearance
+        )
+        return any(overlaps_2d(g, pad) for g in legs for pad in self._axis_pads.get(pin.location, ()))
+
+    def _part_centre(self, pin: Pin) -> tuple[float, float] | None:
+        key = pin.component_no
+        if key not in self._part_centres:
+            mates = [p.location for p in self.board.get_pins() if p.component_no == key] if key else []
+            self._part_centres[key] = (
+                (sum(m.x for m in mates) / len(mates), sum(m.y for m in mates) / len(mates))
+                if len(mates) > 2 else None
+            )
+        return self._part_centres[key]
 
     def _stub_cells(self, pin_location: IntPoint, cell: Cell, half: int | None = None) -> list[Cell]:
         """Cells where another net's trace would come too close to the stub."""
         from freeroute.board.outline import _point_segment
 
         points = self._stub_points(pin_location, cell)
-        end = points[-1]
         reach = (half or self._cur_half) + self.half_width + self.clearance
         box = IntBox(
-            min(pin_location.x, end.x), min(pin_location.y, end.y),
-            max(pin_location.x, end.x), max(pin_location.y, end.y),
+            min(p.x for p in points), min(p.y for p in points),
+            max(p.x for p in points), max(p.y for p in points),
         )
         legs = list(zip(points, points[1:], strict=False))
-        return [
-            c
-            for c in self._cells_in_box(box, reach)
-            if min(_point_segment(self._cell_center(c), a, b) for a, b in legs) < reach
-        ]
+        joints = points[1:]  # each carries a square corner tile
+
+        def near(c) -> bool:
+            p = self._cell_center(c)
+            if min(_point_segment(p, a, b) for a, b in legs) < reach:
+                return True
+            return any(max(abs(p.x - j.x), abs(p.y - j.y)) < reach for j in joints)
+
+        return [c for c in self._cells_in_box(box, reach) if near(c)]
 
     def _stub_clear(
         self,
@@ -872,13 +1129,12 @@ class GridRouter:
         if keepouts:
             # the stub is off the grid, so check it exactly, as the exact
             # engine will: its copper grown by clearance must miss every keepout
-            from freeroute.geometry.polyline import Polyline, PolylineShape
-
             points = self._stub_points(pin.location, cell)
             if points[-1] != pin.location:
-                for tile in PolylineShape(Polyline(points), self._cur_half).tiles():
-                    grown = tile.offset(self.clearance)
-                    if any(k.overlaps(grown if needs else tile) for k, needs in keepouts):
+                legs = self._leg_shapes(points, self._cur_half)
+                grown_legs = self._leg_shapes(points, self._cur_half, self.clearance)
+                for tile, grown in zip(legs, grown_legs, strict=True):
+                    if any(overlaps_2d(k, grown if needs else tile) for k, needs in keepouts):
                         return False
                 # the track's round end at the pin, for a rule area
                 cap = corner_box(pin.location, self._cur_half)
@@ -892,15 +1148,16 @@ class GridRouter:
             allow_ripup and all(conns[i].rip_count < self.rip_cap for i in owners)
         )
 
-    def _stub_tiles(self, pin_location: IntPoint, cell: Cell, half: int) -> list[IntBox]:
-        """The stub's copper: its legs, and a square at each corner and at the
-        cell end, where the route carries on."""
+    def _stub_tiles(self, pin_location: IntPoint, cell: Cell, half: int, grow: int = 0) -> list:
+        """The stub's copper (grown by ``grow``): its legs, and a square at each
+        corner and at the cell end, where the route carries on."""
         points = self._stub_points(pin_location, cell)
-        tiles = [corner_box(point, half) for point in points[1:]]
+        tiles: list = [
+            corner_box(point, half).offset(grow) if grow else corner_box(point, half)
+            for point in points[1:]
+        ]
         if len(points) > 1 and points[-1] != pin_location:
-            from freeroute.geometry.polyline import Polyline, PolylineShape
-
-            tiles += PolylineShape(Polyline(points), half).tiles()
+            tiles += self._leg_shapes(points, half, grow)
         return tiles
 
     def _stub_owners(
@@ -920,16 +1177,24 @@ class GridRouter:
                 other = [tiles for lay, tiles, nodes in conns[owner].stubs if node in nodes]
                 if other:
                     if grown is None:
-                        grown = [
-                            t.offset(self.clearance)
-                            for t in self._stub_tiles(pin.location, cell, half or self._cur_half)
-                        ]
-                    if not any(g.overlaps(t) for tiles in other for t in tiles for g in grown):
+                        grown = self._stub_tiles(
+                            pin.location, cell, half or self._cur_half, self.clearance
+                        )
+                    if not any(overlaps_2d(g, t) for tiles in other for t in tiles for g in grown):
                         continue
                 owners.add(owner)
-            via_owner = self._via_owner.get(c)
-            if via_owner is not None and conns[via_owner].net_no != net_no:
-                owners.add(via_owner)
+            for idx in self._stub_near.get(node, ()):
+                if idx in owners or conns[idx].net_no == net_no:
+                    continue
+                theirs = [tiles for lay, tiles, _ in conns[idx].stubs if lay == layer]
+                if theirs:
+                    if grown is None:
+                        grown = self._stub_tiles(
+                            pin.location, cell, half or self._cur_half, self.clearance
+                        )
+                    if any(overlaps_2d(g, t) for tiles in theirs for t in tiles for g in grown):
+                        owners.add(idx)
+            owners.update(self._via_others(c, net_no, conns))
         return owners
 
     def _end_penalty(self, pin: Pin, node: Node, net_no: int, allow_ripup: bool, conns) -> float:
@@ -1009,11 +1274,16 @@ class GridRouter:
         return self._cell_of(IntPoint((box.ll.x + box.ur.x) // 2, (box.ll.y + box.ur.y) // 2))
 
     def _stub_cost(self, pin: Pin, node: Node) -> float:
-        c = self._cell_center(node[:2])
-        dx, dy = abs(c.x - pin.location.x), abs(c.y - pin.location.y)
-        if self._orthogonal:  # measured the way the route itself is allowed to move
-            return (dx + dy) / self.step
-        return math.hypot(dx, dy) / self.step
+        if self._axis_exits.get(pin.location) is None:
+            c = self._cell_center(node[:2])
+            dx, dy = abs(c.x - pin.location.x), abs(c.y - pin.location.y)
+            if self._orthogonal:  # measured the way the route itself is allowed to move
+                return (dx + dy) / self.step
+            return math.hypot(dx, dy) / self.step
+        points = self._stub_points(pin.location, node[:2])
+        return sum(
+            math.hypot(b.x - a.x, b.y - a.y) for a, b in zip(points, points[1:], strict=False)
+        ) / self.step
 
     def _end_nodes(self, pin: Pin, net_no: int, conns, allow_ripup: bool = False) -> set[Node]:
         """Nodes a route may start or end on for ``pin``: the nearest cell and
@@ -1023,14 +1293,21 @@ class GridRouter:
         everywhere else, or a pin whose only way out another net has taken
         could never have it back."""
         layers = [layer for layer in pin.layers if layer in self.layers]
-        cx, cy = self._cell_of(pin.location)
+        exit_point = None
+        if self._orthogonal and self._crowded(pin, net_no):
+            exit_point = self._axis_exit(pin)
+        cx, cy = self._cell_of(exit_point if exit_point is not None else pin.location)
         nodes: set[Node] = set()
         for dx, dy in ((0, 0), *self._neighbours):
             cell = (cx + dx, cy + dy)
             if not (0 <= cell[0] < self.cols and 0 <= cell[1] < self.rows):
                 continue
+            if exit_point is not None and self._exit_clips_a_pad(pin, cell):
+                continue
             for layer in layers:
-                if (dx or dy) and self._enter_cost(cell, layer, net_no, allow_ripup, conns) is None:
+                # the pin's own cell is in its pad; an exit cell is not
+                checked = dx or dy or exit_point is not None
+                if checked and self._enter_cost(cell, layer, net_no, allow_ripup, conns) is None:
                     continue
                 if self._stub_clear(pin, cell, layer, net_no, conns, allow_ripup=allow_ripup):
                     nodes.add((*cell, layer))
@@ -1040,6 +1317,11 @@ class GridRouter:
         # cost, so it is only taken where a short step would not do.
         if self._orthogonal and self._crowded(pin, net_no) and self._trapped(pin, net_no, nodes):
             nodes |= self._escape_nodes(pin, net_no, conns, layers, (cx, cy), allow_ripup)
+        if not nodes and exit_point is not None:
+            # every cell past the pin row is taken: report no way out, so the
+            # search goes on to rip-up, rather than fall back to a cell out in
+            # the open on top of another net's route
+            return nodes
         if not nodes:  # nothing clear: fall back to the nearest cell, as before
             nodes = {(cx, cy, layer) for layer in layers}
             if self._keepout_boxes and not any(
@@ -1113,7 +1395,6 @@ class GridRouter:
         whose stub from the pin clears every other net's pad by the full
         clearance, checked on the stub's copper tiles as the exact engine
         will rather than on the grid."""
-        from freeroute.geometry.polyline import Polyline, PolylineShape
 
         reach = self._escape_cells
         near = [
@@ -1135,17 +1416,14 @@ class GridRouter:
                 cell = (cx + dx * k + sx, cy + dy * k + sy)
                 if not (0 <= cell[0] < self.cols and 0 <= cell[1] < self.rows):
                     break
-                grown = [
-                    tile.offset(self.clearance)
-                    for tile in PolylineShape(
-                        Polyline(self._stub_points(pin.location, cell)), self._cur_half
-                    ).tiles()
-                ]
+                grown = self._leg_shapes(
+                    self._stub_points(pin.location, cell), self._cur_half, self.clearance
+                )
                 for layer in layers:
                     if self._enter_cost(cell, layer, net_no, allow_ripup, conns) is None:
                         continue
                     if any(
-                        layer in box_layers and any(g.overlaps(box) for g in grown)
+                        layer in box_layers and any(overlaps_2d(g, box) for g in grown)
                         for box, box_layers in near
                     ):
                         continue
@@ -1206,9 +1484,9 @@ class GridRouter:
                 if conn.index not in claims:
                     claims.append(conn.index)
                     conn.via_halo.append(c)
-                self._via_owner.setdefault(c, conn.index)
         ends = ((conn.a_end, wire_segs[0], 0), (conn.b_end, wire_segs[-1], -1)) if wire_segs else ()
         conn.stubs = []
+        self._forget_stubs(conn)
         for pin, (layer, cells), at in ends:
             if not isinstance(pin, Pin):
                 continue  # ended on a zone or a plane: no stub
@@ -1216,6 +1494,8 @@ class GridRouter:
             claimed: set[Node] = set()
             for c in self._stub_cells(pin.location, cell, half):
                 node = (*c, layer)
+                self._stub_near.setdefault(node, set()).add(conn.index)
+                conn.stub_near.append(node)
                 if node not in self._cell_owner:
                     self._cell_owner[node] = conn.index
                     conn.trace_cells.append((c, layer))
@@ -1249,8 +1529,24 @@ class GridRouter:
             # via k joins wire segments k and k + 1
             conn.vias[0 if idx == 0 else idx - 1] = location
         conn.routed = True
+        self._commits += 1
+        conn.seq = self._commits
+        conn.copper = frozenset(path) | frozenset(
+            (*cell, layer) for cell in conn.via_cells for layer in self.layers
+        )
+        for anchor in conn.anchors:
+            self._dependents.setdefault(anchor, set()).add(conn.index)
         self._settle(conn, -1)
 
+    def _forget_stubs(self, conn: _Connection) -> None:
+        for node in conn.stub_near:
+            near = self._stub_near.get(node)
+            if near is not None:
+                near.discard(conn.index)
+                if not near:
+                    del self._stub_near[node]
+        conn.stub_near = []
+
     def _rip(self, conn: _Connection) -> None:
         for cell, layer in conn.trace_cells:
             if self._cell_owner.get((*cell, layer)) == conn.index:
@@ -1259,11 +1555,6 @@ class GridRouter:
             claims = self._via_claims.get(cell)
             if claims is not None and conn.index in claims:
                 claims.remove(conn.index)
-            if self._via_owner.get(cell) == conn.index:
-                if claims:
-                    self._via_owner[cell] = claims[0]
-                else:
-                    del self._via_owner[cell]
             if claims is not None and not claims:
                 del self._via_claims[cell]
         conn.via_halo = []
@@ -1276,6 +1567,7 @@ class GridRouter:
         conn.halo_nodes = []
         conn.trace_cells = []
         conn.stubs = []
+        self._forget_stubs(conn)
         for cell in conn.via_cells:
             count = self._via_nets.get(cell)
             if count and count.get(conn.net_no):
@@ -1286,6 +1578,12 @@ class GridRouter:
         conn.wires = []
         conn.vias = []
         conn.routed = False
+        for anchor in conn.anchors:
+            hanging = self._dependents.get(anchor)
+            if hanging is not None:
+                hanging.discard(conn.index)
+        conn.anchors = frozenset()
+        conn.copper = frozenset()
         conn.rip_count += 1
         self._settle(conn, +1)
 
@@ -1308,12 +1606,13 @@ class GridRouter:
             owner = self._cell_owner.get((cx, cy, cl))
             if owner is not None and conns[owner].net_no != net_no:
                 owners.add(owner)
-            via_owner = self._via_owner.get((cx, cy))
-            if via_owner is not None and conns[via_owner].net_no != net_no:
-                owners.add(via_owner)
+            owners.update(self._via_others((cx, cy), net_no, conns))
             for i in self._halo.get((cx, cy, cl), ()):
                 if conns[i].net_no != net_no:
                     owners.add(i)
+            for i in self._stub_near.get((cx, cy, cl), ()):
+                if conns[i].net_no != net_no:
+                    owners.add(i)
         return owners
 
     # --- pin access ---------------------------------------------------------
@@ -1360,6 +1659,74 @@ class GridRouter:
                 return self.access_cost
         return 0.0
 
+    # --- negotiated congestion --------------------------------------------
+
+    def _congestion(self, node: Node, net_no: int) -> float:
+        """History of a contested cell, plus while negotiating the price of
+        sharing it with the other nets on it now."""
+        cost = self._history.get(node, 0.0)
+        if self._present is not None:
+            users = self._present.get(node)
+            if users:
+                others = len(users) - (1 if net_no in users else 0)
+                cost += self._present_cost * others
+        return cost
+
+    def _footprint(self, path: list[Node]) -> set[Node]:
+        """The nodes a route claims: its cells and their clearance halo on
+        its layer, and every via's footprint on all layers."""
+        wire_segs, via_cells = _split_path(path)
+        halo = [(0, 0), *self._halo_offsets]
+        nodes: set[Node] = set()
+        for layer, cells in wire_segs:
+            for cx, cy in cells:
+                for dx, dy in halo:
+                    nodes.add((cx + dx, cy + dy, layer))
+        for cell in via_cells:
+            for c in self._via_cells(cell):
+                for layer in self.layers:
+                    nodes.add((*c, layer))
+        return nodes
+
+    def _negotiate(self, order: list[_Connection], conns: list[_Connection]) -> None:
+        """Route every connection on the empty board ``self.negotiate`` times,
+        letting routes share cells at a price: the number of other nets on a
+        cell times a factor that doubles every round, plus the cell's history,
+        which grows by one for every extra net each round it stays shared.
+        Only the history is kept; the board is left empty."""
+        present: dict[Node, dict[int, int]] = {}
+        claimed: dict[int, set[Node]] = {}
+        ends = [(c, c.a_end, c.b_end) for c in conns]
+        self._present, self._present_cost = present, 0.5
+        try:
+            for _ in range(self.negotiate):
+                for conn in order:
+                    for node in claimed.pop(conn.index, ()):
+                        users = present[node]
+                        users[conn.net_no] -= 1
+                        if not users[conn.net_no]:
+                            del users[conn.net_no]
+                    path = self._search(conn, allow_ripup=False, conns=conns)
+                    if path is None:
+                        continue
+                    nodes = self._footprint(path)
+                    claimed[conn.index] = nodes
+                    for node in nodes:
+                        users = present.setdefault(node, {})
+                        users[conn.net_no] = users.get(conn.net_no, 0) + 1
+                shared = 0
+                for node, users in present.items():
+                    if len(users) > 1:
+                        shared += 1
+                        self._history[node] = self._history.get(node, 0.0) + len(users) - 1
+                if not shared:
+                    break
+                self._present_cost *= 2
+        finally:
+            self._present = None
+            for conn, a_end, b_end in ends:  # the search picks ends; undo that
+                conn.a_end, conn.b_end = a_end, b_end
+
     # --- passes -------------------------------------------------------------
 
     def route(self) -> RouteResult:
@@ -1383,6 +1750,8 @@ class GridRouter:
         if self.route_first:
             # stable: the promoted keep their order among themselves, as do the rest
             order.sort(key=lambda c: (c.net_no, *_ends_of(c)) not in self.route_first)
+        if self.negotiate:
+            self._negotiate(order, conns)
         for _ in range(passes):
             changed = False
             for conn in order:
@@ -1430,7 +1799,7 @@ class GridRouter:
                     crossed |= self._stub_owners(
                         end, node[:2], node[2], conn.net_no, conns, self._conn_half(conn)
                     )
-            victims = [conns[i] for i in sorted(crossed)]
+            victims = self._with_dependents([conns[i] for i in sorted(crossed)], conns)
             if self.rollback:
                 return self._ripup_transaction(conn, path, victims, conns)
             for victim in victims:
@@ -1441,7 +1810,7 @@ class GridRouter:
     def _ripup_transaction(self, conn, path, victims, conns) -> bool:
         """Route ``conn`` through ``victims``, reroute them at once in free
         space, and undo it all if fewer connections end up routed."""
-        saved = [(v, v.path, v.a_end, v.b_end, v.rip_count) for v in victims]
+        saved = [(v, v.path, v.a_end, v.b_end, v.rip_count, v.anchors) for v in victims]
         own_rips = conn.rip_count
         for victim in victims:
             self._rip(victim)
@@ -1459,8 +1828,8 @@ class GridRouter:
                 self._rip(victim)
         self._rip(conn)
         conn.rip_count = own_rips
-        for victim, old_path, a_end, b_end, rips in saved:
-            victim.a_end, victim.b_end = a_end, b_end
+        for victim, old_path, a_end, b_end, rips, anchors in saved:
+            victim.a_end, victim.b_end, victim.anchors = a_end, b_end, anchors
             self._commit(victim, old_path)
             victim.rip_count = rips
         return False
@@ -1482,8 +1851,11 @@ class GridRouter:
                 planes_by_net.setdefault(zone.net_nos[0], []).append(zone)
         plane_ids = frozenset(id(z) for zs in planes_by_net.values() for z in zs)
         conns: list[_Connection] = []
+        self._plane_nets: set[int] = set()
         nets = set(pins_by_net) | set(zones_by_net) | set(planes_by_net)
         # deterministic: fewer-pin nets first, then by net number
+        if self.only_nets is not None:
+            nets &= self.only_nets
         for net_no in sorted(nets, key=lambda n: (len(pins_by_net.get(n, [])), n)):
             zones = zones_by_net.get(net_no, []) + planes_by_net.get(net_no, [])
             groups = _connected_groups(
@@ -1494,12 +1866,23 @@ class GridRouter:
                 # a plane net: every other group goes straight to the plane
                 # (usually a stub and a via), not pad to pad across the board
                 pairs = [(g, hubs[0]) for g in groups if g is not hubs[0]]
+                self._plane_nets.add(net_no)
+            elif self.tree:
+                pairs = _spanning_pairs(groups)
             else:
                 pairs = list(zip(groups, groups[1:], strict=False))
             for ga, gb in pairs:
                 conn = _Connection(len(conns), net_no, _first(ga[0]), _first(gb[0]))
                 conn.a_group, conn.b_group = ga, gb
                 conns.append(conn)
+        self._net_conns: dict[int, list[_Connection]] = {}
+        for conn in conns:
+            self._net_conns.setdefault(conn.net_no, []).append(conn)
+        if self._bounds is not None:
+            self._outside = {
+                c.index for c in conns
+                if not (_group_inside(c.a_group, self._bounds) and _group_inside(c.b_group, self._bounds))
+            }
         return conns
 
     def _fixed_pieces(self, net_no: int) -> list[_FixedPiece]:
@@ -1549,18 +1932,22 @@ class GridRouter:
         return wide, narrowed
 
     def _snapshot(self, conns: list[_Connection]) -> list[tuple]:
+        # in commit order, so a connection teed onto another comes after it;
+        # its anchors as positions in this list
+        routed = sorted((c for c in conns if c.routed), key=lambda c: (c.seq, c.index))
+        position = {c.index: i for i, c in enumerate(routed)}
         return [
             (c.net_no, [(layer, list(pts)) for layer, pts in c.wires], list(c.vias),
-             (*_ends_of(c), self._left_to_zone(c)))
-            for c in conns
-            if c.routed
+             (*_ends_of(c), self._left_to_zone(c)),
+             tuple(sorted(position[a] for a in c.anchors if a in position)))
+            for c in routed
         ]
 
     def _result_from(self, snapshot, unrouted: int) -> RouteResult:
         result = RouteResult(self.half_width)
         written: set[tuple[int, IntPoint]] = set()
         result.unrouted = unrouted
-        for net_no, wires, vias, ends in snapshot:
+        for net_no, wires, vias, ends, anchors in snapshot:
             for layer, points in wires:
                 result.add_wire(net_no, layer, points)
             for location in vias:
@@ -1571,7 +1958,8 @@ class GridRouter:
                 result.add_via(net_no, location)
             result.connections.append((net_no, wires, vias))
             result.connection_ends.append(ends)
-        routed = {ends[:2] + (net_no,) for net_no, _w, _v, ends in snapshot}
+            result.connection_anchors.append(anchors)
+        routed = {ends[:2] + (net_no,) for net_no, _w, _v, ends, _a in snapshot}
         result.failed = [
             (c.net_no, *_ends_of(c), self._left_to_zone(c))
             for c in self._conns
@@ -1584,6 +1972,53 @@ def _first(items):
     return items[0] if items else None
 
 
+def _anchors(path, starts, goals, a_tree, b_tree) -> frozenset[int]:
+    """What a found path relies on: the connections between the copper it
+    starts or ends on and its own groups."""
+    found: set[int] = set()
+    if starts.get(path[0]) is None and path[0] in a_tree:
+        found |= a_tree[path[0]]
+    if goals.get(path[-1]) is None and path[-1] in b_tree:
+        found |= b_tree[path[-1]]
+    return frozenset(found)
+
+
+def _group_points(group) -> list[tuple[int, int]]:
+    pins, zones = group
+    if pins:
+        return [(p.location.x, p.location.y) for p in pins]
+    points = []
+    for zone in zones:
+        box = zone.bounding_box()
+        points.append(((box.ll.x + box.ur.x) // 2, (box.ll.y + box.ur.y) // 2))
+    return points or [(0, 0)]
+
+
+def _spanning_pairs(groups) -> list[tuple]:
+    """A minimum spanning tree over a net's groups (Prim, Manhattan distance
+    between their nearest pins), as (in the tree, joining it) pairs: each
+    connection joins the nearest group not yet joined, not the next in pin
+    order."""
+    if len(groups) < 2:
+        return []
+    points = [_group_points(g) for g in groups]
+
+    def gap(i: int, j: int) -> int:
+        return min(abs(ax - bx) + abs(ay - by) for ax, ay in points[i] for bx, by in points[j])
+
+    best = {j: (gap(0, j), 0) for j in range(1, len(groups))}
+    pairs = []
+    while best:
+        j = min(best, key=lambda k: (best[k][0], k))
+        _, i = best.pop(j)
+        pairs.append((groups[i], groups[j]))
+        for k in best:
+            d = gap(j, k)
+            if d < best[k][0]:
+                best[k] = (d, j)
+    return pairs
+
+
 def _group_label(group) -> str:
     pins, zones = group
     parts = [f"{p.component_ref}-{p.name}" for p in pins[:3]]
@@ -1593,6 +2028,19 @@ def _group_label(group) -> str:
     return "/".join(parts) or "?"
 
 
+def _group_inside(group, bounds: IntBox) -> bool:
+    """A group has a pin inside ``bounds``, or a zone reaching into it."""
+    pins, zones = group
+    if any(bounds.ll.x <= p.location.x <= bounds.ur.x and bounds.ll.y <= p.location.y <= bounds.ur.y
+           for p in pins):
+        return True
+    for zone in zones:
+        box = zone.bounding_box()
+        if box.ll.x <= bounds.ur.x and bounds.ll.x <= box.ur.x and box.ll.y <= bounds.ur.y and bounds.ll.y <= box.ur.y:
+            return True
+    return False
+
+
 def _ends_of(conn) -> tuple[str, str]:
     """A readable description of what a connection joins."""
     return _group_label(conn.a_group), _group_label(conn.b_group)
@@ -1779,10 +2227,14 @@ def route_board(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    negotiate: int = 0,
     rollback: bool = True,
+    tree_nets: bool = True,
     net_widths: dict[int, int] | None = None,
     via_drill: int | None = None,
     hole_to_hole: int = 0,
+    only_nets: frozenset | None = None,
+    bounds: IntBox | None = None,
 ) -> RouteResult:
     """Convenience wrapper: build a :class:`GridRouter` and route the board."""
     router = GridRouter(
@@ -1801,9 +2253,13 @@ def route_board(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        negotiate=negotiate,
         rollback=rollback,
+        tree_nets=tree_nets,
         net_widths=net_widths,
         via_drill=via_drill,
         hole_to_hole=hole_to_hole,
+        only_nets=only_nets,
+        bounds=bounds,
     )
     return router.route()

src/freeroute/route/pipeline.py

@@ -13,6 +13,7 @@ to DSN units (dividing by the resolution) for the SES ``(wire (path ...))`` and
 from __future__ import annotations
 
 import re
+import time
 
 from freeroute.board import build_board
 from freeroute.dsn import DsnBoard, parse_dsn
@@ -21,6 +22,7 @@ from freeroute.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 .window import window_reroute as window_reroute_stage
 
 __all__ = ["route", "route_dsn_board", "build_routing_result"]
 
@@ -118,8 +120,10 @@ def route_dsn_board(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    negotiate: int = 0,
     hole_to_hole_mm: float = 0.25,
     rollback: bool = True,
+    tree_nets: bool = True,
 ) -> 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
@@ -143,7 +147,9 @@ def route_dsn_board(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        negotiate=negotiate,
         rollback=rollback,
+        tree_nets=tree_nets,
         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,
@@ -196,8 +202,10 @@ def build_routing_result(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    negotiate: int = 0,
     hole_to_hole_mm: float = 0.25,
     rollback: bool = True,
+    tree_nets: bool = True,
 ) -> RoutingResult:
     """Route ``dsn`` (grid track) and convert to a DSN-unit RoutingResult."""
     route, scale, layer_names = route_dsn_board(
@@ -205,8 +213,10 @@ def build_routing_result(
         edge_clearance_mm=edge_clearance_mm, resolution=resolution, seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        negotiate=negotiate,
         hole_to_hole_mm=hole_to_hole_mm,
         rollback=rollback,
+        tree_nets=tree_nets,
     )
     return _to_routing_result(route, dsn, scale, layer_names)
 
@@ -225,8 +235,15 @@ def route_dsn_board_exact(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    negotiate: int = 0,
     hole_to_hole_mm: float = 0.25,
     rollback: bool = True,
+    tree_nets: bool = True,
+    window_reroute: int = 0,
+    window_resolution: int = 4,
+    window_margin_mm: float = 1.5,
+    window_budget: float = 0.25,
+    window_cap: int = 40,
 ) -> 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.
@@ -238,27 +255,48 @@ def route_dsn_board_exact(
     edge_clearance_board = _mm_to_board(dsn, scale, edge_clearance_mm)
     width_board = round(_rule_width_dsn(dsn) * scale)
     clearance_board = round(_rule_clearance_dsn(dsn) * scale)
+    # the settings a window re-route repeats, at its own resolution
+    common = {
+        "heuristic_weight": heuristic_weight,
+        "via_half": _via_half_board(dsn, scale),
+        "edge_clearance": edge_clearance_board,
+        "trace_width": width_board,
+        "clearance": clearance_board,
+        "layers": layers,
+        "max_passes": max_passes,
+        "rip_up": rip_up,
+        "shove": shove,
+        "diagonal": diagonal,
+        "rollback": rollback,
+        "tree_nets": tree_nets,
+        "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,
+    }
+    started = time.monotonic()
     exact = route_board_exact(
         board,
         resolution=resolution,
-        heuristic_weight=heuristic_weight,
-        via_half=_via_half_board(dsn, scale),
-        edge_clearance=edge_clearance_board,
-        trace_width=width_board,
-        clearance=clearance_board,
-        layers=layers,
-        max_passes=max_passes,
-        rip_up=rip_up,
-        shove=shove,
-        diagonal=diagonal,
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
-        rollback=rollback,
-        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,
+        negotiate=negotiate,
+        **common,
     )
+    if window_reroute > 0:
+        via_half = common["via_half"] or max(width_board // 2, 1)
+        exact.result = window_reroute_stage(
+            dsn, exact.result, common,
+            rounds=window_reroute,
+            resolution=max(int(window_resolution), resolution),
+            margin=_mm_to_board(dsn, scale, window_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(window_budget), 0.0) * (time.monotonic() - started),
+            max_windows=window_cap,
+        )
     return exact, scale, [layer.name for layer in dsn.layers]
 
 
@@ -276,8 +314,15 @@ def build_exact_routing_result(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    negotiate: int = 0,
     hole_to_hole_mm: float = 0.25,
     rollback: bool = True,
+    tree_nets: bool = True,
+    window_reroute: int = 0,
+    window_resolution: int = 4,
+    window_margin_mm: float = 1.5,
+    window_budget: float = 0.25,
+    window_cap: int = 40,
 ) -> RoutingResult:
     """Route ``dsn`` (exact track) and convert to a DSN-unit RoutingResult."""
     exact, scale, layer_names = route_dsn_board_exact(
@@ -293,8 +338,15 @@ def build_exact_routing_result(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        negotiate=negotiate,
         hole_to_hole_mm=hole_to_hole_mm,
         rollback=rollback,
+        tree_nets=tree_nets,
+        window_reroute=window_reroute,
+        window_resolution=window_resolution,
+        window_margin_mm=window_margin_mm,
+        window_budget=window_budget,
+        window_cap=window_cap,
     )
     return _to_routing_result(exact.result, dsn, scale, layer_names)
 

src/freeroute/route/window.py

@@ -0,0 +1,248 @@
+"""Window re-route: a last stage for the connections still unrouted.
+
+Around each stuck connection a window is cut: the box of its two end pins
+plus a margin. Every net whose routed copper lies wholly inside it is
+ripped; everything else stays, as fixed copper. The window is then routed
+again on its own, on a finer grid than the whole board can afford, the
+stuck connection's net and the ripped nets only. The result is kept only
+if fewer connections are left unrouted than before; otherwise the board is
+as it was. Each round doubles the margin for the connections still stuck.
+
+It is a last stage, so it is kept cheap: a window's board holds only what
+the window needs (every pin and piece of copper of the nets it reroutes,
+so their connectivity is unchanged, and of the other items only those near
+the window), the smallest windows go first, at most ``max_windows`` run per
+round, and no new window starts once ``budget_s`` seconds are spent.
+
+What makes it differ from re-running the same search near the failure: the
+finer grid finds gaps the board's grid steps over, and the ripped nets go in
+again in a new order around the stuck one. A finer grid on the whole board
+costs routes elsewhere (its cells are slower and its order changes); inside
+a small window it only ever replaces what it can improve.
+"""
+
+from __future__ import annotations
+
+import time
+from typing import Any
+
+from freeroute.board import BasicBoard, build_board
+from freeroute.board.items import ObstacleArea, Pin, Trace, Via
+from freeroute.dsn import DsnBoard
+from freeroute.geometry import IntBox, IntPoint
+
+from .exact_router import route_board_exact
+from .grid_router import RouteResult
+
+Copper = tuple[list[tuple[int, list[IntPoint]]], list[IntPoint]]
+
+
+def _pin_labels(board) -> dict[tuple[int, str], IntPoint]:
+    """Each pin's location by (net, label), the label a failure names it by."""
+    found: dict[tuple[int, str], IntPoint] = {}
+    for pin in board.get_pins():
+        for net in pin.net_nos:
+            found.setdefault((net, f"{pin.component_ref}-{pin.name}"), pin.location)
+    return found
+
+
+def _end_point(labels, net: int, label: str) -> IntPoint | None:
+    """Where a failure's end is: the first pin its label names."""
+    return labels.get((net, label.split("/")[0]))
+
+
+def _inside(copper: Copper, window: IntBox) -> bool:
+    wires, vias = copper
+    points = [p for _layer, path in wires for p in path] + list(vias)
+    return bool(points) and all(
+        window.ll.x <= p.x <= window.ur.x and window.ll.y <= p.y <= window.ur.y for p in points
+    )
+
+
+def _item_box(item) -> IntBox | None:
+    if isinstance(item, (Pin, Via)):
+        return item.shape.bounding_box() if item.shape is not None else None
+    if isinstance(item, ObstacleArea):
+        return item.bounding_box()
+    if isinstance(item, Trace) and item.corners:
+        h = item.half_width
+        xs, ys = [p.x for p in item.corners], [p.y for p in item.corners]
+        return IntBox(min(xs) - h, min(ys) - h, max(xs) + h, max(ys) + h)
+    return None
+
+
+def _meets(box: IntBox | None, view: IntBox) -> bool:
+    return box is not None and box.ll.x <= view.ur.x and view.ll.x <= box.ur.x and (
+        box.ll.y <= view.ur.y and view.ll.y <= box.ur.y
+    )
+
+
+def _path_box(path: list[IntPoint], grow: int) -> IntBox:
+    xs, ys = [p.x for p in path], [p.y for p in path]
+    return IntBox(min(xs) - grow, min(ys) - grow, max(xs) + grow, max(ys) + grow)
+
+
+def _window_board(
+    base: BasicBoard, base_items: list, view: IntBox, affected: set[int],
+    copper: dict[int, Copper], keep: set[int], half: dict[int, int], default_half: int,
+    via_half: int, via_drill: int, layers: list[int], via_name: str,
+) -> BasicBoard:
+    """The board a window is routed on: the base board's items of the nets
+    being rerouted and those near ``view``, plus the routed copper being kept
+    (all of an affected net's, so its connectivity is the whole board's, and
+    of other nets only what is near ``view``), as fixed copper."""
+    board = BasicBoard(base.layer_structure, base.nets, base.clearance_matrix, base.bounding_box)
+    board.outline = base.outline
+    for item, box in base_items:
+        if (item.net_nos and item.net_nos[0] in affected) or _meets(box, view):
+            board.insert(item)
+    for net in keep:
+        wires, vias = copper.get(net, ([], []))
+        width = half.get(net, default_half)
+        mine = net in affected
+        for layer, path in wires:
+            if len(path) >= 2 and (mine or _meets(_path_box(path, width), view)):
+                board.insert(Trace(net_nos=[net], fixed=True, layer=layer, half_width=width, corners=list(path)))
+        for location in dict.fromkeys(vias):
+            shape = IntBox(location.x - via_half, location.y - via_half,
+                           location.x + via_half, location.y + via_half)
+            if mine or _meets(shape, view):
+                board.insert(Via(
+                    net_nos=[net], fixed=True, padstack_name=via_name, drill=via_drill,
+                    location=location, layers=list(layers), shape=shape,
+                ))
+    return board
+
+
+def _open(failed) -> list:
+    """Failures that are real opens, not connections left to a zone fill."""
+    return [f for f in failed if not (len(f) > 3 and f[3])]
+
+
+def window_reroute(
+    dsn: DsnBoard,
+    result: RouteResult,
+    route_args: dict[str, Any],
+    *,
+    rounds: int,
+    resolution: int,
+    margin: int,
+    via_half: int,
+    via_drill: int,
+    via_name: str,
+    budget_s: float | None = None,
+    max_windows: int = 40,
+) -> RouteResult:
+    """Re-route a window around each still-failing connection; keep only gains.
+
+    ``route_args`` are the exact engine's settings for the whole board (width,
+    clearance, layers, shove, ...); the window runs them at ``resolution``.
+    ``margin`` is the first round's window margin in board units. No new
+    window starts once ``budget_s`` seconds have gone by (None: no limit),
+    and at most ``max_windows`` run per round."""
+    started = time.monotonic()
+    if rounds < 1 or not _open(result.failed):
+        return result
+    default_half = result.half_width
+    copper: dict[int, Copper] = {
+        net: (list(result.wires.get(net, [])), list(result.vias.get(net, [])))
+        for net in set(result.wires) | set(result.vias)
+    }
+    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
+    ]
+    labels = _pin_labels(base)
+    # the copper a window's routing can feel from outside it
+    context = 2 * (route_args["trace_width"] + route_args["clearance"]) + 2 * via_half + (
+        route_args.get("edge_clearance") or 0
+    )
+
+    def window_of(entry, reach: int) -> IntBox | None:
+        ends = [_end_point(labels, entry[0], label) for label in entry[1:3]]
+        ends = [p for p in ends if p is not None]
+        if not ends:
+            return None
+        return IntBox(
+            min(p.x for p in ends) - reach, min(p.y for p in ends) - reach,
+            max(p.x for p in ends) + reach, max(p.y for p in ends) + reach,
+        )
+
+    def area(box: IntBox | None) -> float:
+        return float("inf") if box is None else (box.ur.x - box.ll.x) * (box.ur.y - box.ll.y)
+
+    changed = out_of_time = False
+    for rnd in range(rounds):
+        reach = margin * (2 ** rnd)
+
+        # the cheap wins first: the smallest windows
+        todo = sorted(_open(list(failed)), key=lambda f: area(window_of(f, reach)))
+        for entry in todo[:max(int(max_windows), 1)]:
+            if budget_s is not None and time.monotonic() - started >= budget_s:
+                out_of_time = True
+                break
+            if entry not in failed:
+                continue  # an earlier window routed it
+            net = entry[0]
+            window = window_of(entry, reach)
+            if window is None:
+                continue
+            victims = {n for n, c in copper.items() if _inside(c, window)}
+            affected = victims | {net}
+            before = _open(f for f in failed if f[0] in affected)
+            keep = set(copper) - victims
+            view = IntBox(window.ll.x - context, window.ll.y - context,
+                          window.ur.x + context, window.ur.y + context)
+            board = _window_board(base, base_items, view, affected, copper, keep, half,
+                                  default_half, via_half, via_drill, layers, via_name)
+            sub = route_board_exact(
+                board, **route_args, resolution=resolution,
+                only_nets=frozenset(affected), bounds=window,
+                route_first=frozenset((f[0], f[1], f[2]) for f in before),
+            ).result
+            after = _open(f for f in sub.failed if f[0] in affected)
+            if len(after) >= len(before):
+                continue
+            # the window board left out what lies away from it, so copper
+            # reaching out of the window was never checked against it
+            if any(not _inside((sub.wires.get(n, []), sub.vias.get(n, [])), window)
+                   for n in affected if sub.wires.get(n) or sub.vias.get(n)):
+                continue
+            # a net keeping some of its copper is written at one width: the
+            # window's new copper has to have gone in at that width too
+            if any(
+                n not in victims and copper.get(n) and (sub.wires.get(n) or sub.vias.get(n))
+                and sub.net_half.get(n, default_half) != half.get(n, default_half)
+                for n in affected
+            ):
+                continue
+            for n in affected:
+                kept_wires, kept_vias = copper.get(n, ([], [])) if n not in victims else ([], [])
+                copper[n] = (kept_wires + sub.wires.get(n, []), kept_vias + sub.vias.get(n, []))
+                if n in victims:
+                    half.pop(n, None)
+                    if n in sub.net_half:
+                        half[n] = sub.net_half[n]
+            failed = [f for f in failed if f[0] not in affected] + [
+                f for f in sub.failed if f[0] in affected
+            ]
+            changed = True
+        if out_of_time or not _open(failed):
+            break
+
+    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_axis_escapes.py

@@ -0,0 +1,113 @@
+"""Pins of a fine-pitch part turned off the grid axes leave along their pads.
+
+A QFN at 45 degrees has no straight exit: every horizontal or vertical step
+from a pin passes its neighbours closer than the clearance (0.35 mm away on
+each axis at 0.5 mm pitch). The grid leaves along the pad's own axis first,
+past the pin row, and the exact engine checks that slanted leg on its exact
+copper. Found on th-eda's lift ESC, where a QFN-24 at 45 degrees left 15
+connections unroutable on an empty board.
+"""
+
+from __future__ import annotations
+
+import math
+
+import pytest
+
+from freeroute.board import build_board
+from freeroute.dsn import parse_dsn
+from freeroute.geometry import IntPoint, overlaps_2d, segment_slab
+from freeroute.route.grid_router import GridRouter
+from freeroute.route.pipeline import (
+    _rule_clearance_dsn,
+    _rule_width_dsn,
+    _via_half_board,
+    build_exact_routing_result,
+)
+
+
+def _qfn_side_dsn(rotation: float) -> str:
+    """Two rows of five 0.25 x 0.8 mm pads at 0.5 mm pitch (one side of a
+    QFN and its opposite side), turned by ``rotation``; each pin of the top
+    row is its own net, routed to a pad 4.5 mm out, the pads fanned 1.5 mm
+    apart."""
+    cx, cy = 100000, -100000
+    t = math.radians(rotation)
+    out = (-math.sin(t), math.cos(t))  # the pads' outward axis after turning
+    along = (math.cos(t), math.sin(t))  # the pin row
+    pins, targets, nets = [], [], []
+    for i in range(5):
+        x = -1000 + 500 * i
+        pins += [f"(pin P {i + 1} {x} 1000)", f"(pin P {i + 6} {x} -1000)"]
+        px = cx + x * math.cos(t) - 1000 * math.sin(t)
+        py = cy + x * math.sin(t) + 1000 * math.cos(t)
+        spread = 1500 * (i - 2) - x  # fan the far pads out to 1.5 mm apart
+        tx = px + 4500 * out[0] + spread * along[0]
+        ty = py + 4500 * out[1] + spread * along[1]
+        targets.append(f"(place T{i + 1} {round(tx)} {round(ty)} front 0)")
+        nets.append(f"(net N{i} (pins U1-{i + 1} T{i + 1}-1))")
+    return f"""(pcb qfn (parser) (resolution um 10) (unit um)
+  (structure
+    (layer F.Cu (type signal)) (layer B.Cu (type signal))
+    (boundary (path pcb 0  115000 -115000  85000 -115000  85000 -85000  115000 -85000
+      115000 -115000))
+    (via "Via[0-1]_450:200_um")
+    (rule (width 150) (clearance 150)))
+  (placement
+    (component Q (place U1 {cx} {cy} front {rotation}))
+    (component T {" ".join(targets)}))
+  (library
+    (image Q {" ".join(pins)})
+    (image T (pin t 1 0 0))
+    (padstack P (shape (rect F.Cu -125 -400 125 400)) (attach off))
+    (padstack t (shape (rect F.Cu -300 -300 300 300)) (attach off))
+    (padstack "Via[0-1]_450:200_um" (shape (circle F.Cu 450)) (shape (circle B.Cu 450))
+      (attach off)))
+  (network {" ".join(nets)}))"""
+
+
+@pytest.mark.parametrize("rotation", [45, 30, -45])
+def test_a_turned_fine_pitch_part_gets_its_pins_out(rotation):
+    result = build_exact_routing_result(parse_dsn(_qfn_side_dsn(rotation)), resolution=2, shove=True)
+    assert result.unrouted == []
+
+
+def test_the_exit_runs_along_the_pad_axis_and_clears_the_neighbours():
+    dsn = parse_dsn(_qfn_side_dsn(45))
+    s = dsn.resolution.value
+    board = build_board(dsn)
+    router = GridRouter(
+        board,
+        trace_width=round(_rule_width_dsn(dsn) * s),
+        clearance=round(_rule_clearance_dsn(dsn) * s),
+        via_half=_via_half_board(dsn, s),
+        orthogonal=True,
+    )
+    pins = {p.name: p for p in board.get_pins() if p.component_ref == "U1"}
+    pin = pins["3"]
+    exit_point = router._axis_exit(pin)
+    assert exit_point is not None
+    dx, dy = exit_point.x - pin.location.x, exit_point.y - pin.location.y
+    assert abs(abs(dx) - abs(dy)) <= 2  # along the 45-degree axis
+    leg = segment_slab(pin.location, exit_point, router.half_width + router.clearance)
+    for name in ("2", "4"):
+        assert not overlaps_2d(leg, pins[name].shape)
+
+
+def test_a_pad_on_the_grid_axes_keeps_the_usual_exits():
+    dsn = parse_dsn(_qfn_side_dsn(0))
+    s = dsn.resolution.value
+    board = build_board(dsn)
+    router = GridRouter(board, trace_width=round(_rule_width_dsn(dsn) * s),
+                        clearance=round(_rule_clearance_dsn(dsn) * s), via_half=_via_half_board(dsn, s))
+    pin = next(p for p in board.get_pins() if p.component_ref == "U1" and p.name == "3")
+    assert router._axis_exit(pin) is None
+
+
+def test_a_slanted_slab_is_tight_where_a_bounding_box_is_not():
+    slab = segment_slab(IntPoint(0, 0), IntPoint(10000, 10000), 750)
+    # a point beside the diagonal but inside its bounding box
+    from freeroute.geometry import IntBox
+
+    assert not overlaps_2d(slab, IntBox(8000, 0, 8100, 100))
+    assert overlaps_2d(slab, IntBox(4900, 4900, 5100, 5100))

tests/route/test_grid_exact_agreement.py

@@ -143,11 +143,48 @@ def test_a_shared_via_keeps_its_footprint_when_one_user_is_ripped():
     router._rip(first)
 
     assert second.routed and via in second.via_cells
-    assert all(router._via_owner.get(c) == second.index for c in footprint)
+    assert all(router._via_claims.get(c) == [second.index] for c in footprint)
     # another net still keeps its distance from the via that is left
     assert all(router._enter_cost_base(c, 0, sig.net_no, False, conns) is None for c in footprint)
 
 
+def test_a_route_through_a_shared_via_rips_every_user():
+    """Two connections of a net share a via. Another net routed through it
+    in rip-up mode has to rip both, or the one left keeps its via under the
+    new trace and the exact check throws one of them out."""
+    dsn = parse_dsn(_SHARED_VIA)
+    s = dsn.resolution.value
+    router = GridRouter(
+        build_board(dsn),
+        trace_width=round(_rule_width_dsn(dsn) * s),
+        clearance=round(_rule_clearance_dsn(dsn) * s),
+        via_half=_via_half_board(dsn, s),
+    )
+    conns = router._conns = router._build_connections()
+    gnd = [c for c in conns if len({c.a.component_ref, c.b.component_ref} & {"G1", "G2", "G3"})]
+    sig = next(c for c in conns if c not in gnd)
+    first, second = gnd
+    g3 = router._cell_of(next(p for p in router.board.get_pins() if p.component_ref == "G3").location)
+    via = (g3[0] - 10, g3[1])
+
+    def through_via(conn):
+        a, b = router._cell_of(conn.a.location), router._cell_of(conn.b.location)
+        return _line(a, via, 0) + _line(via, b, 1)
+
+    router._commit(first, through_via(first))
+    router._commit(second, through_via(second))
+    # the via's copper alone: footprint cells no trace or trace halo covers
+    crossing = [
+        node
+        for c in router._via_cells(via)
+        for node in ((*c, 0), (*c, 1))
+        if node not in router._cell_owner and node not in router._halo
+    ]
+    assert crossing
+
+    assert router._crossed_owners(crossing, sig.net_no, conns) == {first.index, second.index}
+
+
 # --- a wider net class --------------------------------------------------------
 
 _WIDE = """(pcb wide (parser) (resolution um 10) (unit um)
@@ -225,3 +262,23 @@ def test_a_pad_cell_check_uses_the_rotated_outline():
         c = router._cell_center(cell)
         square = IntBox(c.x - margin, c.y - margin, c.x + margin, c.y + margin)
         assert oval.shape.intersection(square).dimension() != 2
+
+
+def test_a_via_by_a_chamfered_corner_is_judged_round():
+    """The grid keeps a via's centre its radius plus the edge clearance from
+    the outline. The exact check used the via's square, whose corner reaches
+    past a 45-degree chamfer where the round via does not."""
+    from freeroute.board.outline import BoardOutline
+    from freeroute.geometry import IntBox, IntPoint
+    from freeroute.route.exact_router import _inside_outline
+
+    # a 10 mm square with its lower-left corner cut at 45 degrees
+    outline = BoardOutline([IntPoint(*p) for p in
+                            [(30, 0), (100, 0), (100, 100), (0, 100), (0, 30)]])
+    half, edge = 4, 1
+    via = IntPoint(19, 20)  # its centre 6.4 from the chamfer x + y = 30
+    square = IntBox(via.x - half, via.y - half, via.x + half, via.y + half)
+    assert not outline.box_clear(square, edge)  # the square's corner: 0.7 away
+    assert _inside_outline(outline, [], [via], half + edge, edge)
+    # 4.2 from the chamfer: the round via itself is too close
+    assert not _inside_outline(outline, [], [IntPoint(18, 18)], half + edge, edge)

tests/route/test_negotiate.py

@@ -0,0 +1,65 @@
+"""--negotiate: PathFinder-style rounds on the empty board before routing."""
+
+from __future__ import annotations
+
+from pathlib import Path
+
+import pytest
+
+from freeroute.board import build_board
+from freeroute.dsn import parse_dsn
+from freeroute.route.grid_router import GridRouter
+from freeroute.route.pipeline import _rule_clearance_dsn, _rule_width_dsn, route_dsn_board
+
+FIXTURES = Path(__file__).resolve().parent.parent / "dsn" / "fixtures"
+
+
+def _router(name, negotiate):
+    dsn = parse_dsn((FIXTURES / name).read_text())
+    s = dsn.resolution.value
+    return GridRouter(
+        build_board(dsn),
+        trace_width=round(_rule_width_dsn(dsn) * s),
+        clearance=round(_rule_clearance_dsn(dsn) * s),
+        negotiate=negotiate,
+    )
+
+
+def test_negotiation_leaves_the_board_empty_and_the_ends_as_they_were():
+    router = _router("true_density.dsn", 3)
+    conns = router._conns = router._build_connections()
+    ends = [(c.a_end, c.b_end) for c in conns]
+    router._negotiate(list(conns), conns)
+    assert router._history  # a dense board has contested cells
+    assert not router._cell_owner and not router._halo and not router._via_claims
+    assert not any(c.routed for c in conns)
+    assert [(c.a_end, c.b_end) for c in conns] == ends
+    assert router._present is None
+
+
+def test_sharing_is_priced_only_for_other_nets():
+    router = _router("true_density.dsn", 1)
+    node = (3, 4, 0)
+    router._history[node] = 2.0
+    router._present, router._present_cost = {node: {7: 1, 9: 2}}, 0.5
+    assert router._congestion(node, 7) == pytest.approx(2.5)  # one other net
+    assert router._congestion(node, 5) == pytest.approx(3.0)  # two other nets
+    router._present = None
+    assert router._congestion(node, 5) == pytest.approx(2.0)  # history only, after
+
+
+@pytest.mark.parametrize("name", ["ripup_needed.dsn", "true_density.dsn", "kicad_routable.dsn"])
+def test_negotiated_routing_keeps_the_occupancy_honest(name):
+    """Only routed connections hold cells afterwards, as without negotiation."""
+    router = _router(name, 3)
+    router.route()
+    conns = router._conns
+    assert all(conns[i].routed for i in router._cell_owner.values())
+    assert all(conns[i].routed for claims in router._halo.values() for i in claims)
+
+
+def test_option_reaches_the_router_and_is_off_by_default():
+    text = (FIXTURES / "kicad_routable.dsn").read_text()
+    plain, _, _ = route_dsn_board(parse_dsn(text))
+    again, _, _ = route_dsn_board(parse_dsn(text), negotiate=0)
+    assert plain.unrouted == again.unrouted

tests/route/test_rollback.py

@@ -31,7 +31,7 @@ def test_occupancy_only_holds_routed_connections(name):
     router, _ = _routed_router(name)
     conns = router._conns
     assert all(conns[i].routed for i in router._cell_owner.values())
-    assert all(conns[i].routed for i in router._via_owner.values())
+    assert all(conns[i].routed for claims in router._via_claims.values() for i in claims)
     assert all(conns[i].routed for claims in router._halo.values() for i in claims)
 
 

tests/route/test_tree_nets.py

@@ -0,0 +1,170 @@
+"""Multi-pin nets: spanning-tree pairs, and connections that end on copper
+their net has already routed (a T into the tree)."""
+
+from __future__ import annotations
+
+import pytest
+
+from freeroute.board import build_board
+from freeroute.dsn import parse_dsn
+from freeroute.route import exact_router
+from freeroute.route.grid_router import GridRouter, RouteResult
+from freeroute.route.pipeline import _rule_clearance_dsn, _rule_width_dsn
+
+# P1 and P2 are nearest each other, so the tree pairs them first; P3 sits
+# under the middle of that leg, 50 mm below it and 90 mm from either pin.
+TEE = """(pcb "tee.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)))
+    (boundary (path pcb 0  0 0  200000 0  200000 -100000  0 -100000  0 0))
+    (rule (width 2000) (clearance 2000))
+  )
+  (library
+    (padstack Rect_Pad (shape (rect F.Cu -1000 -1000 1000 1000)) (attach off))
+    (image PAD (pin Rect_Pad 1 0 0))
+  )
+  (placement
+    (component PAD
+      (place P1 60000 -20000 front 0)
+      (place P2 140000 -20000 front 0)
+      (place P3 100000 -70000 front 0)
+    )
+  )
+  (network
+    (net N (pins P1-1 P2-1 P3-1))
+    (class default (rule (width 2000) (clearance 2000)))
+  )
+  (wiring)
+)
+"""
+
+
+def _router(tree_nets=True, text=TEE):
+    dsn = parse_dsn(text)
+    s = dsn.resolution.value
+    return GridRouter(
+        build_board(dsn),
+        trace_width=round(_rule_width_dsn(dsn) * s),
+        clearance=round(_rule_clearance_dsn(dsn) * s),
+        orthogonal=True,
+        tree_nets=tree_nets,
+    )
+
+
+def test_pairs_follow_a_spanning_tree_not_the_pin_order():
+    router = _router()
+    conns = router._build_connections()
+    pairs = [(c.a.component_ref, c.b.component_ref) for c in conns]
+    assert pairs == [("P1", "P2"), ("P1", "P3")]
+    chain = _router(tree_nets=False)._build_connections()
+    assert [(c.a.component_ref, c.b.component_ref) for c in chain] == [("P1", "P2"), ("P2", "P3")]
+
+
+def test_the_third_pin_tees_into_the_first_leg():
+    router = _router()
+    result = router.route()
+    first, second = router._conns
+    assert result.unrouted == 0
+    # the second connection starts on the first one's copper, mid-leg
+    start = second.path[0]
+    assert start in first.copper and second.a_end is None
+    assert second.anchors == {first.index}
+    assert router._dependents[first.index] == {second.index}
+    assert abs(router._cell_center(start[:2]).x - 1_000_000) <= router.step
+    # and so its copper is the 50 mm drop, not 90 mm back to a pin
+    assert len(second.path) < len(router._conns[0].path)
+
+
+def test_without_trees_each_connection_ends_on_a_pin():
+    router = _router(tree_nets=False)
+    router.route()
+    assert all(c.anchors == frozenset() for c in router._conns)
+    assert all(c.a_end is not None and c.b_end is not None for c in router._conns)
+
+
+def test_ripping_an_anchor_takes_what_hangs_on_it():
+    router = _router()
+    router.route()
+    first, second = router._conns
+    victims = router._with_dependents([first], router._conns)
+    assert victims == [first, second]  # anchors first, as committed
+    for victim in victims:
+        router._rip(victim)
+    assert not first.routed and not second.routed
+    assert not router._dependents.get(first.index)
+    assert not router._cell_owner
+
+
+def test_the_snapshot_lists_anchors_before_what_hangs_on_them():
+    router = _router()
+    result = router.route()
+    assert result.connection_anchors == [(), (0,)]
+
+
+def test_the_exact_engine_drops_a_tee_whose_anchor_it_rejects(monkeypatch):
+    """A connection teed onto copper the exact check refuses would dangle."""
+    dsn = parse_dsn(TEE)
+    board = build_board(dsn)
+    real = exact_router.route_board
+
+    def grid_then_spoil(*args, **kwargs):
+        result: RouteResult = real(*args, **kwargs)
+        assert result.connection_anchors == [(), (0,)]
+        # move the first leg off the board edge so the exact check rejects it
+        net, wires, vias = result.connections[0]
+        result.connections[0] = (net, [(layer, [type(p)(p.x, p.y + 2_000_000) for p in pts])
+                                       for layer, pts in wires], vias)
+        return result
+
+    monkeypatch.setattr(exact_router, "route_board", grid_then_spoil)
+    s = dsn.resolution.value
+    exact = exact_router.route_board_exact(
+        board,
+        trace_width=round(_rule_width_dsn(dsn) * s),
+        clearance=round(_rule_clearance_dsn(dsn) * s),
+    )
+    assert len(exact.result.failed) == 2  # the leg and the T hanging on it
+    assert not exact.result.wires
+
+
+@pytest.mark.parametrize("tree_nets", [True, False])
+def test_occupancy_stays_honest(tree_nets):
+    router = _router(tree_nets)
+    router.route()
+    conns = router._conns
+    assert all(conns[i].routed for i in router._cell_owner.values())
+    for anchor, hanging in router._dependents.items():
+        for i in hanging:
+            assert conns[i].routed and conns[anchor].routed
+
+
+# P1-P2 along the top, P3 far off to the lower right, P4 just under the
+# middle of the P1-P2 leg.
+CHAIN_TEE = TEE.replace(
+    """      (place P3 100000 -70000 front 0)
+""",
+    """      (place P3 190000 -90000 front 0)
+      (place P4 100000 -40000 front 0)
+""",
+).replace("(pins P1-1 P2-1 P3-1)", "(pins P1-1 P2-1 P3-1 P4-1)")
+
+
+def test_a_tee_depends_on_every_connection_back_to_its_group():
+    """Joined as P1-P2, P2-P3, P3-P4, P4's connection tees onto P1-P2 copper,
+    which reaches P3's group only through P2-P3. Ripping P2-P3 must take the T
+    too, or it would be counted routed while cut off from P3."""
+    router = _router(text=CHAIN_TEE)
+    conns = router._conns = router._build_connections()
+    groups = {c.a.component_ref: c.a_group for c in conns}
+    groups.update({c.b.component_ref: c.b_group for c in conns})
+    for conn, (a, b) in zip(conns, (("P1", "P2"), ("P2", "P3"), ("P3", "P4")), strict=True):
+        conn.a_group, conn.b_group = groups[a], groups[b]
+    for conn in conns:
+        assert router._try_route(conn, conns)
+    first, second, third = conns
+    assert third.path[0] in first.copper  # the T lands on the far leg
+    assert third.anchors == {first.index, second.index}
+    assert router._with_dependents([second], conns) == [second, third]

tests/route/test_window_reroute.py

@@ -0,0 +1,128 @@
+"""Window re-route: a finer grid around a stuck connection, kept only when
+it leaves fewer connections unrouted."""
+
+from __future__ import annotations
+
+from freeroute.board import build_board
+from freeroute.dsn import parse_dsn
+from freeroute.geometry import IntBox
+from freeroute.route.grid_router import GridRouter
+from freeroute.route.pipeline import _rule_clearance_dsn, _rule_width_dsn, route_dsn_board_exact
+
+
+def _slot(gap: int = 640, far: bool = False) -> str:
+    """A wall across the board with a slot in it. A trace fits the slot
+    only along a narrow band of heights that the board's 1x grid has no row
+    in and a 4x grid does. ``far`` adds a second net nowhere near the wall."""
+    yc = -5000
+    lo, hi = yc - gap // 2, yc + gap // 2
+    extra_place = "(place Q1 2000 -1000 front 0) (place Q2 6000 -1000 front 0)" if far else ""
+    extra_net = "(net M (pins Q1-1 Q2-1))" if far else ""
+    return f"""(pcb "slot.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)))
+    (boundary (path pcb 0  0 0  20000 0  20000 -10000  0 -10000  0 0))
+    (keepout "" (rect F.Cu 9000 -10000 11000 {lo}))
+    (keepout "" (rect F.Cu 9000 {hi} 11000 0))
+    (rule (width 200) (clearance 200))
+  )
+  (library
+    (padstack Rect_Pad (shape (rect F.Cu -100 -100 100 100)) (attach off))
+    (image PAD (pin Rect_Pad 1 0 0))
+  )
+  (placement
+    (component PAD
+      (place P1 3000 {yc} front 0)
+      (place P2 17000 {yc} front 0)
+      {extra_place}
+    )
+  )
+  (network
+    (net N (pins P1-1 P2-1))
+    {extra_net}
+    (class default (rule (width 200) (clearance 200)))
+  )
+  (wiring)
+)
+"""
+
+
+def _route(text: str, rounds: int, **window):
+    exact, _scale, _layers = route_dsn_board_exact(
+        parse_dsn(text), resolution=1, window_reroute=rounds, window_resolution=4, **window,
+    )
+    return exact.result
+
+
+def test_the_board_grid_misses_the_slot_and_a_finer_window_finds_it():
+    plain = _route(_slot(), 0)
+    assert len(plain.failed) == 1
+    windowed = _route(_slot(), 1)
+    assert windowed.failed == []
+    assert windowed.wires  # and the copper it found is in the result
+
+
+def test_a_window_that_cannot_help_leaves_the_board_as_it_was():
+    plain = _route(_slot(gap=500, far=True), 0)  # too narrow for any grid
+    windowed = _route(_slot(gap=500, far=True), 2)
+    assert len(windowed.failed) == len(plain.failed) == 1
+    assert windowed.wires == plain.wires
+    assert windowed.vias == plain.vias
+
+
+def test_copper_outside_the_window_is_kept_as_it_was():
+    plain = _route(_slot(far=True), 0)
+    windowed = _route(_slot(far=True), 1)
+    assert windowed.failed == []
+    far_net = 2  # M, the second net in the DSN
+    assert windowed.wires[far_net] == plain.wires[far_net]
+
+
+def test_a_router_limited_to_some_nets_and_a_box_builds_only_those():
+    dsn = parse_dsn(_slot(far=True))
+    s = dsn.resolution.value
+    board = build_board(dsn)
+    whole = GridRouter(board, trace_width=round(_rule_width_dsn(dsn) * s),
+                       clearance=round(_rule_clearance_dsn(dsn) * s), orthogonal=True)
+    part = GridRouter(board, trace_width=round(_rule_width_dsn(dsn) * s),
+                      clearance=round(_rule_clearance_dsn(dsn) * s), orthogonal=True,
+                      only_nets=frozenset({2}), bounds=IntBox(0, -20000, 80000, 0))
+    assert {c.net_no for c in whole._build_connections()} == {1, 2}
+    assert {c.net_no for c in part._build_connections()} == {2}
+    assert part.cols * part.rows < whole.cols * whole.rows
+
+
+def test_a_spent_budget_starts_no_window():
+    assert len(_route(_slot(), 1, window_budget=0.0).failed) == 1
+    assert _route(_slot(), 1, window_budget=1000.0).failed == []
+
+
+def test_window_board_keeps_far_items_of_the_rerouted_nets_only():
+    from freeroute.route.window import _item_box, _window_board
+
+    board = build_board(parse_dsn(_slot(far=True)))
+    items = [(item, _item_box(item)) for item in board.get_items()]
+    view = IntBox(80000, -60000, 120000, -40000)  # around the slot, far from Q1/Q2
+    sub = _window_board(board, items, view, {1}, {}, set(), {}, 100, 300, 300, [0], "via")
+    refs = {p.component_ref for p in sub.get_pins()}
+    assert {"P1", "P2"} <= refs  # net N's pins, though outside the view
+    assert not refs & {"Q1", "Q2"}  # net M's, far away, left out
+
+
+def test_a_connection_ending_outside_the_window_gets_no_copper():
+    """Its far end has no grid cells; a stub out to it would cross items the
+    window board never saw."""
+    from freeroute.route.exact_router import route_board_exact
+
+    dsn = parse_dsn(_slot(far=True))
+    s = dsn.resolution.value
+    window = IntBox(70000, -70000, 130000, -30000)  # the slot only; net M's pins are far off
+    result = route_board_exact(
+        build_board(dsn), trace_width=round(_rule_width_dsn(dsn) * s),
+        clearance=round(_rule_clearance_dsn(dsn) * s), only_nets=frozenset({2}), bounds=window,
+    ).result
+    assert [f[0] for f in result.failed] == [2]
+    assert not result.wires.get(2) and not result.vias.get(2)

tests/test_cli.py

@@ -158,7 +158,10 @@ def test_cli_supported_combinations_are_accepted(tmp_path):
         "orders": ["--orders", "2"],
         "promote": ["--promote-failures", "2"],
         "access": ["--access-cost", "5"],
+        "negotiate": ["--negotiate", "2"],
         "rollback": ["--no-rollback"],
+        "tree": ["--no-tree"],
+        "window": ["--window-reroute", "1"],
     }
     for engine, options in ENGINE_OPTIONS.items():
         for option in options: